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

時顥等

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

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

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

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

1 研究方法

1.1 FAST角點(diǎn)檢測

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

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

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

（1）

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

1.2 SURF描述向量

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

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

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

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

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

K-D樹的最近鄰搜索算法如下：

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

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

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

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

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

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

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

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

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。對特征點(diǎn)進(jìn)行歸一化處理，可以提高算法的精度。由對應(yīng)匹配xi ^xi ^′形成A^，由A^的最小奇異值的奇異矢景，即A^的SVD分解A^=UDVT中矩陣V的最后一列矢量來確定F^。但由于基本矩陣的秩為2，所以必須通過強(qiáng)制惟約束，用SVD法將F^的秩歸為2，并以F′代替F使得detF′=0。

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

（2）極線約束

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

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

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

2 結(jié)果與分析

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

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

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

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

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

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

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

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

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

參考文獻(xiàn)：

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

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