Source: http://www.google.ca/patents/US8824557
Timestamp: 2018-01-23 10:20:02
Document Index: 185194819

Matched Legal Cases: ['Application No. 05026123', 'Application No. 2005137246', 'Application No. 05026123', 'Application No. 2005234613', 'Application No. 2527654', 'Application No. 2527654', 'Application No. 10', 'art 2', 'Application No. 2005234613', 'Application No. 2005', 'Application No. 2005', 'Application No. 10', 'Application No. 2005', 'Application No. 200510128737', 'Application No. 200510128737', 'Application No. 200510128737', 'Application No. 200510128737', 'Application No. 2005137246']

Patent US8824557 - Adaptive coefficient scan order - Google Patents
A digital media codec adaptively re-arranges a coefficient scan order of transform coefficients in accordance with the local statistics of the digital media, so that the coefficients can be encoded more efficiently using entropy encoding. The adaptive scan ordering is applied causally at encoding and...http://www.google.ca/patents/US8824557?utm_source=gb-gplus-sharePatent US8824557 - Adaptive coefficient scan order
Publication number US8824557 B2
Application number US 13/674,748
Also published as CA2527654A1, CA2527654C, CN1798341A, CN1798341B, EP1679903A2, EP1679903A3, EP1679903B1, US8311119, US20060146936, US20130070843
Publication number 13674748, 674748, US 8824557 B2, US 8824557B2, US-B2-8824557, US8824557 B2, US8824557B2
Patent Citations (28), Non-Patent Citations (32), Classifications (15), Legal Events (1)
US 8824557 B2
1. A block transform-based method of encoding a compressed bitstream containing digital media data, the method comprising:
iteratively for each of a plurality of successive blocks in order:
entropy encoding coefficient values at locations of a current one of the plurality of successive blocks according to a scan order;
analyzing the statistical incidence of occurrence of non-zero-value coefficient values at the locations;
updating a set of cumulative statistics of the occurrence of non-zero-value coefficients at the locations, the cumulative statistics accounting for the occurrence of non-zero-value coefficient values at the locations in each block previously encoded since a scan order was set to an initial order; and
wherein the adapting comprises exchanging the scan order of a first location with the scan order of a second location if the cumulative statistics indicate a higher occurrence of non-zero coefficient values at the second location than at the first location and not exchanging the scan order of the first location with the scan order of the second location if the cumulative statistics indicate a lower occurrence of non-zero coefficient values at the second location than at the first location, wherein the scan order of the second location is adjacent to the scan order of the first location, and wherein the method further comprises performing no further changes to the scan order of the second location for the current block if the scan order of the first location is exchanged with the scan order of the second location.
2. The method of claim 1 further comprising periodically resetting the statistics of the incidence of non-zero-value occurrence of coefficients values at the locations during the encoding of blocks of the digital media data.
4. The method of claim 1, wherein the scan order is stored in a first array and the cumulative statistics are stored in a second array.
6. The method of claim 1, further comprising performing only a single conditional exchange of two locations in the scan order per block of the digital media data.
7. At least one computer-readable media device storing a program for causing a computer to perform a method, the method comprising:
8. The at least one computer-readable media device of claim 7, wherein the method further comprises periodically resetting the statistics of the incidence of non-zero-value occurrence of coefficients values at the locations during the encoding of blocks of the digital media data.
9. The at least one computer-readable media device of claim 7, wherein the method further comprises:
10. The at least one computer-readable media device of claim 7, wherein the scan order is stored in a first array and the cumulative statistics are stored in a second array.
11. The at least one computer-readable media device of claim 7, wherein the method further comprises:
12. The at least one computer-readable media device of claim 7, wherein the method further comprises performing only a single conditional exchange of two locations in the scan order per block of the digital media data.
13. A digital media processing device, comprising:
a processor programmed to perform a method, the method comprising:
for each of a plurality of successive blocks in order:
14. The digital media processing device of claim 13, wherein the method further comprises periodically resetting the statistics of the incidence of non-zero-value occurrence of coefficients values at the locations during the encoding of blocks of the digital media data.
15. The digital media processing device of claim 13, wherein the method further comprises:
16. A block transform-based method of encoding a compressed bitstream containing digital media data, the method comprising:
17. The method of claim 16, wherein the method further comprises periodically resetting the statistics of the incidence of non-zero-value occurrence of coefficients values at the locations during the encoding of blocks of the digital media data.
This application is a continuation of U.S. patent application Ser. No. 11/026,650, filed Dec. 31, 2004, which is hereby incorporated by reference.
The block transform 120-121 can be defined as a mathematical operation on a vector x of size N. Most often, the operation is a linear multiplication, producing the transform domain output y=M×,M being the transform matrix. When the input data is arbitrarily long, it is segmented into N sized vectors and a block transform is applied to each segment. For the purpose of data compression, reversible block transforms are chosen. In other words, the matrix M is invertible. In multiple dimensions (e.g., for image and video), block transforms are typically implemented as separable operations.
Temp := Order[n]
Order[n] := Order[n − 1]
Order[n − 1] := Temp
Temp := Totals[n]
Totals[n] := Totals[n − 1]
Totals[n − 1] := Temp
US5767909 27 Mar 1996 16 Jun 1998 Daewoo Electronics, Co., Ltd. Apparatus for encoding a digital video signal using an adaptive scanning technique
US6408025 2 Aug 1999 18 Jun 2002 Siemens Aktiengesellschaft Method and configuration for coding and decoding digitized pictures
US7215707 14 Nov 2002 8 May 2007 Samsung Electronics Co., Ltd. Optimal scanning method for transform coefficients in coding/decoding of image and video
US20020107669 14 Nov 2001 8 Aug 2002 Yu-Ling Chen Entropy coding
US20030128753 * 14 Nov 2002 10 Jul 2003 Samsung Electronics Co., Ltd. Optimal scanning method for transform coefficients in coding/decoding of image and video
US20040120590 5 Nov 2003 24 Jun 2004 Canon Kabushiki Kaisha Data encoding with an amplitude model and path between the data and corresponding decoding
US20050068208 15 Nov 2004 31 Mar 2005 Microsoft Corporation Scan patterns for progressive video content
US20050078754 15 Nov 2004 14 Apr 2005 Microsoft Corporation Scan patterns for interlaced video content
CN1431828A 14 Nov 2002 23 Jul 2003 三星电子株式会社 Optimum scanning method for change coefficient in coding/decoding image and video
EP0836328A2 9 Oct 1997 15 Apr 1998 Texas Instruments Incorporated A coding method for a video signal
JP2003250157A Title not available
JP2003333339A Title not available
JPH0750836A Title not available
JPH0787331A Title not available
JPH0974562A Title not available
JPH06177774A Title not available
JPH08280021A Title not available
JPH11275582A Title not available
KR20000073634A Title not available
RU2202826C2 Title not available
1 Communication pursuant to Article 94(3) EPC dated Oct. 1, 2010, from European Patent Application No. 05026123.9, 4 pp.
2 Decision to Grant dated May 13, 2010, from Russian Patent Application No. 2005137246 (with English translation), 17 pp.
3 European Search Report dated Jun. 22, 2006, from European Patent Application No. 05026123.9, 7 pp.
4 Examiner's First Report dated Oct. 13, 2009, from Australian Patent Application No. 2005234613, 5 pp.
5 Examiner's Report dated Jul. 24, 2013, from Canadian Patent Application No. 2527654, 2 pp.
6 Examiner's Report dated Jul. 30, 2012, from Canadian Patent Application No. 2527654, 3 pp.
7 Fan et al., "A Novel Coefficient Scanning Scheme for Directional Spatial Prediction-Based Image Compression," Multimedia and Expo Proceedings, pp. 557-560 (Jul. 2003).
8 Final Notice of Preliminary Rejection dated Nov. 15, 2012, Korean Patent Application No. 10-2005-0115372 (with English translation), 5 pp.
11 ISO/IEC, "ISO/IEC 11172-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," 112 pp. (1993).
12 ISO/IEC, "JTC1/SC29/WG11 N2202, Information Technology—Coding of Audio-Visual Objects: Visual, ISO/IEC 14496-2," 329 pp. (1998).
13 ITU-T, "ITU-T Recommendation H.261, Video Codec for Audiovisual Services at p × 64 kbits," 25 pp. (1993).
14 ITU-T, "ITU-T Recommendation H.262, Information Technology-Generic Coding of Moving Pictures and Associated Audio Information: Video," 205 pp. (1995).
15 ITU-T, "ITU-T Recommendation H.263, Video coding for low bit rate communication," 162 pp. (1998).
16 ITU-T, "ITU-T Recommendation H.262, Information Technology—Generic Coding of Moving Pictures and Associated Audio Information: Video," 205 pp. (1995).
18 Martin, "Sorting," Computer Surveys, vol. 3, No. 4, pp. 147-174 (Dec. 1971).
19 Microsoft Corporation, "Microsoft Debuts New Windows Media Player 9 Series, Redefining Digital Media on the PC," 4 pp. (Sep. 4, 2002) [Downloaded from the World Wide Web on Jul. 16, 2004].
20 Mook, "Next-Gen Windows Media Player Leaks to the Web," BetaNews, 18 pp. (Jul. 2002) [Downloaded from the World Wide Web on Mar. 16, 2004].
21 Notice of Acceptance dated Feb. 16, 2010, from Australian Patent Application No. 2005234613, 3 pp.
22 Notice of Allowance dated Feb. 18, 2010, from Mexican Patent Application No. PA/a/2005/012973, 2 pp.
23 Notice of Allowance dated Feb. 4, 2011, from Japanese Patent Application No. 2005-379861 (with English translation), 4 pp.
24 Notice of Final Rejection dated Sep. 10, 2010, from Japanese Patent Application No. 2005-379861 (with partial English translation), 5 pp.
25 Notice of Preliminary Rejection dated Jun. 13, 2012, from Korean Patent Application No. 10-2005-0115372, 4 pp.
26 Notice of Reason for Rejection dated May 20, 2010, from Japanese Patent Application No. 2005-379861 (with English translation), 8 pp.
27 Notice on First Office Action dated Sep. 11, 2009, from Chinese Patent Application No. 200510128737.2 (with English translation), 11 pp.
28 Notice on Grant of patent Right for Invention dated Mar. 20, 2012, from Chinese Patent Application No. 200510128737.2, 4 pp.
29 Notice on the Second Office Action dated Jun. 29, 2011, from Chinese Patent Application No. 200510128737.2 (with English translation), 11 pp.
30 Notice on the Third Office Action dated Nov. 30, 2011, from Chinese Patent Application No. 200510128737.2 (with English translation), 7 pp.
31 Official Action dated Sep. 22, 2009, from Russian Patent Application No. 2005137246, 3 pp.
32 Zeng et al., "Directional Discrete Cosine Transform for Image Coding," IEEE Int'l Conf. on Multimedia and Expo, pp. 721-724 (Jul. 2006).
U.S. Classification 375/240.18, 375/240.24, 375/240.23
International Classification H04N7/18, H04N11/04, H04N19/60, H04N1/41, H04N11/02, H03M7/30
Cooperative Classification H04N19/60, H04N19/129, H04N19/13, H04N19/136, H04N19/18, H04N19/00121