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

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

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

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

1 邊界鏈碼表示

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

圖1 Freeman八方位鏈編碼

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

1.1 圖像預(yù)處理

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

1.2 邊界鏈碼表示算法描述

通常圖像中的目標(biāo)對(duì)象可分為連通體和非連通體。對(duì)于連通體的邊界鏈碼讀取方法為：從圖像邊界上任一像素點(diǎn)開(kāi)始，沿著圖像的邊界像素點(diǎn)按順時(shí)針?lè)较蚧蚰鏁r(shí)針?lè)较蛩阉?，直到回到起點(diǎn)坐標(biāo)為止。搜索中記錄邊界線上兩兩相鄰像素點(diǎn)間的方向，形成一個(gè)由方向鏈碼組成的有序鏈。同時(shí)記錄下起點(diǎn)坐標(biāo)，這樣圖像的邊界就可以被惟一確定下來(lái)[5-6]。這種由方向鏈碼構(gòu)成的有序鏈為Freeman鏈碼。

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

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

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

顯然，按上述連通體的邊界鏈碼讀取方法，對(duì)于非連通體，起點(diǎn)選擇在首尾兩端點(diǎn)之間的其他任何點(diǎn)，都會(huì)出現(xiàn)這種一條曲線讀出兩條鏈碼的錯(cuò)誤。而起點(diǎn)若選擇首尾兩端點(diǎn)之一，就不會(huì)出現(xiàn)這樣的錯(cuò)誤。圖2中按左側(cè)的首端點(diǎn)（X0，Y0）為起點(diǎn)，則讀取的鏈碼為：{（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的方向?yàn)橹鞣较颍枣湸a值為1、3、5、7的方向?yàn)榇畏较颍?、次方向中各方向?yōu)先級(jí)按碼值遞增而減少。其中主方向優(yōu)先于次方向。從起點(diǎn)處開(kāi)始，按此優(yōu)先級(jí)順序深度搜索邊界。實(shí)驗(yàn)結(jié)果證明，該種方法對(duì)于單像素的邊界，其編碼正確有效。

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

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

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

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

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

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

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

3 實(shí)驗(yàn)結(jié)果及分析

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

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

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

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

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

出現(xiàn)次數(shù)的閾值＼節(jié)點(diǎn)數(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é)束語(yǔ)

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

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

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

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

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

參考文獻(xiàn)：

[1] 劉雄偉，張定華.數(shù)控加工理論及編程技術(shù)[M].機(jī)械工業(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] 劉勇奎.計(jì)算機(jī)圖形學(xué)的基礎(chǔ)算法[M].科學(xué)出版社，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].清華大學(xué)出版社，1999.

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