Entropy coding

Abstract

A method, an apparatus ( 100 ) and a computer program product for entropy coding of discrete wavelet transform (DWT) coefficient bits that are arranged into code blocks and coded in bitplane order using three coding passes for each bitplane are disclosed. In the method, transform coefficients of a code block ( 200 ) in sign-magnitude form are pre-analyzed. Statistical data about the coefficients is stored, preferably with the coefficients. Significance state data ( 330 ), coded data ( 340 ), magnitude refinement data ( 350 ), bit data ( 310 ), and sign data ( 320 ) for the code block are buffered. More preferably, the buffering is implemented using a FIFO ( 120, 1130 ), located between a context generation module ( 110, 1120 ) and an arithmetic coder ( 130, 1150 ). Based upon the statistical data, at least one command for at least one sequence of bit and context pairs is generated for arithmetic encoding.

1. A method of entropy coding of discrete wavelet transform coefficient bits that are arranged in code blocks and coded in bitplane order using three coding passes for each bitplane, said method including the steps of:
 pre-analyzing transform coefficients of a code block in sign-magnitude form to determine statistical data about the coefficients;  
 storing the statistical data; and  
 generating, based upon the statistical data, a command for arithmetic encoding of a sequence, wherein the sequence comprises a plurality of bit and context pairs for the code-block, and wherein the command specifies a length of the sequence.  
 
   
   
     2. The method according to  claim 1 , wherein the statistical data is stored with the coefficients. 
   
   
     3. The method according to  claim 1 , further including the step of buffering significance state data, coded data, magnitude refinement data, bit data, and sign data for the code block. 
   
   
     4. The method according to  claim 3 , wherein said buffering step is implemented using register arrays for context generation. 
   
   
     5. The method according to  claim 4 , further including the step of switching to a specific region of the code block in any one of significance propagation, magnitude refinement, and cleanup coding passes. 
   
   
     6. The method according to  claim 5 , wherein said switching step is implemented using rotate-left and rotate-up operations of the register arrays. 
   
   
     7. The method according to  claim 1 , further including the step of buffering bit and context data before arithmetic coding using the bit and context data. 
   
   
     8. The method according to  claim 7 , wherein bit, context and the number of bit and context pairs are buffered. 
   
   
     9. The method according to  claim 8 , wherein said buffering step is implemented using a FIFO. 
   
   
     10. The method according to  claim 1 , further including the steps of:
 buffering a region of a code block, the region being currently coded; and  
 buffering separately the remaining regions of the code block.  
 
   
   
     11. The method according to  claim 10 , wherein:
 said buffering step for the region being currently coded is implemented using a register window; and  
 said buffering step for the remaining regions is implemented using a scratch memory.  
 
   
   
     12. The method according to  claim 1 , further including the steps of:
 looking for, using a bypass control module, the next region of a code block to be coded in each of significance propagation, magnitude refinement, and cleanup coding passes; and  
 generating, using a context generation module, a context of a region previously provided by the bypass control module, the bypass control and context generation modules operating in parallel.  
 
   
   
     13. The method according to  claim 12 , further including the step of communicating data between the bypass control and context generation modules using a bus, the bus including a control bus and a data bus, the control bus providing an indication of which column to start in a region when the context generation module processes the region. 
   
   
     14. The method according to  claim 13 , further including the step of detecting termination of processing in the context generation module for each pass, the detected termination enabling coding in the region to be terminated before scanning to a last column. 
   
   
     15. The method according to  claim 1 , wherein the entropy coding is JPEG 2000 entropy coding. 
   
   
     16. A method according to  claim 1 , wherein the statistical data comprises a predicted significance state after a first cleanup coding pass. 
   
   
     17. An apparatus for entropy coding of discrete wavelet transform coefficient bits that are arranged in code blocks and coded in bitplane order using three coding passes for each bitplane, said apparatus including:
 means for pre-analyzing transform coefficients of a code block in sign-magnitude form to determine statistical data about the coefficients;  
 means for storing the statistical data; and  
 means for generating, based upon the statistical data, a command for arithmetic encoding of a sequence, wherein the sequence comprises a plurality of bit and context pairs for the code-block, and wherein the command specifies a length of the sequence.  
 
   
   
     18. The apparatus according to  claim 17 , wherein the statistical data is stored with the coefficients. 
   
   
     19. The apparatus according to  claim 17 , further including means for buffering significance state data, coded data, magnitude refinement data, bit data, and sign data for the code block. 
   
   
     20. The apparatus according to  claim 19 , wherein said buffering means comprises register arrays for context generation. 
   
   
     21. The apparatus according to  claim 20 , further including means for switching to a specific region of the code block in any one of significance propagation, magnitude refinement, and cleanup coding passes. 
   
   
     22. The apparatus according to  claim 21 , wherein said switching means implements rotate-left and rotate-up operations of the register arrays. 
   
   
     23. The apparatus according to  claim 17 , further including means for buffering bit and context data before arithmetic coding using the bit and context data. 
   
   
     24. The apparatus according to  claim 23 , wherein bit, context and the number of bit and context pairs are buffered. 
   
   
     25. The apparatus according to  claim 24 , wherein said buffering means is a FIFO. 
   
   
     26. The apparatus according to  claim 17 , further including:
 means for buffering a region of a code block, the region being currently coded; and  
 means for buffering separately the remaining regions of the code block.  
 
   
   
     27. The apparatus according to  claim 26 , wherein:
 said buffering means for the region being currently coded is a register window; and  
 said buffering means for the remaining regions is implemented using a scratch memory.  
 
   
   
     28. The apparatus according to  claim 17 , further including:
 a bypass control module for looking for the next region of a code block to be coded in each of significance propagation, magnitude refinement, and cleanup coding passes; and  
 a context generation module for generating a context of a region previously provided by the bypass control module, the bypass control and context generation modules operating in parallel.  
 
   
   
     29. The apparatus according to  claim 28 , further including a bus for communicating data between the bypass control and context generation modules, the bus including a control bus and a data bus, the control bus providing an indication of which column to start in a region when the context generation module processes the region. 
   
   
     30. The apparatus according to  claim 29 , further including means for detecting termination of processing in the context generation module for each pass, the detected termination enabling coding in the region to be terminated before scanning to a last column. 
   
   
     31. The apparatus according to  claim 17 ,
 wherein the entropy coding is JPEG 2000 entropy coding.  
 
   
   
     32. A computer program product having a computer readable medium having a computer program recorded therein for entropy coding of discrete wavelet transform coefficient bits that are arranged in code blocks and coded in bitplane order using three coding passes for each bitplane, said computer program product including:
 computer program code means for pre-analyzing transform coefficients of a code block in sign-magnitude form to determine statistical data about the coefficients;  
 computer program code means for storing the statistical data; and  
 computer program code means for generating, based upon the statistical data, a command for arithmetic encoding of a sequence, wherein the sequence comprises a plurality of bit and context pairs for the code-block and wherein the command specifies a length of the sequence.  
 
   
   
     33. The computer program product according to  claim 32 , wherein the statistical data is stored with the coefficients. 
   
   
     34. The computer program product according to  claim 32 , further including computer program code means for buffering significance state data, coded data, magnitude refinement data, bit data, and sign data for the code block. 
   
   
     35. The computer program product according to  claim 34 , wherein said buffering computer program code means implements register arrays for context generation. 
   
   
     36. The computer program product according to  claim 35 , further including computer program code means for switching to a specific region of the code block in any one of significance propagation, magnitude refinement, and cleanup coding passes. 
   
   
     37. The computer program product according to  claim 36 , wherein said computer program code means for switching implements rotate-left and rotate-up operations of the register arrays. 
   
   
     38. The computer program product according to  claim 32 , further including computer program code means for buffering bit and context data before arithmetic coding using the bit and context data. 
   
   
     39. The computer program product according to  claim 38 , wherein bit, context and the number of bit and context pairs are buffered. 
   
   
     40. The computer program product according to  claim 39 , wherein said buffering computer program code means implements a FIFO. 
   
   
     41. The computer program product according to  claim 32 , further including:
 computer program code means for buffering a region of a code block, the region being currently coded; and  
 computer program code means for buffering separately the remaining regions of the code block.  
 
   
   
     42. The computer program product according to  claim 41 , wherein:
 said computer program code means for buffering the region being currently coded is a register window; and  
 said buffering means for the remaining regions is a scratch memory.  
 
   
   
     43. The computer program product according to  claim 32 , further including:
 computer program code means for implementing a bypass control module to look for the next region of a code block to be coded in each of significance propagation, magnitude refinement, and cleanup coding passes; and  
 computer program code means for context generation module to generate a context of a region previously provided by the bypass control module, the bypass control and context generation modules operating in parallel.  
 
   
   
     44. The computer program product according to  claim 43 , further including a bus for communicating data between the bypass control and context generation modules, the bus including a control bus and a data bus, the control bus providing an indication of which column to start in a region when the context generation module processes the region. 
   
   
     45. The computer program product according to  claim 44 , further including computer program code means for detecting termination of processing in the context generation module for each pass, the detected termination enabling coding in the region to be terminated before scanning to a last column. 
   
   
     46. The computer program product according to  claim 32 , wherein the entropy coding is JPEG 2000 entropy coding.