李詠豪

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

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

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

1 KNN演化模型

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

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

2 圖像描述與特征提取

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

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

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

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

2.2 提取特征向量

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

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

3 算法流程

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

4 實(shí)驗(yàn)結(jié)果

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

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

5 結(jié)束語(yǔ)

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