Variable length coding/decoding method of image data and apparatus thereof

Abstract

A method of variable length coding/decoding of image data and an apparatus thereof can vary the length of an escape sequence during variable length coding to thereby reduce the amount of transmitted data.The method of variable length coding/decoding includes the steps of loading an initial potential maximum run length; determining a number of bits necessary to express the potential maximum run length, coding a run length using the necessary number of bits and decreasing the potential maximum ran length by an amount equal to the previously coded run length to arrive at a new potential maximum ran length until an end of a block to be encoded has been reached.

What is claimed is:  
     
       1. A method of variable length coding of image data, the method comprising the steps of: 
       dividing the image data into a plurality of blocks, each said block formed of N×N pixels, wherein N is an integer;  
       transforming each said block to obtain transform coefficients of each said block;  
       quantizing said transform coefficients of each said block;  
       scanning said quantized transform coefficients in a predetermined pattern within each said block to arrange the quantized transform coefficients into a one-dimensional sequence of transform coefficients;  
       converting said one-dimensional sequence into symbol data having a run component and a level component;  
       determining a potential maximum run value;  
       (1) determining whether said symbol data is found within a regular region or an escape region;  
       (2) assigning a Huffman code to said symbol data if said symbol data is within said regular region and outputting said Huffman code of said symbol;  
       (3) if said symbol data is within said escape region,  
       a) determining an escape code number of bits necessary to represent sod potential maximum run value;  
       b) assigning a run code having the escape code number of bits to the run component of said symbol data and outputting said assigned run code of said ran length;  
       c) decrementing said maximum run potential value by a value equal to said run component plus one;  
       d) determining a number of level bits based upon a quantization step size value;  
       e) assigning a code to said level component using said number of determined level bits and outputting said assigned level code of said level component;  
       (4) determining if an end of the block has been reached, and asserting an end of block signal if the end of the block has been determined; and  
       if the end of the block has not been reached, repeating steps (1)-(4).  
     
     
       2. A method of variable length coding of image data as recited in  claim 1  wherein, 
       said potential maximum run value is equal to N 2 −1 for the N×N block.  
     
     
       3. A method of variable length coding of image data, the method comprising the steps of: 
       dividing the image data into a plurality of blocks, each said block formed of N×N pixels, wherein N is an integer;  
       transforming each said block to obtain transform coefficients of each said block;  
       quantizing said transform coefficients of each said block;  
       scanning said quantized transform coefficients in a predetermined pattern within each said block to arrange the quantized transform coefficients into a one-dimensional sequence of transform coefficients;  
       converting said one dimensional sequence into symbol data having a run component and a level component;  
       determining a potential maximum run value;  
       (1) determining whether said symbol data is found within a regular region or an escape region;  
       (2) if said symbol data is found in the regular region, assigning a Huffman code to said symbol data,  
       (3) if said symbol data is found in the regular region,  
       a) determining an escape code number of bits necessary to represent said potential maximum run value;  
       b) assigning a run code having the escape code number of bits to the run component of said symbol data;  
       c) decrementing said potential maximum run value by a value equal to said run component plus one;  
       d) determining a number of level bits based upon a quantization step size value;  
       e) assigning a code using said number of determined level bits to said level component;  
       f) outputting said assigned Huffman code if a number of bits of said assigned Huffman code is less than a number of bits of said escape codes of said run length and level codes together;  
       g) outputting said escape codes of said run length and level codes together if the number of bits of said escape code of said run length and level codes together is less than the length of the assigned Huffman code;  
       (4) if said symbol data is within said escape region,  
       a) determining an escape code number of bits necessary to represent said potential maximum run value;  
       b) assigning a run code having the escape code number of bits to the run component of said symbol data and outputting said assigned run code of said run length;  
       c) decrementing said maximum run potential value by a value equal to said run component plus one;  
       d) determining a number of level bits based upon a quantization step size value;  
       e) assigning a code using said number of determined level bits to said level component and outputting said assigned level code of said level component;  
       (5) determining if an end of the block has been reached, and asserting an end of block signal if the end of the block has been reached; and  
       if the end of the block has not been reached, then repeating steps (1)-(5).  
     
     
       4. A method of variable length coding of image data as recited in  claim 3  wherein, 
       said potential maximum run value is equal to N 2 −1 for the N×N block.  
     
     
       5. An apparatus for variable length coding of image data, the apparatus comprising: 
       first means for dividing the image data into a plurality of blocks, each said block formed of N×N pixels, wherein N is an integer;  
       second means for transforming each said block to obtain transform coefficients of each said block;  
       third means for quantizing said transform coefficients of each said block;  
       fourth means for scanning said quantized transform coefficients in a predetermined pattern within each said block to arrange the quantized transform coefficients into a one-dimensional sequence of transform coefficients;  
       fifth means for converting said one dimensional sequence into symbol data having a run component and a level component;  
       sixth means for determining a potential maximum run value;  
       seventh means for determining whether said symbol data is found within a regular region or an escape region, assigning a Huffman code to said symbol data if said symbol data is within said regular region and outputting said Huffman code of said symbol;  
       eighth means for determining an escape code number of bits necessary to represent said potential maximum run value, assigning a run code having the escape code number of bits to the run component of said symbol data and outputting said assigned run code of said run length, and decrementing said potential maximum run value by a value equal to said run component plus one;  
       ninth means for determining a number of level bits based upon a quantization step size value, assigning a code to said level component using said number of determined level bits and outputting said assigned level code of said level component;  
       tenth means for determining if an end of the block has been reached, and for outputting an end of block signal.  
     
     
       6. An apparatus for variable length coding of image data as recited in  claim 5 , wherein 
       said sixth means determines that said potential maximum run value is N 2 −1 for an N×N block.  
     
     
       7. An apparatus for variable length coding of image data as recited in  claim 5 , wherein said eighth means comprises: 
       a delaying means for loading, storing and outputting the potential maximum run value when coding on the block is started;  
       a subtracting means for subtracting from the potential maximum run value a value of a run length plus one;  
       a run coding length determining means for determining a run coded length, which is a number of bits necessary for expressing the potential maximum run value supplied from the delaying means;  
       a run coding means for coding the run data in accordance with the run coded length determined by the run coding length determining means;  
       a level coding length determining means for determining a level coded length, which is a number of bits necessary for expressing a quantized value calculated according to a quantization step size; and  
       a level coding means for coding the level data in accordance with the level coded length determined by the level coding length determining means.  
     
     
       8. A method of coding a data signal by means of runlength encoding, comprising the steps of: 
       ( a )  storing a maximum potential runlength;    
       ( b )  producing a runlength signal, having the number of bits required to express the stored maximum potential runlength from an input signal representing run data based on whether symbol data corresponding to the input signal is found in a regular region or an escape region, wherein a Huffman code is assigned if the symbol data is within said regular region and a run code corresponding to an escape sequence is assigned if the symbol data is within said escape region;    
       ( c )  producing a new maximum potential runlength by subtracting said run data from a predetermined factor from the stored maximum potential runlength;    
       ( d )  storing the new maximum potential runlength; and    
       ( e )  repeating steps  ( b )  to  ( d ). 
     
     
       9. A method of decoding a data signal, coded according to  claim 8  comprising the steps of: 
       ( a )  storing a maximum potential runlength;    
       ( b )  extracting run data from an input coded data signal, the extracted run data having the same number of bits as the stored maximum potential runlength;    
       ( c )  producing a new maximum potential runlength by subtracting said run data and a predetermined factor from the stored maximum potential runlength;    
       ( d )  storing the new maximum potential runlength; and    
       ( e )  repeating steps  ( b )  to  ( d ). 
     
     
       10. A data signal decoding apparatus comprising: 
       
         storage means for storing a maximum potential runlength;  
       
       
         input means for receiving a coded data signal;  
       
       
         decoding means responsive to the necessary bit length of a maximum potential runlength stored in a storage means to output the runlength data of the coded data signal as a run signal having the same number of bits as the stored maximum runlength; and  
       
       
         means to generate a new potential runlength in dependence on the run signal and the stored maximum runlength. 
       
     
     
       11. A method of decoding a digital data signal, comprising: 
       ( a )  loading a maximum potential run value;    
       ( b )  decoding run data from an input compressed data signal, the decoded run data having the same number of bits as the maximum potential run value of  ( a );  
       ( c )  producing a new maximum potential run value by subtracting said run data and a predetermined factor from the maximum potential run value of  ( a );  
       ( d )  determining whether the data signal is an end of the block; and    
       ( e )  repeating  ( b )  to  ( d )  using the new maximum run value in place of maximum run value if it is determined in  ( d )  that the data signal is not the end of the block.   
     
     
       12. A method of decoding a digital data signal according to  claim 11  further comprising: 
       ( f )  setting a run coded length to a predetermined value; and    
       ( g )  determining a level coded length according to a quantization step size, wherein  ( a )  is performed in response to a block start signal.   
     
     
       13. A variable length coded signal decoding method comprising: 
       ( a )  determining the number of bits of a symbol of an input signal which convey run length data;    
       ( b )  decoding said run length data;    
       ( c )  decoding level data in said symbol; and    
       ( d )  producing an output signal based on the decoded run length data and the decoded level data.   
     
     
       14. A variable length coded signal decoding method comprising: 
       ( a )  determining whether an input signal is one of a first signal according to a first code and a second signal produced by:    
       ( a 1   )  storing a maximum potential run value;    
       ( a 2   )  producing from an input run data signal a run length signal having a number of bits required for the stored maximum potential run value;    
       ( a 3   )  producing a new maximum potential run value by subtracting said run length signal produced in  ( a 2   )  and a predetermined factor from said maximum potential run value of  ( a 1   );  
       ( a 4   )  storing the new maximum potential run value; and    
       ( a 5   )  repeating  ( a 2   )  through  ( a 5   )  using the new maximum potential run value in place of the maximum potential run value of  ( a 1   )  and    
       ( b )  decoding the input signal in response to a result of  ( a ). 
     
     
       15. The variable length coded signal decoding method according to  claim 14 , wherein the second signal is further produced by; 
       ( a 6   )  determining number of bits required to represent a level signal based on a quantization step signal; and    
       ( a 7   )  producing a level signal having the number of bits determined in  ( a 6   ),  wherein  ( a 6   )  and  ( a 7   )  are performed prior to performing  ( a 5   ). 
     
     
       16. The variable length coded signal decoding method according to  claim 15 , wherein said first code is a Huffman code. 
     
     
       17. The variable length coded signal decoding method according to  claim 14 , wherein said first code is a Huffman code.