Classification and Compression of Multi-Resolution Vectors: A Tree Structured Vector Quantizer Approach
December 01, 2002
Tree structured classifiers and quantizers have been used with good success for problems ranging from successive refinement coding of speech and images to classification of texture, faces and radar returns. Although these methods have worked well in practice there are few results on the theoretical side. We present several existing algorithms for tree structured clustering using multi-resolution data and develop some results on their convergence and asymptotic performance. We show that greedy growing algorithms will result in asymptotic distortion going to zero for the case of quantizers and prove termination in finite time for constraints on the rate. We derive an online algorithm for the minimization of distortion. We also show that a multiscale LVQ algorithm for the design of a tree structured classifier converges to an equilibrium point of a related ordinary differential equation. Simulation results and description of several applications are used to illustrate the advantages of this approach.