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

裴姍 章騰

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

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

中圖分類號：TP317.4 文獻標識碼：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

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

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

2 Freeman鏈碼技術

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

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

3 算法描述

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

3.1 去噪、二值化

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

3.2 頂點搜索

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

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

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

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

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

（3）在當前點的八連通鄰域內從當前方向順時針搜索到下一個邊界點。

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

（5）若當前點和當前方向為起始點和起始方

向，則終止搜索，否則重復3和4。

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

3.3 確定頂點個數

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

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

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

3.4 圖形的判定

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

4 仿真結果

根據上述設計的算法得到相應的MATLAB程序，運行得到如下結果。

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

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

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

5 結束語

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

參考文獻

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

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

[3] 張家怡.圖像識別的技術現狀與發展趨勢[J].電腦知識與技術，2010，06（21）：6045—6046.

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

[5] 楊治明，周齊國.基于霍夫變換理論的圖形識別[J].重慶工業高等專科學校學報，2002，17（4）：16—17.

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

[7] 王麗華.基于神經網絡的圖像識別系統的研究[D].青島：中國石油大學（華東），2008.

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

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

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

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