New two-phase spatial data structures with applications to binary images

Considering a binary image, a new two-phase representation is presented in this paper to reduce the memory requirement in the conventional tree-based spatial data structures (SDSs) such as the linear quadtree, DF-expression, S-tree representation, etc. Experimental results show that not only our proposed two-phase representation has a better memory-saving effect. but it also can speed up the coding-time when compared to the existing SDSs. We also show that our proposed two-phase representation has a better computational performance when running geometric operations, such as computing the area and the centroid, on the proposed two-phase representation directly. (C) 2003 Elsevier Science (USA). All rights reserved.