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

胡 曉 宏

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

?

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

胡 曉 宏

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

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

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

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

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

1 方向鏈碼

方向鏈碼是一種有效描述圖形邊界形狀的編碼方法,其特點是定義一種方向,然后根據該方向對圖形邊界進行編碼,得到一組相連的具有特定長度和方向的字符串.目前較常用的方向鏈碼包括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表示方向個數;m表示某一方向鏈碼的子串個數.從而可定義一個鏈碼特征為

(5)

該鏈碼特征結合了鏈碼直方圖和鏈碼空間分布熵,因此具有起點無關性以及尺度、平移不變性.此時,再以圖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特征區分性較強,特別有利于識別.

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

2.2相似性度量

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

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

(6)

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

表1 相似性計算結果Table 1 Similarity results

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

2.3算法實現

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

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

2)對基本方向鏈碼串進行旋轉歸一化處理；

3)計算鏈碼串的統計直方圖；

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

5)根據式(5)構造圖形鏈碼特征；

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

3 仿真實驗

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

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

(7)

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

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

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

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

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

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

[1] 孫來軍,李江游,候影,等.一種規則幾何圖形的計算機識別方法 [J].微型機與應用,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].計算機技術與發展,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] 段汝嬌,趙偉,黃松嶺,等.一種基于改進Hough變換的直線快速檢測算法 [J].儀器儀表學報,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].計算機工程與科學,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] 孫建成,曾培峰,禹素萍,等.方向鏈碼及其曲線描述在纖維圖像識別中的應用 [J].上海工程技術大學學報,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].機械工程學報,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].計算機應用,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] 杜京義,殷姣.改進的Freeman鏈碼進行人民幣的面額識別 [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] 韓光,趙春霞,陸建峰,等.面向彩色圖像的尺度和旋轉不變性特征提取方法及應用 [J].中國圖象圖形學報,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].計算機應用研究,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.)

(責任編輯：韓 嘯)

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. *“吉林省計算機學會2015年學術年會(JLPCF2015)”征集論文.

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

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

TP317.4

：A

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