吳觀茂 陳令剛 王倩倩

摘要：對圓形的識別是機器視覺中最基本和最重要的任務之一，為了準確確定復雜背景圖像中圓的位置，提出了一種將支持向量回歸模型與三點擬合圓聯(lián)合起來的新算法，通過支持向量回歸模型訓練不同類型的圓形樣本，得到超平面方程f（x），以f（x）為中心線，構建一個寬度為2ε的近似圓環(huán)型間隔帶，在此間隔帶上的點都被認為屬于圓形邊界上的點，然后運用三點擬合圓幾何算法計算出圓心和半徑，從而達到識別圓形的目的。實驗結果表明，聯(lián)合算法通過對訓練樣本的學習，能夠在噪聲比較大的背景圖像中得到圓形的邊界信息，從而確定圓的位置，較僅使用某一種圓形識別算法有一定的優(yōu)勢。在以圓形作為定位的機器視覺領域，具有重要的理論研究價值與實踐意義。

關鍵詞：計算機圖象處理；圓形檢測；支持向量回歸；三點擬合圓；機器視覺

中圖分類號：TP181文獻標志碼：A

收稿日期：20170921；修回日期：20180306；責任編輯：李穆

基金項目：國家自然科學基金（61471004）；安徽理工大學研究生創(chuàng)新基金項目（2017CX2045）

第一作者簡介：吳觀茂（1965—），男，安徽歙縣人，副教授，博士，主要從事數(shù)據(jù)庫技術、礦山信息技術方面的研究。

Email：gmwu@ah.edu.cn

吳觀茂，陳令剛，王倩倩.支持向量回歸在圓形檢測中的應用[J].河北科技大學學報，2018，39（2）：99106.

WU Guanmao， CHEN Linggang， WANG Qianqian.Application of support vector regression in circle detection[J].Journal of Hebei University of Science and Technology，2018，39（2）：99106.Application of support vector regression in circle detection

WU Guanmao1， CHEN Linggang1， WANG Qianqian2

（1.School of Computer Science and Engineering， Anhui University of Science and Technology， Huainan， Anhui 232001， China； 2.School of Mathematics and Big Data， Anhui University of Science and Technology， Huainan， Anhui 232001， China）

Abstract：Circle detection is one of the most basic and important tasks in machine vision. In order to accurately determine the circle location in complex background images， a new joint algorithm that combines the model of support vector regression with the threepoint fitting circle detection algorithm is proposed. The different types of circular samples are trained by the support vector regression model in the algorithm. So the hyperplane equation f（x） can be obtained. Taking the f（x） as the center line， one similar circular ring with the width of 2 can be constructed. The points in this interval are considered as the circular boundary points. Then， the center and radius can be calculated based on the threepoint fitting circular geometry algorithm， so as to achieve the purpose of identifying the circle. The experimental results show that the circular boundary information can be obtained from the relatively noisy background images by learning the training samples thereby determining the location of the circle， which has some advantages over using only a certain circular recognition algorithm. In the field of machine vision positioning with circles， this joint algorithm has important theoretical research value and practical significance.

Keywords：computer image processing； circle detection； support vector regression； threepoint fitting circle； machine vision

圓檢測是機器視覺中一項基礎性的研究任務，在工業(yè)制造、交通檢測、虹膜識別、生物醫(yī)藥等領域都有著廣泛的應用[1]。實際場景中，由于光線、圖像采集、遮擋等多種因素的影響，待檢測的目標經(jīng)常出現(xiàn)變異的情況，比如橢圓、空心圓、邊緣斷續(xù)、多圓粘連等，也就是說在復雜背景下的圓檢測依然是一件挑戰(zhàn)性的工作[24]。

河北科技大學學報2018年第2期吳觀茂，等：支持向量回歸在圓形檢測中的應用目前，圓形霍夫變換（circular Hough transform ，CHT）[5]是最常用的圓形識別算法，但是該方法采用一到多的映射計算量龐大，在復雜背景下識別的準確率并不高。為了克服CHT的問題，多年來研究者提出一些替代和改進的算法，如：圓度檢測算法[6]、隨機Hough變換（RHT）[7]、廣義Hough變換等[8]。但是這些算法需要獲得圓形的邊界信息，以確定圓的位置，見圖1、圖2，這種噪聲比較大甚至邊緣出現(xiàn)了斷續(xù)的情況，邊界信息是不易得到的，這就讓其實際應用受到了限制。

圖1源圖像1

Fig.1Source image 1

圖2源圖像2

Fig.2Source image 2

考慮到支持向量回歸在圖像識別、自然語言處理、信息檢索等領域的發(fā)展及應用中起著重要的作用[910]，本文擬使用支持向量回歸模型，通過對圓形樣本的訓練，構建一個寬度為2ε的近似圓環(huán)的間隔帶，落入此間隔帶的樣本點則認為是屬于圓形邊界上的點，最后對間隔帶內(nèi)的點運用三點擬合圓幾何算法確定圓心和半徑。實驗結果表明該方法具有很好的魯棒性和精確度。

1相關算法

1.1支持向量回歸基本原理

支持向量機（support vector machine， SVM）是20世紀90年代中期發(fā)展起來的基于統(tǒng)計學習理論的一種機器學習方法[11]，該方法具有泛化能力強、在小樣本的情況下也能取得良好訓練效果的優(yōu)點，近年來已成功應用于很多領域，比如文字識別、語音處理、人臉檢測等。將SVM用于解決回歸預測時便有了支持向量回歸（support vector regression，SVR）[12]，SVR回歸，就是找到一個回歸平面，讓一個集合的所有數(shù)據(jù)到該平面的距離最近，其思想如下：給定訓練樣本D={（x1，y1），（x2，y2），…，（xi，yi），…，（xm， ym）}，其中每個樣本點由實例與標記組成，實例xi∈X標記yi∈R，X是實例空間，R是輸入空間。希望學得一個類似圖3的回歸函數(shù)線性模型：f（x）=ωTx+b，（1）使得f（x）與實際值y盡可能接近，ω和b是待求解的參數(shù)。但是這樣得到的SVR泛化能力還很弱，只能處理線性的情況，而檢測圓形是一種非線性問題。SVR的做法是選擇一個核函數(shù)Kernel，通過映射函數(shù)Φ將輸入數(shù)據(jù)映射到高維空間，在高維特征空間中構造出最優(yōu)分離超平面f（x），以超平面f（x）為中心線，構建一個寬度為2ε的間隔帶，在此間隔帶中的訓練樣本都是被認為分類正確的。也就是說允許f（x）與實際值y之間有ε的偏差，即當f（x）與y差值的絕對值大于ε時才計算損失，從而解決在原始空間中線性不可分的問題（見圖4）。通過引入核函數(shù)Kernel映射之后，需要學習的回歸模型變?yōu)閒（x）=ωTΦ（x）+b，（2）于是，SVR問題的目標函數(shù)可以表示為minω，b12‖ω‖2+C∑mi=1lε（f（xi）-yi），（3）其中C為正則化常數(shù)，lε是不敏感損失函數(shù)，lε=0，if|z|≤ε；|z|-ε，otherwise。（4） 圖3支持向量回歸示意圖

Fig.3SVR diagram

圖4分割超平面示意圖

Fig.4Partition hyperplane diagram

為了包容一些異常樣本點，引入松弛變量ξi和ξ*i，將式（3）重寫為minω，b12‖ω‖2+C∑mi=1（ξi+ξ*i），s.t.f（xi）-yi≤ε+ξi，yi-f（xi）≤ε+ξ*i，ξi≥0，ξ*i≥0，i=1，2，…，m。 （5）通過引入拉格朗日乘子λi≥0，λ*i≥0，γi≥0，γ*i≥0，建立拉格朗日函數(shù)L（ω，b，ξi，ξ*，λ，λ*，γ，γ*）=

minω，b12‖ω‖2+C∑mi=1（ξi+ξ*i）-∑mi=1λiξi-∑mi=1λ*iξ*i+

∑mi=1γi（f（xi）-yi-ε-ξi）+∑mi=1γ*i（yi-f（xi）-ε-ξ*i），（6）令參數(shù)ω，b，ξi，ξ*i的偏導都等于零，可得L（ω，b，ξi，ξ*，λ，λ*，γ，γ*）的最小值，Lω=ω-∑mi=1（γ*i-γi）Φ（xi）=0， （7）

Lb=∑mi=1（γ*i-γi）=0， （8）

Lξi=C-γi+λi， （9）

Lξ*i=C-γ*i+λ*i，（10）將式（5）—式（8）代入式（4），即可得到SVR的對偶優(yōu)化問題 maxγ，γ* ∑mi=1 yi（γ*i-γi）-ε（γ*i+γi）-

12 ∑mi=1 ∑mj=1（γ*i-γi）（γ*j-γj）Φ（xi）TΦ（xi），

s.t.∑mi=1（γ*i-γi），

0≤γi，γ*i≤C，（11）由此，支持向量機的回歸問題轉(zhuǎn)換成了二次優(yōu)化問題，求解出式（9）的二次優(yōu)化問題，得到數(shù)據(jù)點表示的ω：ω=∑mi=1（γ*i-γi）Φ（xi）， （12）式中γi和γ*i是最小化式（2）的解，將式（12）代入式（2）可求得支持向量機線性回歸函數(shù)f（x）=ωx+b=∑mi=1（γ*i-γi）Φ（xi）TΦ（x）+b=

∑mi=1（γ*i-γi）K（xi，x）+b，（13）式中K（xi，x）=Φ（xi）T，Φ（x）為核函數(shù)。

1.2三點擬合圓算法

三點擬合圓是求解圓心和半徑的幾何算法，該算法隨機取屬于圓形上非共線的3點以確定圓的位置[2]。圓的方程如式（14）所示：

x2+y2+2ax+2by+c=0。（14）

假設選取支持向量機線性回歸函數(shù)f（x）=∑mi=1（γ*i-γi）K（xi，x）+b上的3點為（x1，y1），（x2，y2），（x3，y3），將這3點代入方程（14），得到：

x21+y21+2ax1+2ay1+c=0，x22+y22+2ax2+2ay2+c=0，x23+y23+2ax3+2ay3+c=0。 （15）

運用Cramer法則解此方程組，得到參數(shù)a，b，c：

a=D1/D，b=D2/D，c=D3/D。（16）

式中：

D=2x12y112x22y212x32y31，D1=-（x21+y21）2y11-（x22+y22）2y21-（x23+y23）2y31，

D2=2x1-（x21+y21）12x2-（x22+y22）12x3-（x23+y23）1，D3=2x12y1-（x21+y21）2x22y2-（x22+y22）2x32y3-（x23+y23）。

于是方程（14）可以重新寫為（x+a）2+（y+b）2=a2+b2-c，于是可以得到圓心（x0，y0）和半徑r分別為（-a，-b）和（a2+b2-c）1/2。

2支持向量回歸聯(lián)合三點擬合圓算法原理

2.1聯(lián)合算法原理

本文主要針對圖1、圖2這種噪聲比較大的空心圓的識別，對于圖5中的實心圓，只要運用Canny邊緣檢測算子檢測出實心圓的邊緣（見圖6），便可以使用該算法檢測。支持向量回歸聯(lián)合三點擬合圓算法原理如下：首先選取合適的支持向量回歸模型，通過訓練數(shù)據(jù)訓練該模型，從而在待識別圖像中構建一個寬度為2ε的近似圓環(huán)的間隔帶（見圖4），落入此間隔帶樣本的點構成分割超平面f（x）=∑mi=1（γ*i-γi）K（xi，x）+b，此時使得f（x）=0的數(shù)據(jù)點則認為是屬于圓形邊界上的點，然后對這些點運用三點擬合圓幾何算法確定圓心和半徑。

2.2支持向量回歸核函數(shù)的選擇

該聯(lián)合算法性能的關鍵是支持向量回歸模型的選擇，模型選擇主要包括2方面：1）核函數(shù)類型的選擇；2）確定核函數(shù)類型后相關參數(shù)的選擇。其中核函數(shù)的選擇更加重要，核函數(shù)直接決定了支持向量回歸的最終性能，不同的核函數(shù)可以生成不同的支持向量回歸模型。常用的核函數(shù)有線性核、多項式核、高斯徑向基核（RBF）、Sigmoid核等，其表達式與參數(shù)見表1。

這些核函數(shù)各有其優(yōu)點和適用場合，如何根據(jù)具體的數(shù)據(jù)選擇恰當?shù)暮撕瘮?shù)是支持向量回歸應用領域中的一個難點，遺憾的是核函數(shù)的選擇是一個未解決的問題[1318]。

目前來說，應用最廣泛的是高斯徑向基核（RBF），無論在小樣本還是大樣本、高維還是低維等情況下[15]，缺乏先驗知識時其適用性都是最好的。RBF相比其他核函數(shù)有以下優(yōu)點：1）RBF核函數(shù)可以將一個樣本映射到一個更高維的空間，也就是說如果考慮使用RBF，便就沒有必要考慮線性核函數(shù)；2）與多項式核函數(shù)相比，RBF需要確定的參數(shù)更少，能夠減少數(shù)值的計算困難；3）參數(shù)取某些特定值時，RBF和sigmoid具有相似的性能。

綜合以上分析，本文選定高斯徑向基核（RBF）作為支持向量回歸模型與三點擬合圓聯(lián)合算法的核函數(shù)。

2.3高斯徑向基核（RBF）參數(shù)的選擇

選擇好核函數(shù)之后，便要確定核參數(shù)選擇的方法，基于RBF核的支持向量回歸的性能主要受參數(shù)σ和正則化參數(shù)C的影響。參數(shù)σ是RBF核的唯一參數(shù)，σ不同則樣本向量映射的特征空間也不同，因此參數(shù)σ是影響RBF靈活度的關鍵[15]。正則化參數(shù)C是目標函數(shù)的參數(shù)，是對錯分樣本數(shù)據(jù)偏離值的懲罰系數(shù)，它的作用是調(diào)節(jié)學習機的經(jīng)驗風險和置信范圍的比例，一般來說，訓練樣本集越大，訓練結果對C越不敏感[18]。

選擇RBF參數(shù)通常有如下幾種方法：統(tǒng)計學習理論的VC維學習方法、貝葉斯法（Bayesian）、交叉驗證法（Crossvalidation）等。統(tǒng)計學習理論的VC維學習方法通過使得參數(shù)在VC維的上界最小，來確定模型的參數(shù)；貝葉斯法（Bayesian）主要應用于最小二乘支持向量機（LSSVM）中核函數(shù)的參數(shù)的確定[19]；交叉驗證法為最簡單、最方便的方法，其基本思想是將原始數(shù)據(jù)分成2組，一組作為訓練集，另一組作為驗證集，首先通過選擇幾組不同的（C，σ）對訓練集進行訓練，再利用驗證集來驗證訓練集訓練得到的模型，選擇其中使驗證集中數(shù)據(jù)錯誤最小的那一組（C，σ）作為模型的參數(shù)。在小樣本的情況下，交叉驗證法是較為方便的方法，也是本文所采用的方法。

2.4支持向量回歸聯(lián)合三點擬合圓算法步驟

圓形檢測的步驟如下。

Step1：人為隨機選取測試集圓形邊緣上10組的不共線的3點，使用三點擬合圓的方法分別計算圓心、半徑，精度取小數(shù)點后3位，求其平均值。

Step2：加載訓練樣本，將訓練樣本轉(zhuǎn)換為灰度圖像，并將圖像大小統(tǒng)一調(diào)整為32（寬）*32（高）。樣本中黑色像素標記為正例1，白色像素標記為-1。

Step3：選取一組參數(shù)（C，σ），運用支持向量回歸SVR算法求出訓練樣本的超平面方程

f（x）=∑mi=1（γ*i-γi）K（xi，x）+b，其中K（xi，yj）=exp（-‖xi-yj‖22σ2）。

Step4：將測試集的數(shù)據(jù)點代入f（x）=∑mi=1（γ*i-γi）K（xi，x）+b中，如果f（x）=0，則判斷該點屬于圓形上的點。將屬于圓形上的點存入數(shù)組arg[]，隨機選取arg[]中50組非共線的3點，用三點擬合圓的方法計算每一組的圓心和半徑，精度取小數(shù)點后3位。統(tǒng)計這50組識別圓的結果，概率最大一組數(shù)據(jù)即為該聯(lián)合算法確定的圓心和半徑。

Step5：將識別的圓心與半徑與Step1中手動計算的標準值進行比較，若偏差大于1個像素，則通過交叉驗證法更換下一組參數(shù)（C，σ），重復步驟Step2—Step5。

Step6：得到聯(lián)合算法的參數(shù)（C，σ）之后，重復步驟step4和步驟5識別驗證集。

3實驗仿真及分析

3.1實驗平臺

算法結果均在CPU為Intel（R） Core（TM） i3 M350 ，2.27 GHz，內(nèi)存為8 GB，操作系統(tǒng)為Windows7 旗艦版的宏碁筆記本電腦上運行得到，開發(fā)工具為VS2010+opencv2.49。

3.2實驗仿真

為了驗證支持向量回歸聯(lián)合三點擬合圓算法（聯(lián)合算法）的有效性，對其進行了大量的測試，并引入了模板匹配[2021]、RHT算法、圓度檢測、手動計算作為對照。該聯(lián)合算法實驗是在合成的圖像上進行訓練與檢測，將數(shù)據(jù)分為訓練集圖7—圖14、測試集圖1、驗證集圖15 a）—圖15 d），其中訓練集展示為部分數(shù)據(jù)。測試集用來得到參數(shù)（C，σ），驗證集為檢測的樣本數(shù)據(jù)。各檢測結果如圖15所示，圖15 a）—圖15 d）為源圖像，圖15 a1）—圖15 d1）為聯(lián)合算法識別結果，圖15 a2）—圖15 d2）、圖15 a3）—圖15 d3）、圖15 a4）—圖15 d4）分別為模板匹配、RHT算法、圓度檢測算法的識別結果。

3.3實驗分析

由圖15可知：1）聯(lián)合算法與模板匹配的檢測結果類似，識別出了圖15 a）—圖15 d）所有類型的圓形；2）邊緣比較清晰的實心圓見圖15 a），噪聲比較小的空心圓見圖15 d），各算法均有比較好的識別效果；3）噪聲比較大的見圖15 b）、在圖15 c）中，RHT算法識別的結果偏差較大；4）圓度檢測能夠識別圖15 b）、圖15 c），但對圖15 b）、圖15 c）的識別有所偏差。聯(lián)合算法、模板匹配、RHT算法、圓度檢測和手動計算的圓心與半徑的精度分別記錄在表2中，從表2中記錄結果來看，背景比較復雜的圖15 b）、圖15 c）中，聯(lián)合算法、模板匹配、手動計算的結果最為接近，說明聯(lián)合算法與模板匹配在這幾種算法中識別精度是最好的。但是模板匹配需要選中合適的模板才能匹配出最優(yōu)的位置，也就是每識別一種類型的圖片就需要更換一種模板，且識別精度僅能達到像素級，聯(lián)合算法的識別結果帶有小數(shù)位，能夠達到像素級以下，因此在精度上聯(lián)合算法又優(yōu)于模板匹配。綜上，聯(lián)合算法在模板匹配、RHT算法、圓度檢測算法中為最優(yōu)的。

總體上模板匹配檢測時間最短，RHT算法其次，圓度檢測第三，聯(lián)合算法用時最長。這是由于聯(lián)合算法需要通過核函數(shù)將低維數(shù)據(jù)映射到高維空間，在高維空間中構造訓練數(shù)據(jù)的最優(yōu)分類超平面，增加了時間的開銷。說明該聯(lián)合算法是在犧牲了算法的時間復雜度的基礎上提升了識別圓的精確度。

表3各算法時間消耗對比

Tab.3Executiontime comparison

算法圖像檢測時間/s圖15 a）圖15 b）圖15 c）圖15 d）聯(lián)合算法0.850.740.560.63模板匹配0.130.250.140.12RHT算法0.530.540.280.42圓度檢測0.320.440.410.39

4結語

本文提出了基于支持向量回歸與三點擬合圓聯(lián)合的圓形檢測新算法，該算法通過選擇適當?shù)暮藚?shù)對圓形樣本進行訓練，能夠識別復雜背景下的圓形，使得識別的精度與手動擬合圓的圓心與半徑誤差均在1個像素之內(nèi)。實際工程應用中，同一個程序常常需要識別不同類型的圓形，單純某一種算法識別的效果經(jīng)常受到局限，此聯(lián)合算法通過對樣本的學習來確定圓形的邊界信息，是對圓形物體檢測的一種有益嘗試。該聯(lián)合算法目前只針對源圖像中僅有一個圓形的情況且時間消耗比較大，下一步將繼續(xù)拓展該算法的適用范圍及優(yōu)化該算法的時間復雜度，使其能夠在合理的時間內(nèi)識別出多圓的情形。

參考文獻/References：

[1]于起鋒，陸宏偉，劉肖琳. 基于圖像的精密測量和運動測量[M]. 北京：國防工業(yè)出版社，2002.

[2]CUEVAS E， WARIO F. Automatic multiple circle detection based on artificial immune systems[J]. Expert Systems with Applications An International Journal， 2012， 39（1）：713722.

[3]LAMIROY B， GUEBBAS Y.Robust and precise circular arc detection[J]. Lecture Notes in Computer Science， 2010， 6020：4960.

[4]YUAN B， LIU M. Power Histogram for Circle Detection on Images[M]. Elsevier： Science Inc，2015.

[5]MUAMMAR H， NIXON M. Approaches to extending the Hough transform[J]. Speech and Signal Processing ICASSP， 1989， 3： 15561559.

[6]張之穩(wěn)，宋世軍. 利用圓度進行圓定位方法[J]. 山東大學學報（工學版），2006，36（1）：1922.

ZHANG Zhiwen， SONG Shijun. Circle locating method based on roundness[J]. Journal of Shandong University （Engineering Science）， 2006， 36（1）：1922.

[7]XU L， OJA E， KULTANEN P. A new curve detection method： Randomized Hough transform （RHT）[J]. Pattern Recognition Letters， 1990， 11（5）：331338.

[8]黎自強，騰弘飛. 廣義Hough變換：多個圓的快速隨機檢測[J]. 計算機輔助設計與圖形學學報，2006， 18（1）：2733.

LI Ziqiang， TENG Hongfei. Generalized Hough transform： Fast randomized mu1ticircle detection[J]. Journal of ComputerAided Design & Computer Graphics， 2006， 18（1）： 2733.

[9]王定成， 方廷健， 唐毅. 支持向量機回歸理論與控制的綜述[J]. 模式識別與人工智能， 2003，16（2）：192197.

[10]周志華，機器學習[M]. 北京：清華大學出版社，2016：121140.

[11]SMOLA A J.A tutorial on support vector regression[J]. Statistics & Computing， 2004， 14（3）：199222.

[12]李航， 統(tǒng)計學習方法[M].北京：清華大學出版社，2012：95134.

[13]鄧乃揚，田英杰. 支持向量機——理論、算法與拓展[M]. 北京：科學出版社，2009.

[14]朱樹先， 張仁杰. 支持向量機核函數(shù)選擇的研究[J]. 科學技術與工程， 2008， 8（16）：45134517.

[15]歐陽中， 王育齊， 俞梅洪. 基于不同核函數(shù)的支持向量機的分析與比較[J]. 福建電腦， 2013， 29（10）：1214.

[16]鐘震. 稀疏表示下支持向量機核函數(shù)選擇[D]. 南昌：江西理工大學，2015.

ZHONG Zhen. Support Vector Machine Kernel Function Selection with Sparse Representation[D]. Nanchang：Jiangxi University of Science and Technology，2015.

[17]李海生. 支持向量機回歸算法與應用研究[D]. 廣州：華南理工大學， 2005.

LI Haisheng. Algorithm and Application Research of Support Vector Machine Regression[D]. Guangzhou：South China University of Technology， 2005.

[18]劉明. 支持向量機中Sigmoid核函數(shù)的研究[D]. 西安：西安電子科技大學，2009

LIU Ming. Research on Sigmoid Kernel Function in Support Vector Machines[D]. Xian：Xidian University，2009.

[19]樊曉雪. 最小二乘支持向量機的參數(shù)選擇[D]. 保定：河北大學， 2012.

FAN Xiaoxue. Least Squares Support Vector Machine Parameter Selection[D].Baoding：Hebei University，2012.

[20]劉瑞禎， 于仕琪. opencv教程——基礎篇[M]. 北京：北京航空航天大學出版社，2007.

[21]陳令剛. 基于模板匹配的多圓識別算法[J]. 電腦知識與技術， 2017， 13（24）： 173174.

CHEN Linggang. A algorithm for multiplecircle detection on images using template matching[J]. Computer Knowledge and Technology， 2017， 13（24）： 173174.第39卷第2期河北科技大學學報Vol.39，No.2

2018年4月Journal of Hebei University of Science and TechnologyApr. 2018