一種圖像矢量化中的圓弧擬合方法

楊延竹，袁秀泰，韓阜益

（1.東華大學 機械工程學院，上海 201620；2.東華大學 資產管理處，上海 201620）

1 引言

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

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

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

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

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

2 圓弧擬合算法

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

2.1 圓弧搜索

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

（1）兩條相鄰的折線段的夾角要在規(guī)定的范圍之內。這是因為：首先，人眼在觀察一副圖片時，對夾角小于90°的部分最容易發(fā)現(xiàn)，因此具有該特征的部分不能被擬合為圓弧。另外，夾角越大的兩條折線段，被擬合的圓弧和實際圖形越匹配。

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

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

圖2 弧長近似法搜索圓弧Fig.2 Approximation Method of Arc Length Search Arc

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

角度較小情況下，弦長與弧長近似相等，可知：

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

2.2 圓弧擬合算法

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

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

圓弧坐標點（xi，yi）到圓心的距離為：

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

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

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

3 改進的最小二乘圓弧擬合算法

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

首先，用經典最小二乘法求出待擬合圓弧的半徑R和圓心O（x，y），具體算法前面已經說明，在此不再贅述。要使兩端點落在擬合圓弧上，即要求兩端點到圓心的距離為半徑，設起始點為P1，終止點為P2，根據圓心到圓弧上的任一點的距離都為半徑的原理，我們假設P1，P2在擬合的圓弧上，連接兩端點P1P2，作其垂直平分線L，以P1（P2）為圓心，R為半徑作圓交垂直平分線L于O1，O2兩點。比較O1，O2兩點到圓心O的距離，判定距離較近的一點為新的圓心O′?？梢钥闯觯倪M的算法保有了經典最小二乘法擬合出的半徑R，而對圓心的位置進行了適當?shù)母淖儯磳⒄麄€圓進行了微小的平移，平移的距離一般不會超過2個像素，反應到實際中不會超過1mm，在精度要求并不高的加工生產中，這類誤差完全在允許范圍內，但這種方法保證了圓弧的端點落在擬合的圓弧上。

在對圓弧進行擬合時，還要確定圓弧端點與圓心的關系。通過上述算法求得擬合圓弧的圓心坐標及半徑，且圓弧端點坐標已知，圓心及端點坐標是二值圖像中的像素坐標，也是絕對坐標。通過絕對坐標求圓心和端點的相對坐標關系，以圓心O為原點，像素坐標的x方向為新的坐標系的x方向，像素坐標的y方向為新的坐標系的y方向建立直角坐標系，以x正半軸為始邊，沿逆時針方向旋轉，判斷向量O′P1，O′P2與x正半軸的夾角，通過這種方式，確定兩端點的相對方位，實現(xiàn)對圓弧的擬合。

僅確定圓弧端點的相對方位不能實現(xiàn)圓弧的正確擬合，還要知道圓弧的旋轉方向，有的圓弧是按照順時針方向擬合，而有的是按照逆時針方向擬合。正確的擬合方式應該是從圓弧起始點按照逆時針旋轉進行擬合，在沒有規(guī)定其旋轉方向的情況下，就有可能出現(xiàn)其沿順時針方向擬合，導致擬合錯誤，如圖3所示。

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

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

圖4 圓弧旋轉方向Fig.4 Direction of Arc Rotation

但有時還會遇到，如圖5所示。很明顯，圓弧應從逆時針方向擬合，但此時∠P1O′X＞∠SO′X，按照上述方法，其將按照順時針方向擬合，導致擬合錯誤。因此，在擬合時，將起始點P1，第二個坐標點S，終止點P2三點進行比較。

圖5 錯誤擬合Fig.5 Error of Fitting

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

當∠P2O′X＜min（∠P1O′X，∠SO′X）或者∠P2O′X＞max（∠P1O′X，∠SO′X）時，令

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

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

4 實驗對比分析

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

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

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

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

5 結論

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