Home

This project represents a parallel implementation of the differential pulse code modulation video codec. The algorithm uses frame differencing which exploits temporal redundancy in a video sequence to achieve good compresion, as in it doesn't code each frame individually, but it codes the difference between two adjacent frames. The performance comes from the assumption that the next frame or the predicted frame will be equal to the current frame. This process is lossy because the difference between the frames lose a lot of information while going through the quantization process.

If there is little motion in the video, validating the assumption that two frames will be almost identical, the difference will be mostly uniform and easily coded. Rapid motion frames will induce poor results in the compression process.

The theory and base model for this algorithm was taken from An Introduction to Video Compression in C/C++.

The encoding process involves the following steps:

1.We read a frame from the uncompressed avi file, loaded using an OpenFileDialog. We access the frames using the library offered by Corinna John, A Simple C Wrapper for the AviFile Library, which come out as simple Bitmap objects. The whole coding process is done in a BackgroundWorker as to not freeze the interface.

2.We decompose the frame in macroblocks of 16x16 pixels which we convert in 6 8x8 macroblocks in the YCbCr 4:2:0 format. The conversion implies that for each pixel we retain the Y component, thus resulting in 4 8x8 macroblocks, and for each group of 2x2 pixels we retain the average Cb and Cr components, resulting in 2 more 8x8 macroblocks. An insignificant part of the information is lost at this point, but we gain a good advantage in compression. The 6 macroblocks are saved in an instance of the Macroblock class defined in the DPCM class, containing the coordonates for the macroblock and 3 lists, one of 256 Y values and two of 64 Cb and Cr values. For each frame, this process is done in a parallel mode, gaining an advantage in speed.

3.After we obtain the macroblocks, if it isn't the first frame, we calculate the difference between the macroblocks for this frame and the macroblocks for the previous frame. The difference is calculated in the MacroblockDifference method of the DPCM class.

4.The next step is to apply the Discrete Cosine Transform or DCT for each 8x8 macroblock, done in the Dct method of the DPCM class.

5.After we obtain the DC and AC coefficients for each 8x8 macroblock, as in the result of the transform from step 4, we quantize the block using the Q10 quantization matrix. The quantization process is done in a parallel fashion for each block.

6.Each quantized block is reordered in the zigzag manner as accustomed to the DCT algorithm. As the quantization process, this step is done also in a parallel manner.

7.After reordering, the next step is run-level encoding of the obtained array. Run-level encoding implies two different procedures for the DC and AC coefficients. The DC coefficient is coded in two parts, the first part being a code associated to the size in bits of the coefficient taken from the DCHuffTable dictionary in the HuffmanTable class and the second part the actual bit representation of the DC coefficient. The AC coefficients, being composed from a large number of zeros, are coded in pairs of x,y where x is the number of zeros preceding the number y, each pair having an unique code in the ACHuffTable dictionary in the HuffmanTable class. If the AC coefficients contain a number of 16 adjacent zeros, they are coded separately by the code for the 15,0 pair.

8.The resulting code for each macroblock is then saved in a .txt file near the original avi file. Because C# has trouble writing bits directly into a file, we had to convert each group of 8 bits into a byte and write its ASCII code in the file. Preceding the actual bytes, we wrote a small header in the file to retain the original Width and Height of the frames, and after the bytes, a footer contains the last bits that couldn't fit in groups of 8.

Every test we succesfully completed resulted in files of smaller dimensions than the original avi file.

The decoding process implies simply backtracking the steps, as in reading the bytes from the file, and reconstructing the macroblocks using the same Huffman dictionaries. The reconstruction process goes backwards through the reordering, dequantization, inverse DCT, reconstruction of RGB macroblocks and reconstruction of the frames.

Because reading a continuous flux of bits couldn't be parallelized, the decompression process lasts much longer, requiring a lot of patience. Based on the quantization method used, information is mostly lost and the video ends up in a much lower quality.

Project Members:

• Voicu Alexandru (admin)