Obviousness

Obviousness Analysis of US Patent 9036701 under 35 U.S.C. § 103

US Patent 9036701 (hereinafter '701 patent) claims a method and apparatus for providing complexity-balanced entropy coding in video content. The core invention, as defined by Claim 1, involves categorizing syntax elements based on their frequency of occurrence and applying different entropy coding techniques (with or without context updating) to these categories.

Specifically, Claim 1 of the '701 patent recites:
"1. A method comprising:
determining a frequency of occurrence threshold based on an expected frequency of occurrence of syntax elements in a bit stream;
categorizing a plurality of syntax elements of video content into first and second categories based on the frequency of occurrence threshold, wherein syntax elements which occur greater than the frequency of occurrence threshold are categorized into the first category and syntax elements which occur less than the frequency of occurrence are categorized into the second category;
entropy coding symbols that correspond to the first category of syntax elements and that have been subjected to a context update; and
entropy coding symbols that correspond to the second category of syntax elements and that have bypassed context updating."

A person having ordinary skill in the art (PHOSITA) in video coding at the time of the invention (priority date 2010-07-28) would have been familiar with the H.264/AVC video coding standard and its associated entropy coding schemes, Context Adaptive Variable Length Coding (CAVLC) and Context Adaptive Binary Arithmetic Coding (CABAC). The '701 patent itself acknowledges that H.264/AVC defines coding tools with different computational requirements in different profiles, with some supporting only CAVLC and others supporting CABAC, and that "computational requirements of the CABAC method increase substantially as a function of the utilized bitrate" particularly for DCT transform coefficients. This background identifies a known problem in the art: balancing coding efficiency (achieved by complex methods like CABAC) with computational complexity.

The combination of the following prior art references, along with the common general knowledge in the field, would render Claim 1 of the '701 patent obvious:

1. Marpe et al., "Context-Based Adaptive Binary Arithmetic Coding in the H.264/AVC Video Compression Standard" (2003): This non-patent literature is a foundational text describing CABAC, a key entropy coding method in H.264/AVC. It teaches the use of context models combined with adaptive binary arithmetic coding to achieve high coding efficiency and redundancy reduction. This directly discloses the concept of "entropy coding symbols... subjected to a context update," which is applied to the first category in Claim 1. Marpe et al. also acknowledges that the "computational requirements of CABAC may be still too high given today's silicon technology" and that H.264/AVC offers a baseline entropy coding method (CAVLC) with "reduced coding efficiency and complexity level compared to CABAC" for certain syntax elements, such as residual data. This implicitly teaches the existence and use of lower-complexity entropy coding methods that may involve less or no context adaptation.

2. Vivienne et al., "A High Throughput CABAC Algorithm Using Syntax Element Partitioning" (2009): This paper explicitly addresses the throughput bottleneck of CABAC in video decoding. It proposes a new CABAC algorithm where "binary symbols are grouped by syntax elements and assigned to different partitions which can be decoded in parallel". While focused on parallel processing, this reference clearly teaches the concept of categorizing or partitioning syntax elements and applying different processing (in this case, parallel decoding) based on these groupings. The paper also mentions an "adaptive binary symbol allocation scheme" that recognizes that the "distribution of binary symbols changes with quantization", demonstrating an awareness of varying symbol statistics (i.e., frequency of occurrence) in video coding.

Motivation for Combination:

A PHOSITA, faced with the recognized problem of high computational complexity associated with CABAC, particularly at high bitrates for frequently occurring data like transform coefficients (as highlighted by the '701 patent's background and Marpe et al.), would be motivated to optimize the balance between coding efficiency and complexity.

1. Categorization based on Frequency: The recognition that different syntax elements have varying statistical properties (as hinted by Vivienne et al.'s "adaptive binary symbol allocation scheme" and generally understood in adaptive coding) would motivate a PHOSITA to treat these elements differently. A "frequency of occurrence threshold" (as in Claim 1) is a straightforward and obvious statistical metric to use for such categorization, as it directly relates to how often a symbol contributes to both data size and processing load.

   • The idea of partitioning or grouping syntax elements (Vivienne et al.) provides the structural basis for this categorization.
   • The determination of a threshold is a routine engineering step when implementing a decision rule based on a quantifiable characteristic like frequency.

2. Differential Entropy Coding:

   • For syntax elements that occur greater than the frequency of occurrence threshold (first category in Claim 1), a PHOSITA would naturally choose the most efficient coding method available. Given Marpe et al.'s teaching of CABAC and its high efficiency due to context adaptation, applying "entropy coding symbols... subjected to a context update" to these high-frequency elements would be an obvious choice to maximize compression where it matters most.
   • For syntax elements that occur less than the frequency of occurrence threshold (second category in Claim 1), the computational overhead of full context adaptation might not be justified due to their rarity, or the benefit to coding efficiency might be minimal. A PHOSITA, aware of the complexity concerns with CABAC and the existence of simpler coding methods in H.264/AVC (e.g., CAVLC, or inherent bypass modes within arithmetic coders as described in the '701 patent), would be motivated to "bypass context updating" for these less frequent symbols to reduce overall computational complexity. The patent itself alludes to "static fifty percent bin probabilities" or a "bypass coding mode for a CABAC engine" as a known simplification.

By combining the teachings of Marpe et al. (for context-adaptive arithmetic coding), Vivienne et al. (for syntax element partitioning/grouping and adaptive allocation based on statistics), and the general knowledge within H.264/AVC of balancing complexity and efficiency through different coding tools, a PHOSITA would find it obvious to categorize syntax elements based on frequency and selectively apply context-adaptive or context-bypassed entropy coding to achieve a "complexity balanced" system as described in Claim 1. The motivation is clear: to mitigate the computational bottlenecks of complex entropy coding while preserving efficiency for the most significant data.