Obviousness

The search results strongly point to H.264/MPEG-4 AVC's Context-Adaptive Variable-Length Coding (CAVLC) as highly relevant prior art.

Let's check the dates carefully. The priority date of US7769238 is April 15, 2002.

• Wikipedia on CAVLC states: "Context-adaptive variable-length coding (CAVLC) is a form of entropy coding used in H.264/MPEG-4 AVC video encoding." It also mentions H.264/MPEG-4 AVC "standard finalized in 2003".
• However, WO2003084242A3 (published October 9, 2003) has priority dates including US36703202P 2002-03-22 and US60/367,032 2002-03-22. These are before the priority date of US7769238 (April 15, 2002).
• Specifically, WO2003084242A3 describes: "Adaptive encoding of the number and trailing one coefficients may be performed in view of one or more neighboring sample blocks, whereas adaptive encoding of level measures may be performed in view of quantization parameters of a macroblock and previously encoded level measures." This directly teaches using neighboring blocks to adaptively encode the number of coefficients.
• The same document also cites "BJONTEGAARD G: "IMPROVED LOW COMPLEXITY ENTROPY CODING FOR TRANSFORM COEFFICIENTS", JOINT VIDEO TEAM (JVT) OF ISO/IEC MPEG & ITU-T VCEG (ISO/IEC JTC1/SC29/WG11 AND ITU-T SG16 Q.6) JVT-B045, XX, XX, 29 January 2002 (2002-01-29), pages 1 - 8, XP002257294". This document is dated January 29, 2002, which is before the priority date of US7769238. This is a crucial piece of prior art.

Let's call JVT-B045 "Bjontegaard 2002" or Reference B.
WO2003084242A3 (itself based on earlier provisional applications) confirms that the concepts of CAVLC were being developed and documented prior to the priority date of US7769238. Even if the full H.264 standard wasn't finalized, the underlying adaptive entropy coding techniques were known.

Analysis of JVT-B045 (Bjontegaard 2002) (Reference B):
While I don't have the full text of JVT-B045, the citation in WO2003084242A3 and the Wikipedia descriptions of CAVLC provide sufficient detail.

• Wikipedia states that in CAVLC, "The number of non-zero coefficients in neighbouring blocks is correlated. The number of coefficients is encoded using a look-up table; the choice of look-up table depends on the number of non-zero coefficients in neighbouring blocks." And further: "Coefficient Token (COEFF_TOKEN): Encodes the number of non-zero coefficients (TotalCoeffs) and trailing ones (T1s, up to 3 high-frequency ±1 values) using one of four context-adaptive VLC tables selected based on the average non-zero count in adjacent blocks (upper and left neighbors)."
• Vcodex BV also states: "The number of non-zero coefficients in neighbouring blocks is correlated. The number of coefficients is encoded using a look-up table; the choice of look-up table depends on the number of non-zero coefficients in neighbouring blocks." It also details the logic for calculating the "predictive value" (N in their notation): "If only block U is available, N=NU ; if only block L is available, N=NL ; if neither is available, N=0." This is very similar to the predictive value calculation described in US7769238.
• WO2003084242A3, with a priority date before April 2002, explicitly states: "Adaptive encoding of the number and trailing one coefficients may be performed in view of one or more neighboring sample blocks".

Combining MPEG-4 Visual (Reference A) with Bjontegaard 2002 / CAVLC principles (Reference B):

Reference A: ISO/IEC 14496-2:1999(E) (MPEG-4 Visual) discloses a picture coding method that codes an image block-by-block by transforming the image into spatial frequency coefficients, performing quantization, and then variable length coding using run-level coding for coefficients. This reference, as admitted by US7769238, uses fixed VLC tables for intra and inter prediction.

Reference B: The principles of Context-Adaptive Variable-Length Coding (CAVLC), as disclosed in early JVT documents like Bjontegaard G: "IMPROVED LOW COMPLEXITY ENTROPY CODING FOR TRANSFORM COEFFICIENTS", JVT-B045 (January 29, 2002), and described in WO2003084242A3 (with priority dates before April 2002), teach an adaptive variable length coding method for transform coefficients. Specifically, Reference B teaches that the number of non-zero coefficients in neighboring blocks is correlated and that the choice of VLC look-up table for encoding the number of coefficients in a current block depends on the number of non-zero coefficients in neighboring blocks. Reference B further discloses methods for deriving a "predictive value" from these neighboring blocks (e.g., using the number of non-zero coefficients from an upper or left block, or setting to 0 if none are available).

Obviousness Argument for Claims 1 and 13:

A person having ordinary skill in the art (POSITA) in video compression at the time of the invention (priority date April 15, 2002) would have been motivated to combine the teachings of MPEG-4 Visual (Reference A) with the adaptive VLC principles of CAVLC (Reference B).

1. Problem Recognition: Reference A (MPEG-4 Visual) suffers from suboptimal coding efficiency because its VLC tables are fixed for intra and inter prediction, which means efficiency "differs greatly depending on a quality of a current picture to be coded". A POSITA would recognize this as a clear drawback and seek improvements in entropy coding efficiency.

2. Motivation to Combine:

   • Adaptive VLC: The general concept of adaptive Huffman coding or adaptive VLC was well-known in data compression to improve efficiency by tailoring codes to observed statistics. Reference B (CAVLC principles) specifically applies this to video transform coefficients, identifying that the distribution of non-zero coefficients is highly variable and can be better coded with adaptive tables.
   • Context from Neighbors: It was well-established in video coding that characteristics of a current block (e.g., motion, texture, number of non-zero coefficients) are highly correlated with those of its spatially adjacent, previously coded/decoded blocks. Reference B explicitly leverages this by stating that "The number of non-zero coefficients in neighbouring blocks is correlated" and that the "choice of look-up table depends on the number of non-zero coefficients in neighbouring blocks".
   • Specific Adaptation to Number of Non-Zero Coefficients: Reference B specifically highlights the benefit of adapting VLC tables based on the number of non-zero coefficients in neighboring blocks for encoding the coeff_token (which represents the total number of non-zero coefficients and trailing ones). This is precisely the feature claimed in US7769238.

3. Combination Yields Claimed Invention:

   • Claim 1 (Coding Method): Starting with the block-based coding method of MPEG-4 Visual (Reference A) that transforms images into coefficients and performs VLC, a POSITA, motivated to improve efficiency, would look to adaptive entropy coding techniques like those described in Reference B. Reference B specifically teaches calculating a predictive value for the number of non-zero coefficients based on coded neighboring blocks and then selecting an appropriate VLC table based on this predictive value for encoding the number of non-zero coefficients in the current block. This combination directly teaches all elements of Claim 1:

     • Coding an image block-by-block by transforming into coefficients. (Reference A)
     • Predicting step: calculating a predictive value of the number of non-zero coefficients in a current block based on numbers of non-zero coefficients in coded blocks located on a periphery. (Reference B, specifically CAVLC's context derivation from upper and left neighbors)
     • Table selecting step: selecting tables for variable length coding based on the predictive value. (Reference B, CAVLC's selection of look-up tables based on the predictive value)
     • Variable length coding step: performing variable length coding for the number of coefficients other than 0 in the current block with reference to the selected tables. (Reference B, CAVLC's use of the selected tables to encode coeff_token)

   • Claim 13 (Decoding Method): The decoding method naturally mirrors the encoding method. Given the encoding scheme of Reference A modified by Reference B, a POSITA would find it obvious to apply the inverse operations for decoding. The process would involve:

     • Predicting step: calculating the same predictive value for the number of non-zero coefficients in the current block based on numbers of non-zero coefficients in decoded blocks on its periphery. (Reference B teaches that the decoder also uses the same context derivation for decoding)
     • Table selecting step: selecting the corresponding variable length decoding tables based on this predictive value. (Reference B, the decoder needs to select the same tables as the encoder to correctly decode)
     • Variable length decoding step: performing variable length decoding to obtain the number of non-zero coefficients using the selected tables. (Reference B, the decoder uses the selected tables to inverse the coeff_token encoding)

Therefore, the combination of MPEG-4 Visual (ISO/IEC 14496-2:1999(E)) with the principles of Context-Adaptive Variable-Length Coding (CAVLC) as described in JVT-B045 (Bjontegaard 2002) and WO2003084242A3 would render claims 1 and 13 of US7769238 obvious to a POSITA.## Obviousness Analysis of US Patent 7769238 Under 35 U.S.C. § 103

This analysis addresses the obviousness of US Patent 7769238, titled "Picture coding method and picture decoding method," in light of prior art available before its priority date of April 15, 2002. The patent's core innovation lies in adaptively selecting variable length coding (VLC) tables for encoding the number of non-zero coefficients in a current image block, based on a predictive value derived from the number of non-zero coefficients in neighboring coded blocks. The corresponding decoding method mirrors this adaptive table selection.

Independent Claims Recap

• Independent Claim 1 (Picture Coding Method): Encompasses block-by-block image coding where an image is transformed into spatial frequency coefficients. Key steps include: 1) calculating a predictive value for the number of non-zero coefficients in a current block using data from already coded peripheral blocks; 2) selecting VLC tables based on this predictive value; and 3) performing variable length coding for the current block's non-zero coefficient count using the selected tables.
• Independent Claim 13 (Picture Decoding Method): Describes the corresponding decoding process, involving: 1) calculating a predictive value for the number of non-zero coefficients in a current block based on data from already decoded peripheral blocks; 2) selecting variable length decoding (VLD) tables based on this predictive value; and 3) performing variable length decoding to ascertain the number of non-zero coefficients using the selected tables.

Prior Art Combination and Motivation

The primary prior art for this analysis includes the widely adopted MPEG-4 Visual standard (ISO/IEC 14496-2:1999(E)) and the principles of Context-Adaptive Variable-Length Coding (CAVLC) as documented in early Joint Video Team (JVT) contributions for the H.264/MPEG-4 AVC standard, particularly JVT-B045 by G. Bjontegaard.

Reference A: ISO/IEC 14496-2:1999(E) (MPEG-4 Visual)
The patent itself acknowledges MPEG-4 Visual as a foundational prior art. It describes a general moving picture coding scheme that divides a picture into blocks, performs intra and inter picture prediction, applies orthogonal transformations (like Discrete Cosine Transform), and then uses variable length coding based on run-level coding for coefficients representing spatial frequency components. Crucially, US7769238 highlights a problem with this existing technique: "only one table is prepared as a VLC table respectively for intra prediction coding and inter prediction coding," leading to "coding efficiency differ[ing] greatly depending on a quality of a current picture to be coded." This establishes a clear motivation for improvement in the art.

Reference B: Principles of Context-Adaptive Variable-Length Coding (CAVLC) from early H.264/AVC Development
The concepts behind CAVLC were publicly disclosed prior to the priority date of US7769238. Specifically, JVT-B045, "IMPROVED LOW COMPLEXITY ENTROPY CODING FOR TRANSFORM COEFFICIENTS" by G. Bjontegaard, dated January 29, 2002, predates the patent's priority date of April 15, 2002. Furthermore, WO2003084242A3, with a priority date of March 22, 2002, also describes these principles.

CAVLC directly addresses the adaptive encoding of transform coefficients, including the number of non-zero coefficients. According to descriptions of CAVLC, "The number of non-zero coefficients in neighbouring blocks is correlated. The number of coefficients is encoded using a look-up table; the choice of look-up table depends on the number of non-zero coefficients in neighbouring blocks." This reference further details that the choice of VLC tables for encoding the "Coefficient Token" (which includes the total number of non-zero coefficients) is "selected based on the average non-zero count in adjacent blocks (upper and left neighbors)." The method for determining a predictive value based on the availability of upper and left neighboring blocks (e.g., using the upper, left, or an average, or defaulting to zero) is also described.

Obviousness Argument for Claims 1 and 13:

A person having ordinary skill in the art (POSITA) in video compression as of April 2002 would have been motivated to combine the teachings of MPEG-4 Visual (Reference A) with the adaptive VLC principles of CAVLC (Reference B) to improve coding efficiency.

1. Problem Identification: The POSITA would readily acknowledge the inefficiency of fixed VLC tables in MPEG-4 Visual (Reference A) as explicitly stated in US7769238. The goal would be to develop a more efficient entropy coding scheme that adapts to local image characteristics.

2. Motivation for Combination:

   • Adaptive Entropy Coding: The general concept of adaptive Huffman coding or variable length coding to improve compression by dynamically adjusting coding tables based on input statistics was a known technique in data compression.
   • Exploiting Spatial Correlation: Video coding extensively uses spatial correlation, where characteristics of a current block are predicted or derived from those of its already coded/decoded neighbors. Reference B explicitly highlights that "The number of non-zero coefficients in neighbouring blocks is correlated," making this a valuable contextual cue for adaptive coding.
   • Targeting Non-Zero Coefficients: The number of non-zero coefficients is a critical factor in the bit rate of transform-coded video. Reference B specifically identifies that adapting the VLC table based on the number of non-zero coefficients in neighboring blocks is an effective way to improve coding efficiency for this parameter.

3. Combination Directly Teaches Claimed Invention:

   • For Claim 1 (Picture Coding Method): Starting with the block-based transformation and fixed VLC of MPEG-4 Visual (Reference A), a POSITA, seeking to overcome its inefficiencies, would naturally turn to adaptive entropy coding. Reference B provides a concrete method for this by teaching:

     • Calculating a predictive value for the number of non-zero coefficients in a current block by examining the number of non-zero coefficients in coded neighboring blocks (e.g., upper and left neighbors).
     • Selecting specific VLC tables based on this predictive value.
     • Using these selected VLC tables to encode the number of non-zero coefficients in the current block.
       This combination directly covers all elements of Claim 1, rendering it obvious.

   • For Claim 13 (Picture Decoding Method): The decoding method is the inverse of the coding method, and in a closed-loop system, the decoder must perform operations symmetrical to the encoder. Therefore, a POSITA would readily implement a decoding method that mirrors the combined encoding scheme:

     • Calculating the same predictive value for the number of non-zero coefficients in a current block based on decoded neighboring blocks.
     • Selecting the corresponding VLD tables using this same predictive value.
     • Performing VLD to determine the number of non-zero coefficients using the selected tables.
       This inverse process is an obvious design choice for a POSITA implementing the decoding side of the adaptively coded bitstream, making Claim 13 obvious.

In conclusion, the combination of ISO/IEC 14496-2:1999(E) (MPEG-4 Visual) with the context-adaptive VLC principles disclosed in JVT-B045 (Bjontegaard, January 29, 2002) and WO2003084242A3 (priority March 22, 2002) would have made the claimed picture coding and decoding methods of US7769238 obvious to a person having ordinary skill in the art at the time of the invention.