Fixed binary linear quadtree coding scheme for spatial data

In this paper, a new linear quadtree construction based on a binary coding is proposed. The proposed fixed binary linear quadtree (FBLQ) coding scheme emphasizes the reduction of bit string to encode spatial data. The decomposition discrimination process is designed to separate data representation in two lists. In the decomposition discrimination process, identifier list is first used to indicate whether or not four subquadrants of a decomposition should be further decomposed. Once a subquadrant is found to have uniform intensity, i.e. the region is of either object or background, a bit of either one or zero is inserted to the color list. With the usage of both identifier and color lists, a compact storage is derived to code spatial data on a binary image. Two sets of binary images with various resolution factors are tested in the experiments; a theoretic analysis for the image in the worst case is also derived. Both empirical results and theoretic analysis demonstrate that the proposed FBLQ coding scheme has the smallest storage space among all other three methods.