REPRESENTING BLOCKS WITH HASH VALUES IN VIDEO AND IMAGE CODING AND DECODING

• US 20160241876A1
• Filed: 10/25/2013
• Published: 08/18/2016
• Est. Priority Date: 10/25/2013
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Xu, Jizheng, Zhu, Weijia
• Granted Patent: US 11,076,171 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: H04N 1/4466 Enveloping, wrapping, or sealing, i.e. keeping the document closed
• CPC Class Codes: H04N 1/4486 using digital data encryption
• CPC Class Codes: H04N 19/105 Selection of the reference unit for prediction within a chosen coding or prediction mode, e.g. adaptive choice of position and number of pixels used for prediction
• CPC Class Codes: H04N 19/136 Incoming video signal characteristics or properties
• CPC Class Codes: H04N 19/176 the region being a block, e.g. a macroblock
• CPC Class Codes: H04N 19/44 Decoders specially adapted therefor, e.g. video decoders which are asymmetric with respect to the encoder
• CPC Class Codes: H04N 19/46 Embedding additional information in the video signal during the compression process H04N19/517, H04N19/68, H04N19/70 take precedence
• CPC Class Codes: H04N 19/593 involving spatial prediction techniques
• CPC Class Codes: H04N 19/70 characterised by syntax aspects related to video coding, e.g. related to compression standards
• CPC Class Codes: H04N 19/97 Matching pursuit coding

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.

Claims

1. 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 hash value for the current block, the 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 hash value for the current block; and

outputting the encoded data, wherein the encoded data includes the hash value for the matching block to represent the current block.

2. The computing device of claim 1 wherein the encoding data for the current block further comprises encoding the hash value for the current block.

3. The computing device of claim 1 wherein the determining the hash value for the current block uses one of a cyclic redundancy check function a hash function that includes averaging and XOR operations, and a locality-sensitive hash function.

6. The computing device of claim 1 wherein the determining the hash value for the current block uses a hash function that includes block width and block height as inputs.

7. The computing device of claim 1 wherein the picture that includes the current block also includes the multiple candidate blocks, and wherein the encoding data for the current block uses intra block copy prediction.

8. The computing device of claim 1 wherein another picture includes at least some of the multiple candidate blocks.

9. The computing device of claim 1 wherein the identifying the matching block includes, for each of one or more of the multiple candidate blocks, comparing the hash value for the current block to a hash value for the candidate block.

4-5. -5. (canceled)

10. In a computing device with a video decoder or image decoder, a method comprising:

receiving encoded data for a picture, wherein the encoded data includes a hash value for a current block of sample values of the picture, the hash value for the current block having been determined using the sample values of the current block; and

decoding the current block, including;

identifying a reconstruction block among multiple candidate blocks based at least in part on the hash value for the current block; and

using the reconstruction block for the current block.

11. The method of claim 10 wherein the decoding the current block further comprises decoding the hash value for the current block.

12. The method of claim 10 wherein a data structure organizes the multiple candidate blocks according to hash value.

13. The method of claim 10 further comprising, for each of the multiple candidate blocks, determining a 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.

16. The method of claim 10 further comprising, for each of the multiple candidate blocks, determining a hash value using a hash function that includes block width and block height as inputs.

17. The method of claim 10 wherein the picture that includes the current block also includes the multiple candidate blocks, and wherein the decoding the current block uses intra block copy prediction.

18. The method of claim 10 wherein another picture includes at least some of the multiple candidate blocks.

14-15. -15. (canceled)

19-20. -20. (canceled)

21. One or more computer-readable media storing computer-executable instructions for causing a computing device, when programmed thereby, to perform operations comprising:

receiving encoded data for a picture, wherein the encoded data includes a hash value for a current block of sample values of the picture, the hash value for the current block having been determined using the sample values of the current block; and

decoding the current block, including;

identifying a reconstruction block among multiple candidate blocks based at least in part on the hash value for the current block; and

using the reconstruction block for the current block.

22. The one or more computer-readable media of claim 21 wherein the decoding the current block further comprises decoding the hash value for the current block.

23. The one or more computer-readable media of claim 21 wherein a data structure organizes the multiple candidate blocks according to hash value.

24. The one or more computer-readable media of claim 21 wherein the operations further comprise, for each of the multiple candidate blocks, determining a 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.

25. The one or more computer-readable media of claim 21 wherein the picture that includes the current block also includes the multiple candidate blocks, and wherein the decoding the current block uses intra block copy prediction.

26. The one or more computer-readable media of claim 21 wherein another picture includes at least some of the multiple candidate blocks.