Classification and Compression of Multi-Resolution Vectors: A Tree Structured Vector Quantizer Approach

Abstract

Tree structured classifiers and quantizers have been used withgood success for problems ranging from successive refinement coding of speechand images to classification of texture, faces and radar returns. Althoughthese methods have worked well in practice there are few results on thetheoretical side.<p> We present several existing algorithms for tree structured clustering using multi-resolution data and develop some results on their convergenceand asymptotic performance.<p> We show that greedy growing algorithms will result in asymptoticdistortion going to zero for the case of quantizers and prove terminationin finite time for constraints on the rate. We derive an online algorithmfor the minimization of distortion. We also show that a multiscale LVQalgorithm for the design of a tree structured classifier converges to anequilibrium point of a related ordinary differential equation.<p>Simulation results and description of several applications are used toillustrate the advantages of this approach.