Run-level video encoding - Copied from Open Source Logs (Tandberg) - Patent Application - PRIOR ART REQUEST

Question

AN OVERBROAD PATENT ON run-level encoding for video - This application from Cisco seeks to patent work that was previously published as open-source software! 10 minutes of your time can help narrow US patent applications before they become patents. Follow @askpatents on twitter to help.

I believe there is good prior art for this patent. Now the applicant is trying to patent the same idea in the US!

Quantized transform coefficients representing pixel values in a Video

Controversy is explained in full here:

• Wikipedia Article

• x264.nl

QUESTION - Have you seen anything that was published before 12/30/2008 that discusses: Run-level coders for video

From x264.nl: A run-level coder is a function that takes an array of values and calculates the distances between nonzero values (runs) in the array, as well as the indices of the nonzero values (levels). This is necessary for practically any video format that makes use of run-level compression (H.264, MPEG-2, Theora, etc). Here's one of x264's unoptimized run-level coders.

This function is run often enough that high performance is very important. Naively, there is no obvious way to make use of SIMD in such an algorithm, so some trickery has to be used to write a fast assembly function for it. Near the end of 2008, I added optimized assembly implementations of two run-length coders (for block decimation and CAVLC) to x264.

So why the deja vu? Because this patent application was an exact, step-by-step description of the algorithm I came up with for decimate_score (and later coeff_level_run) in x264 in 2008!

• Publication Number: US 20100166076 A1
• Application Number: US 12/649,764
• Assignee: Tandberg Telecom (now Cisco)
• Prior Art Date: Seeking prior Art predating 12/30/2008
• Link to Google Prior Art Search - "Find Prior Art"

Claim 1 requires each and every step below:

A method for calculating run and level representations of quantized transform coefficients representing pixel values included in a block of a video picture, the method comprising:

1. Packing, at a video processing apparatus, each quantized transform coefficients in a value interval [Max, Min] by setting all quantized transform coefficients greater than Max equal to Max, and all quantized transform coefficients less than Min equal to Min;

2. Reordering, at the video processing apparatus, the quantized transform coefficients according to a predefined order depending on respective positions in the block resulting in an array C of reordered quantized transform coefficients;

3. Masking, at the video processing apparatus, C by generating an array M containing ones in positions corresponding to positions of C having non-zero values, and zeros in positions corresponding to positions of C having zero values;

4. Generating, at the video processing apparatus, for each position containing a one in M, a run and a level representation by setting the level value equal to an occurring value in a corresponding position of C; and

5. Setting, at the video processing apparatus, for each position containing a one in M, the run value equal to the number of proceeding positions relative to a current position in M since a previous occurrence of one in M.

Answer 1

So this is a trivial combination of a zero-run-length encoder with a quantiser. That somebody thinks this is worthy of patenting beggars belief.

In any case, the same technique is used in the JPEG/JFIF format, which counts as a video codec because many cameras (prior to the introduction of cheap realtime MPEG4 encoders) used Motion JPEG for video recording, leveraging their existing JPEG acceleration hardware. Motion JPEG simply encodes each frame of the video as a separate JPEG image.

The steps for encoding JPEG are essentially similar to the claim here:

0) The source pixel data is transformed into a series of coefficients (DCT).

1) The coefficients are quantised, effectively reducing their range of possible values.

2) These coefficients are reordered using a specific "zigzag" pattern. It would be natural to have an array describing the required order, but optimised code would probably be unrolled to express it directly using loads and stores to specific indices. This "fastcoding" technique is widely used when performance is critical.

3) The resulting reordered series of quantised coefficients typically contains long runs of zeroes. These are encoded using RLE.

4) The remaining, nonzero coefficients are encoded individually using a Huffman scheme (in most implementations) or with arithmetic coding (rarely, due to - yes - patent concerns).

The JPEG standard was published at least by September 1992 as an ITU Recommendation. It was ratified as a formal ISO standard two years later. Additionally, it is my understanding that all MPEG-family video codecs ultimately trace their heritage back to JPEG, especially the basic DCT-quantisation scheme described here.

The only step in the claim but not in the above is the creation of a mask to identify the zero and non-zero coefficients. This appears to have been introduced as part of an optimisation. It's not immediately obvious to me how this code works or why it is supposed to be faster than examining the elements individually, but my grasp of x86 SIMD assembly is hazy at best - all I can gather so far is that the 2008 x264 code makes a mask involving four coefficients at a time, and then does something complicated with it.

Answer 2

Not exactly what you were looking for, but if Animated GIF counts as video encoding, then GNU plotutils had a weird bastardised version of GIF that used RLE instead of LZW in 1998. The original Compuserve work on creating GIF was to replace an RLE based graphics format. LZW was used in GIF instead of RLE because it was considered a more efficient upgrade, but RLE was certainly known to the creators of GIF, and would have been a fairly obvious choice if LZW hadn't been available. (Obvious in the real world definition, anyway. Possibly not obvious in the legal sense.)

https://www.gnu.org/software/plotutils/manual/en/html_node/History-and-Acknowledgements.html#History-and-Acknowledgements