英语原文共 8 页，剩余内容已隐藏，支付完成后下载完整资料

解析流形上聚类的非线性均值漂移

Raghav Subbarao ，Peter Meer

电子与计算机工程专业

皮斯卡塔韦，罗格斯大学

概论

在欧几里德空间中，Meanshift算法被广泛应用于无参聚类方法。最近，meanshift算法逐渐被推广到李群矩阵中。我们又进一步把该算法拓展到更一般的非线性空间中，一个解析流形的集合。举个例子，在两个特定的频繁发生的参数空间中，格拉斯曼集合和李群代数会被考虑。当该算法被限制在李群矩阵中时，就会得到早前提出的方法。该算法被应用于各种运动分割问题和多元因数分解中。运动分割方法对离群点具有鲁棒性，对独立运动的数量和当前所有动作的估计不做任何事先规范。

1.介绍

Meanshift算法[6, 9]是一种流行的无参聚类方法。该算法已被应用于图片分割，图像追踪[3, 7, 10, 12, 21]和鲁棒性融合[5, 8]。Meanshift算法的理论性质也已被研究，等等[13]。

原始的meanshift算法的主要限制是它只能被应用于欧氏空间中的点。在[17]中，meanshift算法被拓展到一类特殊的非线性空间--李群矩阵中。由此产生的算法被用来开发一个强大的运动分割方法，同时估计运动的数量和它们的参数。即使限制我们自己的运动分割问题，也存在大量的运动模型，它们的参数空间不是李群。这些运动例子包括从标准相机转换的3D视图和多元因数分解[20]。

解析流形的集合是一个更一般的非线性空间。李群是解析流形的一个例子，但并非所有的解析流形都是李群。在前面提到的所有运动模型中，参数空间是格拉斯曼流形的例子，但是却不是李群。对于这样的问题，[ 17 ]算法不适用。

我们提出一个更一般的meanshift算法，该算法可以应用于任何解析流形。如果正在解决的流形是一个李群矩阵，那么我们的算法和算法[17]一样，因此，算法[17]是这里提出的算法的一个特殊情况。

本文的结构如下，在第2节中我们简要地讨论了解析流形的相关理论，在第三节回顾了标准的meanshift算法[ 9 ]，在第四节中我们得出一般非欧氏空间meanshift算法。我们还提出了两个经常发生的类参数空间的计算细节，格拉斯曼流形和李群矩阵。在第五节，我们将该算法应用于一些运动分割问题当中。

2.解析流形

流形是一个类似于欧氏空间的拓扑空间。直观地说，我们可以把流形看成是位于高维欧氏空间中的连续曲面。解析流形满足平滑的进一步的条件[ 4 ]。从现在起，我们只分析流形，并且每当提到流形都是指解析流形。

在切线空间中，在点x的，是在那个点上与流形表面相切的平面。切线空间可以被看作是一组限制在流形上移动的点的允许速度的集合。对于d维流形，切线空间是一个d维向量空间。在图1中，一个二维的流形的例子被嵌入到切线空间中。实心箭头，是一个在点x处的切线。由于是一个向量空间，我们可以定义一个内积。内积产生一个范数的切线，。应该指出的是，内积和范数是随x变化而变化的，这种变化关系是通过下标来指出的。

流形中的两个点之间的距离是通过它们之间的曲线的长度给出的。任何曲线的长度是通过切线的积分得到的[2]。最小长度的曲线称为短程线，短程线的长度为本征距离。在计算机视觉问题中出现的参数空间通常有被透彻研究的几何结构，并且本征距离的封闭形公式是可以得到的。切线（在切线空间中）和短程线（在流形中）是密切相关的。对于每一个切线，在点x都有一个独特的拥有初始速率的短程线。指数图，通过短程线将指向流形中的点。对数映射是指数映射的逆，。指数和对数随点x移动而变化。这些概念如图1中所示，x,y是流形中的点，。虚线显示了短程线从x处开始，并且在y处结束。这个短程线有一个初始速率，因此y和满足和。这些运算符的具体形式依赖于流形和我们在后面的章节中明确讨论的公式。

操作数通常是映射关系，但不是一对一映射。对于流形上的任何一个y，如果存在很多满足，被选为最小范数的切线。

对于一个定义在流形上的光滑的实值函数f，函数f在点x的变化率，被定义为一个唯一的切向量，满足

(1)

对于任意的，是沿着的定向导数。这个变化率具有表示拥有最大增长量的正切的性质。注意，我们用小黑体字母表示流形上的点，例如，x，y。在我们的一些例子中，流形由矩阵构成，每个点表示一个矩阵。虽然矩阵通常用大写粗体字母表示，但是当我们把矩阵当作流形上的点时，我们用小写字母表示它们。这不应该是一个问题，因为任何矩阵都可以通过将元素重新排列成一个单一的列的而表示为一个向量。

对于格拉斯曼流形上的一个点，表示了上的一个k维空间，也可以通过一组标准正交基，表示为一个Ntimes;K矩阵，即，。由于许多基础共享相同的子空间，这表示上的点不是唯一的[11]。

对于黎曼流形，可以定义和，例如

(2)

这样的度量称为黎曼度量。

李群矩阵是GL(n,R)的子群，其中GL(n,R)是NN非奇异矩阵的组。李群矩阵是黎曼流形的例子[15]。

3.meanshift算法

给定欧氏空间中的n个点，内核密度估计为

(3)

基于轮廓函数K满足

(4)

是x的密度的非参数估计。常数被选择以确保集成到1。定义

。公式(3)的变化率可以被表示如下

(5)

C是一个正常数，是均值漂移向量。表达式(5)表明均值漂移向量与归一化密度变化率估计成正比。迭代公式

(6)

是一个收敛到密度平稳点的变化率上升技术。鞍点可以被检测和删除，只获得模式。

4.非欧几里德均值漂移

流形上的点的加权和没有得到很好的定义，并且（5）的平均移位向量是无效的。在本节中，我们将得到均值漂移向量作为切向量加权和。由于切空间是向量空间，因此，正切的加权平均是可以得到的，而且可以用来更新模估计。此方法对任何解析流形都是有效的。

考虑一个带有度量d的流形。在给定n个点的流形上，，轮廓k，带宽为h，内核密度估计公式是

(7)

带宽h可以包含在距离函数中作为一个参数。然而，我们以这种形式写它，因为它给我们一个参数来调整应用程序的性能。如果流形是拥有欧氏距离度量的欧氏空间，（7）与欧氏核密度估计公式（3）相同。估计并不总是容易的，因为它需要流形上轮廓的积分。由于一个全局性的缩放不影响模式的位置，我们从现在起删除。

计算在点x的变化率，我们得到

(8)

跟之前一样，。距离的变化率取决于x。类似于（5），定义了欧氏空间的均值漂移向量，定义非欧均值漂移矢量如下

(9)

上述方程中所有的运算都有明确的定义。变化率位于正切空间中，内核是标量。均值漂移向量是切向量的加权和，而且它本身在中是一个切向量。该算法通过移动沿着短程线移动的均值漂移向量定义的点来前进。非欧均值漂移迭代公式如下

(10)

迭代公式(10)，通过沿着均值漂移向量定义的短程线移动来更新，以得到下一个估计。完整的算法如下所示。

解析流形上的均值漂移算法

给定：流形上点，i= 1,hellip;,n

for i=1hellip;n

x=

repeat

x=

until

保留x作为本地模式

报告不同的本地模式。

一个均值漂移迭代通过在每个数据点处设置而开始。内循环通过迭代更新x直到收敛。

该算法适用于任何流形。一个实际的操作需要变化率矢量的计算和指数算符。我们现在讨论这两个常见的流形类的计算。

4.1 格拉斯曼流形

如前所述，格拉斯曼流形由正交矩阵组成。设f是一个定义在上的可微函数。对于f的变化率存在一个封闭形式的公式，就雅可比公式[11]而言

(11)

作为一个度量，我们使用的弧长[1]

(12)

k来自格拉斯曼流形，tr是追踪。如果我们考虑（12）中定义的距离函数，

作为x的函数，并用它代替（11）中的f，我们得到

(13)

使用（13）代替非欧均值漂移方程（9）中的，我们可以得到

(14)

切线矢量被表示为一个的矩阵，格拉斯曼流形的指数算符如公式所示[11]

(15)

其中是的紧凑SVD，其找到k个最大奇异值和相应的奇异向量。sin和cos逐个作用于奇异值。

4.2 李群矩阵

李群矩阵[15]经常作为参数空间在计算机视觉空间中出现。一般的非线性均值漂移算法没有明确地涉及，但是对于李群矩阵，我们用来估计变化率。令exp和log为矩阵运算符

(16)

(17)

这些是可以应用到任何正方形矩阵的标准矩阵运算符，并且不需要下标来定义它们。它们不应该被流形操作符和混淆，它们由以下公式给出

(18)

(19)

其中，y是流形中的任意一个点，。距离公式由下式给出

(20)

表示矩阵的Frobenius范数。由于李群矩阵是黎曼，所以d的定义可以被证明是对应于上的内积的距离。变化率的公式是相当复杂的，因为我们必须将log x的变化解释为x的变化。但是，通过忽视这种依赖，我们可以得到

(21)

该公式可以被证明是一阶近似的真正梯度[ 17 ]。这个推倒涉及大量的代数，但是因为空间的限制，因此省略。将其代入（9）中，矩阵李群的均值漂移向量

(22)

由于均值漂移矢量和运算符（18）是已知的，因此矩阵李群的算法与[17]中提出的相同。

5. 实验结果

作为我们的算法的一个应用，我们使用它来增强运动分割和多体因子分解。给定具有多个运动的数据集，这里讨论的方法同时分割和估计存在的所有运动，并且不需要规定运动次数。

据我们所知，目前还没有算法能解决这样一般的问题。RANSAC类的算法具有鲁棒，并且尝试估计单个运动，同时将所有其他点视为异常值。另外，诸如GPCA [18]的算法同时估计多个运动，但是不稳健，因为它们假设每个点是运动之一的一个惰性。这两个算法家族都需要一些由用户给出的关于运动数量的知识。

出于两个原因，我们不会与其他算法进行任何比较。首先，运动分割只是我们新的均值偏移算法的一个应用。我们的算法也可以用于其他应用，比如在流形上的稳健融合。其次，我们不了解以前的算法，这些算法具有鲁棒性，并且在不知道当前运动的数量的前提下就可以同时估计所有的运动。

5.1多运动估计

我们的算法与[17]的方法类似，唯一的区别是我们聚类的运动参数被允许位于任何解析流形上。算法的输入由一组点匹配组成，其中一些是异常值。该算法有两个阶段。在第一阶段，随机抽样以产生元素子集。元素子集由指定运动假设所需的最小点数组成。根据问题，可以使用各种方法从元素子集中产生运动假设。选择多个元素子集，并且每个元素用于生成运动假设。可以通过减少第二阶段计算的验证步骤来提高采样和假设生成[17]。在第二阶段，使用这里提出的算法对参数估计进行聚类。主要模式的数量给出了数据中的运动次数。这些模式对应于运动参数。对于每个模式，我们使用[16]中的方法来找到相应的内部值。由于各运动的内在因素是独立决定的，因此一点可以分配给两个动作。在这种情况下，通过将连接分配给给出较低错误的运动来破坏连接。在我们所有的实验中，使用Harris角检测器来检测点，并使用[14]的方法在视图中匹配。对于平均偏移，我们使用高斯内核，带宽由最近邻程序选择。

5.2.错误处理

我们现在讨论用于测试我们系统对实际数据的错误处理的性能。模式的数量应等于存在的运动的数量。然而，均值漂移返回核密度估计的所有局部最大值。因此，对于具有m个运动的数据集的第一个m的模式应该明确地支配第（m 1）个模式，从而使这些多余的模式可以被修改。

我们比较了一个运动使用算法分割与手动分割所返回的结果。更少的错误分类意味着更好的表现。

设为估计运动，是包含所有帧的点坐标的向量。对于一个内层和正确的运动，形式的关系应该成立。由于噪声影响，这在实践中是不被满足的。我们测量的残差平方误差为

(23)

较低的错误意味着更好的性能。在

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[26505]，资料为PDF文档或Word文档，PDF文档可免费转换为Word