Encoding digital video

• US 8,295,358 B1
• Filed: 07/25/2005
• Issued: 10/23/2012
• 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:
  US11/190,108
• Time in Patent Office: 2,647 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:

means for receiving a video frame of a video stream;

means for subdividing the video frame into blocks of a first block size;

means for subdividing the video frame into blocks of a second block size;

means for comparing the blocks of the first block size and the blocks of the second block size to corresponding blocks of a decoded version of a preceding video frame to determine whether any of the blocks of the first block size or the blocks of the second block size have not changed more than a minimum amount as compared to the corresponding blocks of the decoded version of the preceding video frame;

means for discarding the blocks of the first block size and the blocks of the second block size that have not changed more than the minimum amount;

means for determining that either the blocks of the first block size or the blocks of the second block size correspond to a compression block size that is capable of producing a smaller encoded video frame; and

means for encoding the video frame of the video stream using the compression block size.

2. The apparatus of claim 1, wherein the means for encoding the video frame is configured to encode multiple video frames of the video stream using different block sizes.

3. An apparatus, comprising:

means for determining which block size of multiple block sizes produces a smaller encoded frame, wherein the multiple block sizes are used to subdivide and compare a first video frame and a second video frame of a video stream to determine whether any blocks of the first video frame are sufficiently unchanged to be discarded;

means for compressing the first video frame using the block size of the multiple block sizes determined to produce the smaller encoded frame; and

means for storing a compressed video frame in conjunction with an indication of the block size used to compress the first video frame.

4. An apparatus, comprising:

means for dividing a video frame into blocks according to an approximately uniform block size;

means for identifying changed blocks by comparing each of the blocks to each of respective corresponding blocks in a decoded version of a previous video frame;

means for copying the changed blocks into a contiguous block of memory; and

means for associating a preamble block with the changed blocks, the preamble block identifying the changed blocks.

5. The apparatus of claim 4, wherein the preamble block indicates that the changed blocks are included in the contiguous block of memory.

6. The apparatus of claim 4, wherein the preamble block indicates the approximately uniform block size.

7. The apparatus of claim 4, wherein said the means for identifying is 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.

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

9. The apparatus of claim 4, further comprising means for compressing the contiguous block of memory using an LZW-like compression algorithm.

10. The apparatus of claim 4, further comprising means for compressing the contiguous block of memory using an LZW-like compression algorithm, wherein the compression algorithm used is zLIB.

11. The apparatus of claim 4, further comprising means for compressing the contiguous block of memory using an LZW-like compression algorithm, wherein the compression algorithm used is LZO.

12. An apparatus comprising:

means for receiving an encoded video frame encoded using multiple block size detection;

means for decompressing the encoded video frame;

means for determining a block size that was used to encode the encoded video frame;

means for determining blocks that are present in the encoded video frame; and

means for associating the blocks that are present in the encoded video frame with a display area.

13. The apparatus of claim 12, 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.

14. The apparatus of claim 12, 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.

15. An apparatus comprising:

means for dividing a video frame into blocks of a first size;

means for dividing the video frame into blocks of a second size;

means for identifying the blocks of the first size and the blocks of the second size that differ by at least a minimum extent from corresponding blocks in a preceding video frame; and

means for determining that either the blocks of the first size or the blocks of the second size can be used to produce a smaller encoded frame.

16. The apparatus of claim 15, further comprising means for encoding the video frame using one or more of the blocks of the first size or the blocks of the second size.

17. The apparatus of claim 16, wherein the means for determining utilizes an output of said the means for encoding.

18. The apparatus of claim 17, 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.

19. A method comprising:

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

dividing, by the computing device, the video frame into blocks of a second block size;

comparing, by the computing device, the blocks of the first block size and the blocks of the second block size to corresponding blocks of a preceding video frame to determine whether any of the blocks of the first block size or the blocks of the second block size have not changed more than a minimum amount as compared to the corresponding blocks of the preceding video frame;

discarding, by the computing device, the blocks of the first block size and the blocks of the second block size that have not changed more than the minimum amount;

determining, by the computing device, that either the blocks of the first block size or the blocks of the second block size 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.

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

21. A method comprising:

determining, by a computing device, which of multiple different block sizes produces a smaller encoded video frame for encoding a video frame, wherein the multiple different block sizes are used to compare the video frame to a preceding video frame to determine whether one or more blocks of the video frame are sufficiently unchanged with respect to the preceding video frame to be discarded; and

compressing, by the computing device, the video frame to produce a compressed video frame using at least in part a block size determined to produce the smaller encoded video frame.

22. The method of claim 21, further comprising storing the compressed video frame and an indication of the block size determined to produce the smaller encoded video frame.

23. A method comprising:

dividing, by a computing device, a video frame into multiple blocks of an approximately uniform block size;

identifying, by the computing device, one or more changed blocks of the multiple blocks by comparing one or more of the multiple blocks to one or more corresponding blocks of a previous video frame; and

associating, by the computing device, a preamble block with the one or more changed blocks, the preamble block identifying the one or more changed blocks.

24. The method of claim 23, wherein the preamble block indicates a block size used to encode the video frame.

25. The method of claim 23, wherein the identifying the one or more changed blocks of the multiple blocks comprises determining a luminance difference between the one or more of the multiple blocks and the one or more corresponding blocks of the previous video frame.

26. The method of claim 25, wherein the luminance difference comprises a predefined threshold value.

27. The method of claim 23, further comprising encoding the one or more changed blocks using LZW-type compression.

28. The method of claim 23, further comprising encoding the one or more changed blocks using a zLIB-type process.

29. The method of claim 23, further comprising encoding the one or more changed blocks using an LZO-type process.

30. A method comprising:

encoding, by a computing device, a video stream using video frames of multiple block sizes; and

associating, by the computing device, a preamble block with the video stream, the preamble block including one or more of bitmaps of the video frames or an indication of one or more of the multiple block sizes.

31. The method of claim 30, wherein the encoding the video stream comprises determining that at least one of the multiple block sizes produces a smaller encoded frame for one or more of the video frames.

32. A method comprising:

decompressing, by a computing device, a compressed video frame to produce a decompressed video frame;

reading, by the computing device, a preamble block included in the decompressed video frame to determine a block size used to generate the compressed video frame and to determine pixel blocks associated with the decompressed video frame; and

assembling, by the computing device, a displayable video frame based on the block size and using the pixel blocks.

33. The method of claim 32, wherein the compressed video frame is part of a sequence of video frames that includes a key frame and wherein the key frame is configured to enable the sequence of video frames to be decoded starting at a location other than a beginning of the sequence of video frames.

34. The method of claim 32, wherein the compressed video frame is part of a sequence of video frames, the method further comprising assembling the displayable video frame by utilizing one or more other pixel blocks included in a key frame of the sequence of video frames.

35. A computer-implemented method, comprising:

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

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

combining, by the computer, the changed blocks associated with the first video frame with unchanged blocks 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 blocks associated with the first video frame with the unchanged blocks associated with the first video frame to generate a compressed video frame.

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

37. The method of claim 35, wherein the second video frame precedes the first video frame in a video stream.

38. The method of claim 35, wherein the second video frame occurs after the first video frame in a video stream.