影像同名點匹配的SIFT算法與貝葉斯抽樣一致性檢驗

賈豐蔓，康志忠，于 鵬

中國地質大學（北京）土地科學技術學院，北京 100083

1 緒 論

影像匹配是指通過一定的匹配算法在兩幅或多幅影像之間識別同名點的過程，它是圖像處理及計算機視覺領域中的一個非常重要的熱點問題［1］。所以，穩(wěn)定、精確、快速的影像匹配算法有利于進行對圖像信息的后續(xù)處理的研究。影像匹配方法大致分為兩類：基于影像灰度的匹配［2］與基于特征的匹配［3］。SIFT 算法［4］是由文獻［5—6］提出的一種提取局部特征的方法［7］，由于利用了圖像中數量較少、特征較穩(wěn)定的一些點、線或邊緣等進行匹配，大大壓縮了所需處理信息量，使得匹配搜索的計算量小，速度較快。而且該方法對圖像灰度的變化具有魯棒性，是目前研究最多、應用最廣的一類匹配方法。SIFT算法通過在尺度空間探測極值，提取具有穩(wěn)健性的特征描述向量［4］。在傳統(tǒng)SIFT算法的基礎上，本文提出了一些改進的SIFT算法。為了綜合利用影像的結構特征和灰度特征，文獻［8］中提出了基于SIFT特征和灰度特征的綜合匹配相似性測度的計算方法。考慮到在圖像發(fā)生旋轉后，特征點周圍的區(qū)域都會發(fā)生變化，而圓具有很好的旋轉不變性，文獻［9］中提出可以用圓來構造SIFT特征點描述符，在以特征點為中心的圓形區(qū)域內構造4個圓環(huán)，在每個圓環(huán)內分別計算（0°，360°）均勻分布的12個方向上的梯度直方圖。針對匹配中存在的重復匹配和多對一匹配等問題，文獻［10］優(yōu)化了其關鍵點匹配策略，通過比較匹配點對的像素坐標值和遍歷對應點對的索引值將其全部提取出來，這就提高了匹配點對的精確度。

傳統(tǒng)RANSAC在假設檢驗時采用的是隨機抽樣，即認為每個點的正確點先驗概率是相同的，這在有很多粗差點存在時會增加迭代次數，嚴重地影響運算效率。為提高運算效率，本文引入了基于貝葉斯抽樣一致性的BAYSAC算法［11］。該算法在每次假設檢驗時總是選擇正確點概率最高的點，能有效地減少找到最優(yōu)模型所需的迭代次數和運算時間，提高匹配的效率。本文在原有BAYSAC算法基礎上，對正確點先驗概率確定和概率更新兩部分進行了優(yōu)化。

2 基于SIFT特征匹配的BAYSAC算法

SIFT算法是基于特征的匹配方法，它的匹配能力很強，但受各種外部噪聲因素的影響，要準確地對特征點進行無歧義的匹配難度很大，通常會在一定程度上引起特征的誤匹配。因此，影像匹配中通過實現模型參數的穩(wěn)健性估計剔除誤匹配。傳統(tǒng)的模型參數的穩(wěn)健性估計方法，例如RANSAC算法，已經在圖像匹配的領域取得了良好的效果。BAYSAC算法以RANSAC算法的原理為基礎，結合了貝葉斯估計的原理，能有效剔除影像匹配粗差點，得到精確可靠的匹配結果，提高SIFT算法的穩(wěn)健性。

2.1 SIFT算法簡介

SIFT（尺度不變特征變換：scale invariant feature transform）算法由D.G.Lowe在1999年所發(fā)表，2004年完善總結。它通過在尺度空間探測極值，提取具有穩(wěn)健性的特征描述向量。SIFT特征匹配算法的匹配能力很強，它能夠處理兩幅影像之間發(fā)生平移、旋轉、仿射變換情況下的匹配問題，尋找匹配最佳點位。

SIFT特征匹配的主要步驟如下［12］：

① 建立尺度空間；② 尺度空間極值探測；③ 確定特征點方向；④ 提取SIFT區(qū)域特征描述向量；⑤ 尋找最佳匹配點位。

2.2 RANSAC算法

RANSAC（random sample consensus）算法，也稱作隨機抽樣一致性算法，它是一種穩(wěn)健性的算法，最早于1981年由文獻［13］提出。與 M－estimator［14］、L－estimator［15］和 LMedS［16］等統(tǒng)計方法類似，該算法廣泛運用在計算機視覺的各領域，成為估計基本矩陣的基本方法之一。RANSAC算法估計基本矩陣時，要求在置信概率為p的條件下，在預匹配的特征點集組中隨機抽樣n次，每次抽樣的數據量為m，要保證至少有一次抽樣的數據全是正確點［17］。傳統(tǒng)的RANSAC算法為剔除影像誤匹配提供了有效的途徑，它盡可能地剔除了粗差點，一定程度地提高了影像匹配的穩(wěn)健性。

2.3 BAYSAC算法

2.3.1 算法原理

BAYSAC（Bayes sample consensus）算法是指貝葉斯抽樣一致性，由文獻［11］提出。傳統(tǒng)RANSAC方法下由隨機產生的假設點集估計基本矩陣模型，并選擇符合點數最多的模型作為最佳模型。BAYSAC算法則是利用可能擁有的每個點的正確點可能性（概率）作為先驗信息，在每次抽樣時總選擇具有最高先驗概率的n個點作為假設點集計算模型參數，用模型符合點數判斷該模型是否是更好的模型；之后結合貝葉斯公式更新每個樣本點的正確點概率，作為下次假設檢驗時的正確點先驗概率，進入下一次抽樣。BAYSAC算法在每次抽樣時總選擇正確點概率最高的n個點作為假設點集，能夠減少得到最佳模型所用的時間，提高計算效率。

本文引入了原始BAYSAC算法基于隨機概率的先驗概率確定方法，并對原始BAYSAC算法進行改進，主要體現在：① 結合影像對的幾何成像原理確定幾何約束以確定先驗概率；② 對概率更新公式進行優(yōu)化，用檢驗模型最優(yōu)的概率來估計假設點集整體為局內點最優(yōu)的可能性，并用k／D作為檢驗模型是否最優(yōu)的評價指標。

2.3.2 算法步驟

（1）由如下公式獲得欲抽樣的次數T

式中，p為置信區(qū)間；ε為數據集的錯誤點所占的比率；n為樣本容量；

（2）選擇數據集合中正確點概率最高的n個點作為假設點集；

（3）由所選假設點集計算基本矩陣；

（4）對數據集內剩余的點進行檢驗，以點到對應核線的距離判斷正確點和粗差點，將距離超出閾值的點作為粗差點剔除；

（5）每次循環(huán)結束前更新每個點的正確點概率Pt（i∈I），進入下一次循環(huán)；

（6）重復步驟2—5，直至達到抽樣次數T；

（7）記錄符合點數最多的模型，認為該模型為最佳基本矩陣模型；

（8）用符合最佳基本矩陣模型的點估計最終的模型參數。

BAYSAC算法要解決的核心問題是正確點先驗概率的估計，以及每次假設檢驗之后正確點概率的更新。

2.3.3 正確點先驗概率估計方法

BAYSAC算法是基于RANSAC算法的改進，體現在以每個點的正確點先驗概率作為抽樣的依據。然而在實際應用中，正確點先驗概率是很難得到的，因此要盡可能準確地估計點的正確點先驗概率。本文分析了不同影像的成像特點，確定了3種正確點先驗概率的估計方法：

2.3.3.1 基于隨機概率U（0，1）的正確點先驗概率估計方法

這種估計先驗概率的算法由文獻［11］提出。由于概率值為分布在（0，1）之間的浮點數，因此，選取基于隨機概率U（0，1）分布的隨機值作為每個點的正確點先驗概率。這種方法可通用于不同影像。試驗中這種正確點先驗概率的估計算法用RANDOM－BAYSAC表示。但由于其概率估計的隨機性，很有可能將較大的概率值賦給原本是誤匹配的點，導致無法有效剔除誤匹配，保留正確匹配。因此本文還結合了不同的影像成像原理，提出了兩種正確點先驗概率的估計方法。

2.3.3.2 基于像點到像片中心距離比值的正確點概率估計方法

沿主光軸方向拍攝的地面影像在拍攝時，攝影機是沿主光軸推進的。影像同名點間的幾何關系如圖1所示。

圖1 地面影像坐標幾何關系Fig.1 Geometric relationships of ground image coordinates

圖1中S1（S2）為兩個攝站，r1（r2）為S1（S2）沿基線到像片的距離，ΔS為基線長度，LA（LB）為物方點A（B）到其主光軸上投影點的距離，DA（D′A）和DB（D′B）是物方點A（B）所在平面與攝站S1（S2）間的距離，lA（l′A）和lB（l′B）是同名點a（a′）／b（b′）到同名像對中心的距離，取像幅長（寬）的一半作為像片中心的坐標。即可得到如下所示的幾何關系

如式（2）所示，對于一對同名像點，像點到兩張像片中心的距離與像點到兩攝站的距離成反比。像點到兩攝站的距離差為基線長度ΔS，ΔS是一個常量。ΔS相對于多數D′都是一個較小的值，使得ΔS／D′成為一個較小的量。因此對于不同的同名點對，如式（3）所示，比值l′／l是一個集中在1附近的變量，即一個近似于常量1的變量。用SIFT匹配得到的同名點坐標計算每個點l′／l的值，并統(tǒng)計該比值的分布，計算其在出現峰值的區(qū)域內的均值，該均值即被看作是描述兩張像片幾何關系的比值常量的最近似值。在改進的算法中，以同名像點與像片中心的距離的比值在峰值區(qū)域內的均值作為賦予先驗概率的參考。若某個點的距離比值偏離這個均值太多，則認為該點是錯誤匹配的可能性較大，即賦予其較小的先驗概率。試驗中這種正確點先驗概率的估計算法用RATIO－BAYSAC表示。

2.3.3.3 基于影像重疊度的正確點先驗概率估計方法

航空影像在拍攝時，相鄰相片的航向重疊度一般應為60%～65%，最大不大于75%，最小不小于56%［18］。因此在航行基本穩(wěn)定，航高和航向沒有太大的變化時，對于每個物方點，它在兩幅圖像上對應的視差應該是一個常量，如圖2。

為估計視差的常量，用SIFT匹配得到的同名點坐標計算每個點的視差，并統(tǒng)計該視差的分布，計算其在出現峰值的區(qū)域的均值，該均值即被看作是描述兩幅相片偏移關系的最近似值。在改進的算法中，以兩幅圖像對應方向的視差在峰值區(qū)域內的均值作為賦予先驗概率的參考。若某個點的坐標偏移量偏離這個均值太多，則認為該點是錯誤匹配的可能性較大，即賦予其較小的先驗概率。試驗中這種正確點先驗概率的估計算法用OVERLAP－BAYSAC表示。

圖2 航空影像坐標偏移Fig.2 Coordinate shift of aerial image

“嫦娥一號”衛(wèi)星搭載的三線陣CCD立體相機，在衛(wèi)星飛行過程中連續(xù)獲取前視、正視、后視3個線陣的數據，形成3幅連續(xù)影像，同一地物在一定的時間內分別被前、正、后視3條線陣掃過［19］。由于相機的前視、正視和后視線陣之間的夾角不大，獲取的前視、正視和后視影像兩兩之間都存在近100%的重疊度［20］。適用于基于影像重疊度的正確點先驗概率估計方法。

2.3.4 概率更新公式

文獻［11］中提出的貝葉斯公式更新正確點先驗概率的公式如下

式中，Pt－1（i∈I）表示更新前的正確點先驗概率；Pt（i∈I）表示更新后的正確點先驗概率；P（Ht?I）表示樣本數據中存在粗差點的概率；P（Ht?I｜i∈I）表示i點為正確點時樣本數據中存在粗差點的概率。

貝葉斯公式可按照相似性度量的原理進行簡化

其中，L（A｜B）反映了概率更新前后的相似性。若某次假設檢驗符合點數較多，則認為其選擇的假設點集較優(yōu)。用每次檢驗模型最優(yōu)的概率來估計假設點集整體為局內點最優(yōu)的可能性，并用此評價檢驗前后正確點概率的相似性

式中，k為某次假設檢驗模型的符合點數；D為所有的數據點。即可優(yōu)化貝葉斯抽樣一致性正確點概率更新的公式

3 試 驗

本文用基于不同成像原理的兩組像對的試驗結果為例，比較RANSAC算法和BAYSAC算法在剔除誤匹配時的表現。其中像對Ⅰ是沿主光軸方向拍攝的地面影像，像對Ⅱ為“嫦娥一號”衛(wèi)星搭載的三線陣CCD相機推掃的月表影像。

SIFT算法提取匹配點時，當兩幅圖像的SIFT特征向量生成后，可以用關鍵點特征向量的歐式距離來作為兩幅圖像中關鍵點的相似性判定度量。取出圖像A中的某個關鍵點，并找出其與圖像B中歐式距離最近的前兩個關鍵點。獲得這兩個關鍵點后，給定一個小于1的數值作為閾值θ，用距離最近的兩個關鍵點點中最近的距離除以次近的距離，若獲得的比值少于θ，則接受這一對匹配點。一般情況下，θ取0.6時，能得到穩(wěn)健的匹配點。提高這個比例閾值，SIFT匹配點數目就會增加，但容易出現誤匹配點。為比較RANSAC算法和BAYSAC算法在不同數量的誤匹配存在時的表現，分別將SIFT算法的閾值θ設置為0.6和0.8，這樣一個像對能得到兩組數量不同的同名點，試驗數據見表1。用RANSAC算法和BAYSAC算法對由SIFT算法得到的每幅影像的兩組數據分別進行處理，匹配效果見表2。

表1 試驗數據Tab.1 Experimental data

3.1 沿主光軸拍攝的地面影像試驗結果

像對I是沿主光軸拍攝的地面影像，影像分辨率為4500像素×3000像素。θ＝0.6時由SIFT算法提取的匹配點數為368個（見圖3）；θ＝0.8時由SIFT算法提取的匹配點數為571個（見圖4）。

圖3 θ＝0.6時SIFT匹配的同名點Fig.3 Correspondences extracted by SIFT with the threshold 0.6

圖4 θ＝0.8時SIFT匹配的同名點Fig.4 Correspondences extracted by SIFT with the threshold 0.8

如表1，當SIFT算法的閾值不同時，提取的同名點有不同的誤匹配率。對于像對I，θ＝0.6和θ＝0.8時的誤匹配點率都較大，導致RANSAC運行效率較低；而 RANDOM－BAYSAC和RATIO－BAYSAC的運行效率則很高，并能有效剔除粗差點，如圖5。

圖5（a）、（b）、（c）分別為 RANSAC、RANDOM－BAYSAC和 RATIO－BAYSAC 算法試 驗結果的細部放大圖。圖中可以看到，經RATIOBAYSAC算法處理后，圖像右側邊緣（圖5（c））的錯誤匹配得到了有效的剔除。

圖5 像對I匹配細部放大圖Fig.5 Zoom－in parts of image pair I

3.2 “嫦娥一號”衛(wèi)星搭載的三線陣CCD相機推掃的月表影像試驗結果

3.2.1 前視／正視影像

像對Ⅱ（1）是“嫦娥一號”衛(wèi)星搭載的三線陣CCD相機推掃的月表前視／正視影像，影像分辨率為512像素×8745像素。θ＝0.6時由SIFT算法提取的匹配點數為839個；θ＝0.8時由SIFT算法提取的匹配點數為903個。各算法匹配效果見表2。

3.2.2 前視／后視影像

像對Ⅱ（2）是“嫦娥一號”衛(wèi)星搭載的三線陣CCD相機推掃的月表前視／后視影像，影像分辨率為512像素×8745像素。θ＝0.6時由SIFT算法提取的匹配點數為703個；θ＝0.8時由SIFT算法提取的匹配點數為781個。各算法匹配效果見表2。

表2 匹配效果對比Tab.2 Comparison of matching effects

通過兩個指標對試驗結果進行分析：

（1）計算效率：統(tǒng)計不同算法在誤匹配率不同時運算效率的變化情況，比較結果見圖6。

（2）可靠性：以沿主光軸拍攝的像對I和“嫦娥一號”衛(wèi)星搭載的三線陣CCD相機推掃的月表前視／后視影像為例（θ＝0.6），分析不同算法的匹配可靠性。分析結果見表3。

圖6 運算效率比較Fig.6 Comparison of computation efficient

當SIFT的閾值不同時，同名點的誤匹配率隨之變化。圖6比較了各算法在不同誤匹配率時的運行效率。從圖中可以看出，隨誤匹配率提高，RANSAC算法的運行時間顯著的增加，運算效率明顯降低，而本文提出的RANDOM－BAYSAC、RATIO－BAYSAC和 OVERLAP－BAYSAC算法的運算效率則在誤匹配率變化時仍表現平穩(wěn)。

表3 可靠性分析Tab.3 Comparison of reliability

4 結 語

本文試驗結果表明，針對不同影像，基于不同正確點先驗概率估計方法的算法能將運算效率提高至少2倍以上，保留的正確匹配和匹配正確率也有不同程度的提高。

文章引入了一種通用的基于隨機概率正確點先驗概率估計方法，又提出了另外兩種有針對性的正確點先驗概率估計方法，3種方法給出的總是估計值，盡管能得到良好的試驗結果，但這樣的值不是精確的。在以后的研究中，可以設法獲得更加精確的正確點先驗概率，并能通用于不同影像中，就能得到更可靠的結果。

［1］ QU Tianwei，AN Bo，CHEN Guilan.Application of Improved RANSAC Algorithm to Image Registration［J］.Journal of Computer Applications，2010，30（7）：1849－1852.（曲天偉，安波，陳桂蘭.改進的RANSAC算法在圖像配準中的應用［J］.計算機應用，2010，30（7）：1849－1852.）

［2］ ZHU Q，WU B，XU Z.Seed Point Selection Method for Triangle Constrained Image Matching Propagation［J］.IEEE Geoscience and Remote Sensing Letters，2006，3（2）：207－211.

［3］ YOU J，BHATTACHARYA P.A Wavelet－based Coarseto－fine Image Matching Scheme in a Parallel Virtual Machine Environment［J］.IEEE Transactions on Image Processing，2000，9（9）：1547－1559.

［4］ LOWE D G.Distinctive Image Feature from Scaleinvariant Keypoints［J］.International Journal of Computer Vision.2004，60（2）：91－110.

［5］ YANG Xuemei，GONG Junbin，WANG Peng，et al.Registration Algorithm for SAR and Optical Images Based on Improved SIFT［J］.Aerospaced Control，2010，28（6）：13－17.（楊雪梅，龔俊斌，王鵬，等.基于改進SIFT的SAR圖像與可見光圖像配準［J］.航天控制，2010，28（6）：13－17.）

［6］ GONG Junbin，ZHANG Dazhi，YANG Xuemei，et al.Automatic Registration Algorithm for SAR and Optical Images with Rotation and Scale Invariability［J］.Journal of Astronautics，2011，32（6）：350－358.（龔俊斌，張大志，楊雪梅，等.抗旋轉和縮放的SAR與可見光圖像自動配準算法［J］.宇航學報，2011，32（6）：350－358.）

［7］ YUE Chunyu，JIANG Wanshou.An Automatic Registration Algorithm for SAR and Optical Images Based on Geometry Constraint and Improved SIFT［J］.Acta Geodaetica et Cartographica Sinica，2012，41（4）：570－576.（岳春宇，江萬壽.幾何約束和改進SIFT的SAR影像和光學影像自動配準方法［J］.測繪學報，2012，41（4）：570－576.）

［8］ ZHANG Ka，SHENG Yehua，YE Chun.Digital Close－range Stereo Image Matching Based on Digital Parallax Model and Improved SIFT Feature［J］.Acta Geodaetica et Cartographica Sinica，2012，39（6）：624－630.（張卡，盛業(yè)華，葉春.基于數字視差模型和改進SIFT特征的數字近景立體影像匹配［J］.測繪學報，2012，39（6）：624－630.）

［9］ YAO Wenwei，ZHANG Zhibin，LI Guo，et al.Improvement of Image Matching Algorithm SIFT［J］.Geomatics and Information Science of Wuhan University，2011，26（6）：67－70.（姚文偉，張智斌，李國，等.圖像匹配算法SIFT的改進［J］.武漢大學學報：信息科學版，2011，26（6）：67－70.）

［10］ LI Fangfang，XIAO Benlin，JIA Yonghong，et al.Improved SIFT Algorithm and Its Application in Automatic Registration of Remotely－sensed Imagery［J］.Geomatics and Information Science of Wuhan University.2009，34（10）：1245－1250.（李芳芳，肖本林，賈永紅，等.SIFT算法優(yōu)化及其用于遙感影像自動配準［J］.武漢大學學報：信息科學版，2009，34（10）：1245－1250.）

［11］ BOTTERILL T，MILLS S，GREEN R.New Conditional Sampling Strategies for Speeded－up RANSAC ［C］∥Proceedings of British Machine Vision Conference：BMVC 2009，London：British Machine Vision Association，2009：223－233.

［12］ LI Ersen，ZHANG Baoming，LIU Jingzheng，et al.The Application of SIFT Feature Matching Method in the Automatic Relative Orientation［J］.Science of Surveying and Mapping，2008，33（5）：16－18.（李二森，張保明，劉景正，等.SIFT特征匹配技術在自動相對定向中的應用［J］.測繪科學，2008，33（5）：16－18.）

［13］ MAINS J，CHUM O.Randomized RANSAC withTd，dTest［J］.Image and Vision Computing，2004，22（10）：837－84.

［14］ ZHANG Z Y.Determining the Epipolar Geometry and Its Uncertainty：A Review ［J］.International Journal of Computer Vision，1998，27（2）：161－198.

［15］ FISCHLER M A，BOLES R C.Random Sample Consensus：A Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography［J］.Communications of the ACM，1981，24（6）：381－395.

［16］ TORR P H S，MILRRAY D W.The Development and Comparision of Robust Methods for Estimating the Fundamental Matrix［J］.International Journal of Computer Vision.1997，24（3）：271－300.

［17］ FAN Xuedong.Base on the Fundamental Matrix Study of Matching Algorithm ［D］.Changsha：Central South University，2006.（范學棟.基于基本矩陣的匹配算法研究［D］.長沙：中南大學，2006.）

［18］ WANG Dongliang，XIAO Jianhua，WAN Youchuan，et al.Aerial Route Design Approach for Stereomapping Based on Stereomodel Overlap［J］.Acta Geodaetica et Cartographica Sinica，2011，40（2）：188－193.（王東亮，肖建華，萬幼川，等.基于立體模型重疊度的航空攝影航線設計［J］.測繪學報，2011，40（2）：188－193.）

［19］ CUI Tengfei，CHEN Shengbo，WANG Jingran.Threedimensional Modeling of the Lunar Surface Based on Stereo Camera Onboard Chang’e Orbitor［J］.Remote Sensing for Land ＆Resources，2009，4（32）：31－34.（崔騰飛，陳圣波，王景然.基于“嫦娥衛(wèi)星”三線陣CCD立體相機的月球表面三維建模［J］.國土資源遙感，2009，4（32）：31－34.）

［20］ LI Qiaozhi，ZHANG Wuming，YAN Guangjian，et al.Simulation of Three－line CCD Satellite Images of the Moon［J］.Journal of Beijing Normal University，2007，43（3）：298－302.（李巧枝，張吳明，閻廣建，等.月球衛(wèi)星三線陣CCD影像模擬［J］.北京師范大學學報：自然科學版，2007，43（3）：298－302.）