Representing blocks with hash values in video and image coding and decoding
AssigneeMicrosoft Technology Licensing, LLC
InventorsJizheng Xu, Weijia Zhu
Life of this patent
Estimating the term…
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 blocks with hash values determined using hash-based block matching. Other innovations relate to reconstructing blocks using hash values determined with hash-based block matching.
Claims20
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 sample values of a picture, including:
- determining a first hash value for the current block using one of a cyclic redundancy check function, a hash function that includes averaging and XOR operations, and a locality-sensitive hash function, the first hash value for the current block being determined using the sample values of the current block;
- and
- identifying a matching block among multiple candidate blocks based at least in part on the first hash value for the current block, including:
- using the first hash value for the current block to filter out at least some non-matching blocks among the multiple candidate blocks;
- and
- using a second hash value, different than the first hash value, for the current block to filter out at least some non-matching blocks among remaining candidate blocks of the multiple candidate blocks and/or determining an index value for the current block that indicates the matching block among the remaining candidate blocks;
- and
- outputting the encoded data, wherein the encoded data includes, to represent the current block, the first hash value for the current block as well as the second hash value for the current block and/or the index value for the current block.
In a computing device with a video decoder or image decoder, a method comprising:
- for each of multiple candidate blocks, determining a first hash value using one of a cyclic redundancy check function, a hash function that includes averaging and XOR operations, and a locality-sensitive hash function;
- receiving encoded data for a picture, wherein the encoded data includes a first hash value for a current block of sample values of the picture, the first hash value for the current block having been determined using the sample values of the current block, and wherein the encoded data further includes a second hash value, different than the first hash value, for the current block and/or an index value for the current block;
- and
- decoding the current block, including:
- identifying a reconstruction block among the multiple candidate blocks based at least in part on the first hash value for the current block, including:
- using the first hash value for the current block to filter out at least some non-matching blocks among the multiple candidate blocks;
- and
- using the second hash value for the current block to filter out at least some non-matching blocks among remaining candidate blocks of the multiple candidate blocks and/or using the index value for the current block to identify the reconstruction block among the remaining candidate blocks;
- and
- using the reconstruction block for the current block.
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:
- for each of multiple candidate blocks, determining a first hash value using one of a cyclic redundancy check function, a hash function that includes averaging and XOR operations, and a locality-sensitive hash function;
- receiving encoded data for a picture, wherein the encoded data includes a first hash value for a current block of sample values of the picture, the first hash value for the current block having been determined using the sample values of the current block, and wherein the encoded data further includes a second hash value, different than the first hash value, for the current block and/or an index value for the current block;
- and
- decoding the current block, including:
- identifying a reconstruction block among the multiple candidate blocks based at least in part on the first hash value for the current block, including:
- using the first hash value for the current block to filter out at least some non-matching blocks among the multiple candidate blocks;
- and
- using the second hash value for the current block to filter out at least some non-matching blocks among remaining candidate blocks of the multiple candidate blocks and/or using the index value for the current block to identify the reconstruction block among the remaining candidate blocks;
- and
- using the reconstruction block for the current block.
Dependencies are inferred from the claim text.