Hash table construction and availability checking for hash-based block matching

Patent metadata

Field	Value
Publication number	US-2016277733-A1
Application number	US-201415029589-A
Country	US
Kind code	A1
Filing date	Mar 4, 2014
Priority date	Mar 4, 2014
Publication date	Sep 22, 2016
Grant date	—

Abstract

Innovations in the areas of hash table construction and availability checking reduce computational complexity of hash-based block matching. For example, some of the innovations speed up the process of constructing a hash table or reduce the size of a hash table. This can speed up and reduce memory usage for hash-based block matching within a picture (for block vector estimation) or between different pictures (for motion estimation). Other innovations relate to availability checking during block vector estimation that uses a hash table.

First claim

1 .- 24 . (canceled)

25 . In a computing device, a method comprising:
for each of multiple candidate blocks:
evaluating whether the candidate block satisfies a complexity criterion;
if the candidate block satisfies the complexity criterion, determining a block hash value for the candidate block and adding the block hash value to a hash table.

26 . The method of claim 25 wherein, for a given candidate block of the multiple candidate blocks, the complexity criterion is satisfied if:
at least one row of the given candidate block has non-uniform sample values; and/or
at least one column of the given candidate block has non-uniform sample values.

27 . The method of claim 25 wherein, for a given candidate block of the multiple candidate blocks, the evaluating whether the candidate block satisfies the complexity criterion includes:
computing a complexity metric for the given candidate block; and
comparing the complexity metric to a threshold.

28 . The method of claim 27 wherein the complexity metric is count of non-zero AC coefficients at a non-zero horizontal position and/or a non-zero vertical position, and wherein the threshold is zero.

29 . The method of claim 25 wherein, for a given candidate block of the multiple candidate blocks, the determining the block hash value includes:
for each of multiple sections of the given candidate block, finding an intermediate hash value;
computing the block hash value for the given candidate block based at least in part on results of hashing the intermediate hash values; and
retaining at least some of the intermediate hash values for reuse in computing other block hash values for other candidate blocks among the multiple candidate blocks.

30 . The method of claim 25 wherein at least some of the multiple candidate blocks are organized as candidate super-blocks, the method further comprising:
for each of multiple candidate super-blocks, determining a super-block hash value based at least in part on results of hashing the block hash values for candidate blocks of the candidate super-block.

31 . The method of claim 25 wherein the block hash values in the hash table are computed using original sample values.

32 . The method of claim 25 wherein the block hash values in the hash table are computed using reconstructed sample values.

33 . The method of claim 25 wherein a current picture includes the multiple candidate blocks, the method further comprising:
determining a block hash value for a current block of the current picture; and
searching the hash table to identify any of the multiple candidate blocks having a block hash value that matches the block hash value for the current block.

34 . The method of claim 25 wherein a reference picture includes the multiple candidate blocks, the method further comprising:
determining a block hash value for a current block of a current picture; and
searching the hash table to identify any of the multiple candidate blocks having a block hash value that matches the block hash value for the current block.

35 . A computing device comprising:
one or more buffers configured to store a current picture; and a video encoder or image encoder configured to perform operations comprising:
determining a block hash value for a current block of a current picture;
searching a hash table to identify any of multiple candidate blocks of the current picture having a block hash value that matches the block hash value for the current block; and
for any given candidate block among the multiple candidate blocks having a block hash value that matches the block hash value for the current block, checking availability of the given candidate block for use as a reference region for the current block in intra block copy prediction.

36 . The computing device of claim 35 wherein the checking the availability of the given candidate block includes checking that the given candidate block includes only sample values in blocks that precede the current block in coding order.

37 . The computing device of claim 36 wherein the checking that the given candidate block includes only sample values in blocks that precede the current block in coding order includes checking that one of the following conditions is satisfied:
(a) vertical coding tree unit (“CTU”) position for a bottom position of the given candidate block is above vertical CTU position for a top position of the current block;
(b) the vertical CTU position for the bottom position of the given candidate block equals the vertical CTU position for the top position of the current block, but horizontal CTU position for a right position of the given candidate block is left of horizontal CTU position for a left position of the current block; and
(c) the vertical CTU position for the bottom position of the given candidate block equals the vertical CTU position for the top position of the current block, and the horizontal CTU position for the right position of the given candidate block equals the horizontal CTU position for the left position of the current block, but z-scan order for a bottom-right corner position of the given candidate block is lower than z-scan order for a top-left corner position of the given candidate block.

38 . The computing device of claim 35 wherein the checking the availability of the given candidate block includes checking that the given candidate block and the current block are part of the same set of blocks.

39 . The computing device of claim 38 wherein the checking that the given candidate block and the current block are part of the same slice and part of the same tile includes:
checking that a top-left corner position of the given candidate block and a top-left corner position of the current block are part of the same slice and part of the same tile; and
checking that a bottom-right corner position of the given candidate block and the top-left corner position of the current block are part of the same slice and part of the same tile.

40 . The computing device of claim 35 wherein the checking the availability of the given candidate block includes:
checking that the given candidate block and the current block are part of the same set of blocks; and
checking that the given candidate block includes only sample values in blocks that precede the current block in coding order.

41 . The computing device of claim 35 wherein the block hash value for the current block is determined using the same hashing approach as the block hash values in the hash table, and wherein the block hash values in the hash table are determined using original sample values.

42 .- 43 . (canceled)

44 . One or more computer-readable media storing computer-executable instructions for causing a computing device, when programmed thereby, to perform operations comprising:
determining a block hash value for a current block of a current picture; searching a hash table to identify any of multiple candidate blocks of the current picture having a block hash value that matches the block hash value for the current block; and for any given candidate block among the multiple candidate blocks having a block hash value that matches the block hash value for the current block, checking availability of the given candidate block for use as a reference region for the current block in intra block copy prediction.

45 . The one or more computer-readable media of claim 44 wherein the checking the availability of the given candidate block includes checking that the given cand

Assignees

• Li Bin
• Xu Jizheng
• Wu Feng
• Microsoft Technology Licensing Llc

Inventors

• Li Bin
• Xu Jizheng
• Wu Feng

Classifications

• H04N19/593

  involving spatial prediction techniques · CPC title

• H04N19/176

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

• H04N19/91

  Entropy coding, e.g. variable length coding [VLC] or arithmetic coding · CPC title

• H04N19/96

  Tree coding, e.g. quad-tree coding · CPC title

• H04N19/567 Primary

  Motion estimation based on rate distortion criteria · CPC title