基于Freeman鏈碼的幾何圖形識別算法

裴姍 章騰

摘 要：目前關(guān)于幾何圖形識別的算法存在的問題主要有準(zhǔn)確率低，計算復(fù)雜度較高，運行時間較長等。利用簡潔高效的Freeman鏈碼算法結(jié)合幾何圖形特有的幾何屬性設(shè)計出新的算法，使其能夠快速識別幾何圖形的頂點分布，并反映在一張邊界震蕩（boundary vibration，BV）曲線圖上。該曲線圖能夠刻畫幾何圖形的屬性，如頂點的個數(shù)、距離分布，角度的大小，線段的曲直和圖形的周長等。因此通過對曲線圖的特征分析可以準(zhǔn)確識別對應(yīng)的幾何圖形。該算法不受圖形的平移、旋轉(zhuǎn)、放縮、噪聲影響。為了測試算法的穩(wěn)定性，仿真試驗針對九種不同的隨機(jī)生成且?guī)г肼暤膸缀螆D形，結(jié)果識別率較高，運行速度較快，達(dá)到了預(yù)期的效果。

關(guān)鍵詞：幾何圖形；識別；Freeman鏈碼；邊界震蕩曲線

中圖分類號：TP317.4 文獻(xiàn)標(biāo)識碼：A

Abstract： Currently there exist some problems about recognition algorithm for geometry figure，such as low rate of accuracy，high order of complexity，long time of running and so forth.This article designs a new algorithm by using the laconic efficient Freeman chain code algorithm with geometry properties of geometry figures，so that it can recognize the distribution of vertexes of geometry figures quickly，and it is displayed in a figure of boundary vibration（BV） curve.By analyzing，we see this figure of curve can describe the properties of geometry figures，such as the number and distance distribution of vertexes，the size of angles，the curvity of line segments，the perimeter of figures and so on.Hence we can recognize the relevant geometry figure accurately by analyzing the characteristic of the figure of curve.This algorithm isn't influenced by translation，rotation，extension and noise of figures.In order to test the stability of the algorithm，the simulation is in connection with nine different kinds of geometry figures which are generated arbitrarily and carry noise，the result shows the rate of accuracy is high and the speed of running is fast，we acquire the prospective effect.

Key words： geometry figure；recognition；Freeman chain code；boundary vibration curve

目前圖像識別技術(shù)應(yīng)用十分廣泛，如在實驗室監(jiān)控中的應(yīng)用[1]，在編組站駝峰作業(yè)過程控制中的應(yīng)用等[2]。也有學(xué)者專門研究了圖像識別的技術(shù)現(xiàn)狀與發(fā)展趨勢[3]。而對基本的幾何圖形的識別在實際的圖像識別中十分關(guān)鍵，通過幾何圖形的識別可以快速掌握實際圖像的輪廓，屬性等特征。目前已有許多學(xué)者在幾何圖形的識別算法研究中卓有成效，文獻(xiàn)[4]中依據(jù)多邊形頂點和其它邊緣像素點的特征值變化規(guī)律設(shè)計了一種簡潔高效的識別算法；文獻(xiàn)[5]中采用了霍夫變換理論來研究圖形的識別。另外，還有一些學(xué)者的研究基于深度學(xué)習(xí)、神經(jīng)網(wǎng)絡(luò)、遺傳算法、特征分布等技術(shù)與方法[6-9]。

考慮到算法的簡潔高效性，借助Freeman鏈碼技術(shù)[10]提出一種新的幾何圖形識別算法。在文獻(xiàn)[11]中雖也采用了類似的方法，并考慮了鏈碼直方圖和鏈碼空間分布熵。但本文試圖充分利用幾何性質(zhì)來設(shè)計出一種新的算法，該算法不受圖形的平移、旋轉(zhuǎn)、伸縮、噪聲影響。仿真結(jié)果準(zhǔn)確率較高，算法運行時間較短，實現(xiàn)了預(yù)期的效果。

2 Freeman鏈碼技術(shù)

Freeman鏈碼技術(shù)是一種用來刻畫數(shù)字圖像的邊界的方法。該方法首先需要定義一個方向坐標(biāo)，常用的兩個方向坐標(biāo)是如圖1的四方向和八方向坐標(biāo)。然后根據(jù)坐標(biāo)來對圖像的邊界按照Moore邊界追蹤算法 進(jìn)行數(shù)字編碼，使得圖像的邊界被一一地轉(zhuǎn)換成一個數(shù)字序列。

如上圖所示，采用四方向坐標(biāo)只能刻畫出的具有四個方向的邊界，因此本文采用八方向坐標(biāo)。

3 算法描述

算法將考慮九種不同形狀的幾何圖形，分別是圓、橢圓、正方形、長方形、菱形、三角形、五邊形、六邊形，以及不規(guī)則圖形。把整個圖形的識別過程分為四個步驟。

3.1 去噪、二值化

在實際的圖像識別中，經(jīng)常會出現(xiàn)噪聲的干擾，如模糊的監(jiān)控畫面等。為了增加算法的適用范圍，考慮隨機(jī)生成的帶有椒鹽噪聲和高斯噪聲的幾何形狀，采用均值濾波來處理高斯噪聲、中值濾波來處理椒鹽噪聲。由于二值圖像比灰度圖像更容易處理，所以通過設(shè)定閾值來進(jìn)行二值化。但是多次運行程序發(fā)現(xiàn)，二值化后的圖像有時會出現(xiàn)孔洞，于是進(jìn)行孔洞填充，取得了不錯的效果，如下圖所示。

3.2 頂點搜索

基于Freeman鏈碼技術(shù)的邊界搜索啟發(fā)，設(shè)計了頂點搜索算法，其思想是：構(gòu)造一個大小合適的正方形，將正方形中心沿圖形邊界移動，用y來記錄正方形落入圖形的面積，即正方形與圖形重合的部分，隨著正方形中心沿著邊界移動，y的值也在不斷的變化。分析發(fā)現(xiàn)，當(dāng)正方形中心在幾何圖形的邊上時，y的值大約為正方形面積的一半；當(dāng)正方形中心靠近到圖形的頂點時，y的值會迅速變小。我們根據(jù)y的值來判斷圖形頂點的個數(shù)。搜索示意圖如下：

通過簡單的平面幾何的知識，在理論上證明了：當(dāng)正方形的中心移動到矩形的頂點時，正方形與矩形重合的面積正好是正方形的1/4，不受矩形旋轉(zhuǎn)的影響。這個事實將幫助在后續(xù)區(qū)分矩形和菱形。

正方形中心沿圖形邊界移動的過程中，模仿Freeman鏈碼的邊界點的搜索來操作。首先模仿Freeman鏈碼中的八方向：1為右上，2為右，3為右下，4為下，5為左下，6為左，7為左上，8為上。搜索過程類似Freeman鏈碼：

（1）起始點為左上角邊界點，起始方向為起始點的下邊。

（2）當(dāng)前點取為起始點，當(dāng)前方向取為起始方向，記錄一次y的值。

（3）在當(dāng)前點的八連通鄰域內(nèi)從當(dāng)前方向順時針?biāo)阉鞯较乱粋€邊界點。

（4）當(dāng)前點改為搜索到的點，當(dāng)前方向改為搜索方向的反方向的下一個方向，并記錄y的值。

（5）若當(dāng)前點和當(dāng)前方向為起始點和起始方

向，則終止搜索，否則重復(fù)3和4。

相應(yīng)的，在具體的代碼中，取圖像左上方的點作為初始點，設(shè)該點坐標(biāo)為（I，J），同時也為正方形的中心，起始方向設(shè)為direct=4。如果（I-1，J+1）=1，即檢測到在（I，J）的右上方有一個邊界點，則將當(dāng)前點（I，J）取為（I-1，J+1），當(dāng)前方向direct=4取為direct=1；否則（I，J）順時針移到下一個檢索點（I，J+1），如果（I，J+1）=1，則當(dāng)前點（I，J）取為（I，J+1），當(dāng)前方向direct=4取為direct=2；以此類推直到檢索完當(dāng)前點（I，J）所有的相鄰點。

3.3 確定頂點個數(shù)

通過上述操作，在每一個邊界點上都得到一個y值，這就將圖形的邊界轉(zhuǎn)化成一個數(shù)字序列，將序列反映在坐標(biāo)軸上，橫坐標(biāo)表示圖形的周長area，縱坐標(biāo)表示正方形與幾何圖形重合的面積y。稱該圖像為邊界震蕩曲線（BV曲線），用該曲線就能分析出圖形頂點的個數(shù)。首先對曲線做預(yù)處理，以便后續(xù)的判定。

（1）由于比較毛糙，因此對曲線進(jìn)行多值化，多值化的目的除了使曲線平滑外，還為了后續(xù)判定圖形角度的大小。

（2）通過算法的設(shè)計知道，圖像的波谷代表頂點出現(xiàn)的位置。由于幾何圖形的邊界都是閉合的，所以BV曲線的頭部與尾部應(yīng)當(dāng)是相接的，故將靠近頭部和尾部的波谷算成同一個波谷。

3.4 圖形的判定

對曲線進(jìn)行多值化后，僅波谷所在的位置會出現(xiàn)極小值點。如果極值點個數(shù)為2，判定為橢圓。如果極值點個數(shù)等于3，則幾何圖形為三角形。如果極值點個數(shù)等于4，但是最大波谷只有2個，則幾何圖形為菱形，因為菱形有2個大波谷，2個小波谷；否則，若波谷之間距離大致相同，則幾何圖形為正方形；若波谷之間距離明顯不相同，則幾何圖形為長方形。如果極值點個數(shù)等于5，則幾何圖形為五邊形。如果極值點個數(shù)等于6，則幾何圖形為六邊形。如果極值點個數(shù)大于6，則幾何圖形為其它圖形。否則，如果圖形的偏心率小于0.1，則幾何圖形為圓；否則為橢圓。

4 仿真結(jié)果

根據(jù)上述設(shè)計的算法得到相應(yīng)的MATLAB程序，運行得到如下結(jié)果。

設(shè)計的頂點搜索算法可以較為準(zhǔn)確的判定出幾何圖形的形狀。為了更直觀的看出圖形與BV曲線的聯(lián)系，把兩者在圖6中同時呈現(xiàn)出來。

規(guī)整的幾何圖形相對應(yīng)的BV曲線的特征是十分明顯的。尤其是前面六種圖形，如圓的BV曲線是正弦形的，正方形的BV曲線是呈現(xiàn)四個大小和間距一致的波谷。通過簡單的幾何證明發(fā)現(xiàn)結(jié)果與理論是相符的。

通過程序的多次運行發(fā)現(xiàn)，該算法對前六種圖形的識別率接近100%，而對邊數(shù)較多且像素較小的圖形識別率相對較低。在BV曲線中也可以看出后三種圖形的周長明顯小于前六種。為了克服這個問題，在識別前將像素較小的圖形放大一倍，使得識別率有了顯著的提高。

5 結(jié)束語

利用Freeman鏈碼的思想得到了一種識別基本幾何圖形的算法，該算法最大的特點是充分利用了圖形的幾何性質(zhì)，并且依然具備Freeman鏈碼算法的簡潔高效性，而且識別率較高。同時利用該算法提出了能夠刻畫邊界屬性的BV曲線概念，該曲線很好地反映出圖形邊界的特征，如頂點數(shù)目與分布，角的大小，線段的曲直等。不同圖形的BV曲線具有顯著的差異。因此接下來的研究方向是BV曲線的代數(shù)刻畫與分類，用以更精準(zhǔn)地提取曲線的特征以及對幾何圖形的判定。

參考文獻(xiàn)

[1] 劉胤，馮軍煥，尹幫旭.圖像識別技術(shù)在實驗室監(jiān)控中的應(yīng)用[J].實驗室研究與探索，2013，32（10）：210—213.

[2] 邢群雁.圖像識別在編組站駝峰作業(yè)過程控制中的應(yīng)用[D].北京：鐵道科學(xué)研究院，2005.

[3] 張家怡.圖像識別的技術(shù)現(xiàn)狀與發(fā)展趨勢[J].電腦知識與技術(shù)，2010，06（21）：6045—6046.

[4] 姚雷博，郭超，張偉民.基于邊緣點特征值的快速幾何圖形識別算法[J].計算機(jī)應(yīng)用研究，2011，28（11）：4386- 4388.

[5] 楊治明，周齊國.基于霍夫變換理論的圖形識別[J].重慶工業(yè)高等?？茖W(xué)校學(xué)報，2002，17（4）：16—17.

[6] 豐曉霞.基于深度學(xué)習(xí)的圖像識別算法研究[D].太原：太原理工大學(xué)，2015.

[7] 王麗華.基于神經(jīng)網(wǎng)絡(luò)的圖像識別系統(tǒng)的研究[D].青島：中國石油大學(xué)（華東），2008.

[8] 范寧.基于遺傳算法的圖像識別方法研究[D].長春：吉林大學(xué)，2015.

[9] 王宇新.基于特征分布的圖像識別方法研究與應(yīng)用[D].大連：大連理工大學(xué)，2012.

[10] GONZALEZ R C，WOODS R E.Digital image processing，Third Edition[M].Pearson Education，2008：796—801.

[11] 胡曉宏.基于鏈碼特征的幾何圖形快速識別算法[J].吉林大學(xué)學(xué)報：理學(xué)版，2015，53（3）：489—493.