There are a number of techniques used to represent binary image data; among them are borders, arrays, skeletons, and quadtrees. This paper presents a new representation technique called TID (for Translation Invariant Data structure). The idea of the TID is simple: represent a two-dimensional binary image by its cover in maximal squares. A maximal square is a square of object pixels which is not contained in any larger size square. Squares are represented by the triple (i,j,s), where (i,j) is the northwest corner of the square and s is the size (length of each of the four sides) of the square. The total number of such triples is clearly invariant with respect to translations of the set of object pixels within the image.

The authors show that the total set of maximal squares for any binary image can be located in linear time (in the number of pixels). The total set of maximal squares may be redundant. The authors show that finding a minimal size covering set is a nonlocal (and hence nonlinear) operation, but provide a simple, local heuristic to reduce the size of the total set somewhat. Comparisons between the TID and other representation techniques are given both in terms of their storage required and the time needed to construct the representation given a two-dimensional binary image. The authors discuss some standard operations on images using the TID representation but do not compare their times when other representations are used. The authors seem most concerned about the total storage space used by the various representations, a concern which is vital in large image database applications. Only future work will show if the TID representation provides any real advantages in image processing or image database applications.