基于圖結(jié)構(gòu)的全景圖自動(dòng)識別與拼接方法

趙毅力，武仲科，張 雁，夏 炎

（1.西南林業(yè)大學(xué) 計(jì)算機(jī)與信息學(xué)院，云南 昆明650224；2.北京師范大學(xué)信息科學(xué)與技術(shù)學(xué)院，北京100875；3.西南林業(yè)大學(xué) 材料工程學(xué)院，云南 昆明650224）

0 引 言

圖像匹配的方法一般分為兩種類型，直接匹配或是基于特征的匹配。直接匹配的方法試圖使用圖像的像素值通過迭代的方法對圖像進(jìn)行配準(zhǔn)［1，2］?；谔卣鞯姆椒ㄔ噲D從圖像中提取出不同類型的特征，例如線特征或點(diǎn)特征，并使用該特征的鄰域信息來進(jìn)行特征匹配［3，4］。

在基于特征的方法中，目前使用較多的是基于不變特征的方法。這類方法根據(jù)點(diǎn)特征的鄰域信息計(jì)算出相應(yīng)的特征描述符用以完成特征檢索和匹配。這方面的工作最早是由Schmid和Mohr提出的，他們的方法通過對Harris角點(diǎn)進(jìn)行高斯求導(dǎo)，形成旋轉(zhuǎn)不變描述符。Lowe對這種方法進(jìn)行了擴(kuò)展，增加了特征的尺度不變性［5］。目前常用的特征點(diǎn)檢測算子包括Harris角點(diǎn)檢測算子、SIFT檢測算子、BRIEF算子［6］和ORB算子［7］。并且在特征點(diǎn)的可重復(fù)性和描述符匹配性能評價(jià)方面也取得了不錯(cuò)的進(jìn)展［8－10］。

基于不變特征的方法已經(jīng)成功地應(yīng)用到很多領(lǐng)域中，包括物體識別［11］、從運(yùn)動(dòng)獲取結(jié)構(gòu)［12］以及全景圖像拼接［13］。雖然對圖像匹配的研究已經(jīng)取得了很多進(jìn)展，仍然有值得研究的空間，特別是在現(xiàn)有的文獻(xiàn)中缺乏對以下兩個(gè)問題的詳細(xì)討論：①如何有效的判別輸入的多幅無序圖像之間是否有重疊部分以及重疊區(qū)域的大?。虎谌绾巫詣?dòng)對屬于同一個(gè)場景的不同圖像進(jìn)行分類并合成相應(yīng)的全景圖像。

基于此，本文提出了一個(gè)基于圖結(jié)構(gòu)的全景圖像自動(dòng)識別和拼接的方法，能夠?qū)斎氲亩喾鶡o序圖像進(jìn)行自動(dòng)分類識別與拼接。該方法首先對輸入圖像進(jìn)行MOPS特征檢測，然后使用k－d樹對特征點(diǎn)進(jìn)行快速匹配，根據(jù)最近鄰特征點(diǎn)距離與次近鄰特征點(diǎn)距離之比得到初始匹配點(diǎn)對。根據(jù)圖像特征點(diǎn)之間的對應(yīng)關(guān)系使用RANSAC算法建立任意兩幅圖像之間的匹配模型，并用概率統(tǒng)計(jì)策略對其進(jìn)行魯棒校驗(yàn)。論文將多圖像匹配問題建模為在不同圖像節(jié)點(diǎn)之間建立無向連通圖的問題，而多圖像拼接的問題可以歸結(jié)為對建立好的一個(gè)或多個(gè)無向連通圖進(jìn)行深度優(yōu)先遍歷。

1 MOPS特征檢測與匹配

為了判別輸入圖像之間是否具有重疊區(qū)域以及圖像之間的運(yùn)動(dòng)模型，首先對圖像進(jìn)行MOPS特征檢測。MOPS（multi－scale oriented patches）算法［14］是 Matthew Brown針對全景圖像拼接中尺度變化相對較小提出的一種特征檢測算法，與 SIFT （scale－invariant feature transform）相 比 具有檢測速度更快的優(yōu)勢。MOPS算法對Harris算法進(jìn)行了擴(kuò)展，為原本不具備旋轉(zhuǎn)不變和尺度不變的Harris算法增加了一定的旋轉(zhuǎn)不變性和尺度不變性。

對于每一幅輸入圖像I（x，y），首先使用子采樣率參數(shù)s＝2，金字塔平滑尺度參數(shù)σp＝1.0構(gòu)造高斯圖像金字塔。然后在金字塔的每一層提取Harris特征點(diǎn)。在金字塔第L層圖像PL（x，y）處的Harris矩陣計(jì)算公式為

式中： ——梯度算子，積分參數(shù)σd＝1.0，gσi——二維高斯卷積函數(shù)，σi＝1.5。為了在金字塔圖像中的每一層檢測特征點(diǎn)，首先需要計(jì)算Harris角點(diǎn)響應(yīng)函數(shù)fHM

式中：det（HL）——矩陣 HL的行列式，tr（HL）——矩陣HL的跡矩陣，λ1和λ2——矩陣HL的特征值。如果金字塔圖像PL（x，y）在 （x，y）處的角點(diǎn)響應(yīng)函數(shù)值在其3x3的鄰域中為最大值，并且大于閾值t，則將其作為候選特征點(diǎn)，在實(shí)驗(yàn)中取參數(shù)t＝10.0。

為了使Harris特征點(diǎn)具備旋轉(zhuǎn)不變性，需要對每一個(gè)候選特征點(diǎn)賦予一個(gè)主方向θ。通過對局部梯度進(jìn)行平滑可以計(jì)算得到方向向量uL

其中積分尺度參數(shù)σo＝4.5。

檢測得到初始的候選特征點(diǎn)后，為了保證特征檢測的穩(wěn)定性，還需要對其進(jìn)行篩選。由于Harris角點(diǎn)響應(yīng)函數(shù)會在圖像的邊界處取得較大的響應(yīng)值，而圖像的邊界對于噪聲比較敏感，會對檢測到的特征點(diǎn)的位置有比較多的影響，因此需要?jiǎng)h除每一層金字塔圖像邊界上的候選特征點(diǎn)。首先對所有候選特征點(diǎn)進(jìn)行順序遍歷，以當(dāng)前特征點(diǎn)為中心構(gòu)造一個(gè)40x40大小的采樣窗口，將這個(gè)窗口旋轉(zhuǎn)和特征點(diǎn)的主方向?qū)R。如果旋轉(zhuǎn)后的窗口有任意部分超出當(dāng)前特征點(diǎn)所在的金字塔圖像的邊界，就將當(dāng)前特征點(diǎn)從候選特征點(diǎn)中刪除。

一旦確定了特征點(diǎn)在金字塔圖像中的位置，還需要為每一個(gè)特征點(diǎn)賦予一個(gè)描述符。這個(gè)描述符是對特征點(diǎn)所在局部區(qū)域的某種描述，并能夠支持不同圖像之間可靠的、有效的特征匹配。給定一個(gè)特征點(diǎn)fp（x，y，level，θ），對以特征點(diǎn)為中心的40x40大小的圖像局部塊進(jìn)行采樣，采樣間隔s＝5。因此可以將特征點(diǎn)局部圖像塊劃分為8x8的子塊，特征向量的每一個(gè)分量是5x5子塊的平均值，共64維。采樣之后，為了使特征描述符向量對光亮度變化具有不變性，還需要對特征描述符向量進(jìn)行歸一化，使其均值為0，標(biāo)準(zhǔn)偏差為1。

如果拼接的是柱面全景圖或球面全景圖，首先需要使用反向映射將每一幅輸入圖像轉(zhuǎn)換為柱面圖像或球面圖像，在轉(zhuǎn)換過程中還需要使用雙線性插值避免在圖像變換中的走樣。然后將每一幅圖像中的特征點(diǎn)通過正向映射也轉(zhuǎn)換到相應(yīng)的柱面坐標(biāo)系或球面坐標(biāo)系中，再進(jìn)行匹配。在對不同圖像之間的特征點(diǎn)進(jìn)行匹配時(shí)，需要對特征向量進(jìn)行最近鄰搜索。論文采用基于k－d樹的最近鄰搜索算法，可以將特征檢索的時(shí)間復(fù)雜度O（N1N2D）降低到O（N1log2N2）。

算法1 基于k－d樹的快速特征匹配

（1）為每一幅圖像的特征點(diǎn)集構(gòu)造一顆k－d樹；

（2）依次對每一幅圖像的每一個(gè)特征點(diǎn)進(jìn)行遍歷。初始時(shí)圖像索引值i＝0，特征點(diǎn)索引值n＝0。對于第i幅圖像的第n個(gè)特征點(diǎn)，對所有其他圖像的k－d樹進(jìn)行檢索，查找和當(dāng)前特征點(diǎn)歐氏距離最近的前兩個(gè)特征點(diǎn)nn1和nn2，其歐氏距離分別為d1和d2。當(dāng)d1和d2的比值小于0.6時(shí)，認(rèn)為nn1是最佳匹配點(diǎn)。

（3）當(dāng)所有圖像的所有特征點(diǎn)都遍歷完成后，還需要對特征匹配的結(jié)果進(jìn)行校驗(yàn)。假設(shè)第i幅圖像中第ni個(gè)特征點(diǎn)的匹配圖像索引值為j，匹配特征點(diǎn)索引值為nij。需要檢查第j幅圖像中第nij個(gè)特征點(diǎn)對應(yīng)于圖像i的匹配特征點(diǎn)索引值是否為ni，如果兩者不相符就認(rèn)為該匹配是錯(cuò)誤的。

2 基于圖結(jié)構(gòu)的多圖像匹配

根據(jù)圖像特征點(diǎn)之間的對應(yīng)關(guān)系就可以建立輸入圖像集合中任意兩幅圖像之間的匹配關(guān)系。可以用無向圖結(jié)構(gòu)來表示這個(gè)計(jì)算過程，每一幅輸入圖像是無向圖中的一個(gè)節(jié)點(diǎn)，如果兩幅圖像之間滿足給定的匹配關(guān)系，則在這兩個(gè)節(jié)點(diǎn)之間存在一條連接線。多圖像匹配問題就是要計(jì)算這個(gè)無向圖結(jié)構(gòu)中所有存在的無向連通圖。

算法2 基于無向圖結(jié)構(gòu)的多圖像匹配

（1）依次對輸入的每一幅圖像進(jìn)行遍歷，初始索引值i＝0；對除了第i幅圖像以外的圖像進(jìn)行遍歷，初始索引值j＝0。如果第i幅圖像和第j幅圖像之間有匹配的特征點(diǎn)對，就將該特征點(diǎn)對加入到第i幅圖像的圖像匹配集合中；

（2）如果第i幅圖像和第j幅圖像之間匹配的特征點(diǎn)數(shù)量大于給定的閾值，則認(rèn)為兩幅圖像之間存在一個(gè)可以計(jì)算的模型，并將第j幅圖像的索引值加入到第i幅圖像的模型集合中；

（3）用 RANSAC （random sample consensus）算法［15］對第i幅圖像和第j幅圖像之間的匹配特征點(diǎn)對進(jìn)行魯棒校驗(yàn)，剔除外點(diǎn)，同時(shí)求出兩幅圖像之間的運(yùn)動(dòng)模型參數(shù)。

對于每一對潛在的匹配圖像之間都存在兩組不同類型的匹配特征點(diǎn)對，一組是符合運(yùn)動(dòng)模型幾何一致性的特征點(diǎn)對，一組是幾何不一致性的特征點(diǎn)對。論文使用基于統(tǒng)計(jì)的策略對圖像匹配進(jìn)行魯棒校驗(yàn)?；舅枷胧潜容^這一組內(nèi)點(diǎn)／外點(diǎn)是由一個(gè)正確的圖像匹配或者錯(cuò)誤的圖像匹配產(chǎn)生的概率大小。對于一幅給定的圖像，用nf表示這幅圖像在重疊區(qū)域中的特征點(diǎn)數(shù)目，ni表示這幅圖像在重疊區(qū)域中的內(nèi)點(diǎn)數(shù)目?？梢杂梅?－1分布的隨機(jī)變量m來表示隨機(jī)事件 “這幅圖像匹配正確或錯(cuò)誤”。假設(shè)事件 “第i個(gè)匹配點(diǎn)對f（i）∈ ｛ 0，1｝是內(nèi)點(diǎn)／外點(diǎn)”是n重伯努利實(shí)驗(yàn)，那么隨機(jī)變量 “內(nèi)點(diǎn)總的數(shù)目”服從二項(xiàng)分布

式中：p1——給定一個(gè)正確的圖像匹配，一個(gè)特征點(diǎn)是內(nèi)點(diǎn)的概率；p0——給定一個(gè)錯(cuò)誤的圖像匹配，一個(gè)特征點(diǎn)是內(nèi)點(diǎn)的概率。因此內(nèi)點(diǎn)的數(shù)目ni＝∑nfi＝1f（i）。論 文 在實(shí)驗(yàn)中選擇參數(shù)p1＝0.7，p0＝0.01，可以通過貝葉斯公式計(jì)算一個(gè)圖像匹配樣本是正確的后驗(yàn)概率

如果p（m＝＞pmin，則認(rèn)為該圖像匹配是正確的。假設(shè)p（m＝1）＝p（m＝0），則

論文在實(shí)驗(yàn)中選擇參數(shù)pmin＝0.97，則當(dāng)條件ni＞5.9＋0.22nf成立時(shí)，認(rèn)為該圖像匹配是正確的。

3 全景圖自動(dòng)識別與拼接

一旦建立好圖像兩兩之間的匹配關(guān)系，就可以根據(jù)匹配圖像的連接集來查找全景圖像序列，還可以對一組輸入圖像之間存在的一個(gè)或多個(gè)全景圖像進(jìn)行自動(dòng)識別，同時(shí)拒絕那些不和其他圖像匹配的 “噪聲”圖像。在第2部分的基礎(chǔ)上面，論文把這個(gè)問題表示為對多個(gè)無向連通圖的深度優(yōu)先遍歷。

算法3 全景圖自動(dòng)識別算法

（1）檢查圖像列表里面是否還有沒有拼接過的圖像，如果有，選擇這幅圖像記為Ifrom，作為新的拼接圖像Iresult的起始圖像，將其標(biāo)記為 “已經(jīng)拼接”；如果沒有則算法退出；

（2）假設(shè)圖像Ifrom的匹配列表中共有N幅圖像，令索引值s＝0，從匹配列表中選取索引值為s的圖像Ito，如果圖像Ito還沒有被拼接，則調(diào)用算法4對這兩幅圖像進(jìn)行拼接；

（3）令索引值s＝s＋1，如果s＜N回到第 （2）步；否則輸出Iresult，回到第 （1）步。

算法4 全景圖自動(dòng)拼接算法

（1）根據(jù)Ito和Iresult之間的映射關(guān)系動(dòng)態(tài)調(diào)整包圍盒的大小，如圖1所示。在圖1中，每一行表示一次拼接過程。假設(shè)從IMG1開始拼接，其中包圍盒用虛線表示；

圖1 多幅圖像拼接過程中的包圍盒動(dòng)態(tài)調(diào)整

（2）根據(jù)包圍盒的位置依次調(diào)整Iresult中已經(jīng)拼接過的圖像的位置參數(shù)，生成新的結(jié)果圖像I′result，將舊的圖像Iresult拷貝到Iresult中新的位置，并令I(lǐng)′result＝Iresult；

（3）使用多頻帶融合算法［16］將Ito與Iresult進(jìn)行合成，并記錄Ito在Iresult中的位置和索引號，將其標(biāo)記為 “已經(jīng)拼接”。依次從Ito的匹配列表中取出每一個(gè)元素，遞歸調(diào)用算法4。

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

圖2上半部分是使用佳能IXUS 980IS數(shù)碼相機(jī)拍攝的8幅圖像，下半部分是將這8幅圖像輸入系統(tǒng)后得到的4幅輸出圖像。系統(tǒng)能夠自動(dòng)識別出每一幅圖像是否和其他圖像有重疊，并能夠?qū)⑵ヅ涞膱D像按組進(jìn)行拼接輸出。其中的一幅圖像由于和其他圖像都不匹配，因此作為一幅單獨(dú)的 “拼接”圖像輸出。

圖2 多幅圖像的自動(dòng)識別與拼接

5 結(jié)束語

本文提出了一種新的基于圖結(jié)構(gòu)的全景圖像序列自動(dòng)識別和拼接方法。這個(gè)方法使用MOPS進(jìn)行特征檢測，并用概率模型對圖像匹配進(jìn)行魯棒校驗(yàn)，能夠?qū)o序圖像集中的多個(gè)全景圖像進(jìn)行自動(dòng)識別，在沒有用戶輸入的情況下將它們自動(dòng)進(jìn)行拼接。即使圖像之間存在由于光照變化帶來的亮度差異，對多頻帶圖像融合方案的采用也能夠在圖像重疊區(qū)域之間形成平滑過渡，同時(shí)保持高頻細(xì)節(jié)。論文進(jìn)一步的研究內(nèi)容包括使用OpenCL或CUDA這樣的并行計(jì)算框架將計(jì)算放到GPU中運(yùn)行，以及探索其他圖像融合方法。

：

［1］Bartoli A.Groupwise geometric and photometric direct image registration ［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence.2008，30 （2）：2098－2108.

［2］GAY V.Direct estimation of nonrigid registrations with imagebased self－occlusion reasoning ［J］.IEEE Transactions on PatternA－nalysis and Machine Intelligence.2010，32 （1）：87－104.

［3］Sandip R，Satish K.A survey：Methods of feature based image registration ［J］.International Journal of Electronics Communication and Computer Engineering，2012，3 （4）：787－791.

［4］Jose S，Oscar C.GRASP and path relinking hybridizations for the point matching－based image registration problem ［J］.Journal of Heuristics，2012，18 （1）：169－192.

［5］Lowe D.Distinctive image features from scale－invariant keypoints ［J］.International Journal of Computer Vision，2004，60（2）：91－110.

［6］Calonder M，Lepetit V.Brief：Binary robust independent elementary features ［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2012，34 （7）：1281－1298.

［7］Ethan R，Vincent R，Kurt K，et al.ORB：An efficient alternative to SIFT or SURF ［C］／／Barcelona：13th International Conference on Computer Vision，2011：2564－2571.

［8］Pierre M，Pietro P.Evaluation of features detectors and descriptors based on 3Dobjects ［J］.International Journal of Computer Vision，2007，73 （3）：263－284.

［9］Steffen G，Tobias H，Mmtthew T.Evaluation of interest point detectors and feature descriptors for visual tracking ［J］.International Journal of Computer Vision.2011，94 （3）：335－360.

［10］Mikolajczyk K，Schmid C.A performance evaluation of local descriptors ［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2005，27 （10）：1615－1630.

［11］Noah S，Rahul G，Steven M，et al.Finding Paths through the worlds photos ［J］.ACM Transactions on Graphics，2008，27（3）：11－21.

［12］Furukawa Y，Snavely N，Curless B，et al.Reconstructing rome ［J］.IEEE Computer，2010，43 （6）：40－47.

［13］Byrod M，Brown M，Astrom A.Minimal solutions for panoramic stitching with radial distortion ［C］／／Procee－dings of the British Machine Vision Conference.London，2009：1－7.

［14］Brown M，Szeliski R，Wwnder S.Multi－image matching using multi－scale oriented patches ［C］／／International Conference on Computer Vision and Pattern Recognition.Anchorage：IEEE，2005：510－517.

［15］Jongmoo C，Medioni G.StaRSaC：Stable random sample consensus for parameter estimation ［C］／／IEEE Conference on Computer Vision and Pattern Recognition.Miami，2009：675－682.

［16］Allene C，Pons J，Keriven R.Seamless image－based texture atlases using multi－band blending ［C］／／19th International Conference on Pattern Recognition.Tampa，2008：1－4.