馬庭田，葉文華，葉華欣

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

1 問(wèn)題的提出

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

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

對(duì)于兩幅圖像中的匹配點(diǎn)m1和m2，滿(mǎn)足如下等式：

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

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

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

2 角點(diǎn)提取和匹配

2.1 亞像素級(jí)Harris角點(diǎn)檢測(cè)

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

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

傳統(tǒng)方法定義了角點(diǎn)響應(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局部非極大值抑制得到的角點(diǎn)，忽略了周?chē)赡艽嬖谙嗨平屈c(diǎn)簇的影響，使得角點(diǎn)確定易受噪聲影響，抗噪能力差，致使角點(diǎn)定位有偏差。以具有CRF最大值的角點(diǎn)作為初始角點(diǎn)，考慮其一定半徑r內(nèi)角點(diǎn)簇對(duì)角點(diǎn)定位的貢獻(xiàn)，并以各CRF作為各自的權(quán)，采用最小二乘法加權(quán)歐幾里得距離角點(diǎn)精化初始角點(diǎn)坐標(biāo)，實(shí)現(xiàn)亞像素角點(diǎn)定位。

2.2 基于差分求和定理的粗匹配改進(jìn)算法

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

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

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

2.3 快速聚類(lèi)法提純匹配點(diǎn)

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

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

(3)

(4)

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

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

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

3.1 Hartley 8點(diǎn)法

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

(5)

寫(xiě)成線(xiàn)性齊次方程：

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

(6)

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

3.2 Hartley 8點(diǎn)法的改進(jìn)算法

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

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

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

下面以實(shí)際例子對(duì)該算法進(jìn)行詳細(xì)說(shuō)明：

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

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

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

4 算法比較

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

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

(8)

(9)

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

(10)

式中:Di為對(duì)極距離，

(11)

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

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

按照?qǐng)D像匹配的步驟，從以上圖像對(duì)中分別提取Harris角點(diǎn)，使用改進(jìn)后的NCC算法對(duì)角點(diǎn)進(jìn)行粗匹配，得到62對(duì)匹配點(diǎn)，分析可知，其中包含18對(duì)錯(cuò)誤的匹配點(diǎn)，因此需要利用快速聚類(lèi)法去除錯(cuò)誤的匹配點(diǎn)。

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

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

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

表1 基礎(chǔ)矩陣估計(jì)算法精度的實(shí)驗(yàn)結(jié)果比較 mm

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

5 實(shí)驗(yàn)驗(yàn)證

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

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

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

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

6 結(jié)束語(yǔ)

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

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