英语原文共 19 页，剩余内容已隐藏，支付完成后下载完整资料
基于中心聚类的多椭圆拟合
作者：Tomislav Marosevi and Rudolf Scitovski
摘要：本文讨论了基于给定样本数据点集的多椭圆拟合问题。假设所有的数据点都来自k个需要拟合的椭圆，针对聚类是椭圆形状的问题，可以通过基于中心的聚类算法来解决。如果在每个簇中引入马氏距离函数，则该簇中心可由相应的马氏圆心来表示，并采用代数方法判断每一个aisin;R2点到马氏圆的距离。本文验证了著名的k-means算法可以被用来计算马氏圆心的最优解问题，并采用了几个例子来验证了所提出的算法的可行性。
关键词:多椭圆拟合，中心聚类，代数判据，马氏距离
1、简介
本文考虑了基于给定数据点集的多椭圆拟合问题。这一问题在地质(岩石中的应变估计[25])、地震调查[19]、医学[3,6]、机器人技术、对象检测等图像处理应用[12]领域通常有所体现。
假设数据集A = {a i = (x i ,y i ) isin; R 2 : i = 1,...,m} sub; R 2拟合出k个椭圆的问题。本文提供了解决这个问题的各种方法，最常见的是基于代数距离最小化[9,12]、最小二乘距离最小化[1,21]、基于圆弧的方法[15]或模糊聚类技术[2,6]。另一方面，也可以利用基于霍夫变换的方法来解决数字图像[12]中的椭圆检测问题。
为了解决聚类拟合这一问题，本文将采用基于中心的聚类方法[10,11,22]。将样本划分为k个非空的不相交的子集,这样，该分区将表示为Pi;(A)= {pi;1,。,pi;k }，分区Pi;的元素在里被称为集群，这些分区的集合通过P(A;k)表示，上述理念被称为数据聚类。数据聚类在医学、生物学、设施选址问题、模式识别、信息检索、地球气候、心理学、城市排名等广泛应用中都很重要[3、4、8、14、17]。
为了使用中心的聚类方法,首先必须定义适当的特征椭圆来拟合每个集群的pi;jisin;Pi;(A)。最常用的方法是解决其全局优化问题求解。
其中D(a, E)为点a到椭圆E的距离(在[13,18]中给出了圆中心的类似定义)。
这样马氏距离看起来就与函数times;→R (见[2、3、21])类似,
其中，Sisin;R2times;2是一个正对称矩阵,并且每个椭圆可以被定义为一个马氏循环(即一个马氏圆)
（3）式是以cisin;R2为中心,半径r gt; 0的马氏圆组成的集合。
马氏圆(即椭圆）可以被视为一个转换的圆，其中矩阵S决定主轴和小轴的长度，以及椭圆[3]的方向。
此外,为了构建一个k - means算法寻找局部最优分区的马氏圆圆心,从aisin;R2的任意一点到椭圆E(c,r,S)的距离也应该被定义。为此，应用[2]中的定理。
定理1。让“·”作为Rn的标准,让B(c,r)= { xisin;Rn:minus;c = r,r gt; 0 }的封闭球的半径r集中体现在c上。然后以“·”来衡量最短的距离,,通过|||a-c||minus;r|得到点aisin;Rn到球B(c,r)的距离。
在应用定理1的 LAD-distance中，从任意一点aisin;R2到马氏圆 E(c,r,S)的距离可以被定义为
具体来说,从点aisin;R2到马氏圆E(c r;S)代数距离可定义为
这在实际应用中经常用到(参见[9,20])，因此本文采用了代数距离。
如果每个集群pi;jisin;Pi;与马氏圆心 Ej可以通过公式(1)计算得出，那么可以通过GOP来解决集合A的最优分区的问题(见, [2, 21, 23])
相反，对于给定的一组不同的椭圆E1，hellip;Eksub;R2,那么根据最小距离原则,分区Pi;= {pi;1。。。,pi;k }的设置可以通过以下方式来定义:
因此，找到集合A的最优解问题可以归结为以下优化问题
(5)和(7)的解与[21]相同。
一般来说，函数F可以有大量的自变量，不需要是可积或可微的，但是通常有几个局部和全局的最小值。因此，这就变成了一个复杂的GOP问题
第2节描述了我们所了解的k-means算法的修改。在2.1小节中引入自适应的马氏距离函数，在2.2小节中给出k-means算法计算局部最优分区的优越性，以及可以确定基于相应的马氏圆心的簇。第2.2.1小节考虑对所提出的算法构造一个良好的初始值。最后，在第3节中给出了几个例子。
2、修改的k-means算法
众所周知，k-means算法通常用于搜索集合a的K部分的划分的局部最优解。
步骤A:对于每一组相互不同的中心c1，hellip;c kisin;R n，并且基于最小距离原则，设计一个分为k份不相交的集群pi;1,hellip;,pi;k。
步骤B:考虑到分区Pi;= {pi;1,hellip;pi;k }的设定,可以定义相应的聚类中心。
k-means算法严格地依赖于中心或初始分区的初始近似值。设计一个优秀的初始值，利用该算法可以提供一个可接受的解。
2.1、利用函数定义马氏距离
修改k - means算法,利用自适应的马氏距离函数dj M:R2times;R2→R 为每个集群pi;j定义(见[2、3、14])
此时：
协方差矩阵是一个规范化的因素，它鱼cj的重心以及集群的pi;j和detSj有很重要关联。协方差矩阵Sj通常是一个正对称矩阵。只有在特殊情况下，当椭圆退化为直线或点(即Sj的一个或两个特征值接近于零)时，它才几乎是奇异的。
由[2,21]可以看出
在特定情况下，如果Ej(cj, rj;Sj)是一个马氏圆的集群pi;j，则任意一点aisin;A到马氏圆Ej(cj,rj）的代数距离可以由下式得出
2.2、马氏k - means算法
为了解决多椭圆拟合问题，本文将前面描述的k-means算法应用于搜索以马氏圆为集群中心的局部最优解。
首先,将任意一点 a isin; A到马氏圆心的距离被定义为代数距离(11)。随后,通过步骤B，利用集群的马氏圆心pi;j解决以下GOP问题
其中全部样本点aisin;pi;j到马氏圆Ej(cj,rj;Sj)的代数距离的总和记为Phi;j。
在本文中，相应的自适应k-means算法可以分为AB两个步骤进行描述，并进行迭代。
算法1：(计算离马氏圆心最近的K的算法(KCMC))
步骤A:针对每组相互不同的马氏圆心E1(c1, r1);S1)。Ek(ck,rk;Sk)可以分为k个不相交的非空集集群pi;1,...,pi;k，并通过使用最小距离原则计算pi;j = {isin;:D(a,Ej(cj,rj;Sj)le;D(Es(cs,rs;Ss))、forall;s = 1。， k, s = j}， j = 1，hellip;,k。
步骤B:给定一个分区Pi;= {pi;1,...,pi;k },以及相应的马氏圆Ê1(ĉ1,r̂1;Ŝ1)可以通过下式得出
根据[21,23]以及(5)式得出的目标函数，(7)式得出的权重能够减少算法计算量。这确保了结果包含自适应马氏距离函数(8)的定义中的归一化因子。
如前所述，k-means算法是一种通常提供局部最优分区的方法。然而，如果能找到一个良好的初始逼近，k-means算法就能得到一个全局最优解的满意结果。因此，在第2.2.1节中，我们特别注意寻找尽可能最好的马氏圆心的初始逼近。
为了确定算法1步骤B中的m圆中心，首先必须为每个簇定义合适的初始逼近，即马氏圆心:
由作为中心的一个近似马氏圆心和矩阵(9)是一个近似的协方差矩阵S̄j可以计算出集的质心pi;j。但同时仍然有需要构造一个好的近似半径r̄j。对于给定的c̄j S̄j,通过定义
因此,初始半径的近似j被视为问题的解决方案(14)
然后，我们可以通过这样的方法得到的初始逼近。同时为寻找步骤B中相应的马氏圆心，我们应用了局部优化方法(如Levenberg-Marquardt方法或其他牛顿型方法[7])。
备注1。众所周知(参见[2,23,24])，这种方法有一些缺点。在应用k-means算法时，需要定义初始逼近，即需要先确定A所属的椭圆，然后近似确定这些椭圆。此外，在数据点较少的情况下，协方差矩阵可以是奇异的。
2.2.1、构造一个好的初始近似
假设A是一组数据点，如果存在一些小差错，点可能属于k个椭圆。事实上，假设椭圆的数目和位置是事先不知道的。
当运行算法1 (KCMC)时，首先要估计可能的椭圆的数目和位置。为了做到这一点，必须对数据集进行可视化处理。对于每个椭圆，它的五个参数在视觉上被定义为中心c =(p,q),椭圆半轴长度 a,b,和半轴和x轴的正方向的夹角ϕ。这个椭圆由方程定义
通过马氏距离函数(2)，椭圆(16)以马氏圆的形式表示
当期半径为1时，S是对称正定矩阵。矩阵S的表示相对容易
因此在a b gt; 0时，矩阵S是正定的。在规范化的马氏距离函数中，很容易看出这一点
椭圆(16)的形式表示的马氏圆半径r2 =radic;detS= ab,可以明确表示出相应的矩阵保存。通过这种方法，可以得到很好的m圈中心的初始逼近(即参数p、q、r、S的逼近)。
备注2。在特殊情况下当椭圆长短轴a,b与坐标轴平行,此时角度ϕ= 0,即矩阵(18)成为对角线。此时矩阵S的形式为S = diag(a2, b2)
例1。为了演示如何进行一个椭圆的良好初始逼近，下面的示例如图1所示。数据来自(16)图1的灰色椭圆及其参数:(p,q)=(4.8,4.3),(a,b)=(3.75,1.25),ϕ= 39◦如图1所示。初始逼近(见图1 b红色椭圆)是通过视觉估计椭圆参数:中心c =(5,4),椭圆轴a= 4,b = 1,和角度ϕ= 45◦,随后,最佳椭圆(12)(见图1 c红色椭圆)。表1给出了三个m圈的参数值，即，原始m圆，初始逼近和解。
备注3。根据定理1，基于给定的一组平面数据点的多椭圆拟合问题也可以用其他类似距离的函数来求解。例如如果LAD-distance表示从a点isin;R2的马氏圆E(c r;使用S)(由D1定义(a,E(c, r);S) = | dM (a, c;minus;r |),然后在每个集群pi;j LAD距离由马氏圆上的任意一点aisin; Ej(cj,rj;Sj)到半径rj cj被定义为中心
因此,构建一个良好的初始近似半径rj十分重要
并且该式遵从：
从点aisin;pi;j到马氏圆Ej圆心cj的距离被称为中值马氏距离。
这样，也可以在LAD意义上修改马氏k-means算法。如预期的那样，当数据中出现异常值时，应用LAD-distance函数将显示出更好的拟合结果(参见[16])。
3数值示例
本节提供一些实际的数值示例。假设在所有示例中都预先给出了集群k的数量。因此，数据点集合是从需要重构的k个椭圆中派生出来的。即在不事先知道集群数量(椭圆)的情况下，可以找到指向一个分区中最适当的集群数量的各种索引(参见[10,18])。
例2。四个椭圆的集合以参数形式表示：
其中主轴平行于坐标轴(图2中灰色椭圆)。在附近的j圆mjsim;U(50、60)生成随机点是通过使用副法线与平均向量随机添加点0isin;R2和协方差矩阵而实现,aisin;R2times;2是单位矩阵。通过这种方式,数据集A = { aiisin;R2:1,...,m}，利用高斯分布得到m = 58 50 55 59 = 222个随机点(图2a)。基于数据集A重构椭圆。
以第2.2.1节(图2b中的红色薄椭圆)描述的方式获得椭圆的初始逼近。随后，利用算法1和列文伯格-马夸尔特法求解非线性最小二乘问题，得到的马氏圆心(图2c中几乎覆盖了原始灰度椭圆的薄红色椭圆)。从点到马氏圆所对应的代数距离和的F值也如图2所示。根据原椭圆集与得到的椭圆集之间的F值、视觉视图和非常小的豪斯多夫距离，得到的马氏圆心对原椭圆有很好的拟合。
(a)数据点F = 41.97
(b)初始逼近F = 259.18
(c)解决方案
F = 34.52
例3。给出了四个椭圆的集合，其中两个椭圆与坐标轴不平行(图3中的灰色椭圆)。基于数据集A重构椭圆。
以第2.2.1节中描述的方式获得椭圆的初始逼近(参见图3b中的细红色椭圆)。然后，利用算法1和列文伯格-马夸尔特法求解一个非线性最小二乘问题，得到了马氏圆心(图3c中几乎被原始灰色椭圆覆盖的薄红色椭圆)。从点到m个圆对应的代数距离和的值F也如图3所示。基于F值和目视检验，得到的m个圆心表示对原始椭圆的良好重构。
基于中心聚类51的多椭圆拟合。
(a)数据点F = 108.85
(b)初始逼近F = 562.95
(c)解决方案
F = 87.22
例4。考虑图4a所示的情况。注意，所有椭圆的主轴与坐标轴不平行(参见图4中的灰色椭圆)。
以第2.2.1节(图4b)所述的方式获得椭圆的初始逼近。因此，在算法1的基础上，利用列文伯格-马夸尔特法求解一个非线性最小二乘问题，得到了m圈中心(图4c中几乎被灰度原椭圆覆盖的薄红色椭圆)。从点到m圈对应的代数距离和的F值也如图4所示。基于F值和视觉视图，这些得到的马氏圆心也表现了原始椭圆的一个很好的拟合。
例5。比较三个具有相同中心和比例轴的近似“同心”椭圆的情况，如图5a所示。
椭圆的初始逼近按照第2.2.1节(图5b中的细红色椭圆)描述的方式得到。因此，在算法1中，利用列文伯格-马夸尔特法求解非线性最小二乘问题，得到了马氏圆心(图5c中几乎被原始灰度椭圆覆盖的薄红色椭圆)。从点到马氏圆的相应的代数距离的值F也如图5所示。基于F值和可视视图，得到的马氏圆也能很好地重构原始椭圆。
最后，作者感谢匿名审稿人和期刊编辑们对论文的认真阅读，以及他们对改进论文的评论。我们还要感谢克里斯蒂安·萨布教授(Osijek大学数
全文共10186字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[15023]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
