Microsoft Corporation
LOW-COST HASH TABLE CONSTRUCTION AND HASH-BASED BLOCK MATCHING FOR VARIABLE-SIZE BLOCKS

Abstract:

Innovations in hash table construction and hash-based block matching for image encoding or video encoding are described. For example, an encoder determines hash values for base-size candidate blocks in a reference picture. The encoder stores, in a hash table, the hash values for the base-size candidate blocks. The encoder encodes a trial-size current block in a current picture. In some cases, the trial-size current block has a block size larger than the base block size. As part of the encoding, the encoder uses hash-based block matching, between base-size current blocks of the trial-size current block and the base-size candidate blocks, to identify a trial-size matching block, if any, in the reference picture. The encoder stores hash values only for the base-size candidate blocks. This can significantly reduce the computational cost and memory cost for hash table construction during encoding, without hurting compression efficiency or the overall speed of encoding.