UC Irvine

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.