基于Freeman鏈碼的自由曲線直線逼近算法

摘 要： 提出一種簡單而有效的直線逼近自由曲線算法。自由曲線輪廓采用Freeman鏈碼描述，提出快速分割鏈碼算法，得出逼近節(jié)點，從而準確地實現(xiàn)對曲線的逼近。此外，該方法不僅適用于直線、圓弧和非圓曲線，而且還適用于形狀復(fù)雜，不能用初等解析函數(shù)直接表示的自由曲線。實驗結(jié)果表明，該算法簡單、快速、準確，并對自由曲線具有較好的逼近效果。

關(guān)鍵詞： Freeman鏈碼； 逼近節(jié)點； 自由曲線； 邊界描述； 直線逼近

中圖分類號：TP391.72 文獻標志碼：A 文章編號：1006-8228（2013）12-57-03

Linear approximation algorithm of free curves based on Freeman chain code

Yang Bin

（Dept. of Information center， Wuxi AIC， Wuxi， Jiangshu 214023， China）

Abstract： A simple and efficient algorithm of the linear approximation of free curves is proposed. In the paper， the contour of a free curve is described by Freeman chain code. A rapid segmentation algorithm of chain code is proposed so as to get the approximation nodes. Thus， a more accurate approximation of the curve can be achieved. In addition， this method can not only be applied to straight lines， arcs and non-circular curves， but also curves which have complex shape and can not be described by an explicit function. The experiment results show that the algorithm is simple， rapid， accurate， and free curves have good approximation.

Key words： Freeman chain code； approximation node； free curve； contour description； line approximation

0 引言

在數(shù)控系統(tǒng)中，非圓曲線是指除直線與圓弧之外，可以用數(shù)學方程式表達的平面輪廓曲線。而數(shù)控系統(tǒng)一般只能做直線插補和圓弧插補，對于輪廓為非圓曲線的零件，數(shù)學處理的方法是用直線段或圓弧段去逼近曲線輪廓[1]。直線段逼近輪廓曲線的關(guān)鍵在于計算出節(jié)點。節(jié)點是在用直線段或圓弧段去近似曲線時，相鄰直線段或圓弧段之間的交點。其中，直線逼近非圓曲線常用的計算節(jié)點方法有：等間距法、等弦長法、等誤差法等。等間距法就是將曲線沿著某一坐標軸分割，分割點在坐標軸上的投影等間距，根據(jù)曲線方程得到分割點的坐標，即根據(jù)已知曲線方程y=f（x），可由xi求得yi，xi+1=xi+Δx，yi+1=f（xi+Δx）（其中Δx為間距）。這種方法是通過調(diào)整分割點個數(shù)來調(diào)整逼近誤差。但節(jié)點越多，程序運行耗時越多。等弦長法是用各段長度相同的弦來逼近曲線，誤差是通過以最小曲率半徑處的加精度確定弦長。這種方法在曲線曲率半徑變化較大時，節(jié)點將增多，所以此種方法適用于曲線曲率變化不大的情況。等誤差法是以最大允許誤差為半徑，以曲線一端點為圓心作圓。然后作圓與曲線的公切線，再以曲線端點為點作一條與公切線平行的直線與曲線相交，交點即為節(jié)點，依次類推。該方法特別適合于曲率變化較大的復(fù)雜曲線。不足之處是直線插補段的連接處不光滑[2]。

以上方法對于已知方程的曲線各有較好的逼近效果，但是，對于未知表達式的曲線都不適用。所以本文在此基礎(chǔ)上，提出直線逼近自由曲線的算法，改善原有計算節(jié)點方法中的缺陷，針對非圓曲線和未知表達式曲線，采用Freeman鏈碼來描述曲線，快速分割鏈碼，找出逼近節(jié)點，從而實現(xiàn)對自由曲線的快速逼近。另外，減少了大量的數(shù)學計算，大大提高了程序的運行速度。

1 邊界鏈碼表示

鏈碼是圖像處理及模式識別中很常見一種的表達線條、平面曲線及區(qū)域邊界的編碼技術(shù)。鏈碼技術(shù)被廣泛應(yīng)用是因為它能用較少的數(shù)據(jù)來存儲較多的信息。用鏈碼來表示線條模式的方法是由Freeman首先提出來的。Freeman鏈碼至今仍然是一個被廣泛使用的最主要的鏈碼編碼方法。Freeman鏈碼主要有兩種編碼方式：八方位鏈編碼和四方位鏈編碼。八方位鏈的編碼方法是沿著數(shù)字曲線或邊界像素以8鄰接的方式移動，每一個移動方向由數(shù)字集{i|i=0，1，2，3，4，5，6，7，8}進行編碼，表示與x軸正向的 45?×i夾角[3，4]，如圖1所示。

圖1 Freeman八方位鏈編碼

四方位的鏈編碼在矩形點陣中，沿著區(qū)域的邊界西、北、東、南分別以數(shù)字1、2、3、4標記。本文中采用Freeman鏈碼的八方位編碼方式。

1.1 圖像預(yù)處理

在讀取曲線鏈碼之前，需要對原圖像進行一系列預(yù)處理工作：①根據(jù)原圖像像素分布特征，采用閾值分割或像素3×3鄰域像素和分割，分離出目標和背景；②采用中值濾波，對圖像進行平滑處理；③對于圖像中出現(xiàn)的“毛刺”采用剔除的辦法，進行去噪；④細化處理，保留目標圖像的骨架及線條的連貫性；⑤輪廓跟蹤，提取出目標邊界。

1.2 邊界鏈碼表示算法描述

通常圖像中的目標對象可分為連通體和非連通體。對于連通體的邊界鏈碼讀取方法為：從圖像邊界上任一像素點開始，沿著圖像的邊界像素點按順時針方向或逆時針方向搜索，直到回到起點坐標為止。搜索中記錄邊界線上兩兩相鄰像素點間的方向，形成一個由方向鏈碼組成的有序鏈。同時記錄下起點坐標，這樣圖像的邊界就可以被惟一確定下來[5-6]。這種由方向鏈碼構(gòu)成的有序鏈為Freeman鏈碼。

圖像邊界的Freeman鏈碼可以表示為{（x0，y0）|c0c1c2…cn-1}，其中（x0，y0）為起點坐標，ci∈{0，1，2，3，4，5，6，7}為Freeman八方向鏈碼，n為鏈的長度。

在Freeman鏈碼中，對同一邊界，如果目標旋轉(zhuǎn)或起點選取不同，鏈碼表示就會發(fā)生變化。這種情況可以通過求取差分碼的方法來解決[7]。所以任意選取連通體的起點并不會影響Freeman鏈碼以及鏈的條數(shù)。

但是對于非連通體，起點的選取將會直接對鏈碼以及鏈碼的條數(shù)產(chǎn)生影響。如圖2中所示，這樣一條非連通曲線，若起點選擇最高點（Xmaxh， Ymaxh），F(xiàn)reeman鏈碼將會讀成該點的左右兩條鏈。然而，鏈碼的正確讀取直接關(guān)系后序?qū)︽湸a的正確分割，所以此處正確讀取鏈碼非常關(guān)鍵。

顯然，按上述連通體的邊界鏈碼讀取方法，對于非連通體，起點選擇在首尾兩端點之間的其他任何點，都會出現(xiàn)這種一條曲線讀出兩條鏈碼的錯誤。而起點若選擇首尾兩端點之一，就不會出現(xiàn)這樣的錯誤。圖2中按左側(cè)的首端點（X0，Y0）為起點，則讀取的鏈碼為：{（X0，Y0） | 2 1 2 1 2 2 1 2 2 1 2 1 2 2 1 2 2 1 2 1 2 2 1 2 1 2 2 1 2 2 1 2 1 2 2 1 2 1 2 2 1 2 1 2 1 2 2 1 2 1 2 2 1 2 1 2 1 2 1 2 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 1 2 1 1 2 1 2 1 1 1 1 2 1 1 1 1 0 1 1 1 0 0 0 0 0 0 0 0 0 7 0 7 7 0 7 7 7 7 7 7 7 7 6 7 7 7 7 7 6 7 7 7 6 7 7 7 7 6 7 7 7 7 6 7 7 7 6 7 7 7 7 7 7 6 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 0 7 7 7 0 7 7 7 0 7 7 0 7 7 7 0 7 0 7 0 7 0 7 0 7 0 7 0 7 0 7 0 7 0 7 0 7 0 7 0 0 7 0 0 7 0 0 7 0 0 7 0 0 0 7 0 0 0 7 0 0 0 0 7 0 0 0 0 0 0 7 0 0 0 0 0 0 0 0 0 7 0 0 0 0 0 0 0 }。

圖2 非連通曲線

本文還擬設(shè)一種新的深度搜索順序，設(shè)Freeman鏈碼值為0、2、4、6的方向為主方向，以鏈碼值為1、3、5、7的方向為次方向，主、次方向中各方向優(yōu)先級按碼值遞增而減少。其中主方向優(yōu)先于次方向。從起點處開始，按此優(yōu)先級順序深度搜索邊界。實驗結(jié)果證明，該種方法對于單像素的邊界，其編碼正確有效。

2 自由曲線的直線逼近算法

任何目標物體的平面圖像的輪廓都可以由一條或幾條閉合曲線構(gòu)成，這些曲線一般可近似認為由直線及圓弧組合而成。因此，直線及圓弧是構(gòu)成目標物體輪廓的基元[8]。非圓曲線在編制加工程序中常要轉(zhuǎn)換成用直線或圓弧逼近的曲線后加工。引言部分中所提到的幾種直線逼近非圓曲線的方法就是在非圓曲線方程已知的前提下求取逼近節(jié)點，實現(xiàn)對曲線的近似的。但對于平面曲線方程未知的情況，上述方法并不能實現(xiàn)對此類曲線的逼近。

圖3、圖4中列出的幾種曲線，分別為：非連通未知方程和連通未知方程，非連通已知方程和連通已知方程四種曲線。本文中在正確提取該條曲線的Freeman鏈碼之后，提出快速分割鏈碼算法，分割點作為節(jié)點，這種方法針對方程已知與未知的曲線均適用。

圖3 非連通未知方程和連通未知方程曲線圖

圖4 非連通已知方程和連通已知方程曲線圖

正確讀取鏈碼后，快速分割鏈碼的過程具體如下：

從鏈碼起始處開始，計算相鄰兩鏈碼值之差的絕對值_abs，若_abs為1或7，則判為兩相鄰碼值，每段鏈碼中只允許最多出現(xiàn)2個鏈碼值，若出現(xiàn)第3個鏈碼值，則設(shè)置斷開點，若兩碼值之一單獨出現(xiàn)次數(shù)超過給定的閾值SingleRepeatCount，則將此段連續(xù)鏈碼判為直線段，同樣設(shè)置斷開點；若_abs大于等于2，則設(shè)置斷開點；若_abs等于0，則累加重復(fù)出現(xiàn)次數(shù)。按以上規(guī)則，遍歷鏈碼直至結(jié)束。

3 實驗結(jié)果及分析

我們應(yīng)用本文算法，在計算機上對圖像中的自由曲線進行了大量的直線逼近實驗，都能得出較為理想的結(jié)果。限于篇幅，我們只在圖5中列出結(jié)果，從圖5可以看出隨著設(shè)定的單像素連續(xù)重復(fù)出現(xiàn)次數(shù)的閾值SingleRepeatCount的減小，逼近的效果越好。

圖5 曲線1在閾值SingleRepeatCount不同下的直線逼近結(jié)果

同樣，我們對實際曲線均進行了大量的實驗，現(xiàn)將圖3、圖4中的四種曲線在不同閾值下的實驗結(jié)果數(shù)據(jù)列在表1中，將圖3、4中曲線2、3、4的實驗結(jié)果圖附在圖6、7、8中。

表1 圖3、4中四條曲線的直線逼近測試結(jié)果（單位：像素）

[測試曲線＼總碼數(shù)＼總像素數(shù)＼單像素連續(xù)重復(fù)

出現(xiàn)次數(shù)的閾值＼節(jié)點數(shù)＼

曲線1

＼255

255

255＼256

256

256＼10

5

3＼8

13

21＼

曲線2＼646

646

646＼646

646

646＼10

5

3＼32

43

67＼曲線3＼256

256

256＼257

257

257＼10

5

3＼5

5

13＼

曲線4＼326

326

326＼326

326

326＼10

5

3＼8

17

29＼]

4 結(jié)束語

本文主要研究了自由曲線輪廓的Freeman鏈碼描述，并在此基礎(chǔ)上，提出了快速分割鏈碼算法，通過分割鏈碼，找到直線逼近曲線的節(jié)點。該方法所具有的優(yōu)點是：①解決了未知表達式曲線的直線逼近節(jié)點的求取，此類方法對直線、圓弧和非圓曲線，以及自由曲線均適用；②合理引入閾值，通過閾值控制逼近的精度；③分割鏈碼中，曲線輪廓上的主要特征點均能得到；④避免了大量的數(shù)學計算，提高了程序的運行速度。實驗結(jié)果證明，該方法能準確、快速地實現(xiàn)直線對自由曲線的逼近。

圖6 曲線2在閾值不同情況下逼近

圖7 曲線3在閾值不同情況下逼近

圖8 曲線4在閾值不同情況下逼近

在以后的工作中，將進一步研究和分析曲線鏈碼的特征，進一步提高曲線擬合中的光滑性。

參考文獻：

[1] 劉雄偉，張定華.數(shù)控加工理論及編程技術(shù)[M].機械工業(yè)出版社，

1993.

[2] Powell， M.J.D.， Approximation theory and methods[M]. Cambridge

University Press， London，1981.

[3] Freeman H. \"Boundary encoding and processing\" in Picture

Processing and Psychopictories[C]. New York： Academic，1970：241-266

[4] 劉勇奎.計算機圖形學的基礎(chǔ)算法[M].科學出版社，2002.

[5] Milan Sonka， Vaclav Hlavac， Roger Boyle. Image Processing，

Analysis， and Machine Vision， Second Edition[M]. American： Thomson Learning Publishing Company，1999.

[6] Shi Ce. A discussion of a fast algorithm for boundary tracing[J].

Mini-Micro Systems，2000.21（6）：641-645

[7] 章晉毓.圖像處理與分析[M].清華大學出版社，1999.

[8] 孫即祥.圖像分析[M].科學出版社，2005.