文摘

拟合直线和简单的弯曲的对象(圆、椭圆等)观测数据点是计算机视觉的基本任务和现代统计(errors-in-variables回归)。我们有最适合的调查存在的问题我们之前的论文(见基诺夫et al . (2012))。我们处理问题的最适合的独特性。

1。介绍

这是一个延续我们的论文(1在那里,我们研究的问题存在最好的拟合曲线。在这里我们处理它独特性。

我们对这些问题的兴趣来自描述一个点集的应用程序(代表实验数据或观察)由简单的几何形状,如线、圆弧、椭圆弧线等等。最适合实现几何距离时给定的点拟合曲线的最小化,在最小二乘意义上。减少寻找最适合的目标函数的最小化 在哪里表示拟合曲线(直线,圆,椭圆,等等)。在这里表示最短的距离来,代表的欧几里得度量。我们参考读者1)背景的几何拟合问题。

大多数出版物上的拟合问题致力于实用算法寻找最佳拟合曲线最小化(1)或统计特性的估计。很少一个地址等基本问题最合适的存在性和唯一性。如果这些问题出现,一个假设最适合的存在,而且是独一无二的或者只是没有深入调查指出相反的例子。

在我们之前的论文(1我们调查了最适合的存在。这里我们解决这个问题的独特性。这些问题是很重要的,导致意想不到的结论。看到我们的结果,在这里,在1),我们提供一个表总结的事务问题的拟合最流行的二维对象(这里是的意味着最好的拟合对象存在或者是独特的在所有各自的情况下;没有的存在唯一性/失败的一些各自的情况下)。

我们发现最好的拟合对象的存在性和唯一性不能想当然。其实答案表的2/31是负的。特别是,独特性永远无法得到保证。(的确切含义所有情况下和典型案例我们参考读者1]。)

最适合的独特性不仅是理论的兴趣也几乎有关。非唯一性意味着最好的拟合对象可能不稳定的轻微的扰动下的数据点。一个例子是被Nievergelt [2]。他提出了一套点,同样可以安装三个不同的圈子。然后任意小的点的坐标的变化,这三个圈的一个可以使任何适合的点有点比另两个圆,因此最好的拟合圆会突然改变。

类似的例子被基诺夫(32.2节),给定数据集的最佳拟合线点是水平的,但在任意小的变化数据的坐标点,结果并成为垂直的。

这些例子表明,最好的拟合对象可能是极其敏感的小数值错误的数据或舍入错误计算。

2。独特性的最佳拟合线

我们开始我们的研究的独特性问题最简单的case-fitting直线数据点。我们首先介绍相关统计符号和符号。

给定数据点,,,我们表示和的样本均值 这一点叫做质心或重心给定的数据集,我们也表示 所谓的“散射矩阵”的组件 特征的“传播”的数据集对其重心。

这个矩阵是对称的和积极的semidefinte。散射矩阵定义了所谓的散射椭圆的中心是的轴是由特征向量张成的散射矩阵(主要的轴是由较大的特征值对应的特征向量张成的)。

接下来,我们发现以下最佳拟合线(3,第二章]。我们将描述线路平面的方程 在哪里线的参数。现在最好的拟合线是发现通过最小化目标函数 的参数只需要指定一个标量。因此我们可以施加约束。由于参数无约束,我们可以消除,这给了吗 特别是,我们发现最好的拟合线总是通过质心的数据集,现在目标函数 或以矩阵形式 在哪里表示参数向量。最小化(9)受约束是一个简单的矩阵代数的问题;其解决方案是散射矩阵的特征向量对应于特征值越小。

观察到的参数向量正交线(5),因此线本身是平行于其他特征向量。此外,它通过质心,因此散射椭圆的长轴。

上述观察结果总结如下。

定理1。每一个最佳拟合线通过质心与散射椭圆的长轴一致。

对于典型的数据集,上述过程导致一个独特的最佳拟合线。但有一些例外。

如果这两个特征值一致,那么每一个向量它的特征向量,函数实际上是常数在单位圆上。在这种情况下所有的线通过质心数据最小化;因此,这个问题有多个(无穷)解决方案。当且仅当是一个标量矩阵,即 上述观察结果总结如下。

定理2。最佳拟合线并不是唯一当且仅当散射矩阵的特征值一致的。在这种情况下,散射椭圆变成一个圆。此外,在这种情况下通过质心的每一行是一个最好的拟合线。

因此我们有一个二分法;要么有一个单最佳拟合线或无穷多的最佳拟合线。在后一种情况下,整个束线通过质心是最佳拟合线。

一个简单的例子的一个数据集有多个最佳拟合线点放在正多边形的顶点顶点(百分度)。旋转角度的数据集在中心周围将数据集本身。如果有一个最佳拟合线,然后通过旋转角我们得到另一个同样适合。因此,最佳拟合线并不是唯一的。

它是那么明显(但真实,根据定理2),每一个线穿过我们的正多边形的中心是一个最佳拟合线;他们都最小化目标函数。

数据点放在正多边形的顶点似乎是一种非常特殊的情况。然而多个最佳拟合线更为常见。以下是正确的。

定理3。给出任何数据点,人们总是可以移动其中一个新的数据集将承认多个最佳拟合线。准确地说,总有和这样一组承认多个最佳拟合线。

换句话说,点可任意放置,没有任何规律,然后我们可以添加一个额外的点的集合点会承认多个最佳拟合线,也就是说,将满足(10)。

不过,多个最佳拟合线的存在是一个不太可能的事件在概率。如果随机采样数据点的绝对连续概率分布,那么这个事件发生的概率为零。事实上,(10)指定了一个地下(子流形)维空间坐标。子流形的体积为零;因此,对于任何绝对连续概率分布,其概率为零。

然而,如果数据点从数字图像获得(说,电脑屏幕上的像素),然后的机会(10)可能已不再是微不足道的,并有可能不容小觑的。例如,一个简单的配置4像素进行平方满足(10),因此正交拟合线不是唯一地定义。

3所示。独特性的最佳拟合圆

我们已经看到在部分2这最简单的拟合直线拟合问题的线可以有多个解决方案,所以它可能不是太吃惊发现更复杂的问题也可以有多个解决方案(我们强调最好的拟合圆的平方和最小化几何距离,定义在介绍)。这里我们展示最适合圆的多样性。

然而,我们不能描述所有数据集的最佳拟合圆不是唯一的全面与我们相同的线路部分2。我们只能提供这样的数据集的一些示例。

著名的例子是基于旋转对称我们已经使用的数据集。这个想法2。假设数据集可以左右旋转通过角对于一些整数后,旋转它回来。然后,如果有一个最佳拟合圆,旋转通过角会给我们另一个圈,同样的数据集。这就是我们得到不止一个最佳拟合圆。

这是一个好主意,但是它分解立即如果最好的拟合圆的中心正好和旋转的中心。然后我们会旋转绕自身中心显然会得到同样的圈。因此必须构建一个旋转对称数据集更仔细,以避免最佳拟合圆集中在自然的对称中心。

最早的和最简单的例子是由Nievergelt [2]。他选择了数据点如下: 最后三个点在一个等边三角形的顶点为中心。所以整个集可以左右旋转原点通过角,它会回到本身。

Nievergelt声称,最好的拟合圆中心和半径。这个圆通过削减最后两个数据点和前两个之间的中间。所以前两个点的距离从这个圆圈,最后两个是正确的(他们的圆的距离是零)。因此,目标函数 很容易相信Nievergelt圈是最好的,实际上,任何试图扰乱它的中心和半径只会使健康恶化(目标函数将增长)。不过一个完整的数学证明的索赔将可能非常困难,所以我们离开它。

我们的目标是比寻找最好的拟合圆更温和Nievergelt的例子。我们的目标是证明有多个最佳拟合圆(没有显式地找到它们)。这里的多样性可以证明如下。

根据我们一般的结果(1),为每个数据集最适合的存在,这可能是一个圆或直线。如果最好的对象是一个圆,则在它的中心或其他地方。我们有三种可能的情况:(i)的最佳拟合对象是一条线,(ii)的最佳拟合对象为中心的圆,(iii)的最佳拟合中心不同的对象是一个圆。在过去的情况下我们的旋转对称将工作,如上所述,并证明最好的拟合圆的多重性。所以我们需要排除前两个案件。

考虑任何圆的半径集中在。很容易看到各自的目标函数 它是达到最小,它的最小值 这是比在(12)。因此圆圈围绕原点不能与Nievergelt竞争的圈子,应该排除。

接下来,我们考虑所有行。正如我们所看到的部分2为旋转对称的数据集,所有最好的拟合线穿过中心。所有的线条同样适合。以轴,例如,它很容易看到相应的目标函数 这是大于在(12),甚至超过在(14)。因此线甚至比圈竞争力集中在原点,所以他们也排除了。证明完成为止。

因此,不同于最佳拟合圆的中心。因此通过这个圆旋转角度和,我们得到了两个圈,同样的数据一致。所以圆拟合问题有三个不同的解决方案。所谓的最佳拟合圆图所示1。

Nievergelt例子后,其他两个文件,独立,类似nonunique圆适合的例子。

基诺夫和Lesort4)使用一个完美的平方,而不是Nievergelt的等边三角形。他们把四分的顶点在其中心广场和另一个4分,所以数据集组成点总。然后他们使用上述策略,证明至少4个不同的圈子实现最适合。

Zelniker和克拉克森5)使用一个等边三角形,三分在其顶点和三个点在其中心(数据集包括点)。然后他们表明,至少有三个不同的圈子实现最适合。

这些例子导致一个有趣的事实,似乎违反直觉。让是一个圆的半径与中心。让我们把大量的数据点和一个数据点的中心。假设点放置均匀(比如正多边形的顶点)。然后似乎是一个很好的候选人最好的拟合圆,篡改的所有数据点,只想念,所以。很难想象,任何其他圆或线可以做得更好。

然而,一个引人注目的事实证明了Nievergelt [6,引理7]说最好的拟合圆的中心不能配合任何数据点。因此,在我们的例子中,不能最好的拟合圆。因此一些圆中心更适合的数据集。再一次,最好的圈旋转使其他最佳拟合圆,这并不是唯一的。

旋转对称数据集上述明显异常;小扰动的数据点容易破坏对称。但是可能有许多其他数据集,没有任何对称性,也承认多个圆适合。我们相信,他们都是不寻常的,很容易被小扰动。以下是我们的观点。

假设一组数据点承认两个圆适合最好,表示圆的和。首先考虑一个简单的案例;和是同心的,也就是说,有一个共同的中心,。让表示点的距离中心。通过直接检查,对于任何圆的半径集中在目标函数是 这是一个二次多项式,所以它不能有两个截然不同的最小值。所以这两个最好的拟合圆不能同心。

现在假设圆和没有同心,也就是说,他们有不同的中心,和。让表示通过和。注意,不能所有的数据点在直线上(因为如果数据点共线,最适合将通过插值,而不是由两个圆行)。所以存在一个点不撒谎。因此我们可以把它略圆但远离圆。的目标函数稍有变化,就会减少在一个最低(其他()和增加)。这将打破领带,保证全球最低的独特性。

4所示。独特性的最佳拟合椭圆

基于前两部分,我们应该期待数据集存在的最佳拟合椭圆并不是唯一的。然而,我们在文献中找不到任何明确的例子,所以我们提供我们自己的。

我们之前的论文(1)是第一个提供这样的一个例子。我们拟合曲线均匀分布在一个完美的正方形,。我们发现,出乎意料的是,最适合通过两个独特的椭圆形;他们是几何(即平等。,的y had the same major axis and the same minor axis), and they had a common center, but one was oriented vertically and the other horizontally. See Figure2。

严格地说,在这个例子中,我们没有一个数据集取而代之的是均匀分布,获得大样本的限制,。但我们会得到同样的picture-two最佳拟合ellipses-if我们的地方数据点在广场上安排一个完美的平方晶格(例如,点坐标,在那里和)。

可以构造一个更加优雅的例子如下。回忆(部分3),Nievergelt多个拟合圆的的例子数据点;三个被放置在一个等边三角形的顶点和第四个中心。

注意,一个圆有三个独立参数,但椭圆有五个。这是通过将自然推广Nievergelt的例子五在顶点数据点普通的五角大楼和第六的中心。因此我们有数据点如下:

我们坚信最好的拟合椭圆通过最后四个数据点和重点。这五个点确定椭圆独特。这显然是对称的轴,所以它的主轴是水平的。这个椭圆削减对前两个数据点之间的中间。所以这两个点的距离从椭圆和最后四右(距离为零)。因此,目标函数 下面我们提供的部分证据声称上述椭圆是最好的。我们还设计了一个完整的计算机辅助证明涉及广泛的数值计算。

最后,通过椭圆旋转角度为我们得到了四个椭圆适合同样的数据。椭圆拟合问题有五个不同的解决方案;参见图3。

我们将比较最佳拟合椭圆的圆心在起源和最佳拟合线。考虑任何圆的半径集中在。很容易看到各自的目标函数 它是达到最小,它的最小值 这是比在(18)。因此圆圈围绕原点不能与我们的椭圆。

考虑所有行。正如我们所看到的部分2为旋转对称的数据集的所有最佳拟合线穿过中心,和所有这些线同样适合。以轴,例如,它很容易看到相应的目标函数 这是大于在(18),甚至超过在(20.)。因此线甚至比圈竞争力以原点为中心。

椭圆拟合问题,双平行线是合法的模型对象;参见[1]。我们检查了适合通过双平行线。最适合我们发现两个水平线和,在那里 请注意,是平均坐标的第一个四分在我们的样例。因此第一行是最好的拟合线第一4分,第二行通过最后两个点。这条线的目标函数 这是很好,比最好的拟合圆(20.)。但仍然是一个小比最好的拟合椭圆(18)。

因此我们更适合比椭圆的圆心在原点,任何行,任何一对平行线。为了得出结论,这真的是最好的拟合椭圆,我们都必须把它比作其他椭圆和抛物线。这项任务似乎是件极度困难的事,如果一个人只使用如上所述的理论争论。相反,我们开发了一个计算机辅助证明。这是一个由问:黄博士论文的一部分,我们计划发布在网络上(7]。