基于聚类和马氏距离的SURF昆虫图像匹配算法

兰 红 王秋丽

基于聚类和马氏距离的SURF昆虫图像匹配算法

兰 红 王秋丽

(江西理工大学信息工程学院 江西 赣州 341000)

针对SURF(Speeded Up Roubust Features)算法在检测特征点和进行特征匹配过程中存在的受噪声点干扰，容易产生误匹配、匹配效率低等问题，提出一种基于聚类和马氏距离的改进SURF图像匹配算法。首先，利用均值聚类算法剔除噪声，对SURF算法提取的特征点，采用聚类算法进行分类和噪声点去除，生成新的特征点数据集；然后，应用马氏距离考虑整体相关性的特点，将SURF算法中的欧式距离用马氏距离替代，提高算法的匹配效率。实验应用于昆虫图像识别和匹配时，改进算法较原SURF算法在匹配效率和准确率上有明显提高。

图像匹配 SURF算法 聚类算法 马氏距离

0 引 言

昆虫是地球上最繁盛的动物类群,其种类多数量大，在自然生态系统和人类社会生活中扮演着重要的角色。昆虫既可以作为有利资源供人们使用，同时也可以给经济带来重大的损失。因此研究昆虫生态学和昆虫形态学具有重大的意义[1]。研究昆虫生态学和昆虫形态学首先要研究昆虫的形态特征以及昆虫的结构特征，图像分割[2]技术将所要识别的图像与背景分割开来是昆虫图像识别的第一步，图像匹配将分割出来的昆虫图像作为模板，利用图像的特征信息对目标昆虫图像进行筛选得到所要的昆虫图像，是昆虫图像识别的又一重要环节。因此图像匹配在昆虫图像识别中有重要的作用。

测序技术[3]、多元线性回归[4]、机器视觉技术[5]、DNA条形码[6]、EM算法[7]等是常见的昆虫识别方法。目前，昆虫图像匹配的方法一般有两种，一种是以灰度为基础的匹配，另一种是以特征为基础的匹配。以灰度为基础的匹配主要利用昆虫图像的灰度信息，采用统计相关的方法得到昆虫图像的相关匹配，虽然匹配率较高但是以灰度为基础的匹配计算量大，速度慢，并且极易受噪声和光照变化的影响，因此在大部分场合不宜使用。以特征为基础的昆虫图像匹配通过提取昆虫图像的特征如颜色、纹理、形状、空间关系等，对提取到的特征参数进行描述，并运用所描述的参数来进行匹配的一种算法，是目前研究的热点。常见的特征提取方法有Harris特征[8]、SUSAN特征[9]、M估计法[10]、随机抽样最大似然估计MLESAC(Maximum likelihood estimation by sample and consensus)[11]。SURF算法[12]由于对光照、旋转、尺度变换有良好的鲁棒性，在图像匹配领域得到广泛应用。但将SURF算法应用于色彩度要求较高的昆虫图像识别时容易受噪声点干扰，匹配精度较低。本文针对SURF算法在昆虫图像识别中的不足结合K-means算法和马氏距离，提出了一种融合K-means均值聚类和马氏距离的改进SURF图像匹配算法。实验证明，本文所提出的算法比传统的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。取高斯系数δ=2s为中心检测特征点，计算小波响应，统计60度扇形内所有的点的水平和垂直Harr小波总和，旋转360度，将得到的最大的矢量作为该特征点的主方向。

1.1.3 特征描述符生成

获得特征点主方向后，还要得到特征点的描述算子。选取边长为20s的正方形区域，以特征点的主方向作为该区域的方向，将此区域划分为16个子区域，对每个子区域统计25个像素的相对于主方向的水平垂直方向的Harr小波特性。记平行于主方向的Haar小波响应为dx，垂直于主方向的Haar小波响应为dy，统计每个子区域Haar小波响应的总和及绝对值之和。所以每个小区域就有4个特征量，每个特征点就是16×4=64维的特征向量。

1.1.4 特征点匹配

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

SURF算法主要用于图像匹配中，但当图像含有较多噪声点时存在不足。

首先SURF算法得到特征点后没有检测噪声点而是直接进行匹配。由于外界噪声或其他因素的影响，有可能使检测到的特征点含有噪声点或其他一些不相关的点，SURF算法在得到含有噪声点的特征点后直接进行匹配，发生误匹配的概率较大。

其次，应用欧式距离进行特征点匹配时受阈值的影响较大，并且匹配效率有待提高。传统的SURF匹配过程采用kd-trees近似算法，计算两特征点的欧式距离，通过比较匹配阈值与门限值来确定是否匹配成功。由于图像所选的特征点通常受纹理、光照、旋转等多元因素影响，而欧式距离将不同属性之间的差异同等看待，且容易受变量之间相关性的干扰，从而使特征点的匹配效果变差。另外，应用欧氏距离进行匹配时，门限值的设定对实验效果有很大的影响。由大量实验表明，如果门限值选取得较大，虽然匹配点对较多，但是误匹配对也较多，致使匹配精度较低；如果门限值选取得较小，虽然匹配精度有所提升，但是匹配对较少，不符合性能最优条件。图2和图3分别是采用不同匹配阈值得到的结果。

图2 ρ=0.3的匹配效果图

图3 ρ=0.85的匹配效果图

由图2和图3可以看出当ρ为0.3时图像匹配准确率较高但是匹配点对较少；当ρ为0.85时虽然匹配点数较多但是误匹配现象比较突出，如图3中斜线部分为误匹配对。针对以上两点问题本文采用K-means聚类算法和马氏距离对SURF算法进行改进。

2 基于聚类和马氏距离的SURF昆虫图像匹配算法与实现

本文对SURF算法从两个方面进行改进。首先由SURF算法得到带有描述符的特征点，根据匹配图像的特征点在不同方向的像素特征，应用K-means算法对特征点进行聚类，去除噪声改变数据集；然后，采用马氏距离代替欧式距离。虽然欧式距离对区域描述性好，但是没有考虑特征点的分布信息和几何信息从而导致匹配精度和效率不理想，马氏距离将总体的相关性考虑在内，考虑了特征点的分布信息和几何信息以及对于整幅图像的缩放与平移变换，具有重大的优越性。本文改进算法的总体流程如图4所示。

图4 改进SURF算法的流程图

改进算法包括三个主要功能模块，图4中步骤2-8主要利用SURF构建特征点数据集，步骤9-13利用聚类算法对噪声点处理，步骤14-17利用马氏距离优化特征点匹配。每一功能模块的具体算法描述如下。

2.1 利用SURF构建特征数据点集

以图3(a)和图3(b)为例说明特征点选取过程。选取图上任意一点X=(x,y)计算矩形区域积分图像的像素和：

(2)

计算该点二阶偏导数卷积值：

(3)

其中σ表示尺度值，g(σ)为高斯滤波函数公式如下：

(4)

同样方法计算Lxy(x,σ)与Lyy(x,σ)，然后代入Hessian矩阵公式：

(5)

得到该点的Hessian矩阵，应用式(1)得到该点的Hessian矩阵的判别式Det(Hqpprox)值。

2.2 利用聚类算法对噪声点处理

聚类算法对噪声点处理首先对特征点进行聚类，然后剔除噪声点。

2.2.1 特征点聚类

(6)

分类公式如下:

(7)

根据公式(8)计算各子集Sl(x,y)(l≅{1,2,3,…,K}) 的新簇中心Zl(n+1) ：

(8)

其中Nl是集合Sl(n)中的元素个数，Zl(n+1)是属于Sl的X的平均值，当所有的簇满足式(9)时聚类结束。

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

(9)

2.2.2 噪声点剔除

定义公式

(10)

其中，A表示P×P的正定矩阵，E表示数据集中所有误差的平方和，将图3(a)和图3(b)中特征点集应用上式，重复迭代，直到误差平方和收敛于某一值,将不满足式(10)的特征点舍弃，使算法对噪声、背景等有强的鲁棒性。

图像的聚类效果如图5(b)所示。从图中可以看出特征点a不满足式(10)，因此a为噪声点被剔除。

2.2.3 聚类后的去噪效果图

图5 聚类前后的效果图

经检测聚类后的特征点个数为83，聚类使特征点数据集减小了。通过实验得到被筛选的的特征点集，并对这些点集进行分析，确定K-means聚类算法改进了特征点集。上述算法解决了SURF算法得到特征点后没有检测噪声点而是直接进行匹配的问题，对于下一步要进行的特征点匹配有很大帮助。

2.3 马式距离优化特征点匹配

传统的SURF算法利用阈值法进行匹配，匹配阈值由欧式距离确定，阈值公式表示为：

(11)

其中Dnear表示最近邻欧式距离，Dsub-near表示次近邻欧式距离，欧氏距离的定义公式为：

(12)

马氏距离表示数据的协方差距离，它能够有效地计算两个未知样本集的相似度[15,16]。应用马氏距离进行特征点匹配方法如下。

针对图3(a)和图3(b)经均值聚类优化的特征点数据集X和Y，马氏距离首先计算任意一点样本均值μ和协方差矩阵Σ。

(13)

(14)

任意一点Xi=(xi,yi)的马氏距离定义为：

(15)

其中Σ表示协方差矩阵，Σ-1是Σ的逆矩阵，μ为样本的均值。

将式(13)、(14)代入式(15)中，并将式(15)代替SURF算法中式(12)。由式(15)计算得到图3(a)每个特征点的马氏距离Adi，及图3(b)每个特征点的马氏距离Bdi定义公式：

(16)

式中，α为匹配阈值，若α越接近于1，则说明这两个特征点的相似度越高。当α在一定阈值范围内时，表明马氏距离很接近，特征描述很相似，则匹配成功，否则重新生成特征点。

本文应用马氏距离代替欧式距离进行特征点的匹配解决了应用欧式距离进行特征点匹配时没有考虑多方面因素的影响而将不同属性的因素同等看待，致使匹配鲁棒性较差的问题，并且对于应用欧式距离匹配阈值选择较困难的问题也得到较好的解决。

3 改进算法的核心代码实现

根据改进算法的实现流程，软件编程实现基于聚类和马氏距离的SURF昆虫图像匹配算法的核心代码如下。

% 数据点采集

% 读取两个待匹配图像

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

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

% 生成特征点数据集

img1=Surf(I1,Options);

img2=Surf(I2,Options);

% 均值聚类的优化

% 取其中一个数据点集聚类优化

[m,n]=size(img1)

img1=double(img1);

%img1为特征点数据集

% 选择特征点聚类中心

%计算各像素灰度与聚类中心的距离

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()为初始聚类中心

% 特征点优化

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系统下，设备为Intel i5-2400 2 GHz 四核处理器、4 GB内存，基于MATLAB 2014a。为了验证本文改进算法的有效性，对算法进行效果验证，选取1张动物图片和3张昆虫图片，图片来源于课题组的科研数据库。这4张图片的大小分别为48、841、9810、294 KB，并且图片的水平分辨率和垂直分辨率均为96 dpi。经过大量实验验证，设置初始参数匹配阈值0.8≤α≤1.2，SURF算法中金字塔各层数据如下：

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是传统的SURF算法和本文算法的效果图。

图6 图像匹配对比

表1记录了传统的SURF匹配算法和本文算法匹配实验30次所用的平均时间和平均特征点数。

表1 匹配性能比较

根据图6和表1的对比可以看出，本文在配准率方面有明显提高，原因是本文应用聚类算法去除噪声点，然后又应用马氏距离进行精匹配。并且经试验验证，当0.8≤α≤1.2时，改进后的算法几乎不受匹配阈值α的影响。由于应用聚类时要遍历所有特征点因此匹配时间较原来稍长，但是可以满足一般匹配需要。

4.2 将本文算法应用于昆虫图像

选取天堂凤碟成虫、华北大黑腮金龟成虫和蜘蛛成虫为例，为了体现算法的有效性，选取不同背景下昆虫图片进行对比。同样采用传统的SURF算法和本文算法进行实验比较，实验环境和参数设置与上述实验保持一致，两种算法对昆虫图像的匹配效果如图7-图9所示。

图7 天堂凤碟成虫图像的匹配

图8 华北大黑腮金龟成虫图像的匹配

图9 蜘蛛成虫图像的匹配

从图7-图9可以看出传统SURF算法误匹配较多，如图中斜线部分，本文算法相比传统的SURF算法匹配效果明显提升。图中增加了带背景噪声的图像匹配，改进算法对有背景噪声的图像匹配仍然具有较好的效果，几乎没有受到背景噪声干扰。表2为传统的SURF匹配算法和本文算法对昆虫图像特征匹配的性能比较。从表中数据可以看出，改进算法的匹配成功率达到百分之九十以上，相比传统的SURF算法有较大的提升。对于噪声点较多的图像进行匹配，本文算法仍然有较好的匹配效果。

表2 匹配性能比较

5 结 语

针对传统的SURF算法由于噪声点及其他外界条件的影响致使误配率低的问题，本文提出的基于均值聚类和马氏距离的SURF算法改进了传统SURF算法匹配效率低匹配精度低的不足。

在图像信息检索中，应用本文算法可以很好地实现特征匹配，从而提高信息检索的效率。应用于昆虫图像识别领域，改进算法较原SURF算法具有更高的匹配效率，可以有效识别不同环境下的昆虫极其样本。对果树害虫防治和农业生产具有重要意义。

由于本文算法聚类时要遍历特征点，因此计算时间稍长，因此，在以后的改进工作中有必要考虑缩短匹配时间。

[1] 孙荆涛,杨现明,葛成,等.微卫星分子标记在昆虫分子生态学研究上的应用[J].南京农业大学学报,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].农业工程学报,2011,27(11):388-392.

[6] 温娟,陈睿,姜立云,等.基于DNA条形码对北京地区蔷薇科花卉上蚜虫的快速鉴定[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].电网技术,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