Source: http://patents.com/us-5646618.html
Timestamp: 2018-08-22 06:20:12
Document Index: 634669207

Matched Legal Cases: ['application no. 60', 'art1', 'art2', 'art3', 'art4', 'art1', 'art2', 'art3', 'art4', 'art1', 'art2', 'art1', 'art2', 'art1', 'art2', 'art 1', 'art 2']

US Patent # 5,646,618. Decoding one or more variable-length encoded signals using a single table lookup - Patents.com
United States Patent 5,646,618
Walsh July 8, 1997
Inventors: Walsh; Thomas E. (Portland, OR)
Appl. No.: 08/558,258
Current U.S. Class: 341/67 ; 341/106; 375/E7.03; 375/E7.093; 375/E7.107; 375/E7.14; 375/E7.144; 375/E7.161; 375/E7.166; 375/E7.172; 375/E7.176; 375/E7.181; 375/E7.211; 375/E7.212; 375/E7.214; 375/E7.226; 375/E7.231
Field of Search: 341/67,106,65,99,50,51
4369463 January 1983 Anastassiou
4386416 May 1983 Giltner
4574382 March 1986 Ko
4700175 October 1987 Bledsoe
4899149 February 1990 Kahan
4967196 October 1990 Spraque et al.
5045853 September 1991 Astle et al.
5268769 December 1993 Tsuchiya et al.
5304995 April 1994 Dachiku
0145396 Jun., 1985 EP
WO8905556 Jun., 1989 EP
"DVI Image Compression--Second Generation," by Stuart J. Golin, Image Processing Algorithms and Techniques III, SPIE vol. 1657, Proceedings of the International Society for Optical Engineering, 1992, pp. 106-113. .
Abramson, N., "Information Theory and Coding," McGraw-Hill 1963, pp. 77-92. .
"The i750 Video Processor: A Total Multimedia Solution," Communications of the ACM, vol. 34 , No. 4, Apr. 1991, New York, pp. 64-78. .
Patent Abstracts of Japan, vol. 11, No. 83, (E-489) (2530), Mar. 13, 1987, entitled "Data Processing Method" and JP,A61237520 (Canon, Inc.) 22 Oct. 1986..
This nonprovisional U.S. national application, filed under 35 U.S.C. .sctn.111(a), claims, under 37 C.F.R. .sctn.1.78(a)(3), the benefit of the filing date of provisional U.S. national application no. 60/001369, filed on Jul. 21, 1995 under 35 U.S.C. .sctn.111(b).
FIGS. 7-9 show representations of the pixels in the current (16.times.16) macroblock of the current frame in the spatial domain used for motion estimation;
FIG. 15 is a representation of an example of the band scan pattern generated during the processing of FIG. 14 for a band having (4.times.4) coefficient blocks;
Capture processor 104 captures the digitized component signals received from converter 102. Capturing may include one or more of color conversion (e.g., RGB to YUV), scaling, and subsampling. Each captured video frame is represented by a set of three two-dimensional component planes, one for each component of the digitized video signals. In one embodiment, capture processor 104 captures video signals in a YUV9 (i.e., YUV 4:1:1) format, in which every (4.times.4) block of pixels of the Y-component plane corresponds to a single pixel in the U-component plane and a single pixel in the V-component plane. Capture processor 104 selectively stores the captured signals to memory device 112 and/or mass storage device 120 via system bus 114. Those skilled in the art will understand that, for real-time encoding, the captured signals are preferably stored to memory device 112, while for non-real-time encoding, the captured signals are preferably stored to mass storage device 120.
Referring now to FIG. 2, decoding system 200 is preferably a microprocessor-based PC system similar to the basic PC system of encoding system 100. In particular, host processor 208 may be any suitable means for decoding encoded video signals and is preferably an Intel.RTM. general purpose microprocessor such as an Intel.RTM. i486.TM., Pentium.TM., or higher processor. System bus 206 may be any suitable digital signal transfer device and is preferably a PCI bus. Mass storage device 212 may be any suitable means for storing digital signals and is preferably a CD-ROM device. Receiver 210 may be any suitable means for receiving the digital signals transmitted by transmitter 118 of encoding system 100. Display processor 202 may be any suitable device for processing video signals for display (including converting the digital video signals to analog video signals) and is preferably implemented through a PC-based display system such as a VGA or SVGA system. Monitor 204 may be any means for displaying analog signals and is preferably a VGA monitor.
Referring now to FIG. 3, there is shown a process flow diagram of the compression processing implemented by encode system 100 of FIG. 1 for each frame of a video stream, according to a preferred embodiment of the present invention. The RGB24 signals generated by A/D converter 102 are converted to YVU24 signals by capture processor 104. Capture processor 104 subsamples the YVU24 signals to generate subsampled YVU9 signals. This is done by subsampling the U and V planes using the following 16-tap (4.times.4) 2-dimensional filter:
______________________________________ { 3, 5, 5, 3. 5, 25, 25, 5, 5, 25, 25, 5, 3, 5, 5, 3 }/152 ______________________________________
Eight bits of precision are maintained for the components of the YVU9 data, which are captured for each frame as a Y-component plane, a subsampled U-component plane, and a subsampled V-component plane. Capture processor 104 is also capable of generating YVU12, in which there are one U component and one V component for each (2.times.2) block of Y components.
For D frames, motion estimator 602 of FIG. 6 is selectively enabled to perform motion estimation on macroblocks of the current band relative to a reference band to generate a set of motion vectors for the current band, where the D-frame reference band is generated by decoding the corresponding encoded band for a previous frame. (A block may correspond to an (8.times.8) set of pixels, while a macroblock may correspond to a (2.times.2) array of blocks (i.e., a (16.times.16) set of pixels).) For B frames, motion estimator 602 performs motion estimation on macroblocks of the current band with respect to two reference bands: one corresponding to a previous frame and one corresponding to a subsequent frame. When motion estimator 602 is disabled, no motion estimation is performed and zero motion vectors are used by motion-compensated differencer 604. The processing of motion estimator 602 is described in further detail later in this specification in the section entitled "Motion Estimation."
The preferred processing of motion estimator 602 is explained in further detail in the context of the example shown in FIGS. 7-12. In this example, the block size for motion estimation is a (16.times.16) macroblock and the search range is +/-15 pixels. FIGS. 7-9 show representations of the pixels in the current (16.times.16) macroblock of the current frame in the spatial domain. Each small block in FIGS. 7-9 represents a different pixel in the current macroblock. FIGS. 10-12 show representations of the full-pixel motion vectors within the search range in the velocity domain. Each small block in FIGS. 10-12 represents a different motion vector in the velocity domain. Each comparison by motion estimator 602 is preferably based on a SAD measure.
For this example, the first phase of motion estimation processing is represented in FIGS. 7 and 10. The motion vectors used in the first phase are designated by "x" in FIG. 10. In the first phase, a comparison is made between the current macroblock and the reference macroblock corresponding to each motion vector designated in FIG. 10. Rather than using the full current macroblock for each comparison, however, a subsampled current macroblock is compared to a subsampled reference macroblock. The pixels of the subsampled macroblock used in the first phase are indicated by "x" in FIG. 7. Thus, for each comparison of the first phase, a (4.times.4) set of current pixels is compared to a (4.times.4) set of reference pixels. In this example, 49 comparisons are made, corresponding to the (7.times.7) array of motion vectors designated in FIG. 10.
FIGS. 8 and 11 show the second phase of motion estimation processing for the present example. Rather than using only the single best match from the first phase, the second phase is based on the best n matches from the first phase (e.g., in this case, the best n=7 matches: (0,-13), (-8,-8), (-4,-4), (+8,-4), (-8,+4), (-4,+4), and (+4,+8)). These seven best matches are designated by "x" in FIG. 11. For the second phase, each of the best matches from the first phase is used to select eight new motion vectors at a finer velocity resolution than was used in the first phase. The new motion vectors are designated by "o" in FIG. 11. In FIG. 8, the pixels used for each comparison for the second are designated by an "x". Thus, for the second phase, an (8.times.8) set of current pixels is compared to a (8.times.8) set of reference pixels for each comparison. In this example, there is a comparison for each motion vector in the seven sets of motion vectors. Note that the sets of motion vectors may overlap. For example, (-6,-6) is in two different sets of motion vectors. Depending upon the sophistication of the implementation, the comparison for such shared motion vectors needs only be performed once.
FIGS. 9 and 12 show the third phase of motion estimation processing for the present example. The third phase is based on the best m matches from the second phase (e.g., in this case, the best m=3 matches: (-6,-6), (-4,-4), and (-6,+4)). These three best matches are designated by "x" or "o" in FIG. 12. Note that, in this example, one of the best matches from the second phase was also a best match from the first phase. In the third phase, each of the best matches from the second phase is used to select eight new motion vectors at a finer velocity resolution than was used in the second phase. The new motion vectors are designated by "*" in FIG. 12. In FIG. 9, the pixels used for each comparison are designated by an "x". Thus, for each comparison of the third phase, the full (16.times.16) macroblock of current pixels is compared to a (16.times.16) macroblock of reference pixels. For the third phase, there is a comparison for each motion vector in the three sets of eight motion vectors. As in the second phase, the sets of motion vectors may overlap in the third phase. The motion vector corresponding to the best match from the third phase is selected as the motion vector for the current macroblock.
______________________________________ for(I=0; I<32, I++) for(j=0; j<BlockSize; j++) { for(k=0; k<BlockSize; k++) { QuantSet[i][j][k] = (BaseMatrix[j][k] *i* ScaleMatrix[j][k]) >> 6; if( QuantSet[i][j][k] > 511 ) QuantSet[i][j][k] = 511; if( QuantSet[i][j][k] < 1 ) QuantSet[i][j][k] = 1; } } } ______________________________________
BlockSize is the size of blocks of coefficients to be quantized (e.g., 8 for (8.times.8) blocks)
______________________________________ o For (8.times.8) slant and (8.times.8) DCT transforms: 0 1 5 6 14 15 27 28 2 4 7 13 16 26 29 42 3 8 12 17 25 30 41 43 9 11 18 24 31 40 44 53 10 19 23 32 39 45 52 54 20 22 33 38 46 51 55 60 21 34 37 47 50 56 59 61 35 36 48 49 57 58 62 63 o For the 8.times.8 Slaar: 1 2 6 7 33 34 38 39 3 5 8 13 35 37 40 45 4 9 12 14 36 41 44 46 10 11 15 16 42 43 47 48 17 18 22 23 49 50 54 55 19 21 24 29 51 53 56 61 20 25 28 30 52 57 60 62 26 27 31 32 58 59 63 64 o For (8.times.8) Haar transform: 0 2 6 7 16 17 18 19 1 3 10 11 28 29 30 31 4 8 24 25 40 41 42 43 5 9 26 27 47 46 45 44 12 20 32 33 48 49 50 51 13 21 35 34 55 54 53 52 14 22 36 37 56 57 58 59 15 23 39 38 63 62 61 60 o For all (1.times.8) Haar transforms: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 o For all (8.times.1) transforms: 0 8 16 24 32 40 48 56 1 9 17 25 33 41 49 57 2 10 18 26 34 42 50 58 3 11 19 27 35 43 51 59 4 12 20 28 36 44 52 60 5 13 21 29 37 45 53 61 6 14 22 30 38 46 54 62 7 15 23 31 39 47 55 63 o For (8.times.8) blocks that are not transformed: 0 1 5 6 14 15 27 28 2 4 7 13 16 26 29 42 3 8 12 17 25 30 41 43 9 11 18 24 31 40 44 53 10 19 23 32 39 45 52 54 20 22 33 38 46 51 55 60 21 34 37 47 50 56 59 61 35 36 48 49 57 58 62 63 o For (4.times.4) slant and (4.times.4) DCT transforms: 0 1 5 6 2 4 7 12 3 8 11 13 9 10 14 15 o For the 4.times.4 Slaar: 1 2 9 10 3 4 11 12 5 6 13 14 7 8 15 16 o For (4.times.4) Haar transform: 0 1 8 9 2 3 11 10 4 5 12 13 7 6 14 15 o For all (4.times.1) transforms: 0 4 8 12 1 5 9 13 2 6 10 14 3 7 11 15 o For all (1.times.4) transforms: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 o For (4.times.4) blocks that are not transformed: 0 1 5 6 2 4 7 12 3 8 11 13 9 10 14 15 ______________________________________
______________________________________ switch( Context->FrameType ) case PIC.sub.-- TYPE.sub.-- I: case PIC.sub.-- TYPE.sub.-- K: {//for intra or key frames ByteDelta = MaxBuffer/2 - GlobalByteBankFuliness; if( ByteDelta > 0 ) { //lower than half the buffer BytesForThisFrame = BytesPerI+ (ByteDelta*ReactPos)/256; } else { //exceeded half the buffer BytesForThisFrame = BytesPerI+ (ByteDelta*ReactNeg)/256; }//endif GlobalByteBankFullness -= BytesPerI; }//end case I or K frame break; case PIC.sub.-- TYPE.sub.-- D: {//for delta frames ByteDelta = MaxBuffer/2 - GlobalByteBankFullness; if( ByteDelta > 0 ) { // lower than half the buffer BytesForThisFrame = BytesPerD+ (ByteDelta*ReactPos)/256; } else { //exceeded half the buffer BytesForThisFrame = BytesPerD+ (ByteDelta*ReactNeg)/256; } GlobalByteBankFullness -= BytesPerD; //end case D frame break; case PIC.sub.-- TYPE.sub.-- B: {//for bidirectional frames ByteDelta = Buffer/2 - GlobalByteBankFuliness; if( ByteDelta > 0 ) { //lower than half the buffer BytesForThisFrame = BytesPerB+ (ByteDelta*ReactPos)/256; } else { //exceeded half the buffer BytesForThisFrame = BytesPerB+ (ByteDelta*ReactNeg)/256; } GlobalByteBankFullness -= BytesPerB; }//end case B frame break; } /*end switch frame type*/ ______________________________________
______________________________________ //Perform initial encode using current global Q level Initial Encode( GlobalQuant ) //Test if the number of bytes generated during the initial encode are less than the number of bytes allocated for this frame. if( BytesGenerated During Initial Encode < BytesForThisFrame ) Delta = 0; while( BytesGenerated < BytesForThisFrame && ABS(Delta) < 2 ) {//Decrement global Q level and perform trial encode. GlobalQuant -= 1 BytesGenerated = Trial Encode( GlobalQuant ) Delta -= 1 } } else { Delta = 0; while( BytesGenerated < BytesForThisFrame && ABS(Delta) <2 ) {//Increment global Q level and perform trial encode. GlobalQuant += 1 BytesGenerated = Trial encode( GlobalQuant ) Delta += 1; } } //Perform final encode using selected global Q level. ______________________________________
______________________________________ for (p=0 to BlockSize) { for (q=0 to BlockSize) { E(p,q) = 0; for (i=1 to N) { E(p,q) += ABS ( Bi(p,q) ); } E(p,q)/= N; //Normalization step. } ______________________________________
Referring now to FIG. 15, there is shown a representation of an example of the band scan pattern generated during steps 1402 and 1404 of FIG. 14 for a band having (4.times.4) coefficient blocks. Block 1502 shows the sums for the 16 coefficients of the (4.times.4) blocks for the current band. The values shown in block 1502 were selected to demonstrate the constrained sorting rule and are not intended to represent realistic values accumulated for real video images.
Referring now to FIG. 20, there is shown a flow diagram of the processing implemented by Huffman decoder 1802 of FIG. 18, according to a preferred embodiment of the present invention. Huffman decoder 1802 decodes VLE signals by considering k bits of the bitstream at a time. If N is the number of bits in the shortest code, then k.gtoreq.N. In a preferred embodiment, N varies during run time and k is 10.
______________________________________ TB (bits 0-3) Represents the number of bits of the k bits that are decoded by the current table entry (i.e., the number of bits in the k-bit signal that correspond to the complete VLE signals). This value is used to update the bitstream pointer. NC (bits 4-5) Represents the number of VLE codes that are decoded by the current table entry (i.e., the number of the complete VLE signals in the k-bit signal). PS (bits 6-7) Indicates the position of a special VLE code (e.g., an end-of-block (EOB) code), if one is present in the current table entry. Cl (bits 8-15) Represents the decoded value for the first complete VLE code in the k bits, if a first complete VLE code is present. C2 (bits 16-23) Represents the decoded value for the second complete VLE code in the k bits, if a second complete VLE code is present. C3 (bits 24-31) Represents the decoded value for the third complete VLE code in the k bits, if a third complete VLE code is present. ______________________________________
In a cache-efficient embodiment of the present invention, the value of k is chosen based on the size of the data cache on the CPU. The value of k can also be used to tailor the branch behavior to match what the CPU performs well on (minimizing branches). In a preferred embodiment, k is 10. With k=10, the lookup table fits within the unified cache of an Intel.RTM. 486.TM. processor and does not exceed one half of the size of the data cache of the Intel.RTM. Pentium.TM. processor. If the average VLE code size is 5 bits, using k=10 provides an average of two VLE codes decoded per table lookup.
__________________________________________________________________________ Target # of Y Y-Band UV-Band Motion Vector Mode Platform Scalability Bands Transforms Transforms Resolution __________________________________________________________________________ 0 High On 4 Sl8.times.8, Sl4.times.4 Half Pixel Sl1.times.8, Sl8.times.1, None 1 Medium On 4 Hr8.times.8, Hr4.times.4 Half Pixel Hr1.times.8, Hr8.times.1, None 2 Low On 4 Hr8.times.8 Hr4.times.4 Integer Pixel None, None, None 3 High Off 1 Sl8.times.8 Sl4.times.4 Half Pixel 4 Medium Off 1 Hr8.times.8 Hr4.times.4 Half Pixel 5 Low Off 1 Hr8.times.8 Hr4.times.4 Integer Pixel __________________________________________________________________________
______________________________________ Picture Band Tile Macroblock Block ______________________________________
Each band is subdivided into a regular grid of tiles, each of which is encoded in a self-contained section of the bitstream. Tiles permit local decoding of a video sequence (i.e., decoding of a sub-rectangle of the picture), and are also useful in minimizing latency in real-time encoding and decoding. Each tile is subdivided into a regular grid of macroblocks and blocks. Bits in the band header specify what the macroblock and block sizes are for all tiles in this band. Macroblocks can be either 16.times.16, 8.times.8, or 4.times.4. Blocks are either 8.times.8 or 4.times.4.
DCT8.times.1: an (8.times.1) discrete cosine transform,
DCT1.times.8: a (1.times.8) discrete cosine transform,
DCT8.times.8: an (8.times.8) discrete cosine transform,
DCT4.times.4: a (4.times.4) discrete cosine transform,
Slant8.times.1: an (8.times.1) slant transform,
Slant1.times.8: a (1.times.8) slant transform,
Slant8.times.8: an (8.times.8) slant transform,
Slant4.times.1: a (4.times.1) slant transform,
Slant1.times.4: a (1.times.4) slant transform,
Slant4.times.4: a (4.times.4) slant transform,
Slaar8.times.1: an (8.times.1) hybrid slant-Haar transform,
Slaar1.times.8: a (1.times.8) hybrid slant-Haar transform,
Slaar8.times.8: an (8.times.8) hybrid slant-Haar transform,
Slaar4.times.1: a (4.times.1) hybrid slant-Haar transform,
Slaar1.times.4: a (1.times.4) hybrid slant-Haar transform,
Slaar4.times.4: a (4.times.4) hybrid slant-Haar transform,
Haar8.times.1: an (8.times.1) Haar transform,
Haar1.times.8: a (1.times.8) Haar transform,
Haar8.times.8: an (8.times.8) Haar transform,
Haar4.times.1: a (4.times.1) Haar transform,
Haar1.times.4: a (1.times.4) Haar transform, and
Haar4.times.4: a (4.times.4) Haar transform.
Those skilled in the art will understand that, for a given size (e.g., 8.times.8), a DCT (discrete cosine transform) provides higher quality results than either a slant or a Haar transform, but that a DCT transform is also computationally more complex. A Haar transform is computationally less complex than a DCT or a slant transform, but also provides lower quality results.
Those skilled in the art will recognize that the Slaar transform exploits local redundancy in the first stage and then exploits more remote redundancies in the later stages. The first stage of the Slaar transform applies an invertible frequency decomposition on n input samples to generate .eta./2 high-frequency values and .eta./2 low-frequency values (e.g., same as the first stage of a Haar or Daubechies transform). The second stage of the Slaar transform is an (.eta./2.times.1) transform that is either a generalized slant or a DCT transform (i.e., not a Haar or Hademard transform).
Slant8.times.1, Slant1.times.8
The Slant8.times.1 transform is the Slant8 transform applied to each of the eight rows in an 8.times.8 block and the Slant1.times.8 transform is the Slant8 transform applied to each of the eight columns in an 8.times.8 block. The forward Slant8 transform is defined by the following C code:
______________________________________ #define bfly(x,y) t1 = x-y; x += y; y = t1; #define NUM1 40 #define NUM2 16 #define DEN 29 /* The following is a reflection using a,b = 16/29, 40/29 without prescale and with rounding. */ #define freflect(s1,s2).backslash. t = ((NUM1*s1) + (NUM2*s2) + DEN/2)/DEN,.backslash. s2 = ((NUM2*s1) - (NUM1*s2) + DEN/2)/DEN:.backslash. s1 = t; r1 = *src++; r2 = *src++; r3 = *src++; r4 = *src++; r5 = *Src++; r6 = *src++; r7 = *src++; r8 = *Src++; bfly(r1,r4); bfly(r2,r3); bfly(r5,r8); //FSlantPart1 bfly(r6,r7); bfly(r1,r2); freflect(r4,r3); bfly(r5,r6); //FSlantPart2 freflect(r8,r7); bfly(r1,r5); bfly(r2,r6); bfly(r7,r3); //FSlantPart3 bfly(r4,r8); t = r5 - (r5>>3) + (r4>>1); //FSlantPart4 r5 = r4 - (r4>>3) - (r5>>1); r4 = t; *dst++ = r1; *dst++ = r4; *dst++ = r8; *dst++ = r5; *dst++ = r2; *dst++ = r6; *dst++ = r3; *dst++ = r7; } ______________________________________
Src is a pointer to the input linear (e.g., 8.times.1) array to be forward transformed, and
Dst is a pointer to the output linear (e.g., 8.times.1) forward transformed array.
______________________________________ #define bfly(x,y) t1 = x-y; x += y; y = t1; /* The following is a reflection with rounding using a,b = 1/2, 5/4. */ #define reflect(s1,s2).backslash. t = (s1*5 + s2*2 + 2) >> 2;.backslash. s2 = (s1*2 - s2*5 + 2) >> 2;.backslash. s1 = t; r1 = *Src++; r4 = *Src++; r8 = *Src++; r5 = *Src++; r2 = *Src++; r6 = *Src++; r3 = *Src++; r7 = *Src++; t = (r4*4 + r5*7 + 4) >> 3;.backslash. //ISlantPart1 r5 = (r4*7 - r5*4 + 4) >> 3;.backslash. r4 = t; bfly(r1,r5); bfly(r2,r6); bfly(r7,r3); bfly(r4,r8); //ISlantPart2 bfly(r1,r2); reflect(r4,r3); bfly(r5,r6); //ISlantPart3 reflect(r8,r7); bfly(r1,r4); bfly(r2,r3); bfly(r5,r8); bfly(r6,r7); //ISlantPart4 *Dst++ = r1; *Dst++ = r2; *Dst++ = r3; *Dst++ = r4; *Dst++ = r5; *Dst++ = r6; *Dst++ = r7; *Dst++ = r8; } ______________________________________
Src is a pointer to the input linear (e.g., 8.times.1) array to be inverse transformed, and
Dst is a pointer to the output linear (e.g., 8.times.1) inverse transformed array.
Slant8.times.8
The forward Slant8.times.8 transform has three parts:
(1) Slant8.times.1 forward,
(2) Slant1.times.8 forward, and
The inverse Slant8.times.8 transform also has three parts:
(1) Slant1.times.8 inverse,
(2) Slant8.times.1 inverse, and
Slant4.times.1, Slant1.times.4
The Slant4.times.1 transform is the Slant4 transform applied to each of the four rows in a 4.times.4 block and the Slant1.times.4 transform is the Slant4 transform applied to each of the four columns in a 4.times.4 block. The forward Slant4 transform is defined by the following C code:
______________________________________ #define bfly(x,y) t1 = x-y; x += y; y = t1; #define NUM1 40 #define NUM2 16 #define DEN 29 /* The following is a reflection using a,b = 16/29, 40/29 without prescale and with rounding. */ #define freflect(s1,s2).backslash. t = ((NUM1*s1) + (NUM2*s2) +DEN/2)/DEN;.backslash. s2 = ((NUM2*s1) - (NUM1*s2) + DEN/2)/DEN;.backslash. s1 = t; r1 = *Src++; r2 = *Src++; r3 = *Src++; r4 = *Src++; bfly(r1,r4); bfly(r2,r3); //FSlantPart1 freflect(r4,r3); bfly(r1,r2); //FSlantPart2 *Dst++ = r1; *Dst++ = r4; *Dst++ = r2; *Dst++ = r3; } ______________________________________
Src is a pointer to the input linear (e.g., 4.times.1) array to be forward transformed, and
Dst is a pointer to the output linear (e.g., 4.times.1) forward transformed array.
______________________________________ #define bfly(x,y) t1 = x-y; x += y; y = t1; /* The following is a reflection with rounding using a,b = 1/2, 5/4. */ #define reflect(s1,s2).backslash. t = (s1*5 + s2*2 + 2) >> 2;.backslash. s2 = (s1*2 - s2*5 + 2) >> 2;.backslash. s1 = t; r1 = *p++; r4 = *p++; r2 = *p++; r3 = *p++; bfly(r1,r2); reflect(r4,r3); //SlantPart1 bfly(r1,r4); bfly(r2,r3); //SlantPart2 *p++ = r1; *p++ = r2; *p++ = r3; *p++ = r4; } ______________________________________
Src is a pointer to the input linear (e.g., 4.times.1) array to be inverse transformed, and
Dst is a pointer to the output linear (e.g., 4.times.1) inverse transformed array.
Slant4.times.4
The forward Slant4.times.4 transform has three parts:
(1) Slant4.times.1 forward,
(2) Slant1.times.4 forward, and
The inverse Slant4.times.4 transform also has three parts:
(1) Slant1.times.4 inverse,
(2) Slant4.times.1 inverse, and
Slaar8.times.1, Slaar1.times.8
The Slaar8.times.1 transform is the Slaar8 transform applied to each of the eight rows in an 8.times.8 block and the Slaar1.times.8 transform is the Slaar8 transform applied to each of the eight columns in an 8.times.8 block. The forward Slaar8 transform is defined by the following C code:
______________________________________ #define bfly(x,v) t1 = x-y; x +=y; y = t1; #defineNUM1 40 #define NUM2 16 #define DEN 29 /* The following is a reflection using a,b = 16/29, 40/29. */ #define freflect(s1,s2).backslash. t = ((NUM1*s1) + (NUM2*s2) + DEN/2 )/DEN;.backslash. s2 = ((NUM2*s1) - (NUM1*s2) + DEN/2 )/DEN;.backslash. s1 = t; /* The following is a reflection using a,b = 1/2, 5/4. */ #define freflect(s1,s2).backslash. t = sl + (s1>>2) + (s2>>1);.backslash. s2 = -s2 - (s2>>2) + (s1>>1);.backslash. s1 = t; r1 = *Src++; r2 = *Src++; r3 = *Src++; r4 = *Src++; r5 = *Src++; r6 = *Src++; r7 = *Src++; r8 = *Src++; bfly(r1,r2); bfly(r3,r4); bfly(r5,r6); bfly(r7,r8); bfly(r1,r7); bfly(r3,r5); bfly(r2,r8); bfly(r4,r6); freflect(r7,r5); bfly(rl,r3); freflect(r8,r6); bfly(r2,r4); *Dst++ = r1; *Dst++ = r7; *Dst++ = r3; *Dst++ = r5; *Dst++ = r2; *Dst++ = r8; *Dst++ = r4; *Dst++ = r6; } ______________________________________
______________________________________ #define bfly(x,y) t1 = x-y; x += y; y = t1; #define bfly2(x,y) t1 = x-y; x += y; y = DIV2(t1); x = DIV2(x); #define reflect(s1,s2) t = s1 + (s1>>2) + (s2>>1); s2 = -s2 - (s2>>2) + (s1>>1); s1 = t; r1 = *Src++; r7 = *Src++; r3 = *Src++; r5 = *Src++; r2 = *Src++; r8 = *Src++; r4 = *Src++; r6 = *Src++; reflect(r7,r5); bfly(r1,r3); reflect(r8,r6); bfly(r2,r4); bfly(r1,r7); bfly(r3,r5); bfly(r2,r8); bfly(r4,r6); bfly2(r1,r2); bfly2(r3,r4); bfly2(r5,r6); bfly2(r7,r8); *Dst++ = r1; *Dst++ = r2; *Dst++ = r3; *Dst++ = r4; *Dst++ = r5; *Dst++ = r6; *Dst++ = r7; *Dst++ = r8; } ______________________________________
Slaar8.times.8
The forward Slaar8.times.8 transform has three parts:
(1) Slaar8.times.1 forward,
(2) Slaar1.times.8 forward, and
The inverse Slaar8.times.8 transform also has three parts:
(1) Slaar1.times.8 inverse,
(2) Slaar8.times.1 inverse, and
Slaar4.times.1, Slaar1.times.4
The Slaar4.times.1 transform is the Slaar4 transform applied to each of the four rows in a 4.times.4 block and the Slaar1.times.4 transform is the Slaar4 transform applied to each of the four columns in a 4.times.4 block. The forward Slaar4 transform is defined by the following C code:
______________________________________ #define bfly(x,y) t1 = x-y; x += y; y = t1; #define NUM1 40 #define NUM2 16 #define DEN 29 /* The following is a reflection using a,b = 16/29, 40/29 without prescale and with rounding. */ #define freflect(s1,s2).backslash. t = ((NUM1*s1) + (NUM2*s2) + DEN/2 )/DEN;.backslash. s2 = ((NUM2*s1) - (NUM1*s2) + DEN/2 )/DEN;.backslash. s1 = t; r1 = *Src++; r2 = *Src++; r3 = *Src++; r4 = *Src++; bfly(r1,r2); bfly(r3,r4); // FSlaarPart1 bfly(r1,r3); bfly(r2,r4); // FSlaarPart2 *Dst++ = r1; *Dst++ = r3; *Dst++ = r2; *Dst++ = r4; } ______________________________________
______________________________________ #define bfly(x,y) t1 = x-y; x += y; y = t1; /* The following is a reflection using a,b = 1/2, 5/4. */ #define reflect(s1,s2).backslash. t = s1 + (s1>>2) + (s2>>1);.backslash. s2 = -s2 - (s2>>2) + (s1>>1);.backslash. s1 = t; r1 = *p++; r3 = *p++; r2 = *p++; r4 = *p++; bfly(r1,r3); bfly(r2,r4); // ISlaarPart 1 bfly(r1,r2); bfly(r3,r4); // ISlaarPart 2 *p++ = r1; *p++ = r2; *p++ = r3; *p++ = r4; } ______________________________________
Slaar4.times.4
The forward Slaar4.times.4 transform has three parts:
(1) Slaar4.times.1 forward,
(2) Slaar1.times.4 forward, and
The inverse Slaar4.times.4 transform also has three parts:
(1) Slaar1.times.4 inverse,
(2) Slaar4.times.1 inverse, and
Haar8.times.1, Haar1.times.8
The Haar8.times.1 transform is the Haar8 transform applied to each of the eight rows in an 8.times.8 block and the Haar1.times.8 transform is the Haar8 transform applied to each of the eight columns in an 8.times.8 block. The forward Haar8 transform is defined by the following C code:
______________________________________ #define DIV2(x) ((x)>0?(x)>>1:-(-(x))>>1) #define bfly(x,y) t1 = x-y; x += y; y = t1; #define bfly2(x,y) t1 = x-y; x += y; y = DIV2(t1); x = DIV2(x); r1 = *Src++; r2 = *Src++; r3 = *Src++; r4 = *Src++; r5 = *Src++; r6 = *Src++; r7 = *Src++; r8 = *Src++; bfly(r1,r2); bfly(r3,r4); bfly(r5,r6); bfly(r7,r8); //HaarFwd1 bfly(r1,r3); bfly(r5,r7); //HaarFwd2; bfly(r1,r5); //HaarFwd3; r1 = DIV2(r1); r5 = DIV2(r5); *Dst++ = r1; *Dst++ = r5; *Dst++ = r3; *Dst++ = r7; *Dst++ = r2; *Dst++ = r4; *Dst++ = r6; *Dst++ = r8; } ______________________________________
______________________________________ #define DIV2(x) ((x)>0?(x)>>1:-(-(x))>>1) #define bfly2(x,y) t1 = x-y; x += y; y = DIV2(t1); x = DIV2(x); r1 = *Src++; r1 = r1<<1; r5 = *Src++; r5 = r5<<1; r3 = *Src++; r7 = *Src++; r2 = *Src++; r4 = *Src++; r6 = *Src++; r8 = *Src++; bfly2(r1,r5); //HaarInv1; bfly2(r1,r3); bfly2(r5,r7); //HaarInv2; bfly2(r1,r2); bfly2(r3,r4);bfly2(r5,r6); //HaarInv3; bfly2(r7,r8); *Dst++ = r1; *Dst++ = r2; *Dst++ = r3; *Dst++ = r4; *Dst++ = r5; *Dst++ = r6; *Dst++ = r7; *Dst++ = r8; } ______________________________________
Haar8.times.8
The forward Haar8.times.8 transform has three parts:
______________________________________ (1) Haar8.times.1 forward, (2) Haar1.times.8 forward, and (3) Scaling: for(i=0; i<8; i++) { for(j=0; j<8; j++) { c(i,j) = ( c(i,j))>> Scaling Matrix[i][j] } ______________________________________
______________________________________ { 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0. 0. 0, 0, 0, 0, 0, 0, 0, 0, 0 } ______________________________________
The inverse Haar8.times.8 transform also has three parts:
______________________________________ (1) Scaling: for(i=0; i<8; i++) for(j=0; j<8; j++) { c(i,j) = (c(i,j)) >> ScalingMatrix[i][j] } } ______________________________________
______________________________________ { 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0. 0, 0, 1, 1, 1, 1, 0, 0. 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, } (2) Haar1.times.8 inverse, and (3) Haar8.times.1 inverse. ______________________________________
Haar4.times.1, Haar1.times.4
The Haar4.times.1 transform is the Haar4 transform applied to each of the four rows in a 4.times.4 block and the Haar1.times.4 transform is the Haar4 transform applied to each of the four columns in a 4.times.4 block. The forward Haar4 transform is defined by the following C code:
______________________________________ #define DIV2(x) ((x)>0?(x)>>1:-(-(x))>>1) #define bfly(x,y) t1 = x-y; x += y; y = t1; #define bfly2(x,y) t1 = x-y; x += y; y = DIV2(t1); x = DIV2(x); r1 = *Src++; r3 = *Src++; r5 = *Src++; r7 = *Src++; bfly(r1,r3); bfly(r5,r7); //HaarFwd1; bfly(r1,r5); //HaarFwd2; *Dst++ = r1; *Dst++ = r5; *Dst++ = r3; *Dst++ = r7; } ______________________________________
______________________________________ #define DIV2(x) ((x)>0?(x)>>1:-(-(x))>>1) #define bfly2(x,y) t1 = x-y; x += y; y = DIV2(t1); x = DIV2(x); r1 = *Src++; r5 = *Src++; r3 = *Src++; r7 = *Src++; bfly2(r1,r5); //HaarInv1; bfly2(r1,r3); bfly2(r5,r7); //HaarInv2; *Dst++ = r1; *Dst++ = r3; *Dst++ = r5; *Dst++ = r7; } ______________________________________
Haar4.times.4
The forward Haar4.times.4 transform has three parts:
______________________________________ (1) Haar4.times.1 forward, (2) Haarl.times.4forward, and (3) Scaling: for(i=0; i<4; i++) for(j=0; j<4; j++) { c(i,j) = c(i,j)) >> ScalingMatrix[i][j] } } ______________________________________
______________________________________ { 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0. 0, 0, 0, 0 } ______________________________________
The inverse Haar4.times.4 transform also has three parts:
______________________________________ (1) Scaling: for(i=0; i<4; i++) for(j=0; j<4; j++) { c(i,j) = ( c(i,j)) >> ScalingMatrix[i][j] } } ______________________________________
______________________________________ { 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 } (2) Haar1.times.4 inverse, and (3) Haar4.times.1 inverse. ______________________________________
Previous Patent US 5,646,617 | Next Patent US 5,646,619