基于KNN有向复杂网络的图像轮廓识别

李咏豪

摘  要： 图像的目标识别是模式识别的研究领域之一，现已广泛应用于视频监控、交通运输和动作识别等。受图像采集过程中光照变化、形状和噪声等因素影响，基于区域或轮廓的方法往往会出现若干错误。图像的复杂网络特征具有较强的稳定与抗噪能力，因此，提出一种图像的有向复杂网络表示模型，利用K近邻（KNN）确定有向复杂网络的演化序列，并利用复杂网络的度平均与熵等参数完成图像的轮廓识别。图像检索实验结果表明，该方法在查全率与查准率上均获得较好结果。

关键词： 复杂网络; 图像识别; 图像轮廓; K最近邻; 熵

中图分类号：TP274          文献标志码：A     文章编号：1006-8228（2019）06-31-03

Abstract： The object recognition in image is one of the research fields of pattern recognition， which is widely used in video surveillance， transportation and motion recognition. There are some errors in the region or contour based methods due to the influence of illumination change， shape and noise during the image acquisition. The characteristics of complex network for image have the abilities of strong stability and anti-noise. In this paper， a directed complex network representation model of image is proposed. The evolutionary sequence of directed complex network has been determined with K-nearest neighbor （KNN）， and the contour recognition of image is completed via the parameters of average degree and entropy of complex network. The results of image retrieval experiment show that the proposed method obtains the better results in terms of recall and precision.

Key words： complex network; image recognition; image contour; K-nearest neighbor; entropy

0 引言

图像的目标识别是模式识别的研究领域之一，已广泛应用于视频监控、交通运输、动作识别等场合。按提取的目标对象特征，可将目标识别方法分为基于模型的、基于区域的以及基于轮廓的方法。基于区域的方法，一般是利用颜色和纹理特征来表示区域，该方法可以抗区域大小、平移与旋转等变化，但由于这些特征不包括图像像素间空间位置特性，因此不能较好地进行图像识别。另外，对于基于轮廓的方法，由于受图像采集过程中光照变化、形状和噪声等因素影响，一般不能保证形状轮廓的完整性，所以，利用该方法进行目标识别也会出现若干错误。复杂网络是以图论为基础来建立模型，着重关注节点之间的相对位置，当网络图发生旋转、平移等对其拓扑特性影响较小。图像由多个像素构成，图像中的像素与复杂网络中的节点可以建立一一对应关系，由此，复杂网络中的节点间的边与图像中像素间的关系也存在一一对应关系。因此，可以将图像看成一复杂网络，通过分析网络性质来选取部分参数来记录图像形状，再对这些网络参数作进一步组合，最终识别图像中目标。因此，本文采用复杂网络来描述目标边界来进行形状识别，从而保证形状识别算法的稳定性。

1 KNN演化模型

基于复杂网络的图像形状轮廓识别方法一般可以分为三个步骤：①复杂网络建模;②识别参数提取;③图像识别分类。对于第一步复杂网络建模，以往的动态演化模型，包括最小生成树演化，阈值演化等，大多利用无向网络进行演化。由于有向网络中包含的结构信息更丰富，因此，本文提出一种基于KNN的演化模型，经演化后得到有向子网络。假定初始网络用G0表示，则演化过程如下：

其中，KNN（i）表示节点i的K近邻，k=1，2，…，|v|-1，KNN（i）。即，当节点j为节点i的邻点，则节点i与j间存在有向边。这样，对不同k，可以得到演化有向子网络序列。

2 图像描述与特征提取

下面，利用Harris方法提取圖像中的关键点[1]，并构建初始网络;接着利用网络拓扑特征实现图像识别。

2.1 图像的复杂网络表示

我们可以用图G（V，E）表示图像I，其中，V和E分别表示图中顶点的集合以及边的集合。Harris方法可以提出图像中的角点，因此，本文首先利用该方法提取图像中的角点，即n个关键点。再以这n个关键点作为网络的顶点，来建立网络模型Gn=（Vn，En），其中，任意两个节点i与j间的连接边的权值用两者的欧氏距离d（i，j）表示，即：

上述网络模型Gn可以用一个n×n的权值矩阵来表示，并将权值归一化：

2.2 提取特征向量

利用KNN对上述网络进行动态演化，从而得到有向子网络序列，并将其串联构成一特征向量，即：

其中，分别表示第i个有向子网络的度均值、熵值和能量。这里，度均值是将有向子网络中的各节点的度相加再计算其平均值。熵和能量的计算公式如下：

3 算法流程

算法流程如图1所示。算法具体步骤如下：首先，利用Harris角点检测法提取图像中的关键点，并构建初始网络模型;接着，利用KNN实现复杂网络的动态演化，从而得到有向子网络序列;然后，利用有向子网络中的度平均、熵等特征构成特征向量;最后，利用特征向量完成图像轮廓的识别。

4 实验结果

为验证本文提出算法的性能，我们在Columbia Object Image Library-100（COIL-100）[1]图像库上进行了图像检索实验。该图像库共包括100种类别的物体，每个类别中各包含72幅从不同视角拍摄的图像，总共有7200幅。本文共选取8种物体，每种物体包括15幅图像，总共组成120幅图像作检索，并与基于EWT（Edges Weights Threshold）[3]和基于GED（Graph Edit Distance）[4]的图像描述方法进行对比。实验中，每幅图像共提取45个关键点。本文利用查全率与查准率来说明检索结果[5]，当查全—查准率曲線与坐标轴围成的面积越大，则说明检索性能越好[6]。

本文选用查全率和查准率来表示图像的检索性能。查全率是指，检索出的相关记录与全部相关记录之间的比值，查准率是指检索出的相关记录与检索出的全部记录的比值，从查全-查准率曲线的分布我们可以判断图像检索算法的性能。当查全-查准率曲线与两条坐标轴之间所围成的面积越大，则检索性能越好[7]。图2显示了三种方法的实验结果。从图2可以发现，本文提出的方法优于EWT和GED方法。检索结果如图3所示，其中第一列表示待检索图像，其余8列表示检索结果。从图3可知，大部分类别的图像得到较好的检索结果，仅有第七类的图像出现了二幅错误检索结果。

5 结束语

本文提出了基于KNN的有向复杂网络模型来进行图像形状的识别，并在COIL-100图像库上选取8种物体，共120幅图像进行了检索实验。实验结果，相比于基于EWT和基于GED方法，本文提出的方法查全率与查准率均高于其他方法。未来工作将着重解决如何在复杂网络中保留更多的图像特征，以进一步提高识别准确率。

参考文献（References）：

[1] Backes A R， Casanova D，Bruno O M. A complexnetwork-based approach for boundary shape analysis[J].Pattern Recognition，2009.42（1）： 54-67

[2] Gao X B， Xiao B， Tao D C， et al. Image categorization： Graph edit distance edge direction histogram[J]. Pattern Recognition，2008.41（10）： 3179-3191

[3] Neuhaus M， Bunke H. A probabilistic approach to learningcosts for graph edit distance [C]// Proceedings of the 17th International Conference on Pattern Recognition，2004：389-393

[4] Xiao B， Li J， Gao X B. An HMM-based cost function freealgorithm for graph edit distance [C]// Proceedings of International Conference on Visual Information Engineering，2008：286-291

[5] Luo B， Wilson R C， Hancock E R. Spectral embedding of graphs[J].Pattern Recognition，2003.36（10）：2213-2230

[6] Tang J， Jiang B， Chang C， et al. Graph structure analysisbased on complexnetwork[J]. Digital Signal Processing，2012.22（5）：713-725

[7] Bai X ，Wang B， Wang X G， et al. Co-transduction forshape retrieval[J].IEEE Transactions on Image Processing，2012.21（5）： 2747-2757

[7] Bhowmik M K，Shil S， Saha P. Feature Points Extraction of Thermal Face using Harris Interest Point Detection[J].Procedia Technology，2013.10：724-730

[8] Shu X' Wu X J. A novel contour descriptor for 2D shape matching and itsapplication to image retrieval[J]. Image and Vision Computing，2011.29（4）：286-294