块匹配算法中特征块的选取方法研究

江小明　杨德贵　魏玺章

摘 要：运动背景补偿是红外序列图像目标跟踪的基础，首先分析块匹配法原理及其误匹配现象产生的原因；然后提出3种定义块的复杂度的方法，据此快速选取用于背景运动估计的特征块群；最后经过外场实测图像验证，基于图像梯度特征定义块的复杂度能够比较准确地估计出背景的运动矢量，且性能优于其他两种方法。

关键词：背景运动估计；块匹配；图像梯度；块的复杂度；特征块群

中图分类号：TP3174 文献标识码：A 文章编号：1004－373X(2009)04－117－04

Research on Choosing Feature Block in Block Matching Algorithm

JIANG Xiaoming,YANG Degui,WEI Xizhang

(Institute of Space Electronic Technology,College of Electric Science and Engineering,National University of Defence Technology,Changsha,410073,China)

Abstract：The motion background compensation is the foundation in the infrared sequence image target tracking.Firstly,the block matching principle and the reason of mismatching are introduced,Then,three kinds of defining methods to the complexity of block are presented,so feature block group applied the background motion estimation is chosen quickly.Finally,verifying by the sociable reality data,what the complexity of block definition based on the image gradient characteristic can be fairly more accurate estimates a motion vector of background,and the function is superior to others.

Keywords：background motion estimation;block matching;image gradient;complexity of block;feature block group

0 引 言

在以序列图像为基础的红外目标跟踪中，往往先要分析视场中背景的运动情况。为了对动态背景进行跟踪，人们也研究了许多方法，如块匹配法、光流法、纹理法［1－3］等。其中块匹配法是一种非常直观的运动估计算法，它是基于平移运动的假设进行运动估计的，应用相当广泛。但当它应用于运动背景估计时，也存在一些问题，首先是如何选取背景复杂的特征块。以往的块匹配主要针对的是运动目标，特征块的选取必须包含目标，所以不必对特征块复杂程度进行分析。而对运动背景，背景复杂表现在图像灰度的变化上，如果所选取的特征块灰度变化不明显，将很容易产生误匹配问题，不利于得出正确的匹配结果，所以必须对背景的复杂程度进行分析，以便最优地选取特征块。

1 块匹配法

块匹配算法是图像序列稳定中最常用的一种算法［4－6］，该算法不需要对图像序列进行任何预处理,只在原始图像数据上进行运算，因此保留了图像序列中每一帧图像的全部信息；另外，该算法原理简单,可以快速实现，因此对块匹配算法的研究一直在进行。

1.1 块匹配法原理

块匹配算法是当今流行的运动估值技术。块匹配法的基本思想是将每一帧图像分割成一系列子块图像(矩形块)，计算当前帧中每一子块与相邻帧中的各子块的误差函数，把具有最小误差的相邻帧的对应子块作为当前块的预测块，并把两块的相对位移定义为位移矢量(运动矢量)。其基本原理如图1所示。

图1 块匹配法示意图

块匹配法基于以下假设：

(1) 运动物体为刚体运动，即运动只有平移,没有旋转和收缩形变;

(2) 一个块内所有点的运动方向一致;

(3) 不考虑被遮掩，因运动而暴露的部分;

(4) 一个块内的光线照度变化均匀。

1.2 块匹配法的误匹配

由块匹配算法原理可知，要得到图像全域运动参数，关键是在相邻帧k，k+1中找到2对匹配点。以前的块匹配算法，有误匹配问题，如图2所示。若k帧中的块实际对应k+1帧中的A块，但由于噪声等因素，误差最小的块为B块，此时，得到的运动矢量就会有较大误差。出现这种问题的原因是A块与B块极为相似，即其灰度变化不大。换言之，这些灰度变化不大的区域对块匹配算法而言，是有害的，它导致块匹配算法在其测度空间中发生模糊，所以，应将这些区域视作模糊区域加以抑制。

图2 块匹配算法的误匹配现象

1.3 块的选择原则

因此，基于块的误匹配原因，对特征块的选择至关重要。针对灰度图像，应当选取那些灰度变化大的区域块作为特征块。图像灰度变化即为图像梯度，一般相邻的不同背景的边缘灰度变化比较大，比如草地与路面、建筑物、树木等有明显的分界线。所以如果选择的特征块是含有不同背景边缘的部分或者特征块内部灰度变化非常明显，将会大大提高匹配的精确度。因此，如何选取背景灰度变化大的区域作为特征块是研究的重点。

2 特征块的选取

求解全局运动参数的关键在于特征块的选取［3］,如果选择参与运算的特征块不能很好地反映背景变化的规律(例如特征块选在平坦灰度的背景区域包括天空、路面、建筑物的表面等)或者特征块选择在运动目标上,都会严重影响运动参数的估计,从而影响后继运动目标的检测。因而在大面积的平坦灰度区域上进行块匹配是不可靠的，因为匹配块周围区域都跟匹配块太相似，特征块选取的目的就是提取能体现背景运动特征的特征块。

2.1 块的复杂度描述方法

一幅图像某些区域灰度分布不均匀表明该区域是不同背景或背景与目标的边缘区域，这里所要选取的特征块也正是这些区域，这些区域可以用块的复杂度(Complexity of Block)来表征。

(1) 块的复杂度用均方差描述。方差是用来度量灰度分布的均匀性的，对于图像中的某块，方差越大表明该块灰度分布越不均匀。

假定块的大小为m×n，这样分的块数为K，fk(i,j)代表第k块中(i,j)处的灰度值，首先求出块的均值为：

uk=1mn∑mi=1∑nj=1fk(i,j)(1)

块的均方差为：

k=1mn∑mi=1∑nj=1fk(i,j)-uk2(2)

则第k块的复杂度定义为：

COB=k(3)

(2) 块的复杂度用直方图灰度等级跨度描述。图像灰度直方图是一种统计后得出的数据，直方图反映了图像中像素的分布特性，因而能够描述图像的一些统计特征，直方图灰度等级跨度可以用来衡量图像灰度分布的均匀性。

针对大小固定的块，统计各块灰度直方图上不为0的灰度等级的个数N，将此N值作为块的复杂度：

И

COB=N(4)

(3) 块的复杂度用平均梯度描述。对于数字图像，图像灰度值的显著变化可以用梯度来表示。梯度是图像处理中最常用的一次微分方法，对应一阶导数。设原图像以函数f(i,j)描述,图像中某一点(i,j)У奶荻仁且桓鍪噶,可定义为：

Grad［f(i,j)］=礷礽 礷礿T(5)

式中：Grad［f(i,j)］表示图像函数f(i,j)的梯度,它考虑了(i,j)点的灰度沿水平方向和竖直方向的变化率指向灰度变化最大的方向。

点(i,j)之梯度的幅值被称为梯度的模,若以G(i,j)П硎,则有：

G(i,j)=Grad［f(i,j)］=

礷(i,j)礽2+礷(i,j)礿2〗12(6)

对离散图像而言,由于灰度变化率的大小用梯度的模衡量,因此可用差分法近似计算梯度。如果定义数字图像行和列数字增加的方向为“后”,并设数字图像中点(i,j)的灰度值以f(i,j)П硎,则用向后差分计算梯度模可表示为：

G(i,j)=

［f(i+1,j)-f(i,j)］2+［f(i,j+1)-f(i,j)］2(7)

采用式(7)计算图像的灰度梯度。根据梯度值,首先找出第k块中最大的n个点的梯度值G(i,j)以及对应位置上的灰度值f(i,j)；然后舍去其中最大的m个点(认为可能是噪声引起的突跳点)。将提取出来的(n-m)Ц龅愕奶荻戎登笃骄值作为该块的复杂度：

COB=1n-m∑G(i,j)(8)

2.2 特征块阈值的选取

以序列图像为基础的红外目标跟踪中，由于摄像机姿态的调整，将会出现背景移进和移出视场的情况，这些背景主要是图像的边缘部分，这样的边缘背景不宜作为特征块，所以在选取特征块时图像四周的块应当排除。

特征块的个数影响着算法的性能；个数越多，背景运动矢量的提取越精确，但会增加算法的计算量和耗时；个数少，会降低背景运动矢量的精度。

M×N的块大小为m×n；图像分块数目为M/m×N/n(表示向下取整)；有用的块个数为(M/m-2)×(N/n-2)，а≡胥兄档囊谰菔翘卣骺榈母鍪至少为有用的块个数的1/3。因此，将去掉四周背景块剩余的块的复杂度从大到小进行排序，阈值定在这一列数的1/3处，这样，将会有一个特征块群参与匹配。

2.3 运动背景估计算法步骤

基于复杂背景的特征，设计图3所示的背景运动估计算法流程。该算法的核心是特征块的选取，通过定义块的复杂度，按第2.2节所述选取阈值，最终确定进行匹配的特征块。

图3 背景运动估计算法流程图

3 背景运动矢量的提取

通常在运动背景下，除了背景的运动外，目标也发生运动，这样就使得提取的特征块中可能包含少数的目标块，这些含目标的特征块不能真实地反映背景的运动；并且，由于红外图像存在噪声和随机干扰，使得运动矢量与背景的运动产生偏差。因此，需要对所有特征块的运动矢量的统计特性进行分析，提取能精确反映背景运动的运动矢量。

在目标为非大目标的条件下，提取的特征块中背景块的个数要明显多于包含目标的块以及包含噪声与干扰的块的个数，而背景又具有近似一致的运动特性，所以取背景特征块群中出现次数最多的特征块运动矢量值作为背景运动矢量。

4 试验结果及分析

试验块匹配法采用全搜索法，匹配准则为MAD准则［1］；试验数据为复杂背景下外场实测红外图像序列，大小为240×320；块大小为30×30；搜索范围为［-30,30］(搜索窗大小为90×90)。

图4为原始相邻两帧红外图像，后一帧相对前一帧有水平向左的位移。采用3种不同复杂度表示方法的分块结果如图5所示。

图4 相邻两帧红外图像

图5 分块结果

所选参与匹配的特征块结果如图6 所示。

图6 特征块选取结果

在图5、图6中，图5(a)和图6(a)是块的复杂用均方差表示的结果；图5(b)和图6(b)是块的复杂度用直方图灰度等级跨度表示的结果；图5(c)图6(c)是块的复杂度用平均梯度表示的结果。

以上各图对应的运动矢量估计结果如表1所示。

表1 运动矢量估计结果

序号12345678

ax-800-8-8-8-80

y00000000

bx-800-8-8-8-80

y00000000

cx-8-8-8-8-9-8-8-8

y00000000

序号910111213141516

ax-9-8-8-8-8-8-8-8

y00000000

bx-8-8-8-8-8-8-8-8

y00000000

cx-8-8-8-8-8-8-8-8

y00000000

由表1及对应的所选特征块图可以看出：

(1) 该试验所选取特征块数目为16块，采用三种不同方法定义块的复杂度所选取的特征块位置大部分相同，说明3种方法都有效。

(2) 由第3节背景运动矢量提取原则，该试验背景运动矢量应该为(-8，0)，即摄像机在水平方向向左移动了8个像素，竖直方向没有位移。同时可以看出并非所有特征块都能正确得出背景的运动矢量，比如结果为(0，0)的特征块，对应图6(a)中第2，3，8块在各幅图像中相应区域，它们的周围灰度变化并不明显，或者虽然变化明显，但变化规律是不变的。

(3) 图6(a)中第9块在各图中所对应的特征块得出的运动矢量都为(-9，0)，说明此区域不仅仅是背景，还有运动的目标。从图中可以看到一亮点，该亮点所处位置是一辆正在行驶的车辆。

(4) 同时可以看到，对于(1)中所见的那些不能正确得出背景运动矢量的特征块，用第一种和第二种表示复杂度的方法都不能很快地排除这样的背景区域，用平均梯度法就能很好地排除这些区域。

另外，从试验时间上也做一个比较，表2列出选块时间和块匹配实验的总耗时。

表2 试验时间

选块时间 /s试验时间 /s

a0.264 4210.684 4

b0.32510.731 26

c0.346 2810.746 92

由此时间表可以看出，均方差法选块时间相对较短，直方图灰度等级跨度法和梯度法选块时间相对较长。原因在于，均方差法直接对图像中每一块求均方差即可；直方图灰度等级跨度法先要计算每一块的直方图，然后再统计灰度等级跨度，统计时间也比较长；梯度法先要求出整幅图像中每一个位置的梯度，然后再求每块的前n-m个比较大的梯度的平均值，其算法相对比较复杂。另外，实验运用全搜索法所耗时与所选特征块的数目成正比，特征块数目越多，试验时间越长；特征块数目少，试验耗时相对短。由于所选特征块个数一定，所以试验总时间相差并不大。

图7是相邻两帧相对运动微小的情况，特征块选取情况如图8所示，其估计结果如表3所示。

图7 小运动情况

图8 特征块选取结果

表3 小运动估计结果

序号12345678

ax000-10000

y00000000

bx-10000-2-20

y00000000

cx-200-100-2-2

y00000000

序号910111213141516

ax-2000-20-2-2

y00000000

bx0-2-2-2-2-2-2-2

y00000000

cx-2-2-2-2-2-2-2-2

y00000000

图8和表3的试验结果表明，对于小运动矢量的情况，由于两帧图像变化比较小，比较容易发生误匹配的现象，所以对特征块的要求更高。三种方法比较而言，用平均梯度定义块的复杂度能更好地提取背景复杂的特征块。

总结以上试验结果，可以得出以下结论：

(1) 对于复杂背景，在一定条件下3种定义块的复杂度的方法都能用于特征块的选取；

(2) 图像灰度梯度直接反映图像灰度的局部变化，用每块的平均梯度表示该块的复杂度是最直接的方法。

(3) 3种方法相比较而言，平均梯度法适用的背景范围更广。

5 结 语

介绍了块匹配法原理及误匹配现象产生的原因，重点阐述了复杂背景下提取特征块的方法；从3个不同角度定义了块的复杂度，根据一定的原则设定复杂度阈值，可以实时、准确地提取背景特征块，采用全搜索块匹配法分析比较了3种方法的实验效果。试验结果表明，3种算法在一定范围内都能提取出背景复杂的块，相比之下，采用平均梯度定义块的复杂度的方法适用范围更广一些，提取的特征块更准确、更复杂、更能正确地得出背景的运动矢量。但是，对于对比度较低的简单背景，背景特征块的匹配结果更多的取决于匹配准则，所以下一步的工作将会针对简单背景在匹配准则上进行改进，以便正确地得出背景的运动矢量。

参 考 文 献

［1］Gharavi H,Mills M.Block Matching Motion Estimation Algorithms－New Results.IEEE Trans.on Circuit sand Systems,1990,37(5):649－651.

［2］Diehl N.Object－oriented Motions Estimation and Segmentation in Image Sequences［J］.Signal Processing,1991,15(3):23－56.

［3］李智勇,沈振康,杨卫平.动态图像分析［M］.北京:国防工业出版社,1999.

［4］周铁,丁钟琦.运动估值块匹配算法的一种改进［J］.海南大学学报:自然科学版,2005,6(2):140－149.

［5］杨卫平,李吉平,沈振康.红外图像序列目标识别与跟踪中的几个问题［J］.红外技术,2001,23(4):8－11.

［6］刘其真,姚剑,孙薇.红外成像运动目标识别与跟踪方法研究［J］.遥感技术与应用,1999,14(2):27－33.

［7］屈志毅,王玉珍,钟声伟.图像拼接中特征块的选取［J］.计算机工程,2002,28(9):165－166.

作者简介

江小明 男，1984年出生，湖北浠水人，硕士研究生。研究方向为红外图像处理、目标检测。

科学计算及信息处理 张海波等：一种改善微弱信号信噪比的小波变换消噪法

注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。