魏利勝 ，周圣文

1.安徽工程大學(xué) 電氣工程學(xué)院，安徽 蕪湖 241000

2.上海大學(xué) 機(jī)電工程與自動(dòng)化學(xué)院，上海 200072

圖像匹配是虛擬現(xiàn)實(shí)、機(jī)器視覺(jué)等領(lǐng)域的一個(gè)研究熱點(diǎn)[1]，被廣泛應(yīng)用于遠(yuǎn)程監(jiān)控、工業(yè)機(jī)器人、地質(zhì)勘探、醫(yī)療診斷以及汽車電子等領(lǐng)域[2]。它主要包括圖像配準(zhǔn)和圖像融合兩個(gè)方面。當(dāng)前，許多科研人員對(duì)圖像配準(zhǔn)技術(shù)及應(yīng)用進(jìn)行了深入研究，取得了豐碩的成果。

Lowe[3]于1999年提出了尺度不變特征變換（Scale Invariant Feature Transform，SIFT）圖像配準(zhǔn)算法，該方法在仿射、旋轉(zhuǎn)、縮放、遮蔽、光照等方面均具有較好的不變性，其配準(zhǔn)精度高，而得到廣泛應(yīng)用；張凱等[4]將SIFT算法運(yùn)用于智能對(duì)靶施藥系統(tǒng)中的圖像特征匹配，實(shí)現(xiàn)高噪聲環(huán)境下的紅掌圖像快速有效的拼接；傅衛(wèi)平等[5]利用SIFT算法進(jìn)行圖像初次匹配，并計(jì)算出仿射變換的參數(shù)，以推導(dǎo)出復(fù)雜環(huán)境中圖像目標(biāo)的形心位置及其坐標(biāo)定位；在文獻(xiàn)[6]中，朱梅華等將SIFT算法用于處理卷煙小包裝的圖像配準(zhǔn)中，取得了良好的效果。然而，傳統(tǒng)SIFT算法耗時(shí)較長(zhǎng)，導(dǎo)致其在實(shí)時(shí)性要求較高的應(yīng)用場(chǎng)合受到制約[2，7]。因此，如何提高SIFT算法的實(shí)時(shí)性已成為國(guó)內(nèi)外學(xué)者的探索焦點(diǎn)[8-14]。李芳芳等[8]通過(guò)自適應(yīng)選擇高斯核函數(shù)的尺寸大小，并通過(guò)構(gòu)建三角網(wǎng)法進(jìn)行小面元微分糾正配準(zhǔn)，以提高SIFT算法的實(shí)時(shí)性；張謙等[9]利用均勻網(wǎng)格分割圖像，以網(wǎng)格數(shù)量及其局部區(qū)域熵來(lái)決定特征點(diǎn)數(shù)量、分布，并在此基礎(chǔ)上采用放射變換進(jìn)行特征匹配，以達(dá)到配準(zhǔn)效率高和實(shí)時(shí)性好的目的；在文獻(xiàn)[10]中，熊自明等將SIFT算法和Harris特征點(diǎn)進(jìn)行結(jié)合，以Harris特征點(diǎn)作為待匹配特征點(diǎn)，并利用主成分分析法（Principle Component Analysis，PCA）得到降維后的特征向量，大大提升了SIFT算法的配準(zhǔn)效率；王民等在文獻(xiàn)[11]中采用DOG尺度空間提取Harris算子作為圖像的特征點(diǎn)，提出了一種基于Harris角點(diǎn)的SIFT立體匹配方法；Sukthankar等[12]也通過(guò)PCA法將特征向量維數(shù)由128維降到20維，以提升原算法實(shí)時(shí)性；趙壘等[13]以特征圓環(huán)領(lǐng)域代替方形區(qū)域進(jìn)行特征向量計(jì)算并進(jìn)行排序，省去特征點(diǎn)主方向計(jì)算，減少了特征描述符維數(shù)；另外，王田甲等[14]提出了一種在方形鄰域內(nèi)提取60維描述子的SIFT匹配算法，Bay使用近似Hessian矩陣進(jìn)行關(guān)鍵點(diǎn)提取，同時(shí)引入haar小波變換進(jìn)行特征方向以及特征描述符計(jì)算，生成64維特征向量，以提升算法的匹配效率和準(zhǔn)確性。

以上文獻(xiàn)主要集中于SIFT算法特征點(diǎn)的提取以及后續(xù)匹配算法的改進(jìn)，并取得了一定的成果。本文將在以上研究基礎(chǔ)上，通過(guò)極值特性約束條件和降采樣預(yù)處理，利用差分尺度空間的局部單極值，實(shí)現(xiàn)重合區(qū)域特征提取和匹配，以減小冗余特征點(diǎn)，從而有效提高匹配速度和配準(zhǔn)精度。

1 重合區(qū)極值特征提取法

圖像配準(zhǔn)的過(guò)程主要包括圖像特征點(diǎn)的提取、匹配以及坐標(biāo)變換三個(gè)環(huán)節(jié)[15]，即：利用SIFT算法來(lái)提取圖像特征點(diǎn)，生成特征向量；然后，利用最近鄰次近鄰歐式距離之比進(jìn)行粗匹配；再進(jìn)一步采用RANSAC算法進(jìn)行精匹配，計(jì)算得到圖像拼接變換矩陣H；最后，使用變換矩陣H將待配準(zhǔn)的兩幅圖像變換在同一坐標(biāo)系下進(jìn)行圖像匹配。SIFT算法實(shí)時(shí)性、精確度在很大程度上受特征點(diǎn)對(duì)數(shù)量的影響，且特征點(diǎn)粗匹配的精確率直接影響RANSAC算法抽樣次數(shù)。為此，本文在特征匹配的過(guò)程中，只考慮重疊區(qū)域的特征點(diǎn)對(duì)，從而剔除重疊區(qū)域以外的特征點(diǎn)對(duì)，以減小圖像配準(zhǔn)過(guò)程中的無(wú)用計(jì)算和錯(cuò)誤匹配。

考慮到圖像匹配點(diǎn)對(duì)極值具有一致性的特點(diǎn)，即同為極大值或同為極小值[16]，而傳統(tǒng)SIFT算法并未考慮該約束條件，對(duì)極大和極小值組成的特征集均進(jìn)行搜索匹配，會(huì)增大圖像誤匹配率和匹配時(shí)間。假設(shè)特征點(diǎn)集A極大值點(diǎn)和極小值點(diǎn)分別為m、n，特征點(diǎn)集B中分別為m′、n′。若采用窮舉搜索的話，搜索次數(shù)為：

而利用極值約束條件后，極大值只在極大值之間進(jìn)行搜索，極小值同理，搜索次數(shù)變?yōu)椋?/p>

僅選擇極大值或極小值時(shí)作為特征點(diǎn)時(shí)，搜索次數(shù)則為：

由式（1）～（3）得到k2＜k1＜k，可見，極值約束條件下能夠有效降低搜索次數(shù)，若僅選擇一種極值點(diǎn)作為特征點(diǎn)不僅能夠降低特征提取數(shù)量，從而減少特征提取過(guò)程耗時(shí)，且可以有效減少搜索次數(shù)；另外，傳統(tǒng)SIFT算法是在極大和極小值所組成的特征集中進(jìn)行搜索匹配，會(huì)造成誤匹配率的增加，因此利用重合區(qū)單極值作為待匹配特征點(diǎn)，將大大減少冗余特征點(diǎn)對(duì)數(shù)量，可有效提高SIFT算法的實(shí)時(shí)性以及匹配率。

2 圖像降采樣預(yù)處理法

針對(duì)傳統(tǒng)SIFT算法實(shí)時(shí)性差的問(wèn)題，本章將進(jìn)一步采用圖像有下限降采樣預(yù)處理方法，以縮小圖像尺寸，并根據(jù)拍攝設(shè)備位置關(guān)聯(lián)性這一約束條件估計(jì)出圖像重合區(qū)域；然后依據(jù)極大值特征點(diǎn)對(duì)提取法，減少特征點(diǎn)對(duì)的數(shù)量；最后，通過(guò)計(jì)算未縮放前原始圖像變換矩陣H與降采樣后的變換矩陣H1之間的關(guān)聯(lián)性，將原始圖像變換同一坐標(biāo)系下完成原圖像配準(zhǔn)工作，以提高SIFT算法的實(shí)時(shí)性。其流程圖如圖1所示。

圖1 改進(jìn)SIFT算法配準(zhǔn)流程圖

圖1中的改進(jìn)SIFT算法配準(zhǔn)流程主要包括三個(gè)部分：（1）有下限降采樣過(guò)程；（2）重合區(qū)極大值提取法，利用該方法提取圖像特征并匹配，得到縮小后圖像變換矩陣H1；（3）根據(jù)變換矩陣之間的關(guān)聯(lián)性，推導(dǎo)原始圖像之間坐標(biāo)變換，實(shí)現(xiàn)原始圖像配準(zhǔn)。

2.1 圖像降采樣預(yù)處理

原SIFT算法通過(guò)尋找待配準(zhǔn)圖像間的匹配特征點(diǎn)對(duì)實(shí)現(xiàn)圖像變換矩陣H的求解，以完成圖像配準(zhǔn)[16]。設(shè) (x，y)(，)是原圖像的一對(duì)匹配特征點(diǎn)對(duì)，其變換矩陣H如式（4）所示：

可見至少需要四對(duì)正確的匹配特征點(diǎn)對(duì)才能完成變換矩陣H相關(guān)參數(shù)的求解。通常情況下大尺度圖像會(huì)產(chǎn)生大量冗余特征點(diǎn)以及匹配點(diǎn)對(duì)數(shù)量，使得圖像配準(zhǔn)所用時(shí)間大大增加。文獻(xiàn)[17]通過(guò)對(duì)圖像進(jìn)行降采樣預(yù)處理，對(duì)不同采樣倍數(shù)和不同插值方法進(jìn)行對(duì)比，發(fā)現(xiàn)圖像降采樣80%～90%時(shí)，能滿足匹配的精度和匹配點(diǎn)對(duì)數(shù)量，并相對(duì)原算法減少了20%～30%的配準(zhǔn)時(shí)間。因此，本文將在文獻(xiàn)[17]的基礎(chǔ)上，以尺寸（180×180）為限對(duì)原圖像進(jìn)行三次卷積內(nèi)插降采樣預(yù)處理，并保持待配準(zhǔn)圖像之間降采樣比例相同，有效減少冗余特征點(diǎn)以提升圖像配準(zhǔn)的實(shí)時(shí)性。為此，需要先計(jì)算出降采樣后圖像的變換矩陣H1與原始圖像間的變換矩陣H之間的關(guān)聯(lián)性。

2.2 變換矩陣之間關(guān)聯(lián)性

圖像進(jìn)行降采樣預(yù)處理之后，特征提取及匹配均是在縮小后的圖像上進(jìn)行，因此式（6）圖像之間變換矩陣H1是縮小后圖像之間的變換矩陣。若直接采用縮小后的圖像進(jìn)行配準(zhǔn)，會(huì)嚴(yán)重影響圖像的分辨率。為此，需要求取原始圖像之間的變換矩陣H和預(yù)處理后的變換矩陣H1之間的關(guān)聯(lián)性。本文通過(guò)計(jì)算出縮放后圖像之間的變換矩陣，然后利用縮放系數(shù)，以推導(dǎo)出縮放前后圖像兩變換矩陣之間的關(guān)系，從而得到原圖像之間的變換矩陣，以實(shí)現(xiàn)圖像之間坐標(biāo)變換。

設(shè)兩待配準(zhǔn)圖像大小分別為 (m，n)、(k，l)，則降采樣比例p和變換矩陣H1如下所示：

可見：

由上式可得：

根據(jù)原圖像的一對(duì)匹配特征點(diǎn)對(duì)變換矩陣H，可知：

將式（13）～（14）代入式（9）～（10）并化簡(jiǎn)，可知：

根據(jù)式（15）和式（11）～（12）可以得到：

可見，根據(jù)式（16）可以推導(dǎo)降采樣圖像的變換矩陣H1與原始圖像間的變換矩陣H之間的變換關(guān)系，從而實(shí)現(xiàn)原始圖像間的配準(zhǔn)，減少圖像匹配的時(shí)間。

3 實(shí)驗(yàn)驗(yàn)證

本實(shí)驗(yàn)平臺(tái)為Window XP操作系統(tǒng)，CPU為3.3 GHz，內(nèi)存2 GB，編程環(huán)境Matlab 7.0，原始圖像大小為768×1 280，如圖2所示，其中圖（a）為左鏡頭拍攝的圖像，而圖（b）為右鏡頭拍攝圖像。下面將重點(diǎn)探討如何基于優(yōu)化SIFT方法對(duì)兩幅圖像進(jìn)行拼接實(shí)驗(yàn)。

圖2 配準(zhǔn)圖像

實(shí)驗(yàn)1基于重合區(qū)極大值特征提取法

為了能夠明確改進(jìn)方法與傳統(tǒng)SIFT特征提取的效率，選擇SIFT特征提取時(shí)間、粗匹配率以及精匹配率三個(gè)指標(biāo)進(jìn)行對(duì)比，如下：

利用實(shí)驗(yàn)可得傳統(tǒng)SIFT算法特征點(diǎn)分布以及改進(jìn)的重合區(qū)極大值特征分布圖如3所示。

圖3 圖像特征點(diǎn)提取分布圖

圖3（a）表示傳統(tǒng)SIFT算法提取特征點(diǎn)分布結(jié)果，圖3（b）表示改進(jìn)的基于重合區(qū)極大值提取特征點(diǎn)分布結(jié)果，紅色代表所提取的特征點(diǎn)，可見，改進(jìn)后的圖像特征點(diǎn)數(shù)量得到了明顯的降低。

由表1可知，經(jīng)過(guò)選取圖像重合區(qū)域后，在重合區(qū)域采用圖像極大值（或極小值）作為圖像特征點(diǎn)，能有效去除無(wú)效特征點(diǎn)數(shù)量，特征點(diǎn)數(shù)縮小約75%，且粗匹配與精匹配準(zhǔn)確率均得到大幅度提高，其中粗匹配率提高20.9%，精匹配率提高34.7%，總共匹配用時(shí)由103.516 s縮減到13.515 s，可見改進(jìn)方法大幅度縮減了時(shí)間消耗，提高了圖像匹配的實(shí)時(shí)性。經(jīng)過(guò)配準(zhǔn)后，得到的拼接效果如圖4所示。

表1 實(shí)驗(yàn)數(shù)據(jù)分析表

實(shí)驗(yàn)2降采樣預(yù)處理配準(zhǔn)法

為了進(jìn)一步驗(yàn)證降采樣預(yù)處理方法的有效性，先將圖像尺寸縮小，通過(guò)式（4）、（6）以及（16）之間的關(guān)聯(lián)性，對(duì)原始圖像進(jìn)行拼接實(shí)驗(yàn)，其提取的特征點(diǎn)分布結(jié)果如圖5所示。

從圖5中可知，采用降采樣預(yù)處理配準(zhǔn)法后，圖像的特征點(diǎn)數(shù)量得到了進(jìn)一步的降低。

圖4 拼接效果圖

圖5 降采樣預(yù)處理特征點(diǎn)提取分布圖

表2 實(shí)驗(yàn)數(shù)據(jù)分析表

由表2可知，基于圖像尺寸降采樣預(yù)處理，能進(jìn)一步去除無(wú)效特征點(diǎn)數(shù)量，減少冗余特征點(diǎn)，特征點(diǎn)數(shù)由傳統(tǒng)SIFT算法的3 251個(gè)降低為121個(gè)，其粗匹配率由11.5%提高到23.97%、精匹配率由60.4%提高到96.6%，總共匹配用時(shí)由103.516 s縮減到1.102 s，可見改進(jìn)后的圖像匹配方法能大幅度縮減時(shí)間消耗，提高了圖像匹配的實(shí)時(shí)性以及配準(zhǔn)精度。

經(jīng)過(guò)配準(zhǔn)后，得到的拼接效果如圖6所示，其中（a）表示采用傳統(tǒng)SIFT算法拼接的效果圖，（b）表示采用文獻(xiàn)[17]的降采樣算法拼接的效果圖，（c）表示采用降采樣+重合區(qū)極大值優(yōu)化方法拼接的效果圖。

4 結(jié)束語(yǔ)

本文在對(duì)傳統(tǒng)SIFT圖像拼接算法相關(guān)理論研究基礎(chǔ)上，提出了兩種改進(jìn)的SIFT算法，首先，通過(guò)尋找重疊區(qū)的策略來(lái)降低特征點(diǎn)對(duì)的數(shù)量，從而有效減少了原SIFT算法的復(fù)雜度和配準(zhǔn)時(shí)間；在此基礎(chǔ)上，采用極大值匹配方法和圖像降采樣預(yù)處理方法，以有效消除重復(fù)和錯(cuò)誤匹配。實(shí)驗(yàn)結(jié)果表明本文所提算法比傳統(tǒng)SIFT算法在圖像配準(zhǔn)中取得了更高的配準(zhǔn)速度和精度。

圖6 拼接效果圖

[1]呂娜，馮祖仁.圖像匹配與跟蹤研究[J].西安交通大學(xué)學(xué)報(bào)，2010，44（10）.

[2]白廷柱，侯喜報(bào).基于SIFT算子的圖像匹配算法研究[J].北京理工大學(xué)學(xué)報(bào)，2013，33（6）：622-627.

[3]Qi Zhi，Cooperstock J R.Toward dynamic image mosaic generation with robustness to parallax[J].IEEE Transactions on Image Processing，2012，21（1）：366-378.

[4]張凱，耿長(zhǎng)興，張二鵬，等.溫室環(huán)境下紅掌圖像拼接算法[J].農(nóng)業(yè)機(jī)械學(xué)報(bào)，2013，44（4）：223-227.

[5]傅衛(wèi)平，秦川，劉佳，等.基于SIFT算法的圖像目標(biāo)匹配與定位[J].儀器儀表學(xué)報(bào)，2011，32（1）：163-169.

[6]朱梅華，魏承科，張素偉.SIFT算法在卷煙小包裝圖像配準(zhǔn)中的應(yīng)用[J].計(jì)算機(jī)工程與應(yīng)用，2012，48（21）：244-248.

[7]Kim B S，Lee S H，Cho N I.Real-time panorama canvas ofnaturalimages[J].IEEE Transactions on Consumer Electronics，2011，57（4）：1961-1968.

[8]李芳芳，肖本林，賈永紅，等.算法優(yōu)化及其用于遙感影像自動(dòng)配準(zhǔn)[J].武漢大學(xué)學(xué)報(bào)，2009，34（10）：1245-1249.

[9]張謙，賈永紅，胡忠文.遙感影像配準(zhǔn)中的SIFT特征匹配改進(jìn)[J].微電子學(xué)與計(jì)算機(jī)，2013，38（4）：455-459.

[10]熊自明，萬(wàn)剛，閆鶴，等.SIFT算法的小型無(wú)人機(jī)航拍圖像自動(dòng)配準(zhǔn)[J].繪測(cè)科學(xué)技術(shù)學(xué)報(bào)，2012，29（2）：153-156.

[11]王民，劉偉光.基于改進(jìn)SIFT特征的雙目圖像匹配算法[J].計(jì)算機(jī)工程與應(yīng)用，2013，49（2）：203-206.

[12]Ke Y，Sukthankar R.PCA-SIFT：a more distinctive representation for local image descriptors[C]//Proceedings of the Conference on Computer Vision and Pattern Recognition，Washington，USA，2004：511-517.

[13]趙壘，侯振杰.一種改進(jìn)的SIFT圖像配準(zhǔn)方法[J].計(jì)算機(jī)工程，2012，36（12）：226-228.

[14]王田甲，劉國(guó)榮.SIFT改進(jìn)算法在圖像配準(zhǔn)中的應(yīng)用[J].微電子學(xué)與計(jì)算機(jī)，2011，28（5）：184-188.

[15]劉健，張國(guó)華，黃琳琳.基于改進(jìn)SIFT的圖像配準(zhǔn)算法[J].北京航空航天大學(xué)學(xué)報(bào)，2010，36（9）：1121-1124.

[16]Zhou Wu，Goshtasby A.Adaptive image registration via hierarchical voronoi subdivision[J].IEEE Transactions on Image Processing，2012，21（5）：2464-2473.

[17]王書民，張愛(ài)武，崔營(yíng)營(yíng).基于降采樣處理的低空遙感影像SIFT特征匹配分析[J].測(cè)繪通報(bào)，2011（9）：18-20.