基于FAST檢測及SIFT描述的特征檢測算法

常旭劍，韓 燮，熊風光

（中北大學 計算機與控制工程學院，山西 太原030051）

0 引 言

通常，提取特征點分為兩步：特征點檢測和特征點描述。特征點檢測就是找到圖像中的特征點位置以及該特征點周圍像素的信息；特征點描述需要在不同變化因素下依舊保持較好的可匹配性。

本文提出一種FAST－SIFT 局部特征探測算法，首先采用FAST 特征檢測算法來檢測待測圖像中的特征點，根據FAST 獲得的特征點采用SIFT 特征描述算法對特征點進行描述；對這些獲得的描述特征點，采用基于SNR 驗證的特征點匹配進行闡述，有效地提高特征點檢測的速度及描述的精度，從而提高匹配度。

1 相關工作

許多論文中提出了很多特征檢測算法，Canny［1］，Harris［2］，及多尺度Harris［3］；特 征 描 述 算 法SIFT［4］，Affine SIFT［5］等；以及特征匹配算法FLANN［6］等。通過不同特征檢測算法與特征描述算法可以構成不同的組合。

1.1 特征檢測

John F Canny提出了多級邊緣檢測算法，是采用尋找圖像中亮度梯度的方法，該方法可以快速地找到圖像的邊緣，但是卻無法有效地提取圖像的特征點；Schmid等提出利用Harris角點檢測提取局部特征，利用Harris提取的局部特征不但具有抗旋轉變化的特性，而且對光照及噪聲有很強的魯棒性，但是通過該方法提出的特征在尺度縮放的應用上效果很差；Dufournaud等基于Harris特征檢測方法的基礎上提出多尺度Harris的特征檢測算法，盡管解決了尺度縮放應用問題，但是會提出大量重復特征，大幅增加錯誤匹配和匹配時間復雜度。直到Lowe提出基于多尺度下不變特征 （scale invariant feature transform，SIFT），此算法在特征檢測過程中采用了DoG （difference－of－Gaussian）算子，來構造尺度空間，在每個尺度下，選取出對應尺度空間所有的極值點，這些極值點信息即為所檢測圖像的特征點。但是由于采用DoG 建立尺度空間，算法的時間復雜度相對較大，比較耗時。

1.2 特征描述

特征描述向量一般是使用一個n維向量來對每個特征點的信息描述。M K Hu［7］提出基于不變矩理論的統計特征提取方法，廣泛應用在彩色圖像處理中。SIFT 是Lowe提出的，由于SIFT 對尺度、旋轉以及光照等變量的變化具有不變性，使得SIFT 特征描述子具有極強魯棒性，在特征點檢測中應用最為廣泛。ASIFT （affine sift）在SIFT 的基礎上對所有成像視角下得到的圖像進行特征匹配，克服了SIFT 在視角變化情況下，尤其是在特別大的視角變化下匹配度不高的缺點。

1.3 特征匹配

在特征檢測獲得的特征點后，需要進行特征描述，得到描述特征向量，最后通過分析這些特征向量進行分類匹配。本文采用了K－D樹進行特征向量匹配。

2 特征點檢測與描述

2.1 FAST特征檢測算法

很多傳統的檢測算法如SIFT，SURF 等很耗時，圖像處理中第一步一般都是特征檢測，如果在這一步耗時太多，顯然得不償失。Edward Rosen 提出的基于像素搜索的FAST （features from accelerated segment test）［8］是 目 前 公認的檢測速度較快的特征點檢測方法，速度達到毫秒 （ms）級別。

FAST 特征檢測算法是基于角點的定義。FAST 算法主要包含3個步驟：

（1）待檢測的點周圍的一圈像素的灰度值與候選的點的灰度值差別夠大，可以認為這個候選點是一個特征點，在二維圖像中任意一點圓心坐標 （x，y）。特征點描述算法公式如下

式中：t——閾值， （一般取t＝10），其中定義圓周上任意一點的灰度為Ix，圓心的灰度為Ip。當中心像素的灰度值Ip小于周圍圈點x處像素灰度值Ix＋t時，則認為該灰度像素屬于更暗的，則Sp→x＝d；以此類推相似的s和更亮的灰度像素點b。這樣在這么一個以候選特征點p 為圓心的圓形區域邊緣就找到了3種類型的灰度像素點d、s和b。統計d 或b 的次數，如果大于n （當分割測試點數目為12時，即Ix的個數的3／4），則認為該點為候選特征點。本實驗中采用模版半徑為3，即需要和周圍16個像素比較。

FAST 算法特征點檢測算法如圖1所示。

圖1 FAST 算法特征點檢測算法

（2）然后，通過固定半徑圓上像素的灰度值進行比較獲得候選特征點。利用ID3分類器，根據16個特征，判斷此候選特征點是否為特征點。將上面步驟獲得的d、s、b記作Pd、Ps、Pb，計算得到的Sp→x必定對應式 （1）的某種情況。令Ip為特征點時kp＝true，否則false。從而判定某個像素是否為特征點。

（3）最后，通過ID3決策樹算法訓練特征點，使用計算角點響應函數。定義一個響應函數V 如下

可以用常規極大值抑制法對非特征點進行排除。

2.2 SIFT特征描述算法

2.2.1 特征點的方向匹配

檢測到的局部特征，描述的重點是局部特征的魯棒性及可區分性。

通過FAST 特征檢測算法，已經找到了待處理圖像的特征點位置，下一步通過SIFT 算法所提供的特征描述算法來對特征點進行描述，為下一步的匹配做準備。

SIFT 描述算法是采用SIFT 特征探測算法中獲得的DoG 金字塔的特征點，采用在高斯金字塔3σ鄰域窗口內像素的梯度和方向特征分布，但是本文提出方法采用的不是尺度空間，故梯度的模值及方向如下

式中：L——特征點所在的尺度空間值，按照尺度采樣的3σ原則，鄰域半徑16×16為采樣窗口。

特征點的梯度計算過程如圖2 所示。首先如圖2 （a）中的特征點把周圍像素的梯度方向和幅值分別通過式 （3）、式（4）算出，如圖2 （b）所示其鄰域像素梯度方向和幅值。進一步分割如圖2 （c）所示。在圓周0～360°內分割成梯度直方圖，45°一柱，分為8柱，其中每個直方圖值代表該點方向，直方圖最大值即為該關鍵點方向，如圖2 （d）所示。

圖2 特征點產生直方圖

2.2.2 特征點的特征描述

通過2.2.1特征點的方向匹配的步驟，對于采用FAST找到的每個特征點，都賦予了每個特征點兩個重要的信息：位置 （FAST 獲得）、方向 （SIFT 賦予）。

接下來，需要為每個特征點建立一個描述向量。使得這些特征點不隨著光照、視角的變化而變化等。這個SIFT描述子不但包括此特征點，也包含了特征點周圍對其有貢獻的其它像素點，使得該特征點描述子具有較高的唯一性，以便可以提高特征點的正確匹配概率。

特征點描述子在4×4的窗口內計算8個方向的梯度學習，那么就是4×4×8＝128維度的向量表征。

3 特征點臨近匹配

3.1 特征點匹配

通過FAST檢測算法找到待測圖像的特征點后，用SIFT特征描述算法把找到的特征點通過4×4×8＝128維度的向量表示，下一步就要通過匹配來驗證找到特征點的正確性。

匹配檢索的過程包括了存儲SIFT 描述特征點的鍵值以及鑒別待匹配圖像中獲得的鍵值。在這里采用的是最優節點優先算法 （best bin first）算法，此算法是SIFT 的作者Lowe在KD－tree算法的基礎上的改進，利用BBF計算可以確定概率高的鄰域下的特征點，從而減少計算量。

3.2 基于SNR 驗證的特征點匹配

3.2.1 基本思路

如圖3所示，每個特征點在二維圖像中都有一組對應坐標，設與圖像（a）中的特征點是 （xai，yai）對應的圖像（b）的特征點為（xbi，ybi），那么對應的Δxi＝｜xai－xbi｜及Δbi＝｜yai－ybi｜應該服從正態分布。

如圖4為所對應的匹配的高斯分布，首先確定峰值，好的匹配可以找到一個峰值，如圖4 （a）中的P1，P2不是一個好的峰值，因為有次高峰值干擾。然后確定對應面積，圖4 （b）對應面積越大越好 （實框好于虛框）。

3.2.2 算法實現

最后，確定信噪比，值越高越好。如圖5 所示，目標物體逐次和不同場景圖片比對，獲得不同信噪比SNRn。

圖3 特征點匹配

圖4 特征點在x、y軸上的差值直方圖

圖5 目標物體與不同場景匹配信噪比結果

獲得信噪比后，可簡單采用Max（SNRx）為最佳匹配，但為了進一步提高匹配的精度以及系統魯棒性。本文采用樸素貝葉斯分類［10］，此方法基本思想是概率統計推理，在各種條件的已知且知道其出現的概率但是存在不確定哪個出現情況下，來做出決策。

4 實驗結果與分析

4.1 實驗結果

如圖6所示為欲檢測物體以及干擾物體。

圖6 目標檢測物及干擾物體

把目標物體a （書）置于高度雜亂的環境中。運行FAST 檢測算法，提取出376個FAST 特征點，利用SIFT描述算法描述FAST 檢測到的特征點，如圖7所示。

FAST特征算法提取在本實驗環境下（8－cores，2.4GHz intel i7，16Gb RAM）提取376個特征點用時8ms，SIFT描述符用時183ms。本文中限制FAST點在30像素（為減少獲得的總特征點的點數，增強系統的魯棒性）。

圖7 FAST 特征點提取

這些特征關鍵點都嘗試匹配數據庫中每個物體／子物體關鍵點。匹配所有數據庫中物體過程耗時57ms。直方圖在x軸以及y軸上位移如圖8所示標出了匹配的質量：信噪比（SNR），計算了每一個匹配的信噪比。

最后匹配的概率通過使用樸素貝葉斯分類的方法，把數據庫中每個物體進行計算。先對所檢測物體所在類別進行初步分類，然后在子類內進行檢測。實驗結果如圖9所示。

圖8 x軸及y軸上的匹配差值直方圖

圖9 數據庫中物體與場景中物體匹配結果

4.2 實驗結果評估

本文提出算法，實驗中采用了700 個樣本，通過不同的最優化值來計算。本文對FAST 和SIFT 的組合的性能與常見的幾個傳統組合的速度和性能進行了對比。見表1，可以看到SIFT＋SIFT 的組合是匹配比最高的，但是耗時也是最長的。FAST 是目前檢測速度最快的特征提取算法，達到微秒 （μs）級別。其效用比的直方圖如圖10所示。

5 結束語

本文提出一種全新的FAST－SIFT 局部不變特征的檢測和描述算法的組合進行特征點檢測的算法，并且將其應用于物體在復雜場景中的匹配。在局部特征檢測方面采用速度快的FAST 來進行檢測，獲得目標圖像中的極值點。再采用SIFT 特征描述算法，對獲得的特征極值點進行描述，得到了128維的描述向量。在基于SNR 樸素貝葉斯分類的分類匹配，不但結合了FAST 檢測快速性，SIFT 描述的準確性，以及貝葉斯分類的魯棒性，由于前期FAST 檢測的簡單快速性，大幅度提高了圖像匹配的速度，大量圖像匹配和減速的實驗結果驗證了本文算法的有效性。

表1 常見特征點探測描述算法間不同組合耗時對比

圖10 常見特征點探測描述算法間不同組合對比效用比

［1］Deng Caixia.Image edge detection algorithm based on improved canny operator ［C］／／International Conference on Wavelet Analysis and Pattern Recognition，2013：168－172.

［2］Wang Xiangyang.Invariant image watermarking using multiscale Harris detector and wavelet moments［J］.Computers ＆Electrical Engineering，2010，36 （1）：31－44.

［3］XU Xianfeng.An improved multi－scale Harris feature point detection method ［J］.Computer Engineering，2012，38 （17）：65－68 （in Chinese）.［徐賢鋒.一種改進的多尺度Harris特征點檢測方法 ［J］.計算機工程，2012，38 （17）：65－68.］

［4］Lowe D.Distinctive image features from scale－invariant keypoints［J］.International Journal of Computer Vision，2004，60 （2）：91－110.

［5］Morel JM，Yu G.ASIFT：An algorithm for fully affine invariant comparison ［J］.SIAM Journal on Imaging Sciences，2009，2 （2）：1597－1600.

［6］Zhang Xuejie.A physical system for binocular vision through saccade generation and vergence control［J］.Cybernetics and Systems：An International Journal，2009，40 （6）：549－568.

［7］DOU Jianfang.Automatic registration of visible and infrared images based on corners and Hu invariant［J］.Infrsred，2011，32 （7）：23－27（in Chinese）.［竇建方.基于角點和Hu矩不變量的可見光和 紅 外 圖 像 自 動 配 準 方 法 ［J］.紅 外，2011，32 （7）：23－27.］

［8］F rstner W，Gülch.Adaptive and generic corner detection based on the accelerated segment test［G］.LNCS 6312：Proceedings of the European Conference on Computer Vision，2010：183－196.

［9］Jiang Liangxiao.A novel Bayes model：Hidden naive Bayes［J］.Knowledge and Data Engineering，2009 （21）：1361－1371.

［10］Abel G，Nuria L.Improving the assessment of the outcome of nonsynonymous SNVs with a consensus deleteriousness score，condel［J］.American Journal of Human Genetics，2011，88（4）：440－449.