時顥等

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

關鍵詞：FAST；SURF；BBF；RANSAC；外極線約束

中圖分類號：S126 文獻標志碼：A 文章編號：1002-1302（2014）03-0343-03

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

1 研究方法

1.1 FAST角點檢測

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

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

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

（1）

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

1.2 SURF描述向量

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

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

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

1.3 二叉樹搜索圖像匹配點對

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

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

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

（2）以此葉結(jié)點為“當前最近點”。

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

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

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

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

（1）歸一化八點法解基本矩陣

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

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

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

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

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

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

（2）極線約束

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

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

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

2 結(jié)果與分析

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

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

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

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

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

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

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

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

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

參考文獻：

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

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