蘭 紅 王秋麗

基于聚類和馬氏距離的SURF昆蟲圖像匹配算法

蘭 紅 王秋麗

(江西理工大學信息工程學院 江西 贛州 341000)

針對SURF(Speeded Up Roubust Features)算法在檢測特征點和進行特征匹配過程中存在的受噪聲點干擾，容易產(chǎn)生誤匹配、匹配效率低等問題，提出一種基于聚類和馬氏距離的改進SURF圖像匹配算法。首先，利用均值聚類算法剔除噪聲，對SURF算法提取的特征點，采用聚類算法進行分類和噪聲點去除，生成新的特征點數(shù)據(jù)集；然后，應用馬氏距離考慮整體相關性的特點，將SURF算法中的歐式距離用馬氏距離替代，提高算法的匹配效率。實驗應用于昆蟲圖像識別和匹配時，改進算法較原SURF算法在匹配效率和準確率上有明顯提高。

圖像匹配 SURF算法 聚類算法 馬氏距離

0 引 言

昆蟲是地球上最繁盛的動物類群,其種類多數(shù)量大，在自然生態(tài)系統(tǒng)和人類社會生活中扮演著重要的角色。昆蟲既可以作為有利資源供人們使用，同時也可以給經(jīng)濟帶來重大的損失。因此研究昆蟲生態(tài)學和昆蟲形態(tài)學具有重大的意義[1]。研究昆蟲生態(tài)學和昆蟲形態(tài)學首先要研究昆蟲的形態(tài)特征以及昆蟲的結構特征，圖像分割[2]技術將所要識別的圖像與背景分割開來是昆蟲圖像識別的第一步，圖像匹配將分割出來的昆蟲圖像作為模板，利用圖像的特征信息對目標昆蟲圖像進行篩選得到所要的昆蟲圖像，是昆蟲圖像識別的又一重要環(huán)節(jié)。因此圖像匹配在昆蟲圖像識別中有重要的作用。

測序技術[3]、多元線性回歸[4]、機器視覺技術[5]、DNA條形碼[6]、EM算法[7]等是常見的昆蟲識別方法。目前，昆蟲圖像匹配的方法一般有兩種，一種是以灰度為基礎的匹配，另一種是以特征為基礎的匹配。以灰度為基礎的匹配主要利用昆蟲圖像的灰度信息，采用統(tǒng)計相關的方法得到昆蟲圖像的相關匹配，雖然匹配率較高但是以灰度為基礎的匹配計算量大，速度慢，并且極易受噪聲和光照變化的影響，因此在大部分場合不宜使用。以特征為基礎的昆蟲圖像匹配通過提取昆蟲圖像的特征如顏色、紋理、形狀、空間關系等，對提取到的特征參數(shù)進行描述，并運用所描述的參數(shù)來進行匹配的一種算法，是目前研究的熱點。常見的特征提取方法有Harris特征[8]、SUSAN特征[9]、M估計法[10]、隨機抽樣最大似然估計MLESAC(Maximum likelihood estimation by sample and consensus)[11]。SURF算法[12]由于對光照、旋轉、尺度變換有良好的魯棒性，在圖像匹配領域得到廣泛應用。但將SURF算法應用于色彩度要求較高的昆蟲圖像識別時容易受噪聲點干擾，匹配精度較低。本文針對SURF算法在昆蟲圖像識別中的不足結合K-means算法和馬氏距離，提出了一種融合K-means均值聚類和馬氏距離的改進SURF圖像匹配算法。實驗證明，本文所提出的算法比傳統(tǒng)的SURF匹配算法效率高、匹配錯誤少、匹配效果好。

1 SURF算法及其在圖像匹配中的不足

1.1 SURF算法簡介

SURF算法由Herbert Bay[12]等人提出，是一種具有快速魯棒特征的匹配描述方法。SURF算法主要分為四個部分：特征點檢測、主方向選取、特征描述符生成、特征點匹配。

1.1.1 特征點檢測

SURF算法要得到關鍵的特征點首先要計算積分圖像，然后構建Hessian矩陣檢測特征點，最后構建圖像金子塔來表述尺度空間。SURF利用Hessian矩陣完成興趣點檢測和尺度變換的操作，并且采用盒子濾波模板[13]作為例子，其中盒子濾波器的估計值分別為Dxx、Dyy和Dxy，由此可得Hessian矩陣的近似行列式可表示為：

Det(Hqpprox)=(DxxDyy-(0.9Dxy)2

(1)

通過不斷增加盒子濾波器的窗口尺寸來構建圖像金字塔，其中圖像金子塔分為若干層，每一層叫做一個octave。圖像金字塔的構建如圖1所示。

圖1 金字塔示意圖

1.1.2 主方向選取

為了使圖像具有旋轉不變性，需要定義主方向，首先以Hessian矩陣定位的特征點為中心，計算以6s為半徑的圓鄰域在x和y方向的Harr小波，其中s為特征點所在的尺度值，小波邊長為4s。取高斯系數(shù)δ=2s為中心檢測特征點，計算小波響應，統(tǒng)計60度扇形內所有的點的水平和垂直Harr小波總和，旋轉360度，將得到的最大的矢量作為該特征點的主方向。

1.1.3 特征描述符生成

獲得特征點主方向后，還要得到特征點的描述算子。選取邊長為20s的正方形區(qū)域，以特征點的主方向作為該區(qū)域的方向，將此區(qū)域劃分為16個子區(qū)域，對每個子區(qū)域統(tǒng)計25個像素的相對于主方向的水平垂直方向的Harr小波特性。記平行于主方向的Haar小波響應為dx，垂直于主方向的Haar小波響應為dy，統(tǒng)計每個子區(qū)域Haar小波響應的總和及絕對值之和。所以每個小區(qū)域就有4個特征量，每個特征點就是16×4=64維的特征向量。

1.1.4 特征點匹配

1.2 SURF算法在圖像匹配中的不足

SURF算法主要用于圖像匹配中，但當圖像含有較多噪聲點時存在不足。

首先SURF算法得到特征點后沒有檢測噪聲點而是直接進行匹配。由于外界噪聲或其他因素的影響，有可能使檢測到的特征點含有噪聲點或其他一些不相關的點，SURF算法在得到含有噪聲點的特征點后直接進行匹配，發(fā)生誤匹配的概率較大。

其次，應用歐式距離進行特征點匹配時受閾值的影響較大，并且匹配效率有待提高。傳統(tǒng)的SURF匹配過程采用kd-trees近似算法，計算兩特征點的歐式距離，通過比較匹配閾值與門限值來確定是否匹配成功。由于圖像所選的特征點通常受紋理、光照、旋轉等多元因素影響，而歐式距離將不同屬性之間的差異同等看待，且容易受變量之間相關性的干擾，從而使特征點的匹配效果變差。另外，應用歐氏距離進行匹配時，門限值的設定對實驗效果有很大的影響。由大量實驗表明，如果門限值選取得較大，雖然匹配點對較多，但是誤匹配對也較多，致使匹配精度較低；如果門限值選取得較小，雖然匹配精度有所提升，但是匹配對較少，不符合性能最優(yōu)條件。圖2和圖3分別是采用不同匹配閾值得到的結果。

圖2 ρ=0.3的匹配效果圖

圖3 ρ=0.85的匹配效果圖

由圖2和圖3可以看出當ρ為0.3時圖像匹配準確率較高但是匹配點對較少；當ρ為0.85時雖然匹配點數(shù)較多但是誤匹配現(xiàn)象比較突出，如圖3中斜線部分為誤匹配對。針對以上兩點問題本文采用K-means聚類算法和馬氏距離對SURF算法進行改進。

2 基于聚類和馬氏距離的SURF昆蟲圖像匹配算法與實現(xiàn)

本文對SURF算法從兩個方面進行改進。首先由SURF算法得到帶有描述符的特征點，根據(jù)匹配圖像的特征點在不同方向的像素特征，應用K-means算法對特征點進行聚類，去除噪聲改變數(shù)據(jù)集；然后，采用馬氏距離代替歐式距離。雖然歐式距離對區(qū)域描述性好，但是沒有考慮特征點的分布信息和幾何信息從而導致匹配精度和效率不理想，馬氏距離將總體的相關性考慮在內，考慮了特征點的分布信息和幾何信息以及對于整幅圖像的縮放與平移變換，具有重大的優(yōu)越性。本文改進算法的總體流程如圖4所示。

圖4 改進SURF算法的流程圖

改進算法包括三個主要功能模塊，圖4中步驟2-8主要利用SURF構建特征點數(shù)據(jù)集，步驟9-13利用聚類算法對噪聲點處理，步驟14-17利用馬氏距離優(yōu)化特征點匹配。每一功能模塊的具體算法描述如下。

2.1 利用SURF構建特征數(shù)據(jù)點集

以圖3(a)和圖3(b)為例說明特征點選取過程。選取圖上任意一點X=(x,y)計算矩形區(qū)域積分圖像的像素和：

(2)

計算該點二階偏導數(shù)卷積值：

(3)

其中σ表示尺度值，g(σ)為高斯濾波函數(shù)公式如下：

(4)

同樣方法計算Lxy(x,σ)與Lyy(x,σ)，然后代入Hessian矩陣公式：

(5)

得到該點的Hessian矩陣，應用式(1)得到該點的Hessian矩陣的判別式Det(Hqpprox)值。

2.2 利用聚類算法對噪聲點處理

聚類算法對噪聲點處理首先對特征點進行聚類，然后剔除噪聲點。

2.2.1 特征點聚類

(6)

分類公式如下:

(7)

根據(jù)公式(8)計算各子集Sl(x,y)(l?{1,2,3,…,K}) 的新簇中心Zl(n+1) ：

(8)

其中Nl是集合Sl(n)中的元素個數(shù)，Zl(n+1)是屬于Sl的X的平均值，當所有的簇滿足式(9)時聚類結束。

Zl(n+1)=Zl(n) l∈Nk

(9)

2.2.2 噪聲點剔除

定義公式

(10)

其中，A表示P×P的正定矩陣，E表示數(shù)據(jù)集中所有誤差的平方和，將圖3(a)和圖3(b)中特征點集應用上式，重復迭代，直到誤差平方和收斂于某一值,將不滿足式(10)的特征點舍棄，使算法對噪聲、背景等有強的魯棒性。

圖像的聚類效果如圖5(b)所示。從圖中可以看出特征點a不滿足式(10)，因此a為噪聲點被剔除。

2.2.3 聚類后的去噪效果圖

圖5 聚類前后的效果圖

經(jīng)檢測聚類后的特征點個數(shù)為83，聚類使特征點數(shù)據(jù)集減小了。通過實驗得到被篩選的的特征點集，并對這些點集進行分析，確定K-means聚類算法改進了特征點集。上述算法解決了SURF算法得到特征點后沒有檢測噪聲點而是直接進行匹配的問題，對于下一步要進行的特征點匹配有很大幫助。

2.3 馬式距離優(yōu)化特征點匹配

傳統(tǒng)的SURF算法利用閾值法進行匹配，匹配閾值由歐式距離確定，閾值公式表示為：

(11)

其中Dnear表示最近鄰歐式距離，Dsub-near表示次近鄰歐式距離，歐氏距離的定義公式為：

(12)

馬氏距離表示數(shù)據(jù)的協(xié)方差距離，它能夠有效地計算兩個未知樣本集的相似度[15,16]。應用馬氏距離進行特征點匹配方法如下。

針對圖3(a)和圖3(b)經(jīng)均值聚類優(yōu)化的特征點數(shù)據(jù)集X和Y，馬氏距離首先計算任意一點樣本均值μ和協(xié)方差矩陣Σ。

(13)

(14)

任意一點Xi=(xi,yi)的馬氏距離定義為：

(15)

其中Σ表示協(xié)方差矩陣，Σ-1是Σ的逆矩陣，μ為樣本的均值。

將式(13)、(14)代入式(15)中，并將式(15)代替SURF算法中式(12)。由式(15)計算得到圖3(a)每個特征點的馬氏距離Adi，及圖3(b)每個特征點的馬氏距離Bdi定義公式：

(16)

式中，α為匹配閾值，若α越接近于1，則說明這兩個特征點的相似度越高。當α在一定閾值范圍內時，表明馬氏距離很接近，特征描述很相似，則匹配成功，否則重新生成特征點。

本文應用馬氏距離代替歐式距離進行特征點的匹配解決了應用歐式距離進行特征點匹配時沒有考慮多方面因素的影響而將不同屬性的因素同等看待，致使匹配魯棒性較差的問題，并且對于應用歐式距離匹配閾值選擇較困難的問題也得到較好的解決。

3 改進算法的核心代碼實現(xiàn)

根據(jù)改進算法的實現(xiàn)流程，軟件編程實現(xiàn)基于聚類和馬氏距離的SURF昆蟲圖像匹配算法的核心代碼如下。

% 數(shù)據(jù)點采集

% 讀取兩個待匹配圖像

I1=im2double(imread(′testf25.jpg′));

I2=im2double(imread(′testf255.jpg′));

% 生成特征點數(shù)據(jù)集

img1=Surf(I1,Options);

img2=Surf(I2,Options);

% 均值聚類的優(yōu)化

% 取其中一個數(shù)據(jù)點集聚類優(yōu)化

[m,n]=size(img1)

img1=double(img1);

%img1為特征點數(shù)據(jù)集

% 選擇特征點聚類中心

%計算各像素灰度與聚類中心的距離

r=abs(img1-c1(i));

g=abs(img1-c2(i));

b=abs(img1-c3(i));

r_g=r-g;

g_b=g-b;

r_b=r-b;

% 尋找最小、中間、最大的聚類中心

n_r=find(r_g<=0&r_b<=0);

n_g=find(r_g>0&g_b<=0);

n_b=find(g_b>0&r_b>0);

% 特征點聚類中心更新

%將所有灰度求和取平均，作為下一個灰度中心

c1(i)=sum(img1(n_r))/length(n_r);

c2(i)=sum(img1(n_g))/length(n_g);% c3(i)=sum(img1(n_b))/length(n_b);%

d1(i)=abs(c1(i)-c1(i-1));

d2(i)=abs(c2(i)-c2(i-1));

d3(i)=abs(c3(i)-c3(i-1));

% c1() c2() c3()為初始聚類中心

% 特征點優(yōu)化

if d1(i)<=0.001&&d2(i)<=0.001&&d3(i)<=0.001

R=c1(i);

G=c2(i);

B=c3(i);

k=i;

break;

end

img1=uint8(img1);

img1(img1

img1(img1>R&img1

img1(img1>G)=255;

toc

% 馬氏距離匹配

cor1=1:length(img1);

cor2=zeros(1,length(img1));

for i=1:length(img1)

% i為點集img中的點

Adi=mahal(img1)

%Adi為I1的馬氏距離

Bdi=mahal(img2)

% Bdi為I2的馬氏距離

AD=0

%AD為I1所有點的馬氏距離

BD=0

%BD為I2所有點的馬氏距離

AD=AD+Adi;

BD=BD+Bdi;

end

alpha=AD/BD

% alpha為匹配閾值

If

alpha1<=alpha<=alpha2

then

c=rand(1,3);

plot[img1(cor1(i)).x img2(cor2(i)).x+size(I1,2)],[img1(cor1(i)).y img2(cor2(i)).y],′-′,′Color′,c)

plot([img1(cor1(i)).ximg2(cor2(i)).x+size(I1,2)],[img1(cor1(i)).y img2(cor2(i)).y],′o′,′Color′,c)

else

return 0

4 改進算法的實驗與仿真

算法在Windows 7系統(tǒng)下，設備為Intel i5-2400 2 GHz 四核處理器、4 GB內存，基于MATLAB 2014a。為了驗證本文改進算法的有效性，對算法進行效果驗證，選取1張動物圖片和3張昆蟲圖片，圖片來源于課題組的科研數(shù)據(jù)庫。這4張圖片的大小分別為48、841、9810、294 KB，并且圖片的水平分辨率和垂直分辨率均為96 dpi。經(jīng)過大量實驗驗證，設置初始參數(shù)匹配閾值0.8≤α≤1.2，SURF算法中金字塔各層數(shù)據(jù)如下：

Oct1: 9, 15, 21, 27 Oct2: 15, 27, 39, 51

Oct3: 27, 51, 75, 99 Oct4: 51, 99, 147,195

Oct5: 99, 195,291,387

4.1 圖像匹配實驗

再次對圖3中的圖像進行匹配，圖6是傳統(tǒng)的SURF算法和本文算法的效果圖。

圖6 圖像匹配對比

表1記錄了傳統(tǒng)的SURF匹配算法和本文算法匹配實驗30次所用的平均時間和平均特征點數(shù)。

表1 匹配性能比較

根據(jù)圖6和表1的對比可以看出，本文在配準率方面有明顯提高，原因是本文應用聚類算法去除噪聲點，然后又應用馬氏距離進行精匹配。并且經(jīng)試驗驗證，當0.8≤α≤1.2時，改進后的算法幾乎不受匹配閾值α的影響。由于應用聚類時要遍歷所有特征點因此匹配時間較原來稍長，但是可以滿足一般匹配需要。

4.2 將本文算法應用于昆蟲圖像

選取天堂鳳碟成蟲、華北大黑腮金龜成蟲和蜘蛛成蟲為例，為了體現(xiàn)算法的有效性，選取不同背景下昆蟲圖片進行對比。同樣采用傳統(tǒng)的SURF算法和本文算法進行實驗比較，實驗環(huán)境和參數(shù)設置與上述實驗保持一致，兩種算法對昆蟲圖像的匹配效果如圖7-圖9所示。

圖7 天堂鳳碟成蟲圖像的匹配

圖8 華北大黑腮金龜成蟲圖像的匹配

圖9 蜘蛛成蟲圖像的匹配

從圖7-圖9可以看出傳統(tǒng)SURF算法誤匹配較多，如圖中斜線部分，本文算法相比傳統(tǒng)的SURF算法匹配效果明顯提升。圖中增加了帶背景噪聲的圖像匹配，改進算法對有背景噪聲的圖像匹配仍然具有較好的效果，幾乎沒有受到背景噪聲干擾。表2為傳統(tǒng)的SURF匹配算法和本文算法對昆蟲圖像特征匹配的性能比較。從表中數(shù)據(jù)可以看出，改進算法的匹配成功率達到百分之九十以上，相比傳統(tǒng)的SURF算法有較大的提升。對于噪聲點較多的圖像進行匹配，本文算法仍然有較好的匹配效果。

表2 匹配性能比較

5 結 語

針對傳統(tǒng)的SURF算法由于噪聲點及其他外界條件的影響致使誤配率低的問題，本文提出的基于均值聚類和馬氏距離的SURF算法改進了傳統(tǒng)SURF算法匹配效率低匹配精度低的不足。

在圖像信息檢索中，應用本文算法可以很好地實現(xiàn)特征匹配，從而提高信息檢索的效率。應用于昆蟲圖像識別領域，改進算法較原SURF算法具有更高的匹配效率，可以有效識別不同環(huán)境下的昆蟲極其樣本。對果樹害蟲防治和農(nóng)業(yè)生產(chǎn)具有重要意義。

由于本文算法聚類時要遍歷特征點，因此計算時間稍長，因此，在以后的改進工作中有必要考慮縮短匹配時間。

[1] 孫荊濤,楊現(xiàn)明,葛成,等.微衛(wèi)星分子標記在昆蟲分子生態(tài)學研究上的應用[J].南京農(nóng)業(yè)大學學報,2012,35(5):103-112.

[2] 劉曉靜,耿國華,周明全,等.一種基于復雜背景下的昆蟲彩色圖像分割方法[J].計算機應用與軟件,2008,25(11):37-38,88.

[3] 岳桂東,高強,羅龍海,等.高通量測序技術在動植物研究領域中的應用[J].中國科學,2012,42(2):107-124.

[4] 蘭紅,王璇.基于多元線性回歸的昆蟲圖像分割方法[J].計算機應用與軟件,2013,30(7):193-196,208.

[5] 張志強,牛智有,趙思明.基于機器視覺技術的淡水魚品種識別[J].農(nóng)業(yè)工程學報,2011,27(11):388-392.

[6] 溫娟,陳睿,姜立云,等.基于DNA條形碼對北京地區(qū)薔薇科花卉上蚜蟲的快速鑒定[J].應用昆蟲學報,2013,50(1):29-40.

[7] 程小梅,耿國華,周明全,等.基于多特征的EM算法在昆蟲圖像分割中的應用[J].計算機應用與軟件,2009,26(2):20-22,82.

[8] Harris C,Stephens M.A combined corner and edge detector[C]//Alvey vision conference,1988,15:50.

[9] Smith S M,Brady J M.SUSAN-a new approach to low level image processing[J].Internation Journal of Computer Vision,1997,23(1):43-78.

[10] Chen J H,Chen C S,Chen Y S.Fast algorithm for robust template matching with M-estimators[J].IEEE Transactions on Signal Processing,2003,51(1):230-243.

[11] Torr P H S,Zisserman A.MLESAC:a new robust estimator with application to estimating image geometry[J].Computer Vision and Image Understanding,2000,78(1):138-156.

[12] Bay H,Ess A,Tuytelaars T,et al.Speeded-up robust features (SURF)[J].Computer vision and image understanding,2008,110(3):346-359.

[13] 孫浩,王程,王潤生.局部不變特征綜述[J].中國圖象圖形學報,2011,16(2):141-151.

[14] Beis J S,Lowe D G.Shape indexing using approximate nearest-neighbour search in high-dimensional spaces[C]//Computer Vision and Pattern Recognition,1997.Proceedings.,1997 IEEE Computer Society Conference on.IEEE,1997:1000-1006.

[15] 汪洋,肖先勇,劉陽,等.短時電能質量復合擾動分類特征選取與馬氏距離分類法[J].電網(wǎng)技術,2014,38(4):1064-1069.

[16] 王晉,李夕兵,楊金林.深部硬巖巖爆評判的加權馬氏距離判別法[J].采礦與安全工程學報,2011,28(3):395-400.

SURF ALGORITHM OF INSECTS IMAGE MATCHING BASED ON CLUSTERING AND MAHALANOBIS DISTANCE

Lan Hong Wang Qiuli

(SchoolofInformationEngineering,JiangxiUniversityofScienceandTechnology,Ganzhou341000,Jiangxi,China)

In the process of detecting feature points and carrying out feature matching, Speeded Up Robust Features (SURF) algorithm has the problems of interfering by noise points, being prone to mismatching and low matching efficiency, etc. To resolve these problems, we proposed a cluster and Mahalanobis distance-based improved SURF image matching algorithm. First, it uses mean clustering algorithm to eliminate noise, for the feature points extracted by SURF algorithm, it uses clustering algorithm to make classification and to remove noise points, and generates new feature point dataset. Then, it applies Mahalanobis distance to consider the characteristics of overall correlation, and replaces the Euclidean distance in SURF algorithm with Mahalanobis distance to improve matching efficiency of the algorithm. When applying the method to insects image recognition and matching in experiment, the improved algorithm has obvious improvement than original SURF algorithm in matching efficiency and accuracy.

Image matching SURF algorithm Clustering algorithm Mahalanobis distance

2015-01-15。江西教育廳重點項目(贛教技字[12770]號)；江西省教育廳科技項目(GJJ14430)。蘭紅，教授，主研領域：圖像處理，模識識別。王秋麗，碩士生。

TP391

A

10.3969/j.issn.1000-386x.2016.04.047