Fast Dynamic Encoding of Linear Quadtree and Its Realization

Raster data structure is one of the effective data structures to express spatial data.When raster data structure is used, the smaller the size of pixel or grid cell is, the higher resolving power of spatial data comes and the more cells with the same attribute value.This structure causes a large amount of redundant information.It is essential to compress the original raster data for the purpose of reducing the amount of data storage and the requirement of memory resource during data processing. Linear quadtree encoding is one of the significant compressing and organizing approaches for raster data.It transforms the primal raster data into a linear table.In the table, there are two columns that represent respectively the decimal Morton codes which denote the location and size of the leaf nodes of the quadtree and their corresponding attribute values.Two different traditional methods can be used to construct the linear table.They are linear-table method and pseudo-code method respectively.Both of the two methods are time-consuming and require large memory blocks when a huge raster data file is processed.It is necessary to investigate a new, fast and effective data compressing method to suit for huge raster data.Due to disadvantages of the two traditional linear quadtree encoding methods, a fast dynamic linear quadtree encoding approach (FDLQE) is put forward in this paper.This method can construct linear quadtree directly through only once tracing of the whole raster data.It uses a dynamic stack instead of linear table or one-dimensional array.FDLQE takes the decimal Morton code and its corresponding attribute value of a pixel or a homogeneous region as a record.It once uses a 2×2 window to extract 4 sequential pixels from the original raster data according to their decimal Morton codes, compares whether their attribute values are the same.If the attribute values of the pixels are the same, the 4 pixels can be combined into a node and the smallest decimal Morton code and its corresponding attribute value are pushed into the stack as one record.Otherwise, they are all taken as records and pushed into the stack.The point to the top of the stack is recorded.The top record is examined together with other records previously pushed into in the stack whether they can be united to form upper nodes synchronously.When the pixels of the raster data are traced over, the records remained in the stack are just the linear quadtree encoding result. The algorithm of FDLQE approach is realized on a Pentium Ⅱ233 micro-computer with V C ++ program language.For the purpose of comparing the encoding efficiency between FDLQE and linear-table method or pseudo-code method, the running speed and memory requirement are taken as the comparing index.The testing result shows that FDLQE is superior to linear-table method or pseudo-code method in both indexes.The larger the raster data is, the more obvious advantages FDLQE has over the other two conventional encoding methods.