Row-Major Scheduling of Image Decoders

摘要

Image decoding based on Markov source models involves computing a set ofrecursively-defined likelihood functions at each point of the image plane. One of the central issues in decoder implementation is determining a sequence for these computations which is consistent with the data dependencies implied by the model. The paper presents an approach to decoder scheduling based on linear scheduling theory, as developed for the implementation of regular iterative algorithms on parallel processor arrays. A particular form of linear schedule, the row-major schedule, is proposed for decoding images in a row-wise fashion, from top to bottom. Theoretical bounds and constraints on the parameters of a valid row-major schedule are derived. Decoder storage requirements are analyzed and an approach is developed for optimizing schedule parameters for minimum storage by linear programming. Two scheduling algorithms are presented and illustrated using several image models, including simple text and printed music notation. (Copyright (c) 1992 Xerox Corporation.)