李詠豪

摘? 要： 圖像的目標識別是模式識別的研究領(lǐng)域之一，現(xiàn)已廣泛應用于視頻監(jiān)控、交通運輸和動作識別等。受圖像采集過程中光照變化、形狀和噪聲等因素影響，基于區(qū)域或輪廓的方法往往會出現(xiàn)若干錯誤。圖像的復雜網(wǎng)絡特征具有較強的穩(wěn)定與抗噪能力，因此，提出一種圖像的有向復雜網(wǎng)絡表示模型，利用K近鄰（KNN）確定有向復雜網(wǎng)絡的演化序列，并利用復雜網(wǎng)絡的度平均與熵等參數(shù)完成圖像的輪廓識別。圖像檢索實驗結(jié)果表明，該方法在查全率與查準率上均獲得較好結(jié)果。

關(guān)鍵詞： 復雜網(wǎng)絡; 圖像識別; 圖像輪廓; 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 引言

圖像的目標識別是模式識別的研究領(lǐng)域之一，已廣泛應用于視頻監(jiān)控、交通運輸、動作識別等場合。按提取的目標對象特征，可將目標識別方法分為基于模型的、基于區(qū)域的以及基于輪廓的方法?；趨^(qū)域的方法，一般是利用顏色和紋理特征來表示區(qū)域，該方法可以抗區(qū)域大小、平移與旋轉(zhuǎn)等變化，但由于這些特征不包括圖像像素間空間位置特性，因此不能較好地進行圖像識別。另外，對于基于輪廓的方法，由于受圖像采集過程中光照變化、形狀和噪聲等因素影響，一般不能保證形狀輪廓的完整性，所以，利用該方法進行目標識別也會出現(xiàn)若干錯誤。復雜網(wǎng)絡是以圖論為基礎來建立模型，著重關(guān)注節(jié)點之間的相對位置，當網(wǎng)絡圖發(fā)生旋轉(zhuǎn)、平移等對其拓撲特性影響較小。圖像由多個像素構(gòu)成，圖像中的像素與復雜網(wǎng)絡中的節(jié)點可以建立一一對應關(guān)系，由此，復雜網(wǎng)絡中的節(jié)點間的邊與圖像中像素間的關(guān)系也存在一一對應關(guān)系。因此，可以將圖像看成一復雜網(wǎng)絡，通過分析網(wǎng)絡性質(zhì)來選取部分參數(shù)來記錄圖像形狀，再對這些網(wǎng)絡參數(shù)作進一步組合，最終識別圖像中目標。因此，本文采用復雜網(wǎng)絡來描述目標邊界來進行形狀識別，從而保證形狀識別算法的穩(wěn)定性。

1 KNN演化模型

基于復雜網(wǎng)絡的圖像形狀輪廓識別方法一般可以分為三個步驟：①復雜網(wǎng)絡建模;②識別參數(shù)提取;③圖像識別分類。對于第一步復雜網(wǎng)絡建模，以往的動態(tài)演化模型，包括最小生成樹演化，閾值演化等，大多利用無向網(wǎng)絡進行演化。由于有向網(wǎng)絡中包含的結(jié)構(gòu)信息更豐富，因此，本文提出一種基于KNN的演化模型，經(jīng)演化后得到有向子網(wǎng)絡。假定初始網(wǎng)絡用G0表示，則演化過程如下：

其中，KNN（i）表示節(jié)點i的K近鄰，k=1，2，…，|v|-1，KNN（i）。即，當節(jié)點j為節(jié)點i的鄰點，則節(jié)點i與j間存在有向邊。這樣，對不同k，可以得到演化有向子網(wǎng)絡序列。

2 圖像描述與特征提取

下面，利用Harris方法提取圖像中的關(guān)鍵點[1]，并構(gòu)建初始網(wǎng)絡;接著利用網(wǎng)絡拓撲特征實現(xiàn)圖像識別。

2.1 圖像的復雜網(wǎng)絡表示

我們可以用圖G（V，E）表示圖像I，其中，V和E分別表示圖中頂點的集合以及邊的集合。Harris方法可以提出圖像中的角點，因此，本文首先利用該方法提取圖像中的角點，即n個關(guān)鍵點。再以這n個關(guān)鍵點作為網(wǎng)絡的頂點，來建立網(wǎng)絡模型Gn=（Vn，En），其中，任意兩個節(jié)點i與j間的連接邊的權(quán)值用兩者的歐氏距離d（i，j）表示，即：

上述網(wǎng)絡模型Gn可以用一個n×n的權(quán)值矩陣來表示，并將權(quán)值歸一化：

2.2 提取特征向量

利用KNN對上述網(wǎng)絡進行動態(tài)演化，從而得到有向子網(wǎng)絡序列，并將其串聯(lián)構(gòu)成一特征向量，即：

其中，分別表示第i個有向子網(wǎng)絡的度均值、熵值和能量。這里，度均值是將有向子網(wǎng)絡中的各節(jié)點的度相加再計算其平均值。熵和能量的計算公式如下：

3 算法流程

算法流程如圖1所示。算法具體步驟如下：首先，利用Harris角點檢測法提取圖像中的關(guān)鍵點，并構(gòu)建初始網(wǎng)絡模型;接著，利用KNN實現(xiàn)復雜網(wǎng)絡的動態(tài)演化，從而得到有向子網(wǎng)絡序列;然后，利用有向子網(wǎng)絡中的度平均、熵等特征構(gòu)成特征向量;最后，利用特征向量完成圖像輪廓的識別。

4 實驗結(jié)果

為驗證本文提出算法的性能，我們在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個關(guān)鍵點。本文利用查全率與查準率來說明檢索結(jié)果[5]，當查全—查準率曲線與坐標軸圍成的面積越大，則說明檢索性能越好[6]。

本文選用查全率和查準率來表示圖像的檢索性能。查全率是指，檢索出的相關(guān)記錄與全部相關(guān)記錄之間的比值，查準率是指檢索出的相關(guān)記錄與檢索出的全部記錄的比值，從查全-查準率曲線的分布我們可以判斷圖像檢索算法的性能。當查全-查準率曲線與兩條坐標軸之間所圍成的面積越大，則檢索性能越好[7]。圖2顯示了三種方法的實驗結(jié)果。從圖2可以發(fā)現(xiàn)，本文提出的方法優(yōu)于EWT和GED方法。檢索結(jié)果如圖3所示，其中第一列表示待檢索圖像，其余8列表示檢索結(jié)果。從圖3可知，大部分類別的圖像得到較好的檢索結(jié)果，僅有第七類的圖像出現(xiàn)了二幅錯誤檢索結(jié)果。

5 結(jié)束語

本文提出了基于KNN的有向復雜網(wǎng)絡模型來進行圖像形狀的識別，并在COIL-100圖像庫上選取8種物體，共120幅圖像進行了檢索實驗。實驗結(jié)果，相比于基于EWT和基于GED方法，本文提出的方法查全率與查準率均高于其他方法。未來工作將著重解決如何在復雜網(wǎng)絡中保留更多的圖像特征，以進一步提高識別準確率。

參考文獻（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