Source: http://www.google.com/patents/US7548583?ie=ISO-8859-1
Timestamp: 2015-05-28 08:25:00
Document Index: 161495315

Matched Legal Cases: ['art 2', 'art 2', 'art 2', 'art 2', 'art 2', 'art 2']

Patent US7548583 - Generation and use of masks in MPEG video encoding to indicate non-zero ... - Google PatentsSearch Images Maps Play YouTube News Gmail Drive More »Sign inAdvanced Patent SearchPatentsDuring Motion Picture Experts Group (MPEG) video encoding a two-dimensional discrete cosine transform (DCT) is performed on data representing an original image. The resulting coefficients are then quantized, which typically results in many zero coefficients. Because of the nature of most video data,...http://www.google.com/patents/US7548583?utm_source=gb-gplus-sharePatent US7548583 - Generation and use of masks in MPEG video encoding to indicate non-zero entries in transformed macroblocksAdvanced Patent SearchPublication numberUS7548583 B2Publication typeGrantApplication numberUS 11/200,949Publication dateJun 16, 2009Filing dateAug 9, 2005Priority dateJan 7, 2002Fee statusPaidAlso published asCA2415977A1, US6985529, US20060034368Publication number11200949, 200949, US 7548583 B2, US 7548583B2, US-B2-7548583, US7548583 B2, US7548583B2InventorsJason KlivingtonOriginal AssigneeApple Inc.Export CitationBiBTeX, EndNote, RefManPatent Citations (13), Non-Patent Citations (4), Classifications (13), Legal Events (2) External Links: USPTO, USPTO Assignment, EspacenetGeneration and use of masks in MPEG video encoding to indicate non-zero entries in transformed macroblocks
US 7548583 B2Abstract
transforming a set of n coefficients representing video data from a zig-zag order to a second order, n is an integer greater than 1;
generating an n-bit mask indicating whether the individual coefficients in the second order are non-zero;
storing the mask as one or more vectors, wherein the stored vectors are factored so that the sum of the mask can be determined using only shift and bitwise OR operations;
retrieving the non-zero coefficients;
encoding, by an encoder, the set of coefficients based on the number of leading zero coefficients determined from the mask and corresponding non-zero entries; and
transmitting the encoded set of coefficients in an encoded video bitstream.
3. The method of claim 2 wherein transforming the set of coefficients representing video data from the zig-zag order to the second order comprises transforming a matrix having an original order of
to a matrix having an order of
4. The method of claim 1 wherein the mask comprises a 64-bit value where each bit in the mask corresponds to a coefficient in a discrete cosine transformed macroblock of video data.
7. The method of claim 1 wherein generating the mask comprises:
determining whether a coefficient exceeds a predetermined threshold value; and
generating an entry in a vector to be used in computing the mask, the entry corresponding to the location of the coefficient within the macroblock that exceeds the predetermined threshold value.
9. A machine-accessible medium stored computer executable instructions that, when executed, cause one or more processors to:
transform a set of n coefficients representing video data from a zig-zag order to a second order;
generate an n-bit mask indicating whether the individual coefficients in the second order are non-zero, n is an integer greater than 1;
store the mask as one or more vectors, wherein the stored vectors are factored so that the sum of the mask can be determined using only shift and bitwise OR operations;
retrieve the non-zero coefficients;
encode the set of coefficients based on the number of leading zero coefficients determined from the mask and corresponding non-zero entries; and
transmit the encoded set of coefficients in an encoded video bitstream.
10. The machine accessible medium of claim 9 wherein the computer executable instructions that cause the one or more processors to transform the set of coefficients from a first order to a second order comprises instructions that, when executed, cause the one or more processors to transform the zig-zag ordering of a set of coefficients corresponding to a macroblock of video data to a transposed zig-zag ordering of the set of coefficients.
11. The machine accessible medium of claim 10 wherein transforming the set of coefficients representing video data from the zig-zag order to the second order comprises transforming a matrix having an original order of
12. The machine accessible medium of claim 9 wherein the mask comprises a 64-bit value where each bit in the mask corresponds to a coefficient in a discrete cosine transformed macroblock of video data.
13. The machine accessible medium of claim 9 wherein the mask comprises a 64-bit value where each bit in the mask corresponds to a coefficient in a discrete cosine transformed and quantized macroblock of video data.
14. The machine accessible medium of claim 9 wherein the instructions that cause the one or more processors to retrieve the non-zero coefficients comprises instructions that, when executed, cause the one or more processors to access memory locations storing the set of coefficients only to retrieve non-zero coefficients.
15. The machine accessible medium of claim 9 wherein the instructions that cause the one or more processors to generate the mask comprises instructions that, when executed, cause the one or more processors to:
determine whether a coefficient exceeds a predetermined threshold value; and
generate an entry in a vector to be used in computing the mask, the entry corresponding to the location of the coefficient within the macroblock that exceeds the predetermined threshold value.
16. The machine accessible medium of claim 15 wherein the coefficient comprises a quantized coefficient.
means for transforming a set of n coefficients representing video data from a zig-zag order to a second order;
means for generating an n-bit mask indicating whether the individual coefficients in the second order are non-zero, n is an integer greater than 1;
means for storing the mask as one or more vectors, wherein the stored vectors are factored so that the sum of the mask can be determined using only shift and bitwise OR operations;
means for retrieving the non-zero coefficients;
means for encoding the set of coefficients based on the number of leading zero coefficients determined from the mask and corresponding non-zero entries; and
means for transmitting the encoded set of coefficients in an encoded video bitstream.
18. The apparatus of claim 17 wherein transforming the set of coefficients representing video data from the zig-zag order to the second order comprises transforming a matrix having an original order of
19. The apparatus of claim 17 wherein the mask comprises a 64-bit value where each bit in the mask corresponds to a coefficient in a discrete cosine transformed macroblock of video data.
20. The apparatus of claim 17 wherein the mask comprises a 64-bit value where each bit in the mask corresponds to a coefficient in a discrete cosine transformed and quantized macroblock of video data.
21. The apparatus of claim 17 wherein the means for retrieving the non-zero coefficients comprises means for accessing memory locations storing the set of coefficients only to retrieve non-zero coefficients.
22. The apparatus of claim 17 wherein the means for generating the mask comprises:
means for determining whether a coefficient exceeds a predetermined threshold value; and
means for generating an entry in a vector to be used in computing the mask, the entry corresponding to the location of the coefficient within the macroblock that exceeds the predetermined threshold value.
23. The apparatus of claim 22 wherein the coefficient comprises a quantized coefficient.
one or more processors coupled with the memory, the one or more processors to transform a set of coefficients representing video data from a zig-zag order to a second order, generate a mask indicating whether the individual coefficients in the second order are non-zero, determine using the mask, a number of leading zero coefficients for the non-zero coefficients, store the mask as one or more vectors, wherein the stored vectors are factored so that the sum of the mask can be determined using only shift and bitwise OR operations, retrieve the non-zero coefficients, encode the set of coefficients based on the number of leading zero coefficients determined from the mask and corresponding non-zero entries, and transmit the encoded set of coefficients in an encoded video bitstream.
25. The system of claim 24 wherein transforming the set of coefficients representing video data from the zig-zag order to the second order comprises transforming a matrix having an original order of
26. The system of claim 24 wherein the mask comprises a 64-bit value where each bit in the mask corresponds to a coefficient in a discrete cosine transformed macroblock of video data.
27. The system of claim 24 wherein the mask comprises a 64-bit value where each bit in the mask corresponds to a coefficient in a discrete cosine transformed and quantized macroblock of video data.
28. The system of claim 24 wherein the one or more processors retrieving the non-zero coefficients comprises the one or more processors to accessing memory locations storing the set of coefficients only to retrieve non-zero coefficients.
29. The system of claim 24 wherein the one or more processors generating the mask comprises the one or more processors determining whether a coefficient exceeds a predetermined threshold value, and generating an entry in a vector to be used in computing the mask, the entry corresponding to the location of the coefficient within the macroblock that exceeds the predetermined threshold value.
This application is a continuation application of U.S. patent application Ser. No. 10/041,535, filed Jan. 7, 2002 now U.S. Pat. No. 6,985,529.
In a typical MPEG encoding scheme, a frame of an image is divided into macroblocks. Each 16 pixel by 16 pixel macroblock (which is further divided into four 8 by 8 blocks) has 256 bytes of luminance (Y) data for the 256 pixels of the macroblock. The blue chrominance (U) and red chrominance (V) data for the pixels of the macroblock are communicated at � resolution, or 64 bytes of U data and 64 byes of V data for the macroblock and filtering is used to blend pixel colors.
The macroblock data output by DCT 110 is further processed by quantization 120. A DCT coefficient is quantized by dividing the DCT coefficient by a nonzero positive integer called a quantization value and rounding the quotient to the nearest integer. See, for example, Joan L. Mitchell, et al., “MPEG Video Compression Standard,” Kluwer Academic Publishers, 1996, pages 46-49. The quantized macroblock coefficients are converted from a two-dimensional format (e.g., 16�16 block) to a one-dimensional sequence using a zig-zag scanning order. The sequence resulting from zig-zag transform 130 is a compressible bitstream.
FIG. 3 is a flow diagram of one embodiment of generation of a mask to indicate non-zero entries in a zig-zag transformed array of quantized video data coefficients.
To minimize the lengths of these runs, coefficients are encoded in a zig-zag order, which groups the lower-order (and therefore more likely non-zero) coefficients together and the higher-order coefficients at the end of the sequence. The zig-zag transform is performed at processing block 130. A zig-zag conversion of an 8�8 matrix having an original order of:
O = [ 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 ] is converted to an order of:
This conversion will usually result in a few short runs at the beginning of the sequence with the sequence typically ending with a long run of zeros. The run/level pairs of the sequence are encoded using a Huffman table with shorter entries given smaller entries so this strategy of run/level ordering results in a smaller, more concise variable length coding of the data. The zig-zag transformed coefficients are stored in memory.
The transposed zig-zag array is
In one embodiment, a 64-bit mask that represents all non-zero coefficients in Z′ is generated during quantization. If the mask is a 64-bit value, the value for the first element (most significant bit) is 263 and the value for the last element (least significant bit) is 20. The bit values for each element of Z′ are given by:
L = [ 2 63 2 61 2 60 2 54 2 53 2 43 2 42 2 28 2 62 2 59 2 55 2 52 2 44 2 41 2 29 2 27 2 58 2 56 2 51 2 45 2 40 2 30 2 26 2 15 2 57 2 50 2 46 2 39 2 31 2 25 2 16 2 14 2 49 2 47 2 38 2 32 2 24 2 17 2 13 2 6 2 48 2 37 2 33 2 23 2 18 2 12 2 7 2 5 2 36 2 34 2 22 2 19 2 11 2 8 2 4 2 1 2 35 2 21 2 20 2 10 2 9 2 3 2 2 2 0 ] This matrix can be grouped and factored into:
M 1 = 2 b 1 [ 2 13 2 11 2 12 2 9 2 8 2 6 2 7 2 0 ] M 2 = 2 b 2 [ 2 21 2 15 2 16 2 13 2 12 2 6 2 7 2 0 ] M 3 = 2 b 3 [ 2 28 2 18 2 19 2 16 2 15 2 5 2 6 2 0 ] M 4 = 2 b 4 [ 2 28 2 14 2 15 2 13 2 12 2 1 2 2 2 0 ] M 5 = 2 b 5 [ 2 28 2 26 2 27 2 16 2 15 2 13 2 14 2 0 ] M 6 = 2 b 6 [ 2 28 2 22 2 23 2 13 2 12 2 9 2 10 2 0 ] M 7 = 2 b 7 [ 2 24 2 17 2 18 2 12 2 11 2 8 2 9 2 3 ] M 8 = 2 b 8 [ 2 13 2 6 2 7 2 5 2 4 2 1 2 2 2 0 ] with b1=50, b2=39, b3=25, b4=14, b5=21, b6=10, b7=0, and b8=0.
Factoring further provides:
Thus, each Mn can be written as Mn=Nn�Pn�2b n where
N 1 = [ 2 13 2 11 2 12 2 9 2 8 2 6 2 7 2 0 ] N 2 = [ 2 15 2 15 2 15 2 13 2 12 2 6 2 7 2 0 ] N 3 = [ 2 15 2 15 2 15 2 15 2 15 2 5 2 6 2 0 ] N 4 = [ 2 15 2 14 2 15 2 13 2 12 2 1 2 2 2 0 ] N 5 = [ 2 15 2 15 2 15 2 15 2 15 2 13 2 14 2 0 ] N 6 = [ 2 15 2 15 2 15 2 13 2 12 2 9 2 10 2 0 ] N 7 = [ 2 15 2 15 2 15 2 12 2 11 2 8 2 9 2 3 ] N 8 = [ 2 13 2 6 2 7 2 5 2 4 2 1 2 72 2 0 ] P 1 = [ 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 ] P 2 = [ 2 6 2 0 2 1 2 0 2 0 2 0 2 0 2 0 ] P 3 = [ 2 13 2 3 2 4 2 1 2 0 2 0 2 0 2 0 ] P 4 = [ 2 13 2 0 2 0 2 0 2 0 2 0 2 0 2 0 ] P 5 = [ 2 13 2 11 2 12 2 1 2 0 2 0 2 0 2 0 ] P 6 = [ 2 13 2 7 2 3 2 0 2 0 2 0 2 0 2 0 ] P 7 = [ 2 9 2 2 2 3 2 0 2 0 2 0 2 0 2 0 ] P 8 = [ 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 ] Thus, every element of Nn and Pn can be expressed as a product of two 16-bit values and one 64-bit value. Summing all elements of Nn�Pn�2b n results in 264−1 or a 64-bit value with all bits set.
W1=(213 211 215 215 215 215 215 214)
W2=(212 29 215 213 215 215 215 213)
W3=(28 26 212 26 215 25 212 21)
W4=(27 20 27 20 26 20 22 20)
W5=(215 215 215 215 215 215 213 26)
W6=(215 215 215 213 215 212 27 25)
W7=(215 213 212 29 211 28 24 21)
W8=(214 20 210 20 29 23 22 20)
X1=(20 20 26 20 213 23 213 20)
X2=(20 20 21 20 24 21 20 20)
X3=(20 20 20 20 20 20 20 20)
X4=(20 20 20 20 20 20 20 20)
X5=(213 211 213 27 29 22 20 20)
X6=(212 21 28 20 23 20 20 20)
X7=(20 20 20 20 20 20 20 20)
X8=(20 20 20 20 20 20 20 20)
Given a matrix Q of quantized coefficients represented by row vectors {Q1 . . . Qn} the elements of each Wn are zeroed out for every corresponding zero element of Qn to create a set of vectors W′n. In one embodiment, the zeroing out of the elements of the vectors Wn is performed at the quantization phase of MPEG encoding. The result of each quantization operation is used to determine whether each element of the vector Wn should be clear or set. In one embodiment, the result of the DCT operation is used to determine whether the coefficient will be zero or non-zero after the quantization operation. For example, if a coefficient is below a threshold value before quantization, that coefficient will be zero after quantization. In one embodiment, vector compare and vector select instructions are used; however, other instructions can also be used depending on the architecture used.
Multiply-sum operations are performed on vectors Xn and W′n such that the following vectors are produced.
V 1 = ∑ i = 1 4 ( X 1 i W 1 i ′ + X 2 i W 2 i ′ + X 3 i W 3 i ′ + … + X 7 i W 7 i ′ + X 8 i W 8 i ′ ) V 2 = ∑ i = 5 8 ( X 1 i W 1 i ′ + X 2 i W 2 i ′ + X 3 i W 3 i ′ + … + X 7 i W 7 i ′ + X 8 i W 8 i ′ ) where the summation symbol operates componentwise (i.e., each component is a sum of eight XW′ products. Using the vector architecture described above, the generation of all W′n and subsequent calculation of V1 and V2 requires 24 instructions, which averages 0.375 instructions per coefficient.
Using 64-bit arithmetic, the following is performed:
T = ∑ i = 1 4 V 1 , i * 2 b i + V 2 , i * 2 b i + 4 which can be calculated using only shifts and bitwise OR operations. The result, T, is the sum of the bitmask. Having the bitmask allows simplified determination of the run lengths of zeros by counting the leading zeros. When non-zero elements are indicated by the bitmask, the non-zero elements can be retrieved from memory using a lookup table. The bitmask also allows an early abort when all remaining coefficients are zero rather than the exhaustive scan that would otherwise be required.
An electronically-accessible medium includes any mechanism that provides (i.e., stores) content (e.g., computer executable instructions) in a form readable by an electronic device (e.g., a computer, a personal digital assistant, a cellular telephone). A machine-accessible medium includes read only memory (ROM); random access memory (RAM); magnetic disk storage media; optical storage media; flash memory devices.
Patent CitationsCited PatentFiling datePublication dateApplicantTitleUS4821119 *May 4, 1988Apr 11, 1989Bell Communications Research, Inc.Method and apparatus for low bit-rate interframe video codingUS5657086 *Mar 31, 1994Aug 12, 1997Sony CorporationHigh efficiency encoding of picture signalsUS5659362 *Sep 7, 1994Aug 19, 1997University Of South FloridaVLSI circuit structure for implementing JPEG image compression standardUS5737020 *Jan 7, 1997Apr 7, 1998International Business Machines CorporationAdaptive field/frame encoding of discrete cosine transformUS5821887 *Nov 12, 1996Oct 13, 1998Intel CorporationMethod and apparatus for decoding variable length codesUS5959872 *Oct 28, 1996Sep 28, 1999Samsung Electronics Co., Ltd.Apparatus and method for bidirectional scanning of video coefficientsUS6351492 *Jun 29, 1998Feb 26, 2002Daewoo Electronics Co., Ltd.Method and apparatus for encoding a video signalUS6373412 *Dec 15, 2000Apr 16, 2002International Business Machines CorporationFast JPEG huffman encoding and decodingUS6452970 *Oct 22, 1998Sep 17, 2002Siemens AktiengesellschaftMethod and device for processing a digitized imageUS6473463 *May 18, 2001Oct 29, 2002Intel CorporationTemporal tile staggering for block based video compressionUS6529554 *Jun 29, 2000Mar 4, 2003Intel CorporationLow branch-mispredict technique for MPEG run length encodingUS6731686 *May 31, 2000May 4, 2004Sun Microsystems, Inc.Apparatus and method for pipelining variable length decode and inverse quantization operations in a hybrid motion-compensated and transform coded video decoderUS6985529 *Jan 7, 2002Jan 10, 2006Apple Computer, Inc.Generation and use of masks in MPEG video encoding to indicate non-zero entries in transformed macroblocks* Cited by examinerNon-Patent CitationsReference1"Information Technology-Coding of Moving Pictures and Associated Audio for Digital Storage Media at Up to About 1,5 Mbit/s-Part 2: Video," International Standard, ISO/IEC # 11172, Part 2, 1993, pp. i-113, Published by ISO/IEC, Switzerland.2"Information Technology-Coding of Moving Pictures and Associated Audio for Digital Storage Media at Up to About 1,5 Mbit/s-Part 2: Video," Technical Corrigendum 1, International Standard, ISO/IEC # 11172, Part 2, 1996, pp. 1-2, Published by ISO/IEC, Switzerland.3"Information Technology-Coding of Moving Pictures and Associated Audio for Digital Storage Media at Up to About 1,5 Mbit/s-Part 2: Video," Technical Corrigendum 2, International Standard, ISO/IEC # 11172, Part 2, 1999, pp. 1-5, Published by ISO/IEC, Switzerland.4Office Action for U.S. Appl. No. 10/041,535 mailed Aug. 16, 2004, 8 pgs.Classifications U.S. Classification375/240.2International ClassificationH04B1/66, H04N7/30, H04N7/26, G06F17/16, G06F17/14, H04N7/50Cooperative ClassificationH04N19/60, H04N19/126, H04N19/112European ClassificationH04N7/26A4C4, H04N7/30, H04N7/26A4Q2Legal EventsDateCodeEventDescriptionOct 1, 2012FPAYFee paymentYear of fee payment: 4Apr 30, 2007ASAssignmentOwner name: APPLE INC.,CALIFORNIAFree format text: CHANGE OF NAME;ASSIGNOR:APPLE COMPUTER, INC., A CALIFORNIA CORPORATION;US-ASSIGNMENT DATABASE UPDATED:20100225;REEL/FRAME:19241/20Free format text: CHANGE OF NAME;ASSIGNOR:APPLE COMPUTER, INC., A CALIFORNIA CORPORATION;US-ASSIGNMENT DATABASE UPDATED:20100406;REEL/FRAME:19241/20Owner name: APPLE INC., CALIFORNIAFree format text: CHANGE OF NAME;ASSIGNOR:APPLE COMPUTER, INC., A CALIFORNIA CORPORATION;REEL/FRAME:019241/0020Effective date: 20070109Owner name: APPLE INC., CALIFORNIAFree format text: CHANGE OF NAME;ASSIGNOR:APPLE COMPUTER, INC., A CALIFORNIA CORPORATION;REEL/FRAME:019241/0020Effective date: 20070109Owner name: APPLE INC.,CALIFORNIAFree format text: CHANGE OF NAME;ASSIGNOR:APPLE COMPUTER, INC., A CALIFORNIA CORPORATION;US-ASSIGNMENT DATABASE UPDATED:20100225;REEL/FRAME:19241/20Effective date: 20070109Owner name: APPLE INC.,CALIFORNIAFree format text: CHANGE OF NAME;ASSIGNOR:APPLE COMPUTER, INC., A CALIFORNIA CORPORATION;US-ASSIGNMENT DATABASE UPDATED:20100406;REEL/FRAME:19241/20Effective date: 20070109Owner name: APPLE INC.,CALIFORNIAFree format text: CHANGE OF NAME;ASSIGNOR:APPLE COMPUTER, INC., A CALIFORNIA CORPORATION;REEL/FRAME:019241/0020Effective date: 20070109RotateOriginal ImageGoogle Home - Sitemap - USPTO Bulk Downloads - Privacy Policy - Terms of Service - About Google Patents - Send FeedbackData provided by IFI CLAIMS Patent Services