A quadtree normalization scheme based on cyclic translations

An image can be represented by a compact and hierarchical structure, i.e. a quadtree. The storage requirements of an image constructed by a quadtree is highly sensitive to its position. Ang and Samet Pattern Recognition Lett. 15(1), 57–63 (1994)] proposed an algorithm capable of normalizing a quadtree in O(s²log₂s) time and O(s²) space, where s is the length of the image grid, such that the number of nodes of the quadtree after normalization can be minimal. However, s is twice as long as the length of one side of the image to be normalized. In this study, we propose a normalization scheme based on cyclic translations. The time complexity and the space requirements of this scheme have four times less than those in Ang and Samet's case. In addition, no translation is necessary to fit the image into the northwest quadrant of the grid before the process of normalization. Also, this scheme can normalize a quadtree to obtain less node numbers than that of Ang and Samet. Furthermore, if the image's four corners have the same color, the amount of reduction for node number becomes larger after cyclic translations; it can occasionally reach to 75%. The analytical and empirical results demonstrate the advantages of this scheme.