Based On Affinity Propagation Clustering The Context Model Quantization Algorithm Research

Due to the rapid development of computer hardware and abroad using of arithmetic coding, high order context model arithmetic coding becomes more popular and implementable in entropy coding. Literally, higher order of context model would achieve shorter code length. However, since the conditional distribution of the high order context model would not always converge, even large scales of data were used to train these distributions. Poor estimation of the conditional distributions will lead to a lower coding efficiency. Thus the expected benefit of high order context model will be compromised. This is called'context dilution'or'model cost'. Besides, high order context model introduces geometric-increasing computation complexity and memory consumption.An effective approach to solve the'model cost'problem and to realize the coding scheme is to quantize the high order context model, which is by sorting and merging certain context conditional distributions conformed to some particular rules to obtain a much simpler context model with lower quantization distortion.Some researchers proved when an appropriate distortion measure was selected, the optimal context model quantizing problem was equal to a common vector quantization problem, so that a Lloyd style algorithm or K-means clustering algorithm could obtain the optimal quantized context model.Then two problems follows:How do we know a clustering algorithm such as Lloyd style algorithm would find the global optimal quantized context model when the number of clusters is specified, since most clustering algorithm has been suffering from many local optimal solutions? Secondly, how many clusters are there due to this particular vector quantization problem.We study a state-of-art clustering algorithm called Affinity Propagation Clustering. Great efforts have been made to utilize this clustering algorithm in context model quantization problem and we propose an algorithm called Context model Quantization base on Affinity Propagation Clustering.Several experiments suggest the new context model quantization scheme can solve the 'model cost'problem better than the Lloyd style algorithm with lower computation complexity. This algorithm is also capable of finding the near-optimal number of clusters during context model quantization.