Two-dimensional template-based encoding for linear quadtree representation

A two-dimensional template-based encoding (2DTE) technique for linear quadtree construction is proposed. The 2DTE technique combines the concept of template mapping and the Morton sequence to encode regional data on an image. With the definition of the last homogeneous pixel, the new coding algorithm can be completed in a time linear to the number of pixels without repetitive scanning of image pixels. Compared with other linear quadtree coding methods, the proposed 2DTE technique has a linear n time reduction of storage space if a 2(n) by 2(n) image is processed. The potential of the proposed 2DTE technique for encoding multicolored images is also described. Several empirical tests and theoretical analyses verify that the proposed 2DTE technique outperforms other linear quadtree construction algorithms. The proposed 2DTE technique is believed to be profitable for applications in image processing or geographic information systems.