This invention relates to coding methods, and more particularly to run length coding as is useful with block transforms, such as DCT, plus variable length coding and related systems.
Many methods exist to compress images/video, such as JPEG for still images and H.26x/MPEGs for video sequences. In DCT-based video compression, such as H.261, H.263, MPEG1, MPEG2, and MPEG4, or image compression, such as JPEG, a picture is decomposed into macroblocks. Each macroblock contains a certain number of 8×8 blocks, depending upon the chroma-format used. For example, in the case of 4:2:0 chroma-format a macroblock is made up of four 8×8 luminance blocks (i.e., 16×16 pixels) and two 8×8 chrominance blocks (each located as a subsampling of the 16×16). FIG. 3 depicts the block diagram of DCT-based video encoding. In order to reduce the bit-rate, 8×8 DCT (discrete cosine transform) is used to convert the blocks into the frequency domain for quantization. The first coefficient (0 frequency) in an 8×8 DCT block is called the DC coefficient; the remaining 63 DCT-coefficients in the block are called AC coefficients. The DCT-coefficients blocks are quantized, scanned into a 1-D sequence, and coded by using variable length coding (VLC). For motion compensation (MC) which uses motion estimation (ME) of successive video frames, inverse-quantization and IDCT are needed for the feedback loop. Except for MC, all the function blocks in FIG. 3 operate on 8×8 block basis.
H.26L is a new video compression video standard being developed by ITU-T which offers much higher coding efficiency (about 30–50% additional bit-rate reduction at the same coding qualities) than MPEG-4 SP. A typical application of H.26L could be wireless video on demand, in which the bandwidth is so limited that a coding standard of high compression ratio is strongly desired.
The basic coding techniques in H.26L are still motion compensated prediction, transform, quantization and entropy coding as illustrated in FIG. 3. However, H.26L differs from MPEG4/H.263 in many details. One of major differences lies in the transform and quantization. Instead of 8×8 DCT transforms, H.26L may use a 4×4 integer transform for the residual coding of the residual blocks generated either by using motion compensation for inter-coded macroblocks or by using intra prediction for intra-coded macroblocks.
The transform coefficient encoding, illustrated as operation VLC in FIG. 3, encodes a scan-order sequence of transform coefficients of a block by first run-length encoding and then entropy encoding the run-length coding symbols into variable length codewords according to a frequency of occurrence (a lookup table). In particular, MPEG1, MPEG2, and H.26L first encode the scanned quantized DCT transform coefficient sequence, DCT0, DCT1, . . . , DCT63, as a sequence of run-length coding symbols, (run1, level1), (run2, level2), . . . , (runN, levelN), EOB, where run1 is the number of initial DCTjs equal to zero, level1 is the value of the first non-zero DCTj, run2 is the number of DCTjs equal to zero between the first non-zero DCTj and the second non-zero DCTj, level2 is the value of the second non-zero DCTj, and so forth; and EOB is a coding symbol indicating no more nonzero coefficients and thus no more coding symbols. Then the coding symbols are assigned variable length codewords according to a lookup table. This is called a 2-D coding because of the coding symbols include pairings (runk, levelk).
Analogously, MPEG4 and H.263 use 3-D coding symbols, (runk, levelk, lastk), where again runk is the number of DCTjs equal to zero following the (k−1)th non-zero DCTj, levelk is the value of the kth nonzero DCTj, and lastk=0 if there are more nonzero DCTjs, whereas lastk=1 if this is the last nonzero DCTj and thus the last 3-D symbol generated by DCT0, DCT1, . . . , DCT63. The 3-D symbols do not need an EOB coding symbols due to the lastk indicator in each coding symbol. Again, variable length codewords are assigned to the possible coding symbols; and, in particular, two separate codewords are needed for (runk, levelk, lastk=0) and (runk, levelk, lastk=1). Because lastk=0 is more common than lastk=1, the lookup tables typically have shorter codewords for (runk, levelk, lastk=0) than for (runk, levelk, lastk=1).
In some cases, however, these runl-length codings contain redundancy.