基于圖結構的全景圖自動識別與拼接方法

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

（1.西南林業大學 計算機與信息學院，云南 昆明650224；2.北京師范大學信息科學與技術學院，北京100875；3.西南林業大學 材料工程學院，云南 昆明650224）

0 引 言

圖像匹配的方法一般分為兩種類型，直接匹配或是基于特征的匹配。直接匹配的方法試圖使用圖像的像素值通過迭代的方法對圖像進行配準［1，2］。基于特征的方法試圖從圖像中提取出不同類型的特征，例如線特征或點特征，并使用該特征的鄰域信息來進行特征匹配［3，4］。

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

基于不變特征的方法已經成功地應用到很多領域中，包括物體識別［11］、從運動獲取結構［12］以及全景圖像拼接［13］。雖然對圖像匹配的研究已經取得了很多進展，仍然有值得研究的空間，特別是在現有的文獻中缺乏對以下兩個問題的詳細討論：①如何有效的判別輸入的多幅無序圖像之間是否有重疊部分以及重疊區域的大小；②如何自動對屬于同一個場景的不同圖像進行分類并合成相應的全景圖像。

基于此，本文提出了一個基于圖結構的全景圖像自動識別和拼接的方法，能夠對輸入的多幅無序圖像進行自動分類識別與拼接。該方法首先對輸入圖像進行MOPS特征檢測，然后使用k－d樹對特征點進行快速匹配，根據最近鄰特征點距離與次近鄰特征點距離之比得到初始匹配點對。根據圖像特征點之間的對應關系使用RANSAC算法建立任意兩幅圖像之間的匹配模型，并用概率統計策略對其進行魯棒校驗。論文將多圖像匹配問題建模為在不同圖像節點之間建立無向連通圖的問題，而多圖像拼接的問題可以歸結為對建立好的一個或多個無向連通圖進行深度優先遍歷。

1 MOPS特征檢測與匹配

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

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

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

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

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

其中積分尺度參數σo＝4.5。

檢測得到初始的候選特征點后，為了保證特征檢測的穩定性，還需要對其進行篩選。由于Harris角點響應函數會在圖像的邊界處取得較大的響應值，而圖像的邊界對于噪聲比較敏感，會對檢測到的特征點的位置有比較多的影響，因此需要刪除每一層金字塔圖像邊界上的候選特征點。首先對所有候選特征點進行順序遍歷，以當前特征點為中心構造一個40x40大小的采樣窗口，將這個窗口旋轉和特征點的主方向對齊。如果旋轉后的窗口有任意部分超出當前特征點所在的金字塔圖像的邊界，就將當前特征點從候選特征點中刪除。

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

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

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

（1）為每一幅圖像的特征點集構造一顆k－d樹；

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

（3）當所有圖像的所有特征點都遍歷完成后，還需要對特征匹配的結果進行校驗。假設第i幅圖像中第ni個特征點的匹配圖像索引值為j，匹配特征點索引值為nij。需要檢查第j幅圖像中第nij個特征點對應于圖像i的匹配特征點索引值是否為ni，如果兩者不相符就認為該匹配是錯誤的。

2 基于圖結構的多圖像匹配

根據圖像特征點之間的對應關系就可以建立輸入圖像集合中任意兩幅圖像之間的匹配關系。可以用無向圖結構來表示這個計算過程，每一幅輸入圖像是無向圖中的一個節點，如果兩幅圖像之間滿足給定的匹配關系，則在這兩個節點之間存在一條連接線。多圖像匹配問題就是要計算這個無向圖結構中所有存在的無向連通圖。

算法2 基于無向圖結構的多圖像匹配

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

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

（3）用 RANSAC （random sample consensus）算法［15］對第i幅圖像和第j幅圖像之間的匹配特征點對進行魯棒校驗，剔除外點，同時求出兩幅圖像之間的運動模型參數。

對于每一對潛在的匹配圖像之間都存在兩組不同類型的匹配特征點對，一組是符合運動模型幾何一致性的特征點對，一組是幾何不一致性的特征點對。論文使用基于統計的策略對圖像匹配進行魯棒校驗。基本思想是比較這一組內點／外點是由一個正確的圖像匹配或者錯誤的圖像匹配產生的概率大小。對于一幅給定的圖像，用nf表示這幅圖像在重疊區域中的特征點數目，ni表示這幅圖像在重疊區域中的內點數目。可以用服從0－1分布的隨機變量m來表示隨機事件 “這幅圖像匹配正確或錯誤”。假設事件 “第i個匹配點對f（i）∈ ｛ 0，1｝是內點／外點”是n重伯努利實驗，那么隨機變量 “內點總的數目”服從二項分布

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

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

論文在實驗中選擇參數pmin＝0.97，則當條件ni＞5.9＋0.22nf成立時，認為該圖像匹配是正確的。

3 全景圖自動識別與拼接

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

算法3 全景圖自動識別算法

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

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

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

算法4 全景圖自動拼接算法

（1）根據Ito和Iresult之間的映射關系動態調整包圍盒的大小，如圖1所示。在圖1中，每一行表示一次拼接過程。假設從IMG1開始拼接，其中包圍盒用虛線表示；

圖1 多幅圖像拼接過程中的包圍盒動態調整

（2）根據包圍盒的位置依次調整Iresult中已經拼接過的圖像的位置參數，生成新的結果圖像I′result，將舊的圖像Iresult拷貝到Iresult中新的位置，并令I′result＝Iresult；

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

4 實驗結果

圖2上半部分是使用佳能IXUS 980IS數碼相機拍攝的8幅圖像，下半部分是將這8幅圖像輸入系統后得到的4幅輸出圖像。系統能夠自動識別出每一幅圖像是否和其他圖像有重疊，并能夠將匹配的圖像按組進行拼接輸出。其中的一幅圖像由于和其他圖像都不匹配，因此作為一幅單獨的 “拼接”圖像輸出。

圖2 多幅圖像的自動識別與拼接

5 結束語

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

：

［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.