Source: http://www.google.com/patents/US5539662?dq=5,960,411
Timestamp: 2015-02-27 11:42:48
Document Index: 188292945

Matched Legal Cases: ['art1', 'art2', 'art3', 'art4', 'art4', 'art3', 'art2', 'art1', 'art1', 'art2', 'art3', 'art4']

Patent US5539662 - Computer implemented process - Google PatentsSearch Images Maps Play YouTube News Gmail Drive More »Sign inAdvanced Patent SearchPatentsThe complexity of a plurality of signals in a first domain are characterized. A transform is selected in accordance with the complexity of the plurality of signals, wherein the selected transform is one of a plurality of transforms having differing complexities. The selected transform is applied to the...http://www.google.com/patents/US5539662?utm_source=gb-gplus-sharePatent US5539662 - Computer implemented processAdvanced Patent SearchPublication numberUS5539662 APublication typeGrantApplication numberUS 08/234,324Publication dateJul 23, 1996Filing dateApr 28, 1994Priority dateNov 24, 1993Fee statusPaidPublication number08234324, 234324, US 5539662 A, US 5539662A, US-A-5539662, US5539662 A, US5539662AInventorsBrian NickersonOriginal AssigneeIntel CorporationExport CitationBiBTeX, EndNote, RefManPatent Citations (8), Referenced by (6), Classifications (101), Legal Events (5) External Links: USPTO, USPTO Assignment, EspacenetComputer implemented process
US 5539662 AAbstract
The complexity of a plurality of signals in a first domain are characterized. A transform is selected in accordance with the complexity of the plurality of signals, wherein the selected transform is one of a plurality of transforms having differing complexities. The selected transform is applied to the plurality of signals to generate a plurality of transformed signals in a second domain.
1. A computer-implemented process for transforming signals, comprising the steps of:(a) generating a complexity measure for a plurality of signals in a first domain: (b) selecting a transform in accordance with the complexity measure of the plurality of signals, wherein the selected transform is one of a plurality of transforms corresponding to differing values of the complexity measure; and (c) transforming the plurality of signals into a plurality of transformed signals in a second domain by applying the selected transform to the plurality of signals. 2. The process of claim 1, wherein:the plurality of signals in the first domain comprise a plurality of discrete slant transform coefficients in a spatial frequency domain arranged in a matrix; the plurality of discrete slant transform coefficients correspond to a region of a video image; the matrix comprises a plurality of columns and a plurality of rows; step (a) comprises the steps of:(1) generating the complexity measure for each column of the matrix; and (2) generating the complexity measure for each row of the matrix; step (b) comprises the steps of:(1) selecting one or more column transform operations in accordance with the complexity measures of the columns wherein the selected one or more column transform operations are one or more of a plurality of column transform operations corresponding to differing values of the complexity measure; and (2) selecting one or more row transform operations in accordance with the complexity measures of the columns, wherein the selected one or more row transform operations are one or more of a plurality of row transform operations corresponding to differing values of the complexity measure; and step (c) comprises the steps of applying the selected one or more column transform operations and the selected one or more row transform operations to the matrix to generate a plurality of component signals in a spatial domain, wherein the plurality of component signals correspond to the video image. 3. The process of claim 2, wherein:step (a) comprises the steps of:(1) generating a total column complexity mask for the plurality of columns of the matrix, wherein the total column complexity mask comprises a column complexity mask for each column of the plurality of columns; and (2) generating a row complexity mask for the plurality of columns of the matrix; and step (b) comprises the steps of:(1) selecting the one or more column transform operations in accordance with the total column complexity mask; and (2) selecting the one or more row transform operations in accordance with the row complexity mask. 4. The process of claim 2, wherein:the matrix comprises eight columns and eight rows; each column having discrete slant transform coefficients C0, C1, C2, C3, C4, C5, C6, and C7, from top to bottom; and the plurality of column transform operations corresponding to differing values of the complexity measure comprise:a first column transform operation corresponding to a column, wherein at least one of coefficients C4, C5, C6, and C7 is non-zero; a second column transform operation corresponding to a column, wherein all coefficients C4, C5, C6, and C7 are zero and at least one of coefficients C2, C3 is non-zero; a third column transform operation corresponding to a column, wherein all coefficients C2, C3, C4, C5, C6, and C7 are zero and coefficient C1 is non-zero; and a fourth column transform operation corresponding to a column, wherein all coefficients C1, C2, C3, C4, C5, C6, and C7 are zero and coefficient C0 is non-zero; and a fifth column transform operation corresponding to a column, wherein all coefficients C0, C1, C2, C3, C4, C5, C6, and C7 are zero. 5. An apparatus for transforming signals, comprising:(a) means for generating a complexity measure for a plurality of signals in a first domain; (b) means for selecting a transform in accordance with the complexity measure of the plurality of signals, wherein the selected transformed is one of a plurality of transforms corresponding to differing values of the complexity measure; and (c) means for transforming the plurality of signals into a plurality of transformed signals in a second domain by applying the selected transform to the plurality of signals. 6. The apparatus of claim 5, wherein:the plurality of signal in the first domain comprise a plurality of discrete slant transform coefficients in a spatial frequency domain arranged in a matrix; the plurality of discrete slant transform coefficients correspond to a region of a video image; the matrix comprises a plurality of columns and a plurality of rows; means (a) comprises:(1) means for generating the complexity measure for each column of the matrix; and (2) means for generating the complexity measure for each row of the matrix: means (b) comprises:(1) means for selecting one or more column transform operations in accordance with the complexity measures of the columns wherein the selected one or more column transform operations are one or more of a plurality of column transform operations corresponding to differing values of the complexity measure; and (2) means for selecting one or more row transform operations in accordance with the complexity measures of the columns, wherein the selected one or more row transform operations are one or more of a plurality of row transform operations corresponding to differing values of the complexity measure; and means (c) comprises means for applying the selected one or more column transform operations and the selected one or more row transform operations to the matrix to generate a plurality of component signals in a spatial domain, wherein the plurality of component signals correspond to the video image. 7. The apparatus of claim 6, wherein:means (a) comprises:(1) means for generating a total column complexity mask for the plurality of columns of the matrix, wherein the total column complexity mask comprises a column complexity mask for each column of the plurality of columns; and (2) means for generating a row complexity mask for the plurality of columns of the matrix; and means (b) comprises:(1) means for selecting the one or more column transform operations in accordance with the total column complexity mask; and (2) means for selecting the one or more row transform operations in accordance with the row complexity mask. 8. The apparatus of claim 6, wherein:the matrix comprises eight columns and eight rows; each column having discrete slant transform coefficients C0, C1, C2, C3, C4, C5, C6, and C7, from top to bottom; and the plurality of column transform operations corresponding to differing values of the complexity measure comprise:a first column transform operation corresponding to a column, wherein at least one of coefficients C4, C5, C6, and C7 is non-zero; a second column transform operation corresponding to a column, wherein all coefficients C4, C5, C6, and C7 are zero and at least one of coefficients C2, C3 is non-zero; a third column transform operation corresponding to a column, wherein all coefficients C2, C3, C4, C5, C6, and C7 are zero and coefficient C1 is non-zero; and a fourth column transform operation corresponding to a column, wherein all coefficients C1, C2, C3, C4, C5, C6, and C7 are zero and coefficient C0 is non-zero; and a fifth column transform operation corresponding to a column, wherein all coefficients C0, C1, C2, C3, C4, C5, C6, and C7 are zero. 9. The apparatus of claim 5, wherein the apparatus comprises a host processor.
10. A system for transforming signals, comprising:(a) a monitor; and (b) a conferencing system for:(1) generating a complexity measure for a plurality of signals in a first domain; (2) selecting a transform in accordance with the complexity measure of the plurality of signals, wherein the selected transform is one of a plurality of transforms corresponding to differing values of the complexity measure; (3) transforming the plurality of signals into a plurality of transformed signals in a second domain by applying the selected transform to the plurality of signals; and (4) transmitting a plurality of decoded signals corresponding to the plurality of transformed signal to the monitor for display. 11. The system of claim 10, wherein:the plurality of signals in the first domain comprise a plurality of discrete slant transform coefficients in a spatial frequency domain arranged in a matrix; the plurality of discrete slant transform coefficients correspond to a region of a video image; and the matrix comprises a plurality of columns and a plurality of rows; and the conferencing system:generates the complexity measure for each column of the matrix; generates the complexity measure for each row of the matrix; selects one or more column transform operations in accordance with the complexity measures of the columns wherein the selected one or more column transform operations are one or more of a plurality of column transform operations corresponding to differing values of the complexity measure; selects one or more row transform operations in accordance with the complexity measures of the columns, wherein the selected one or more row transform operations are one or more of a plurality of row transform operations corresponding to differing values of the complexity measure; and applies the selected one or more column transform operations and the selected one or more row transform operations to the matrix to generate a plurality of component signals in a spatial domain, wherein the plurality of component signals correspond to the video image. 12. The system of claim 11, wherein the conferencing system:generates a total column complexity mask for the plurality of columns of the matrix, wherein the total column complexity mask comprises a column complexity mask for each column of the plurality of columns; generates a row complexity mask for the plurality of columns of the matrix; selects the one or more column transform operations in accordance with the total column complexity mask; and selects the one or more row transform operations in accordance with the row complexity mask. 13. The system of claim 11, wherein:the matrix comprises eight columns and eight rows; each column having discrete slant transform coefficients C0, C1, C2, C3, C4, C5, C6, and C7, from top to bottom; and the plurality of column transform operations corresponding to differing values of the complexity measure comprise:a first column transform operation corresponding to a column, wherein at least one of coefficients C4, C5, C6, and C7 is non-zero; a second column transform operation corresponding to a column, wherein all coefficients C4, C5, C6, and C7 are zero and at least one of coefficients C2, C3 is non-zero; a third column transform operation corresponding to a column, wherein all coefficients C2, C3, C4, C5, C6, and C7 are zero and coefficient C1 is non-zero; and a fourth column transform operation corresponding to a column, wherein all coefficients C1, C2, C3, C4, C5, C6, and C7 are zero and coefficient C0 is non-zero; and a fifth column transform operation corresponding to a column, wherein all coefficients C0, C1, C2, C3, C4, C5, C6, and C7 are zero. 14. The system of claim 10, wherein the conferencing system comprises a host processor for applying the selected transform to transform the signals.
The present invention is a computer-implemented process, apparatus, and system for transforming signals. The complexity of a plurality of signals in a first domain are characterized. A transform is selected in accordance with the complexity of the plurality of signals, wherein the selected transform is one of a plurality of transforms having differing complexities. The selected transform is applied to the plurality of signals to generate a plurality of transformed signals in a second domain.
Referring again to FIG. 2, host processor 202 may be any suitable general-purpose processor and is preferably an Intel� processor such as an Intel� i486� or Pentium� microprocessor. Host processor 202 preferably has at least 8 megabytes of host memory. Bus 208 may be any suitable digital communications bus and is preferably an Industry Standard Architecture (ISA) PC bus. Communications board 206 may be any suitable hardware/software for performing communications processing for conferencing system 100.
As described above in reference to step 402 of FIG. 4, the encoder performs motion estimation to identify, for each (16�16) target macroblock of the current image, a (16�16) macroblock from the reference image that matches (relatively closely) the target macroblock. In general, the encoder implements motion estimation as a three-step log search to identify a motion vector within a specified pixel range of the current macroblock. According to a preferred embodiment, the pixel range is specified as �7 pixels in the horizontal and vertical directions.
Those skilled in the art will understand that motion estimation under the above rules for error recovery will be affected by the edges of the Y component plane, the number of rows of macroblocks per intra-encoded image region, and the limitations on range of allowable motion vectors. In a preferred embodiment, each intra-encoded image region has only one row of macroblocks and the allowable motion vectors are limited to �7 pixels in the horizontal and vertical directions.
InterSAD=sum of .linevert split.c(i,j)-p(i,j).linevert split.
IntraSAD=sum of .linevert split.c(i,j)-C.linevert split.
The normalized activity index Ina (i) for the current macroblock i is generated (in step 808) using the following Equation (3): ##EQU2## where C is a specified constant (preferably 2), MA(i) is a macroblock activity measure for the current macroblock i, and MAave is the average macroblock activity measure of the entire component plane. In a preferred embodiment, the macroblock activity measure MA is the sum of absolute differences SAD. In alternative preferred embodiments, the macroblock activity measure MA may be some other activity measure, such as mean absolute difference, mean square error, or sum of square errors. The normalized activity index Ina (i) is a measure of the relative variation with the signals used to encode the current macroblock i.
The quantization level Q(i) alter step 812 is the quantization level used to encode the current macroblock i. A quantization level Q(i) of 15 corresponds to the coarsest quantization, while a quantization level Q(i) of 0 corresponds to the finest quantization.
Bit rate controller 1000 generates an estimate Bu e (i-1) of the number of bits used to encode the previous macroblock i-1(in step 1004 of FIG. 10) using Equation (6) as follows: ##EQU4## where: K2 is a specified positive constant (preferably, 3);
The estimated buffer content Cb e (i) is then used to generate the unscaled quantization level Qu (i) for the current macroblock i (in step 1008) using the following Equation (8): ##EQU5## Steps 1010, 1012, and 1014 of FIG. 10 for bit rate controller 1000 are identical to steps 808, 810, and 812 of FIG. 8 for bit rate controller 800, respectively.
Cb a is the adjusted buffer content, which is used as the previous buffer content for the similar component plane of the next frame:
BPF=Mintra q * IntraSAD+Bintra q where Mintra q is the slope and Bintra q is the Y intercept for the linear relationship for intra-encoding quantization level q. For N intra quantization levels, N linear relationships are generated.
BPF=Minter q * InterSAD+Binter q where Minter q is the slope and Binter q is the Y intercept for the linear relationship for inter-encoding quantization level q. For N inter quantization levels, N linear relationships are generated.
BPFe =k*(Mintra q * IntraSADave +Bintra q)+(1-k)*(Minter q *InterSADave +Binter q)
BPFt =BPFt *(BPFt /BPFa)
As described above in reference to step 416 of FIG. 4, the encoder quantizes the DST coefficients. In a preferred embodiment, quantization is performed as follows: ##EQU6## where vu is the unquantized DST coefficient, q is the quantizer, "/" represents division with truncation, and vq is quantized DST coefficient. The different treatment of DST coefficients with negative values ensures truncation toward zero. Those skilled in the art will understand that a purpose of this is to improve compression by always truncating toward the smaller of the two nearest integer values.
______________________________________Macroblock Codebook              {1, 2, 3, 4*}Block Codebook     {1, 2, 3, 4, 5, 6, 5, 6*}______________________________________
TABLE III______________________________________Code Words and Corresponding Values for theBlock Codebook.Code Words            Values______________________________________1x                    0-101xx                  2-5001xxx                 6-130001xxxx              14-2900001xxxxx            30-61000001xxxxxx           62-1270000001xxxxx          128-15900000000 00xxxx       hole00000000 010000 to 00000001 101111                 160-255______________________________________
TABLE IV______________________________________Image Sizes Indicated by the ImageSize Signal.ImageSizeValue         ImageSize______________________________________0             (160 � 120)1             (240 � 180)2             (320 � 240)3             defined______________________________________
The 2-bit TempFiltStrength signal specifies the strength of the temporal post-filter. Table V contains the temporal post-filter strengths for the different values of TempFiltStrength. A TempFiltStrength signal value of 0 indicates that the temporal post-filter is turned off for this image. The temporal post-filter is described in further detail earlier in this specification in the section entitled "Temporal
The 3-bit QuantMatrices signal encodes the quantization matrices the decoder should use for this frame. There are preferably 32 different quantization matrices--16 for use in intra blocks and 16 for use in inter blocks. These 32 quantization matrices may be derived from two base matrices (one for intra and one for inter), five quantization parameters, and a flag (PowersOf2). The generation of the 32 quantization matrices from the two base matrices, five quantization parameters, and PowersOf2 flag is described in further detail later in this specification in the section entitled "Generation of Quantization Matrices."Table VI identifies which base matrices, quantization parameters and PowersOf2 flags to use for the different values of QuantMatrices. "Default" indicates that the specified default base matrices or specified default values for the five quantization parameters are to be used to generate the 32 quantization matrices. "In QuantData" indicates that the matrices and/or parameters are specified in the QuantData signal of the picture header. "From Past" indicates that the matrices and/or parameters (which must have been set on a previous frame) are inherited from the past). The QuantMatrices values 5-7 are preferably reserved.
TABLE VI______________________________________Base Matrices, Quantization Parameters, and PowersOf2Flag Values Indicated by the QuantMatrices Signal.QuantMatrices     Base       QuantizationValue     Matrices   Parameters   PowersOf2______________________________________0         Default    Default      01         Default    Default      12         Default    In QuantData In QuantData3         In QuantData                In QuantData In QuantData4         From Past  From Past    From Past5-7                  . . . Reserved . . .______________________________________
A value of 1 for time 1-bit IntraFlag signal indicates that this frame is entirely intra encoded (i.e., that each block of each macroblock of each slice of each component plane of the current frame is intra encoded). If the IntraFlag signal value is 0, then this frame may include both intra and inter blocks.
______________________________________    tosigned (val)    {      r = (val + 1) &gt;&gt; 1;      if (val is even)        return (r);      else        return (-r);    }______________________________________
TABLE VIII______________________________________Semantic Table for Information Stored in CBPSignal.Block Block     Block   Block   4-bit Huffman4     3         2       1       Value Value______________________________________1     1         1       1       15    00     0         1       1        3    11     1         1       0       14    21     1         0       1       13    31     1         0       0       12    40     1         1       1        7    50     1         0       0        4    61     0         0       0        8    71     0         1       1       11    80     0         0       1        1    91     0         1       0       10    100     0         1       0        2    110     1         0       1        5    120     1         1       0        6    131     0         0       1        9    14______________________________________
______________________________________empty = 0    \\ initialize number of empty        macroblockswhile (1)code = gethuff();           \\ retrieve and decode next signalif (code &lt; 42){empty += code; \\ increment empty by codebreak;}else if (code == 42)empty += 41;    \\ increment empty by 41else if (code == 43)all macroblocks to end of slice are empty}______________________________________
Host processor 202 reconstructs the (8�8) blocks of quantized DST coefficients using the runs of zero DST coefficients and the non-zero DST coefficient values to undo the zig-zag scanning sequence of FIG. 6 (step 2104). An (8�8) block of quantized DST coefficients (coeff[8][8]) nay be created by the following procedure:
______________________________________for (i = 0; i &lt; 8; i++)for (j = 0; j &lt; 8; j++)coeff[i][j] = 0;start at position "-1` on the zig-zag path (one step "before" 0)for (each run/val pair)step forward by `run` positions on the zig-zag pathdeposit `val` at the new position}______________________________________
______________________________________for (i = 0; i &lt; 8; i++)for (j = 0; j &lt; 8; j++)q = Qmatrix[Intra][thisQ][i][j];c = coeff[i][j];if (c &gt; 0)coeff[i][j] = (q * c) + (q &gt;&gt; 1) - (q &amp; 1);else if (c &lt; 0)coeff[i][j] = (q * c) - (q &gt;&gt; 1) + (q &amp; 1);else if (c == 0)coeff[i][j] = 0;}______________________________________
______________________________________    coeff[0][0] += prevDC    prevDC = coeff[0][0]______________________________________
______________________________________for (i = 0; i &lt; 8; i++)for (j = 0; j &lt; 8; j++)image[i][j] = clamp(MCprev[i][j]) + array[i][j], 8, 120);______________________________________
where array[][] contains the results of the IDST calculation, MCprev[][] is the corresponding motion-compensated (8�8) block of component signals from the previous image, and the function clamp(n,min,max) limits a value n to the range (min,max).
______________________________________for (i = 0; i &lt; 8; i++)for (j = 0; j &lt; 8; j++)image [i][j] = clamp (array [i][i], 8, 120);______________________________________
______________________________________k = 0;while (1)v = gethuff();if (v == EOB)break;else if (v == ESC) // get explicit run,val from bitstream{run[k] = gethuff() + 1;lo = gethuff();hi = gethuff();val[k] = tosigned((lo .linevert split. (hi &lt;&lt; 6)) + 1);}else // lookup run,val in tables{run[k] = runtbl[v];val[k] = valtbl[v];}k++}______________________________________
______________________________________runtbl [] = {    0      1      1    2    2    1    1    3    1      3      1    0    4    4    1    2    1      2      5    5    1    6    1    6    1      7      7    1    1    9    8    8    2      9      1    2    3    10   1    10    3      1      11   1    1    2    1    13    1      4      4    1    1    11   12   2    13     1      2    15   1    1    12   14    3      14     1    2    15   5    6    5    1      1      1    1    1    3    1    1    6      16     2    1    1    7    1    21    1      2      2    4    7    18   1    16    1      1      17   2    8    4    1    8    18     19     7    22   3    17   9    2    4      20     10   19   10   1    1    2    21     20     29   28   23   25   3    3    3      24     26   26   2    12   9    2    1      2      2    27   13   22   5    5    28     30     23   32   27   2    3    6    9      4      32   12   11   31   11   14    3      3      3    3    2    6    8    7    5      29     14   9    25   24   2    3    2      6      6    8    7    4    4    4    13     31     10   18   6    7    5    4    5      5      4    10   21   30   19   18    19     22     20   21   22   20   16   15    15     17     17   16   3    3    4    4    3      3      4    6    6    7    7    5    4      4      5    6    5    5valtbl[] = {    0      -1     1    1    -1   -2   2    -1    -3     1      3    0    1    -1   -4   -2    4      2      -1   1    -5   1    5    -1    -6     -1     1    6    7    -1   -1   1    -3     1      -7   3    -2   -1   -8   1    2      8      -1   9    -9   4    -11  1    -10    -2     2    10   11   1    -1   -4    -1     -13    -5   -1   -12  13   1    1    3      -1     12   5    1    2    2    -2    -15    14     16   -14  15   -3   -17  18    -2     -1     6    17   -16  2    19   -1    -19    7      -6   -3   -2   1    -22  1    -20    -18    -1   -7   2    4    20   -2    -1     -1     -3   -1   -4   1    -2   -8    3      1      -2   1    2    -21  22   9    1      -1     -1   -1   -1   -1   5    -5    4      -1     -1   1    8    -2   2    11    21     10     -11  1    -2   1    3    -3    1      -1     1    1    -1   12   6    3    -3     -4     -1   2    -2   -1   2    2    -7     -9     -8   7    -12  5    -3   3    -4     1      -2   3    1    1    -10  8    -9     -4     -3   3    -4   6    5    -5    2      1      -3   -2   4    -5   7    -6    5      -5     7    3    2    1    2    2    -2     -2     2    -2   2    -2   -2   2    -2     2      -2   2    -6   -10  -8   -9    10     9      -7   6    -5   5    4    -7    9      8      6    -6   -6   4}______________________________________
______________________________________slant8 � 1(s, d, fwd)        // s = pointer to input column or row        // d = pointer to output column or rowint s[], d[], fwd;        // fwd = 1 for forward DST, 0 for        inverse DSTint r1, r2, r3, r4, r5, r6, r7, r8;int t, t1, *p;if (fwd)   // apply forward DST{p = s;r1 = *p++;   // store value pointed to by p to r1 and        // then increment pr2 = *p++;r3 = *p++;r4 = *p++;r5 = *p++;r6 = *p++;r7 = *p++;r8 = *p++;SlantPart1;SlantPart2;SlantPart3;SlantPart4;p = d;*p++ = r1;*p++ = r4;*p++ = r8;*p++ = r5;*p++ = r2;*p++ = r6;*p++ = r3;*p++ = r7;}else       // apply inverse DSTp = s;r1 = *p++;r4 = *p++;r8 = *p++;r5 = *p++;r2 = *p++;r6 = *p++;r3 = *p++;r7 = *p++;SlantPart4;SlantPart3;SlantPart2;SlantPart1;p = d;*p++ = r1;*p++ = r2;*P++ = r3;*p++ = r4;*p++ = r5;*p++ = r6;*p++ = r7;*p++ = r8;}}______________________________________
______________________________________#define SlantPart1\bfly(r1, r4);\bfly(r2, r3);\bfly(r5, r8);\bfly(r6, r7);#define SlantPart2bfly(r1, r2) ;\reflect(r4, r3);\bfly(r5, r6) ;\reflect(r8, r7);#define SlantPart3\bfly(r1, r5);\bfly(r2, r6);\bfly(r7, r3);\bfly(r4, r8);#define SlantPart4\t = r5 - (r5 &gt;&gt; 3) + (r4 &gt;&gt; 1); \\ t = 7/8 r5 + 1/2r4r5 = r4 - (r4 &gt;&gt; 3) - (r5 &gt;&gt; 1);\\ r5 = 7/8 r4 - 1/2r5r4 = t;______________________________________
______________________________________bfly(x, y):t = x + y;y = x - y;x = t;#define reflect(s1, s2)        \\for forward transform\\t = 11/8 s1 + 9/16 s2t = s1 + (s1 &gt;&gt; 2) + (s1 &gt;&gt; 3) + (s2 &gt;&gt; 1) +(s2 &gt;&gt; 4);\\s2 = -11/8 s2 + 9/16 s1s2 = -s2 - (s2 &gt;&gt; 2) - (s2 &gt;&gt; 3) + (s1 &gt;&gt; 1) +(s1 &gt;&gt; 4);s1 = t;#define reflect(s1, s2)        \\for inverse transform\\t = 5/4 s1 + 1/2 s2t = s1 + (s1 &gt;&gt; 2) + (s2 &gt;&gt; 1)\\s2 = -5/4 s2 + 1/2 s1s2 = -s2 - (s2 &gt;&gt; 2) + (s1 &gt;&gt; 1);s1 = t;______________________________________
______________________________________for (i = 0; i &lt; 8; i++)for (j = 0; j &lt; 8; j++)array[i][j] = (array[i][j] + 4) &gt;&gt; 3______________________________________
______________________________________for (i = 0; i &lt; 8; i++)for (j = 0; j &lt; 8; j++)array[i][j] = array[i][j] &gt;&gt; 3______________________________________
In order to increase the efficiency of IDST processing, a preferred embodiment of the present invention takes advantage of the fact that, for typical video images, many DST coefficients in a non-empty (8�8) block will be zero. The likelihood of a DST coefficient being zero increases for components further away from the DC component (the (0,0) component). Thus, DST coefficients in the bottom half of each column, and those in the right half of each row, are more likely to be zero than those in the other halves.
Bit 3 corresponds to rows 4.5, 6, and 7.
TABLE IX______________________________________Initial Assignment of Column DST Operations and FinalAssignment of Row DST Operations.4-bitComplexity  Mask            DSTMask        Values          Operation______________________________________(1xxx)       8-15           slant8 � 1(01xx)      4-7             slant4 � 1(001x)      2-3             slant2 � 1(0001)      1               slant1 � 1(0000)      0               null______________________________________
Referring again to FIG. 18, after the temporal post-filter is applied, block edge filtering is applied if selected (step 1816 of FIG. 18). Block edge filtering improves visual quality, especially during periods of high motion, by reducing blocking artifacts along the edges of the (8�8) blocks. If selected, block edge filtering is preferably applied only to the Y component signals.
q1 ≧T and if Block 1 is not {empty and inter and MV=0} or
q2 ≧T and if Block 2 is not {empty and inter and MV=0},
As described earlier in this specification in the section entitled "Variable-Length Encoding," Table II presents the Huffman codebook for encoding macroblock signals and Table III presents the Huffman codebook for encoding block signals. According to Tables II and III, Huffman-encoded encoded macroblock signals are either 2, 4, 6, or 8 bits long, while Huffman-encoded block signals are either 2, 4, 6, 8, 10, 12, or 14 bits long. Each byte in the Huffman-encoded bitstream may therefore comprise a whole or part of one or more Huffman-encoded signals.
Referring again to FIG. 33, decoder 3300 is initialized at the start of decoding a stream of Huffman-encoded macroblock signals (step 3302 of FIG. 33). Decoder 3300 is initialized to the state signifying that the macroblock signal prefix begins at bit 0 (i.e., MPrefixAt0 of Table X below). Decoder 3300 need not be re-initialized at the start of decoding a stream of Huffman-encoded block signals, since the block signals immediately follow the macroblock signals for a given slice of a video frame. Decoder 3300 handles the transition from decoding macroblock signals to decoding block signals. Since a stream of Huffman-encoded block signals may begin at either bits 0, 2, 4, or 6 of the current byte, there are tour different states for the beginning of decoding block signals (i.e., BlkDataAt0, BlkDataAt2, BlkDataAt4, and BlkDataAt6 of Table XI below). The initialization of step 3302 also involves initializing the input and output pointers and the accumulator.
B=*pIn & MASK[STATE]
______________________________________Contrib&#9633;&#9633;    Specifies the contribution to the 8-bit accumulator.NextState&#9633;&#9633;    Specifies a 6-bit value corresponding to the next    state.IncIn&#9633;&#9633;    Specifies a 1-bit flag indicating whether the input    pointer (pIn) is to be incremented.IncOut&#9633;&#9633;    Specifies a 1-bit flag indicating whether the    accumulator is to be initialized and whether the    output pointer (pOut) is to be incremented.______________________________________
TABLE XII__________________________________________________________________________Abstract Rules for Variable-Length Decoding.Byte   Current         Next   Base Increment                              Signal NotValue  State  State  Contrib                     Bitstream Pointer                              Complete__________________________________________________________________________XXXXXXF1  MPrefixAt0         MPrefixAt2                0    0        0XXXXFE10  MPrefixAt0         MPrefixAt4                2    0        0X1FED100  MPrefixAt0         MPrefixAt6                6    0        010FED100  MPrefixAt0         MNeed2Code                6    1        000FED100  MPrefixAt0         MGot2Prefix                6    1        0fedcb000  MPrefixAt0         MPrefixAt0                14-1 1        000000000  MPrefixAt0         IllegalCode                255  1        011111000  MPrefixAt0         BlkDataAt0                255  1        0XXXXF1ZZ  MPrefixAt2         MPrefixAt4                0    0        0X1FE10ZZ  MPrefixAt2         MPrefixAt6                2    0        010FE10ZZ  MPrefixAt2         MNeed2Code                2    1        000FE10ZZ  MPrefixAt2         MGot2Prefix                2    1        0FED100ZZ  MPrefixAt2         MPrefixAt0                6    1        0dcb000ZZ  MPrefixAt2         MNeed2Code                14-3 1        1000000ZZ  MPrefixAt2         MNeed2Non0                0    1        1111000ZZ  MPrefixAt2         MNeed2Non1                28   1        1X1F1ZZZZ  MPrefixAt4         MPrefixAt6                0    0        010F1ZZZZ  MPrefixAt4         MNeed2Code                0    1        000F1ZZZZ  MPrefixAt4         MGot2Prefix                0    1        0FE10ZZZZ  MPrefixAt4         MPrefixAt0                2    1        0D100ZZZZ  MPrefixAt4         MNeed2Code                 6-2 1        10000ZZZZ  MPrefixAt4         MNeed4Non0                0    1        11000ZZZZ  MPrefixAt4         MNeed4Non1                16   1        1F1ZZZZZZ  MPrefixAt6         MPrefixAt0                0    1        010ZZZZZZ  MPrefixAt6         MNeed2Code                0    1        100ZZZZZZ  MPrefixAt6         MGot2Prefix                0    1        1ZZXXFED1  MGot2Prefix         MPrefixAt4                6    0        0ZZfedcb0  MGot2Prefix         MPrefixAt6                14-1 0        0ZZ000000  MGot2Prefix         Illegalcode                255  1        0ZZ111110  MGot2Prefix         BlkDataAt6                255  0        0ZZZZZZFE  MNeed2Code         MPrefixAt2                2    0        0ZZZZFEDC  MNeed4Code         MPrefixAt4                2    0        0__________________________________________________________________________
TABLE XIII__________________________________________________________________________Abstract Rules for Variable-Length Decoding.Byte   Current         Next   Base Increment                              Signal NotValue  State  State  Contrib                     Bitstream Pointer                              Complete__________________________________________________________________________ZZZZZZfe  MNeed2Non0         MPrefixAt2                14-1 0        0ZZZZZZ00  MNeed2Non0         IllegalCode                255  0        0ZZZZZZfe  MNeed2Non1         MPrefixAt2                14-1 0        0ZZZZZZ11  MNeed2Non1         BlkDataAt2                255-28                     0        0ZZZZfedc  MNeed4Non0         MPrefixAt4                14-1 0        0ZZZZ0000  MNeed4Non0         IllegalCode                255  0        0ZZZZfedc  MNeed4Non1         MPrefixAt4                14-1 0        0ZZZZ1111  MNeed4Non1         BlkDataAt4                255-16                     0        0XYYYYYF1  BPrefixAt0         BPrefixAt2                0    0        0000000F1  BPrefixAt0         BGot6Prefix                0    1        0100000F1  BPrefixAt0         BNeed6Code                0    1        0XYYYFE10  BPrefixAt0         BPrefixAt4                2    0        00000FE10  BPrefixAt0         BGot4Prefix                2    1        01000FE10  BPrefixAt0         BNeed4Code                2    1        0X1FED100  BPrefixAt0         BPrefixAt6                6    0        000FED100  BPrefixAt0         BGot2Prefix                6    1        010FED100  BPrefixAt0         BNeed2Code                6    1        0FEDC1000  BPrefixAt0         BPrefixAt0                14   1        0DCB10000  BPrefixAt0         BNeed2Code                30-2 1        1BA100000  BPrefixAt0         BNeed4Code                 62-14                     1        1B1000000  BPrefixAt0         BNeed4Code                126-14                     1        110000000  BPrefixAt0         BNeed6Code                206-62                     1        100000000  BPrefixAt0         BGot8Prefix                0    1        1XYYYF1ZZ  BPrefixAt2         BPrefixAt4                0    0        00000F1ZZ  BPrefixAt2         BGot4Prefix                0    1        01000FlZZ  BPrefixAt2         BNeed4Code                0    1        0X1FE10ZZ  BPrefixAt2         BPrefixAt6                2    0        000FE10ZZ  BPrefixAt2         BGot2Prefix                2    1        010FE10ZZ  BPrefixAt2         BNeed2Code                2    1        0FED100ZZ  BPiefixAt2         BPrefixAt0                6    1        0DC1000ZZ  BPrefixAt2         BNeed2Code                14-2 1        1B10000ZZ  BPrefixAt2         BNeed4Code                 30-14                     1        1100000ZZ  BPrefixAt2         BNeed6Code                0    1        1000000ZZ  BPrefixAt2         BGot6Prefix                0    1        1__________________________________________________________________________
TABLE XIV__________________________________________________________________________Abstract Rules for Variable-Length Decoding.Byte   Current         Next   Base Increment                              Signal NotValue  State  State  Contrib                     Bitstream Pointer                              Complete__________________________________________________________________________X1F1ZZZZ  BPrefixAt4         BPrefixAt6                0    0        000F1ZZZZ  BPrefixAt4         BGot2Prefix                0    1        010F1ZZZZ  BPrefixAt4         BNeed2Code                0    1        0FE10ZZZZ  BPrefixAt4         BPrefixAt0                2    1        0D100ZZZZ  BPrefixAt4         BNeed2Code                 6-2 1        11000ZZZZ  BPrefixAt4         BNeed4Code                0    1        10000ZZZZ  BPrefixAt4         BGot4Prefix                0    1        1F1ZZZZZZ  BPrefixAt6         BPrefixAt0                0    1        010ZZZZZZ  BPrefixAt6         BNeed2Code                0    1        100ZZZZZZ  BPrefixAt6         BGot2Prefix                0    1        1XYYYFED1  BGot2Prefix         BPrefixAt4                6    0        00000FED1  BGot2Prefix         BGot4Prefix                6    1        01000FED1  BGot2Prefix         BNeed4Code                6    1        0X1FEDC10  BGot2Prefix         BPrefixAt6                14   0        000FEDC10  BGot2Prefix         BGot2Prefix                14   1        010FEDC10  BGot2Prefix         BNeed2Code                14   1        0FEDCB100  BGot2Prefix         BPrefixAt0                30   1        0DCBA1000  BGot2Prefix         BNeed2Code                62.2 1        1DCB10000  BGot2Prefix         BNeed2Code                126-2                     1        1BA100000  BGot2Prefix         BNeed4Code                206-14                     1        1ba000000  BGot2Prefix         BNeed4Code                158-30                     1        100000000  BGot2Prefix         BEnd   255  0        1ZZZZDCB1  BGot4Prefix         BNeed2At4                30   0        1ZZZZBA10  BGot4Prefix         BNeed4At4                62   0        1ZZZZB100  BGot4Prefix         BNeed4At4                126  0        1ZZZZ1000  BGot4Prefix         BNeed6At4                206  0        1ZZZZ0000  BGot4Prefix         BGot8PAt4                0    0        1DCbaZZZZ  BGot8PAt4         BNeed2Code                158-18                     1        10000ZZZZ  BGot8PAt4         BEnd   255  0        1ZZZZDCB1  BGot6Prefix         BNeed2At4                126  0        1ZZZZBA10  BGot6Prefix         BNeed4At4                206  0        1ZZZZba00  BGot6Prefix         BNeed4At4                158-16                     0        1ZZZZ0000  BGot6Prefix         BEnd   255  0        1__________________________________________________________________________
TABLE XV__________________________________________________________________________Abstract Rules for Variable-Length Decoding.Byte   Current         Next   Base Increment                              Signal NotValue  State  State  Contrib                     Bitstream Pointer                              Complete__________________________________________________________________________ZZZZZZYY  BGot8Prefix         BNeed6Code                158-78                     0        0ZZZZZZ00  BGot8Prefix         BEnd   255  0        1ZZZZZZFE  BNeed2Code         BPrefixAt2                2    0        0ZZZZFEDC  BNeed4Code         BPrefixAt4                14   0        0ZZFEDCBA  BNeed6Code         BPrefixAt6                62   0        0X1FEZZZZ  BNeed2At4         BPrefixAt6                0    0        000FEZZZZ  BNeed2At4         BGot2Prefix                0    1        010FEZZZZ  BNeed2At4         BNeed2Code                0    1        0FEDCZZZZ  BNeed4At4         BPrefixAt0                0    1        0DCBAZZZZ  BNeed6At4         BNeed2Code                0xFE 1        1ZZZZZZZZ  BlkDataAt0         BPrefixAt0                0    0        1ZZZZZZZZ  BlkDataAt2         BPrefixAt2                0    0        1ZZZZZZZZ  BlkDataAt4         BPrefixAt4                0    0        1ZZZZZZZZ  BlkDataAt6         BPrefixAt6                0    0        1__________________________________________________________________________
______________________________________for (k = 0; k &lt; 2; k++) // for each of inter, intra base matrices// Apply tilt to base matrixfor (j = 0; j &lt; 8; j++)for (i = 0; i &lt; 8; i++)Base [k][j ][i] = (Base [k][j][i] *       (32 + (i + j) * (Tilt[k] - 32)/32))/32;// Generate the 16 quantization matrices of this typefor (m = 0; m &lt; 16; m++){for (j = 0; j &lt; 8; j++){for (i = 0; i &lt; 8; i++){   if (i == 0 &amp;&amp; j == 0 &amp;&amp; k == 1)     s = DCstep;   else     s = QuantStep;   q = (Base [k][j][i] *     (QuantStart + ((s*m) &gt;&gt; 2))) &gt;&gt; 6;   if (q &lt; 2) q = 2;   if (q &gt; 127) q = 127;   if (PowersOf2)     q = Round2[q];   else     q = q &gt;&gt; 1;   Qmatrix[k][m][j][i] = q;}}}}______________________________________
______________________________________Round2[] =    0,     0,     1,   2,   2,   2,   4,   4,    4,     4,     4,   4,   8,   8,   8,   8,    8,     8,     8,   8,   8,   8,   8,   16,    16,    16,    16,  16,  16,  16,  16,  16,    16,    16,    16,  16,  16,  16,  16,  16,    16,    16,    16,  16,  16,  16,  32,  32,    32,    32,    32,  32,  32,  32,  32,  32,    32,    32,    32,  32,  32,  32,  32,  32,    32,    32,    32,  32,  32,  32,  32,  32,    32,    32,    32,  32,  32,  32,  32,  32,    32,    32,    32,  32,  32,  32,  32,  32,    32,    32,    32,  64,  64,  64,  64,  64,    64,    64,    64,  64,  64,  64,  64,  64,    64,    64,    64,  64,  64,  64,  64,  64,    64,    64,    64,  64,  64,  64,  64,  64,    64,    64,    64,  64,  64,  64,  64,  64};______________________________________
______________________________________     QuantStart = 30     QuantStep = 36     DCstep = 8     Tilt [0] = Tilt [1] = 32     PowersOf2 = 1______________________________________
______________________________________Inter:   8      8      8    8    9    9    10   10   8      8      8    9    9    10   10   11   8      8      8    9    10   11   11   12   8      9      9    10   10   11   12   13   9      9      10   10   11   12   12   14   9      10     11   11   11   12   13   15   10     10     11   12   13   13   14   15   10     11     12   13   14   15   15   16Intra:   6      8      9    11   13   13   14   17   8      8      11   12   13   14   17   18   9      11     13   13   14   17   17   19   11     11     13   13   14   17   18   20   11     13     13   14   16   17   20   24   13     13     14   16   17   20   24   29   13     13     14   17   19   23   28   34   13     14     17   19   23   28   34   41______________________________________
Patent CitationsCited PatentFiling datePublication dateApplicantTitleUS4797740 *Jun 9, 1987Jan 10, 1989Nec CorporationReal-time video signal processing device capable of typically executing interframe codingUS5309237 *Mar 31, 1992May 3, 1994Siemens Corporate Research, Inc.Apparatus and method of compensating image-sequences for motionUS5329318 *May 13, 1993Jul 12, 1994Intel CorporationMethod for optimizing image motion estimationUS5351085 *Jun 16, 1993Sep 27, 1994Intel CorporationMethod and system for generating compressed image signalsUS5367629 *Dec 18, 1992Nov 22, 1994Sharevision Technology, Inc.Digital video compression system utilizing vector adaptive transformUS5381180 *Aug 16, 1993Jan 10, 1995Intel CorporationMethod and apparatus for generating CLUT-format video imagesUS5386232 *Jun 16, 1993Jan 31, 1995Intel CorporationMethod and apparatus for encoding images using a specified data formatUS5432554 *Jun 16, 1993Jul 11, 1995Intel CorporationMethod and apparatus for decoding images using a specified data format* Cited by examinerReferenced byCiting PatentFiling datePublication dateApplicantTitleUS5754742 *May 12, 1995May 19, 1998Intel CorporationSetting quantization level to match DCT coefficientsUS5774677 *Jun 28, 1996Jun 30, 1998Intel CorporationMethod for processing image dataUS6539124 *Aug 17, 1999Mar 25, 2003Sarnoff CorporationQuantizer selection based on region complexities derived using a rate distortion modelUS8854389Sep 22, 2004Oct 7, 2014Intel CorporationApparatus and method for hardware-based video/image post-processingUS20130003872 *Jul 10, 2012Jan 3, 2013Alvarez Jose RobertoMethod, system and device for improving video quality through in-loop temporal pre-filteringWO2007137403A1 *May 23, 2007Dec 6, 2007Ion-Dan CalinescuSystem and method of generating applications for mobile devices* Cited by examinerClassifications U.S. Classification358/1.15, 375/E07.271, 375/E07.162, 375/E07.148, 375/E07.176, 375/E07.281, 375/E07.144, 375/E07.14, 375/E07.226, 348/E07.084, 375/E07.217, 375/E07.231, 375/E07.241, 348/E07.083, 375/E07.19, 375/E07.157, 375/E07.254, 375/E07.145, 375/E07.18, 375/E07.224, 375/E07.267, 375/E07.193, 375/E07.214, 375/E07.211, 375/E07.138, 375/E07.194International ClassificationH04N7/52, H04Q11/04, H04N7/30, H04N7/68, H04N7/26, H04N7/50, H04N7/15, H04N7/46, G06T9/00Cooperative ClassificationH04N19/80, H04N19/198, H04N19/107, H04N19/91, H04N19/196, H04N19/14, H04N19/174, H04N19/587, H04N19/82, H04N19/124, H04N19/86, H04N19/61, H04N19/197, H04N19/132, H04N19/60, H04N19/126, H04N19/13, H04N19/146, H04N19/527, H04N19/149, H04N19/176, H04N19/895, H04N7/15, H04N21/4341, H04N21/2368, H04Q2213/1319, H04Q2213/13299, H04Q2213/13103, H04Q2213/13106, H04Q2213/13337, H04Q2213/13152, H04Q2213/13209, H04Q2213/13034, H04Q2213/1324, H04Q11/0435, H04N7/152, H04N7/52European ClassificationH04N21/434A, H04N21/2368, H04N19/00A4P1, H04N19/00A4P2, H04N7/26F2, H04N7/30, H04N7/26A4C2, H04N7/15M, H04N7/46T2, H04N7/50, H04N7/68, H04N7/26A4Q2, H04N7/26P4, H04N7/30E2, H04N7/50E5F, H04N7/50R, H04N7/26F, H04N7/26A4P, H04N7/26A4V, H04Q11/04S1, H04N7/52, H04N7/50E4, H04N7/15, H04N7/26A8B, H04N7/26A6C2, H04N7/26A8L, H04N7/26A4Z, H04N7/26A6E4E, H04N7/26M2GLegal EventsDateCodeEventDescriptionJan 17, 2008FPAYFee paymentYear of fee payment: 12Jan 23, 2004FPAYFee paymentYear of fee payment: 8Jan 21, 2000FPAYFee paymentYear of fee payment: 4Feb 18, 1997CCCertificate of correctionJun 15, 1994ASAssignmentOwner name: INTEL CORPORATION, OREGONFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNOR:NICKERSON, BRIAN;REEL/FRAME:007047/0567Effective date: 19940531RotateOriginal ImageGoogle Home - Sitemap - USPTO Bulk Downloads - Privacy Policy - Terms of Service - About Google Patents - Send FeedbackData provided by IFI CLAIMS Patent Services