Video Compression

23. Huffman Coding Implementation

    Because Huffman coding involve reading and writing one bit at a time, we need to first write some functions that can process an arbitrary number of bits of a file. We provide the program fbitios.cpp along with its header file fbitios.h that has this capability:

    fbitios.cpp
    fbitios.h

    We do not intend to discuss the details of this program as it does not directly relate to video compression. All we need to know is how to use it, which is straight forward. The following is the class interface that does the job.

    class bitFileIO{ public: bitFileIO ( char *argv_in, char *argv_out ); //constructors bitFileIO :: bitFileIO( char *argv_out, int in_out ); int inputBit(); //input one bit from file void outputBit( int bit ); //output one bit to file long inputBits( int n ); //input n bits from file void outputBits ( unsigned long data, int n ); //output n bits to file void closeOutput(); //close_output void closeInput(); //close input };

    The constructor bitFileIO ( char *argv_out, int in_out ) opens the file specified by argv_out for input output depending on the value of in_out. If it is 1, it is opened for input, otherwise it is for output.

    The main purpose of the Huffman code here is to encode the run-level codewords of the DCT coefficients after forward quantization and reordering. Recall that we have defined a struct to represent a 3D run-level codeword:

    typedef struct { unsigned char run; short level; char last; } run3D;

    We define a class called RunHuff that will help encode and decode run-level codewords with a Huffman code. This class "has-a" run3D. As you'll see, we'll insert RunHuff objects into a set ,which involves the ordering of nodes. Therefore, we have to define the comparison operator "<" so that RunHuff objects ( nodes ) can be ordered. In this case, we order the objects using the values of ( run, level, last ) of their run3D objects. We first compare the runs of the two objects; whichever is smaller determines the smaller RunHuff object. If the runs are equal, we compare levels and so on. The data member index will point to the table location where the run-level codeword will be saved. ( Note that in the set data abstraction, the equality testing operator ( operator == ) is not used to test objects for equality. Instead, two objects X and Y are considered to be equal is X < Y and Y < X are false. Each element in a set is unique. If one tries to insert an element which is already in the set, the "insert" operation will be ignored. ) The class is defined below.

    class RunHuff { public: run3D r; unsigned int codeword; char hlen; //length of the Huffman codeword short index; //table index where codeword saved RunHuff() {} //constructors RunHuff ( run3D a, unsigned c, char len, short idx ) { r = a, codeword = c, hlen = len; index = idx; } //'<' operator is to order run-level tuples so that they can be saved in a binary tree ( set ) friend bool operator < ( RunHuff left, RunHuff right ) { if ( left.r.run < right.r.run ) return true; if ( left.r.run > right.r.run ) return false; //runs equal if ( left.r.level < right.r.level ) return true; if ( left.r.level > right.r.level ) return false; //both runs and levels equal if ( left.r.last > right.r.last ) return true; return false; //so, the left object is not smaller than the right } };

    We assume that a pre-calculated Huffman Table like the one shown in Table 4 of Section 22 is provided. We now define a variable htable to collect RunHuff objects, each of which contains a 3D run-level tuple and the corresponding Huffman codeword ( see Table 4 of section 22 ). This is most conveniently done using the C++ Standard Template Library ( STL ) set. We use the member function insert() of the set class to insert all RunHuff objects into the set as shown below. ( As a matter of fact, the STL set class is implemented using a balanced binary tree structure, which gives efficient search and insert operations. This is why we need to define a comparison operator in htable in order to use the STL set since a binary tree is fully ordered. )

    //use a set ( htable ) to collect all pre-calculated run-level and Huffman codewords void build_htable ( set &htable ) { short i, j, k, N = 10; //N is the number of pre-calculated codewords of positive levels char hlen[] = {2, 3, 4, 4, 4, 5, 5, 5, 6, 7}; //lengths of Huffman codewords (not including sign-bit) unsigned short hcode[] = { 0x01, 0x3, 0x7, 0xf, 0xe, 0x16, 0x6, 0x1a, 0x2a, 0x60 }; //Huffman codewords, 0x60 is ESC unsigned char runs[] = { 0, 1, 2, 0, 0, 3, 4, 5, 0, 255 }; //255 signifies ESC short levels[] = { 1, 1, 1, 2, 1, 1, 1, 1, 3, 0 }; //level of 3D run-level tuple char lasts[] = { 0, 0, 0, 0, 1, 0, 0, 0, 0, 0 }; //last of 3D run-level tuple run3D r; //a 3D run-level codeword ( tuple ) RunHuff rf[128]; //table containing RunHuff objects k = 0; j = 0; for ( i = 0; i < N; ++i ) { r.run = runs[i]; r.level = levels[i]; r.last = lasts[i]; rf[k++] = RunHuff ( r, hcode[i] << 1, hlen[i], j++ ); //construct RunHuff object, sign-bit = 0 r.level = -r.level; //do the same thing for negative level rf[k++] = RunHuff ( r, (hcode[i]<<1) | 1, hlen[i], j++ ); //level negative, so sign = 1 } k = 2 * N; //insert all 2N RunHuff objects into htable for ( i = 0; i < k; ++i ) htable.insert ( rf[i] ); }

    After we have collected all the pre-calculated run-level Huffman codewords in the set htable, the encoding of 3D run-levels tuples becomes simple. To encode a run-level codeword, all we need to do is to lookup the set htable; if the run-level codeword is in the set, we output the Huffman codeword along with the sign-bit; if it is not in the set, we "escape" and output the run-level codeword "directly".

    Suppose the array runs[] contains all the run-level codewords of a macroblock; the following piece of code shows how to encode them using the pre-calculated Huffman codewords saved in htable. In the code, we define an iterator itr to traverse htable. If it finds the run-level tuple in htable, it outputs the Huffman codeword and the sign-bit, otherwise it escape-encodes the tuple by first outputting the ESCAPE code followed by a fixed-length codeword for the tuple.

    /* Inputs: htable contains all the pre-calculated Huffman codewords of 3D run-level tuples runs[] contains the 3D run-level tuples of a macroblock of quantized DCT coefficients Outputs:bitstreams of codewords ( Huffman + sign or ESCAPE + 3D run-level ) to bitFileIO outputs */ void huff_encode ( set &htable, run3D runs[], bitFileIO &outputs ) { short i, j, k; k = 0; set::iterator itr; //iterator to traverse htable i = 0; while ( i < 64 ) { //a macroblock has at most 64 samples RunHuff rf ( runs[k], 0, 0, 0 ); //construct a RunHuff object; only runs[k] is relevant // as it is used for searching ( we defined '<' // in RunHuff class ) if ( (itr = htable.find ( rf )) != htable.end() ) //found outputs.outputBits ( itr->codeword, itr->hlen + 1); else //not found escape_encode( outputs, rf.r ); //need to 'escape encode' the 3D run-level tuple if ( runs[k].last ) break; //end of run-level codewords i += ( runs[k].run + 1 ); //for handling the special case of whole block of run being 0 k++; } }

    The following code shows how to escape-encode a run-level tuple.

    void escape_encode ( bitFileIO &outputs, run3D &r ) { if ( r.level < 0 ) { //value of level negative outputs.outputBit ( 1 ); //output sign-bit first r.level = -r.level; //change level value to positive } else outputs.outputBit ( 0 ); //value of level negative outputs.outputBits ( 0x60, 7 ); //ESCAPE code if ( r.run == 64 ) r.run = 63; //r.level differentiates between if last element nonzero outputs.outputBits ( r.run, 6 ); //6 bits for run value outputs.outputBits ( r.level, 8 ); //8 bits for level value outputs.outputBit ( r.last ); //1 bit for last value }

    The functions huff_encode() and escape_encode() encode the 3D run-level tuples of a macroblock. In the encoding process, the Huffman tree is not needed. However, to decode the encoded bitstream, we have to use the Huffman tree to recover the 'symbols' ( run-level tuples ). We can easily construct the Huffman tree in the form of a table from the set htable. Note that here we build the Huffman tree from pre-calculated codewords, not from symbol weights as people normally do. Therefore, the process is a lot simpler as Huffman codewords have been provided. The following function build_huff_tree() builds the Huffman tree from htable and saves it in the table ( array ) huf_tree[] of data type short. An entry of huf_tree[] holds a node's pointer to a child or an index ( 'symbol' ) if the node is a leaf; the index points to an entry of another table, run_table[], which contains the actual run-level tuple ( see Table 4 of Section 22 ). For convenience of programming, we put huf_tree[] and run_table[] in a public class ( i.e. a struct ) called Dtables:

    class Dtables { public: short huf_tree[1024]; //table containing Huffman Tree run3D run_table[512]; //table containing run-level codewords }; /* Input: htable, a set containing all pre-calculated Huffman codewords of 3D run-level tuples Outputs: d.huf_tree[], the Huffman tree containing pointers and indices pointing to run-level tuples d.run_table[], the table that contains the run-level tuples ( codewords ) */ void build_huff_tree ( set &htable, Dtables &d ) { set::iterator itr; //iterator to traverse set htable short i, j, n0, free_slot, loc, loc0, root, ntotal; unsigned int mask, hcode; n0 = NSymbols; //"number" of symbols ( = number of leaves in tree ) printf("\nn0=%d", n0 ); ntotal = 2 * n0 - 1; //Huffman tree has 2n0 - 1 internal nodes root = 3 * n0 - 3; //location of root ( see section 21 ), offset n0 has been added free_slot = root - 2; //next free table entry for filling in with a pointer or an index // ( note: root has root_left, root_right ) for ( i = 0; i < ntotal; ++i ) //initialize the table d.huf_tree[i] = -1; //all entries empty for ( itr = htable.begin(); itr != htable.end(); ++itr ) { //consider all codewords in the set htable if ( itr->r.level < 0 ) continue; //only save positive levels of run-level codeword d.run_table[itr->index/2]=itr->r; //save run-level codeword; index divided by 2 as only postive levels saved loc = root; //always start from root mask = 0x01; //for examining bits of Huffman codeword hcode = itr->codeword >> 1; //the rightmost bit is sign-bit, not part of Huffman for ( i = 0; i < itr->hlen; ++i ){ //traverse the Huffman codeword loc0 = loc - n0; //everything shifted by offset n0 if ( i == ( itr->hlen - 1 ) ){ //last bit, should point to leaf if ( (mask & hcode) == 0 ) //a 0, save it at 'left' leaf d.huf_tree[loc0] = itr->index/2; else //a 1, save it at 'right' leaf d.huf_tree[loc0-1] = itr->index/2; continue; //get out of for i for loop, consider next codeword } if ( (mask & hcode) == 0 ){ //a 0 ( go left ) if (d.huf_tree[loc0] == -1){ //slot empty d.huf_tree[loc0] = free_slot; //point to left new child free_slot -= 2; //next free table entry } //else : already has left child loc = d.huf_tree[loc0]; //follow the left child } else { //a 1 ( go right ) if (d.huf_tree[loc0-1]== -1){ //slot empty d.huf_tree[loc0-1]=free_slot;//point to right new child free_slot -= 2; } //else: already has right child loc = d.huf_tree[loc0-1]; //follow the right child } mask <<= 1; //consider next bit } //for i } //for itr } //build_huff_tree()

    After we have built the Huffman tree, the decoding becomes quite simple. We read in a bitstream and traverse the tree starting from the root. If the bit read is a 0, we traverse left otherwise we traverse right until we reach a leaf where we recover a symbol. If the symbol is an ESCAPE code, we need to further read in a fixed-number of bits to determine the 'symbol' ( the run-level tuple ). Then we read in another bit and start the tree-traversal from the root again. The details are shown in the function huff_decode() listed below. ( More elaborations on Huffman tree properties concerning our implementation will be discussed in a later chapter. )

    /* Inputs: bf, the encoded bitstream to be decoded d.huf_tree[], table containing the Huffman tree d.run_table[], table containing the actual run-level codewords Output: runs[], table containing the run-level tuples of a macroblock */ short huff_decode( bitFileIO &bf, Dtables &d, run3D runs[] ) { short n0, loc, loc0, root, k; char c, sign; bool done = false; run3D r; n0 = NSymbols; //"number" of symbols root = 3 * n0 - 3; //points to root of tree k = 0; while ( !done ) { loc = root; //starts from root sign = bf.inputBit(); //sign-bit do { loc0 = loc - n0; c = bf.inputBit(); //read one bit if (c < 0) {done = true; break;} //no more data, done if ( c == 0 ) //a 0, go left loc = d.huf_tree[loc0]; else //a 1, go right loc = d.huf_tree[loc0-1]; } while ( loc >= n0 ); //traverse until reaches leaf r = d.run_table[loc]; if ( r.run == 255 ) { //ESCAPE code, read actual run-level tuple r.run = bf.inputBits ( 6 ); //read 6 bits for run r.level = bf.inputBits ( 8 ); //read 8 bits for level r.last = bf.inputBit(); //read 1 bit for last if ( sign ) //if sign is 1, level should be negative r.level = -r.level; } else { if ( sign ) //1 => negative r.level = -r.level; } if ( (r.run == 63) && (r.level == 0) ) r.run = 64; //whole block 0 runs[k++] = r; //save tuple in table runs[] if ( r.last ) //end of macroblock break; } //while if ( done ) return -1; //if ( done ) => no more data else return 1; }

    Putting all these together, we provide the programs test_huf.cpp and fbitios.cpp for you to do the testing of the concepts discussed above. You can copy the files along with the "sample_video.dct" and put them in a directory. You can compile them to obtain the executable by

    g++ -o test_huf test_huf.cpp fbitios.cpp

    You can run test_huf with the following options:

    	./test_huf
               This reads in DCT coefficients from "sample_video.dct", quantizes, reorders, run-level encodes
               and Huffman encodes. The Huffman-encoded bitstream is saved in "sample_video.huf".
            ./test_huf d
               This reads in encoded bitstream from "sample_video.huf", Huffman decodes, run-level decodes,
               reverses reordering, inverse quantizes and saves the decoded data in "sample_video.dec".
            ./test_huf t
               Similar to "d" but decodes block by block interactively and prints out the decoded DCT blocks.
       

    The program links are given below. ( The file "sample_video.dct" is not zipped. )

    fbitios.h
    fbitios.cpp
    test_huf.cpp
    sample_video.dct
    
    <<Prev   Next >>