title: 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.
authors.affiliation: Department of Cognitive Sciences SSPA-3, University of California at Irvine 92697-5100, USA. cfchubb@uci.edu
authors.forename: C
authors.initials: C
authors.lastname: Chubb
authors.forename: J I
authors.initials: JI
authors.lastname: Yellott
mesh_terms: D000465:Algorithms; D003118:Color Perception; D006801:Humans; D008960:Models, Psychological; D010364:Pattern Recognition, Visual; D011601:Psychophysics