基于KNN有向復(fù)雜網(wǎng)絡(luò)的圖像輪廓識別

李詠豪

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

關(guān)鍵詞： 復(fù)雜網(wǎng)絡(luò); 圖像識別; 圖像輪廓; K最近鄰; 熵

中圖分類號：TP274? ? ? ? ? 文獻(xiàn)標(biāo)志碼：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 引言

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

1 KNN演化模型

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

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

2 圖像描述與特征提取

下面，利用Harris方法提取圖像中的關(guān)鍵點[1]，并構(gòu)建初始網(wǎng)絡(luò);接著利用網(wǎng)絡(luò)拓?fù)涮卣鲗崿F(xiàn)圖像識別。

2.1 圖像的復(fù)雜網(wǎng)絡(luò)表示

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

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

2.2 提取特征向量

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

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

3 算法流程

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

4 實驗結(jié)果

為驗證本文提出算法的性能，我們在Columbia Object Image Library-100（COIL-100）[1]圖像庫上進(jìn)行了圖像檢索實驗。該圖像庫共包括100種類別的物體，每個類別中各包含72幅從不同視角拍攝的圖像，總共有7200幅。本文共選取8種物體，每種物體包括15幅圖像，總共組成120幅圖像作檢索，并與基于EWT（Edges Weights Threshold）[3]和基于GED（Graph Edit Distance）[4]的圖像描述方法進(jìn)行對比。實驗中，每幅圖像共提取45個關(guān)鍵點。本文利用查全率與查準(zhǔn)率來說明檢索結(jié)果[5]，當(dāng)查全—查準(zhǔn)率曲線與坐標(biāo)軸圍成的面積越大，則說明檢索性能越好[6]。

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

5 結(jié)束語

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

參考文獻(xiàn)（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