基于SURF與BBF的棉花圖像匹配算法

時(shí)顥等

摘要：在棉花圖像分割與識(shí)別的基礎(chǔ)上，為獲得棉花三維空間位置信息，需要對(duì)雙目采集的棉花圖像對(duì)進(jìn)行精確的匹配。采用加速分割檢測(cè)特征、加速魯棒性特征和BBF方法匹配棉花圖像對(duì)。首先采用FAST檢測(cè)圖像角點(diǎn)，并計(jì)算各角點(diǎn)的SURF描述向量，然后采用BBF方法搜索匹配點(diǎn)對(duì)，最后利用RANSAC和極線約束剔除誤匹配點(diǎn)對(duì)，為下一步準(zhǔn)確定位棉花三維空間位置信息奠定基礎(chǔ)。

關(guān)鍵詞：FAST；SURF；BBF；RANSAC；外極線約束

中圖分類(lèi)號(hào)：S126 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：1002-1302（2014）03-0343-03

圖像匹配在三維重構(gòu)、導(dǎo)航圖像處理、圖像搜索、圖像融合等計(jì)算機(jī)視覺(jué)領(lǐng)域應(yīng)用廣泛，基于局部特征的匹配逐漸成為研究的熱點(diǎn)。基于特征點(diǎn)的檢測(cè)算法，如Harris-Affine、SIFT[1-2]算法，能夠?qū)崿F(xiàn)較準(zhǔn)確的匹配對(duì)，但計(jì)算時(shí)間較長(zhǎng)。2006年，Bay等人提出SURF（speeded-up robust features）特征算子在匹配性能方面接近SIFT算法，但計(jì)算時(shí)間較快，王海麗[3-4]等人將SURF算法應(yīng)用于SAR圖像等領(lǐng)域，實(shí)現(xiàn)匹配的抗視角變換。上述匹配算法特征點(diǎn)的邊緣特性較差，在計(jì)算時(shí)間方面仍然較長(zhǎng)。本研究在前人研究的基礎(chǔ)上提出基于FAST角點(diǎn)檢測(cè)、SURF描述向量和BBF搜索匹配點(diǎn)的算法，具有良好的邊緣特性與高效的分割速度。

1 研究方法

1.1 FAST角點(diǎn)檢測(cè)

加速分割檢測(cè)特征（features from accelerated segment test，F(xiàn)AST）是一種簡(jiǎn)單快速的角點(diǎn)探測(cè)算法，當(dāng)某個(gè)像素點(diǎn)的周?chē)I(lǐng)域內(nèi)有足夠多的像素點(diǎn)與該點(diǎn)處于不同的灰度區(qū)域時(shí)，該點(diǎn)被確認(rèn)為一個(gè)FAST角點(diǎn)。應(yīng)用到灰度圖像中，即有足夠多的像素點(diǎn)的灰度值大于該點(diǎn)的灰度值或者小于該點(diǎn)的灰度值。考慮圖像中任意一個(gè)像素點(diǎn)和以它為中心的一個(gè)區(qū)域，通常選擇圓形區(qū)域，圖1給出了以該點(diǎn)為中心的圓形區(qū)域的模板情況，該圓形區(qū)域?yàn)橐粋€(gè)半徑等于3像素的離散化區(qū)域，最外圍的像素點(diǎn)按順時(shí)針順序依次編號(hào)為1～16。

一個(gè)候選點(diǎn)是否為角點(diǎn)可以用一個(gè)角點(diǎn)響應(yīng)函數(shù)來(lái)判斷，即：

N=∑x（circle（p））|Ix-Ip|>εd

（1）

式中：Ix表示圓周上任意一點(diǎn)的圖像灰度值；Ip表示中心像素點(diǎn)的圖像灰度值；p表示中心像素點(diǎn)即候選點(diǎn)；εd為給定的一個(gè)極小閾值。通過(guò)該角點(diǎn)響應(yīng)函數(shù)，計(jì)算出圓周上滿(mǎn)足公式（1）像素點(diǎn)的個(gè)數(shù)N。如果N大于給定的一個(gè)閾值，就可以確定該候選點(diǎn)為角點(diǎn)。為實(shí)現(xiàn)快速計(jì)算，一般選擇n=12。角點(diǎn)檢測(cè)可簡(jiǎn)化為檢測(cè)像素編號(hào)為1、9、5、13的4個(gè)像素點(diǎn)，因?yàn)樵谠?個(gè)像素點(diǎn)中，有3個(gè)均滿(mǎn)足公式（1），才能被確認(rèn)為角點(diǎn)，如此可以快速排除整幅圖像中的很多像素點(diǎn)，提高角點(diǎn)檢測(cè)的時(shí)間效率。

1.2 SURF描述向量

SURF描述向量主要是根據(jù)特征點(diǎn)鄰域范圍內(nèi)的灰度統(tǒng)計(jì)信息[5-6]，通過(guò)計(jì)算主方向和特征向量來(lái)得到的，具體步驟如下。

1.2.1 SURF特征點(diǎn)主方向的確定 本研究采取將原圖檢測(cè)到的極值點(diǎn)轉(zhuǎn)換到灰度圖像中，利用灰度圖像的信息生成特征描述向量。為保證旋轉(zhuǎn)不變性，以特征點(diǎn)為圓心、6σ（σ為特征點(diǎn)所在的尺度值）為半徑的圓形區(qū)域內(nèi)的所有像素x和y方向上的Haar小波響應(yīng)dx和dy，使每個(gè)像素點(diǎn)都有一個(gè)對(duì)應(yīng)的Haar小波響應(yīng)點(diǎn)Hp（dx，dy）；然后，通過(guò)一個(gè)大小為600的扇形滑動(dòng)窗口對(duì)所有小波響應(yīng)進(jìn)行求和，選擇長(zhǎng)度最長(zhǎng)的方向作為特征點(diǎn)的主方向。

1.2.2 基于Haar小波響應(yīng)生成描述向量 SURF特征向量提取是在一個(gè)以特征點(diǎn)為中心、與主方向平行的方形區(qū)域中進(jìn)行的：首先確定一個(gè)以特征點(diǎn)為中心、大小為20S的方形區(qū)域，為使提取到的特征向量具有抗旋轉(zhuǎn)特性，需要旋轉(zhuǎn)該方形區(qū)域，使之與特征點(diǎn)的主方向平行；然后，將這個(gè)方形區(qū)域再均勻細(xì)分成4×4個(gè)子區(qū)域，在每個(gè)子區(qū)域中統(tǒng)計(jì)x和y方向上的Haar小波響應(yīng)之和及其絕對(duì)值之和（∑dx，∑dy，∑|dx|，∑|dy|）。在統(tǒng)計(jì)的過(guò)程中，仍用以特征點(diǎn)為中心的高斯函數(shù)進(jìn)行賦權(quán)處理。如此，每個(gè)子區(qū)域有一個(gè)四維的描述子V4=（∑dx，∑dy，∑|dx|，∑|dy|），整個(gè)區(qū)域就有4×4×4=64維的特征向量。再進(jìn)行歸一化，形成特征點(diǎn)的描述向量。

1.3 二叉樹(shù)搜索圖像匹配點(diǎn)對(duì)

1.3.1 K-D樹(shù) K-D樹(shù)是一棵平衡二叉樹(shù)，K-D代表 K-Dimension，每個(gè)節(jié)點(diǎn)即為一個(gè)K維的點(diǎn)。每個(gè)非葉節(jié)點(diǎn)可以想象為一個(gè)分割超平面，用垂直于坐標(biāo)軸的超平面將空間分為2個(gè)部分，這樣遞歸的從根節(jié)點(diǎn)不停的劃分，直到?jīng)]有實(shí)例為止[7-8]。

K-D樹(shù)的最近鄰搜索算法如下：

（1）在K-D樹(shù)中找出包含目標(biāo)點(diǎn)x的葉結(jié)點(diǎn)：從根結(jié)點(diǎn)出發(fā)，遞歸地向下搜索K-D樹(shù)。若目標(biāo)點(diǎn)x當(dāng)前維的坐標(biāo)小于切分點(diǎn)的坐標(biāo)，則移動(dòng)到左子結(jié)點(diǎn)，否則移動(dòng)到右子結(jié)點(diǎn)，直到子結(jié)點(diǎn)為葉結(jié)點(diǎn)為止。

（2）以此葉結(jié)點(diǎn)為“當(dāng)前最近點(diǎn)”。

（3）遞歸的向上回溯，在每個(gè)結(jié)點(diǎn)進(jìn)行以下操作：（a）如果該結(jié)點(diǎn)保存的實(shí)例點(diǎn)比當(dāng)前最近點(diǎn)距離目標(biāo)點(diǎn)更近，則更新“當(dāng)前最近點(diǎn)”，也就是說(shuō)以該實(shí)例點(diǎn)為“當(dāng)前最近點(diǎn)”。（b）當(dāng)前最近點(diǎn)一定存在于該結(jié)點(diǎn)一個(gè)子結(jié)點(diǎn)對(duì)應(yīng)的區(qū)域，檢查子結(jié)點(diǎn)的父結(jié)點(diǎn)的另一子結(jié)點(diǎn)對(duì)應(yīng)的區(qū)域是否有更近的點(diǎn)。

1.3.2 BBF查詢(xún)算法 BBF（best bin first）是對(duì)K-D樹(shù)搜索算法的改進(jìn)。實(shí)際上，K-D樹(shù)搜索算法大部分時(shí)間花費(fèi)在檢查節(jié)點(diǎn)上，而只有一部分節(jié)點(diǎn)滿(mǎn)足最近鄰條件，因此，可以采用近似的最近鄰算法，通過(guò)限制K-D樹(shù)中葉子節(jié)點(diǎn)數(shù)來(lái)縮短搜索時(shí)間。優(yōu)化改進(jìn)方法是以節(jié)點(diǎn)和被查詢(xún)節(jié)點(diǎn)距離遞增的順序來(lái)搜索節(jié)點(diǎn)。當(dāng)沿一個(gè)方向的分支搜索一節(jié)點(diǎn)時(shí)，優(yōu)先級(jí)隊(duì)會(huì)被加入一個(gè)成員，該成員記錄了該節(jié)點(diǎn)相關(guān)的信息，包括當(dāng)前節(jié)點(diǎn)在樹(shù)中的位置和該節(jié)點(diǎn)與被查詢(xún)節(jié)點(diǎn)之間的距離。當(dāng)一個(gè)葉節(jié)點(diǎn)被搜索到后，從隊(duì)首刪除一項(xiàng)；然后，再搜索包括最近節(jié)點(diǎn)的其他分支。

1.4 RANSAC與極限約束剔除偽匹配

在匹配點(diǎn)對(duì)中仍然存在部分誤匹配對(duì)以及匹配不準(zhǔn)的點(diǎn)，由于匹配點(diǎn)對(duì)的正確率在很大程度上決定了后期進(jìn)行三維重建的精度，因此需要對(duì)初始匹配點(diǎn)對(duì)集合進(jìn)行進(jìn)一步的篩選。本研究利用RANSAC算法在未得到基本矩陣的情況下消除誤匹配點(diǎn)對(duì)，同時(shí)獲得優(yōu)化后的基本矩陣，再利用極線約束進(jìn)一步得到高精度的匹配點(diǎn)對(duì)，為下一步的三維重建打下良好的基礎(chǔ)。

（1）歸一化八點(diǎn)法解基本矩陣

從n組點(diǎn)匹配的集合可以得到一個(gè)線性方程組：

Af=x1′x1x1′y1x1′y1′x1y1′y1y1′x1y11

xn′xnxn′ynxn′yn′xnyn′ynyn′xnyn1=0

利用歸一化8點(diǎn)法可以求解上述方程組，可以得到基本矩陣F。具體算法如下：

歸一化：根據(jù)xi ^=Txi和xi ^′=T′xi′變換圖像坐標(biāo)，其中T和T′是歸一化變換，由平移和縮放組成。它將點(diǎn)集Xi變換到新的點(diǎn)集X～i，使得該點(diǎn)集X～i的形心位于原點(diǎn)（0，0）T，并且它原點(diǎn)的平均距離是2。對(duì)特征點(diǎn)進(jìn)行歸一化處理，可以提高算法的精度。由對(duì)應(yīng)匹配xi ^xi ^′形成A^，由A^的最小奇異值的奇異矢景，即A^的SVD分解A^=UDVT中矩陣V的最后一列矢量來(lái)確定F^。但由于基本矩陣的秩為2，所以必須通過(guò)強(qiáng)制惟約束，用SVD法將F^的秩歸為2，并以F′代替F使得detF′=0。

解除歸一化：令F=TTF^′T。矩陣F是對(duì)應(yīng)于原始數(shù)據(jù) xi ^xi ^′ 的基本矩陣。

（2）極線約束

根據(jù)對(duì)極幾何原理，其對(duì)應(yīng)幾何關(guān)系如圖2所示，如果已知空間點(diǎn)M在左圖像中的像點(diǎn)m，那么它在右圖像中的對(duì)應(yīng)點(diǎn)m′必然約束于對(duì)極線l′上，因此存在一個(gè)從左視圖上的點(diǎn)到右視圖上與之對(duì)應(yīng)的對(duì)極線的映射：m→l′，這個(gè)映射也可表示成矩陣形式，稱(chēng)為基本矩陣F，基本矩陣的本質(zhì)描述了2個(gè)攝像機(jī)平面的位置關(guān)系。

（3）RANSAC算法與極線約束的匹配點(diǎn)優(yōu)化

在初始匹配結(jié)果中，隨機(jī)選擇8組匹配點(diǎn)構(gòu)成的一個(gè)隨機(jī)樣本，并按歸一化八點(diǎn)法來(lái)計(jì)算基本矩陣F。根據(jù)計(jì)算得到的F，對(duì)每組假設(shè)對(duì)應(yīng)計(jì)算距離d=xi ^′Fxi ^。根據(jù)基本矩陣的定義，理論上x(chóng)i ^′Fxi ^=0，但是由于有誤匹配點(diǎn)對(duì)的存在以及匹配點(diǎn)的不準(zhǔn)確造成d不為零，因此可以定義d 如圖3所示，通過(guò)前面所求得的最佳基本矩陣F即可畫(huà)出對(duì)應(yīng)的極線，左圖中的直線為右圖中的點(diǎn)在左圖中找到的相對(duì)應(yīng)極線。根據(jù)對(duì)極幾何原理，若為精確匹配點(diǎn)對(duì)，則極線應(yīng)該穿過(guò)左圖中的匹配點(diǎn)，因此可以濾除那些距離極線較遠(yuǎn)的點(diǎn)，從而保留那些精確匹配的點(diǎn)對(duì)[10]。

2 結(jié)果與分析

本研究是基于研究采棉機(jī)器人視覺(jué)系統(tǒng)基金項(xiàng)目，為實(shí)現(xiàn)棉花的三維空間定位，在圖像分割的基礎(chǔ)上實(shí)現(xiàn)圖像對(duì)的精確匹配。

本試驗(yàn)條件為CPU2.80G、內(nèi)存2G。

FAST角點(diǎn)檢測(cè)算法是在灰度圖像中檢測(cè)角點(diǎn)，有足夠多的像素點(diǎn)的灰度值大于該點(diǎn)的灰度值或者小于該點(diǎn)的灰度值。由圖4可以看出，利用FAST檢測(cè)出的角點(diǎn)均在棉花的邊緣或是棉花的形心位置，有很好的邊緣特性，利于定位采摘點(diǎn)的位置信息。并且，F(xiàn)AST角點(diǎn)檢測(cè)出1 339個(gè)特征點(diǎn)，而SURF角點(diǎn)檢測(cè)算法只檢測(cè)出415個(gè)特征點(diǎn)，且部份特征點(diǎn)分布于棉花目標(biāo)外，不能用于棉花采摘點(diǎn)的定位（圖5）。因此本研究采用FAST角點(diǎn)檢測(cè)算法用于檢測(cè)棉花圖像對(duì)的特征點(diǎn)。

由于SURF方法具有良好的抗旋轉(zhuǎn)性，而且SURF向量為64維，相比于SIFT（128維）向量具有更低的維數(shù)，具有更快的速度。SURF特征向量如圖6所示。

基于上述檢測(cè)出的特征點(diǎn)與特征向量，建立K-D樹(shù)，并采用BBF方法搜索圖像匹配的對(duì)，結(jié)果如圖7所示。

從圖7可以看出，195對(duì)匹配點(diǎn)對(duì)中仍然存在部分誤匹配點(diǎn)對(duì)，采用RANSAC剔除誤匹配點(diǎn)對(duì)，結(jié)果如圖8所示。

采用RANSAC方法剔除誤匹配點(diǎn)對(duì)后，采用極限約束準(zhǔn)則進(jìn)一步提高匹配精度，淘汰掉一些匹配精度不高的匹配的對(duì)，結(jié)果如圖9所示。

在圖像對(duì)匹配中，圖像對(duì)往往伴隨著旋轉(zhuǎn)、縮放等各種復(fù)雜情況，在圖9中分別就圖像縮放、旋轉(zhuǎn)30°、180°條件采用本研究方法進(jìn)行匹配，仍然可以得到很精確的匹配的對(duì)，切特征點(diǎn)均分布在棉花的邊緣與棉花的型心位置（圖9b、c）。

為評(píng)價(jià)匹配效果，將本研究的匹配方法分別與SURF和SIFT方法進(jìn)行比較[11-12]，其對(duì)比結(jié)果如表1所示。

參考文獻(xiàn)：

[1]李玲玲，李翠華，曾曉明，等. 基于Harris-Affine和SIFT特征匹配的圖像自動(dòng)配準(zhǔn)[J]. 華中科技大學(xué)學(xué)報(bào)：自然科學(xué)版，2008，36（8）：13-16.

[2]謝 凡，秦世引. 基于SIFT的單目移動(dòng)機(jī)器人寬基線立體匹配[J]. 儀器儀表學(xué)報(bào)，2008，29（11）：2247-2252.