常旭劍，韓 燮，熊風(fēng)光

（中北大學(xué) 計(jì)算機(jī)與控制工程學(xué)院，山西 太原030051）

0 引 言

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

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

1 相關(guān)工作

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

1.1 特征檢測(cè)

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

1.2 特征描述

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

1.3 特征匹配

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

2 特征點(diǎn)檢測(cè)與描述

2.1 FAST特征檢測(cè)算法

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

FAST 特征檢測(cè)算法是基于角點(diǎn)的定義。FAST 算法主要包含3個(gè)步驟：

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

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

FAST 算法特征點(diǎn)檢測(cè)算法如圖1所示。

圖1 FAST 算法特征點(diǎn)檢測(cè)算法

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

（3）最后，通過ID3決策樹算法訓(xùn)練特征點(diǎn)，使用計(jì)算角點(diǎn)響應(yīng)函數(shù)。定義一個(gè)響應(yīng)函數(shù)V 如下

可以用常規(guī)極大值抑制法對(duì)非特征點(diǎn)進(jìn)行排除。

2.2 SIFT特征描述算法

2.2.1 特征點(diǎn)的方向匹配

檢測(cè)到的局部特征，描述的重點(diǎn)是局部特征的魯棒性及可區(qū)分性。

通過FAST 特征檢測(cè)算法，已經(jīng)找到了待處理圖像的特征點(diǎn)位置，下一步通過SIFT 算法所提供的特征描述算法來對(duì)特征點(diǎn)進(jìn)行描述，為下一步的匹配做準(zhǔn)備。

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

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

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

圖2 特征點(diǎn)產(chǎn)生直方圖

2.2.2 特征點(diǎn)的特征描述

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

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

特征點(diǎn)描述子在4×4的窗口內(nèi)計(jì)算8個(gè)方向的梯度學(xué)習(xí)，那么就是4×4×8＝128維度的向量表征。

3 特征點(diǎn)臨近匹配

3.1 特征點(diǎn)匹配

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

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

3.2 基于SNR 驗(yàn)證的特征點(diǎn)匹配

3.2.1 基本思路

如圖3所示，每個(gè)特征點(diǎn)在二維圖像中都有一組對(duì)應(yīng)坐標(biāo)，設(shè)與圖像（a）中的特征點(diǎn)是 （xai，yai）對(duì)應(yīng)的圖像（b）的特征點(diǎn)為（xbi，ybi），那么對(duì)應(yīng)的Δxi＝｜xai－xbi｜及Δbi＝｜yai－ybi｜應(yīng)該服從正態(tài)分布。

如圖4為所對(duì)應(yīng)的匹配的高斯分布，首先確定峰值，好的匹配可以找到一個(gè)峰值，如圖4 （a）中的P1，P2不是一個(gè)好的峰值，因?yàn)橛写胃叻逯蹈蓴_。然后確定對(duì)應(yīng)面積，圖4 （b）對(duì)應(yīng)面積越大越好 （實(shí)框好于虛框）。

3.2.2 算法實(shí)現(xiàn)

最后，確定信噪比，值越高越好。如圖5 所示，目標(biāo)物體逐次和不同場(chǎng)景圖片比對(duì)，獲得不同信噪比SNRn。

圖3 特征點(diǎn)匹配

圖4 特征點(diǎn)在x、y軸上的差值直方圖

圖5 目標(biāo)物體與不同場(chǎng)景匹配信噪比結(jié)果

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

4 實(shí)驗(yàn)結(jié)果與分析

4.1 實(shí)驗(yàn)結(jié)果

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

圖6 目標(biāo)檢測(cè)物及干擾物體

把目標(biāo)物體a （書）置于高度雜亂的環(huán)境中。運(yùn)行FAST 檢測(cè)算法，提取出376個(gè)FAST 特征點(diǎn)，利用SIFT描述算法描述FAST 檢測(cè)到的特征點(diǎn)，如圖7所示。

FAST特征算法提取在本實(shí)驗(yàn)環(huán)境下（8－cores，2.4GHz intel i7，16Gb RAM）提取376個(gè)特征點(diǎn)用時(shí)8ms，SIFT描述符用時(shí)183ms。本文中限制FAST點(diǎn)在30像素（為減少獲得的總特征點(diǎn)的點(diǎn)數(shù)，增強(qiáng)系統(tǒng)的魯棒性）。

圖7 FAST 特征點(diǎn)提取

這些特征關(guān)鍵點(diǎn)都嘗試匹配數(shù)據(jù)庫中每個(gè)物體／子物體關(guān)鍵點(diǎn)。匹配所有數(shù)據(jù)庫中物體過程耗時(shí)57ms。直方圖在x軸以及y軸上位移如圖8所示標(biāo)出了匹配的質(zhì)量：信噪比（SNR），計(jì)算了每一個(gè)匹配的信噪比。

最后匹配的概率通過使用樸素貝葉斯分類的方法，把數(shù)據(jù)庫中每個(gè)物體進(jìn)行計(jì)算。先對(duì)所檢測(cè)物體所在類別進(jìn)行初步分類，然后在子類內(nèi)進(jìn)行檢測(cè)。實(shí)驗(yàn)結(jié)果如圖9所示。

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

圖9 數(shù)據(jù)庫中物體與場(chǎng)景中物體匹配結(jié)果

4.2 實(shí)驗(yàn)結(jié)果評(píng)估

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

5 結(jié)束語

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

表1 常見特征點(diǎn)探測(cè)描述算法間不同組合耗時(shí)對(duì)比

圖10 常見特征點(diǎn)探測(cè)描述算法間不同組合對(duì)比效用比

［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）.［徐賢鋒.一種改進(jìn)的多尺度Harris特征點(diǎn)檢測(cè)方法 ［J］.計(jì)算機(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）.［竇建方.基于角點(diǎn)和Hu矩不變量的可見光和 紅 外 圖 像 自 動(dòng) 配 準(zhǔn) 方 法 ［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.