Data compression techniques for maps

The efficiencies of various data-compression techniques as applied to color maps are compared. These color maps have certain special characteristics, such as large homogeneous regions, and fine detail, such as lines and lettering. The color maps are first classified using the K-means clustering algorithm with neighborhood classification. Three techniques are investigated, namely, contour, quadtree, and run-length coding. The run-length coding algorithm is modified to allow wrap-around of runs. A modification of the standard binary image quadtree compression algorithm for color images is introduced. In quadtree coding a modified eldest-son eldest-younger-sibling quadtree is used to reduce the memory requirement for storing the quadtree. Lempel-Ziv compression is applied to the classified and unclassified images as well as to the output of the compression algorithms. The algorithms are compared on the compression ratios achieved. The exponential behavior of the histogram of the runs indicates that runs of short run length have higher probability. Accordingly, Huffman coding of the runs would result in more efficient bit assignment and hence greater compression ratios