楊延竹，袁秀泰，韓阜益

（1.東華大學(xué) 機(jī)械工程學(xué)院，上海 201620；2.東華大學(xué) 資產(chǎn)管理處，上海 201620）

1 引言

在對(duì)圖像進(jìn)行矢量化的過(guò)程中，對(duì)于簡(jiǎn)單圖形目前多采用若干折線段進(jìn)行擬合的方式，但針對(duì)復(fù)雜圖形，如存在圓弧，或復(fù)雜的非圓曲線等，用直線對(duì)曲線進(jìn)行擬合只能大致反映曲線的方向，不能客觀地反映曲線的特征，而且直線擬合形狀精度不高，不能很好的反應(yīng)輪廓特征，在擬合時(shí)如果曲線局部曲率較大，則會(huì)造成該部分直線段較多而短，造成機(jī)器手頻繁地啟動(dòng)和停止，影響切割效率。

針對(duì)上述問(wèn)題，很多研究人員將直線擬合與圓弧擬合相結(jié)合，進(jìn)行了充分研究并且收獲了一定成果。采用混合圓弧—直線逼近法逼近原始輪廓的方法，用樣條曲線擬合輪廓曲線，用圓弧—直線逼近法逼近擬合的曲線，并重新離散化機(jī)器手加工點(diǎn)，減少了機(jī)器手走刀數(shù)，提高了加工效率[1]。不過(guò)這種方法只適合一條曲線，對(duì)于存在斷點(diǎn)的連續(xù)的多條曲線則不適用。還有基于遺傳算法的相切圓弧逼近曲線算法[2]；使用雙圓弧擬合非圓曲線的算法[3]。然而這兩種算法都比較復(fù)雜，實(shí)際應(yīng)用效果較差。還可以利用垂直平分線求交法對(duì)曲線進(jìn)行圓弧擬合，即利用圓內(nèi)接多邊形的任意一條線段都通過(guò)圓心的原理，將滿足圓弧擬合條件的折線段進(jìn)行圓弧擬合[4-5]。采用最小二乘法對(duì)圓弧進(jìn)行擬合的算法[6-7]，利用這種方法得到的圓弧，是采樣點(diǎn)的最優(yōu)解，即最佳逼近圓。

上述方法都可以得到逼近原始輪廓的最佳圓弧曲線，但是原始輪廓的起始點(diǎn)和終止點(diǎn)很有可能不會(huì)落在擬合的圓弧曲線上，造成現(xiàn)象，如圖1所示。即擬合后的兩段相鄰的圓弧或圓弧與直線段之間會(huì)出現(xiàn)交叉、沒(méi)有交點(diǎn)等狀況，造成機(jī)械手在跟蹤識(shí)別完第一條圓弧曲線后，找不到下一段圓弧或者直線的起點(diǎn)，導(dǎo)致機(jī)器手誤判或者丟步，無(wú)法完成后續(xù)的切割。

圖1 交叉和分離現(xiàn)象Fig.1 Phenomenon of Intersectional and Separated

在前人各種研究成果的前提下，結(jié)合實(shí)際情況，在最小二乘法的基礎(chǔ)上，對(duì)擬合的圓弧進(jìn)行了微小的平移和改動(dòng)，保證圓弧每段圓弧的起始點(diǎn)和終止點(diǎn)都落在擬合后的圓弧上。這樣既對(duì)原始輪廓有了很好的保形，保證了加工精度，使輪廓更加平滑，也使機(jī)器手能夠連續(xù)工作，不會(huì)出現(xiàn)誤判或者丟刀等現(xiàn)象，提高了加工效率。

2 圓弧擬合算法

在進(jìn)行圓弧擬合前，首先要對(duì)折線段進(jìn)行判斷其是否符合圓弧特征。因此對(duì)完成直線擬合的圖像，搜索其連續(xù)的折線段，判斷出符合圓弧擬合條件的折線段序列，將符合條件的折線段進(jìn)行圓弧擬合。

2.1 圓弧搜索

對(duì)于線條輪廓圖像，判斷連續(xù)的直線段能否可以構(gòu)成一段圓弧，一般遵循如下規(guī)則[8]：

（1）兩條相鄰的折線段的夾角要在規(guī)定的范圍之內(nèi)。這是因?yàn)椋菏紫龋搜墼谟^察一副圖片時(shí)，對(duì)夾角小于90°的部分最容易發(fā)現(xiàn)，因此具有該特征的部分不能被擬合為圓弧。另外，夾角越大的兩條折線段，被擬合的圓弧和實(shí)際圖形越匹配。

（2）按照同一矢量化方式，獲得的圓內(nèi)接多邊形應(yīng)該近似為等邊多邊形或其中連續(xù)的幾條邊，因此，各折線段的長(zhǎng)度近似，各夾角近似相等。

不過(guò)，如果只根據(jù)上述兩條規(guī)則，不能判斷出折線段序列是否符合圓弧條件，因此，還需要引用其他條件加以限制。

圖2 弧長(zhǎng)近似法搜索圓弧Fig.2 Approximation Method of Arc Length Search Arc

利用弧長(zhǎng)近似法搜索圓弧[5，9]，如圖 2 所示。H1，H2，H3是擬合圓 O 中三條連續(xù)的折線段，H1、H2的夾角是 α1，H2、H3之間的夾角是α2。設(shè)HAC、HBD分別是AC、BD間的距離，由余弦定理可得：

角度較小情況下，弦長(zhǎng)與弧長(zhǎng)近似相等，可知：

通過(guò)該規(guī)則，可以求出每?jī)蓷l相鄰直線段對(duì)應(yīng)的半徑R。若求出的半徑與之前求得的半徑之差超過(guò)規(guī)定的范圍內(nèi)，就認(rèn)為該直線段不屬于該段圓弧，若在允許范圍內(nèi)，則認(rèn)為新的折線段屬于該圓弧，繼續(xù)判斷下一折線段是否屬于該圓弧。

2.2 圓弧擬合算法

通過(guò)上述算法對(duì)折線段實(shí)現(xiàn)圓弧搜索，將符合圓弧擬合條件的折線段進(jìn)行圓弧擬合。目前比較典型的圓弧擬合算法有利用垂直平分線求交法[10]和最小二乘圓擬合算法。利用垂直平分線求交法擬合圓弧的原理是從識(shí)別出的可以擬合為圓弧段的折線段中選一條為母線段，作其垂直平分線，再與其他折線段的垂直平分線求交點(diǎn)，獲得交點(diǎn)的最遠(yuǎn)點(diǎn)PF和最近點(diǎn)PC，設(shè)定一矩形區(qū)域，以PFPC兩點(diǎn)距離為矩形的高，以母線段為矩形的寬。計(jì)算該區(qū)域內(nèi)每個(gè)坐標(biāo)點(diǎn)到每個(gè)頂點(diǎn)的距離（即圓的近似半徑），同時(shí)計(jì)算半徑的平均值以及均方差。最后取使均方差最小的坐標(biāo)點(diǎn)為該圓弧段半徑，所對(duì)應(yīng)的平均半徑為圓弧半徑。

最小二乘法是經(jīng)典的數(shù)學(xué)優(yōu)化算法，通過(guò)最小化誤差的平方和找到一組數(shù)據(jù)的最佳函數(shù)匹配。利用最小二乘法對(duì)圓弧進(jìn)行擬合的核心思想是：獲取可以擬合為圓弧的折線段頂點(diǎn)坐標(biāo)數(shù)據(jù)，根據(jù)誤差平方和最小化原則，找出這些數(shù)據(jù)的最佳函數(shù)匹配，即最佳擬合圓。其數(shù)學(xué)原理為：給定一組圓弧坐標(biāo)點(diǎn)（xi，yi）（i=1，2，…n），已知圓曲線方程：

圓弧坐標(biāo)點(diǎn)（xi，yi）到圓心的距離為：

點(diǎn)（xi，yi）到圓心的距離的平方與半徑的平方求差：

通過(guò)求δi的平方和的極小值可以求得待定系數(shù)a，b，c，從而求出圓弧的圓心坐標(biāo)及半徑的最優(yōu)解，使該函數(shù)的誤差平方和最小。

上述兩種擬合方法從不同角度實(shí)現(xiàn)了圓弧的擬合，都具有一定的實(shí)用性。但這兩種方法都有其局限性和各自的缺陷。利用垂直平分線求交法中對(duì)母線段的選擇非常關(guān)鍵，而且由于要對(duì)區(qū)域內(nèi)的所有坐標(biāo)點(diǎn)進(jìn)行分析，計(jì)算量較大。兩種方法雖然能計(jì)算出圓弧的圓心與半徑，但都只能擬合出圓而非圓弧，由于擬合圓為該圓弧段坐標(biāo)點(diǎn)的最優(yōu)解，因此折線段的起始點(diǎn)和終止點(diǎn)很有可能不會(huì)落在擬合的圓上，這將導(dǎo)致機(jī)器手無(wú)法找到起始點(diǎn)而無(wú)法運(yùn)行或者出現(xiàn)丟刀等現(xiàn)象。綜合上述結(jié)論，考慮實(shí)際加工要求，在最小二乘法擬合圓的基礎(chǔ)上，對(duì)擬合的圓弧或者圓進(jìn)行了微小的平移和改動(dòng)，使其能夠在滿足切割要求的前提下，有效地解決上述問(wèn)題。

3 改進(jìn)的最小二乘圓弧擬合算法

為使后續(xù)的機(jī)器手軌跡行程更加簡(jiǎn)單高效，便于路徑規(guī)劃，保證機(jī)器手在運(yùn)行時(shí)連續(xù)而不出現(xiàn)間斷。在圓弧擬合時(shí)，應(yīng)保證待擬合折線段的起始點(diǎn)和終止點(diǎn)在擬合的圓弧上，即圓弧的端點(diǎn)確定。針對(duì)這一約束性要求，改進(jìn)方法的基本思路是：在滿足機(jī)械手加工精度要求的前提下，從機(jī)械手的實(shí)際切割工藝出發(fā)，保證待擬合為圓弧的折線段的起始點(diǎn)和終止點(diǎn)落在圓弧上為約束條件，約束最小二乘圓弧的擬合，保證擬合出的圖形連續(xù)不會(huì)出現(xiàn)間斷或交叉。

首先，用經(jīng)典最小二乘法求出待擬合圓弧的半徑R和圓心O（x，y），具體算法前面已經(jīng)說(shuō)明，在此不再贅述。要使兩端點(diǎn)落在擬合圓弧上，即要求兩端點(diǎn)到圓心的距離為半徑，設(shè)起始點(diǎn)為P1，終止點(diǎn)為P2，根據(jù)圓心到圓弧上的任一點(diǎn)的距離都為半徑的原理，我們假設(shè)P1，P2在擬合的圓弧上，連接兩端點(diǎn)P1P2，作其垂直平分線L，以P1（P2）為圓心，R為半徑作圓交垂直平分線L于O1，O2兩點(diǎn)。比較O1，O2兩點(diǎn)到圓心O的距離，判定距離較近的一點(diǎn)為新的圓心O′。可以看出，改進(jìn)的算法保有了經(jīng)典最小二乘法擬合出的半徑R，而對(duì)圓心的位置進(jìn)行了適當(dāng)?shù)母淖?，即將整個(gè)圓進(jìn)行了微小的平移，平移的距離一般不會(huì)超過(guò)2個(gè)像素，反應(yīng)到實(shí)際中不會(huì)超過(guò)1mm，在精度要求并不高的加工生產(chǎn)中，這類誤差完全在允許范圍內(nèi)，但這種方法保證了圓弧的端點(diǎn)落在擬合的圓弧上。

在對(duì)圓弧進(jìn)行擬合時(shí)，還要確定圓弧端點(diǎn)與圓心的關(guān)系。通過(guò)上述算法求得擬合圓弧的圓心坐標(biāo)及半徑，且圓弧端點(diǎn)坐標(biāo)已知，圓心及端點(diǎn)坐標(biāo)是二值圖像中的像素坐標(biāo)，也是絕對(duì)坐標(biāo)。通過(guò)絕對(duì)坐標(biāo)求圓心和端點(diǎn)的相對(duì)坐標(biāo)關(guān)系，以圓心O為原點(diǎn)，像素坐標(biāo)的x方向?yàn)樾碌淖鴺?biāo)系的x方向，像素坐標(biāo)的y方向?yàn)樾碌淖鴺?biāo)系的y方向建立直角坐標(biāo)系，以x正半軸為始邊，沿逆時(shí)針?lè)较蛐D(zhuǎn)，判斷向量O′P1，O′P2與x正半軸的夾角，通過(guò)這種方式，確定兩端點(diǎn)的相對(duì)方位，實(shí)現(xiàn)對(duì)圓弧的擬合。

僅確定圓弧端點(diǎn)的相對(duì)方位不能實(shí)現(xiàn)圓弧的正確擬合，還要知道圓弧的旋轉(zhuǎn)方向，有的圓弧是按照順時(shí)針?lè)较驍M合，而有的是按照逆時(shí)針?lè)较驍M合。正確的擬合方式應(yīng)該是從圓弧起始點(diǎn)按照逆時(shí)針旋轉(zhuǎn)進(jìn)行擬合，在沒(méi)有規(guī)定其旋轉(zhuǎn)方向的情況下，就有可能出現(xiàn)其沿順時(shí)針?lè)较驍M合，導(dǎo)致擬合錯(cuò)誤，如圖3所示。

圖3 按照不同旋轉(zhuǎn)方向擬合的圓弧Fig.3 Different Direction of Rotation of Arc Fitting

對(duì)折線段進(jìn)行圓弧擬合至少需要兩段及以上的連續(xù)折線段，即至少3個(gè)以上的有序坐標(biāo)點(diǎn)，在判斷圓弧的旋轉(zhuǎn)方向時(shí)，將第二個(gè)坐標(biāo)點(diǎn)S作為參考對(duì)象。同樣，用確定端點(diǎn)方位的方法確定點(diǎn)S的方位，如圖4所示。比較∠P1O′X和∠SO′X，若∠P1O′X＜∠SO′X，則令圓弧沿逆時(shí)針?lè)较蛐D(zhuǎn)，若∠P1O′X＞∠SO′X，則令圓弧沿順時(shí)針?lè)较蛐D(zhuǎn)。

圖4 圓弧旋轉(zhuǎn)方向Fig.4 Direction of Arc Rotation

但有時(shí)還會(huì)遇到，如圖5所示。很明顯，圓弧應(yīng)從逆時(shí)針?lè)较驍M合，但此時(shí)∠P1O′X＞∠SO′X，按照上述方法，其將按照順時(shí)針?lè)较驍M合，導(dǎo)致擬合錯(cuò)誤。因此，在擬合時(shí)，將起始點(diǎn)P1，第二個(gè)坐標(biāo)點(diǎn)S，終止點(diǎn)P2三點(diǎn)進(jìn)行比較。

圖5 錯(cuò)誤擬合Fig.5 Error of Fitting

當(dāng)∠P2O′X 介于∠P1O′X 和∠SO′X 之間時(shí)，即 min（∠P1O′X，∠SO′X）＜∠P2O′X＜max（∠P1O′X，∠SO′X），此時(shí)再按照上述分析方法確定正確的擬合方向。

當(dāng)∠P2O′X＜min（∠P1O′X，∠SO′X）或者∠P2O′X＞max（∠P1O′X，∠SO′X）時(shí)，令

min′（∠P1O′X，∠SO′X）=min（∠P1O′X，∠SO′X）+2π，同樣再按照上面的分析方法進(jìn)行分析比較，確定擬合方向。

通過(guò)此種方法，包含了所有可能出現(xiàn)的情況，實(shí)現(xiàn)圓弧的正確擬合。

4 實(shí)驗(yàn)對(duì)比分析

分別采用經(jīng)典最小二乘法與提出的方法擬合圓弧，如圖6所示（a線為經(jīng)典最小二乘法擬合結(jié)果，b線為改進(jìn)的算法擬合結(jié)果），相對(duì)于經(jīng)典最小二乘法，通過(guò)改進(jìn)的算法發(fā)生了微小的移動(dòng)，但保證了圓弧的端點(diǎn)落在圓弧上。

圖6 兩種不同算法擬合效果圖Fig.6 Two Different Fitting Rendering Algorithm

在多段連續(xù)的圓弧上，經(jīng)典最小二乘法在兩段圓弧相接處會(huì)出現(xiàn)間斷以及交叉的現(xiàn)象，而通過(guò)這里的方法解決了這一問(wèn)題，如圖7所示。

圖7 多段連續(xù)圓弧擬合結(jié)果Fig.7 Multistage Continuous Arc Fitting Results

5 結(jié)論

在經(jīng)典最小二乘法擬合圓的基礎(chǔ)上，針對(duì)機(jī)器手實(shí)際運(yùn)動(dòng)特點(diǎn)，對(duì)擬合的圓弧進(jìn)行了微小的改動(dòng)或平移，保證可以擬合為圓弧折線段序列中的第一條折線段的起點(diǎn)和最后一條折線段的終點(diǎn)落在擬合后基于圓心約束最小二乘圓擬合的短圓弧測(cè)量的圓弧上。與經(jīng)典的最小二乘法相比，這里的方法并沒(méi)有對(duì)圓弧進(jìn)行巨大的改動(dòng)，使其在誤差允許范圍內(nèi)，對(duì)原始圖案實(shí)現(xiàn)了高度的保形，擬合后的輪廓更加平滑。使機(jī)器手能夠連續(xù)跟蹤識(shí)別而不出現(xiàn)間斷或者丟刀現(xiàn)象，有效地提高了切割效率。