Encoding digital video

• US 8,971,414 B2
• Filed: 08/05/2011
• Issued: 03/03/2015
• Est. Priority Date: 10/02/2000
• Status: Active Grant

• Current Assignee: Nordic Interactive Technologies LLC (Tanit Ventures Inc.)
• Original Assignee: Wimaximum LLC (Intellectual Ventures LLC)
• Inventors: Meggers, Jens
• Primary Examiner(s): Rao, Andy
• Application Number:
  US13/204,556
• Publication Number:
  US 20110286529A1
• Time in Patent Office: 1,306 Days
• Field of Search: 37524001-24029
• US Class Current: 375/240.24
• CPC Class Codes: H04N 19/107 between spatial and temporal predictive coding, e.g. picture refresh
• CPC Class Codes: H04N 19/119 Adaptive subdivision aspects, e.g. subdivision of a picture into rectangular or non-rectangular coding blocks
• CPC Class Codes: H04N 19/137 Motion inside a coding unit, e.g. average field, frame or block difference
• CPC Class Codes: H04N 19/15 by monitoring actual compressed data size at the memory before deciding storage at the transmission buffer
• CPC Class Codes: H04N 19/172 the region being a picture, frame or field
• CPC Class Codes: H04N 19/192 the adaptation method, adaptation tool or adaptation type being iterative or recursive
• CPC Class Codes: H04N 19/46 Embedding additional information in the video signal during the compression process H04N19/517, H04N19/68, H04N19/70 take precedence
• CPC Class Codes: H04N 19/507 using conditional replenishment
• CPC Class Codes: H04N 19/85 using pre-processing or post-processing specially adapted for video compression

Abstract

A video encoder encodes the video stream frame by frame. An encoding process generally includes receiving a video frame, subdividing the video frame into uniform pixel blocks, comparing a selected pixel block with the corresponding pixel block in a previous decoded video frame to determine which blocks have changed, copying changed pixel blocks into a contiguous memory block, and adding a preamble block, compressing the blocks. This process may be repeated for each frame using a different size pixel block to determine and select a pixel block size that results in the smallest encoded frame.

Claims

1. An apparatus, comprising:

an encoder configured to;

divide a video frame into blocks according to an approximately uniform block size;

identify a changed block by comparing a block of the video frame to a corresponding block in a decoded version of a previous video frame;

copy the changed block into a contiguous block of memory; and

associate a preamble block with the changed block, the preamble block identifying the changed block.

2. The apparatus of claim 1, wherein the preamble block indicates that the changed block is included in the contiguous block of memory.

3. The apparatus of claim 1, wherein the preamble block indicates the approximately uniform block size.

4. The apparatus of claim 1, wherein the encoder is further configured to determine a luminance difference between one or more blocks of the video frame and one or more blocks of the previous video frame.

5. The apparatus of claim 4, wherein the luminance difference is associated with a threshold value.

6. The apparatus of claim 1, wherein the encoder is further configured to compress the contiguous block of memory using an LZW-like compression algorithm.

7. The apparatus of claim 1, wherein the encoder is further configured to compress the contiguous block of memory using an LZW-like compression algorithm, wherein the compression algorithm used is zLIB.

8. The apparatus of claim 1, wherein the encoder is further configured to compress the contiguous block of memory using an LZW-like compression algorithm, wherein the compression algorithm used is LZO.

9. The apparatus of claim 1, further comprising:

a decoder configured to;

receive an encoded video frame encoded using multiple block size detection;

decompress the encoded video frame;

determine a block size that was used to encode the encoded video frame;

determine a block that is present in the encoded video frame; and

associate the block that is present in the encoded video frame with a display area.

10. The apparatus of claim 9, wherein the encoded video frame is part of a sequence of frames and wherein one or more key frames are utilized to decode the sequence of frames starting at a location other than a beginning of the sequence of frames.

11. The apparatus of claim 9, wherein the encoded video frame is part of a sequence of frames and wherein one or more key frames are utilized to decode the sequence of frames starting at a location other than a beginning of the sequence of frames, the one or more key frames being utilized to seek forward and backward within the sequence of frames.

12. The apparatus of claim 9, wherein the encoder is further configured to:

divide a second video frame into a first plurality of blocks of a first size and a second plurality of blocks of a second size;

identify a first block of the first plurality of blocks and a second block of the second plurality of blocks that differ by at least a minimum extent from corresponding blocks in a preceding video frame; and

determine that either the first plurality of blocks of the first size or the second plurality of blocks of the second size can be used to produce a smaller encoded frame.

13. The apparatus of claim 12, wherein the encoder is further configured to encode the video frame using one or more of the blocks of the first size or one or more of the blocks of the second size.

14. The apparatus of claim 13, wherein the determining utilizes the encoded video frame.

15. The apparatus of claim 12, wherein the video frame and the preceding video frame are part of a video stream and wherein one or more of multiple frames of the video stream are utilized to generate an encoded video stream in which different video frames are encoded using different block sizes.

16. A method comprising:

dividing, by a computing device, a video frame into a first plurality of blocks of a first block size and a second plurality of blocks of a second block size;

comparing, by the computing device, a first block of the first plurality of blocks to a first corresponding block of a preceding video frame and a second block of the second plurality of blocks to a second corresponding block of the preceding video frame;

determining, by the computing device, whether the first block has changed more than a minimum amount as compared to the first corresponding block of the preceding video frame and whether the second block has changed more than the minimum amount as compared to the second corresponding block of the preceding video frame;

storing, by the computing device, the first block in response to the first block changing more than the minimum amount and the second block in response to the second block changing more than the minimum amount;

determining, by the computing device, that either the first plurality of blocks or the second plurality of blocks are capable of producing a compression block size that results in a smaller encoded video frame; and

encoding, by the computing device, the video frame as part of a video stream using the compression block size.

17. The method of claim 16, further comprising encoding multiple different frames of the video stream using different block sizes.

18. The method of claim 16, further comprising:

discarding, by the computing device, the first block in response to the first block changing less than the minimum amount and the second block in response to the second block changing less than the minimum amount.

19. A computer-implemented method, comprising:

dividing, by a computer, a first video frame and a second video frame into a plurality of blocks;

identifying, by the computer, a changed block associated with the first video frame by comparing a first block associated with the first video frame with a second block associated with the second video frame;

combining, by the computer, the changed block associated with the first video frame with an unchanged block associated with the first video frame responsive to a determination that the first video frame is a key frame; and

compressing, by the computer, the changed block associated with the first video frame with the unchanged block associated with the first video frame to generate a compressed video frame.

20. The method of claim 19, further comprising associating a preamble block with the compressed video frame, the preamble block identifying the changed block associated with the first video frame and the unchanged block associated with the first video frame included in the compressed video frame.