Hash-based block matching in video and image coding

Patent metadata

Field	Value
Publication number	US-2016234530-A1
Application number	US-201315024812-A
Country	US
Kind code	A1
Filing date	Oct 25, 2013
Priority date	Oct 25, 2013
Publication date	Aug 11, 2016
Grant date	—

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 (“BV”) 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.

First claim

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, including:
determining a hash value for the current block;
identifying a matching block among multiple candidate blocks based at least in part on the hash value for the current block; 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 determining the hash value for the current block uses one of a cyclic redundancy check function, a hash function that includes averaging and XOR operations, and a locality-sensitive hash function.

4 .- 6 . (canceled)

7 . 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.

8 . 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.

9 . 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, comparing the hash value for the current block to a hash value for the candidate block.

10 . The computing device of claim 1 wherein the hash value for the current block is a first hash value determined using a first hash function, and wherein the encoding data for the current block further includes:
determining a second hash value for the current block using a second hash function different than the first hash function, wherein the identifying the matching block is also based at least in part on the second hash value for the current block.

11 . The computing device of claim 1 wherein a data structure organizes the multiple candidate blocks according to hash value, and wherein the identifying the matching block includes:
using the hash value for the current block to select a candidate block list; and
determining the matching block among any candidate blocks in the selected list.

12 . (canceled)

13 . The computing device of claim 11 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 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.

14 . (canceled)

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

16 . (canceled)

17 . In a computing device with a video encoder or image encoder, a method comprising:
creating a data structure that organizes multiple candidate blocks according to hash value; encoding data for a current block of a picture, including using the data structure in 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; and outputting the encoded data for the picture.

18 . The method of claim 17 wherein the encoding data for the current block includes:
determining a hash value for the current block; and
using the hash value for the current block to select a candidate block list; and
determining a matching block among any candidate blocks in the selected list.

19 . (canceled)

20 . The method of claim 17 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 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.

21 .- 23 . (canceled)

24 . The method of claim 17 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.

25 . One or more computer-readable media 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; and outputting the encoded data for the picture.

26 . The one or more computer-readable media of claim 25 wherein the hierarchical hash-based block matching for the current block includes identifying a matching block among multiple candidate blocks, including, in each of multiple iterations:
determining a hash value for the current block; and
eliminating at least some of the multiple candidate blocks from consideration based at least in part on the hash value for the current block.

27 . The one or more computer-readable media of claim 26 wherein the determining the hash value uses different hash functions in the multiple iterations.

28 . The one or more computer-readable media of claim 26 wherein the hierarchical hash-based block matching for the current block further includes performing block matching operations between sample values of the current block and a remaining candidate block after the multiple iterations.

29 . The one or more computer-readable media of claim 26 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.

30 . The one or more computer-readable media of claim 25 wherein a data structure:
organizes multiple candidate blocks according to first hash value from a first hash function and according to second hash value from a second hash function different than the first hash function;
includes one or more first candidate block lists indexed according to first hash value from the first hash function, wherein each of the one or more first candidate block lists includes one

Assignees

• Xu Jizheng
• Zhu Weijia
• Microsoft Technology Licensing Llc

Inventors

• Xu Jizheng
• Zhu Weijia

Classifications

• H04N19/94 Primary

  Vector quantisation · CPC title

• H04N19/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 title

• H04N19/176

  the region being a block, e.g. a macroblock · CPC title

• H04N19/147

  according to rate distortion criteria (rate-distortion as a criterion for motion estimation H04N19/567) · CPC title

• H04N19/52

  by predictive encoding · CPC title