王小鵬，房超，雷濤

蘭州交通大學(xué)電子與信息工程學(xué)院，蘭州 730070

一種平移旋轉(zhuǎn)圖像的角點(diǎn)匹配方法

王小鵬，房超，雷濤

蘭州交通大學(xué)電子與信息工程學(xué)院，蘭州 730070

在圖像角點(diǎn)匹配過程中，目標(biāo)圖像往往存在平移旋轉(zhuǎn)現(xiàn)象，直接影響匹配效果，為此提出了一種平移旋轉(zhuǎn)圖像的角點(diǎn)匹配方法。該方法首先利用角點(diǎn)檢測生成自相關(guān)矩陣的梯度信息與仿射變換相結(jié)合，構(gòu)造確定性退火算法中的自由能函數(shù)，然后對該自由能函數(shù)進(jìn)行優(yōu)化，獲取待匹配角點(diǎn)間的仿射變換參數(shù)，最后利用該變換參數(shù)實(shí)現(xiàn)角點(diǎn)匹配。實(shí)驗(yàn)結(jié)果表明，該方法能夠在目標(biāo)圖像發(fā)生平移旋轉(zhuǎn)的情況下，有效實(shí)現(xiàn)角點(diǎn)匹配。

角點(diǎn)匹配；平移旋轉(zhuǎn)；確定性退火；仿射變換

1 引言

角點(diǎn)匹配指利用同一場景中采集到的兩幅圖像角點(diǎn)信息，確定待匹配角點(diǎn)間相對位置關(guān)系的過程，在數(shù)字圖像處理、計(jì)算機(jī)視覺以及和模式識別等領(lǐng)域有重要應(yīng)用價(jià)值。目前已提出了許多角點(diǎn)匹配算法，其中基于圖像點(diǎn)特征及灰度信息的角點(diǎn)匹配算法[1]，利用局部灰度相關(guān)實(shí)現(xiàn)角點(diǎn)匹配；基于位置相似性特征的角點(diǎn)匹配算法[2]，利用局部范圍內(nèi)對應(yīng)點(diǎn)的相對位置不變作為約束條件實(shí)現(xiàn)角點(diǎn)匹配；基于Hausdorff距離的角點(diǎn)匹配[3]，利用待匹配角點(diǎn)間的Hausdorff距離實(shí)現(xiàn)角點(diǎn)匹配；基于圖像亮度相關(guān)的角點(diǎn)匹配[4]，利用光流法與一階差分技術(shù)實(shí)現(xiàn)角點(diǎn)匹配；基于確定性退火技術(shù)魯棒性點(diǎn)匹配算法[5]，利用匹配矩陣估計(jì)方法構(gòu)造自由能函數(shù)，最終實(shí)現(xiàn)角點(diǎn)匹配。

在圖像采集過程中，由于拍攝角度不同會導(dǎo)致圖像在空間上存在平移、旋轉(zhuǎn)等差異，這些差異會影響角點(diǎn)匹配的精度。由于仿射變換[6]能夠有效獲取圖像間的平移和旋轉(zhuǎn)參數(shù)，從而可以消除平移旋轉(zhuǎn)等對角點(diǎn)匹配的影響。通過仿射變換的同素性與平行性可將角點(diǎn)匹配過程轉(zhuǎn)化為求解角點(diǎn)間仿射變換參數(shù)的過程。為此本文將角點(diǎn)檢測與確定性退火技術(shù)[7]相結(jié)合，利用角點(diǎn)檢測時(shí)生成自相關(guān)矩陣梯度信息構(gòu)造退火過程的自由能函數(shù)，并運(yùn)用確定性退火技術(shù)自由能函數(shù)收斂到全局最優(yōu)解的性質(zhì)，對角點(diǎn)匹配自由能函數(shù)進(jìn)行優(yōu)化處理，獲取兩匹配圖像角點(diǎn)間的仿射變換參數(shù)，最后通過該參數(shù)實(shí)現(xiàn)角點(diǎn)匹配。

2 角點(diǎn)匹配流程

提出的角點(diǎn)匹配流程如圖1所示。首先利用Harris算子[8]對目標(biāo)和模板圖像分別進(jìn)行角點(diǎn)檢測，然后將確定性退火技術(shù)應(yīng)用于角點(diǎn)匹配過程中，通過構(gòu)造自由能函數(shù)與優(yōu)化自由能函數(shù)獲取待匹配角點(diǎn)間的仿射變換參數(shù)，最后利用該參數(shù)實(shí)現(xiàn)角點(diǎn)匹配。

圖1 角點(diǎn)匹配流程圖

3 Harris角點(diǎn)檢測

Harris角點(diǎn)檢測[9]是基于圖像灰度的檢測，通過計(jì)算像素點(diǎn)所在位置的梯度變化來檢測角點(diǎn)，若像素點(diǎn)所在位置x方向梯度與y方向梯度的絕對值均較大，則將該像素點(diǎn)判定為角點(diǎn)。

其中detM=λ1×λ2，trM是矩陣M的跡，且trM=λ1+λ2，k為大于零的參數(shù)。通常，detM在邊緣處較小而在角點(diǎn)處較大，而trM在邊緣和角點(diǎn)處則保持一致。因此，當(dāng)像素點(diǎn)(x，y)的Rh值為局部最大時(shí)，即為角點(diǎn)。

4 仿射變換參數(shù)確定

當(dāng)獲取目標(biāo)和模板圖像的角點(diǎn)信息后，如何對角點(diǎn)進(jìn)行匹配直接關(guān)系到匹配精度。由于目標(biāo)圖像可能存在平移旋轉(zhuǎn)，因此如何獲取最優(yōu)的仿射變換參數(shù)是實(shí)現(xiàn)匹配結(jié)果的關(guān)鍵，求得的仿射變換參數(shù)一方面應(yīng)能消除平移旋轉(zhuǎn)的影響，另一方面應(yīng)能保證更多的匹配點(diǎn)數(shù)。為此，本文運(yùn)用確定性退火過程來獲取最優(yōu)仿射變換參數(shù)。

確定性退火技術(shù)是依據(jù)自然法則提出的一種求解全局最優(yōu)解的擬自然方法，將求解一系列隨溫度變化的物理系統(tǒng)自由能函數(shù)極小值思想引入到求解優(yōu)化問題，它能使算法直接得到全局極小值，無需考慮局部極小值對優(yōu)化問題的影響。

退火過程利用自由能減少定律描述系統(tǒng)在每一溫度下達(dá)到平衡態(tài)的過程。由自由能減少定律可得：

其中E(x)是指某一物理系統(tǒng)的能量，當(dāng)系統(tǒng)達(dá)到平衡狀態(tài)時(shí)自由能函數(shù)達(dá)到極小值。確定性退火技術(shù)要求構(gòu)造物理系統(tǒng)式（2）對應(yīng)的自由能函數(shù)F(x，T)。此函數(shù)F(x，T)應(yīng)滿足：

（1）當(dāng)T=∞時(shí)，F(xiàn)(x，T)的全局極小值易求出。

（2）當(dāng)T=0時(shí)，F(xiàn)(x，T)=E(x)。確定性退火技術(shù)就是將系統(tǒng)在T=T+ΔT時(shí)的自由能函數(shù)的極小值xmin(T+ΔT)作為初始值，通過求解m inF(x，T)的極小值來模擬系統(tǒng)達(dá)到平衡狀態(tài)的過程。確定性退火的求解過程如下：

步驟1確定系統(tǒng)自由能函數(shù)F(x，T)，使F(x，T)滿足上述兩個(gè)條件。

步驟2初始化T=T0，記xmin(Tk)為m inF(x，Tk)的最優(yōu)解。

步驟3Tk+1=αTk(0＜α＜1)，以xmin(T0)為初始值求解m inF(x，Tk+1)，記相應(yīng)最優(yōu)解為xmin(Tk+1)，其中α為退火速率。

步驟4判斷Tk是否收斂，若滿足則停止，則xmin(Tk+1)為最優(yōu)解，否則執(zhí)行下一步。

步驟5k=k+1，執(zhí)行步驟3。

4.1 自由能函數(shù)構(gòu)造

能否構(gòu)造出合適的自由能函數(shù)是角點(diǎn)匹配的關(guān)鍵，構(gòu)造出的自由能函數(shù)應(yīng)包含待匹配角點(diǎn)間的仿射變換參數(shù)。為了求取最優(yōu)仿射變換參數(shù)，將仿射變換與角點(diǎn)檢測中自相關(guān)矩陣梯度[10]信息結(jié)合構(gòu)造自由能函數(shù)。

仿射變換的一般表達(dá)式為：

其中PA={(xa1,ya1),(xa2,ya2),(xa3,ya3),…,(xam,yam)}和PB= {(xb1，yb1)，(xb2，yb2)，(xb3，yb3)，…，(xbn，ybn)}，分別表示目標(biāo)圖像與模板圖像中待匹配的角點(diǎn)坐標(biāo)，A是旋轉(zhuǎn)矩陣，T為平移矩陣。旋轉(zhuǎn)和平移參數(shù)矩陣決定了待匹配角點(diǎn)間的坐標(biāo)變換關(guān)系。設(shè)V為仿射變換算子，則二維空間的仿射變換可表示為：

其中θ為旋轉(zhuǎn)角度，tx，ty為平移量。

由角點(diǎn)檢測自相關(guān)矩陣M可知，XY梯度算子包含了水平與垂直方向的梯度信息。因此利用X和Y的乘積重新描述每一個(gè)角點(diǎn)。假設(shè)GXY為某一角點(diǎn)在水平與垂直方向的梯度值之積，則可將通過仿射變換后的目標(biāo)圖像與模板圖像角點(diǎn)的GXY絕對值差之和GXY作為角點(diǎn)是否匹配的依據(jù)，即：

其中P與Q是兩個(gè)ω×ω大小的窗口，其中心位于待匹配角點(diǎn)，ε為給定閾值，a和b分別是P與Q中的角點(diǎn)。當(dāng)GXY值最小時(shí)，則可以判定兩個(gè)角點(diǎn)匹配。

E(θ，tx，ty)值表征在仿射變換V的作用下，兩個(gè)角點(diǎn)集PA與PB的匹配點(diǎn)數(shù)。物理退火過程的自由能函數(shù)采用Boltzman概率分布，其分布表示為：

其中，EN為新能量值，E為原始能量，T為溫度值，ΔE=EN-E。

根據(jù)能量函數(shù)可以構(gòu)造出如下函數(shù)：

由于F(θ，tx，ty，T)具有上述兩個(gè)性質(zhì)，因此可以將其作為角點(diǎn)匹配時(shí)的自由能函數(shù)。

4.2 自由能函數(shù)優(yōu)化

自由能函數(shù)優(yōu)化的目的是為了求取最優(yōu)的仿射變換參數(shù)，利用該參數(shù)對待匹配點(diǎn)集進(jìn)行匹配，獲得角點(diǎn)集之間的對應(yīng)關(guān)系實(shí)現(xiàn)角點(diǎn)匹配。

自由能函數(shù)優(yōu)化處理步驟如下：

步驟1退火系統(tǒng)初始化：T=T0，θ=θ0，tx=tx0，ty=ty0，系統(tǒng)最小溫度Tmin，系統(tǒng)退火速率α。

步驟2自由能函數(shù)的優(yōu)化：當(dāng)系統(tǒng)溫度T≥Tmin時(shí)，利用共軛梯度算法對自由能函數(shù)進(jìn)行處理，求得一組平移與旋轉(zhuǎn)參數(shù)，然后將系統(tǒng)溫度T乘以退火速率α作為新的系統(tǒng)溫度T，與系統(tǒng)最小溫度Tmin進(jìn)行比較，若T≥Tmin，則繼續(xù)上述處理；否則停止運(yùn)算，并輸出自由能函數(shù)最小值：m inF(θ，tx，ty，T)=V(θ，tx，ty)，此時(shí)獲取的(θ，tx，ty)為最優(yōu)仿射變換參數(shù)。

步驟3利用最優(yōu)仿射變換參數(shù)對PB中的點(diǎn)進(jìn)行坐標(biāo)變換得到PB'，將PA與PB'中的點(diǎn)進(jìn)行匹配，其中PB'=V(θ，tx，ty)PB。

5 角點(diǎn)匹配

角點(diǎn)匹配的目的是確定待匹配角點(diǎn)間的對應(yīng)關(guān)系，利用Harris角點(diǎn)檢測算法分別獲取待匹配圖像的角點(diǎn)后，運(yùn)用自由能函數(shù)優(yōu)化求取的最優(yōu)仿射變換參數(shù)對角點(diǎn)進(jìn)行匹配。具體步驟如下：

步驟1利用自由能函數(shù)最小化求取最優(yōu)仿射變換參數(shù)V(θ，tx，ty)，對PB進(jìn)行仿射變換得到PB'。

步驟2利用式（5）將待匹配角點(diǎn)進(jìn)行比較，當(dāng)GXY的值達(dá)到最小時(shí)，則判定兩個(gè)角點(diǎn)匹配。

步驟3所有待匹配角點(diǎn)依次執(zhí)行步驟2，完成角點(diǎn)匹配。

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

為了驗(yàn)證方法的有效性，在MATLAB平臺上進(jìn)行了仿真。模板圖像和目標(biāo)圖像均為420×255像素大小，圖2（a）和（b）分別為模板和目標(biāo)圖像，圖2（b）相對于圖2（a）存在平移和旋轉(zhuǎn)現(xiàn)象。首先利用Harris算法對兩幅圖像進(jìn)行角點(diǎn)檢測，結(jié)果如圖2（白色十字為檢測出的角點(diǎn)）所示。

圖2 Harris算法角點(diǎn)檢測結(jié)果

利用本文方法對檢測到的角點(diǎn)進(jìn)行匹配，其中閾值ε=1，初始值T0=100，θ=0°，tx=0，ty=0，Tmin=0.1，退火速率α=0.8，匹配所選用窗口大小為5×5（通常取奇數(shù)對），通過自由能函數(shù)優(yōu)化后得到的仿射變換參數(shù)為：θ=13°，tx=46 pix，ty=9 pix。角點(diǎn)匹配結(jié)果如圖3所示，其中白色十字為匹配角點(diǎn)。

圖3 本文角點(diǎn)匹配方法

為了驗(yàn)證該方法性能，在圖2角點(diǎn)檢測的基礎(chǔ)上，分別采用基于Hausdorff距離[11]的角點(diǎn)匹配和基于歸一化互相關(guān)（NCC）[12]的角點(diǎn)匹配方法進(jìn)行了角點(diǎn)匹配，匹配結(jié)果分別如圖4和圖5所示?？梢钥闯?，本文方法的匹配點(diǎn)數(shù)（具體如表1）明顯多于其他兩種方法。這表明在利用仿射變換參數(shù)實(shí)現(xiàn)角點(diǎn)匹配時(shí)，本文方法充分利用了圖像的特征信息，獲取了最優(yōu)的仿射變換參數(shù)。

圖4 基于Hausdorff距離的角點(diǎn)匹配

圖5 基于歸一化互相關(guān)的角點(diǎn)匹配

從表1也可以看出，本文方法的運(yùn)算復(fù)雜度低于Hausdorff距離的角點(diǎn)匹配，但高于NCC角點(diǎn)匹配方法，但匹配效果明顯優(yōu)于其他兩種方法。

表1 不同匹配方法的匹配點(diǎn)數(shù)及運(yùn)算時(shí)間對比

7 結(jié)論

對于圖像角點(diǎn)匹配過程中由于目標(biāo)圖像存在平移旋轉(zhuǎn)對匹配造成的影響。將角點(diǎn)檢測時(shí)生成的自相關(guān)矩陣梯度信息與仿射變換結(jié)合，通過確定性退火過程中的自由能函數(shù)構(gòu)造以及優(yōu)化獲取最優(yōu)的仿射變換參數(shù)，并以此實(shí)現(xiàn)角點(diǎn)匹配。通過自相關(guān)矩陣的梯度信息構(gòu)造自由能函數(shù)，充分利用了圖像中的特征信息，在一定程度上降低了構(gòu)造自由能函數(shù)的復(fù)雜度。由于獲取了最優(yōu)的仿射變換參數(shù)，因而匹配效果較好。

[1]曹曉光，徐琳，郁文霞.基于角點(diǎn)檢測的高精度點(diǎn)匹配算法[J].儀器儀表學(xué)報(bào)，2006，27（6）：1269-1271.

[2]潘俊君，張艷寧.相關(guān)視覺中基于位置相似性特征的點(diǎn)匹配問題研究[J].中國圖象圖形學(xué)報(bào)，2005，10（1）：80-86.

[3]Huttenlocher D P，K landerman G A，Rucklidge W J.Comparing image using the Hausdorff distance[J].IEEE Trans PAM I，1993，15（9）：850-863.

[4]Georgescu B，Meer P.Point matching under large image deformations and illum ination changes[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2004，26（6）：647-688.

[5]孫東梅，裘正定.基于確定性退火技術(shù)的魯棒性點(diǎn)匹配算法[J].計(jì)算機(jī)學(xué)報(bào)，2002，25（6）：606-611.

[6]Aw rangjeb M，Lu Guojun.An improved curvature scale-space corner detector and a robust corner matching approach[J]. IEEE Transactions on Image Processing，2008，17（12）：2425-2441.

[7]楊廣文，李曉明.確定性退火技術(shù)[J].計(jì)算機(jī)學(xué)報(bào)，1998，21（8）：765-768.

[8]Harris C，Stephens M.A combined corner and edge detector[C]// Proceedings of the 4th A lvey Vision Conference，Manchester，1988：147-151.

[9]趙萬金，龔聲蓉.一種自適應(yīng)的Harris角點(diǎn)檢測算法[J].計(jì)算機(jī)工程，2008，34（10）：212-214.

[10]Alkaabi S，Deravi F.Iterative corner extraction and matching for mosaic construction[C]//Proceeding of 2nd Computer and Robot Vision，British Columbia，Canada，2005：468-475.

[11]孫瑾，顧宏武.一種魯棒性Hausdorff距離圖像匹配方法[J].中國圖像圖形學(xué)報(bào)，2008，13（4）：761-767.

[12]郭偉，趙亦工.一種改進(jìn)的紅外圖像歸一化互相關(guān)匹配算法[J].光子學(xué)報(bào)，2009，38（1）：189-193.

WANG Xiaopeng,FANG Chao,LEI Tao

School of Electronic&Information Engineering,Lanzhou Jiaotong University,Lanzhou 730070,China

During the course of image corner matching,the translation and rotation of object image often affect the matching results.A corner matching method is proposed based on deterministic annealing.Harris corner detection is used to extract the corner points respectively from object and matching image,and the gradient information of the corner points from the autocorrelation matrix are also calculated.The free energy function of deterministic annealing is constructed by combining the gradient information and the affine transform.The optimization affine transform parameters are obtained by optimizing the free energy function.Corner matching between object and matching image are complemented through the affine transform.Simulations show that this method can effectively achieve the corner matching when the object image occurring translation and rotation.

corner matching;translation and rotation;deterministic annealing;affine transform

A

TP391.4

10.3778/j.issn.1002-8331.1209-0290

WANG Xiaopeng,FANG Chao,LEI Tao.Corner matching for translation and rotation image.Computer Engineering and Applications,2014,50（16）：173-176.

國家自然科學(xué)基金（No.61261029，No.61202314）；甘肅省高等學(xué)校碩士生導(dǎo)師科研項(xiàng)目（No.1104-4）。

王小鵬（1969—），博士，教授，研究方向：圖像分析與識別；房超（1987—），碩士研究生，研究方向：圖像處理；雷濤（1981—），博士，副教授，主要研究方向：數(shù)字圖像分析。E-mail：wangxp1969@sina.com

2012-09-25

2012-11-08

1002-8331（2014）16-0173-04

CNKI網(wǎng)絡(luò)優(yōu)先出版：2012-12-18,http://www.cnki.net/kcms/detail/11.2127.TP.20121218.1528.023.htm l