胡 曉 宏

(北華大學(xué) 計(jì)算機(jī)科學(xué)技術(shù)學(xué)院,吉林 吉林 132021)

?

基于鏈碼特征的幾何圖形快速識(shí)別算法*

胡 曉 宏

(北華大學(xué) 計(jì)算機(jī)科學(xué)技術(shù)學(xué)院,吉林 吉林 132021)

針對(duì)目前幾何圖形識(shí)別算法計(jì)算復(fù)雜度高、處理時(shí)間長、識(shí)別種類少等問題,提出一種基于鏈碼特征的幾何圖形快速識(shí)別算法.該算法結(jié)合鏈碼直方圖和鏈碼空間分布熵,兼顧鏈碼的統(tǒng)計(jì)特性和空間分布特性,具有尺度、旋轉(zhuǎn)、平移不變性及鏈碼起點(diǎn)無關(guān)性.仿真實(shí)驗(yàn)表明,該算法能夠識(shí)別較多種類的圖形,且識(shí)別準(zhǔn)確率較高、較快.

幾何圖形;鏈碼特征;信息熵;識(shí)別

根據(jù)物體的幾何形狀對(duì)其屬性進(jìn)行判別的方法在圖像處理、目標(biāo)跟蹤、路徑規(guī)劃、場(chǎng)景識(shí)別等領(lǐng)域應(yīng)用廣泛[1-2].物體形狀識(shí)別的過程主要是先提取幾何形狀的某種特征,再通過Hough變換、模糊聚類、形狀匹配、人工神經(jīng)網(wǎng)絡(luò)等方法進(jìn)行識(shí)別[3-4].目前,較常用的圖像特征包括顏色特征、紋理特征及形狀特征3類.其中形狀特征能直觀地描述物體的幾何特性,與被識(shí)別目標(biāo)的匹配性較高,因此屬于更高層次的特征.形狀特征的描述必須符合目標(biāo)的平移、旋轉(zhuǎn)和尺度不變性,一般包括區(qū)域法和邊緣法兩種,本文主要研究邊緣特征.

在圖像邊緣特征中,鏈碼特征是其主要特征之一,目前已有許多研究結(jié)果.例如:文獻(xiàn)[5]研究了方向鏈碼及其曲線描述在纖維圖像識(shí)別中的應(yīng)用,利用整數(shù)描述邊緣相鄰像素間的轉(zhuǎn)動(dòng)角度得到物體邊界的方向鏈碼,并根據(jù)鏈碼值和像素間距離進(jìn)行序列點(diǎn)插值、平滑、擬合后得到鏈碼的曲線描述,效果較好；文獻(xiàn)[6]利用一種改進(jìn)的鏈碼特征對(duì)抽油系統(tǒng)阻尼系數(shù)進(jìn)行識(shí)別,先將封閉曲線鏈碼化,然后利用Fourier系數(shù)計(jì)算封閉曲線的形狀特征,建立以形狀特征為參數(shù)的歐氏距離,以該距離為優(yōu)化目標(biāo)函數(shù)計(jì)算合理的參數(shù)；文獻(xiàn)[7]研究了鏈碼特征在氣象預(yù)報(bào)領(lǐng)域的應(yīng)用,在構(gòu)建基于氣象圖像內(nèi)容層次結(jié)構(gòu)模型的基礎(chǔ)上,提出了相對(duì)極坐標(biāo)系下的距離鏈碼和基于八方向鏈碼的累積導(dǎo)數(shù)和差碼方法,用于輪廓形態(tài)特征的提取,較好解決了非剛體圖像的相關(guān)特征提??；文獻(xiàn)[8]提出了一種改進(jìn)的Freeman鏈碼并將其應(yīng)用到人民幣的面額識(shí)別中,通過統(tǒng)計(jì)紙幣輪廓點(diǎn)橫、縱坐標(biāo)值出現(xiàn)的頻率確定鏈碼起始點(diǎn),并定義一種新的多方向鏈碼解決圖像邊界點(diǎn)的間斷問題,有效提高了識(shí)別準(zhǔn)確率.但上述方法都是針對(duì)某一特定應(yīng)用領(lǐng)域,普適性和推廣性較差,當(dāng)實(shí)際應(yīng)用背景變化時(shí),算法的識(shí)別準(zhǔn)確率較低.基于此,本文提出一種通用的幾何圖形鏈碼特征提取方法.首先提出了鏈碼空間分布的概念,在此基礎(chǔ)上,計(jì)算圖形鏈碼統(tǒng)計(jì)直方圖的空間分布熵,并將其作為形狀特征用于幾何圖形的識(shí)別.此外,還給出了一種有效的圖形相似性度量方法.仿真實(shí)驗(yàn)表明,本文提出的基于鏈碼空間分布熵的幾何圖形識(shí)別方法正確、有效.

1 方向鏈碼

方向鏈碼是一種有效描述圖形邊界形狀的編碼方法,其特點(diǎn)是定義一種方向,然后根據(jù)該方向?qū)D形邊界進(jìn)行編碼,得到一組相連的具有特定長度和方向的字符串.目前較常用的方向鏈碼包括Freeman鏈碼和Bribiesca鏈碼,如圖1所示.

圖1 鏈碼編碼方式Fig.1 Encoding modes of chain code

圖2 示例形狀Fig.2 Example shapes

2 算法描述

2.1鏈碼空間分布熵特征

鏈碼空間分布是指不同方向鏈碼在鏈碼串中的空間位置變化,圖形的形狀不同,其鏈碼空間分布也不同,因此鏈碼直方圖的空間分布也必不相同.

圖3 鏈碼空間分布示例Fig.3 Examples of chain code distribution

下面以圖3為例描述鏈碼直方圖的空間分布特征.由圖3可見,鏈碼串1的鏈碼直方圖空間分布為

(1)

鏈碼串2的鏈碼直方圖空間分布為

(2)

(3)

(4)

其中:n表示方向個(gè)數(shù);m表示某一方向鏈碼的子串個(gè)數(shù).從而可定義一個(gè)鏈碼特征為

(5)

該鏈碼特征結(jié)合了鏈碼直方圖和鏈碼空間分布熵,因此具有起點(diǎn)無關(guān)性以及尺度、平移不變性.此時(shí),再以圖2所示的兩個(gè)幾何圖形為例,可得它們的鏈碼特征分別為〈(0.21,0),(0.04,0),(0.21,0),(0.04,0),(0.21,0),(0.04,0),(0.21,0),(0.04,0)〉和〈(0.21,0.29),(0.04,0),(0.21,0.29),(0.04,0),(0.21,0.29),(0.04,0),(0.21,0.22),(0.04,0)〉,可見它們的Fc特征區(qū)分性較強(qiáng),特別有利于識(shí)別.

此外,為了使該特征具有旋轉(zhuǎn)不變性,參考文獻(xiàn)[10]的方法,在計(jì)算鏈碼直方圖和鏈碼空間分布熵前,先對(duì)鏈碼串進(jìn)行旋轉(zhuǎn)歸一化處理.

2.2相似性度量

在得到幾何圖形的鏈碼特征后,再考慮如何評(píng)價(jià)待識(shí)別圖形與標(biāo)準(zhǔn)圖形之間的相似性.目前較常用的評(píng)價(jià)方法包括歐氏距離、馬氏距離、余弦相似等,但這些常用方法對(duì)于本文提出的圖形鏈碼特征并不適用,因此本文提出一種新的相似性度量方法.

假設(shè)有兩個(gè)幾何圖形分別為X和Y,根據(jù)鏈碼特征Fc定義相似性為

(6)

以圖2所示幾何圖形為例,分別使用式(6)的相似性計(jì)算公式及歐氏距離、馬氏距離、余弦相似方法,在得到鏈碼特征的基礎(chǔ)上,分別計(jì)算圖中兩個(gè)幾何圖形的相似性,結(jié)果列于表1.

表1 相似性計(jì)算結(jié)果Table 1 Similarity results

由表1可見,利用本文方法計(jì)算的相似性遠(yuǎn)低于其他方法的計(jì)算結(jié)果,因此本文提出的相似性度量指標(biāo)更適合于本文的幾何圖形鏈碼特征.

2.3算法實(shí)現(xiàn)

本文提出的基于鏈碼空間分布熵和鏈碼直方圖特征的幾何圖形識(shí)別算法實(shí)現(xiàn)步驟如下：

1)根據(jù)八方向編碼規(guī)則計(jì)算幾何圖形的基本方向鏈碼串；

2)對(duì)基本方向鏈碼串進(jìn)行旋轉(zhuǎn)歸一化處理；

3)計(jì)算鏈碼串的統(tǒng)計(jì)直方圖；

4)計(jì)算鏈碼串的空間分布熵；

5)根據(jù)式(5)構(gòu)造圖形鏈碼特征；

6)根據(jù)式(6)計(jì)算待識(shí)別圖形與數(shù)據(jù)庫中圖形鏈碼特征之間的相似度,最終實(shí)現(xiàn)對(duì)幾何圖形的識(shí)別.

3 仿真實(shí)驗(yàn)

選取SQUID圖像庫為實(shí)驗(yàn)對(duì)象,該圖像庫是幾何圖形識(shí)別領(lǐng)域較常用的測(cè)試數(shù)據(jù)庫,其中包含1 100幅不同類型魚類的輪廓,圖形種類豐富.但SQUID圖像庫中的圖形基本為不規(guī)則幾何圖形,因此本文又利用MATLAB軟件隨機(jī)生成了700幅規(guī)則幾何圖形(256×256),其中包括圓形、橢圓形、矩形、三角形、五邊形、六邊形及八邊形各100幅,共1 800幅圖像.

為了保證評(píng)價(jià)的客觀性和有效性,同時(shí)將本文算法與基本鏈碼特征方法、鏈碼直方圖方法及文獻(xiàn)[11]的方法進(jìn)行比較分析.首先定義識(shí)別準(zhǔn)確率,在一次識(shí)別過程中,會(huì)出現(xiàn)“準(zhǔn)確識(shí)別”、“錯(cuò)誤識(shí)別”及“未知”3種識(shí)別結(jié)果,因此定義識(shí)別準(zhǔn)確率為

(7)

在相同條件下,共進(jìn)行20次重復(fù)實(shí)驗(yàn),每次隨機(jī)從圖像庫中抽取500幅圖像進(jìn)行實(shí)驗(yàn),識(shí)別結(jié)果如圖4所示.由圖4可見,本文方法的識(shí)別效果最好,評(píng)價(jià)識(shí)別準(zhǔn)確率為90.70%,單次最高為93.88%,單次最低為88.67%；文獻(xiàn)[11]方法的識(shí)別效果略低于本文方法,平均達(dá)到了88.40%,最高為90.70%,最低為86.85%；鏈碼直方圖方法的效果一般,平均僅為71.15%,最高為73.58%,最低為68.49%；基本鏈碼法的結(jié)果最差,平均只有52.74%,最高為54.82%,最低為51.06%.

識(shí)別用時(shí)也是評(píng)價(jià)識(shí)別算法的一個(gè)重要評(píng)價(jià)指標(biāo),對(duì)算法的實(shí)際應(yīng)用有較大影響.本文計(jì)算的識(shí)別用時(shí)是對(duì)單幅圖像識(shí)別的平均用時(shí),測(cè)試圖像的選取方法和測(cè)試方法同上,測(cè)試結(jié)果如圖5所示.由圖5可見,基本鏈碼法的識(shí)別用時(shí)最少,平均僅為0.650 8 s；鏈碼直方圖方法略高,平均為0.686 0 s；文獻(xiàn)[11]方法與本文方法的用時(shí)基本相同,平均約為0.85 s.

圖4 不同方法識(shí)別準(zhǔn)確率的比較Fig.4 Comparison of recognition accuracyrate by different method

圖5 不同方法識(shí)別用時(shí)的比較Fig.5 Comparison of recognition timeconsuming by different method

綜合比較識(shí)別準(zhǔn)確率和識(shí)別用時(shí)兩個(gè)評(píng)價(jià)指標(biāo),本文算法的識(shí)別準(zhǔn)確率在4種方法中最高,說明結(jié)合了鏈碼空間分布熵和鏈碼直方圖的特征有利于幾何圖形的識(shí)別,特征區(qū)分性較好,對(duì)于同一種圖形,不會(huì)因?yàn)殒湸a起點(diǎn)的改變及圖形的平移、旋轉(zhuǎn)和尺度變化,而影響識(shí)別結(jié)果的準(zhǔn)確性.但由于需要計(jì)算鏈碼空間分布熵,所以算法的識(shí)別用時(shí)相對(duì)較長,但由測(cè)試結(jié)果可見,平均0.85 s的識(shí)別用時(shí)完全可以滿足實(shí)際應(yīng)用的需要.

綜上所述,本文研究了基于鏈碼特征的幾何圖形識(shí)別.在鏈碼直方圖特征的基礎(chǔ)上,提出了鏈碼空間分布熵特征,并將二者結(jié)合構(gòu)成幾何圖形識(shí)別的形狀特征.同時(shí),本文給出了一種新的衡量圖像之間相似性的度量方法.仿真實(shí)驗(yàn)表明,本文方法具有較好的識(shí)別準(zhǔn)確率和較低的識(shí)別用時(shí),能夠較好地克服鏈碼起點(diǎn)變化及圖形平移、旋轉(zhuǎn)和尺寸變化帶來的影響.

[1] 孫來軍,李江游,候影,等.一種規(guī)則幾何圖形的計(jì)算機(jī)識(shí)別方法 [J].微型機(jī)與應(yīng)用,2011,30(9):42-45.(SUN Laijun,LI Jiangyou,HOU Ying,et al.A Computer Recognition Method of Regular Geometry Graphics [J].Microcomputer &Its Applications,2011,30(9):42-45.)

[2] 楊凱,華慶一,陳新勝.一種交互式識(shí)別幾何圖形的簡易方法 [J].計(jì)算機(jī)技術(shù)與發(fā)展,2008,18(3):21-23.(YANG Kai,HUA Qingyi,CHEN Xinsheng.A Simple Approach to Recognize Geometric Shapes Interactively [J].Computer Technology and Development,2008,18(3):21-23.)

[3] 段汝嬌,趙偉,黃松嶺,等.一種基于改進(jìn)Hough變換的直線快速檢測(cè)算法 [J].儀器儀表學(xué)報(bào),2010,31(12):2774-2780.(DUAN Rujiao,ZHAO Wei,HUANG Songling,et al.Fast Line Detection Algorithm Based on Improved Hough Transformation [J].Chinese Journal of Scientific Instrument,2010,31(12):2774-2780.)

[4] 張坤艷,鐘宜亞,苗松池,等.一種基于全局閾值二值化方法的BP神經(jīng)網(wǎng)絡(luò)車牌字符識(shí)別系統(tǒng) [J].計(jì)算機(jī)工程與科學(xué),2010,32(2):88-90.(ZHANG Kunyan,ZHONG Yiya,MIAO Songchi,et al.A Plate-Character Identification System Based on Global Valve Binarization and the BP Neural Network [J].Computer Engineering &Science,2010,32(2):88-90.)

[5] 孫建成,曾培峰,禹素萍,等.方向鏈碼及其曲線描述在纖維圖像識(shí)別中的應(yīng)用 [J].上海工程技術(shù)大學(xué)學(xué)報(bào),2005,19(3):239-243.(SUN Jiancheng,ZENG Peifeng,YU Suping,et al.Directional Chain Code and Curve Description Based Fiber Image Recognition [J].Journal of Shanghai University of Engineering Science,2005,19(3):239-243.)

[6] 劉柏希,劉宏昭,饒建華,等.改進(jìn)的鏈碼特征識(shí)別方法及在抽油系統(tǒng)阻尼系數(shù)辨識(shí)中的應(yīng)用 [J].機(jī)械工程學(xué)報(bào),2007,43(12):212-216.(LIU Baixi,LIU Hongzhao,RAO Jianhua,et al.Ameliorative Characteristic Recognition Method Based on Modified Chain Code and Its Application in Damping Coefficients Identification for Rod Pumping System [J].Chinese Journal of Mechanical Engineering,2007,43(12):212-216.)

[7] 王萍,強(qiáng)兆慶,許晉瑋,等.基于鏈碼描述的圖像圖形特征提取 [J].計(jì)算機(jī)應(yīng)用,2009,29(8):2065-2067.(WANG Ping,QIANG Zhaoqing,XU Jinwei,et al.Feature Extraction of Images and Graphics Based on Chain Code Description [J].Journal of Computer Applications,2009,29(8):2065-2067.)

[8] 杜京義,殷姣.改進(jìn)的Freeman鏈碼進(jìn)行人民幣的面額識(shí)別 [J].計(jì)算機(jī)工程與設(shè)計(jì),2012,33(12):4643-4646.(DU Jingyi,YIN Jiao.Using Improved Freeman Chain Code to RMB Denomination Identification [J].Computer Engineering and Design,2012,33(12):4643-4646.)

[9] Iivarinen J,Visa A.Shape Recognition of Irregular Objects [J].SPIE,1996,2904：25-32.

[10] 韓光,趙春霞,陸建峰,等.面向彩色圖像的尺度和旋轉(zhuǎn)不變性特征提取方法及應(yīng)用 [J].中國圖象圖形學(xué)報(bào),2011,16(3):398-405.(HAN Guang,ZHAO Chunxia,LU Jianfeng,et al.Scale and Rotation Invariant Feature Extraction Method Based on Color Image and Its Applications [J].Journal of Image and Graphics,2011,16(3):398-405.)

[11] 姚雷博,郭超,張偉民.基于邊緣點(diǎn)特征值的快速幾何圖形識(shí)別算法 [J].計(jì)算機(jī)應(yīng)用研究,2011,28(11):4386-4388.(YAO Leibo,GUO Chao,ZHANG Weimin.Fast Geometry Figure Recognition Algorithm Based on Edge Pixel Point Eigenvalues [J].Application Research of Computers,2011,28(11):4386-4388.)

(責(zé)任編輯：韓 嘯)

QuickRecognitionAlgorithmforGeometryFigureBasedonChainCodeFeature

HU Xiaohong

(CollegeofComputerScienceandTechnology,BeihuaUniversity,Jilin132021,JilinProvince,China)

In view of some shortcomings about currently shape recognition algorithms such as a large amount of calculation,long processing time,fewer species recognition,a fast geometry figure recognition algorithm based on chain code feature was presented.The algorithm combines the chain code histogram and chain code spatial distribution entropy,which considers both the statistical feature and the spatial feature of the chain code,having the advantages of being invariant to the position,rotation and scale of the image content and having nothing to do with the start point of the chain code.The simulation results show that the algorithm is able to identify many types of graphics with high recognition accuracy and shorter time consuming,and the overall performance is excellent.

geometry figure;chain code feature;information entropy;recognition

10.13413/j.cnki.jdxblxb.2015.03.27

2014-12-11. *“吉林省計(jì)算機(jī)學(xué)會(huì)2015年學(xué)術(shù)年會(huì)(JLPCF2015)”征集論文.

胡曉宏(1969—),女,漢族,碩士,副教授,從事計(jì)算機(jī)應(yīng)用技術(shù)的研究,E-mail:Bhhxh69@163.com.

吉林省科技廳項(xiàng)目(批準(zhǔn)號(hào):20130102030JC).

TP317.4

：A

：1671-5489(2015)03-0489-05