Method to generate hash tables for efficient block matching in predictive coding
Techniques are provided for video encoding. A method includes dividing a video frame into a plurality of areas, and generating a plurality of hash tables to be used for block matching in predictive coding of the video frame. At least one hash table of the plurality of hash tables is assigned for use for a corresponding area of the plurality of areas. The method further includes performing predictive coding of the video frame using the plurality of hash tables.
1 . A method comprising:
dividing a video frame into a plurality of tiles and into a plurality of columns, wherein each of the plurality of columns spans across one or more tiles of the plurality of tiles;
determining when to initiate generating of a hash table of a plurality of hash tables;
generating the plurality of hash tables to be used for block matching in predictive coding of the video frame, at least two hash tables of the plurality of hash tables are usable by at least one of the plurality of tiles, and wherein the at least two hash tables are generated for a predetermined set of columns among the plurality of columns;
performing predictive coding of the video frame using the plurality of hash tables; and
determining when to terminate the generating of the hash table based on a delay after hash motion estimation is no longer used for the predictive coding.
2 . The method of claim 1 , wherein the predictive coding uses intra block copy.
3 . The method of claim 2 , wherein the plurality of columns are aligned at respective tiles of the plurality of tiles.
4 . The method of claim 3 , when a new tile is started, further comprising re-initializing the at least two hash tables for the new tile so that the at least two hash tables hold only valid positions.
5 . The method of claim 3 , wherein the plurality of columns are further aligned at respective superblocks.
6 . The method of claim 1 , wherein the predictive coding uses inter coding.
7 . The method of claim 1 , further comprising:
determining, based on a location of a block to be coded, a size of a tile of the plurality of tiles for which to generate hashes.
8 . The method of claim 7 , wherein the predictive coding uses inter coding, and the size of the tile corresponds to a lookahead of at least one row beyond a row of the block to be coded.
9 . The method of claim 7 , wherein the predictive coding uses intra block coding, and the size of the tile corresponds to a delay of a predetermined number of pixels.
10 . The method of claim 1 , wherein determining when to initiate the generating of the hash table is based on one or more of: when screen content is detected in the video frame; when the hash motion estimation is to be used for the predictive coding; and after a number of blocks satisfying a criterion, of the video frame are coded.
11 . The method of claim 1 , wherein a cost of signaling a position of at least one hash table of the plurality of hash tables in a bitstream is determined based on a sum of absolute differences or a sum of squared differences between a block in the video frame pointed to by the position of the at least one hash table and a block in the video frame to be encoded, a signaling rate, and a quantizer-dependent value, and wherein the position in the at least one hash table is ranked among a plurality of positions in the at least one hash table based on the cost of signaling the position in the bitstream.
12 . The method of claim 1 , wherein at least one hash table of the plurality of hash tables is usable by at least two tiles of the plurality of tiles.
13 . The method of claim 1 , wherein a total number of the plurality of hash tables is different from a total number of the plurality of tiles or a total number of the plurality of columns.
14 . An apparatus comprising:
a communication interface that enables network communications;
a memory; and
one or more processors coupled to the communication interface and the memory, wherein the one or more processors are configured to perform operations including:
dividing a video frame into a plurality of tiles and into a plurality of columns, wherein each of the plurality of columns spans across one or more tiles of the plurality of tiles;
generating a plurality of hash tables to be used for block matching in predictive coding of the video frame, at least two hash tables of the plurality of hash tables are usable by at least one of the plurality of tiles, wherein the at least two hash tables are generated for a predetermined set of columns among the plurality of columns, wherein a cost of signaling a position of at least one hash table of the plurality of hash tables in a bitstream is determined based on a sum of absolute differences or a sum of squared differences between a block in the video frame pointed to by the position of the at least one hash table and a block in the video frame to be encoded, a signaling rate, and a quantizer-dependent value, and wherein the position in the at least one hash table is ranked among a plurality of positions in the at least one hash table based on the cost of signaling the position in the bitstream; and
performing predictive coding of the video frame using the plurality of hash tables.
15 . The apparatus of claim 14 , wherein the predictive coding uses intra block copy.
16 . The apparatus of claim 15 , wherein the plurality of columns are aligned at respective tiles of the plurality of tiles.
17 . The apparatus of claim 14 , wherein the predictive coding uses inter coding.
18 . The apparatus of claim 14 , wherein the one or more processors are configured to perform operations including:
determining, based on a location of a block to be coded, a size of a tile of the plurality of tiles for which to generate hashes.
19 . The apparatus of claim 14 , wherein the one or more processors are configured to perform operations including:
determining when to initiate generating of a hash table of the plurality of hash tables.
20 . The apparatus of claim 14 , wherein the at least one hash table of the plurality of hash tables is usable by at least two tiles of the plurality of tiles.
21 . One or more non-transitory computer readable storage media encoded with instructions that, when executed by a processor, cause the processor to:
divide a video frame into a plurality of tiles and into a plurality of columns, wherein each of the plurality of columns spans across one or more tiles of the plurality of tiles;
determine, based on a location of a block to be coded, a size of a tile of the plurality of tiles for which to generate hashes;
generate a plurality of hash tables to be used for block matching in predictive coding of the video frame, at least two hash tables of the plurality of hash tables are usable by at least one of the plurality of tiles, and wherein the at least two hash tables are generated for a predetermined set of columns among the plurality of columns; and
perform predictive coding of the video frame using the plurality of hash tables, wherein the predictive coding uses intra block coding, and the size of the tile corresponds to a delay of a predetermined number of pixels.
22 . The one or more non-transitory computer readable storage media of claim 21 , wherein the plurality of columns are aligned at respective tiles of the plurality of tiles.
23 . The one or more non-transitory computer readable storage media of claim 21 , wherein at least one hash table of the plurality of hash tables is usable by at least two tiles of the plurality of tiles.
24 . The one or more non-transitory computer readable storage media of claim 21 , wherein a cost of signaling a position of at least one hash table of the plurality of hash tables in a bitstream is determined based on a sum of absolute differences or a sum of squared differences between a block in the video frame pointed to by the position of the at least one hash table and a block in the video frame to be encoded, a signaling rate, and a quantizer-dependent value.
25 . The one or more non-transitory computer readable storage media of claim 24 , wherein the position in the at least one hash table is ranked among a plurality of positions in the at least one hash table based on the cost of signaling the position in the bitstream.