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

胡 曉 宏

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

?

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

胡 曉 宏

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

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

幾何圖形;鏈碼特征;信息熵;識別

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

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

1 方向鏈碼

方向鏈碼是一種有效描述圖形邊界形狀的編碼方法,其特點是定義一種方向,然后根據(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表示方向個數(shù);m表示某一方向鏈碼的子串個數(shù).從而可定義一個鏈碼特征為

(5)

該鏈碼特征結(jié)合了鏈碼直方圖和鏈碼空間分布熵,因此具有起點無關(guān)性以及尺度、平移不變性.此時,再以圖2所示的兩個幾何圖形為例,可得它們的鏈碼特征分別為〈(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ū)分性較強,特別有利于識別.

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

2.2相似性度量

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

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

(6)

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

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

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

2.3算法實現(xiàn)

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

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

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

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

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

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

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

3 仿真實驗

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

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

(7)

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

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

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

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

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

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

[1] 孫來軍,李江游,候影,等.一種規(guī)則幾何圖形的計算機識別方法 [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] 楊凱,華慶一,陳新勝.一種交互式識別幾何圖形的簡易方法 [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變換的直線快速檢測算法 [J].儀器儀表學(xué)報,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ò)車牌字符識別系統(tǒng) [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] 孫建成,曾培峰,禹素萍,等.方向鏈碼及其曲線描述在纖維圖像識別中的應(yīng)用 [J].上海工程技術(shù)大學(xué)學(xué)報,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)的鏈碼特征識別方法及在抽油系統(tǒng)阻尼系數(shù)辨識中的應(yīng)用 [J].機械工程學(xué)報,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] 王萍,強兆慶,許晉瑋,等.基于鏈碼描述的圖像圖形特征提取 [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)行人民幣的面額識別 [J].計算機工程與設(shè)計,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é)報,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] 姚雷博,郭超,張偉民.基于邊緣點特征值的快速幾何圖形識別算法 [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. *“吉林省計算機學(xué)會2015年學(xué)術(shù)年會(JLPCF2015)”征集論文.

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

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

TP317.4

：A

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