面向圖像匹配的基礎(chǔ)矩陣估計改進算法

馬庭田，葉文華，葉華欣

(1.南京航空航天大學(xué) 機電學(xué)院，江蘇 南京 210016)(2.斯蒂文斯理工學(xué)院 工程與科學(xué)學(xué)院，美國 霍博肯 07030)

1 問題的提出

隨著智能制造的深入發(fā)展和智能機器人的廣泛應(yīng)用，基于視覺的機器人搬運系統(tǒng)成為近期的研究熱點。目前，研究主要集中在目標(biāo)識別方面，而絕大多數(shù)目標(biāo)識別采用的都是圖像匹配原理?，F(xiàn)階段的圖像匹配還存在匹配速度慢，匹配精度不高的問題，難以滿足機器人快速、精確搬運的要求，如何解決這兩個問題是實現(xiàn)目標(biāo)識別的關(guān)鍵。

圖像匹配是目標(biāo)識別的關(guān)鍵步驟，主要依據(jù)的是對極幾何關(guān)系，對極幾何關(guān)系是兩幅圖像匹配時的基本約束關(guān)系[1],這是在未標(biāo)定的兩幅圖像中可獲取的唯一信息[2]。如圖1所示，γ1和γ2分別是兩個成像平面，M是空間一點，Oc1和Oc2分別是γ1、γ2對應(yīng)的針孔相機的光心。e1和e2是Oc1和Oc2的連線與兩個成像平面的交點，稱為極點，m1和m2分別是點M在兩個成像平面上的像點。l1為點m2在γ1平面上對應(yīng)的極線，l2為點m1在γ2平面上對應(yīng)的極線。

對于兩幅圖像中的匹配點m1和m2，滿足如下等式：

F是3×3矩陣，稱為基礎(chǔ)矩陣(fundamental matrix)[3]，它描述了圖像間匹配點的對應(yīng)關(guān)系。只需得到匹配圖像的幾個成對的匹配點(至少8對)就可以計算出矩陣，從而推出兩幅圖像中其他點的對應(yīng)關(guān)系。對基礎(chǔ)矩陣的估計是研究視覺問題的關(guān)鍵，在三維重建、運動估計、相機標(biāo)定和匹配跟蹤方面得到廣泛應(yīng)用[4]。

在基礎(chǔ)矩陣估計算法的研究方面，Higgins提出了基礎(chǔ)矩陣估計的傳統(tǒng)8點估計算法[5]，主要特點是計算簡單，匹配速度快且易于實現(xiàn)，適用于簡單圖像匹配，但是對復(fù)雜情況適應(yīng)性較差，實際應(yīng)用比較困難。后來，Hartley提出了改進的8點算法[6]，通過規(guī)范匹配點數(shù)據(jù)的方法極大降低了噪聲的影響，提高了估算精度，但仍然存在估算誤差大的問題。

本文以Harris角點作為特征點，利用改進的歸一化互相關(guān)[7](Normalized Cross Correlation, NCC)方法對特征點進行粗匹配，并采用聚類法對匹配點進行提純，得到相對精確的匹配點，最后以這些點作為基本點估算基礎(chǔ)矩陣，完成整個圖像匹配過程。其中，為進一步提升匹配精度，本文在基礎(chǔ)矩陣估計的選點階段進行了改進，應(yīng)用統(tǒng)計學(xué)中常用的分塊隨機抽樣法抽取具有代表性的點，解決了因部分點太靠近導(dǎo)致的估計準(zhǔn)確性較差的問題。最后采用最小距離約束方法[8]進一步減小匹配誤差，并以平均對極距離作為評判標(biāo)準(zhǔn)對算法的有效性進行驗證。

2 角點提取和匹配

2.1 亞像素級Harris角點檢測

Harris角點是圖像匹配中常用的特征點，該特征點不受光照、姿態(tài)等因素影響，檢測結(jié)果可靠性高。Harris角點表示的是圖像中灰度值和梯度值沿任意方向都較大的特征點。Harris角點提取算法的基本思想為：通過計算像素灰度的一階導(dǎo)數(shù)估計自相關(guān)矩陣，當(dāng)矩陣的特征值都非常大時，其相應(yīng)的像素點即被認(rèn)為是角點。

綜合考慮基礎(chǔ)矩陣估計對特征點的要求，選用一種亞像素級的Harris角點檢測方法[9]，該方法在Harris提取角點過程中，通過兩次角點篩選，剔除非角點和偽角點，利用角點響應(yīng)函數(shù)執(zhí)行非極大值抑制，以局部角點響應(yīng)函數(shù)最大值的像素點作為初始角點，并以該初始角點為中心，以一定半徑搜索角點簇，采用最小二乘法加權(quán)角點簇與待求角點的歐幾里得距離，精化初始角點坐標(biāo)，從而準(zhǔn)確快速定位Harris亞像素角點。

傳統(tǒng)方法定義了角點響應(yīng)函數(shù)(Corner Response Function, CRF)，用R表示：

R=det(M)-Ktrace2(M),

det(M)=λ1λ2,

trace(M)=λ1+λ2。

(1)

式中：K是常數(shù)，通常取0.04～0.06;λ1、λ2是矩陣M的特征值。在CRF局部非極大值抑制得到的角點，忽略了周圍可能存在相似角點簇的影響，使得角點確定易受噪聲影響，抗噪能力差，致使角點定位有偏差。以具有CRF最大值的角點作為初始角點，考慮其一定半徑r內(nèi)角點簇對角點定位的貢獻，并以各CRF作為各自的權(quán)，采用最小二乘法加權(quán)歐幾里得距離角點精化初始角點坐標(biāo)，實現(xiàn)亞像素角點定位。

2.2 基于差分求和定理的粗匹配改進算法

NCC算法是一種經(jīng)典的灰度互相關(guān)匹配算法，該算法具有很好的準(zhǔn)確性和適應(yīng)性，對圖像的亮度變化和灰度值線性變化具有較好的魯棒性，但是運算速度慢，難以滿足實際應(yīng)用中對速度的要求。

本文采用文獻[10]提出的基于差分求和定理改進的NCC算法來提高匹配速度。設(shè)f(x)和g(x)是兩個含有N個變量的一維數(shù)組，滿足如下等式：

(2)

式中：

F(x)=f(x)-f(x+1),

G(x)=G(x-1)-g(x+1),

G(0)=0,

f(K+1)=0。

將模板T(m,n)內(nèi)所有點保存為一維數(shù)組f(x)，子圖內(nèi)對應(yīng)模板的點保存為g(x)。根據(jù)以上差分求和定理，可以將模板T和子圖Si,j的乘積轉(zhuǎn)化為對F(x)和G(x)的乘積運算。由于在灰度變化不大的圖像中，相鄰像素的灰度值非常接近，這樣差分后的數(shù)組內(nèi)會產(chǎn)生大量的0,1和-1元素，這些元素與其他元素的乘法運算可以忽略，因此可以簡化大量的運算；同時，在實際的模板匹配中，模板是固定的，故對其進行差分的運算只需進行一次，從而節(jié)省了時間，明顯提高了匹配速度。

2.3 快速聚類法提純匹配點

聚類法是一種無監(jiān)督學(xué)習(xí)算法，它是研究分類問題的一種統(tǒng)計分析方法，可以通過多次迭代自動找到類簇及聚類中心。本文利用聚類法去除一些錯誤的匹配點，可以在很大程度上提高匹配點的精度。

本文參考文獻[11]提出的快速聚類方法來尋找密度聚類中心。聚類的過程就是將兩幅圖像中的粗匹配點集中到同一個坐標(biāo)系中，并將對應(yīng)的匹配點通過矢量進行連接，對于正確的匹配點，所得到的矢量基本相似，而錯誤的匹配點形成的矢量則雜亂無規(guī)律。為便于計算，用斜率和大小表示矢量，定義如下：

(3)

(4)

其中，(x1，y1)、(x2，y2)分別是匹配點在兩幅圖像中的坐標(biāo)，通過以上公式可以將匹配矢量轉(zhuǎn)換成坐標(biāo)點(angle,d)的形式。

3 基礎(chǔ)矩陣估計算法的改進

基礎(chǔ)矩陣估計是圖像匹配算法的核心步驟，其基本思想是通過待匹配圖像間的部分匹配點得到圖像的對極幾何關(guān)系，并將這種關(guān)系以矩陣的形式表示，兩幅圖像間的其他匹配點可以通過該矩陣互相轉(zhuǎn)換。本文在Hartley 8點法的基礎(chǔ)上進行了改進，利用分塊隨機抽樣法解決其選點階段的問題，提高基礎(chǔ)矩陣估計的精度。

3.1 Hartley 8點法

圖像間的對極幾何關(guān)系表示如下：

(5)

寫成線性齊次方程：

f=(f11,f12,f13,f21,f22,f23,f31,f32,f33)T。

(6)

對于匹配點對的數(shù)目大于等于8的情況，可以隨機抽取8對點并把其坐標(biāo)信息帶入式(5)和式(6)計算出基礎(chǔ)矩陣F，這就是8點算法。

3.2 Hartley 8點法的改進算法

由于Hartley 8點法使用的樣本數(shù)據(jù)(匹配點)是隨機抽取的，容易產(chǎn)生因樣本點太靠近而不具有代表性的問題，降低了基礎(chǔ)矩陣估計的準(zhǔn)確性。因此，必須在基礎(chǔ)矩陣前對樣本數(shù)據(jù)進行預(yù)處理，本文借鑒了統(tǒng)計學(xué)中常用的分塊隨機抽樣法抽取具有代表性的點，用作8點法的樣本點。具體步驟如下：

(1)將模板圖像中所有提純后的匹配點mIi(x,y)(i=1,2,…,n)按其在圖像中的坐標(biāo)繪制在直角坐標(biāo)系中。

(2)分析各匹配點的坐標(biāo)信息，找出橫縱坐標(biāo)的最大值和最小值xmax,xmin,ymax,ymin。以此為邊界繪制矩形框，將所有點包括在矩形框內(nèi)。

下面以實際例子對該算法進行詳細說明：

圖2中的點是經(jīng)過Harris角點提取后得到的角點，圖3是經(jīng)過角點粗匹配和匹配點提純后得到的點，將圖3中的點以像素為單位繪制散點圖，并將散點圖平均分成25個矩形塊，按照從左到右，從上到下的順序給矩形塊排序，如圖4所示，根據(jù)每個矩形塊中點的數(shù)量占總點數(shù)的比例計算出每個塊被選中的概率。

由圖5可以直觀地看出每個塊中的點作為樣本點的概率，有效避免因樣本點太靠近造成誤差較大的問題。

預(yù)處理后的匹配點分布均勻，能夠較好地反映圖像間的關(guān)系，從而保證基礎(chǔ)矩陣估計的準(zhǔn)確性和穩(wěn)定性。

4 算法比較

4.1 基礎(chǔ)矩陣準(zhǔn)確性的評價指標(biāo)

由于基礎(chǔ)矩陣不具有可比性，需要將其轉(zhuǎn)換成可比較的量。對極距離表示的是匹配點到極線的距離，常以平均對極距離作為舉出矩陣準(zhǔn)確性的評價指標(biāo)。

(8)

(9)

式中，(FmIi)k表示向量FmIi中的第k項,k=1,2。通過以上距離公式可將求F問題轉(zhuǎn)化為求解距離問題：

(10)

式中:Di為對極距離，

(11)

4.2 標(biāo)準(zhǔn)圖像的匹配結(jié)果比較

圖6是取自美國明德伯格學(xué)院圖像處理資源庫中的標(biāo)準(zhǔn)圖像，此類標(biāo)準(zhǔn)圖像被廣泛應(yīng)用到圖像處理算法的驗證實驗中。以圖6a作為圖像匹配的基準(zhǔn)，圖6b為與之配對的匹配圖像，兩幅圖像僅有拍攝角度的區(qū)別。

按照圖像匹配的步驟，從以上圖像對中分別提取Harris角點，使用改進后的NCC算法對角點進行粗匹配，得到62對匹配點，分析可知，其中包含18對錯誤的匹配點，因此需要利用快速聚類法去除錯誤的匹配點。

通過式(3)和式(4)計算出上述62對匹配點的矢量坐標(biāo)，圖7所示為匹配矢量坐標(biāo)散點圖，其中灰色的較分散的點是18對錯誤的匹配點，聚在一起的是44對正確的匹配點。

利用得到的匹配點作為基礎(chǔ)矩陣估計的樣本點，計算出基礎(chǔ)矩陣，帶入式(10)得出對極距離。圖8表示的是匹配圖像I2中的部分極線，可以看出匹配點并不是完全落在極線上。

實驗結(jié)果以平均對極距離為比較指標(biāo)，并采用不同復(fù)雜程度的圖像依次增加匹配點數(shù)目，得到的結(jié)果如表1所示。

表1 基礎(chǔ)矩陣估計算法精度的實驗結(jié)果比較 mm

由表1可以得知，RANSANC為魯棒性估計算法，精度較高，且根據(jù)經(jīng)驗在誤匹配量接近50%時仍具有較好穩(wěn)定性，但是隨著匹配點的增多，匹配精度并沒有提高的趨勢，因此，不能通過增加匹配點的方式提高精度。Hartley 8點法的匹配精度最低，穩(wěn)定性較差。加權(quán)迭代算法和本文算法隨著匹配點數(shù)目的增多，匹配精度穩(wěn)定提高，但本文算法在精度方面控制得更好。

5 實驗驗證

為驗證算法的實際應(yīng)用效果，以實際生產(chǎn)線上的餅干箱為對象，進行了多組匹配實驗。從中選擇3組具有代表性的位置進行詳細分析。第一組的位姿和模板圖像的位姿差別很小，第二組的位姿在旋轉(zhuǎn)角度上有很大變化，第三組的位姿變化不僅包含角度平移，還有整體翻轉(zhuǎn)，進一步增加了匹配的困難程度。匹配結(jié)果如圖9所示，圖中白色線段連接的是一對匹配點。

表2除了分析圖9所示的匹配數(shù)據(jù)，還對后續(xù)的目標(biāo)定位進行了分析，得出了定位耗時和匹配精度，更直觀地反映了算法在實際應(yīng)用中的效果。

表2 目標(biāo)識別實驗數(shù)據(jù)分析

由表2中的數(shù)據(jù)可知，每次匹配的耗時都不超過100 ms，且保證了較高的匹配精度，可以滿足工業(yè)機器人搬運系統(tǒng)對實時性和精度的要求。

6 結(jié)束語

針對圖像匹配中存在的匹配速度慢和基礎(chǔ)矩陣估計精度不高等問題，本文以Harris角點作為圖像的特征點，通過合理選用以差分求和定理改進的NCC匹配算法和快速聚類法等對特征點進行預(yù)處理；針對基礎(chǔ)矩陣估計隨機選點階段會造成較大誤差的情況，將統(tǒng)計學(xué)中的分塊隨機抽樣法成功運用到匹配點預(yù)處理中；通過基礎(chǔ)矩陣計算圖像間對極幾何關(guān)系，并以平均對極距離作為評價指標(biāo)對實驗結(jié)果進行了分析，結(jié)果表明匹配速度和基礎(chǔ)矩陣估計精度均有不同程度的提高，充分驗證了算法的有效性。

本文對基礎(chǔ)矩陣估計的改進仍屬于非線性迭代算法，對于誤匹配點較多的情況，并不能完全去除，其估計穩(wěn)定性與魯棒性估計方法相比還有一定差距，因此進一步提高算法的穩(wěn)定性是下一步工作的重點。