Mumbai university > Electronics and telecommunication Engineering > Sem 7 > Data compression and Encryption

Marks: 10

Years: May 2016

1. Approach I: This is appropriate for bi-level images. A pixel in such an image is represented by one bit. Applying the principle of image compression to a bi-level image therefore means that the immediate neighbours of a pixel P tend to be identical to P. Thus, it makes sense to use run length encoding (RLE) to compress such an image.

2. Approach 2: The neighbour of a pixel tend to be similar to the colour C [where C is either black or white], then pixel of the same colour seen in the past tend to have the same immediate neighbours. This approach looks at n of the near neighbours of the current pixel and considers them an n-bit number. This approach is used by JBIG.

3. Approach 3: Separate the grayscale image into n-bit level images and compress each with RLE and prefix codes. The principle of image compression seems to imply intuitively that two adjacent pixels that are similar in the grayscale images will be identical in most of the n bit level images.

4. Approach 4: Use the context of a pixel to predict its value. The context of a pixel is the value of some of its neighbours. The principle of image compression tells us that our prediction will be correct in most cases, almost correct in many cases and completely wrong in a few cases. This is used in MLP method.

5. Approach 5: Transform the values of the pixels and encode the transformed values. The compression is achieved by reducing or removing redundancy. The redundancy of an image is caused by the correlation between pixels, so transforming the pixels to a representation where they are de-correlated eliminates the redundancy. In a highly correlated image, the pixels tend to have equi-probable values which results in maximum entropy. If the transformed pixels are de-correlated certain pixel values become common thereby having large probabilities while others are rare. This results in small entropy. Quantizing the transformed values can produce efficient lossy image compression.

6. Approach 6: The principle of this approach is to separate a continuous tone colour image unto three grayscale images and compress each of the three separately using approaches 3, 4 or 5.An important feature is to use a luminance chrominance colour representation as the eye is sensitive to small changes in luminance but not in chrominance. This allows the loss of considerable data in the chrominance components while making it possible to decode the image without a significant visible loss of quality.

7. Approach 7: A different approach is needed for discrete tone images. A possible way to compress such an image is to scan it, identify regions and find repeating regions. If region B is identical to an already found region A then it can be compressed by writing a pointer to A on the compressed stream. The block decomposition method (FABD) is an example of how this approach can be implemented.

8. Approach 8: Partition the image into parts and compress it by processing the parts one by one. Suppose that the next unprocessed image part is part no. 15. Try to match it with parts 1-14 that have already been processed. If part 15 can be expressed for example as a combination of parts 5 (scaled) and 11 (rotated) then only the few part 15 can be discarded. If part can’t be expressed as a combination of already processed parts, it is declared processed and is saved in raw format.

JPEG-LS:

1. JPEG-LS is a new standard for the lossless compression of continuous tone images. JPEG-LS examines several of the previously seen neighbours of the current pixel, uses them as the context of the pixel, uses the context to predict the pixel and to select a probability distribution out of several such distributions, and uses that distribution to encode the prediction error with a special Golomb code. There is also a run mode where the length of a run of identical pixels is encoded.

2. The encoder examines the context pixels and decides whether to encode the current pixel ‘x’ in the run mode or the regular mode.

3. If the context suggests that the pixels y, z …. Following the current pixel are likely to be identical, the encoder selects the run mode otherwise it selects the regular mode. The rest of the encoding process depends on the mode selected.

4. In the regular mode, the encoder uses the values of context pixels a, b and c to predict pixel ‘x’ and subtracts the prediction from x to obtain the prediction error. This error is then corrected by a term that depends on the context and encoded with a Golomb code.

5. The Golomb coding depends on all 4 pixels of the context and also on prediction errors that were previously encoded for the same context.

6. In the run mode, the encoder starts at the current pixel ‘x’ and finds the longest run of pixels that are identical to context pixel ‘a’.

7. The encoder does not extend this run beyond the end of the current image row. Since all pixels in the run are identical to a, only the length of the run needs to be encoded and this is done with a 32 entry array denoted by J. If near lossless compression is used, the encoder selects a run of pixels that are done to a within the tolerance parameter NEAR.

8. The decoder is not substantially different from the decoder, so JPEG-LS is nearly symmetric compression method. The compressed stream contains data segments, marker segments and markers.

9. A marker is a byte of all ones followed by a special code, signalling the start of a new segment. If a marker is followed by a byte whose most significant bit is 0, that byte is the start of a marker segment. Otherwise, that byte starts a data segment.

10. Advantage of JPEG-LS:

• JPEG-LS is capable of lossless compression.

• JPEG-LS has very low computational efficiency.