Multi-Variable Context Modeling Based On Dynamic Programming

In entropy coding systems based on the context modeling, which is served as an important method to estimate the probability mdodels of sources, three continuous procedures are required to implement context modeling:selecting context templates, estimating conditional probability distributions and conducting context quantization. And the "context dilution" problem introduced by high-order context models needs to be allviated by the context quantization to achieve the desired compression gain, which is our research emphasis.The essence of context quantization is to reduce the amount of conditional probability distributions used to characterise the probability modles. And there are two major research directions:one is to decrease directly the amount by using clustering algorithms to merge the similar conditional probability distributions in the space of the probability distributions; the other is to reduce the number of possibble values of the condition samples in the context fields in order to implement the context quantization. Currently, with the in-depth research of clustering thoughts and the succesive emergence of clustering algorithms, the research of Context quantization has made great progress in the first research direction, but the context modeling algorithms that performed in the context-condition fields are deficient. Therefore, in this paper, a new algorithm is proposed to implement Context Quantization in the space of context conditions by Minimizing the Description Length (MDLCQ), which only applies to the source sequences whose samples have numerical peculiarity.With the description length as the evaluation criterion in the MDLCQ algorithm, the Context Quantization of Single-Condition (CQOSC) is attained by the dynamic programming algorithm. And then the CQOSC algorithm is extended up to the multi-condition context models, so the context quantizer of multi-conditions can be designed by the iterated application of CQOSC. This algorithm can not only design the optimized context quantizer for multi-valued soures, but also determine adaptively the importance of every condition so as to design the best order of the model. Thus a good context-model optimization effect is provided by the MDLCQ algorithm.The performance of MDLCQ algorithm was validated through experimental analysis in this paper. The results show that context quantizer designed by MDLCQ algorithm can not only achieve the expected quantitative effect, but also improve significantly the compression performance of the entropy coding system.