Deterministic Prediction in Progressive Coding

Abstract

Deterministic prediction in progressive coding of images is investigated. Progressive coding first creates a sequence of resolution layers by beginning with an original image and reducing its resolution several times by factors of some natural number M. Next, the resultant layers are losslessly encoded. The lowest-resolution layer is encoded first, then each higher resolution image is encoded incrementally upon the previous, until the original image is finally encoded. Coding efficiency may be improved if knowledge of the rules which produced the lower-resolution image of each pair is used to deterministically predict pixels of the higher, so they need not be encoded. This problem is addressed: given reduction rules expressing each low-resolution pixel as a function of nearby high-resolution pixels and previously-generated low-resolution pixels, find a complete set of rules, each of which deterministically predicts the value of a high-resolution pixel when certain values are found in nearby low-resolution pixels and previously-coded high-resolution pixels. It is shown that this problem is NP-Complete, then propose a recursive algorithm for solving it in optimal time as a depth-first tree search. The extent of prediction is shown to vary depending on the sequence order in which the pixels are processed; upper bounds on predictability are proven and are demonstrated how to find the optimal order. Reduction rules taking their inputs from an area of pixels larger than M × M are shown to exhibit an interdependence between their input pixels such that certain combinations are impossible; a use of this interdependence in a compound prediction that further enhances predictability is demonastrated. This work serves as a basis for both working software implementation and for future research into unsolved problems, which are identified. © 1993 IEEE.