Every discrete, finite image is uniquely determined by its dipole histogram

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 D-I. A dipole is a triple, ((d(x), d(y)), alpha, beta), with d(x) and d(y) horizontal and vertical, integer-valued displacements, and alpha and beta colors. For any such dipole, D-I((d(x), dy), alpha, beta) gives the number of pixel pairs ((x(1), y(1)), (x(2), y(2))) of I such that I[x(1), y(1)] = alpha, I[x(2), y(2)] = beta, and, (x(2), y(2)) - (x(1), y(1)) = (d(x), d(y)). Note that D-I explicitly encodes no locational information. Although D-I is uniquely determined by (and easily constructed from) I, it is not obvious that I is uniquely determined by D-I. Here we prove that any finite image I is uniquely determined by its dipole histogram, D-I. Two proofs are given; both are constructive, i.e. provide algorithms for reconstructing I from D-I. 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 ((d(x), d(y).), alpha, beta) that have \d(x)\ less than or equal to ceil((# columns in I)/2) and \d(y)\ less than or equal to ceil(( # rows in I)/2), where ceil(x) denotes the greatest integer less than or equal to x. (C) 2000 Published by Elsevier Science Ltd. All rights reserved.