Deterministic prediction in progressive coding

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. The resultant layers are losslessly encoded, beginning with the lowest-resolution layer and, then encoding each higher resolution image incrementally upon the previous one. 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. Given reduction rules expressing each low-resolution pixel as a function of nearby high-resolution pixels and previously generated low-resolution pixels, it is shown that finding 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, is NP-complete. A recursive algorithm for solving the problem in optimal time as a depth-first tree search is proposed, and the characteristics of the resultant prediction process are studied