- Main
Every discrete, finite image is uniquely determined by its dipole histogram
Abstract
A finite image I is a function assigning colors to a finite, rectangular array of discrete pixels. Thus, the information directly encoded by I is purely locational. Such locational information is of little visual use in itself: perception of visual structure requires extraction of relational image information. A very elementary form of relational information about I is provided by its dipole histogram DI. A dipole is a triple, ((dx, dy), alpha, beta), with dx and dy horizontal and vertical, integer-valued displacements, and alpha and beta colors. For any such dipole, DI((dx, dy), alpha, beta) gives the number of pixel pairs ((x1, y1), (x2, y2)) of I such that I[x1, y1] = alpha, I[x2, y2] = beta, and, (x2, y2) - (x1, y1) = (dx, dy). Note that DI explicitly encodes no locational information. Although DI is uniquely determined by (and easily constructed from) I, it is not obvious that I is uniquely determined by DI. Here we prove that any finite image I is uniquely determined by its dipole histogram, DI. Two proofs are given; both are constructive, i.e. provide algorithms for reconstructing I from DI. In addition, a proof is given that any finite, two-dimensional image I can be constructed using only the shorter dipoles of I: those dipoles ((dx, dy), alpha, beta) that have magnitude of dx < or = ceil((# columns in I)/2) and magnitude of dy < or = ceil((# rows in I)/2), where ceil(x) denotes the greatest integer < or = x.
Many UC-authored scholarly publications are freely available on this site because of the UC's open access policies. Let us know how this access is important for you.
Main Content
Enter the password to open this PDF file:
-
-
-
-
-
-
-
-
-
-
-
-
-
-