鄭興明

(南京航空航天大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 南京 210016)

利用圖像信息對(duì)目標(biāo)物體進(jìn)行搜尋和攻擊，在當(dāng)前越來越受到重視，特別是在航空航天、軍事打擊、醫(yī)學(xué)手術(shù)中的應(yīng)用，其準(zhǔn)確性，精確性和實(shí)時(shí)性一直是該領(lǐng)域的主要研究方向。圖像信息除了包含內(nèi)容的局部信息，還包含內(nèi)容之間相互關(guān)系的全局信息，局部信息特征表述了目標(biāo)特征區(qū)域的信息，如圖像的直線、顏色特征、角度、輪廓以及這些特征之間的相互關(guān)系。全局特征描述的是整個(gè)圖像的信息，如圖像的灰度直方圖等。圖像全局特征信息在某些細(xì)節(jié)上淡化了局部目標(biāo)區(qū)域的細(xì)節(jié)特征，不能體現(xiàn)匹配的結(jié)果，利用圖像的局部特征進(jìn)行匹配越來越受到重視，并成為計(jì)算機(jī)視覺領(lǐng)域的熱點(diǎn)。

目前針對(duì)圖像匹配的主要方法有基于像素點(diǎn)匹配的歸一化積相關(guān)灰度匹配、序貫相似性檢測匹配(Similarity Sequential Detection Algorithm，SSDA)、基于特征匹配的［1］(Scale － Invariant Features Transform，SIFT)和仿射不變特征點(diǎn)提取方法 Harris－ Affine［2－4］。模板匹配的主要思想是將待匹配的圖像作為模板圖像，以窗口的方式，在待查找的源圖像中掃描一遍，通過該模板所對(duì)應(yīng)區(qū)域的圖像與模板圖像之間的相似距離來判斷識(shí)別的結(jié)果。序貫相似性檢測匹配主要解決模板匹配算法計(jì)算量大的問題，模板匹配每滑動(dòng)一次就要做一次匹配運(yùn)算，除了匹配點(diǎn)外在其他匹配點(diǎn)做了“無用功”，導(dǎo)致匹配算法計(jì)算量上升，一旦發(fā)現(xiàn)所在的參考位置為非匹配點(diǎn)，立刻換到新的參考點(diǎn)計(jì)算，加大匹配速度。SIFT方法能夠從匹配圖像中提取顯著不變特征，使不同視角目標(biāo)或場景圖像穩(wěn)定匹配，該特征向量對(duì)圖像尺度、旋轉(zhuǎn)變化、噪聲和光照變化不敏感。由于SIFT對(duì)目標(biāo)遮擋和圖像混雜穩(wěn)定性較強(qiáng)，因此在目標(biāo)識(shí)別中取得良好效果。仿射不變特征方法主要解決大視角變化的圖像匹配問題，在仿射高斯空間的基礎(chǔ)上，用多尺度Harris特征點(diǎn)，檢測算子提取適應(yīng)仿射變換的特征點(diǎn)，然后用特征點(diǎn)的橢圓鄰域代替圓形鄰域。通過迭代估計(jì)特征點(diǎn)鄰域的仿射形狀，不斷調(diào)整特征點(diǎn)所在的尺度、位置和形狀收斂直到不變?yōu)橹梗罱K得到仿射不變特征向量。利用像素點(diǎn)進(jìn)行匹配的主要缺陷是計(jì)算量過大，對(duì)圖像的灰度變換敏感，尤其是非線性的光照變化。此外，對(duì)目標(biāo)的旋轉(zhuǎn)，變形以及遮擋也比較敏感［5］。因而基于像素點(diǎn)匹配的方法不適合實(shí)際場景中的應(yīng)用，為克服這些缺點(diǎn)，可以利用圖像的特征進(jìn)行匹配，一方面圖像的特征點(diǎn)比像素點(diǎn)要少，減少了匹配過程的計(jì)算量。另一方面局部特征點(diǎn)［6］的匹配度量值對(duì)位置的旋轉(zhuǎn)、變形以及遮擋不是很敏感，可以大大提高匹配的精度。而且特征點(diǎn)的提取過程可以減少噪聲的影響，對(duì)灰度變化，圖像變形以及遮擋等有較好的適應(yīng)能力。文中采用失配函數(shù)的思想，解決像素點(diǎn)計(jì)算量過大的缺陷，同時(shí)利用局部特征匹配的優(yōu)勢，提高圖像匹配的精確度和執(zhí)行速度。

1 尺度不變特征

尺度不變特征(Scale－Invariant Feature Transform，SIFT)是一種計(jì)算機(jī)視覺用于偵測與描述圖片中局部特征的，它在空間尺度中尋找極值點(diǎn)，并提取出其位置、尺度、旋轉(zhuǎn)不變量等相關(guān)特征。

局部特征的描述與偵測可以幫助識(shí)別物體，SIFT特征是基于物體上一些局部外觀的興趣點(diǎn)，而與影像的大小和旋轉(zhuǎn)無關(guān)。對(duì)于光線、噪聲、些微視角改變的容忍度較高?；谶@些特性，它們是高度顯著而且相對(duì)容易擷取，在龐大的特征數(shù)據(jù)庫中，容易辨識(shí)物體且鮮有誤認(rèn)。使用SIFT特征描述對(duì)于部分物體遮蔽的偵測率也較高，甚至只需要3個(gè)以上的SIFT物體特征就能計(jì)算出位置與方位。在現(xiàn)今的計(jì)算機(jī)硬件速度下和小型的特征數(shù)據(jù)庫條件下，辨識(shí)速度可接近即時(shí)運(yùn)算。SIFT特征的信息量大，適合在海量數(shù)據(jù)庫中快速準(zhǔn)確匹配。

SIFT架構(gòu)中的特征點(diǎn)是利用不同尺度下高斯濾波器(Gaussian Filters)進(jìn)行卷積(Convolved)，然后利用連續(xù)高斯模糊化差異，根據(jù)不同尺度下的高斯差(Difference of Gaussians)中最大最小值導(dǎo)出，其公式如下

其中，L(x，y，kiσ)是在尺度 kiσ 的條件下，由原始圖像I(x，y)與高斯模糊 G(x，y，kσ)進(jìn)行卷積

G(x，y，kσ)是尺度可變高斯函數(shù)

為減少噪聲對(duì)特征點(diǎn)的影響，避免將邊緣附近的點(diǎn)也誤認(rèn)為是特征點(diǎn)，采用Hessian［7］矩陣對(duì)極值點(diǎn)進(jìn)行過濾，其公式如下

在得到特征點(diǎn)的尺度和位置信息后，為使特征點(diǎn)描述向量對(duì)旋轉(zhuǎn)不變，需要為特征點(diǎn)分配角度信息。計(jì)算特征點(diǎn)梯度大小 m(x，y)和角度 θ(x，y)。

最后利用特征點(diǎn)的梯度方向構(gòu)建一個(gè)36 bin的角度直方圖，直方圖的峰值代表局部梯度的主方向。以特征點(diǎn)為中心取16×16個(gè)像素的窗口，分成16個(gè)4×4的子塊，在每個(gè) 4 ×4 的子塊上計(jì)算 0°，45°，90°，135°，180°，225°，270°，315°這 8 個(gè)方向的梯度大小和梯度方向直方圖。因此，一個(gè)4×4的子塊可以得到一個(gè)8方向描述符，則16個(gè)4×4的子塊可以得到128個(gè)方向描述符，這個(gè)1×128的向量就定義為特征描述符向量。如圖1所示分別在不同像素下提取的SIFT匹配特征，圖1(a)是相同大小測試圖像和匹配圖像，分辨率較低，其特征點(diǎn)的個(gè)數(shù)只有5個(gè)，圖1(b)特征點(diǎn)的個(gè)數(shù)為32個(gè)，圖1(c)特征點(diǎn)個(gè)數(shù)為43個(gè)，圖1(d)特征點(diǎn)個(gè)數(shù)為106個(gè)。

圖1 SIFT在不同分辨率圖像下的特征匹配

2 匹配函數(shù)

文中提出的匹配函數(shù)［8］是利用匹配本身的特征信息來決策出重新進(jìn)行匹配的起始點(diǎn)。假設(shè)特征序列構(gòu)成的描述符向量可以表示為一串由字母組成的字符串:P=abcabcacab，同樣查找圖像的特征序列也被表示成一串很長的字符串:S=…abacbdfe…，問題轉(zhuǎn)變?yōu)樵谥鞔甋中查找出是否具有P特性的匹配串。

令S=s0s1…sm－1是主串，要確定P是否在si開始處匹配。如果si≠a則接下來顯然要用si－1與a比較。同理，若si=a且si+1≠b，則接下來要用si+1與a比較。若sisi+1=ab且si+2≠c，則有以下情形

其中，“?”表示S在該位置的值是多少無關(guān)緊要。第一個(gè)“?”表示si+2且si+2≠c，下一次應(yīng)該用P的第一個(gè)字符直接與si+2比較，而不是與si+1比較，因?yàn)镻的特征序列的第2個(gè)字符b與S中si+1相等，一定有si+1≠a。假定P的前4個(gè)特征字符和S匹配，但下一個(gè)特征字符失配，即si+4≠b

此時(shí)應(yīng)該用si+4與P的第2個(gè)特征字符進(jìn)行比較，等效于把P向右滑動(dòng)，使它的子串對(duì)準(zhǔn)S的一個(gè)子串，然后比較兩個(gè)相等子串后面的第一個(gè)字符?？梢缘贸?，根據(jù)特征字符串P中的字符信息，以及匹配失效主串的字符位置，可以確定接下來應(yīng)該用特征字符串中的哪個(gè)特征字符和主串的當(dāng)前失配字符繼續(xù)比較，而無需回去比較主串的較前位置字符。

特征串p=p0p1…pn－1的匹配函數(shù)定義為

由定義可得，如果部分匹配結(jié)果是 si－j…si－1=p0p1…pj－1且 si≠pj，則接下來如果 j≠0，應(yīng)該用 si與pf(j－1)+1相比;如果 j=0，用 p0與 si+1相比。

3 算法執(zhí)行

圖像匹配的過程是目標(biāo)圖像在測試圖像中查找相似特征的目標(biāo)。首先將目標(biāo)圖像分割，假設(shè)目標(biāo)圖像的大小是M×N，對(duì)圖像長M進(jìn)行m等分，對(duì)圖像寬N進(jìn)行n等分，這樣目標(biāo)圖像就被分割成m×n個(gè)大小模塊的子圖像，每個(gè)子圖像的大小為，同樣對(duì)測試圖像進(jìn)行相同的處理。處理結(jié)果如圖2所示。

圖2 分割為m×n大小的目標(biāo)圖像

分割好的目標(biāo)圖像分別計(jì)算SIFT局部特征，將計(jì)算完的特征按照?qǐng)D像字塊的順序從左到右從上到下排列成一行序列，其長度為m×n，目標(biāo)圖像就被表示成了一串具有SIFT特征的序列串，每個(gè)串的值代表了當(dāng)前分塊子圖像的細(xì)節(jié)特征表述，如圖3所示。

圖3 SIFT提取映射后的特征序列

分塊子圖像的SIFT特征是1×128個(gè)特征向量描述符。它包含了該子圖像的特征信息，由于每個(gè)子圖像包含的細(xì)節(jié)不相同，保證了特征序列間沒有太大的關(guān)聯(lián)性，同時(shí)子圖像內(nèi)容之間是連續(xù)的，特征序列之間又保持著關(guān)聯(lián)性。同樣測試圖像也按照上述方法進(jìn)行分割，在測試圖像匹配目標(biāo)圖像就轉(zhuǎn)變到在測試圖像特征序列里查找目標(biāo)圖像的特征序列，SIFT提取出的特征向量表述符之間的相似性采用歐氏距離的來確定，設(shè)置某一閾值σ，當(dāng)特征向量之間的歐氏距離＜σ時(shí)，判定這兩個(gè)特征向量之間是相似或者相近的，當(dāng)特征向量之間的歐氏距離＞σ時(shí)，判定該特征向量之間不匹配，利用匹配函數(shù)重新定位新的匹配點(diǎn)，重新進(jìn)行匹配，直至測試圖片整個(gè)特征序列結(jié)束。

算法執(zhí)行流程如下:

(1)初始化測試圖片和目標(biāo)圖片，分別將其轉(zhuǎn)化成灰度圖像。

(2)測試圖片和目標(biāo)圖片分別分割成具有相同大小的子圖像，并按圖像內(nèi)容組織成一行序列。

(3)分別對(duì)上述一行序列進(jìn)行SIFT特征提取，以向量的形式存儲(chǔ)。

(4)計(jì)算測試圖片的特征序列和目標(biāo)圖片的特征序列是否相近或相似，如果相似則繼續(xù)匹配，否則轉(zhuǎn)到(5)。

(5)利用匹配函數(shù)計(jì)算出在測試圖片中失效匹配點(diǎn)重新匹配的位置，重復(fù)(4)。

(6)測試圖像特征序列結(jié)束，輸出匹配序列。

4 實(shí)驗(yàn)結(jié)果

本方法利用SIFT對(duì)目標(biāo)分割子圖像進(jìn)行特征提取，將提取出的特征按照子圖像分割的序列進(jìn)行重構(gòu)，目標(biāo)圖像和測試圖像就轉(zhuǎn)換成一行具有特征描述符的序列，對(duì)特征描述符進(jìn)行匹配函數(shù)計(jì)算，進(jìn)行匹配過程。圖片大小直接影響到子圖像的分割和特征序列的生成，同時(shí)提高各個(gè)子圖像不同的特征序列之間的差異性，實(shí)驗(yàn)圖片選取分辨率較高的1500×1500的測試圖片和分辨率為300×300的目標(biāo)圖片，子圖像的大小為15×15，這樣測試圖片就被劃分為10000個(gè)特征序列，目標(biāo)圖像被劃分為400個(gè)特征序列。特征序列之間的相似度和相近程度用歐氏距離來確定，實(shí)驗(yàn)的過程中歐氏距離的誤差閾值σ≤20，當(dāng)歐氏距離在這個(gè)范圍內(nèi)，特征圖片匹配。實(shí)驗(yàn)一方面從單張圖片匹配結(jié)果進(jìn)行討論，另一方面從單張圖片在模板匹配方法，序貫相似性匹配方法和SIFT本身匹配進(jìn)行比較。圖4顯示的是匹配的結(jié)果，圖4(b)中灰色區(qū)域?yàn)槠ヅ涞哪繕?biāo)區(qū)域，如圖5所示，黑色為匹配結(jié)果，從圖中可以看出，除了目標(biāo)區(qū)域被匹配，其他區(qū)域也被匹配，實(shí)驗(yàn)過程中為了降低匹配函數(shù)帶來的負(fù)面影響，在最優(yōu)情況下連續(xù)20個(gè)特征序列匹配，該20個(gè)特征序列就是匹配的區(qū)域，匹配過程中產(chǎn)生的其他匹配是因?yàn)樵谠?0個(gè)特征序列內(nèi)，其相似程度的歐氏距離都小于閾值σ≤20，由于增大了連續(xù)匹配成功的特征序列的長度以及減小特征序列的相似度的閾值，使得匹配的結(jié)果較為合理。實(shí)驗(yàn)的目標(biāo)區(qū)域特征為房屋建筑，具有棱角和直線的特征，在區(qū)域劃分很小的情況下很難區(qū)分出來，導(dǎo)致結(jié)果在房屋建筑上匹配有誤差。

圖4 分辨率為的測試結(jié)果

圖5 目標(biāo)圖片

匹配函數(shù)在目的上解決了重新匹配的新配點(diǎn)的計(jì)算，同時(shí)又是以局部特征為匹配，而不是以單純的像素點(diǎn)來匹配，加大了匹配的速度，其匹配執(zhí)行速度要高于模板匹配，序貫相似匹配方法和SIFT本身匹配進(jìn)行比較，表1顯示了在上述匹配方法執(zhí)行速度。

表1 3種匹配方法的執(zhí)行速度

5 結(jié)束語

文中主要利用提出的匹配函數(shù)來對(duì)圖像匹配進(jìn)行快速匹配，加快圖像匹配的速度，關(guān)鍵點(diǎn)在于子圖像的劃分和局部特征提取，子圖像的大小直接影響到局部特征的提取，子圖像太小，局部細(xì)節(jié)丟失嚴(yán)重，特征序列之間的相關(guān)性丟失，匹配函數(shù)匹配重復(fù)計(jì)算率提高，子圖像太大，特征序列之間相關(guān)性過大和寬度過短，匹配函數(shù)不起作用。局部特征提取才用SIFT特征提取，一方面SIFT特征在全局圖像匹配中具有良好的匹配結(jié)果，在其基礎(chǔ)上加快處理速度。因子圖像的劃分和相似度的閾值是根據(jù)仿真和先驗(yàn)只是初步估算，接下來的工作主要研究子圖像大小的劃分和局部特征的提取，從圖像本身特征的角度自適應(yīng)劃分子圖像的大小以及對(duì)其局部特征的提取。

［1］LOWE D G.Distinctive image features from scale－ invariant keypoints［J］.International Journal of Computer Vision(S0920 －5691)，2004，60(2):91 －110.

［2］MIKOLAJCZYK K，CORDELIA S.Scale ＆ affine invariant interest point detectors［J］.International Journal of Computer Vision(S0920 －5691)，2004，60(1):63 －86.

［3］MIKOLAJCZYK K，TUYTELAARS T，SCHMID C，et al.A comparison of affine region detectors［J］.International Journal of Computer Vision(S0920 － 5691)，2005，65(1):43－72.

［4］MIKOLAJCZYK K，CORDELIA S.A performance evaluation of local descriptors［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence(S0162 － 8828)，2005，27(10):1615－1630.

［5］ZHAO Zhenbing，WANG Rui.A method of infrared/visible image matching based on edge extraction［C］.International Congress on Image and Signal Processing，2010:871 －874.

［6］田金文，楊磊.基于局部分形特征的快速圖像匹配方法［J］.華中理工大學(xué)學(xué)報(bào)，1996，24(2):12 －14.

［7］劉小軍，楊杰.基于主成分分析的放射不變特征圖像匹配方法［J］.系統(tǒng)仿真學(xué)報(bào)，2004，20(4):977 －980.

［8］ELLIS H，SARTAJ S.Fundamentals of data structures in C［M］.2 ed.，Berlin:Springer Press，2003.