Hash-based block matching in video and image coding

• US 10,264,290 B2
• Filed: 10/25/2013
• Issued: 04/16/2019
• Est. Priority Date: 10/25/2013
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Xu, Jizheng, Zhu, Weijia
• Primary Examiner(s): Perungavoor, Sathyanaraya V
• Assistant Examiner(s): Dang, Philip P.
• Application Number:
  US15/024,812
• Publication Number:
  US 20160234530A1
• Time in Patent Office: 1,999 Days
• CPC Class Codes: H04N 19/147 according to rate distortion criteria rate-distortion as a criterion for motion estimation H04N19/567
• CPC Class Codes: H04N 19/176 the region being a block, e.g. a macroblock
• 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/52 by predictive encoding
• CPC Class Codes: H04N 19/593 involving spatial prediction techniques
• CPC Class Codes: H04N 19/70 characterised by syntax aspects related to video coding, e.g. related to compression standards
• CPC Class Codes: H04N 19/94 Vector quantisation

Abstract

Innovations in hash-based block matching facilitate block copy (“BC”) prediction that is more effective in terms of rate-distortion performance and/or computational efficiency of encoding. For example, some of the innovations relate to encoding that uses hash-based block matching during block vector (“By”) estimation. Other innovations relate to data structures that organize candidate blocks for hash-based block matching. Still other innovations relate to hierarchical hash-based block matching.

Claims

1. A computing device comprising one or more processing units and memory, wherein the computing device implements an encoder of video or images, the encoder being configured to perform operations comprising:

encoding data for a current block of a picture using hierarchical hash-based block matching with multiple stages, including;

determining a first hash value for the current block using a first hash function;

determining a second hash value for the current block using a second hash function different than the first hash function;

identifying a matching block among multiple candidate blocks based at least in part on the first hash value for the current block and the second hash value for the current block, including using the first hash value for the current block to select a candidate block list in a data structure that organizes hash values for the multiple candidate blocks, thereby eliminating at least one of the multiple candidate blocks in one of the multiple stages of the hierarchical hash-based block matching, and, based at least in part on the second hash value for the current block, determining the matching block among any candidate blocks in the selected candidate block list, thereby eliminating at least one of the multiple candidate blocks in a next stage of the multiple stages of the hierarchical hash-based block matching; and

identifying a block vector value for the matching block, the block vector value indicating a displacement to a region of sample values used for block copy prediction; and

outputting the encoded data, wherein the encoded data includes the block vector value.

2. The computing device of claim 1 wherein the encoding for the current block further comprises encoding the block vector value and performing the block copy prediction for the current block using the block vector value.

3. The computing device of claim 1 wherein the first hash function is one of a cyclic redundancy check function, a hash function that includes averaging and XOR operations, and a locality-sensitive hash function.

4. The computing device of claim 1 wherein the picture that includes the current block also includes the multiple candidate blocks, and wherein, for the block copy prediction, the encoding data for the current block uses intra block copy prediction.

5. The computing device of claim 1 wherein another picture includes at least some of the multiple candidate blocks, and wherein the block copy prediction references the other picture.

6. The computing device of claim 1 wherein the encoding data for the current block includes, for each of one or more of the multiple candidate blocks in the selected candidate block list, comparing the second hash value for the current block to a second hash value for the candidate block.

7. The computing device of claim 1 wherein the operations further comprise updating the data structure to account for new candidate blocks that overlap the current block, including, for each of the new candidate blocks:

determining a first hash value and a second hash value for the new candidate block;

evaluating whether the new candidate block is identical to any candidate block already represented in the data structure;

if so, keeping the new candidate block or the identical block in the data structure; and

if not, adding the new candidate block to the data structure.

8. The computing device of claim 1 wherein, for each of the multiple candidate blocks, a first hash value and a second hash value for the candidate block are determined from input sample values of a picture that includes the candidate block, and wherein the first hash value and the second hash value for the current block are determined from input sample values of the current block.

20. The computing device of claim 1 wherein the data structure includes one or more candidate block lists indexed according to first hash value from the first hash function, and wherein each of the one or more candidate block lists includes (a) one or more candidate block lists indexed according to second hash value from the second hash function or (b) for each of one or more of the multiple candidate blocks, a second hash value from the second hash function for the candidate block.

9. In a computing device with a video encoder or image encoder, a method comprising:

creating a data structure that organizes multiple candidate blocks, each of the multiple candidate blocks having a first hash value from a first hash function and a second hash value from a second hash function different than the first hash function;

encoding data for a current block of a picture, including using the data structure in hierarchical hash-based block matching for block vector estimation by eliminating, in each of multiple stages, at least one of the multiple candidate blocks, the block vector estimation identifying a block vector value that indicates a displacement to a region of sample values used for block copy prediction, wherein the encoding the data for the current block includes;

determining a first hash value for the current block using the first hash function;

determining a second hash value for the current block using the second hash function;

using the first hash value for the current block to select a candidate block list in the data structure; and

based at least in part on the second hash value for the current block, determining a matching block among any candidate blocks in the selected candidate block list; and

outputting the encoded data for the picture.

10. The method of claim 9 further comprising updating the data structure to account for new candidate blocks that overlap the current block, including, for each of the new candidate blocks:

determining a first hash value and a second hash value for the new candidate block;

evaluating whether the new candidate block is identical to any candidate block already represented in the data structure;

if so, keeping the new candidate block or the identical block in the data structure; and

if not, adding the new candidate block to the data structure.

11. The method of claim 9 wherein the picture that includes the current block also includes the multiple candidate blocks, and wherein, for the block copy prediction, the encoding data for the current block uses intra block copy prediction.

17. The method of claim 9 wherein the first hash function is one of a cyclic redundancy check function, a hash function that includes averaging and XOR operations, and a locality-sensitive hash function.

18. The method of claim 9 wherein the data structure includes one or more candidate block lists indexed according to first hash value from the first hash function, wherein each of the one or more candidate block lists includes (a) one or more candidate block lists indexed according to second hash value from the second hash function or (b) for each of one or more of the multiple candidate blocks, a second hash value from the second hash function for the candidate block.

12. One or more computer-readable memory or storage devices storing computer-executable instructions for causing a computing device, when programmed thereby, to perform operations comprising:

encoding data for a current block of a picture, wherein the encoding includes hierarchical hash-based block matching for block vector estimation, the block vector estimation identifying a block vector value that indicates a displacement to a region of sample values used for block copy prediction, wherein the hierarchical hash-based block matching for the current block includes identifying a matching block among multiple candidate blocks by;

determining a first hash value for the current block using a first hash function;

determining a second hash value for the current block using a second hash function different than the first hash function;

using the first hash value for the current block to select a candidate block list in a data structure, thereby eliminating at least one of the multiple candidate blocks from consideration based at least in part on the first hash value for the current block; and

based at least in part on the second hash value for the current block, determining a matching block among any candidate blocks in the selected candidate block list; and

outputting the encoded data for the picture.

13. The one or more computer-readable memory or storage devices of claim 12 wherein the first hash function is one of a cyclic redundancy check function, a hash function that includes averaging and XOR operations, and a locality-sensitive hash function.

14. The one or more computer-readable memory or storage devices of claim 12 wherein the identifying the matching block for the current block further includes performing block matching operations between sample values of the current block and a remaining candidate block.

15. The one or more computer-readable memory or storage devices of claim 12 wherein the picture that includes the current block also includes the multiple candidate blocks, and wherein, for the block copy prediction, the encoding data for the current block uses intra block copy prediction.

16. The one or more computer-readable memory or storage devices of claim 12 wherein the data structure includes one or more candidate block lists indexed according to first hash value from the first hash function, wherein each of the one or more candidate block lists includes (a) one or more candidate block lists indexed according to second hash value from the second hash function or (b) for each of one or more of the multiple candidate blocks, a second hash value from the second hash function for the candidate block.

19. The one or more computer-readable memory or storage devices of claim 12 wherein another picture includes at least some of the multiple candidate blocks, and wherein the block copy prediction references the other picture.