一種基于MSER的仿射不變二進制特征提取算法

胡漢莉 席志磊

（武漢數字工程研究所 武漢 430205）

1 引言

景象匹配作為一種自主、無源的導航定位手段，在現在軍事武器中發揮重要的作用。景象匹配的實質是實現實時圖與基準圖之間的圖像匹配問題，以特征相似性為度量的圖像匹配作為景象匹配中的核心內容，得到了廣泛的關注與研究。由于受成像設備安裝角度、成像姿態、傳感器誤差等因素影響，圖像之間會存在復雜的線性或非線性變形，景象匹配算法需要對實測圖與基準圖存在的形變有較強的穩定性，能夠有效地克服圖像之間存在的幾何與輻射變形。

最大穩定極值區域檢測子（MSER）［1］算法通過對圖像進行連續的閾值分割，尋找在一定閾值范圍內保持邊界不變的區域，然后在該區域內提取穩定的多邊形仿射不變特征；基于熵函數的顯著區域（Salient Region）檢測子［2］其理論基礎為局部區域上的亮度概率密度函數，且利用尺度空間思路來實現尺度不變性，特征的尺度由描述子的熵極值來定義，使得顯著區域能有效抵抗仿射及尺度變形。但由于目前對于景象匹配算法的時間和存儲效率的要求不斷提高，有必要對現有的MSER算法進行優化改進。

2MSER特征檢測算法

存在大視角差異的圖像間的相關性不能通過比較矩形或圓形等固定的形狀來建立，因為此類形狀在仿射變化下不能夠保持，如圖1，同一場景中相同的物體內容，在大視角拍攝條件下，發生明顯的幾何形變，相同形狀的窗口不能代表同樣的場景內容。而解決該問題的關鍵在于提取仿射協變區域來構建特征描述。若某區域能通過仿射變換變成規范形，則該區域即為潛在的仿射協變區域［3］。

圖1 不同視角下場景的幾何形變

幾何特性優的橢圓區域是目前在各種局部仿射不變特征中使用最為廣泛的仿射協變區域。最大穩定極值區域［4］（Maximally Stable Extremal Regions，MSER）是寬基線立體匹配中常用的仿射不變的局部區域檢測算法。該算法由Matas于2002年提出，MSER提取具有任意形狀的仿射不變區域，不需預先對圖像進行平滑處理，可以在多種尺度下檢測MSER，可以檢測不同精細程度的區域。算法提取的特征穩定性強、精度高；而且MSER特征區域提取算法具有近似線性的計算速度。據有關學者研究試驗證明，MSER算子在眾多仿射不變特征提取算法中，多數情況下具有最佳性能［5］，其在寬基線、大視角圖像匹配中具有廣泛的應用［6～8］。

2.1 最大穩定極值區域的定義

最大穩定極值區域由區域內或者區域邊界上的灰度函數的極值屬性來定義。假設灰度圖像I(x ，y) ，其灰度值屬于區間［0，255］。設置不同的灰度閾值t∈(0 ，1，…，255) ，對應的閾值圖像分別為 I0，I1，…，I255。

設圖像I(x ，y)中像素值小于某閾值的點為黑點（其像素值為0），而不小于閾值的點為白點（像素值為255）。若將得到的閾值圖像It按照閾值t逐漸增大的順序連續展開，即可得到一系列由白到黑的二進制圖像。如圖2所示，當閾值t=0時，灰度圖像I(x ，y)上所有的像素值均高于該閾值，所以得到一幅白色圖像；隨著閾值t的增大，一些黑色區域在圖像上出現，這些黑色區域由灰度值小于閾值t的像素組成，稱其為局部灰度最小值區域。隨著閾值的增大，這些黑色區域會逐漸增長、融合，最終將變成一幅完全黑色的圖像。這一系列閾值圖像中，每個白色的連通區域都是最大值區域，而那些在多個閾值圖像中面積變化率小于一定閾值的極大值區域就是最大穩定極大極值區域（MSER）。

圖2 閾值圖像

與其它極大值區域不同的是，MSER區域中閾值t從i-Δt變化到i+Δt，對應的極值區域面積變化率最小。因此，MSER區域就是在2Δt鄰域的閾值圖像中，區域面積近似不變的極值區域。以g代表像素點的灰度值，x代表像素點的位置，g（x）代表像素分布曲線，而R、Rg+Δ、Rg-Δ代表極值區域，采用二維圖來代表像素點位置與灰度值的關系（如圖3），則依據三個區域的大小與穩定條件能清楚地判斷出R是否為極值區域。

2.2 MSER區域特征檢測算法流程

MSER算法通過并查算法構造成分樹，利用穩定性度量分析成分樹來提取MSER區域，主要步驟包括：

1）像素點排序

對圖像中所有的像素根據其灰度值按照升序或降序排序。

圖3 極值區域二維關系圖

2）提取極值區域

利用并查算法提取極值區域，并確定區域面積。然后構造成分樹并對嵌套區域進行有效的管理。

3）由成分樹判斷MSER區域

當某個極值區域沿成分樹的某條路徑上下移動，以一定的條件判定該區域是否屬于MSER區域，判斷的依據為閾值變化小于2Δ。

4）區域清理

經過上述步驟可以得到非常多的MSER區域，但部分區域穩定性并不夠，因此需要清理掉面積過小或過大以及區域面積變化率過大或過小的區域。

5）不規則區域橢圓化

由上述過程提取出來的不規則MSER區域很難進行特征描述，需利用組成不規則MSER區域的像素灰度值構建二階中心距，通過二階中心距將不規則的MSER區域調整為規則的橢圓形區域，下圖描述了不規則區域橢圓化調整方法。

圖4 不規則區域橢圓化調整

通過以上五個步驟，即可提取出穩定、有效的MSER特征區域。該區域特征具有良好的仿射不變特性，且對于光照變化和噪聲干擾也具有較強的魯棒性。圖5中橢圓形的區域即為提取MSER區域。

圖5 不規則區域橢圓化調整

3 基于MSER的仿射不變二進制特征提取

MSER仿射不變特征區域提取出來后，需要對區域進行特征描述才能匹配。目前用來表達MSER區域最常用的描述符為SIFT或SURF結構描述符［7，9～10］，以 ORB為代表的二進制特征描述子在時間效率與存儲效率方面比SIFT或SURF具有非常大的優勢。因此本文討論基于ORB描述子的MSER特征匹配。本文將基于MSER的仿射不變二進制特征提取算法簡稱為MSER-ORB算法。

3.1 基于MSER的仿射不變二進制特征提取流程

在上文中獲得基于橢圓描述的MSER區域特征后，使用二進制描述子ORB做特征的描述。由于特征描述子為二進制，則可以使用海明距離作為相似性度量來進行特征的匹配，基于MSER的仿射不變二進制特征提取流程描述如圖6。

圖6 基于MSER的仿射不變二進制特征提取流程圖

在以上流程圖中描述的過程中，如何對MSER區域特征進行二進制描述是關鍵，下節將具體介紹。

3.2 基于ORB描述子的最大穩定極值區域描述

MSER特征匹配算法的抗仿射性能是由每一個獨立的MSER區域來體現的，每一個MSER區域就是一個獨立的仿射不變單元。理想的特征描述子必須能完整地表達整個區域的信息，且該表達不能具有二義性。然而，這樣理想的描述子是不存在的，為了使MSER區域的仿射不變性盡可能地得到保持，特征描述子應當最大限度地反映整個區域的真實屬性。

由2.2節可知，提取出的不規則的MSER區域通過橢圓調整變成了規則的橢圓形狀，對每個橢圓形的MSER區域做如下定義：(Ex，Ey)代表橢圓的中心，a1、a2分別為橢圓長短軸方向的幅值，θ代表長軸的方向，如圖7所示。

圖7 MSER區域的橢圓表達

而ORB描述子的幾個決定性因素包括：特征點的位置eCenter、尺度eScale、主方向eAngle。將MSER橢圓區域轉換為ORB描述子，過程如下：

2）獲取特征點中心坐標：eCenter=(Ex，Ey)；

3）獲取特征點主方向：eAngle=θ。

由此，MSER仿射不變橢圓區域就轉換為了ORB可進行描述的特征點。

4 實驗與分析

本章通過MSER-ORB與MSER-SURF以及ORB特征的比較實驗，驗證分析MSER-ORB的相關性能。其中，MSER-SURF是以MSER作為特征檢測算子，SURF作為特征描述子，ORB特征是以oFAST作為特征檢測子，ORB作為特征描述。主要討論這三種特征在時空效率、仿射不變性方面的性能。

本研究對圖像仿射變形的實驗使用的是由牛津大學機器人研究實驗室提供的圖像特征匹配標準測試數據集［11］中的graf圖像組，該組圖像由6張不同視角差異的彩色圖像組成，圖像分辨率為800×600。與第一張圖像相比，后續5張圖像的拍攝視角與之差異越來越大，圖像如圖8。

圖8 graf仿射不變測試圖像序列

實驗所有的測試軟件均由C++語言在Visual Studio2010平臺下編寫，計算機為32位Win7系統，處理器為4核Intel i7，4G內存。

4.1 時空效率對比分析

對graf圖像序列中的img1與img2做多次匹配，統計MSER-SURF、ORB、MSER-ORB三種特征匹配算法的時間性能，如表1。

表1 三種特征匹配算法耗時統計表（單位：ms）

由上表可以看出，MSER-ORB在特征描述與匹配方面的耗時比MSER-SURF降低19%。然而，由于MSER特征檢測比oFAST慢比較多，導致基于MSER特征檢測的MSER-ORB與MSER-SURF算法耗時均為ORB的兩倍左右。

考慮三種算法的內存消耗，存儲一個ORB特征與SURF特征分別需要內存為32與256字節，即MSER-ORB對內存的占用少于MSER-SURF的八分之一。

4.2 匹配效果對比分析

用graf圖像序列中的img1分別與img2-6匹配，隨著圖像視角差異的變大，圖像間的仿射變形越大，匹配難度也逐漸增大。MSER-SURF、ORB、MSER-ORB三種算法精匹配點對數統計如表2。

表2 三種算法精匹配點對數統計表

其匹配率描述如下表3。

表3 三種算法匹配率統計表

其匹配正確率描述如表4。

表4 三種算法匹配正確率統計表

由以上表格統計結果可以看出，隨著圖像視角差異的增大，具有仿射不變性的MSER-SURF及MSER-ORB匹配性能與ORB算法相比的優勢原來越明顯，其中對于img1-img5及img1-img6圖像對，ORB算法匹配失敗，而MSER-SURF及MSER-ORB都能得到13對以上的精確的同名匹配點對，由此證明了將ORB算法的oFAST特征檢測子替換為具有仿射不變性的MSER特征，有效地提高了其對大視角差異圖像匹配的性能，提高了匹配算法的穩健性。

同時，考慮基于MSER仿射不變特征檢測的MSER-SURF與MSER-ORB算法，由于SURF描述子考慮了尺度不變性，使基于SURF描述子的特征匹配算法比基于ORB描述子的算法在尺度差異較大的時候有更好的適應性，而圖像視角差異過大同時也意味著部分區域的尺度差異較大，如img1-img5與img1-img6，在這兩組的匹配實驗中，MSER-SURF效果優于MSER-ORB，而在視角差異小的前三組實驗中，MSER-ORB的匹配結果優于MSER-SURF。基于MSER-SURF與MSER-ORB的 img1-img5匹配結果展示如下（ORB算法在img1-img5匹配失敗）。

圖9 img1-img5匹配結果

另外，由于MSER算子檢測的特征比oFAST少很多，使得到的精匹配點對數量不多，這在一定程度上制約了后續基于匹配特征的空間模型解算精度。但以MSER為檢測子的MSER-SURF與MSER-ORB算法的特征匹配率與匹配正確率絕大多數都由于基于oFAST檢測子的ORB算法。

5 結語

本文提出了一種結合MSER特征檢測與ORB特征描述的仿射不變二進制特征提取方法。實驗表明基于MSER的仿射不變二進制特征提取能有效結合MSER的抗仿射性能與ORB描述子的快速低存儲優勢，能在滿足抗仿射變形的同時獲得較高的匹配效率。然而，MSER-ORB景象匹配算法的缺陷是提取的特征較少，當圖像在噪聲、尺度、旋轉等方面的變形太大時，MSER-ORB景象匹配算法適應性較差。