Modified Metropolis annealing algorithm for QM-AYA arithmetic Coder design optimization

Abstract

The QM-Coder is an adaptive binary arithmetic coder for the JPEG and JBIG image compression standards. This coder employs a probability estimation state table (finite state machine). The present state corresponds to the current probability estimate. The estimate takes the form of the augend value that (on encode) is added to the code string if the less probable symbol occurs. The state changes only if the arithmetic coder experiences a renormalization. The QM-AYA coder is derived from the Q-Coder and the QM-Coder. A modified Metropolis method was used to fine-tune the QM-AYA augend values for improved compression performance. Heuristics in the search strategy to determine the next change in augend values reduced the estimated 54 year run time of the generalized annealing algorithm to 4 weeks.