Vector quantization and nearest neighbor clustering with applications to image compression and data visualization

Modern digital image acquisition systems are compiling vast stores of raw image data. There is a need for techniques that assist users in browsing and analyzing large imagery databases. Data compression is an important aspect of image retrieval and transmission systems. We review vector quantization (VQ) as a technique for image compression, in the context of a digitized map retrieval system. Then we consider clustering algorithms for vector quantization codebook design. We develop a family of seven clustering algorithms that use a nearest-neighbor merging philosophy and share common data structures. These algorithms embody two algorithm design strategies: incremental construction and refinement, and agglomerative reduction. The algorithms are evaluated extensively for image compression. The best of these new algorithms are found to surpass the generalized-Lloyd optimization algorithm in rate-distortion performance for spatial VQ. Other members of the algorithm family offer improvements in running-time performance and memory requirements. The new clustering algorithms are applied to color quantization of imagery. Using a color-space transformation and edge-detector masking, we are able to automatically generate high-quality color look-up tables that are smaller than previously reported. We develop a new asymmetric model for vector quantization in transform domains. The proposed asymmetric processing model improves visual quality, and eliminates performance barriers for applications in interactive data exploration. Finally, we present vector quantization as a tool that aids in the exploration, visualization, and understanding of large multivariate imagery data sets. We apply this display technique to represent hundreds of multivariate data values per image pixel.