基于改进位平面匹配法的运动估计

刘玉峰，李震

(1.浙江广播电视集团，杭州 310005；2 .浙江大学，杭州310027 )

1 引言

电子稳像是指对数字化后的图像进行各种图像匹配算法来估计出图像序列间的位移，并应用相应的补偿技术来实现图像序列的稳定，是数码摄像机中消除视频抖动的一种重要方法。电子稳像中的一个重要算法就是运动估计，运动估计不仅可以大幅度提升图像序列观测的稳定性，改善图像压缩效果，而且可以获得更为优化的成像质量，是数字图像处理的重要研究方向之一。常见的运动估计算法主要有块匹配法[1]、灰度投影法[2]、光流法[3，4]和特征追踪法[5，6]。相比于其他算法，块匹配法由于所需计算量小而被广泛应用于各种场景下的运动估计中。

块匹配法通过将一个图形分成多个矩形像素块，并假设在所需进行匹配的像素块内所有的像素点的运动矢量相同，对每一个像素块进行匹配后只会得到一个相应的运动矢量，因此块匹配法相比于基于像素和特征点的算法大大减少了计算量。最初的块匹配法为全搜索法，全搜索法将像素块可能运动到的位置均与参考帧相应位置的像素块进行比较，导致计算量较大，计算速度慢，之后许多加速搜索模板被提出。Koga等人提出了三步法[7]，将搜索过程简化为三步，每一步的搜索步长为上一步的一半，每次搜索均采用9个候选点进行匹配，但是其缺陷是第一步的匹配错误会导致后面两步无法得到正确的匹配结果。由Zhu和Ma提出的钻石搜索法[8]则先后采用由9个检测点组成的大钻石搜索和5个检测点组成小钻石搜索两个搜索模板，该方法具有快速的搜索过程和较强的纠错能力，在1999年被MPEG-4国际标准采纳且归于了验证模型。

为了进一步提高块匹配法的计算效率，位平面匹配法被提出。其中Koga等人最早在1998年提出的灰度图位平面匹配[9]，利用包含图像信息的第四位平面代替灰度图进行匹配，简化了匹配运算的复杂度，但是相邻的像素值之间的二进制表示的多位数据的不同，给匹配带来很大的误差，相比于灰度图匹配精度较低。为了改善位平面的匹配精度，多种位平面匹配法被提出。在1999年，Koga提出了改进算法，先将灰度图用格雷码进行编码，并采用三步法进行搜索，提升了搜索匹配的速度[10]。文献[11]则进一步提出了基于格雷码编码的位平面和钻石搜索模板的全局运动估计算法，进一步改善了匹配过程的纠错能力。截断格雷码TGC(Truncated Graycode)位平面匹配是一种利用多个经过格雷码编码后的位平面进行匹配的算法，文献[12]比较测试证明，经过截断格雷码编码的位平面匹配相比于未经过格雷编码的截断位平面具有更好的匹配效果。1BT(One-bit Transform)位平面匹配法[13]的位平面生成不同于[9]中的位平面，是将灰度图像通过变换后设定阈值转换为1个bit的数据。而Erturk在文献[14]中提出了2BT(Two-bit Transform)位平面匹配的概念，即使用两个位平面来提升匹配性能。基于1BT算法，文献[15]则引入了Constraint Mask的概念，提出了C1BT(Constrained One-bit Transform)算法，其匹配性能高于2BT算法和其他的1BT算法。文献[16]利用C1BT算法与2BT算法的优势，提出了C2BT(Constrained Two-bit Transform)算法，其匹配效果分别比基于2BT的位平面匹配和基于C1BT的位平面匹配高出0.35dB和0.28dB。截断格雷码，C1BT和C2BT等算法改进了灰度图位平面匹配法的匹配效果，同时也增加了匹配过程的复杂度和计算量。改进位平面匹配法的匹配效果且尽量减少计算量成为运动估计中的难题。

本文首先研究了基于格雷码的位平面匹配法的原理，进一步分析了基于格雷码的不同位平面全搜索匹配效果，基于分析结果，并利用钻石搜索法的快速搜索特性，提出了位平面混合快速匹配法，在钻石搜索模板的第一步中使用了基于格雷码的第4位平面进行大钻石搜索模板匹配，在第二步中使用了基于格雷码的第5位平面进行大钻石搜索模板匹配，在第三步中使用灰度图进行小钻石搜索模板匹配。最后将本文提出的位平面混合快速匹配法与C1BT，C2BT，截断格雷码第五、第六位平面及基于格雷码的第5位平面分别进行钻石模板搜索，通过仿真比较各自的匹配效果和计算量，验证了本文算法的优越性。

2 基于格雷码的位平面匹配

2.1 提取位平面

对于灰度图像中任意像素的8 bit大小的灰度值，可由式(1)进行二进制分解[9]。

f(x，y)=a727+a626+…+a121+a020

(1)

其中f(x，y)表示二维灰度图像中位置为(x，y)点的灰度值，ak的值为0或1，第k层位平面包含了整幅图像每个点像素值的ak值。

图1是用Lena图生成的各个位平面的图像信息。从图1可以观察到，处于较高层的位平面图像包含了视觉有效信息，较低层的位平面图像仅仅包含一些图像的细节信息及噪声，不能提供有效的视觉参考。使用不同位平面进行匹配得到的结果不同，选取合适的位平面作为匹配平面对整个匹配过程的精度有着非常大的影响。直接利用灰度图位平面进行匹配的主要问题在于相邻的灰度值之间的二进制显示会有多位数据的不同，给匹配带来很大的误差。例如灰度值127的二进制显示为01111111，灰度值128的二进制显示为10000000，虽然127与128在数值上仅相差1，但是两者的二进制显示有8位不同。

针对灰度图位平面的问题，使用格雷码对灰度图进行编码，得到基于格雷码的位平面[10]，格雷码编码公式如(2)所示：

位平面0 位平面1 位平面2 位平面3

位平面4 位平面5 位平面6 位平面7图1 Lena图分解得到各个位平面的图像信息

(2)

其中gk即为基于格雷码的第k层位平面数据。利用相邻灰度图位平面数据依次异或可得基于格雷码的位平面。

2.2 块匹配法

块匹配法首先从基于格雷码的位平面中获取匹配块数据，然后在全搜索范围内利用位平面数据进行匹配，以最小化非匹配点数NNMP (Number of Non-matched Points)为准则获取最佳匹配位置，如图2所示。

匹配使用的像素块大小的选择对匹配精度有着非常大的影响，匹配块过小不足以提供足够的有效信息来实现匹配，匹配块过大可能会导致像素块内存在不一致的运动和计算量过大等问题。在测试图像大小为480*640时，块匹配法在使用匹配块面积小于32*32时不能估计到有效的运动矢量，在匹配块面积为64*64时，得到的运动矢量的匹配效果较好；而在匹配块面积为128*128时，匹配效果更好，但是其计算量非常大[17]。

将匹配图像块的位数据进行异或操作并求得和值即可获取NNMP，计算公式如式(3)所示。

(3)

最后将各个图像块匹配所获得的局部运动矢量与前一帧的全局运动矢量做中值滤波，除去局部运动矢量的尖峰脉冲。

3 位平面匹配效果分析

为了分析基于格雷码的位平面匹配法的性能，如图3所示，我们对手持拍摄设备拍摄的7组视频进行测试，对比分析了使用基于格雷码的不同位平面全搜索得到的匹配结果与使用灰度图进行全搜索得到的匹配结果。测试视频的图像大小为1280*720像素，每组视频序列均选取11帧图像共10对进行匹配，每幅图像选取相同间隔的16个大小为64*64像素的匹配块，检测块在图中的位置如图2所示，每个位平面在进行匹配以后可以得到的运动矢量总数为160个。由于低位平面只包含了一些图像的微小细节及噪声，不能包含有效的视觉信息和匹配信息，匹配效果很差，因而主要考虑第3-7层位平面的匹配效果。我们以灰度图全搜索匹配的结果作为参考，对于相同位置的匹配块，如果基于格雷码的不同位平面全搜索匹配结果与灰度图全搜索匹配的结果不一致，即判定为相应位置的匹配块产生了错误匹配。

图2 匹配块在图中的位置

对每一帧采用第3至7位平面进行匹配的结果与对相同图像进行灰度图全搜索匹配得到的结果进行对比，错误匹配的运动矢量数据如表1所示，可以观察到基于格雷码的第5位平面匹配效果最优，第4位平面匹配效果其次，误匹配率都低于15%，其他位平面匹配的误匹配率均大于15%。结合Celebi[12]和Koga[10]的仿真结果，可以得出基于格雷码的第4位平面与第5位平面在不同场景中相对其他位平面具有较好的匹配效果。

此外，在仿真中我们发现基于格雷码的位平面匹配结果即使存在错误匹配的发生，但大多数的发生错误匹配的运动矢量与灰度图匹配得到的运动矢量误差并不大。表2中统计了将错误匹配运动矢量与灰度图匹配得到的运动矢量相差小于一个像素误差的数据。可以看到每个位平面的错误匹配运动矢量与正确运动矢量距离小于1概率大于50%，而位平面5错误匹配运动矢量与正确运动矢量距离小于1概率高达87.31%，这也表明大部分错误匹配的运动矢量都与正确匹配的运动矢量非常接近。

由上述分析，我们可以总结出使用单个位平面进行匹配，即使是匹配效果最优的两个位平面，其错误匹配的概率仍在11.96%与13.57%，会给运动估计的最终结果带来很大的影响，需要我们进一步增强其匹配精度，而可以通过改善搜索的最后几步的精度来减小匹配错误。

图3 随机拍摄的7个场景图像

位平面7位平面6位平面5位平面4位平面3视频序列1301951325视频序列26465283318视频序列35838383749视频序列44733172237视频序列55940252635视频序列6241010721视频序列72319111425总误匹配率27.23%20.00%11.96%13.57%18.75%

表2 错误匹配运动矢量与正确运动矢量距离小于等于1的概率

4 钻石搜索法

钻石搜索法[8]采用了两个搜索模板：大钻石搜索模板和小钻石搜索模板。如图4中所示大钻石搜索模板由9个检测点组成，小钻石搜索模板由5个检测点组成。

(a)大钻石搜索模板

(b)小钻石搜索模板图4 钻石搜索模板

钻石搜索的操作方法为：首先采用大钻石搜索模板进行搜索，当匹配点为大钻石搜索模板中心时，下一步搜索过程切换到小搜索模板，当匹配点不是大钻石搜索模板的中心点时，以匹配点为中心点，继续用大钻石搜索模板进行匹配；之后使用小钻石搜索模板进行匹配，误差最小点即为运动估计中心点，其与参考图像的中心点的差即为运动矢量。

具体操作过程如图5所示。第一次搜索使用大钻石搜索模板，候选点为红色圆形位置，搜索结果得到位移为(-2，0)的位置为第一次搜索的最佳匹配点；第二次搜索以(-2，0)点为中心，仍旧采用大搜索模板进行匹配，候选点显示为绿色菱形，位移为(-3，1)的位置为第二次搜索的最佳匹配点；第三次搜索以(-3，1)点为中心，仍旧采用大搜索模板进行匹配，搜索点为蓝色方形，位移为(-4，2)的位置为第三次搜索的最佳匹配点；第四次搜索以(-4，2)点为中心，仍旧采用大搜索模板进行匹配，搜索点为黑色三角形，位移为(-4，2)的位置为第四次搜索的最佳匹配点，也是其大钻石搜索模板的中心，下次搜索将采用小钻石搜索模板进行匹配；第五次搜索以(-4，2)为中心，采用小钻石搜索模板进行匹配，候选点为白色五角形，获得的最佳匹配点即为全局的最佳匹配点。

图5 钻石搜索过程

使用钻石搜索法，在几次大钻石搜索模板的匹配过程中如果获得的匹配点为大钻石搜索模板的中心点，就可以快速地进入小钻石搜索模板，并最终获得最佳匹配点。这样的操作可以避免全搜索过程大多数点的匹配计算，大大减少了计算量。

此外钻石搜索法具有较强的纠错能力，在大钻石搜索模板搜索时，必须满足匹配中心位于大钻石搜索模板的中心时才能进入小钻石搜索模板的搜索，在一定程度上增加了钻石搜索法的匹配精度。

5 位平面混合快速算法

全搜索法虽然是一种匹配精度较高的算法，但是其计算量过于庞大，导致搜索时间过长。钻石搜索法由于具有快速搜索的特性被广泛应用，此外相比于其他搜索方法具有较高的匹配精度。将钻石搜索模板应用于基于格雷码的位平面搜索，虽然可以提高基于格雷码的位平面搜索的搜索速度，但是不能提升匹配精度，其匹配精度受限于最佳匹配位平面的匹配效果。由位平面分析可知采用位平面匹配时，大多数错误匹配的运动矢量与正确的运动矢量之间误差不大，只差一到两个像素。使用基于格雷码的位平面进行钻石搜索模板匹配，绝大多数搜索过程中都能找到正确的小钻石搜索模板中心，但是由于自身匹配精度限制，无法在小钻石搜索模板中找到正确的最佳匹配点。因此使用基于格雷码的位平面匹配只需要提升小钻石搜索模板的匹配精度就可以大幅度提升整个钻石搜索匹配的精度。

本文提出一种位平面混合快速匹配算法，在钻石搜索第一步与第二步采用基于格雷码的第4位平面与第5位平面，这两个位平面在不同场景的匹配过程中相比于其他位平面具有较好的匹配效果。而在第三步小钻石搜索模板过程中采用灰度图进行匹配，与其他的位平面匹配算法相比，使用灰度图进行匹配可以获得最佳的匹配精度。位平面混合快速匹配算法的主要步骤如下：

(a)进行块匹配的搜索模板采用钻石搜索模板，第一步搜索使用基于格雷码的第4位平面进行大钻石搜索模板匹配；

(b)当第一步的匹配结果为大钻石搜索模板中心时，则进入第三步；否则以得到的最佳匹配点为中心，使用基于格雷码的第5位平面进行大钻石搜索模板匹配，如果匹配结果为大钻石搜索模板中心，则进入第三步，否则仍重复第二步搜索操作；

(c)进入第三步后使用灰度图进行小钻石搜索模板进行匹配，并得到最终的匹配点。

图6 位平面混合快速匹配法的匹配过程

具体匹配过程如图6所示，在第一步的搜索中使用大钻石搜索模板，候选点显示为红色圆形，使用基于格雷码的第4位平面进行匹配，搜索结果得到位移为(1，1)的位置为第一次搜索的最佳匹配点；进入第二步搜索，但由于上一次大钻石搜索模板匹配中心不为自身中心，第二次搜索仍以大钻石模板进行搜索，以(1，1)点为中心，候选点显示为绿色菱形，由于第一步与第二步匹配的内容不一致，第二步需要重新计算9个匹配点，使用基于格雷码的第5位平面进行匹配，位移为(1，3)的位置为第二次搜索的最佳匹配点；但由于上一次大钻石搜索模板匹配中心不为自身中心，第三次搜索仍以大钻石模板进行搜索，以(-3，1)点为中心，搜索点为蓝色方形，使用基于格雷码的第5位平面进行匹配，位移为(2，4)的位置为第三次搜索的最佳匹配点；但由于上一次大钻石搜索模板匹配中心不为自身中心，第四次搜索仍以大钻石模板进行搜索，以(2，4)点为中心，候选点为黑色三角形，使用基于格雷码的第5位平面进行匹配，位移为(2，4)的位置为第四次搜索的最佳匹配点，也是其大钻石搜索模板的中心，下次搜索则采用小钻石搜索模板进行匹配；第五次搜索以(2，4)为中心，采用小钻石搜索模板进行匹配，匹配计算使用灰度图进行匹配，候选点为白色五角形，由于第三步与第二步匹配的内容不一致，需要重新计算匹配中心点的匹配值，获得的最佳匹配点即为全局的最佳匹配点。

6 实验结果与评价

对10组常用的视频测试序列如图7所示，使用本文算法进行帧间运动估计，并与利用C1BT算法，C2BT算法，截断位为5和6的截断格雷码位平面和基于格雷码的第5位平面分别进行钻石搜索的匹配精度和计算量进行比较。测试视频大小为352*288像素，采用32*32的匹配块进行匹配，每幅图像取16个匹配块，每个视频测试序列选取连续的11帧进行10组测试总共进行160次匹配。

以灰度图全搜索匹配的结果作为参考结果，对每个视频序列测试的误匹配结果如下表3所示。可以观察到本文提出的位平面混合快速匹配算法误匹配率为22.18%，远低于其他平面的匹配算法进行钻石搜索的误匹配率，在所有场景都具有较好的匹配性能。

比较了不同位平面匹配算法进行匹配的计算量。假定在钻石搜索的三步中不进行匹配内容的切换，一共进行了X次的匹配X≥13。由钻石搜索法的特性可知，当前的最佳匹配点的非匹配点数目已为最少，即使在不同步骤中发生匹配内容的更换，只需要多计算一次最佳匹配点的NNMP值。分两种情况进行考虑，如果在钻石搜索法第一步得到的最佳匹配点为大钻石搜索模板的中心，那么位平面混合快速匹配法将进行9次基于格雷码的第4位平面匹配，5次灰度图匹配；否则位平面混合快速匹配法将一共进行了9次基于格雷码的第4位平面匹配，X-12次基于格雷码的第5位平面匹配，5次灰度图匹配。每次位平面匹配需要进行1次矩阵异或运算和1次矩阵求和运算，每次灰度图匹配需要进行1次矩阵相减运算和1次矩阵求和运算。

Container News Stefan Bridge Paris

Foreman Bus Flower Highway Elephants Dream图7 10组常见测试视频序列

视频序列本文算法C1BTC2BTTGC5TGC6Container113077News61619813Stefan8297939492Bridge5379676563Paris019101314Foreman3978666880Bus6683736983Flower5368637477Highway541119196106Elephant Dream110769误匹配率22.18%35.88%30.56%31.25%34.00%

不同位平面匹配算法进行钻石搜索一次运动估计的计算量如下表4所示，由表中数据可以得到位平面混合快速匹配法一共进行了X-3次矩阵位运算操作，X+7次矩阵加减操作。位平面混合快速匹配法的计算量仅高于使用单个位平面进行匹配的C1BT和位平面5的计算量，低于C2BT、TGC5、TGC6等位平面匹配法进行钻石搜索的计算量。

表4 不同位平面匹配算法进行钻石搜索的计算量

7 结论

本文主要对数字视频中帧间运动估计算法进行了研究。对具有计算简单，易于硬件实现特性的基于格雷码的位平面匹配法进行了分析，通过仿真测试得出第4位平面与第5位平面在不同场景中相对其他位平面具有较好的匹配效果并且发现大部分错误匹配的运动矢量都与正确匹配的运动矢量非常接近。针对基于格雷码的位平面匹配法采用全范围搜索模板搜索时间长的缺点，利用具有快速搜索特性和较强的纠错能力钻石搜索模板的进行搜索，同时针对位平面在匹配过程中精度不高，使用快速搜索模板会进一步降低图像的匹配精度的问题，根据基于格雷码的位平面匹配法性能分析的发现，提出了位平面混合快速匹配法，在不同的大钻石搜索步骤中使用匹配精度高的位平面进行匹配，尤其仅在小钻石搜索步骤中使用具有最高匹配精度的灰度平面匹配，大大提高了匹配精度。实验结果表明位平面混合快速匹配法与其他位平面匹配法同时使用钻石搜索模板，其误匹配率最小，匹配效果最好，而其计算量较小。

[1]Barjatya A. Block matching algorithms for motion estimation[J]. IEEE Transactions on Evolution Computation，2004，8(3): 225-239.

[2]Sauer K，Schwartz B. Efficient block motion estimation using integral projections[J]. IEEE Transactions on Circuits and Systems for Video Technology，1996，6(5):513-518.

[3]Lucas B D，Kanade T. An iterative image registration technique with an application to stereo vision[C]. IJCAI，1981，81: 674-679.

[4]Horn B K P，Schunck B G. Determining optical flow[C]. Technical Symposium East，International Society for Optics and Photonics，1981:319-331.

[5]Huang J C，Hsieh W S. Automatic feature-based global motion estimation in video sequences[J]. IEEE Transactions on Consumer Electronics，2004，50(3):911-915.

[6]Ranade S，Rosenfeld A. Point pattern matching by relaxation[J]. Pattern recognition，1980，12(4): 269-275.

[7]Koga T. Motion-compensated interframe coding for video conferencing[C]. Proc of NTC，1981: 5-3.

[8]Zhu S，Ma K K. A new diamond search algorithm for fast block-matching motion estimation[J]. IEEE Transactions on Image Processing，2000，9(2):287-290.

[9]Ko S J，Lee S H，Lee K H. Digital image stabilizing algorithms based on bit-plane matching[J]. IEEE Transactions on Consumer Electronics，1998，44(3): 617-622.

[10]Ko S J，Lee S H，Jeon S W，Kang E S. Fast digital image stabilizer based on gray-coded bit-plane matching[J].IEEE Transactions on Consumer Electronics，1999，45(3): 598-603.

[11]王彦锟，刘方.采用位平面和钻石搜索的全局运动估计[J]. 兵工自动化，2007，26(11):80-85.

[12]Celebi A，Akbulut O，Urhan O，et al. Truncated graycoded bit-plane matching based motion estimation and its hardware architecture[J]. IEEE Transactions on Consumer Electronics，2009，55(3):1530-1536.

[13]Natarajan B，Bhaskaran V，Konstantinides K. Low-complexity block-based motion estimation via one-bit transforms[J]. IEEE Transactions on Circuits and Systems for Video Technology，1997，7(4): 702-706.

[14]Erturk A，Erturk S. Two-bit transform for binary block motion estimation[J]. IEEE Transactions on Circuits and Systems for Video Technology，2005，15(7):938-946.

[15]Urhan O，Erturk S. Constrained one-bit transform for low complexity block motion estimation[J]. IEEE Transactions on Circuits and Systems for Video Technology，2007，17(4) : 478-482.

[16]Choi C，Jeong J. Constrained two-bit transform for low complexity motion estimation[C].International Conference on Consumer Electronics，2013: 350-351.

[17]钟平，于前洋，金光，等.动态图像序列运动矢量估计算法的研究[J]. 光学技术，2003，29(2): 219-225.