塊匹配算法中特征塊的選取方法研究

江小明　楊德貴　魏璽章

摘 要：運(yùn)動(dòng)背景補(bǔ)償是紅外序列圖像目標(biāo)跟蹤的基礎(chǔ)，首先分析塊匹配法原理及其誤匹配現(xiàn)象產(chǎn)生的原因；然后提出3種定義塊的復(fù)雜度的方法，據(jù)此快速選取用于背景運(yùn)動(dòng)估計(jì)的特征塊群；最后經(jīng)過(guò)外場(chǎng)實(shí)測(cè)圖像驗(yàn)證，基于圖像梯度特征定義塊的復(fù)雜度能夠比較準(zhǔn)確地估計(jì)出背景的運(yùn)動(dòng)矢量，且性能優(yōu)于其他兩種方法。

關(guān)鍵詞：背景運(yùn)動(dòng)估計(jì)；塊匹配；圖像梯度；塊的復(fù)雜度；特征塊群

中圖分類(lèi)號(hào)：TP3174 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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 引 言

在以序列圖像為基礎(chǔ)的紅外目標(biāo)跟蹤中，往往先要分析視場(chǎng)中背景的運(yùn)動(dòng)情況。為了對(duì)動(dòng)態(tài)背景進(jìn)行跟蹤，人們也研究了許多方法，如塊匹配法、光流法、紋理法［1－3］等。其中塊匹配法是一種非常直觀的運(yùn)動(dòng)估計(jì)算法，它是基于平移運(yùn)動(dòng)的假設(shè)進(jìn)行運(yùn)動(dòng)估計(jì)的，應(yīng)用相當(dāng)廣泛。但當(dāng)它應(yīng)用于運(yùn)動(dòng)背景估計(jì)時(shí)，也存在一些問(wèn)題，首先是如何選取背景復(fù)雜的特征塊。以往的塊匹配主要針對(duì)的是運(yùn)動(dòng)目標(biāo)，特征塊的選取必須包含目標(biāo)，所以不必對(duì)特征塊復(fù)雜程度進(jìn)行分析。而對(duì)運(yùn)動(dòng)背景，背景復(fù)雜表現(xiàn)在圖像灰度的變化上，如果所選取的特征塊灰度變化不明顯，將很容易產(chǎn)生誤匹配問(wèn)題，不利于得出正確的匹配結(jié)果，所以必須對(duì)背景的復(fù)雜程度進(jìn)行分析，以便最優(yōu)地選取特征塊。

1 塊匹配法

塊匹配算法是圖像序列穩(wěn)定中最常用的一種算法［4－6］，該算法不需要對(duì)圖像序列進(jìn)行任何預(yù)處理,只在原始圖像數(shù)據(jù)上進(jìn)行運(yùn)算，因此保留了圖像序列中每一幀圖像的全部信息；另外，該算法原理簡(jiǎn)單,可以快速實(shí)現(xiàn)，因此對(duì)塊匹配算法的研究一直在進(jìn)行。

1.1 塊匹配法原理

塊匹配算法是當(dāng)今流行的運(yùn)動(dòng)估值技術(shù)。塊匹配法的基本思想是將每一幀圖像分割成一系列子塊圖像(矩形塊)，計(jì)算當(dāng)前幀中每一子塊與相鄰幀中的各子塊的誤差函數(shù)，把具有最小誤差的相鄰幀的對(duì)應(yīng)子塊作為當(dāng)前塊的預(yù)測(cè)塊，并把兩塊的相對(duì)位移定義為位移矢量(運(yùn)動(dòng)矢量)。其基本原理如圖1所示。

圖1 塊匹配法示意圖

塊匹配法基于以下假設(shè)：

(1) 運(yùn)動(dòng)物體為剛體運(yùn)動(dòng)，即運(yùn)動(dòng)只有平移,沒(méi)有旋轉(zhuǎn)和收縮形變;

(2) 一個(gè)塊內(nèi)所有點(diǎn)的運(yùn)動(dòng)方向一致;

(3) 不考慮被遮掩，因運(yùn)動(dòng)而暴露的部分;

(4) 一個(gè)塊內(nèi)的光線照度變化均勻。

1.2 塊匹配法的誤匹配

由塊匹配算法原理可知，要得到圖像全域運(yùn)動(dòng)參數(shù)，關(guān)鍵是在相鄰幀k，k+1中找到2對(duì)匹配點(diǎn)。以前的塊匹配算法，有誤匹配問(wèn)題，如圖2所示。若k幀中的塊實(shí)際對(duì)應(yīng)k+1幀中的A塊，但由于噪聲等因素，誤差最小的塊為B塊，此時(shí)，得到的運(yùn)動(dòng)矢量就會(huì)有較大誤差。出現(xiàn)這種問(wèn)題的原因是A塊與B塊極為相似，即其灰度變化不大。換言之，這些灰度變化不大的區(qū)域?qū)K匹配算法而言，是有害的，它導(dǎo)致塊匹配算法在其測(cè)度空間中發(fā)生模糊，所以，應(yīng)將這些區(qū)域視作模糊區(qū)域加以抑制。

圖2 塊匹配算法的誤匹配現(xiàn)象

1.3 塊的選擇原則

因此，基于塊的誤匹配原因，對(duì)特征塊的選擇至關(guān)重要。針對(duì)灰度圖像，應(yīng)當(dāng)選取那些灰度變化大的區(qū)域塊作為特征塊。圖像灰度變化即為圖像梯度，一般相鄰的不同背景的邊緣灰度變化比較大，比如草地與路面、建筑物、樹(shù)木等有明顯的分界線。所以如果選擇的特征塊是含有不同背景邊緣的部分或者特征塊內(nèi)部灰度變化非常明顯，將會(huì)大大提高匹配的精確度。因此，如何選取背景灰度變化大的區(qū)域作為特征塊是研究的重點(diǎn)。

2 特征塊的選取

求解全局運(yùn)動(dòng)參數(shù)的關(guān)鍵在于特征塊的選?。?］,如果選擇參與運(yùn)算的特征塊不能很好地反映背景變化的規(guī)律(例如特征塊選在平坦灰度的背景區(qū)域包括天空、路面、建筑物的表面等)或者特征塊選擇在運(yùn)動(dòng)目標(biāo)上,都會(huì)嚴(yán)重影響運(yùn)動(dòng)參數(shù)的估計(jì),從而影響后繼運(yùn)動(dòng)目標(biāo)的檢測(cè)。因而在大面積的平坦灰度區(qū)域上進(jìn)行塊匹配是不可靠的，因?yàn)槠ヅ鋲K周?chē)鷧^(qū)域都跟匹配塊太相似，特征塊選取的目的就是提取能體現(xiàn)背景運(yùn)動(dòng)特征的特征塊。

2.1 塊的復(fù)雜度描述方法

一幅圖像某些區(qū)域灰度分布不均勻表明該區(qū)域是不同背景或背景與目標(biāo)的邊緣區(qū)域，這里所要選取的特征塊也正是這些區(qū)域，這些區(qū)域可以用塊的復(fù)雜度(Complexity of Block)來(lái)表征。

(1) 塊的復(fù)雜度用均方差描述。方差是用來(lái)度量灰度分布的均勻性的，對(duì)于圖像中的某塊，方差越大表明該塊灰度分布越不均勻。

假定塊的大小為m×n，這樣分的塊數(shù)為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塊的復(fù)雜度定義為：

COB=k(3)

(2) 塊的復(fù)雜度用直方圖灰度等級(jí)跨度描述。圖像灰度直方圖是一種統(tǒng)計(jì)后得出的數(shù)據(jù)，直方圖反映了圖像中像素的分布特性，因而能夠描述圖像的一些統(tǒng)計(jì)特征，直方圖灰度等級(jí)跨度可以用來(lái)衡量圖像灰度分布的均勻性。

針對(duì)大小固定的塊，統(tǒng)計(jì)各塊灰度直方圖上不為0的灰度等級(jí)的個(gè)數(shù)N，將此N值作為塊的復(fù)雜度：

И

COB=N(4)

(3) 塊的復(fù)雜度用平均梯度描述。對(duì)于數(shù)字圖像，圖像灰度值的顯著變化可以用梯度來(lái)表示。梯度是圖像處理中最常用的一次微分方法，對(duì)應(yīng)一階導(dǎo)數(shù)。設(shè)原圖像以函數(shù)f(i,j)描述,圖像中某一點(diǎn)(i,j)У奶荻仁且桓鍪噶,可定義為：

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

式中：Grad［f(i,j)］表示圖像函數(shù)f(i,j)的梯度,它考慮了(i,j)點(diǎn)的灰度沿水平方向和豎直方向的變化率指向灰度變化最大的方向。

點(diǎn)(i,j)之梯度的幅值被稱為梯度的模,若以G(i,j)П硎,則有：

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

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

對(duì)離散圖像而言,由于灰度變化率的大小用梯度的模衡量,因此可用差分法近似計(jì)算梯度。如果定義數(shù)字圖像行和列數(shù)字增加的方向?yàn)椤昂蟆?并設(shè)數(shù)字圖像中點(diǎn)(i,j)的灰度值以f(i,j)П硎,則用向后差分計(jì)算梯度?？杀硎緸椋?/p>

G(i,j)=

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

采用式(7)計(jì)算圖像的灰度梯度。根據(jù)梯度值,首先找出第k塊中最大的n個(gè)點(diǎn)的梯度值G(i,j)以及對(duì)應(yīng)位置上的灰度值f(i,j)；然后舍去其中最大的m個(gè)點(diǎn)(認(rèn)為可能是噪聲引起的突跳點(diǎn))。將提取出來(lái)的(n-m)Ц齙愕奶荻戎登篤驕值作為該塊的復(fù)雜度：

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

2.2 特征塊閾值的選取

以序列圖像為基礎(chǔ)的紅外目標(biāo)跟蹤中，由于攝像機(jī)姿態(tài)的調(diào)整，將會(huì)出現(xiàn)背景移進(jìn)和移出視場(chǎng)的情況，這些背景主要是圖像的邊緣部分，這樣的邊緣背景不宜作為特征塊，所以在選取特征塊時(shí)圖像四周的塊應(yīng)當(dāng)排除。

特征塊的個(gè)數(shù)影響著算法的性能；個(gè)數(shù)越多，背景運(yùn)動(dòng)矢量的提取越精確，但會(huì)增加算法的計(jì)算量和耗時(shí)；個(gè)數(shù)少，會(huì)降低背景運(yùn)動(dòng)矢量的精度。

M×N的塊大小為m×n；圖像分塊數(shù)目為M/m×N/n(表示向下取整)；有用的塊個(gè)數(shù)為(M/m-2)×(N/n-2)，а≡胥兄檔囊讕菔翹卣骺櫚母鍪至少為有用的塊個(gè)數(shù)的1/3。因此，將去掉四周背景塊剩余的塊的復(fù)雜度從大到小進(jìn)行排序，閾值定在這一列數(shù)的1/3處，這樣，將會(huì)有一個(gè)特征塊群參與匹配。

2.3 運(yùn)動(dòng)背景估計(jì)算法步驟

基于復(fù)雜背景的特征，設(shè)計(jì)圖3所示的背景運(yùn)動(dòng)估計(jì)算法流程。該算法的核心是特征塊的選取，通過(guò)定義塊的復(fù)雜度，按第2.2節(jié)所述選取閾值，最終確定進(jìn)行匹配的特征塊。

圖3 背景運(yùn)動(dòng)估計(jì)算法流程圖

3 背景運(yùn)動(dòng)矢量的提取

通常在運(yùn)動(dòng)背景下，除了背景的運(yùn)動(dòng)外，目標(biāo)也發(fā)生運(yùn)動(dòng)，這樣就使得提取的特征塊中可能包含少數(shù)的目標(biāo)塊，這些含目標(biāo)的特征塊不能真實(shí)地反映背景的運(yùn)動(dòng)；并且，由于紅外圖像存在噪聲和隨機(jī)干擾，使得運(yùn)動(dòng)矢量與背景的運(yùn)動(dòng)產(chǎn)生偏差。因此，需要對(duì)所有特征塊的運(yùn)動(dòng)矢量的統(tǒng)計(jì)特性進(jìn)行分析，提取能精確反映背景運(yùn)動(dòng)的運(yùn)動(dòng)矢量。

在目標(biāo)為非大目標(biāo)的條件下，提取的特征塊中背景塊的個(gè)數(shù)要明顯多于包含目標(biāo)的塊以及包含噪聲與干擾的塊的個(gè)數(shù)，而背景又具有近似一致的運(yùn)動(dòng)特性，所以取背景特征塊群中出現(xiàn)次數(shù)最多的特征塊運(yùn)動(dòng)矢量值作為背景運(yùn)動(dòng)矢量。

4 試驗(yàn)結(jié)果及分析

試驗(yàn)塊匹配法采用全搜索法，匹配準(zhǔn)則為MAD準(zhǔn)則［1］；試驗(yàn)數(shù)據(jù)為復(fù)雜背景下外場(chǎng)實(shí)測(cè)紅外圖像序列，大小為240×320；塊大小為30×30；搜索范圍為［-30,30］(搜索窗大小為90×90)。

圖4為原始相鄰兩幀紅外圖像，后一幀相對(duì)前一幀有水平向左的位移。采用3種不同復(fù)雜度表示方法的分塊結(jié)果如圖5所示。

圖4 相鄰兩幀紅外圖像

圖5 分塊結(jié)果

所選參與匹配的特征塊結(jié)果如圖6 所示。

圖6 特征塊選取結(jié)果

在圖5、圖6中，圖5(a)和圖6(a)是塊的復(fù)雜用均方差表示的結(jié)果；圖5(b)和圖6(b)是塊的復(fù)雜度用直方圖灰度等級(jí)跨度表示的結(jié)果；圖5(c)圖6(c)是塊的復(fù)雜度用平均梯度表示的結(jié)果。

以上各圖對(duì)應(yīng)的運(yùn)動(dòng)矢量估計(jì)結(jié)果如表1所示。

表1 運(yùn)動(dòng)矢量估計(jì)結(jié)果

序號(hào)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

序號(hào)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及對(duì)應(yīng)的所選特征塊圖可以看出：

(1) 該試驗(yàn)所選取特征塊數(shù)目為16塊，采用三種不同方法定義塊的復(fù)雜度所選取的特征塊位置大部分相同，說(shuō)明3種方法都有效。

(2) 由第3節(jié)背景運(yùn)動(dòng)矢量提取原則，該試驗(yàn)背景運(yùn)動(dòng)矢量應(yīng)該為(-8，0)，即攝像機(jī)在水平方向向左移動(dòng)了8個(gè)像素，豎直方向沒(méi)有位移。同時(shí)可以看出并非所有特征塊都能正確得出背景的運(yùn)動(dòng)矢量，比如結(jié)果為(0，0)的特征塊，對(duì)應(yīng)圖6(a)中第2，3，8塊在各幅圖像中相應(yīng)區(qū)域，它們的周?chē)叶茸兓⒉幻黠@，或者雖然變化明顯，但變化規(guī)律是不變的。

(3) 圖6(a)中第9塊在各圖中所對(duì)應(yīng)的特征塊得出的運(yùn)動(dòng)矢量都為(-9，0)，說(shuō)明此區(qū)域不僅僅是背景，還有運(yùn)動(dòng)的目標(biāo)。從圖中可以看到一亮點(diǎn)，該亮點(diǎn)所處位置是一輛正在行駛的車(chē)輛。

(4) 同時(shí)可以看到，對(duì)于(1)中所見(jiàn)的那些不能正確得出背景運(yùn)動(dòng)矢量的特征塊，用第一種和第二種表示復(fù)雜度的方法都不能很快地排除這樣的背景區(qū)域，用平均梯度法就能很好地排除這些區(qū)域。

另外，從試驗(yàn)時(shí)間上也做一個(gè)比較，表2列出選塊時(shí)間和塊匹配實(shí)驗(yàn)的總耗時(shí)。

表2 試驗(yàn)時(shí)間

選塊時(shí)間 /s試驗(yàn)時(shí)間 /s

a0.264 4210.684 4

b0.32510.731 26

c0.346 2810.746 92

由此時(shí)間表可以看出，均方差法選塊時(shí)間相對(duì)較短，直方圖灰度等級(jí)跨度法和梯度法選塊時(shí)間相對(duì)較長(zhǎng)。原因在于，均方差法直接對(duì)圖像中每一塊求均方差即可；直方圖灰度等級(jí)跨度法先要計(jì)算每一塊的直方圖，然后再統(tǒng)計(jì)灰度等級(jí)跨度，統(tǒng)計(jì)時(shí)間也比較長(zhǎng)；梯度法先要求出整幅圖像中每一個(gè)位置的梯度，然后再求每塊的前n-m個(gè)比較大的梯度的平均值，其算法相對(duì)比較復(fù)雜。另外，實(shí)驗(yàn)運(yùn)用全搜索法所耗時(shí)與所選特征塊的數(shù)目成正比，特征塊數(shù)目越多，試驗(yàn)時(shí)間越長(zhǎng)；特征塊數(shù)目少，試驗(yàn)耗時(shí)相對(duì)短。由于所選特征塊個(gè)數(shù)一定，所以試驗(yàn)總時(shí)間相差并不大。

圖7是相鄰兩幀相對(duì)運(yùn)動(dòng)微小的情況，特征塊選取情況如圖8所示，其估計(jì)結(jié)果如表3所示。

圖7 小運(yùn)動(dòng)情況

圖8 特征塊選取結(jié)果

表3 小運(yùn)動(dòng)估計(jì)結(jié)果

序號(hào)12345678

ax000-10000

y00000000

bx-10000-2-20

y00000000

cx-200-100-2-2

y00000000

序號(hào)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的試驗(yàn)結(jié)果表明，對(duì)于小運(yùn)動(dòng)矢量的情況，由于兩幀圖像變化比較小，比較容易發(fā)生誤匹配的現(xiàn)象，所以對(duì)特征塊的要求更高。三種方法比較而言，用平均梯度定義塊的復(fù)雜度能更好地提取背景復(fù)雜的特征塊。

總結(jié)以上試驗(yàn)結(jié)果，可以得出以下結(jié)論：

(1) 對(duì)于復(fù)雜背景，在一定條件下3種定義塊的復(fù)雜度的方法都能用于特征塊的選?。?/p>

(2) 圖像灰度梯度直接反映圖像灰度的局部變化，用每塊的平均梯度表示該塊的復(fù)雜度是最直接的方法。

(3) 3種方法相比較而言，平均梯度法適用的背景范圍更廣。

5 結(jié) 語(yǔ)

介紹了塊匹配法原理及誤匹配現(xiàn)象產(chǎn)生的原因，重點(diǎn)闡述了復(fù)雜背景下提取特征塊的方法；從3個(gè)不同角度定義了塊的復(fù)雜度，根據(jù)一定的原則設(shè)定復(fù)雜度閾值，可以實(shí)時(shí)、準(zhǔn)確地提取背景特征塊，采用全搜索塊匹配法分析比較了3種方法的實(shí)驗(yàn)效果。試驗(yàn)結(jié)果表明，3種算法在一定范圍內(nèi)都能提取出背景復(fù)雜的塊，相比之下，采用平均梯度定義塊的復(fù)雜度的方法適用范圍更廣一些，提取的特征塊更準(zhǔn)確、更復(fù)雜、更能正確地得出背景的運(yùn)動(dòng)矢量。但是，對(duì)于對(duì)比度較低的簡(jiǎn)單背景，背景特征塊的匹配結(jié)果更多的取決于匹配準(zhǔn)則，所以下一步的工作將會(huì)針對(duì)簡(jiǎn)單背景在匹配準(zhǔn)則上進(jìn)行改進(jìn)，以便正確地得出背景的運(yùn)動(dòng)矢量。

參 考 文 獻(xiàn)

［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］李智勇,沈振康,楊衛(wèi)平.動(dòng)態(tài)圖像分析［M］.北京:國(guó)防工業(yè)出版社,1999.

［4］周鐵,丁鐘琦.運(yùn)動(dòng)估值塊匹配算法的一種改進(jìn)［J］.海南大學(xué)學(xué)報(bào):自然科學(xué)版,2005,6(2):140－149.

［5］楊衛(wèi)平,李吉平,沈振康.紅外圖像序列目標(biāo)識(shí)別與跟蹤中的幾個(gè)問(wèn)題［J］.紅外技術(shù),2001,23(4):8－11.

［6］劉其真,姚劍,孫薇.紅外成像運(yùn)動(dòng)目標(biāo)識(shí)別與跟蹤方法研究［J］.遙感技術(shù)與應(yīng)用,1999,14(2):27－33.

［7］屈志毅,王玉珍,鐘聲偉.圖像拼接中特征塊的選取［J］.計(jì)算機(jī)工程,2002,28(9):165－166.

作者簡(jiǎn)介

江小明 男，1984年出生，湖北浠水人，碩士研究生。研究方向?yàn)榧t外圖像處理、目標(biāo)檢測(cè)。

科學(xué)計(jì)算及信息處理 張海波等：一種改善微弱信號(hào)信噪比的小波變換消噪法

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文。