Hash table construction and availability checking for hash-based block matching
AssigneeMicrosoft Technology Licensing, LLC
InventorsBin Li, Jizheng Xu, Feng Wu
Life of this patent
Estimating the term…
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.
Claims20
In a computing device that implements a video encoder, a method comprising:
- reconstructing sample values available for use in encoding at least part of a current picture, wherein a given candidate block among multiple candidate blocks in the current picture or a reference picture partially overlaps one or more other candidate blocks among the multiple candidate blocks;
- and
- updating a hash table for a hash-based block matching, wherein the updating the hash table includes, for the given candidate block:
- evaluating whether the given candidate block satisfies a complexity criterion, including:
- computing a complexity metric for the given candidate block;
- and
- comparing the complexity metric to a threshold;
- and
- selectively screening out the given candidate block, including:
- if the given candidate block satisfies the complexity criterion, determining a block hash value for the given candidate block and adding the block hash value to the hash table;
- and
- otherwise, the given candidate block failing the complexity criterion, omitting the block hash value for the given candidate block from the hash table.
A computing device comprising:
- one or more buffers configured to store a current picture;
- and
- a video encoder configured to perform operations comprising:
- determining a block hash value for a current block of the 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 an intra block copy prediction that uses a block vector value to indicate a displacement from the current block to the reference region within the current picture, the reference region including previously reconstructed sample values of the current picture, including:
- checking that the given candidate block and the current block are part of a same slice and part of a same tile;
- and
- checking that the given candidate block includes only sample values in blocks that precede the current block in a coding order.
One or more non-volatile memory or storage devices 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 an intra block copy prediction that uses a block vector value to indicate a displacement from the current block to the reference region within the current picture, the reference region including previously reconstructed sample values of the current picture, including:
- checking that the given candidate block and the current block are part of a same slice and part of a same tile;
- and
- checking that the given candidate block includes only sample values in blocks that precede the current block in a coding order.
Dependencies are inferred from the claim text.