基于改進SURF特征點的模板匹配算法

吳清輝

（廣州市威控機器人有限公司，廣州 511340）

0 引言

隨著智能制造技術的發展，機器人的智能性越來越受到關注。目前大多數機器人都是面對固定環境，重復完成固定任務，例如機器人抓取物體等。為了更好地引導機器人完成特定任務，機器視覺技術被越來越多地應用到機器人領域。其中目標識別[1－4]能夠幫助機器人檢測場景中的待抓取物體，在機器人抓取領域[5]有著重要的應用。目前來說針對圖像的目標識別問題算法主要有模板匹配以及圖像分割等，而其中由于基于特征點的模板匹配算法[6－9]涉及的參數相對較少，只需要在所獲得的圖像中搜索到之前已經確定的匹配項就可以識別出目標物體，這種類型的算法不僅簡單有效，而且有較強的魯棒性和可擴展性，運用也相對靈活。而其中SURF算法[10－11]在傾斜場景和縮小場景的提取較為穩定，并且實時性較好，已成為廣泛使用的特征點提取算法之一，但其描述子構建在匹配過程中易存在誤匹配的問題。基于此本文采用DAISY算法[12－13]構建特征描述符來代替SURF原本構建特征描述符方法，并采用PROSAC算法[14－15]進行誤匹配點刪除，結合上述兩種算法的優點提高匹配過程中目標識別的準確性。

1 基于改進SURF特征點的模板匹配目標識別算法

基于模板匹配完成目標識別的基本思路是在攝像機采集到的圖像上找到和之前已經確定的模板相近的對象，大致過程如下：

（1）生成與目標物體對應的模板圖像；

（2）采用某種算法對得到的模板圖像進行處理和訓練，構建出模板圖像對應的模型；

（3）根據構建出的模板模型來找出待檢測圖像，也就是攝像機獲得的圖像上的與模板相似或者一致的目標。

前兩步已經有著較好的實現，而第三步匹配精度仍有待提高。傳統的SURF特征點能夠在一定程度上緩解這一問題，因此該算法具有大量的應用，然而SURF算法雖然一定程度上兼顧了實時性和穩定性，但是實時性并不是太高，而且由于SURF算法描述子的局限性，在模板匹配過程中存在有一些誤匹配的情況，從而對目標識別造成影響，本文采用如下方法對SURF算法進行改進。

首先采用DAISY算法構建特征描述符來代替SURF原本構建特征描述符方法，該算法核心思想是采用一種將原始圖像的若干個方向圖與數個尺度不一的高斯濾波函數進行卷積的方法，由于高斯濾波函數具有可分離性，因此該方法具有較高的效率；其次在模板匹配過程中利用PROSAC算法進行誤匹配點刪除，PROSAC算法的核心是將樣本集中的點預先進行等級排名，能估計出正確模型的內點有更高的等級，對估計模型起到阻礙作用的外點具有較低的等級，然后選出等級較高的點集來對模型進行估計，這樣可以減少算法采樣的隨機性，提升獲得正確模型的成功率，從而降低算法迭代次數。

2 算法說明

2.1 SURF算法

在SURF算法中，生成特征點描述子的過程可由圖1所示，在提取出的關鍵點周圍生成一個由4×4共16個矩形塊構成的矩形區域，其中每一個矩形塊的分辨率為5×5，即由25個像素點構成。將矩形區域旋轉至主方向后（主方向為提取關鍵點過程中計算得到），統計各個子矩形塊中像素點相對于主方向的水平方向和豎直方向的haar小波特征[16]，這里的haar小波特征共包含4個方向，分別為水平梯度、豎直梯度、水平梯度絕對值之和以及豎直梯度絕對值之和。經過上述過程后，可以統計得到20×20個像素鄰域內的各方向分布，以此作為該關鍵點的描述子。從上述過程中可以看出由于該過程需要統計每個關鍵點周圍20×20共400個像素點的haar特征，其描述子向量維度一共有400×4＝1 600維，計算量較大，導致SURF算法較為耗時。

圖1 SURF算法說明

2.2 DAISY算法

本文提出采用DAISY算法替代SURF算法過程中生成描述子的過程。DAISY算法主要思想如圖2所示，對于每一個關鍵點，以該關鍵點為中心構建3層半徑不同的同心圓，在每一個同心圓上以45°為單位間隔，取8個點作為采樣點，這樣總共得到了3×8＋1＝25個采樣點，針對每一個采樣點，取8個不同方向的梯度，這樣就能獲得25×8＝200維的特征向量來描述該關鍵點的描述子。從上述過程中，可以看出一方面用于描述關鍵點的描述子向量維數大大降低了，并且在取采樣點的過程中，由于外圈的梯度可以通過內圈的梯度利用高斯卷積推算出來，這使得計算量大大降低了，同時由于采樣點均勻分布在同心圓上，描述子具有一定的魯棒性，不會降低匹配的精度。因此本文采用DAISY算法作為SURF算法的描述子提取過程。

圖2 DAISY算法說明

2.3 PROSAC算法

在特征點匹配過程中，由于存在外點（無法適應該匹配模型的數據），如果兩幀圖像的外點匹配上，那么會引入大量噪聲，對后續任務造成較大影響。傳統方法主要采用RANSAC算法[17]，其算法流程如下：

（1）首先根據兩幅圖像中提取的特征點生成匹配點對，從中隨機選取4個匹配點對；

（2）利用4個匹配點對計算出這兩幅圖像的變換矩陣H；

（3）利用變換矩陣H對所有的特征點做變換，如果變換后的特征點與第二幀圖像中對應的特征點距離小于一定閾值，則將其加入到滿足一致集合C中，即內點集合；

（4）如果當前的一致集合元素個數大于最優的一致集合元素個數，更新當前最優一致集合；

（5）重復（2）～（4）過程，直至迭代終止，迭代終止條件為迭代次數達到最大迭代次數k，計算如下：

式中：p表示置信度，通常取0.995；w表示內點比例；m為取的匹配點對數，取4。

從上述步驟可以看出RANSAC算法忽略了匹配點對的優劣性，由于匹配點對集合中有著匹配度契合的點對，也有匹配度較差的點對，如果在集合中隨機采樣，如果取得了較差的匹配點對，那么將會浪費很多時間。因此本文采用了PROSAC算法，PROSAC算法相較于RANSAC算法改進有兩個方面，首先對匹配點對的優劣性進行排列，取匹配度高于一定閾值的點對作為假設生成集，在假設生成集中進行隨機采樣。這樣針對匹配過程中的PROSAC算法過程則是在RANSAC算法過程中進行了一步預處理操作，即多了一步生成假設生成集的過程。有了該過程的加入后，可以避免匹配度低的點對的計算量，大大提高了該算法的計算過程。并且，由于是在較優的匹配點對中選取，可以使得模型整體匹配效果大大提升，避免了噪聲及局外點對匹配模型的影響。

3 實驗結果對比

根據上述兩種算法的優點，本文在SURF的基礎上，改用DAISY算法來生成描述子能夠進一步提高算法的實時性，然后再通過PROSAC算法進行匹配提純，改進算法與基于SURF算法的匹配對比如圖3所示，其實時性對比如表1所示，可以發現經過改進之后的算法在旋轉、縮小、放大、過亮、過暗場景中均有效去除了誤匹配點對，并且也提高了實時性。例如在旋轉場景中，可以看出書的上半部分與書的下半部分較為相似（均為大塊白色區域），都有著很大一部分的白色區域，因此可以看到在書的上邊緣提取出的SURF特征點很容易就匹配上了書下半部分的SURF特征點，導致匹配點對不對應。但采用了DAISY算法以及PROSAC算法后，由于DAISY算法取了不同尺度下的高斯卷積，多尺度描述子的獲得使其關鍵點描述不再局限于局部（可以獲得更大范圍內的灰紋理區域），配合PROSAC算法提供的高魯棒性匹配，大量的誤匹配點對被濾除，因此匹配效果大大提升了，而且實時性也有一定的提升。此外，值得一提的是，雖然在傾斜場景中改進算法提升的效果并不明顯，因為傾斜場景下書對應的描述子區域在DAISY算法下與SURF算法下相差無幾，因此區分度較低，故沒有明顯的提升效果，然而其實時性大大提升了，從每幀圖像耗時0.634 s提升至每幀圖像耗時0.615 s。

圖3 改進算法（右）與基于SURF算法（左）在不同場景的匹配效果對比

表1 改進算法與基于SURF算法在不同場景所耗時間對比

4 結束語

本文在SURF模板匹配方法基礎上進行了改進。包括使用DAISY算法構建描述子以提高效率，并使用PRO?SAC算法進行匹配提純，最后通過實驗證了改進算法在旋轉、傾斜、放大、縮小、過亮、過暗場景中的有效性，并且相較于SURF模板匹配方法有效剔除了誤匹配點對，并且一定程度上提高了模板匹配算法的實時性。但本文工作仍存在不足，本文中模板圖像只是取了目標物體某一面的信息，對于同一物體換一個面就無法識別，所以本文中所述方法只是針對采集到的物體的可見表面進行識別與重建，缺少物體的完整信息，后續可以考慮對物體進行多視角的圖像采集，建立完整的圖像信息庫，或構造物體的三維模型作為模板，實現對目標更全面、可靠、可靠地識別。