Video Compression Patents

1 Introduction

In early 2007, semiconductor giants Qualcomm and Broadcom faced each other in a San Diego courtroom, the culmination of a year-long patent dispute. The questions at issue were whether two Qualcomm patents were essential to the practice of the H.264 video compression standard; whether Broadcom’s products had infringed these patents; and whether Qualcomm actually had the right to try and enforce its patents in this context. Why were both firms prepared to commit to millions of dollars of legal costs and to go to the wire in a high-profile court case to fight their respective positions?

Intellectual property, patents and licensing have played an increasingly important part in the recent history of video compression (video coding). Video coding is a highly active research and development area and a core technology for a number of billion-dollar industries and so it is perhaps not surprising that there is a high level of patent activity, with a growing number of patents related to video coding. A strong patent on an important video coding concept has the potential to be very lucrative, particularly if the patented technology is adopted in a video coding standard.

2 Video coding patents

The popular international standards for video compression (such as MPEG-2, MPEG-4 and H.264/AVC) make use of the well-known “hybrid” video encoder model in which a prediction (formed from previously-transmitted frames) is subtracted from the current frame to form a residual (e.g. motion- compensated difference frame) which is then transformed (using a block transform such as the DCT), quantized and coded for transmission. In parallel, the coded frame is reconstructed and stored for future predictions.

This concept has been in existence for some time. For example, US patent 3679821, filed April 1970 and issued July 1972, describes an apparatus that “determines the difference between the momentary value of an incoming frame of video signals and a predicted value of the frame of signals, i.e. the error in prediction, and disperses the difference by transforming it into a spatially homogeneous signal. This transformed signal is then quantized for efficient transmission” (Source: US Patent 3679821, “Transform Coding of Image Difference Signals”). Figure 1 from this patent (redrawn below) shows an encoder structure that still commonly used in present-day video compression systems. A predicted frame, formed from previously coded data, is subtracted from a video frame S. The difference (residual) is transform coded, quantized and transmitted (Sq). The quantized output is inverse transformed and added to the prediction to form a “Reconstituted Signal” which is used to form further predicted frame(s).

Figure 1 - Block diagram from US patent 3679821 (redrawn)

By  the  1990s,  improvements  in  processing  and  storage  capabilities  of  integrated  circuits  and  the

development  of  international  standards  for  image  and  video  compression  led  to  a  growing  market  for video compression products and an increased level of research and development activity. This is reflected by a sharp rise in the number of published patents from the early 1990s (when the H.261 and MPEG-1 standards were published), peaking around 1998 (by which time MPEG-2 products were becoming firmly established in the market) and continuing at a steady level thereafter (Figure 2). To date (March 2008), the US Patent Database records 7237 patents featuring the terms “video compression” or “video coding”.

Figure 2 - Issued US patents including the terms "video coding" or "video compression", 1990-2007

Source: USPTO patent database

3 Video coding standards and patents

Given the number of published patents in the field of video compression, it is likely that an implementation of a video compression system (particular one that uses the popular hybrid model of motion compensated prediction, transform and entropy coding) may fall into the scope of one or more patents. This is a concern for manufacturers of products that incorporate video coding technology, since the grant of a US patent confers “the right to exclude others from making, using, offering for sale, or selling the invention throughout the United States or importing the invention into the United States” (source: USPTO) and similar rights are conferred by patents granted in other jurisdictions. It may therefore be necessary to license the right to use the technology covered by the patent. A complex video coding standard such as H.264/AVC may fall within the scope of a large number of patents held by different parties, raising the prospect of a “patent thicket” in which it is difficult and costly to negotiate licenses to all the necessary patents.

This problem has been addressed in recent video coding standards in a number of ways. First, the standard-setting bodies (e.g. ITU-T) attempt to avoid including IPR (Intellectual Property Rights) in a published standard unless the IPR is licensable on RAND (Reasonable And Non Discriminatory) terms. Second, the group responsible for preparing a draft standard for publication (e.g. the MPEG, VCEG or JVT committees) requests a party proposing technical elements of the draft standard to disclose whether it holds IPR relating to the proposal and whether it is prepared to license this on RAND terms. Third, any party holding IPR believed to be necessary to a published standard is encouraged to declare to the standards-setting body whether it is prepared to license this IPR on RAND terms. The aim is to clarify the IPR position prior to publication of a new standard as far as is possible.

A trend in recent years has been the emergence of “pool” licenses for IPR relating to a published video coding standard. A third party representing the interests of a number of patent holders sets out terms for licensing the right to use the patented technology in implementations of a published standard. This is intended to provide a “one stop shop”, a single license agreement that covers large number of patents claimed to be essential to practicing the standard.

4 Licensing MPEG-2 patents

The popular MPEG-2 Video standard is a key component of many consumer digital video products and systems including broadcast digital television and DVD-Video discs. In common with other video compression standards, the MPEG-2 Video standard describes the syntax of a compressed video bitstream and a method of decoding the bitstream, but does not mandate a particular method of video encoding. Consumer products such as DVD players and digital TV set-top boxes typically contain an MPEG-2 video decoder.

A pool license is administered by MPEG-LA, an organisation entirely independent of the standards setting bodies. MPEG-LA publishes a list of several hundred patents, owned by a total of 25 companies or organisations, that are claimed to be “essential” to implementations of MPEG-2 Video. The definition of “essentiality”, according to MPEG-LA’s website, is “directly documented on MPEG-2 video standard” (sic). Any party can submit patent(s) for evaluation and potential inclusion in the patent pool. A fee is payable to MPEG-LA who arrange evaluation of submitted patent(s) in terms of “essentiality” to MPEG-2 implementations. The decision on essentiality is made by MPEG-LA’s patent counsel. (Source: www.mpegla.com, March 2008).

Examples of patents covered by the pool license and claimed to be essential to MPEG-2 Video include:

• US 4706260 (now expired), “DPCM system with rate-of-fill control of buffer occupancy”, describes a rate buffer and control method to address the problem of highly variable rate of encoded “image-representative signals”.
• US 4864393, “Motion vector estimation in television images”, describes an “apparatus for motion vector estimation” incorporating block matching and a method for determining a sub-pixel offset (i.e. choosing a sub-pixel motion vector).

The terms of the license are published by MPEG-LA. Licensees are expected to pay license fees for video encoders, DVD players and recorders, camcorders, computers, DVD discs, digital TV set top boxes, file servers, multiplexers and intermediate products. It is interesting to note that MPEG-LA claims that all the patents in its “pool” are essential to products such as DVD discs, DVD players and set top boxes, regardless of whether these products include encoding technology, decoding technology or both.

5 Licensing H.264/AVC patents

The H.264 Advanced Video Coding standard is emerging as an important successor to earlier standards such as MPEG-2, with applications such as Blu-Ray Discs, internet TV, etc. As with MPEG-2 Video, the H.264 standard specifies a compressed bitstream syntax and a decoding method, but does not specify an encoding method. H.264 includes a large portfolio of coding “tools” or methods and a typical codec may use only a subset of these tools. For convenience, these tools are organised into Profiles (pre-defined subsets of coding tools).

Initially there were two separate patent pools in operation, one managed by Via Licensing and the other by MPEG-LA, each representing some (but not all) of the organisations claiming to hold patents essential to H.264. Via Licensing later withdrew its “pool” license leaving MPEG-LA to offer a license to its pool of patents. MPEG-LA’s website states that its goal is “to provide worldwide access to as much AVC essential intellectual property as possible”, i.e. it does not claim to include all essential IPR in its license. As with the MPEG-2 license pool, parties may submit patents for evaluation and possible inclusion in the MPEG-LA license pool.

MPEG-LA provides a license to several hundred patents owned by 23 organisations, claimed to be essential to H.264/AVC implementations. Examples of patents claimed to be essential include:

• US 4864393, “Motion vector estimation in television images”,  as above.
• US 6882685, “Block transform and quantization for image and video coding”, describes “an improved.. block transform for image or video encoding or decoding.. such that computational complexity is significantly reduced..”. H.264/AVC makes use of a block transform (a scaled approximate DCT) that may be accurately computed using integer arithmetic.
• US 6900748, “Method and apparatus for binarization and arithmetic coding of a data value”, describes a “binarization” scheme, i.e. a method of mapping data values into a form suitable for binary arithmetic coding. H.264/AVC includes an optional Context Adaptive Binary Arithmetic Coding method for coding data symbols.

Under MPEG-LA’s published terms, license fees are required to be paid by manufacturers of encoders and decoders and by suppliers of H.264 coded content (e.g. discs and other media, pay-per-view and subscription services, broadcasting services). No distinction is made between implementations that use different subsets of H.264 functionality (e.g. decoding only; Profiles that are subsets of the available tools; etc).

6 Video coding patents in the news

Following the January 2007 court battle between Qualcomm and Broadcom in San Diego over Broadcom’s H.264-compliant products, the court ruled in favour of Broadcom and subsequently ordered Qualcomm to pay damages to Broadcom, stating that key documents had been withheld during the case.

Organisations owning patents within the MPEG-2 patent pool recently brought patent enforcement actions  against  a  number  of  companies  including  set-top  box  manufacturers  and  DVD  video disc replicators. Several of these companies have now signed licenses with MPEG-LA and further actions are ongoing.

Further reading

Iain E Richardson, “The H.264 Advanced Video Compression Standard”, John Wiley & Sons, 2010.

About the author

Vcodex is led by Professor Iain Richardson, an internationally known expert on the MPEG and H.264 video compression standards. Based in Delft, The Netherlands, he frequently travels to the US and Europe.

Professor Richardson is the author of “The H.264 Advanced Video Compression Standard”, a widely cited work in the research literature. He has written three further books and over 50 journal and conference papers on image and video compression. He regularly advises companies on video codec technology, video coding patents and mergers/acquisitions in the video coding industry. Professor Richardson leads an internationally renowned image and video coding research team, contributes to the MPEG industry standards group and is sought after as an expert witness and litigation consultant.