Proceedings Article | 3 March 1995
KEYWORDS: Image compression, Data modeling, Computer programming, Image processing, Binary data, Modeling, Error analysis, Switching, Mathematical modeling, Receivers
Given a finite sequence x1, x2, .. . , x, the essential problem in lossless data compression is to process the symbols in some order and assign a conditional probability distribution for the current symbol based on the previously processed symbols [44]. For example, if we are to process x1, x2, .. . , x in a sequenal manner [53] then we need to estimate the distributions p(x+iIxi, x2, . . . , xe), 1 < j < fl The number of bits needed to optimally encode the sequence x1, . . , x, is then given by
—log flp(x+iIx,...,x).
Coding techniques that can encode the sequence at rates close to the optimal are known [43]. Hence, higher the probabilities assigned in the above product, the lesser the number of bits that are needed to encode the sequence. A model, in this context is then simply a scheme for assigning conditional probability distributions [53]. Clearly, it is the model that determines the rate at which we can encode the sequence. Hence the critical task in lossless data compression is finding good models for the data under consideration. Finding good models for a given data set is a difficult problem. In lossless compression applications some structure is usually imposed on the data in the form offinile-state models, Markov-models, tree-models, finiie-con1ex models etc to make the problem mathematically and/or computationally tractable. Algorithms are then designed that encode the given data, in an optimal or sub-optimal manner. Algorithms that 'learn' the parameters of the model that best describes the data and achieve rates that are asymptotically optimal are known as oplimal universal coding schemes. Such schemes have been applied very successfully in text or string compression applications. Unfortunately, universal coding schemes and other standard modelling techniques do not work well in practice when applied to gray-scale image data.
