支持向量回归在圆形检测中的应用

吴观茂 陈令刚 王倩倩

摘要：對圆形的识别是机器视觉中最基本和最重要的任务之一，为了准确确定复杂背景图像中圆的位置，提出了一种将支持向量回归模型与三点拟合圆联合起来的新算法，通过支持向量回归模型训练不同类型的圆形样本，得到超平面方程f（x），以f（x）为中心线，构建一个宽度为2ε的近似圆环型间隔带，在此间隔带上的点都被认为属于圆形边界上的点，然后运用三点拟合圆几何算法计算出圆心和半径，从而达到识别圆形的目的。实验结果表明，联合算法通过对训练样本的学习，能够在噪声比较大的背景图像中得到圆形的边界信息，从而确定圆的位置，较仅使用某一种圆形识别算法有一定的优势。在以圆形作为定位的机器视觉领域，具有重要的理论研究价值与实践意义。

关键词：计算机图象处理；圆形检测；支持向量回归；三点拟合圆；机器视觉

中图分类号：TP181文献标志码：A

收稿日期：20170921；修回日期：20180306；责任编辑：李穆

基金项目：国家自然科学基金（61471004）；安徽理工大学研究生创新基金项目（2017CX2045）

第一作者简介：吴观茂（1965—），男，安徽歙县人，副教授，博士，主要从事数据库技术、矿山信息技术方面的研究。

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

圆检测是机器视觉中一项基础性的研究任务，在工业制造、交通检测、虹膜识别、生物医药等领域都有着广泛的应用[1]。实际场景中，由于光线、图像采集、遮挡等多种因素的影响，待检测的目标经常出现变异的情况，比如椭圆、空心圆、边缘断续、多圆粘连等，也就是说在复杂背景下的圆检测依然是一件挑战性的工作[24]。

河北科技大学学报2018年第2期吴观茂，等：支持向量回归在圆形检测中的应用目前，圆形霍夫变换（circular Hough transform ，CHT）[5]是最常用的圆形识别算法，但是该方法采用一到多的映射计算量庞大，在复杂背景下识别的准确率并不高。为了克服CHT的问题，多年来研究者提出一些替代和改进的算法，如：圆度检测算法[6]、随机Hough变换（RHT）[7]、广义Hough变换等[8]。但是这些算法需要获得圆形的边界信息，以确定圆的位置，见图1、图2，这种噪声比较大甚至边缘出现了断续的情况，边界信息是不易得到的，这就让其实际应用受到了限制。

图1源图像1

Fig.1Source image 1

图2源图像2

Fig.2Source image 2

考虑到支持向量回归在图像识别、自然语言处理、信息检索等领域的发展及应用中起着重要的作用[910]，本文拟使用支持向量回归模型，通过对圆形样本的训练，构建一个宽度为2ε的近似圆环的间隔带，落入此间隔带的样本点则认为是属于圆形边界上的点，最后对间隔带内的点运用三点拟合圆几何算法确定圆心和半径。实验结果表明该方法具有很好的鲁棒性和精确度。

1相关算法

1.1支持向量回归基本原理

支持向量机（support vector machine， SVM）是20世纪90年代中期发展起来的基于统计学习理论的一种机器学习方法[11]，该方法具有泛化能力强、在小样本的情况下也能取得良好训练效果的优点，近年来已成功应用于很多领域，比如文字识别、语音处理、人脸检测等。将SVM用于解决回归预测时便有了支持向量回归（support vector regression，SVR）[12]，SVR回归，就是找到一个回归平面，让一个集合的所有数据到该平面的距离最近，其思想如下：给定训练样本D={（x1，y1），（x2，y2），…，（xi，yi），…，（xm， ym）}，其中每个样本点由实例与标记组成，实例xi∈X标记yi∈R，X是实例空间，R是输入空间。希望学得一个类似图3的回归函数线性模型：f（x）=ωTx+b，（1）使得f（x）与实际值y尽可能接近，ω和b是待求解的参数。但是这样得到的SVR泛化能力还很弱，只能处理线性的情况，而检测圆形是一种非线性问题。SVR的做法是选择一个核函数Kernel，通过映射函数Φ将输入数据映射到高维空间，在高维特征空间中构造出最优分离超平面f（x），以超平面f（x）为中心线，构建一个宽度为2ε的间隔带，在此间隔带中的训练样本都是被认为分类正确的。也就是说允许f（x）与实际值y之间有ε的偏差，即当f（x）与y差值的绝对值大于ε时才计算损失，从而解决在原始空间中线性不可分的问题（见图4）。通过引入核函数Kernel映射之后，需要学习的回归模型变为f（x）=ωTΦ（x）+b，（2）于是，SVR问题的目标函数可以表示为minω，b12‖ω‖2+C∑mi=1lε（f（xi）-yi），（3）其中C为正则化常数，lε是不敏感损失函数，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，建立拉格朗日函数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）令參数ω，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的对偶优化问题 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）由此，支持向量机的回归问题转换成了二次优化问题，求解出式（9）的二次优化问题，得到数据点表示的ω：ω=∑mi=1（γ*i-γi）Φ（xi）， （12）式中γi和γ*i是最小化式（2）的解，将式（12）代入式（2）可求得支持向量机线性回归函数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）为核函数。

1.2三点拟合圆算法

三点拟合圆是求解圆心和半径的几何算法，该算法随机取属于圆形上非共线的3点以确定圆的位置[2]。圆的方程如式（14）所示：

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

假设选取支持向量机线性回归函数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法则解此方程组，得到参数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支持向量回归联合三点拟合圆算法原理

2.1联合算法原理

本文主要针对图1、图2这种噪声比较大的空心圆的识别，对于图5中的实心圆，只要运用Canny边缘检测算子检测出实心圆的边缘（见图6），便可以使用该算法检测。支持向量回归联合三点拟合圆算法原理如下：首先选取合适的支持向量回归模型，通过训练数据训练该模型，从而在待识别图像中构建一个宽度为2ε的近似圆环的间隔带（见图4），落入此间隔带样本的点构成分割超平面f（x）=∑mi=1（γ*i-γi）K（xi，x）+b，此时使得f（x）=0的数据点则认为是属于圆形边界上的点，然后对这些点运用三点拟合圆几何算法确定圆心和半径。

2.2支持向量回归核函数的选择

该联合算法性能的关键是支持向量回归模型的选择，模型选择主要包括2方面：1）核函数类型的选择；2）确定核函数类型后相关参数的选择。其中核函数的选择更加重要，核函数直接决定了支持向量回归的最终性能，不同的核函数可以生成不同的支持向量回归模型。常用的核函数有线性核、多项式核、高斯径向基核（RBF）、Sigmoid核等，其表达式与参数见表1。

这些核函数各有其优点和适用场合，如何根据具体的数据选择恰当的核函数是支持向量回归应用领域中的一个难点，遗憾的是核函数的选择是一个未解决的问题[1318]。

目前来说，应用最广泛的是高斯径向基核（RBF），无论在小样本还是大样本、高维还是低维等情况下[15]，缺乏先验知识时其适用性都是最好的。RBF相比其他核函数有以下优点：1）RBF核函数可以将一个样本映射到一个更高维的空间，也就是说如果考虑使用RBF，便就没有必要考虑线性核函数；2）与多项式核函数相比，RBF需要确定的参数更少，能够减少数值的计算困难；3）参数取某些特定值时，RBF和sigmoid具有相似的性能。

综合以上分析，本文选定高斯径向基核（RBF）作为支持向量回归模型与三点拟合圆联合算法的核函数。

2.3高斯径向基核（RBF）参数的选择

选择好核函数之后，便要确定核参数选择的方法，基于RBF核的支持向量回归的性能主要受参数σ和正则化参数C的影响。参数σ是RBF核的唯一参数，σ不同则样本向量映射的特征空间也不同，因此参数σ是影响RBF灵活度的关键[15]。正则化参数C是目标函数的参数，是对错分样本数据偏离值的惩罚系数，它的作用是调节学习机的经验风险和置信范围的比例，一般来说，训练样本集越大，训练结果对C越不敏感[18]。

选择RBF参数通常有如下几种方法：统计学习理论的VC维学习方法、贝叶斯法（Bayesian）、交叉验证法（Crossvalidation）等。统计学习理论的VC维学习方法通过使得参数在VC维的上界最小，来确定模型的参数；贝叶斯法（Bayesian）主要应用于最小二乘支持向量机（LSSVM）中核函数的参数的确定[19]；交叉验证法为最简单、最方便的方法，其基本思想是将原始数据分成2组，一组作为训练集，另一组作为验证集，首先通过选择几组不同的（C，σ）对训练集进行训练，再利用验证集来验证训练集训练得到的模型，选择其中使验证集中数据错误最小的那一组（C，σ）作为模型的参数。在小样本的情况下，交叉验证法是较为方便的方法，也是本文所采用的方法。

2.4支持向量回归联合三点拟合圆算法步骤

圆形检测的步骤如下。

Step1：人为随机选取测试集圆形边缘上10组的不共线的3点，使用三点拟合圆的方法分别计算圆心、半径，精度取小数点后3位，求其平均值。

Step2：加载训练样本，将训练样本转换为灰度图像，并将图像大小统一调整为32（宽）*32（高）。样本中黑色像素标记为正例1，白色像素标记为-1。

Step3：选取一组参数（C，σ），运用支持向量回归SVR算法求出训练样本的超平面方程

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

Step4：将测试集的数据点代入f（x）=∑mi=1（γ*i-γi）K（xi，x）+b中，如果f（x）=0，则判断该点属于圆形上的点。将属于圆形上的点存入数组arg[]，随机选取arg[]中50组非共线的3点，用三点拟合圆的方法计算每一组的圆心和半径，精度取小数点后3位。统计这50组识别圆的结果，概率最大一组数据即为该联合算法确定的圆心和半径。

Step5：将识别的圆心与半径与Step1中手动计算的标准值进行比较，若偏差大于1个像素，则通过交叉验证法更换下一组参数（C，σ），重复步骤Step2—Step5。

Step6：得到联合算法的参数（C，σ）之后，重复步骤step4和步骤5识别验证集。

3实验仿真及分析

3.1实验平台

算法结果均在CPU为Intel（R） Core（TM） i3 M350 ，2.27 GHz，内存为8 GB，操作系統为Windows7 旗舰版的宏碁笔记本电脑上运行得到，开发工具为VS2010+opencv2.49。

3.2实验仿真

为了验证支持向量回归联合三点拟合圆算法（联合算法）的有效性，对其进行了大量的测试，并引入了模板匹配[2021]、RHT算法、圆度检测、手动计算作为对照。该联合算法实验是在合成的图像上进行训练与检测，将数据分为训练集图7—图14、测试集图1、验证集图15 a）—图15 d），其中训练集展示为部分数据。测试集用来得到参数（C，σ），验证集为检测的样本数据。各检测结果如图15所示，图15 a）—图15 d）为源图像，图15 a1）—图15 d1）为联合算法识别结果，图15 a2）—图15 d2）、图15 a3）—图15 d3）、图15 a4）—图15 d4）分别为模板匹配、RHT算法、圆度检测算法的识别结果。

3.3实验分析

由图15可知：1）联合算法与模板匹配的检测结果类似，识别出了图15 a）—图15 d）所有类型的圆形；2）边缘比较清晰的实心圆见图15 a），噪声比较小的空心圆见图15 d），各算法均有比较好的识别效果；3）噪声比较大的见图15 b）、在图15 c）中，RHT算法识别的结果偏差较大；4）圆度检测能够识别图15 b）、图15 c），但对图15 b）、图15 c）的识别有所偏差。联合算法、模板匹配、RHT算法、圆度检测和手动计算的圆心与半径的精度分别记录在表2中，从表2中记录结果来看，背景比较复杂的图15 b）、图15 c）中，联合算法、模板匹配、手动计算的结果最为接近，说明联合算法与模板匹配在这几种算法中识别精度是最好的。但是模板匹配需要选中合适的模板才能匹配出最优的位置，也就是每识别一种类型的图片就需要更换一种模板，且识别精度仅能达到像素级，联合算法的识别结果带有小数位，能够达到像素级以下，因此在精度上联合算法又优于模板匹配。综上，联合算法在模板匹配、RHT算法、圆度检测算法中为最优的。

总体上模板匹配检测时间最短，RHT算法其次，圆度检测第三，联合算法用时最长。这是由于联合算法需要通过核函数将低维数据映射到高维空间，在高维空间中构造训练数据的最优分类超平面，增加了时间的开销。说明该联合算法是在牺牲了算法的时间复杂度的基础上提升了识别圆的精确度。

表3各算法时间消耗对比

Tab.3Executiontime comparison

算法图像检测时间/s图15 a）图15 b）图15 c）图15 d）联合算法0.850.740.560.63模板匹配0.130.250.140.12RHT算法0.530.540.280.42圆度检测0.320.440.410.39

4结语

本文提出了基于支持向量回归与三点拟合圆联合的圆形检测新算法，该算法通过选择适当的核参数对圆形样本进行训练，能够识别复杂背景下的圆形，使得识别的精度与手动拟合圆的圆心与半径误差均在1个像素之内。实际工程应用中，同一个程序常常需要识别不同类型的圆形，单纯某一种算法识别的效果经常受到局限，此联合算法通过对样本的学习来确定圆形的边界信息，是对圆形物体检测的一种有益尝试。该联合算法目前只针对源图像中仅有一个圆形的情况且时间消耗比较大，下一步将继续拓展该算法的适用范围及优化该算法的时间复杂度，使其能够在合理的时间内识别出多圆的情形。

参考文献/References：

[1]于起锋，陆宏伟，刘肖琳. 基于图像的精密测量和运动测量[M]. 北京：国防工业出版社，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]张之稳，宋世军. 利用圆度进行圆定位方法[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]李航， 统计学习方法[M].北京：清华大学出版社，2012：95134.

[13]邓乃扬，田英杰. 支持向量机——理论、算法与拓展[M]. 北京：科学出版社，2009.

[14]朱树先， 张仁杰. 支持向量机核函数选择的研究[J]. 科学技术与工程， 2008， 8（16）：45134517.

[15]欧阳中， 王育齐， 俞梅洪. 基于不同核函数的支持向量机的分析与比较[J]. 福建电脑， 2013， 29（10）：1214.

[16]钟震. 稀疏表示下支持向量机核函数选择[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核函数的研究[D]. 西安：西安电子科技大学，2009

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

[19]樊晓雪. 最小二乘支持向量机的参数选择[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