Obviousness

Obviousness Analysis under 35 U.S.C. § 103 for US Patent 7,707,214

This analysis considers combinations of prior art references that would render the claims of US Patent 7,707,214 obvious to a person having ordinary skill in the art (PHOSITA) at the time of the invention (priority date February 21, 2007). The patent addresses the inefficiency of repeatedly searching large, sparsely updated datasets for extrema, particularly in applications like video encoding using Matching Pursuits (MP) algorithms.

The core invention of US 7,707,214 lies in the use of a hierarchical data structure (e.g., a pyramid or tree) to efficiently locate and update extreme data values (e.g., maximum absolute inner products) within a dataset. This structure is built by partitioning a base level of data values and generating successive higher levels, each holding indices to extreme values of the partitions in the level below it, culminating in an apex containing the index of the overall extremum. Crucially, when a data value changes at the base level, only the affected portions of the hierarchy are updated, rather than requiring a full re-search of the entire dataset.

Prior Art References for Consideration:

The patent explicitly cites several references related to Matching Pursuits and video coding:

1. US 5,699,121 to Zakhor and Neff (1997): "Method and apparatus for compression of very low bit rate video signals". This patent is directly cited in US 7,707,214 as an example of MP methods applied to 2D video coding.
2. Mallat, S. G. and Zhang, Z. (1993): “Matching pursuits with time-frequency dictionaries”, IEEE Trans. Signal Processing. Described as the first MP method for 1D audio signals.
3. Neff, R. and Zakhor, A. (1997): “Very low bit rate video coding based on matching pursuits” IEEE Trans. Circuits and Systems for Video Tech. An earlier paper by some of the inventors of US 5,699,121, also focused on MP for 2D video.
4. Monro, D. M. et al. (2000): “Visual embedding of wavelet transform coefficients”, IEEE Int. Conf. Image Process. (ICIP 2000). (Relates to Precision Limited Quantization (PLQ)).
5. Yuan, Y. and Monro, D. M. (2005): “improved Matching Pursuits Image Coding”, IEEE International Conference on Acoustics, Speech and Signal Processing ICASSP 2005. (Relates to MERGE code and PLQ).

For this obviousness analysis, the primary focus will be on references 1, 2, and 3, as they directly address Matching Pursuits algorithms and their application to video data, which forms the context for the hierarchical data structure invention. References 4 and 5, while cited, appear to pertain more to quantization and coding specifics rather than the core extremum-finding mechanism.

Independent Claims of US 7,707,214:

The independent claims, as summarized previously, cover:

• Claim 1 (Method for generating data): Partitioning base level data, generating a first level with extreme indices from partitions, generating an apex with an overall extreme index, and efficiently updating the first level if a new extreme data value appears in a partition, propagating the new index to the apex.
• Claim 13 (System for generating data): A system (processor, memory, hierarchical data structure) configured to perform the method of Claim 1.
• Claim 26 (Computer-readable storage medium for data generation): A storage medium with instructions for performing Claim 1.
• Claim 37 (Video encoding method): The method of Claim 1, specifically applied to video data values (e.g., absolute inner products in an MP process).
• Claim 49 (Video encoding system): The system of Claim 13, specifically for video encoding.
• Claim 61 (Computer-readable storage medium for video encoding): A storage medium with instructions for performing Claim 37.

The key distinguishing feature across these claims is the hierarchical update scheme for extremum location using indirect addressing, which allows for efficient updates when base-level data changes. Prior art MP algorithms inherently involve repeated searches for extrema.

Combination 1: Mallat & Zhang (1993) / Neff & Zakhor (1997) / US 5,699,121 in view of general knowledge of hierarchical data structures

Teachings of the References:

• Mallat & Zhang (1993) ("Matching pursuits with time-frequency dictionaries") describes the fundamental Matching Pursuits algorithm. In MP, an algorithm repeatedly selects a function (an "atom") from a dictionary that best matches a signal, subtracts it, and repeats the process on the residual. The "best match" is typically determined by finding the maximum absolute inner product between the signal residual and the dictionary atoms. This requires a search, and subsequent iterations involve re-evaluating matches after the signal changes. The paper implies a full search for the maximum inner product at each step to find the best atom.
• Neff & Zakhor (1997) ("Very low bit rate video coding based on matching pursuits") and US 5,699,121 (Zakhor et al. 1997) apply the MP technique to 2D video data, specifically for low bit-rate video coding. These references would teach finding extrema (e.g., maximum absolute inner products) within datasets representing video frames or frame differences. US 5,699,121 describes an apparatus for video compression using MP, emphasizing the iterative process of selecting atoms that match the image data, encoding them, and then updating the image data. The repeated search for the "best matching basis function" (i.e., the extremum of inner products) is central to their teaching. Neither of these explicitly teaches a hierarchical data structure for efficiently updating the extremum location when data changes. The implicit method for finding the best atom in MP is a full search over the relevant set of inner products.

Motivation to Combine:

A PHOSITA in the field of signal processing and video compression, familiar with Matching Pursuits algorithms, would recognize the computational intensity of repeatedly performing a full search for the maximum absolute inner product (or other extrema) over potentially large datasets with each iteration. The patent itself highlights this problem: "Repeatedly searching the entirety of such updated data sets for new extrema wastes computing resources and may be too slow for many applications."

Given this recognized problem in MP, a PHOSITA would be motivated to improve the efficiency of the extremum search process. Hierarchical data structures, such as quadtrees, octrees, k-d trees, or segment trees, for efficient data querying and updates were well-known in computer science for managing large datasets, including for finding minima/maxima, even before the priority date of US 7,707,214. For example, for a 2D dataset, a quadtree hierarchically partitions space into four quadrants, allowing for efficient range queries or updates to specific regions.

A PHOSITA, seeking to optimize the MP algorithm as described by Mallat & Zhang, Neff & Zakhor, or US 5,699,121, would naturally consider applying such well-known data structures to the problem of efficiently finding the maximum inner product and updating the search space when an atom is subtracted (which affects a "footprint" of inner product values).

The combination would involve:

1. Taking the MP algorithm from Mallat & Zhang (for the general principle) or Neff & Zakhor / US 5,699,121 (for video application). These references teach the need to find an extremum (e.g., maximum absolute inner product) at each iteration.
2. Applying a conventional hierarchical data structure (as generally known in the art for efficient extremum finding and localized updates) to store the absolute inner product values. This hierarchical structure would involve:
   • Partitioning the base level data (e.g., the inner product values).
   • Generating higher levels that store indices to the extrema of the lower-level partitions.
   • Propagating updates only through the affected branches of the hierarchy when a base-level data value changes.

The PHOSITA would understand that by organizing the inner product values in a hierarchical manner, the search for the global maximum could be significantly accelerated, especially when only a subset of the inner product values change (as is the case with an atom's "footprint" in MP). The motivation is explicitly to reduce computational resources and improve speed, which directly addresses the recognized problem in the field.

Therefore, the claims of US 7,707,214, particularly Claim 1 and its dependent claims, would be obvious as an application of well-known hierarchical data structure optimization techniques to the problem of efficient extremum finding and updating within the context of iterative Matching Pursuits algorithms for signal and video processing. The problem to be solved (inefficient full searches in MP) was known, and the solution (hierarchical data structures for efficient updates) was also known in a general computing context for similar problems. The combination would have been a matter of routine optimization for a PHOSITA.