IMAGE COMPRESSION
 
Image compression takes advantage of sampling and quantization when encoding images. This is because in images we can try to represent the same thing, or at least a "good" approximation, without sending the whole information (UxVxBits). In other words, we can allow a a certain amount of distortion when decoding the image. This is the main thing one must know in image compression. This is known by most people by "Lossy Compression".

Another nice important thing is that in pictures it's important to represent the image by UNCORRELATED data. For making it we should study reversible linear transformations. That is: Karhunen-Loève, Hadamard, Fourier, cosine, ... and other transforms. These transforms will make the job we want: uncorrelate the picture.

Why I should uncorrelate the picture? Try to think for a short time and I'm sure you will notice that uncorrelating process 'shrinks' a lot the  levels of the original image.
 
I'm very interested in image schemes for compressing digital images. I was for 2 years studying several techniques for doing so. One of the latest algorithm I studied was BTC (Block Truncation Code). This scheme is not very well known for most people in inet...

<< BTC is a (new? 1979 is far) image compression scheme that was proposed
by Delp and Mitchell, whose perfomance is comparable to the DTC, but
which has a much more simpler hardware implmentation.

In Block Truncation Code, an image is, firstly, segmented into NxN blocks
of pixels. Well, in the most cases the size is 4x4, but we can choose other
size as 8x8... Sencondly, a two level output is choosen for every block and
bitmap is also encoded using 1 bit for every pixel.

The main idea is that the two levels are selected independently for every
NxN block. So, encoding the block is a simple binarization process because
every pixel of the block is truncated to 1 or 0 binary representation choosing
the reconstruction level(the two level output)..........>>

The last text is pasted from the DOC I wrote a few months in which I explained the BTC encoder/decoder giving a little piece of source to start with.
 

Click here to download the BTCDOC.ZIP(7kb)
 
In order to 'figure' in the statistic sense, here's a table containing real experiments with a BTC scheme (first note that bpp=bits per pixel, RMSE stands for Root Mean Square Error and it's a numerical distortion measure):
 
 
 Scheme
Bit rate
LISAW
(RMSE)
BTC
2.00 bpp
3.33
BTC-I
2.00 bpp
3.37
BTC
1.25 bpp
4.95
BTC-I
1.25 bpp
4.03
 
 
 
Original Block
Decoded Block (after quantizing)
(binarization process is evident here)
 

In despite its apparent binarized contourn, BTC scheme will not blur the image(as others methods), nor will give a 'blocky aspect' to the decoded image as DCT-JPEG does.
Its simple implementation on hardware and its low computation makes BTC interesting for many applications.

Btw, actually i'm developing 'optimal quantizers' and I must read more about this 
so if you have some texts about it, email me.  I started with the Lloyd-Max algo. (not the generalized one which is used in vector quantization). After a few days making some maths (ie: partially differentiation of the mean-square error introduced when quantizing a continuous tone image to a discrete one), I implemented the algo. and this did not work as I expected. So I myself coded a NEW quantizer based both on visual & statistical criterion. Unfortunately, the algo will work correctly with a gaussian distribution levels in the image since it takes advantage of the properties of the Normal Distribution. heck, also the visual impact is involved. The debate continues in WHICH is the best quantizer  make for encoding predictive image data.
 

A Word about the Lloyd-Max quantizer algorithm

The Lloyd-Max algorithm is a quantizer that minimizes the mean-square error between the image input and the image ouput, ie: the quantizer values. I'll give the 2 formulas used in for determining the ouput levels and the decision levels. How finding these formulas is quite easy since it's only a partial derivation exercise. As you probably will notice the 2 formulas do NOT form a closed solution... they must be solved using numerical rules. I know two ways for solving the system.
The 1st equation gives us the decision levels and 2nd the output levels. For solving it you can use this iterative method:

            Step 0:  Choose an arbitrary set of values for 'Zi's.

            Step 1:  For this set of values, find the following 'Qi's using the 2nd equation.
            Step 2: Now, use the 1st equation to obtain the 'Zi's.
            Step 3: Goto Step 1 if, and only if, the difference between two consecutive 'Qi's is below
                        a threshold. (Check a fine Threshold to achieve good perfomance for the quantizer).

Lloyd-Max quantizer is very useful in digital image processing because its properties for quantizing images and so, for encoding images with no considerable degradation. There exists some others quantizers one can choose instead Lloyd-Max. Some are based on visual criteria. In fact, a few days ago I developed one for encoding the 'differential data' of a lossy predictive encoder.
 
                                    (1)
             (2)

 
 
Subscribe to Digital Image Processing
Enter your e-mail address: 
img-proc Archive
An e-group hosted by FindMail's eGroups.com
 
 
 
 
 
1