Comparison of line-by-line and two-dimensional encoding of random images

Most methods of encoding images require complicated implementation. Thus it is of interest to compare the transmission rates that can be achieved by classes of encoding methods of different complexity. We consider two classes of encoding operations. The first class allows any possible operation on the two-dimensional image source output. The second class allows only certain restricted operations on the image. In acquisition of images by electronic means, the image intensity is in general scanned line by line, resulting in data that appear as a sequence of ordinary time series. In encoding, a simpler implementation results if one accepts the time series from a single scan line and encodes it independently of adjacent scan lines. This limits storage requirements to a single scan line and limits processing to operations on a one-parameter time series instead of operations on a two-dimensional field. This is the second class of encoding operations that we consider. We choose a distortion measure and discuss the rate-distortion function, which represents the minimum rate required by any encoding method in the first (arbitrary complex encoding). We then derive the minimum rate that can be achieved by any encoder from the second class. These rates are compared for a specific example.