基于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