屏幕内容视频编码的基于哈希的运动估计技术

本文将介绍适用于屏幕内容视频编码的基于哈希的运动估计技术。

屏幕内容用来泛指非相机捕获的视频内容，典型的由计算机生成的文字、图像、动画等。屏幕内容在信号特性上和对人类视觉系统感知上都与传统的相机捕获内容不同，因此对屏幕内容处理需要更有效的视频编码技术。屏幕内容的一些特点包括无捕获噪声、含锐变的边缘、含大的运动和不自然的运动、含重复的图案等。

近年来随着屏幕内容重要性的提升，较新的视频编码标准中都含有了一定程度的对屏幕内容编码的支持。[1]总结了一些标准中对一些屏幕内容编码工具的支持情况，如表所示。

帧间预测过程是在参考图像中寻找当前块的最佳匹配块，寻找过程称为运动估计。传统运动估计是在一定搜索窗内按照一定搜索策略算法来进行搜索运动矢量。由于屏幕内容具有大运动和不自然运动等特点，传统运动估计和搜索策略算法不能很好地适用于屏幕内容编码。如果只是直接简单地扩大搜索窗的范围，会造成存储容量和带宽的增加以及待搜索点数的增加，同时也无法解决搜索策略算法不能很好适用的问题。为了解决以上问题，基于哈希的运动估计被提出，同样也适用于与帧间预测过程类似的帧内块拷贝过程（即基于哈希的帧内块拷贝估计）。

在基于哈希的运动估计中，通过比较当前块和参考图像中待搜索块的哈希值来实现快速且大量的搜索匹配过程。具体来说，首先计算参考图像中全部待搜索块的哈希值，建立哈希表存储；然后在运动估计过程中，计算当前块的哈希值，并查找哈希表存储、与哈希表中具有相同哈希值的待搜索块进行比较，完成运动估计过程。这种方法实现快速且大量的搜索匹配，可以在提高编码BD-rate性能的同时也节省编码时间。

哈希（散列）函数是指将任意大小输入数据映射为固定大小输出值的一类函数[2]。哈希函数被广泛用于校验、纠错、指纹、压缩、随机化、加密等场合当中。常用的哈希函数包括SHA-1、MD5、CRC等。

哈希函数的一个重要应用就是用于建立哈希表，即首先对输入数据应用哈希函数计算得到哈希值，然后用哈希值作为输入数据在哈希表中存储的索引值。这样可以通过数据内容直接在哈希表中查找到数据的位置，具有极快的搜索速度。建立哈希表是一个空间-时间权衡的过程，一对一映射具有最快的搜索速度但同时需要最大的输出空间范围，通常使用的是多对一映射，可以将多个不同输入映射到相同的输出从而压缩了输出空间范围，但存在哈希冲突问题，即多个输入可能会被分配到哈希表中的同一个索引位置。

哈希冲突的常用解决方案包括忽略新项、取代旧项、探测其他位置、建立链表等，其中建立链表是指在哈希表中一个索引位置存储的是一个链表，用链表连接所有分配到该索引位置的输入。

下面介绍一种适用于HEVC-SCC的哈希运动估计技术[3]。技术整体可分为哈希表生成和块匹配两个部分。

在哈希表生成部分。使用CRC作为哈希函数。为了提高数据复用性，首先对每一行计算哈希值，然后将块中所有行的哈希值排列后再计算一个新的哈希值作为块的最终哈希值。

在块匹配部分。通过计算当前块的哈希值，可以在哈希表中快速查找到参考图像中具有相同哈希值的待搜索匹配块，即是与当前块内容相同的待搜索匹配块。

其他考虑和实现细节部分。

为了简化运动估计，一些同质区域块被排除在哈希运动估计之外，这些块很容易使用水平或垂直预测进行高效编码。

使用18位哈希值，高2位决定块大小，低16位决定CRC值。额外使用第二个24位CRC值进一步确认两个块内容相同。

如果得到了准确匹配则可以跳过常规的运动估计过程，否则仍需要常规的运动估计过程来得到近似匹配。

如果满足了一些特定条件可以终止一些后续测试，作为快速编码算法。

下面介绍VVC中使用的哈希运动估计技术[4]。与前面的介绍的HEVC-SCC中使用的哈希运动估计技术类似。

不同之处在于是基于4×4块自底向上计算不同大小的块的哈希值。

在块匹配部分，除了进行方形块的匹配，还需要进行非方形块的匹配。对于非方形块，将其按照短边切分成若干个方形块，从其中第一个非简单方形块开始匹配，完成后在匹配结果中继续向后匹配剩余的方形块直到全部完成，得到的能满足全部匹配的结果作为原始非方形块的匹配结果。

下面是VVC中使用的哈希运动估计技术的部分试验结果[5][6]。

参考文献：

[1]X. Xu and S. Liu, “Overview of Screen Content Coding in Recently Developed Video Coding Standards,” in IEEE Transactions on Circuits and Systems for Video Technology, vol. 32, no. 2, pp. 839-852, Feb. 2022, doi: 10.1109/TCSVT.2021.3064210.

[2]en.wikipedia.org/wiki/Hash_function

[3] B. Li, J. Xu and F. Wu, “A unified framework of hash-based matching for screen content coding,” 2014 IEEE Visual Communications and Image Processing Conference, 2014, pp. 530-533, doi: 10.1109/VCIP.2014.7051623.

[4]JVET-Z2002, “Algorithm description for Versatile Video Coding and Test Model 17 (VTM17)”

[5]JVET-M0253, “Non-CE8: Hash-based Motion Search”

[6]JVET-N0247, “Non-CE8: an improvement to hash-based motion estimation”