Video Compression: What is discrete cosine transform?

Question

I've implemented an image/video transformation technique called discrete cosine transform. This technique is used in MPEG video encoding. I based my algorithm on the ideas presented at the following URL:

http://vsr.informatik.tu-chemnitz.de/~jan/MPEG/HTML/mpeg_tech.html

Now I can transform an 8x8 section of a black and white image, such as:

0140  0124  0124  0132  0130  0139  0102  0088  
0140  0123  0126  0132  0134  0134  0088  0117  
0143  0126  0126  0133  0134  0138  0081  0082  
0148  0126  0128  0136  0137  0134  0079  0130  
0147  0128  0126  0137  0138  0145  0132  0144  
0147  0131  0123  0138  0137  0140  0145  0137  
0142  0135  0122  0137  0140  0138  0143  0112  
0140  0138  0125  0137  0140  0140  0148  0143 

Into this an image with all the important information at the top right. The transformed block looks like this:

1041  0039  -023  0044  0027  0000  0021  -019  
-050  0044  -029  0000  0009  -014  0032  -010  
0000  0000  0000  0000  -018  0010  -017  0000  
0014  -019  0010  0000  0000  0016  -012  0000  
0010  -010  0000  0000  0000  0000  0000  0000  
-016  0021  -014  0010  0000  0000  0000  0000  
0000  0000  0000  0000  0000  0000  0000  0000  
0000  0000  -010  0013  -014  0010  0000  0000  

Now, I need to know how can I take advantage of this transformation? I'd like to detect other 8x8 blocks in the same image ( or another image ) that represent a good match.

Also, What does this transformation give me? Why is the information stored in the top right of the converted image important?

Answer 1

If I remember correctly, this matrix allows you to save the data to a file with compression.

If you read further down, you'll find the zig-zag pattern of data to read from that final matrix. The most important data are in the top left corner, and least important in the bottom right corner. As such, if you stop writing at some point and just consider the rest as 0's, even though they aren't, you'll get a lossy approximation of the image.

The number of values you throw away increases compression at the cost of image fidelity.

But I'm sure someone else can give you a better explanation.

Answer 2

The result of a DCT is a transformation of the original source into the frequency domain. The top left entry stores the "amplitude" the "base" frequency and frequency increases both along the horizontal and vertical axes. The outcome of the DCT is usually a collection of amplitudes at the more usual lower frequencies (the top left quadrant) and less entries at the higher frequencies. As lassevk mentioned, it is usual to just zero out these higher frequencies as they typically constitute very minor parts of the source. However, this does result in loss of information. To complete the compression it is usual to use a lossless compression over the DCT'd source. This is where the compression comes in as all those runs of zeros get packed down to almost nothing.

One possible advantage of using the DCT to find similar regions is that you can do a first pass match on low frequency values (top-left corner). This reduces the number of values you need to match against. If you find matches of low frequency values, you can increase into comparing the higher frequencies.

Hope this helps

Answer 3

I'd recommend picking up a copy of Digital Video Compression - it's a really good overview of compression algorithms for images and video.

Answer 4

I learned everything I know about the DCT from The Data Compression Book. In addition to being a great introduction to the field of data compression, it has a chapter near the end on lossy image compression which introduces JPEG and the DCT.

Answer 5

Anthony Cramp's answer looked good to me. As he mentions the DCT transforms the data into the frequency domain. The DCT is heavily used in video compression as the human visual system is must less sensitive to high frequency changes, therefore zeroing out the higher frequency values results in a smaller file, with little effect on a human's perception of the video quality.

In terms of using the DCT to compare images, I guess the only real benefit is if you cut away the higher frequency data and therefore have a smaller set of data to search/match. Something like Harr wavelets may give better image matching results.

Answer 6

Just for general knowledge. Let's say I keep 25% of the DCT Coefficients (Low Frequencies) and zero out the rest.

What would give a better result, 8X8, 16X16 or 32X32 blocks?

Moreover, how should I chose the Coefficients, Top Left Square or Top Left Triangle?

Thanks.