Vector quantization video encoder using hierarchical cache memory scheme

• US 5,444,489 A
• Filed: 02/11/1993
• Issued: 08/22/1995
• Est. Priority Date: 02/11/1993
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Georgia Tech Research Corporation (University System of Georgia)
• Inventors: Mersereau, Russell M., Truong, Kwan K.
• Primary Examiner(s): Chin, Tommy P.
• Assistant Examiner(s): Le, Vu
• Application Number:
  US08/016,813
• Time in Patent Office: 922 Days
• Field of Search: 348/417, 348/418, 348/699, 348/411-412, 348/408, 348/416, 348/414, 348/422, 348/700
• US Class Current: 375/240.22
• CPC Class Codes: G06F 12/0875 with dedicated cache, e.g. instruction or stack
• CPC Class Codes: G06T 9/008 Vector quantisation
• CPC Class Codes: H04N 19/503 involving temporal prediction adaptive coding with adaptive selection between spatial and temporal predictive coding H04N19/107; adaptive coding with adaptive selection among a plurality of temporal predictive coding modes H04N19/109
• CPC Class Codes: H04N 19/51 Motion estimation or motion compensation
• CPC Class Codes: H04N 19/94 Vector quantisation
• CPC Class Codes: H04N 19/96 Tree coding, e.g. quad-tree coding

Abstract

A system compresses image blocks via successive hierarchical stages and motion encoders which employ caches updated by stack replacement algorithms. Initially, a background detector compares the present image block with a corresponding previously encoded image block and if similar, the background detector terminates the encoding procedure by setting a flag bit. Otherwise, the image block is decomposed into smaller present image subblocks. The smaller present image subblocks are each compared with a corresponding previously encoded image subblock of comparable size within the present image block. When a present image subblock is similar to a corresponding previously encoded image subblock, then the procedure is terminated by setting a flag bit. Alternatively, the present image subblock is forwarded to a motion encoder where it is compared with displaced image subblocks, which are formed by displacing previously encoded image subblocks by motion vectors that are stored in a cache, to derive a first distortion vector. When the first distortion vector is below a first threshold T_M, the procedure is terminated and the present image subblock is encoded by setting flag bit and a cache index corresponding to the first distortion vector. Alternatively, the present image subblock is passed to a block matching encoder where it is compared with other previously encoded image subblocks to derive a second distortion vector. When the second distortion vector is below a second threshold T_m, the procedure is terminated by setting a flag bit, by generating the second distortion vector, and by updating the cache.

Claims

1. A method for efficiently compressing source image blocks from a source image, comprising the steps of:

(a) storing cache image blocks as cache code vectors in a cache memory;

(b) performing a comparison between a source image block and a cache code vector;

(c) if said source image block matches said code vector, identifying a cache index which corresponds to said matched code vector and which is smaller in data size than said matched source image block;

(d) using said cache index to encode said code vector by communicating said cache index as a representation of said code vector so that said source image block is effectively compressed to said cache index; and

(e) updating said cache memory based upon a cache stack replacement algorithm and said comparison by the following steps;

(1) when said source image block matches said code vector, reordering said cache code vectors; and

(2) when said source image block fails to match said code vector, generating a new code vector corresponding to said source image block and adding said new code vector to said cache memory.

2. The method of claim 1, further comprising the step of updating said cache memory using a working set model having a causal search window with a selectable size.

3. The method of claim 1, wherein the cache stack replacement algorithm used to update the cache memory in said step (e) is a least-recently-used LRU) stack replacement algorithm.

4. The method of claim 1, wherein the cache stack replacement algorithm used to update the cache memory in said step (e) is a least-frequently-used (LFU) stack replacement algorithm.

5. The method of claim 1, wherein the cache stack replacement algorithm used to update the cache memory in said step (e) is a first-in-first-out (FIFO) stack replacement algorithm.

6. A hierarchical encoding method for efficiently compressing image blocks from an image, comprising the steps of:

(1) comparing a present image block with a corresponding previously encoded image block and if the present image block is substantially similar to said corresponding previously encoded image block, terminating the hierarchical encoding method for said present image block by setting a first flag, or else, continuing to step (2);

(2) decomposing said present image block into smaller present image subblocks;

(3) comparing a present image subblock with a corresponding previously encoded image subblock of comparable size and if said present image subblock is substantially similar to said corresponding previously encoded image subblock, encoding said present image subblock by setting a second flag, or else, continuing to step (4);

(4) comparing said present image subblock with displaced image subblocks, which are formed by displacing previously encoded subblocks by motion vectors stored in a cache memory, to derive a first minimum distortion motion vector, and if said first minimum distortion motion vector is below a first predetermined threshold, encoding said present image subblock by setting a third flag and by generating a cache index corresponding to said first minimum distortion vector and said present image subblock, or else, continuing to step (5);

(5) comparing said present image subblock with said previously encoded image subblocks of comparable size to derive a second minimum distortion motion vector, and if said second minimum distortion motion vector is below a second predetermined threshold, encoding said present image subblock by setting a fourth flag, and updating said cache memory, or else, continuing to step (6); and

(6) encoding said present image subblock using a block encoding technique.

7. The method of claim 6, wherein said block encoding technique uses vector quantization.

8. The method of claim 7, wherein said vector quantization uses a second cache memory which is updated by a stack replacement algorithm.

9. The method of claim 7, further comprising the step of updating said second cache memory using a stack replacement algorithm.

10. The method of claim 7, further comprising the step of updating said second cache memory with another codebook.

11. The method of claim 7, further comprising the step of indexing said image blocks of said image via a localized scanning technique.

12. The method of claim 6, further comprising the steps of:

after step (4), decomposing said present image subblock into smaller present image subblocks; and

repeating steps (4) and (5) on a subblock of said smaller present image subblocks.

13. The method of claim 6, further comprising the step of updating said cache memory using a least-recently-used (LRU) stack replacement algorithm.

14. The method of claim 6, further comprising the step of updating said cache memory using a least-frequently-used (LFU) stack replacement algorithm.

15. The method of claim 6, further comprising the step of updating said cache memory using a first-in-first-out (FIFO) stack replacement algorithm.

16. The method of claim 6, wherein step (2) uses a quadtree decomposition technique.

17. The method of claim 6, wherein step (5) uses a full search technique wherein substantially all of said smaller subblocks within said present image block are compared with said subblock to derive said second minimum distortion motion vector.

18. The method of claim 6, wherein step (5) uses a log search technique for comparing said subblock to said smaller subblocks to derive said second minimum distortion motion vector.

19. The method of claim 6, wherein said block encoding technique uses transform encoding.

20. The method of claim 6, wherein said block encoding technique uses subband encoding.

21. The method of claim 6, further comprising the step of updating said cache memory using a stack replacement algorithm.

22. The method of claim 6, further comprising the step of updating said cache memory using a working set model having a causal search window with a selectable size.

23. An encoding system for compressing motion vectors which represent displacements of image blocks, comprising:

a cache memory for storing motion vectors with corresponding cache indices;

means for performing comparisons between a present image block and previously encoded image blocks of comparable size and for identifying a motion vector representative of a displacement of said present image block from a previously encoded image block, said means for comparing said motion vector with one of said motion vectors in said cache memory, said means for identifying a cache index representative of said motion vector if said motion vector matches said one of said motion vectors, said cache index being smaller in data size than said motion vector so that said motion vector is effectively compressed to said cache index; and

a stack replacement means for updating said cache memory based upon said comparisons, said stack replacement means for;

(1) when said motion vector matches said one of said motion vectors, reordering said motion vectors within said cache memory; and

(2) when said motion vector fails to match said one of said motion vectors, generating a new motion vector corresponding to said present image block and adding said new motion vector to said cache memory.

24. The system of claim 23, further comprising a means for updating said cache memory using a working set model having a causal search window with a modifiable size.

25. The system of claim 23, wherein said stack replacement means performs a least-recently-used (LRU) method to update said cache memory.

26. The system of claim 23, wherein said stack replacement means performs a least-frequently-used (LFU) stack replacement algorithm to update said cache memory.

27. The system of claim 23, wherein said stack replacement means performs a first-in-first-out (FIFO) stack replacement algorithm to update said cache memory.

28. The system of claim 23, wherein image blocks of said image are indexed via a localized scanning method.

29. A hierarchical encoding system for efficiently compressing image blocks from an image by performing a hierarchical encoding method, comprising:

(1) first means for comparing a present image block with a corresponding previously encoded image block and if the present image block is substantially similar to said corresponding previously encoded image block, encoding said present image block by setting a first flag, or else, continuing to step (2);

(2) second means for decomposing said present image block into smaller present image subblocks;

(3) third means for comparing a present image subblock with a corresponding previously encoded image subblock of comparable size and if said present image subblock is substantially similar to said corresponding previously encoded image subblock, encoding said present image subblock by setting a second flag, or else, continuing to step (4);

(4) fourth means for comparing said present image subblock with displaced image subblocks formed by displacing said previously encoded subblocks by motion vectors stored in a cache memory to derive a minimum distortion motion vector, and if said minimum distortion vector is below a first predetermined threshold, encoding said present image subblock by setting a third flag and generating a cache index corresponding to said present image subblock, or else, continuing to step (5);

(5) fifth means for comparing said present image subblock with said previously encoded image subblocks of comparable size to derive a second minimum distortion motion vector, and if said second minimum distortion vector is below a second predetermined threshold, encoding said present image subblock by setting a fourth flag and updating said cache memory, or else, continuing to step (6); and

(6) sixth means for encoding said present image subblock using a block encoding technique.

30. The system of claim 29, wherein said block encoding technique uses vector quantization.

31. The system of claim 30, wherein said vector quantization uses a second cache memory which is updated by a stack replacement algorithm.

32. The system of claim 29, further comprising a least-recently-used (LRU) stack replacement algorithm for updating said cache memory.

33. The system of claim 29, further comprising a least-frequently-used (LFU) stack replacement algorithm for updating said cache memory.

34. The system of claim 29, further comprising a first-in-first-out (FIFO) stack replacement algorithm for updating said cache memory.

35. The system of claim 29, wherein second means uses a quadtree decomposition technique.

36. The system of claim 29, wherein said fifth means further comprises a full search means for performing a full search technique wherein substantially all of said smaller subblocks within said present image block are compared with said subblock to derive said second minimum distortion motion vector.

37. The system of claim 29, wherein said fifth means further comprises a log search means for performing a log search when comparing said subblock to said smaller subblocks to derive said second minimum distortion motion vector.

38. The system of claim 29, further comprising a means for updating said cache memory using a working set model having a causal search window with a selectable size.

39. The system of claim 29, further comprising a means for entropy encoding said cache index.

40. The system of claim 29, wherein said block encoding technique uses transform encoding.

41. The system of claim 29, wherein said block encoding technique uses subband encoding.

42. A method for compressing image blocks from an image, comprising the steps of:

decomposing a present image block into smaller present image subblocks;

comparing a present image subblock with a corresponding previously encoded image block of comparable size and when said present image subblock is substantially similar to said previously encoded image subblock, representing said present image subblock with a first flag;

comparing said present image subblock with a displaced image subblock formed by displacing a previously encoded subblock by a motion vector stored in a cache memory to derive a first minimum distortion motion vector, and when said first minimum distortion motion vector is below a first predetermined threshold, generating a second flag and a cache index corresponding to said first minimum distortion vector and representative of said present image subblock; and

comparing said present image subblock with said previously encoded image subblocks of comparable size to derive a second minimum distortion motion vector, and when said second minimum distortion motion vector is below a second predetermined threshold, representing said present image subblock by a third flag.

43. A method for compressing data using a cache memory with a stack replacement mechanism, comprising the steps of:

storing motion vectors in a cache memory with corresponding cache indices;

matching a present image block with a previously encoded image block and identifying a motion vector indicative of a displacement between said present image block and said previously encoded image block;

comparing said motion vector with one of said motion vectors in said cache memory and, if said motion vector matches said one of said motion vectors, identifying a cache index representative of said matched motion vector, said cache index being smaller in data size than said matched motion vector;

communicating said cache index as a representation for said present image block so that said present image block is compressed to said cache index; and

updating said cache memory with a stack replacement algorithm, said stack replacement algorithm comprising the following steps;

(1) when said motion vector matches said one of said motion vectors, reordering said motion vectors within said cache memory; and

(2) when said motion vector fails to match said one of said motion vectors, generating a new motion vector corresponding to said present image block and adding said new motion vector to said cache memory.

44. A system for compressing image blocks from an image, comprising:

means for comparing a present image block with a previously encoded image block and when said present image block is similar to said previously encoded image block, producing a flag indicative thereof;

means for comparing said present image block with displaced image blocks, which are formed by displacing previously encoded image blocks by motion vectors stored in a cache memory, to derive a minimum distortion motion vector, and when said minimum distortion motion vector is below a predetermined threshold, producing a cache index corresponding to said minimum distortion vector and said present image block; and

wherein said flag and said cache index are smaller in data size than said present image block so that said present image block is compressed when said flag and when said cache index are produced as representative of said present image block.

45. A system for compressing image blocks from an image, comprising:

means for decomposing a present image block into smaller present image subblocks;

means for comparing a present image subblock with a corresponding previously encoded image block of comparable size, and when said present image subblock is substantially similar to said corresponding previously encoded image subblock, representing said present image subblock with a first flag;

means for comparing said present image subblock with displaced image subblocks, which are formed by displacing previously encoded image blocks by motion vectors stored in a cache memory, to derive a first minimum distortion motion vector, and when said first minimum distortion motion vector is below a first predetermined threshold, representing said present image subblock by a cache index corresponding to said first minimum distortion vector and generating a second flag indicative thereof;

means for comparing said present image subblock with said previously encoded image subblocks of comparable size to derive a second minimum distortion motion vector, and when said second minimum distortion motion vector is below a second predetermined threshold, representing said present image subblock by a third flag; and

wherein said flags and said cache index are smaller in data size than said present image block so that said present image block is compressed when said flags and when said cache index are produced as representative of said present image block.

46. A system for compressing a source image block from a source image using a cache which is updated with a cache stack replacement technique, comprising:

(a) means for storing cache image blocks in a cache memory;

(b) means for comparing said source image block with a cache image block;

(c) means for compressing said source image block when said source image block matches said cache image block by representing said source image block with a cache index corresponding to said cache image block, said cache index being smaller in data size than said source image block so that said source image block is compressed to said cache index when said source image block is represented by said cache index; and

means for updating said cache memory by;

(1) when said source image block matches said cache image block, reordering said cache image blocks; and

(2) when said source image block fails to match said cache image block, generating a new cache image block corresponding to said source image block and adding said new cache image block to said cache memory.