Source: http://www.google.com/patents/US5729691?dq=7,069,055
Timestamp: 2013-12-11 18:01:45
Document Index: 749062986

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

Patent US5729691 - Two-stage transform for video signals - Google PatentsSearch Images Maps Play YouTube News Gmail Drive More »Advanced Patent Search | Sign inAdvanced Patent SearchPatentsVideo signals are encoded by applying a forward transform, where the transform has a first stage that exploits local redundancies in the video signals; and a second stage, following the first stage, that exploits remote redundancies in results of the first stage. The transformed video signals are used...http://www.google.com/patents/US5729691?utm_source=gb-gplus-sharePatent US5729691 - Two-stage transform for video signalsPublication numberUS5729691 APublication typeGrantApplication numberUS 08/536,343Publication dateMar 17, 1998Filing dateSep 29, 1995Priority dateSep 29, 1995Fee statusPaidPublication number08536343, 536343, US 5729691 A, US 5729691A, US-A-5729691, US5729691 A, US5729691AInventorsRobit AgarwalOriginal AssigneeIntel CorporationExport CitationBiBTeX, EndNote, RefManPatent Citations (25), Non-Patent Citations (19), Referenced by (17), Classifications (11), Legal Events (5) External Links: USPTO, USPTO Assignment, EspacenetTwo-stage transform for video signalsUS 5729691 AAbstract Video signals are encoded by applying a forward transform, where the transform has a first stage that exploits local redundancies in the video signals; and a second stage, following the first stage, that exploits remote redundancies in results of the first stage. The transformed video signals are used to generate an encoded video bitstream. The transformed video signals are decoded by applying an inverse transform that corresponds to the forward transform.
What is claimed is: 1. A computer-implemented process for encoding video signals, comprising the steps of:(a) applying a forward transform to the video signals to generate transformed video signals, wherein the forward transform comprises:(1) a first stage that exploits local redundancies in the video signals; and (2) a second stage, following the first stage, that exploits remote redundancies in results of the first stage; and (b) encoding the transformed video signals to generate an encoded video bitstream. 2. The process of claim 1, wherein:the first stage applies an invertable frequency decomposition on n input samples to generate n/2 high-frequency values and n/2 low-frequency values; and the second stage comprises an (n/2 both the n/2 high-frequency values and the n/2 low-frequency values. 3. The process of claim 2, wherein:the first stage comprises the first stage of one of a Haar transform and a Daubechies transform; and the second stage comprises one of a generatized slant transform and a DCT transform. 4. The process of claim 3, wherein the video signals comprise one of pixels and pixel differences.
6. An apparatus for encoding video signals, comprising:(a) means for applying a forward transform to the video signals to generate transformed video signals, wherein the forward transform comprises:(1) a first stage that exploits local redundancies in the video signals; and (2) a second stage, following the first stage, that exploits remote redundancies in results of the first stage; and (b) means for encoding the transformed video signals to generate an encoded video bitstream. 7. The apparatus of claim 6, wherein:the first stage applies an invertable frequency decomposition on n input samples to generate n/2 high-frequency values and n/2 low-frequency values; and the second stage comprises an (n/2 both the n/2 high-frequency values and the n/2 low-frequency values. 8. The apparatus of claim 7, wherein:the first stage comprises the first stage of one of a Haar transform and a Daubechies transform; and the second stage comprises one of a generatized slant transform and a DCT transform. 9. The apparatus of claim 8, wherein the video signals comprise one of pixels and pixel differences.
11. A storage medium having stored thereon a plurality of instructions for encoding video signals, wherein the plurality of instructions, when executed by a processor, cause the processor to perform the steps of:(a) applying a forward transform to the video signals to generate transformed video signals, wherein the forward transform comprises:(1) a first stage that exploits local redundancies in the video signals; and (2) a second stage, following the first stage, that exploits remote redundancies in results of the first stage; and (b) encoding the transformed video signals to generate an encoded video bitstream. 12. The storage medium of claim 11, wherein:the first stage applies an invertable frequency decomposition on n input samples to generate n/2 high-frequency values and n/2 low-frequency values; and the second stage comprises an (n/2 both the n/2 high-frequency values and the n/2 low-frequency values. 13. The storage medium of claim 12, wherein:the first stage comprises the first stage of one of a Haar transform and a Daubechies transform; and the second stage comprises one of a generatized slant transform and a DCT transform. 14. The storage medium of claim 13, wherein the video signals comprise one of pixels and pixel differences.
16. A computer-implemented process for decoding encoded video signals, comprising the steps of:(a) decoding an encoded bitstream to generate transformed video signals; and (b) applying an inverse transform to the transformed video signals to generate decoded video signals, wherein the inverse transform corresponds to a forward transform comprising:(1) a first stage that exploits local redundancies in video signals; and (2) a second stage, following the first stage, that exploits remote redundancies in results of the first stage. 17. The process of claim 16, wherein:the first stage applies an invertable frequency decomposition on n input samples to generate n/2 high-frequency values and n/2 low-frequency values; and the second stage comprises an (n/2 both the n/2 high-frequency values and the n/2 low-frequency values. 18. The process of claim 17, wherein:the first stage comprises the first stage of one of a Haar transform and a Daubechies transform; and the second stage comprises one of a generatized slant transform and a DCT transform. 19. The process of claim 18, wherein the decoded video signals comprise one of pixels and pixel differences.
21. An apparatus for decoding encoded video signals, comprising:(a) means for decoding an encoded bitstream to generate transformed video signals; and (b) means for applying an inverse transform to the transformed video signals to generate decoded video signals, wherein the inverse transform corresponds to a forward transform comprising:(1) a first stage that exploits local redundancies in video signals; and (2) a second stage, following the first stage, that exploits remote redundancies in results of the first stage. 22. The apparatus of claim 21, wherein:the first stage applies an invertable frequency decomposition on n input samples to generate n/2 high-frequency values and n/2 low-frequency values; and the second stage comprises an (n/2 both the n/2 high-frequency values and the n/2 low-frequency values. 23. The apparatus of claim 22, wherein:the first stage comprises the first stage of one of a Haar transform and a Daubechies transform; and the second stage comprises one of a generatized slant transform and a DCT transform. 24. The apparatus of claim 23, wherein the decoded video signals comprise one of pixels and pixel differences.
26. A storage medium having stored thereon a plurality of instructions for decoding encoded video signals, wherein the plurality of instructions, when executed by a processor, cause the processor to perform the steps of:(a) decoding an encoded bitstream to generate transformed video signals; and (b) applying an inverse transform to the transformed video signals to generate decoded video signals, wherein the inverse transform corresponds to a forward transform comprising:(1) a first stage that exploits local redundancies in video signals; and (2) a second stage, following the first stage, that exploits remote redundancies in results of the first stage. 27. The storage medium of claim 26, wherein:the first stage applies an invertable frequency decomposition on n input samples to generate n/2 high-frequency values and n/2 low-frequency values; and the second stage comprises an (n/2 both the n/2 high-frequency values and the n/2 low-frequency values. 28. The storage medium of claim 27, wherein:the first stage comprises the first stage of one of a Haar transform and a Daubechies transform; and the second stage comprises one of a generatized slant transform and a DCT transform. 29. The storage medium of claim 28, wherein the decoded video signals comprise one of pixels and pixel differences.
This nonprovisional U.S. national application, filed under 35 U.S.C. 111(a), claims, under 37 C.F.R. filing date of provisional U.S. national application no. 60/001369, filed on Jul. 21, 1995 under 35 U.S.C. BACKGROUND OF THE INVENTION 1. Field of the Invention
Host processor 116 may be any suitable means for controlling the operations of the special-purpose video processing board and for performing video encoding. Host processor 116 is preferably an Intel microprocessor such as an Intel processor. System bus 114 may be any suitable digital signal transfer device and is preferably a Peripheral Component Interconnect (PCI) bus. Memory device 112 may be any suitable computer memory device and is preferably one or more dynamic random access memory (DRAM) devices. High-speed memory interface 110 may be any suitable means for interfacing between memory device 112 and host processor 116. Mass storage device 120 may be any suitable means for storing digital signals and is preferably a computer hard drive. Transmitter 118 may be any suitable means for transtmitting digital signals to a remote receiver. Those skilled in the art will understand that the encoded video signals may be transmitted using any suitable means of transmission such as telephone line, RF antenna, local area network, or wide area network.
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
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
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 (2 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."
QDelta=-8*log 2((Gradi+2*MeanGrad)/(2*Gradi+MeanGrad))if(Qlevel&amp;lt;8)Qdelta=0
This section describes the processing of motion estimator 602 of FIG. 6. Conventional motion estimation is based on comparisons between a block of pixels of the current frame and different blocks of pixels of a reference frame. Typically, the reference blocks are limited to being which a specified search region of the reference frame (e.g., .+-.31 pixels in the vertical and horizontal directions from the location in the reference frame that corresponds to the location of the current block in the current frame). Each comparison may be based on a measure of the "error" between the two blocks, such as a sum of absolute differences (SAD) or a sum of the square of differences (SSD). The reference block that yields the smallest error is typically used to generate the motion vector for the current block, where the motion vector is based on the displacement between the corresponding location of the current block in the reference frame and the selected reference block.
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 search range is .+-.15 pixels. FIGS. 7-9 show representations of the pixels in the current (16 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 current pixels is compared to a (4 this example, 49 comparisons are made, corresponding to the (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 "∘" 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 compared to a (8 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 macroblock of current pixels is compared to a (16 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&amp;lt;32; I++)for(j=0; j&amp;lt;BlockSize; j++){for(k=0; k&amp;lt;BlockSize; k++){QuantSet i! j! k! = (BaseMatrix j! k! * i * ScaleMatrix j! k!)&amp;gt;&amp;gt;6;if( QuantSet i! j! k! &amp;gt; 511 )   QuantSet i! j! k! = 511;if( QuantSet i! j! k! &amp;lt; 1 )   QuantSet i! j! k! = 1;}}}__________________________________________________________________________
BlockSize is the size of blocks of coefficients to be quantized (e.g., 8 for (8
K=m.sub.QST *m.sub.BPT
m.sub.QsT is the mean value of the elements of the QST table; and
m.sub.BPT is the mean value of the elements of the BPT table.
m.sub.QST is fixed for a given transform, while m.sub.BPT varies from band to band and from frame to frame.
______________________________________&#8728;   For (8    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&#8728;   For the 8    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&#8728;   For (8    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&#8728;   For all (1    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&#8728;   For all (8    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&#8728;   For (8    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&#8728;   For (4    0   1     5     6    2   4     7     12    3   8     11    13    9   10    14    15&#8728;   For the 4    1   2     9     10    3   4     11    12    5   6     13    14    7   8     15    16&#8728;   For (4    0   1     8     9    2   3     11    10    4   5     12    13    7   6     14    15&#8728;   For all (4    0   4     8     12    1   5     9     13    2   6     10    14    3   7     11    15&#8728;   For all (1    0   1     2     3    4   5     6     7    8   9     10    11    12  13    14    15&#8728;   For (4    0   1     5     6    2   4     7     12    3   8     11    13    9   10    14    15______________________________________
______________________________________switch( Context-&amp;gt;FrameType)case PIC.sub.-- TYPE.sub.-- I:case PIC.sub.-- TYPE.sub.-- K:{ // for intra or key framesByteDelta = MaxBuffer/2 - GlobalByteBankFullness;if( ByteDelta &amp;gt; 0){     // lower than half the buffer BytesForThisFrame = BytesPerI+(ByteDelta*ReactPos)/256;}else{     // exceeded half the buffer BytesForThisFrame = BytesPerI+(ByteDelta*ReactNeg)/256;} // endifGlobalByteBankFullness -= BytesPerI;} // end case I or K framebreak;casePlC.sub.-- TYPE.sub.-- D:{ // for delta framesByteDelta = MaxBuffer/2 - GlobalByteBankFullness;if( ByteDelta &amp;gt; 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 framebreak;case PIC.sub.-- TYPE.sub.-- B:{ // for bi-directional framesByteDelta = Buffer/2 - GlobalByteBankFullness;if( ByteDelta &amp;gt; 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 framebreak;}   /* end switch frame type */______________________________________
______________________________________// Perform initial encode using current global Q levelInitial Encode( GlobalQuant)// Test if the number of bytes generated during the initial encode areless than the number of bytes allocated for this frame.if( BytesGenerated During Initial Encode &amp;lt; BytesForThisFrame)Delta = 0;while( BytesGenerated &amp;lt; BytesForThisFrame &amp;&amp; ABS(Delta) &amp;lt; 2){ // Decrement global Q level and perform trial encode.GlobalQuant -= 1BytesGenerated = Trial Encode( GlobalQuant)Delta-= 1}}else{Delta = 0;while( BytesGenerated &amp;lt; BytesForThisFrame &amp;&amp; ABS(Delta) &amp;lt; 2){ // Increment global Q level and perform trial encode.GlobalQuant += 1BytesGenerated = Trial encode( GlobalQuant)Delta+= 1;}}// Perform final encode using selected global Q level.Final Encode( GlobalQuant)______________________________________
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 for the 16 coefficients of the (4 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.
The range of motion estimation and the maximum number of search points used can be constrained. For example, a 25-point subsampled log search yielding a search range of .+-.7 may be used. In addition, half-pixel motion estimation can be disabled. On B frames, the search range can be limited to the same total number of search points as in D frames, where B-frame motion estimation is performed using two reference flames.
Referring now to FIG. 21, there is shown a representation of the fields of each 32-bit table entry of the 2.sup.k lookup table, according to a preferred embodiment of the present invention. Each table entry contains the decoded values for up to three different VLE codes that may be contained in the next k bits of the bitstream.
Referring now to FIG. 23, there is shown a graphical representation of a preferred inverse wavelet transform applied to the four decoded bands of Y-component data for each video frame during decompression processing (step 1604 of FIG. 16). This inverse wavelet transform is defined by the following equations: ##EQU2## where b0, b1, b2, b3 are decoded Y-component band data and p0, p1, p2, p3 are the components of the decoded Y-component plane. The function "&gt;&gt;2" means "shift right two bits" and is equivalent to dividing a binary value by 4.
__________________________________________________________________________   Target   Scal-        # of Y            Y-Band                  UV-Band                        Motion VectorMode   Platform   ability        Bands            Transforms                  Transforms                        Resolution__________________________________________________________________________0  High On   4   Sl 8                   Sl 4                         Half Pixel            Sl 1             Sl 8             None1  Medium   On   4   Hr 8                   Hr 4                         Half Pixel            Hr 1             Hr 8             None2  Low  On   4   Hr 8                   Hr 4                         Integer Pixel            None,            None,            None3  High Off  1   Sl 8                   Sl 4                         Half Pixel4  Medium   Off  1   Hr 8                   Hr 4                         Half Pixel5  Low  Off  1   Hr 8                   Hr 4                         Integer Pixel__________________________________________________________________________
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 the 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 4
Slaar8
Slaar1
Slaar4
Those skilled in the art will understand that, for a given size (e.g., 8 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 n/2 high-frequency values and n/2 low-frequency values (e.g., same as the first stage of a Haar or Daubechies transtransform). The second stage of the Slaar transform is an (n/2 either a generalized slant or a DCT transform (i.e., not a Haar or Hademard transform).
The Slant8 eight rows in an 8 Slant8 transform applied to each of the eight columns in an 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 withoutprescale and with rounding. */#define freflect(s1,s2) t = ((NUM1*s1) + (NUM2*s2) + DEN/2 )/DEN; s2 = ((NUM2*s1) - (NUM1*s2) + DEN/2 )/DEN; 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); bfly(r6,r7); // FSlantPart1 bfly(r1,r2); freflect(r4,r3); bfly(r5,r6); freflect(r8,r7); //FSlantPart2 bfly(r1,r5); bfly(r2,r6); bfly(r7,r3); bfly(r4,r8); // FSlantPart3 t = r5 - (r5&amp;gt;&amp;gt;3) + (r4&amp;gt;&amp;gt;1); r5 = r4 - (r4&amp;gt;&amp;gt;3) - (r5&amp;gt;&amp;gt;1); r4 = t; //FSlantPart4 *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 transformed, and
Dst is a pointer to the output linear (e.g., 8 array.
__________________________________________________________________________#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)t = s1 + (s1&amp;gt;&amp;gt;2) + (s2&amp;gt;&amp;gt;1);s2 = -s2 - (s2&amp;gt;&amp;gt;2) + (s1&amp;gt;&amp;gt;1);s1 = t; r1 = *Src++; r4 = *Src++; r8 = *Src++; r5 = *Src++; r2 = *Src++; r6 = *Src++; r3 = *Src++; r7 = *Src++; t = r5 - (r5&amp;gt;&amp;gt;3) + (r4&amp;gt;&amp;gt;1); r5 = r4 - (r4&amp;gt;&amp;gt;3) - (r5&amp;gt;&amp;gt;1); r4 = t; //ISlantPart1 bfly(r1,r5); bfly(r2,r6); bfly(r7,r3); bfly(r4,r8); // ISlantPart2 bfly(r1,r2); reflect(r4,r3); bfly(r5,r6); reflect(r8,r7); //ISlantPart3 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;}__________________________________________________________________________
The forward Slant8
(1) Slant8
(2) Slant1
c(i,j)=(c(i,j)+16)&amp;gt;&amp;gt;5
The inverse Slant8
(1) Slant1
(2) Slant8
c(i,j)=(c(i,j)+1)&amp;gt;&amp;gt;1
The Slant4 four rows in a 4 Slant4 transform applied to each of the four columns in a 4 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 withoutprescale and with rounding. */#define freflect(s1,s2) t = ((NUM1*s1) + (NUM2*s2) + DEN/2)/DEN; s2 = ((NUM2*s1) - (NUM1*s2) + DEN/2)/DEN; 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 transformed, and
Dst is a pointer to the output linear (e.g., 4 array.
______________________________________#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)t = s1 + (s1&amp;gt;&amp;gt;2) + (s2&amp;gt;&amp;gt;1);s2 = -s2 - (s2&amp;gt;&amp;gt;2) + (s1&amp;gt;&amp;gt;1);s1 = t; r1 = *p++; r4 = *p++; r2 = *p++; r3 = *p++; bfly(r1,r2); reflect(r4,r3); // ISlantPart 1 bfly(r1,r4); bfly(r2,r3); // ISlantPart 2 *p++ = r1; *p++ = r2; *p++ = r3; *p++ = r4;}______________________________________
The forward Slant4
(1) Slant4
c(i,j)=(c(i,j)+2)&amp;gt;&amp;gt;2
The inverse Slant4
(2) Slant4
The Slaar8 eight rows in an 8 Slaar8 transform applied to each of the eight columns in an 8 block. The forward Slaar8 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. */#define freflect(s1,s2) t = (NUM1*s1) + (NUM2*s2) + DEN/2 )/DEN; s2 = ((NUM2*s1) - (NUM1*s2) + DEN/2 )/DEN; s1 = t;/* The following is a reflection using a,b = 1/2, 5/4. */#define freflect(s1,s2) t = s1 + (s1&amp;gt;&amp;gt;2) + (s2&amp;gt;&amp;gt;1); s2 = -s2 - (s2&amp;gt;&amp;gt;2) + (s1 &amp;gt;&amp;gt;1); 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(r1,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&amp;gt;&amp;gt;2) + (s2&amp;gt;&amp;gt;1); s2 = -s2 - (s2&amp;gt;&amp;gt;2) +(s1&amp;gt;&amp;gt;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;__________________________________________________________________________
The forward Slaar8
(1) Slaar8
(2) Slaar1
The inverse Slaar8
(1) Slaar1
(2) Slaar8
The Slaar4 four rows in a 4 Slaar4 transform applied to each of the four columns in a 4 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 withoutprescale and with rounding. */#define freflect(s1,s2) t = ((NUM1*s1) + (NUM2*s2) + DEN/2 )/DEN; s2 = ((NUM2*s1) - (NUM1*s2) + DEN/2 )/DEN; 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)t = s1 + (s1&amp;gt;&amp;gt;2) + (s2&amp;gt;&amp;gt;1);s2 = -s2 - (s2&amp;gt;&amp;gt;2) + (s1&amp;gt;&amp;gt;1);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;}______________________________________
The forward Slaar4
(1) Slaar4
The inverse Slaar4
(2) Slaar4
The Haar8 eight rows in an 8 Haar 8 transform applied to each of the eight columns in an 8 block. The forward Haar8 transform is defined by the following C code:
______________________________________#define DIV2(x) ((x)&amp;gt;0?(x)&amp;gt;&amp;gt;1:-(-(x))&amp;gt;&amp;gt;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)&amp;gt;0?(x)&amp;gt;&amp;gt;1:-(-(x))&amp;gt;&amp;gt;1)#define bfly2(x,y) t1 = x-y; x += y; y = DIV2(t1); x = DIV2(x); r1 = *Src++; r1 = r1&amp;lt;&amp;lt;1; r5 = *Src++; r5 = r5&amp;lt;&amp;lt;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,4); bfly2(r5,r6); bfly2(r7,r8); // HaarInv3; *Dst++ = r1; *Dst++ = r2; *Dst++ = r3; *Dst++ = r4; *Dst++ = r5; *Dst++ = r6; *Dst++ = r7; *Dst++ = r8;}______________________________________
The forward Haar8
(1) Haar8
(2) Haar1
The inverse Haar8
(3) Haar8
The Haar4 four rows in a 4 Haar4 transform applied to each of the four columns in a 4 The forward Haar4 transform is defined by the following C code: ##EQU9## The inverse Haar8 transform is defined by the following C code: ##EQU10## Haar4
The forward Haar4
(1) Haar4
The inverse Haar4
(3) Haar4
FIGS. 7-9 show representations of the pixels in the current (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 coefficient blocks;
FIG. 21 is a representation of the fields of each 32-bit table entry of the 2.sup.k lookup table used by the Huffman decoder of FIG. 18;
Patent CitationsCited PatentFiling datePublication dateApplicantTitleUS4229820 *Jul 27, 1978Oct 21, 1980Kakusai Denshin Denwa Kabushiki KaishaMultistage selective differential pulse code modulation systemUS4302775 *Dec 15, 1978Nov 24, 1981Compression Labs, Inc.Digital video compression system and methods utilizing scene adaptive coding with rate buffer feedbackUS4449194 *Sep 25, 1981May 15, 1984Motorola Inc.Multiple point, discrete cosine processorUS4698689 *Mar 28, 1986Oct 6, 1987Gte Laboratories IncorporatedProgressive image transmissionUS4791598 *Mar 24, 1987Dec 13, 1988Bell Communications Research, Inc.Two-dimensional discrete cosine transform processorUS4829465 *Jun 19, 1986May 9, 1989American Telephone And Telegraph Company, At&T Bell LaboratoriesHigh speed cosine transformUS5029122 *Dec 27, 1989Jul 2, 1991Kabushiki Kaisha ToshibaDiscrete cosine transforming apparatusUS5054103 *Sep 22, 1988Oct 1, 1991Matsushita Electric Works, Ltd.Picture encoding systemUS5107345 *May 28, 1991Apr 21, 1992Qualcomm IncorporatedAdaptive block size image compression method and systemUS5157488 *May 17, 1991Oct 20, 1992International Business Machines CorporationAdaptive quantization within the jpeg sequential modeUS5196933 *Mar 19, 1991Mar 23, 1993Etat Francais, Ministere Des PttEncoding and transmission method with at least two levels of quality of digital pictures belonging to a sequence of pictures, and corresponding devicesUS5224062 *Mar 17, 1992Jun 29, 1993Sun Microsystems, Inc.Method and apparatus for fast implementation of inverse discrete cosine transform in a digital image processing system using optimized lookup tablesUS5235420 *Mar 22, 1991Aug 10, 1993Bell Communications Research, Inc.Multilayer universal video coderUS5249146 *Mar 20, 1992Sep 28, 1993Mitsubishi Denki Kabushiki KaishaDct/idct processor and data processing methodUS5253192 *Nov 14, 1991Oct 12, 1993The Board Of Governors For Higher Education, State Of Rhode Island And Providence PlantationsSignal processing apparatus and method for iteratively determining Arithmetic Fourier TransformUS5260782 *Aug 31, 1992Nov 9, 1993Matsushita Electric Industrial Co., Ltd.Adaptive DCT/DPCM video signal coding methodUS5333212 *Nov 17, 1992Jul 26, 1994Storm TechnologyImage compression technique with regionally selective compression ratioUS5339164 *Dec 24, 1991Aug 16, 1994Massachusetts Institute Of TechnologyMethod and apparatus for encoding of data using both vector quantization and runlength encoding and using adaptive runlength encodingUS5341318 *Dec 1, 1992Aug 23, 1994C-Cube Microsystems, Inc.System for compression and decompression of video data using discrete cosine transform and coding techniquesUS5367629 *Dec 18, 1992Nov 22, 1994Sharevision Technology, Inc.Digital video compression system utilizing vector adaptive transformUS5371611 *Aug 17, 1993Dec 6, 1994Kokusai Denshin Denwa Kabushiki KaishaMethod for and system of decoding compressed continuous-tone digital image dataUS5414469 *Oct 31, 1991May 9, 1995International Business Machines CorporationMotion video compression system with multiresolution featuresUS5446495 *Jun 9, 1992Aug 29, 1995Thomson-CsfTelevision signal sub-band coder/decoder with different levels of compatibilityUS5497777 *Sep 23, 1994Mar 12, 1996General Electric CompanySpeckle noise filtering in ultrasound imagingUS5546477 *Mar 30, 1993Aug 13, 1996Klics, Inc.Data compression and decompression* Cited by examinerNon-Patent CitationsReference1Allen et al., "The Multiply-Free Chen Transform--A Rational Approach to JPFG," 1991.2 *Allen et al., The Multiply Free Chen Transform A Rational Approach to JPFG, 1991.3DeVore, Ronald A., et al., "Image Compression Through Wavelet Transform Coding." IEEE Transactions on Information Theory, vol. 38, No. 2, Mar. 1992.4 *DeVore, Ronald A., et al., Image Compression Through Wavelet Transform Coding. IEEE Transactions on Information Theory, vol. 38, No. 2, Mar. 1992.5 *Discrete Cosine Transform Algorithms, Advantages, Applications, by K.R. Rao and P. Yip, published by Academic Press, Inc., dated 1990; 33 pages.6 *IEEE Standard Specifications for the Implementations of 8 8 Inverse Discrete Cosine Transform, IEEE Std. 1/80 1990, Jul. 16, 1992; 14 pages.7IEEE Standard Specifications for the Implementations of 8 Discrete Cosine Transform, IEEE Std. 1/80-1990, Jul. 16, 1992; 14 pages.8McMillan et al., "A Foward-Mapping Realization of the Inverse Discrete Cosine Transform." Sun Microsystems, Inc., Research Triangle Park, NC 27709., 1992.9 *McMillan et al., A Foward Mapping Realization of the Inverse Discrete Cosine Transform. Sun Microsystems, Inc., Research Triangle Park, NC 27709., 1992.10 *Practical Fast 1 D DCT Algorithms with 11 Multiplications, by Christoph Loeffler, Adriaan Ligtenberg, and George S. Moschytz, 1989 IEEE; pp. 988 991.11Practical Fast 1-D DCT Algorithms with 11 Multiplications, by Christoph Loeffler, Adriaan Ligtenberg, and George S. Moschytz, 1989 IEEE; pp. 988-991.12 *Prioritized DCT for Compression and Progressive Transmission of Images, by Yunming Huang, Howard M. Dreizen, and Nikolas P. Galatsanos, Members, IEEE, published by IEEE Transactions on Image Processing, vol. 1, No. 4, dated Oct. 1992; pp. 477 487.13Prioritized DCT for Compression and Progressive Transmission of Images, by Yunming Huang, Howard M. Dreizen, and Nikolas P. Galatsanos, Members, IEEE, published by IEEE Transactions on Image Processing, vol. 1, No. 4, dated Oct. 1992; pp. 477-487.14Shapiro, Jerome M. "An Embedded Hierarchical Image Coder Using Zerotress of Wavelet Coefficients." The David Sarnoff Research Center, a Subsidiary of SRI International, Princeton, NJ 08543-5300. To appear in Proc. Data Compresison Conference, Snowbird, UT, 1993.15 *Shapiro, Jerome M. An Embedded Hierarchical Image Coder Using Zerotress of Wavelet Coefficients. The David Sarnoff Research Center, a Subsidiary of SRI International, Princeton, NJ 08543 5300. To appear in Proc. Data Compresison Conference, Snowbird, UT, 1993.16Shapiro, Jerome M., "An Embedded Wavelet Hierarchical Image Coder," The David Sarnoff Research Center, a Subsidiary of SRI International, Princeton, NJ 08543-5300, Proc. Int. Conf. On Acoustics, Speech, and Signal Processing (ICASSP), San Franncisco, CA, Mar. 23-26, 1992, vol. IV. pp. 657-660.17 *Shapiro, Jerome M., An Embedded Wavelet Hierarchical Image Coder, The David Sarnoff Research Center, a Subsidiary of SRI International, Princeton, NJ 08543 5300, Proc. Int. Conf. On Acoustics, Speech, and Signal Processing (ICASSP), San Franncisco, CA, Mar. 23 26, 1992, vol. IV. pp. 657 660.18 *Wavelets and Image Compression by John C. Huffman, SMPTE Journal, Nov. 1994, pp. 723 727.19Wavelets and Image Compression by John C. Huffman, SMPTE Journal, Nov. 1994, pp. 723-727.* Cited by examinerReferenced byCiting PatentFiling datePublication dateApplicantTitleUS5949912 *Jun 27, 1997Sep 7, 1999Oki Electric Industry Co., Ltd.Image coding method and apparatusUS6330283Apr 18, 2000Dec 11, 2001Quikcat. Com, Inc.Method and apparatus for video compression using multi-state dynamical predictive systemsUS6400766Apr 18, 2000Jun 4, 2002Quikcat.Com, Inc.Method and apparatus for digital video compression using three-dimensional cellular automata transformsUS6456744Apr 18, 2000Sep 24, 2002Quikcat.Com, Inc.Method and apparatus for video compression using sequential frame cellular automata transformsUS6628827 *Dec 14, 1999Sep 30, 2003Intel CorporationMethod of upscaling a color imageUS6658399 *Sep 10, 1999Dec 2, 2003Intel CorporationFuzzy based thresholding technique for image segmentationUS6671413 *Jan 24, 2000Dec 30, 2003William A. PearlmanEmbedded and efficient low-complexity hierarchical image coder and corresponding methods thereforUS6965700Dec 29, 2003Nov 15, 2005William A. PearlmanEmbedded and efficient low-complexity hierarchical image coder and corresponding methods thereforUS7133854 *Dec 11, 2001Nov 7, 2006International Business Machines CorporationMethod and circuits for encoding an input pattern using a normalizer and a classifierUS7158178 *Dec 14, 1999Jan 2, 2007Intel CorporationMethod of converting a sub-sampled color imageUS7321674 *Jan 30, 2003Jan 22, 2008Agfa Healthcare, N.V.Method of normalising a digital signal representation of an imageUS7463782 *Nov 5, 2003Dec 9, 2008Canon Kabushiki KaishaData encoding with an amplitude model and path between the data and corresponding decodingUS8014597Mar 22, 2007Sep 6, 2011Woodman LabsMethod for efficient compression and decoding of single sensor color image dataUS8315468 *Oct 13, 2010Nov 20, 2012Teradici CorporationApparatus for block-selected encoding of a digital video signalUS8345969Aug 2, 2011Jan 1, 2013Woodman Labs, Inc.Method for efficient compression and decoding of single sensor color image dataUS8542741 *Jun 4, 2010Sep 24, 2013Sony CorporationImage processing device and image processing methodUS20100316127 *Jun 4, 2010Dec 16, 2010Masayuki YokoyamaImage processing device and image processing method* Cited by examinerClassifications U.S. Classification709/247, 375/E07.74, 375/E07.56, 375/240.2International ClassificationH04N7/26, G06T9/00Cooperative ClassificationH04N19/00109, H04N19/00884, H04N19/00818European ClassificationH04N7/26H30C1S, H04N7/26H30MLegal EventsDateCodeEventDescriptionAug 19, 2009FPAYFee paymentYear of fee payment: 12Sep 16, 2005FPAYFee paymentYear of fee payment: 8Aug 16, 2001FPAYFee paymentYear of fee payment: 4Sep 29, 1995ASAssignmentOwner name: INTEL CORPORATION, CALIFORNIAFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNOR:AGARWAL, ROHIT;REEL/FRAME:007693/0699Effective date: 19950928Sep 29, 1995AS02Assignment of assignor's interestOwner name: AGARWAL, ROHITOwner name: INTEL CORPORATION 2200 MISSION COLLEGE BOULEVARD -Effective date: 19950928RotateOriginal ImageGoogle Home - Sitemap - USPTO Bulk Downloads - Privacy Policy - Terms of Service - About Google Patents - Send FeedbackData provided by IFI CLAIMS Patent Services©2012 Google