Browse Prior Art Database

Technique to maximize the run length of zeros, suitable for Huffman coding

IP.com Disclosure Number: IPCOM000126029D
Original Publication Date: 2005-Jun-29
Included in the Prior Art Database: 2005-Jun-29
Document File: 8 page(s) / 64K

Publishing Venue

Motorola

Abstract

DCT followed by variable length coding like Huffman coding is one of the most widely used methods used in the Image Compression industry to achieve good compression ratio. If the image being compressed is spatially sampled at or above nyquist rate, the above mentioned techniques can provide compressions which allows the reconstructed image to be "very close" to the actual image. Blocks of 8X8 are used widely for DCT. Then, these blocks are quantized in the transform/frequency domain and are coded using variable length coding like Huffman coding. If an image is NXM pixels, then there will be (N/8)X(M/8) blocks which will be transformed using DCT and variable length encoded independently. But, within each block, the transformed coefficients in frequency domain are scanned in a particular order creating maximum run length of zeros at the end. This is again on the assumption that the image which was transformed has significant amount of low frequency components compared to high frequency components. The technique described below is another method of scanning the coefficients which further increases the run length of zeros.

This text was extracted from a Microsoft Word document.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 45% of the total text.

Technique to maximize the run length of zeros, suitable for Huffman coding

raghus@motorola.com

ABSTRACT

DCT followed by variable length coding like Huffman coding is one of the most widely used methods used in the Image Compression industry to achieve good compression ratio.  If the image being compressed is spatially sampled at or above nyquist rate, the above mentioned techniques can provide compressions which allows the reconstructed image to be “very close” to the actual image.  Blocks of 8X8 are used widely for DCT.  Then, these blocks are quantized in the transform/frequency domain and are coded using variable length coding like Huffman coding.  If an image is NXM pixels, then there will be (N/8)X(M/8) blocks which will be transformed using DCT and variable length encoded independently.  But, within each block, the transformed coefficients in frequency domain are scanned in a particular order creating maximum run length of zeros at the end.  This is again on the assumption that the image which was transformed has significant amount of low frequency components compared to high frequency components.  The technique described below is another method of scanning the coefficients which further increases the run length of zeros.

INTRODUCTION

In JPEG encoding of a frame, or encoding of an I-frame in MPEG, each block of 8X8 pixels is transformed into frequency domain using DCT and is encoded using Huffman code.  The scanning of these coefficients in transform domain is done as shown below. 

This is once again on the assumption that the image which is being compressed has significantly large amount of low frequency information compared to high frequency information.  Assuming that horizontal and vertical information are present in the upper triangle (ABC), most of the values in the lower triangle (CBD) will be zeros.  Thus, this zig-zag scanning will give maximum run length of zeros.

OVERVIEW OF APPROACH

     In the proposed approach, each block of 8X8 is NOT encoded independently.  After the blocks are transformed using DCT, a particular re-arrangement is done in the blocks which will result in much larger run lengths of zeros and hence lesser number of bits to encode the entire image.

DESCRIPTION

     Consider four blocks of 8X8 pixels say, A, B, C and D as shown below.

Let A’, B’, C’ and D’ be corresponding transform domain blocks (after DCT and quantization).   Assuming that the blocks A, B, C and D satisfied the nyquist criteria in spatial sampling, and they contained predominantly low frequency information, the top left values in the blocks A’, B’, C’ and D’ will have significant non-zero values.  And most of the values towards the bottom right will be zero.

The transform domain blocks can be divided into sections as shown above (indicated by 1, 2, …8).  It is clear that section 2 and section 7 have same number of pixels.  Furthermore, section 2 has high frequency coefficients while the section...