GridShift：一种快速的图像分割和物体跟踪算法

81310GridShift：一种更快的图像分割和物体跟踪的模式寻找算法0Abhishek Kumar 1，Oladayo S. Ajani 1，Swagatam Das 2和Rammohan Mallipeddi 1，*01 韩国庆北大学人工智能系，大邱37224，韩国 2印度统计研究所电子与通信科学单元，加尔各答700108，印度0abhishek.kumar.eee13@itbhu.ac.in, oladayosolomon@gmail.com,0swagatamdas19@yahoo.co.in, mallipeddi.ram@gmail.com0摘要0在机器学习和计算机视觉中，均值漂移（MS）被认为是最流行的模式寻找算法之一，用于聚类和图像分割。它将每个数据点迭代地移动到其邻域数据点的加权平均值。找到每个数据点的邻居所需的计算成本与数据点的数量成二次关系。因此，对于大规模数据集来说，传统的MS算法速度非常慢。为了解决这个问题，我们提出了一种基于MS的模式寻找算法GridShift，它具有显著的加速效果。GridShift采用基于网格的邻居搜索方法，其计算复杂度与数据点的数量成线性关系。此外，GridShift通过将活动网格单元（至少与一个数据点相关联的网格单元）移动到更高密度的位置，提供更多的加速效果。GridShift的运行时间与活动网格单元的数量成线性关系，与特征的数量成指数关系。因此，它非常适合大规模低维应用，如物体跟踪和图像分割。通过大量实验证明，与其他基于MS的算法以及最先进的算法相比，GridShift在图像分割的准确性和运行时间方面表现出卓越的性能。最后，我们提供了一种基于GridShift的新的物体跟踪算法，并展示了与CamShift和meanshift++相比的有希望的结果。01. 引言0均值漂移（MS）是一种非参数的迭代模式寻找算法，用于聚类分析。MS有效地检测聚类的能力使其成为几个计算机视觉应用的核心，如无监督图像和视频分割[18, 19, 21, 22,28]，物体跟踪[7, 15, 17]和图像处理[3, 4]。0*通讯作者0MS不需要事先指定簇的数量。此外，它也不对数据点的概率分布做任何先验假设。由于这些特性，MS通常优于其他流行的和应用特定的算法，如k-means [12,27]，谱聚类[10]，Felzenszwalb[8]和简单的线性迭代聚类（SLIC）[1]。然而，MS中的迭代过程在计算上是昂贵的，因为每次迭代的渐近或有界行为是O（n^2）的顺序。换句话说，为了找到每个点的邻域数据点所需的计算复杂度与数据点的数量成二次关系。尽管在图像分割中具有卓越的性能，但这种高计算成本限制了MS在高分辨率图像分割中的应用。为了解决这个问题，我们提出了MS的扩展变体GridShift（GS），其时间复杂度与数据点的数量成线性关系，与特征的数量（数据点的维度）成指数关系。0一种流行的基于颜色的物体跟踪算法CamShift（CS）[2,5]是从MS算法中派生出来的。尽管它被认为是一种流行的无监督物体跟踪方法，但CS有一些主要缺点，限制了它在实际跟踪问题中的适用性。主要缺点是它只利用了反投影概率分布的峰值。因此，它无法区分颜色相似的对象，并且由于搜索窗口周围存在颜色相似的对象，导致跟踪失败[14]。另一个问题是由于计算负担，CS通常只使用一个参考直方图。因此，外观或光照条件的变化会影响CS的跟踪性能，它经常无法跟踪物体。在这项工作中，我们通过解决这两个问题，基于GS算法开发了一种新的物体跟踪算法。0在MS++ [14]和α-MS++[20]中，数据空间被划分为网格，每个数据点与一个网格相关联。81320原始 GridShift MeanShift++ Felzenszwalb SLIC Quickshift 0.028秒 1.168秒 0.231秒 0.223秒 11.489秒00.110秒 4.643秒 1.542秒 0.982秒 54.951秒00.036秒 1.126秒 0.357秒 0.322秒 16.832秒0图1.在三个基准分割问题上，五种算法的比较，取自[16]。GS在所有基准图像中返回质量良好的图像分割结果，且运行时间比其他最先进算法更短：分别比MS++、Felzenszwalb、SLIC和Quickshift快40倍、10倍、8倍和500倍。0GridShiftCamShiftCamShiftGridShift0第1帧0第1帧0第3帧0第14帧0第7帧0第26帧0第17帧0第49帧0第65帧0第120帧0图2.GS和CS在两个基准目标跟踪问题上的比较，取自[26]。上排：我们正在跟踪骑自行车者的脸部（目标对象用蓝色框表示）。由于脸部光线较暗，背景上有大量绿色，CS算法无法跟踪。另一方面，尽管存在这些问题，GS在所有视频帧中都能准确跟踪脸部。下排：我们正在比赛中跟踪选手Bolt（目标对象用绿色表示）。由于Bolt的衣服颜色是黄色，并且被其他黄色物体分散注意力，CS无法跟踪。另一方面，GS在所有视频帧中都能准确跟踪Bolt，而不受其他相同颜色物体的影响。0一个合适的网格单元。随着迭代次数的增加，数据点向其最近的模式收缩；因此，与活动网格单元相关联的数据点的数量也增加[6]。网格单元的所有相关数据点的移动位置可以近似为它们移动位置的加权平均值（称为该网格单元的质心）[14,20]。因此，这激发我们开发一种新的基于网格的框架GridShift，与MS++和α-MS++不同，我们直接将MS的移动步骤应用于数据点的近似质心。由于多个数据点具有相同的质心，我们可以通过增加迭代次数来减少计算成本。因此，所提出的算法比MS++和α-MS++更快。由于计算时间减少，GS可能符合0由于摄像机和传感器采集数据的分辨率不断增加，现代数据集的规模也越来越大，GS成为计算机视觉应用中现有技术的一种有吸引力的替代方案。我们的主要贡献如下：0•我们提出了一种更快的模式寻找算法GS，用于无监督聚类大规模低维数据集（非常适合图像分割等应用）。•为了从闭环迭代循环中退出，GS不需要任何停止准则。•实证分析表明，GS提供了与MS和MS++相比更好或至少相当的聚类结果，并且计算速度显著更快。5148185119611272121181330•一项在公认的基准数据集上进行的图像分割实验表明，GS在准确性和效率方面确实优于一些流行的最先进算法，相比于MS++和MS，速度提升分别达到40倍和40000倍。•我们还提出了一种基于GS的新的目标跟踪算法，该算法逐渐适应场景和颜色分布的变化。我们的实验表明，与MS++和CS-based目标跟踪算法相比，基于GS的目标跟踪算法能更准确地检测到物体。在进一步深入了解GS的细节之前，让我们提供两个热身示例，以说明它在图像分割和目标跟踪应用中的潜力。01）图像分割的一个示例：我们使用来自[26]的三个基准图像进行无监督图像分割。为了进行比较分析，我们将以下算法视为最先进的算法：Felzenszwalb [8]，Quickshift[24]，SLIC（k-means）[1]和MS++[14]。我们在图1中展示了所有这些算法的结果。如图1所示，GS可以产生与MS++类似的分割结果，但速度提高了40倍。与其他算法相比，GS在更快的计算速度下实现了更好的分割效果。从这个例子可以清楚地看出，GS提供了比其他算法更好的分割结果和更低的运行时间。02）目标跟踪的一个示例：对于目标跟踪，我们使用CS和GS。在图2中，我们展示了这些算法在两个来自[26]的基准问题上的跟踪结果。从图2可以看出，GS是一种更强大的目标跟踪算法，在复杂的背景环境中，特别是在颜色相似的大区域中，表现更好。另一方面，CS在这种情况下无法跟踪，因为其性能高度依赖于物体的颜色。02. GridShift0在本节中，我们首先详细介绍GS的基本步骤，然后概述MS++和GS之间的主要区别。最后，我们提出了一种基于GS的目标跟踪算法。02.1. GridShift的基本实现0设X：{x1，x2，...，xn}是一个包含n个数据点的数据集，其中xi∈Rd。该算法假设整个数据空间被划分为预定义长度h的相等且不相交的网格单元。我们将这些网格单元分为两种类型：活动网格单元和非活动网格单元。至少有一个数据点作为居民的网格单元被视为活动网格单元；否则，它们被视为非活动网格单元。在这里，我们可以将每个活动网格单元标记为一个簇，其中0更新的质心位置0活动网格单元0三个活动单元合并，因为它们的更新质心位于同一个网格中0合并单元的质心0收敛0迭代：0 迭代：10迭代：20图3.MS和GS并行进行高斯分布2D数据集聚类的演示。尽管在每次迭代中减少了质心的数量，GS仍然可以有效地近似MS的步骤。这种减少在运行时间上提供了加速，相比原始的MS、MS++和α-MS++。0其居民数据点是该簇的成员。这些网格单元具有自己的三个属性，表示为哈希表：质心、居民数据点的数量和居民数据点的集合。所有活动网格单元在每次迭代中更新它们的哈希表。此外，GS根据它们的新质心移动活动网格单元的位置。在移动过程中，一些活动网格单元可能会注册相同的位置；因此，它们合并为一个。这些步骤重复进行，直到收敛，即所有活动网格单元的哈希表没有变化。收敛后，GS以活动网格单元的形式返回聚类结果。GS步骤的演示如图3所示。我们总结GS的基本步骤如算法1所示，并在以下更详细地讨论。i）活动网格单元的初始化：为了初始化，我们为每个活动单元的每个属性创建三个空的哈希表：S（存储质心）、C（存储居民数据点的数量）和H（存储居民数据点）。我们通过h将每个数据点划分为活动网格单元的初始索引。之后，我们计算逐元素的floor函数，该函数返回一个d维整数向量。这个d维向量表示活动网格单元的索引。使用算法1的第3-11行更新所有三个哈希表。ii）更新每个活动网格单元的质心：为了更新活动网格单元的质心，我们利用其相邻的活动网格单元。这里，相邻的网格单元指的是与该活动网格单元通过边或点接触的网格单元，即如果i = j + v，其中v∈{-1,0,1}d，则索引为j的网格单元被认为是索引为i的网格单元的相邻网格单元。我们更新S(j) ←�(v∈{−1,0,1}d) wvS(j + v)(v∈{−1,0,1}d) wv,(1)S(j) =�i∈M C(i)S(i)i∈M C(i),(3)C(j) =�i∈MC(i),H(j) =�i∈MH(i).(4)5S (⌊xi/h⌋) ←i/h⌋)S(⌊xi/h⌋)+xiC(⌊xi/h⌋)+1;6C (⌊xi/h⌋) ← C (⌊xi/h⌋) + 1;7H (⌊xi/h⌋) ← H (⌊xi/h⌋) ∪ {i};9S (⌊xi/h⌋) ← xi;10C (⌊xi/h⌋) ← 1;11H (⌊xi/h⌋) ← {i};16′(j)v∈{−1,0,1}d) C′(j+v)S′(j+v)d) C′(j+v);/h⌋)+S′(j)C(⌊S′(j)/h⌋)+C′(j);81340使用所有相邻网格单元的质心的加权平均值计算活动网格单元的质心，即0其中，w v  =  C ( j  +  v ) . (2)0iii）更新活动网格单元的位置：每个活动网格单元需要根据其质心的更新来更新其位置或索引。新位置的计算使用  �S/h �。iv）合并一些活动网格单元：具有相同位置（索引）的活动网格单元需要合并为一个具有更新属性的网格单元。新网格单元的质心通过合并的所有活动网格单元的质心的加权平均值计算，即0其中，M是合并为一个的网格单元的索引集合。其他属性的更新方式如下：0v）停止准则：当活动网格单元的属性不再更新时，即活动网格单元没有单个相邻的活动网格单元来更新网格单元的属性时，算法退出迭代。0值得注意的是，在实现算法 1时，我们优化了GS的基本步骤，以减少额外循环，提高时间复杂度。根据算法 1中使用的步骤，GS的时间复杂度为每次迭代 O ( m 3 d )，其中 m表示活动网格单元的数量，并且随着迭代的进行而保持不增加。02.2 基于GS的目标跟踪算法0由于GS具有有效的模式寻找行为和更快的运行时间，因此GS可以成为目标跟踪的良好选择。此外，GS的聚类结果在网格单元中是直方图的适当替代品 [ 14 ]。在算法 2中，我们展示了基于GS的提议的目标跟踪算法的基本步骤。该算法的基本步骤如下：0算法 1：网格移动01  输入：单元格的边长（带宽）h，Xn；02  初始化：空哈希表 S（存储质心）、C（存储居民数据点数量）和H（存储居民数据点）；03  对于 i  ∈  [1 , n ]04 如果  � x i /h � 在 S 的键中，则08 否则013 S ′ ← S，H ′ ← H，C ′ ← C；014 清空哈希表 C 和 S ；015 对于 j  ∈ S的键，执行以下操作：017 如果 S ′ ( j ) /h 在 S 的键中，则020心更新为其所有相邻网格单元质心的加权平均值，即022 S ′ ( j ) /h �� ← S ′ ( j ) ;024将当前网格单元的质心更新为其所有相邻网格单元质025 当 ( S .keys  +  v )  ∩ S .keys  ==  �时，执行以下操作，其中 v  ∈  ( {− 1 ,  0 ,  1 } d − { 0026 返回 H 和 S0算法2：基于GS的物体跟踪01 输入：帧序列 X 0 ，X 1 ，X 2 ，...，X T ；初始中心 o；长度 l；宽度w；增量因子 f；带宽 h；和终止容差 η；02 在帧窗口 W ( o, l, w ) ∩ X 0 上运行GS；03 初始化：B ← {� c/h � : c ∈ C}，其中 C 是手动选择的聚类的并集；04 对于 i = 1, 2, ..., T 做06 W' ← W ( o, l/f, w/f )；07 R ← {x ∈ W' ∩ X i : � x/h � ∈ B}；08 如果 R == φ，则09 l ← 1.1 l；010 w ← 1.1 w；011 else012 o ← R中的数据点的（x，y）位置的均值；013 B ← {� c/h � : c ∈ R}；014 如果 (max(l) - min(l)) < l，则015 l ← 0.99 l；016 else017 l ← 1.01 l；018 如果 (max(w) - min(w)) < w，则019 w ← 0.99 w；020 else021 w ← 1.01 w；022 当 o 收敛于 η 时循环；023 发出 W ( o, l, w ) 对于帧 X i ；0i) 初始化：我们在初始帧窗口 W ( o, l, w )的颜色像素上应用GS，其中 W ( o, l, w ) 表示一个以中心o 的跟踪窗口，̸81350长度 l 和宽度 w。GS对不同的物体返回不同的聚类。我们手动选择目标物体的聚类。通常，我们经常选择较大尺寸的聚类。在选择聚类之后，我们计算网格单元的参考集合R，其中选定聚类的数据点是给定帧窗口中的常驻点。此外，我们使用这个网格单元的参考集合来跟踪新帧中的中心。0ii)计算新中心：随着帧的变化，目标物体也会改变位置。根据目标物体位置的变化，我们需要计算窗口的新中心。给定帧的新中心通过迭代计算直到收敛。为此，我们创建一个跟踪窗口 W。然后，我们找到属于 R的网格单元的数据点，并创建一个集合B。然后，我们通过取给定帧中 B的数据点的（x，y）位置的均值来计算中心。0iii)更新跟踪窗口的长度和宽度：有时由于跟踪窗口的尺寸较小，物体移动得足够快以至于将跟踪窗口驱逐出新帧。在这种情况下，当 B是一个空集时，我们将搜索窗口的长度和宽度增加1.1倍，以增加物体跟踪的机会。另一方面，跟踪对象的大小和外观会随着帧的变化而改变。为了相应地调整跟踪窗口，我们增加或减小长度和/或宽度（在算法2的第14-21行中显示）。0开发的新物体跟踪方案比CS算法更稳健和有效。它对物体的颜色直方图的概率分布的依赖性较低，并且跟踪窗口的自适应方案提高了物体跟踪的性能（在第1节的示例2中演示）。03. 理论分析0在本节中，我们讨论GS的理论性质。由于页面限制，我们在补充文件中提供相应定理的证明。在理论分析之前，值得注意的是，GS也使用了类似于MS++的基于网格的数据空间划分。因此，根据[14]的定理1，我们可以说GS方法在统计上至少可以与其他密度函数估计器表现类似。03.1. 收敛保证0对于任意给定的数据集X(={x1,x2,...,xn})∈Rd，在t次迭代中，定义一个映射g(t):X←C(t)，使得每个数据点xi∈X被分配给k(t)个活动的网格单元c(t)i0数据集 ARI AMI0GS MS++ α-MS++ GS MS++ α-MS++0手机加速度计0.0899 0.0897 0.0896 0.1923 0.1959 0.19210(38.23秒) (1599.34秒) (475.58秒) (45.34秒) (2523.85秒) (646.27秒)0手机陀螺仪0.2401 0.2354 0.2355 0.1837 0.1835 0.18240(110.43秒) (5324.19秒) (934.28秒) (45.39秒) (1723.19秒) (780.35秒)0手表加速度计0.1001 0.0913 0.0908 0.2314 0.2309 0.23010(18.38秒) (926.59秒) (319.29秒) (41.86秒) (2500.97秒) (658.37秒)0手表陀螺仪0.1623 0.1593 0.1602 0.1422 0.1336 0.13970(25.23秒) (1247.08秒) (416.85秒) (11.53秒) (484.27秒) (180.24秒)0静止0.7896 0.7899 0.7901 0.8602 0.8551 0.85990(0.17秒) (8.23秒) (3.12秒) (0.12秒) (6.23秒) (2.62秒)0皮肤0.3266 0.3264 0.3264 0.4251 0.4238 0.42340(0.29秒) (12.58秒) (3.28秒) (0.19秒) (9.28秒) (2.92秒)0墙壁机器人0.1801 0.1788 0.1748 0.3356 0.3239 0.33360(<0.01秒) (0.14秒) (0.08秒) (<0.01秒) (0.42秒) (0.12秒)0睡眠数据0.1201 0.1181 0.1193 0.1117 0.1028 0.10560(<0.01秒) (0.01秒) (<0.01秒) (<0.01秒) (0.01秒) (<0.01秒)0平衡天平0.0799 0.0883 0.0862 0.2301 0.2268 0.22740(<0.01秒) (0.06秒) (0.02秒) (<0.01秒) (0.07秒) (0.02秒)0用户知识0.3403 0.3398 0.3398 0.4108 0.4086 0.40830(<0.01秒) (0.05秒) (0.02秒) (<0.01秒) (0.05秒) (0.02秒)0Vinnie 0.4568 0.4594 0.4597 0.3665 0.3666 0.36770(<0.001秒) (<0.01秒) (<0.01秒) (<0.001秒) (<0.01秒) (<0.01秒)0PRNN 0.2093 0.2093 0.2093 0.2913 0.2912 0.29120(<0.001秒) (0.01秒) (<0.01秒) (<0.001秒) (<0.01秒) (<0.01秒)0鸢尾花0.6246 0.5681 0.5826 0.8014 0.7316 0.74270(<0.001秒) (<0.01秒) (<0.01秒) (<0.001秒) (<0.01秒) (<0.01秒)0移植0.7524 0.7687 0.7543 0.7248 0.7175 0.72170(<0.001秒) (<0.01秒) (<0.01秒) (<0.001秒) (<0.01秒) (<0.01秒)0表1.GS、MS++和α-MS++在14个数据集上基于ARI和AMI得分的比较。这些得分是在每个算法的每个数据集上调整带宽后计算的。最佳得分以粗体字体报告。与其他算法相比，GS在大多数数据集上的ARI和AMI得分最高，运行时间更快。GS比MS++和α-MS++分别快40倍和20倍。0网格单元(聚类) c(t)i∈C(t)。因此，0C(t)={c(t)1,c(t)2,...,c(t)k(t)}，并且0c(t)i∩c(t)j=φ，�i,j∈{1,2,...,k(t)},i≠j。(5)0在这里，每个活动的单元c(t)i都有一组1-邻近的活动网格单元Q(t)ci�C(t)。0定理1.对于任何给定的数据集X∈Rd，通过连续的网格单元移动估计的{C(t)}t=1,2,...达到收敛，即C(i)==C(i++),其中i是有限数。0定理2. 对于任意的 X，存在 T ∈ N，使得对于所有 t ≥T，Q ( t ) c i =  c ( t ) i，� i ∈ { 1 ,  2 , . . . , k ( t ) }。0上述两个定理证实了当活动网格单元在其1-邻域内没有其他活动成员可以进一步更新其属性时，GS在有限次迭代后达到收敛。03.2. 收敛速度0在本小节中，我们分析了GS在从高斯分布中采样的数据集的模式寻找上的行为。我们将证明活动网格单元的数量将形成一个非递增序列，并且这些活动网格单元的质心将以至少立方收敛速度收缩到分布的均值。81360令 φ ( x ;  μ,  Σ) 表示高斯概率密度函数，其中 μ 和 Σ分别是密度函数的均值和离散矩阵。为了消除对随机过程的依赖，我们考虑从密度函数 q ( x ) = φ ( x ; 0 , diag ( s 2 1, s 2 2 , . . . , s 2 d )) 生成的无限样本。0定理3. 对于数据集 X = { x 1 , x 2 , . . . , x n }，其中 x i � N(0 , diag ( s 2 1 , . . . , s 2 d ))，令质心 { c ( t +1) i } k ( t+1) i =1 � � yp ( t ) ( y | c ) dy，其中 p ( t ) () 表示 { c ( t+1) i } k ( t +1) i =1 的分布，p ( t ) ( y | c ) = k ( z  −  y )q ( t ) ( y ) /p ( t ) ( z )。则 (i)  { c ( t +1) i } k ( t +1) i =1 �0N = 0，diag �� s ( t +1) 1 � 2，...，� s ( t +1) d � 2 ��，其中0s 2 � − 1 s ( t ) j，(ii)  k ( t +1) = � d j =10� + 1 �，其中 { k ( t ) } ∞ t =1是非递增序列。0递减的序列，收敛到1。04. 实验结果与讨论0为了验证GS的有效性，我们在三个不同的场景下进行了比较实验：聚类、图像分割和目标跟踪。GS的源代码可以从以下链接下载：0https://github.com/abhisheka456/GridShift。04.1. 聚类应用0在这个实验中，我们对GS在各种聚类数据集上与MS++和α-MS++的性能进行了研究。为了公平比较，我们考虑了原始MS++论文[14]中使用的相同数据集。我们使用Cython实现了GS，并使用[14]中提供的Cython实现的MS++和我们自己实现的α-MS++进行了比较研究。在这里，我们跳过了GS和MS之间的比较，因为MS++和α-MS++已经是更快的MS变体[14,20]。我们使用以下两个指标来确定聚类结果的质量：调整互信息(AMI)[25]和调整兰德指数(ARI)[11]。这两个指标是通过将计算得到的标签与实际聚类的标签进行比较来分析聚类性能的流行方式[13]。正如前面讨论的，GS的计算复杂度与活动网格单元的数量成线性关系，并且与特征数量成指数关系。因此，我们在14个标准低维数据集上使用MS++和α-MS++实现我们的算法，数据点的数量范围从数百万到100个[14]。需要注意的是，我们的实验中排除了19个数据集中的5个，因为它们的规模非常小(小于150)。所有算法的AMI、ARI和运行时间的结果如表1所示。如图所示：0图4.在不同带宽范围内，对四个真实世界数据集上的GS、MS++和α-MS++进行比较。该图显示了所有算法在不同带宽设置下的行为。我们可以看到，尽管GS在不同带宽值上更快，但其性能优于MS++和α-MS++。0表1中，GS在大多数数据集上的运行时间比MS++和α-MS++分别快40倍和20倍，因此在聚类质量和运行时间效率方面，GS优于MS++和α-MS++。我们还分析了带宽设置对GS、MS++和α-MS++的聚类准确性和运行时间性能的影响。我们在图4中描述了这个分析的结果。如图4所示，GS在不同带宽设置下提供了比其他算法更好的聚类结果，并且运行时间更快。这个分析表明，GS比MS++和α-MS++返回更准确的聚类结果的主要原因是它按顺序更新活动网格单元的质心，在下一次迭代中生成更稳定的梯度上升移位步骤。04.2. 图像分割0在本节中，我们将GS的性能与无监督图像分割算法进行了比较。我们将以下算法视为最先进的算法：Quickshift [ 24]，SLIC ( k -means) [ 1 ]和MS++ [ 14]。对于Quickshift和SLIC，我们使用Python SciKit-ImageLi-GridShift0.031MS++2.561MS1690.213SLIC (k-meanss)0.078Quickshift28.031TrackerAUCPTrackerAUCPSupervised Learning-based TrackersGCT (CVPR, 2019)0.6470.853SiamRPN (CVPR, 2018)0.6370.851GradNet (ICCV, 2019)0.6390.861ACT (ECCV, 2018)0.6250.859Unsupervised Learning-based TrackersUSOT (ICCV, 2021)0.5890.806USOT* (ICCV, 2021)0.5740.775LUDT (IJCV, 2021)0.6020.769LUDT+ (IJCV, 2021)0.6390.843AlexPUL (CVPR, 2021)0.551–USOT-GS (Ours)0.6510.872Unsupervised Iterative-based TrackersDSST (2014)0.5180.689KCF (2015)0.4850.696MS++ (CVPR, 2021)0.3260.538GS (Ours)0.6380.86681370图5.使用ARI和FM两个流行的度量标准对BSDS500基准图像的图像分割进行了所有算法的比较。对于每个竞争者，我们分别绘制了GS获胜、竞争者获胜以及AMI和FM得分相似的情况，其中GS在大多数情况下表现优于其他算法。0brary [ 23 ]，并在这里使用了MS++的Cython实现[ 14]。在这个实验中，我们跳过了MS算法，因为MS++的性能与MS相似，但速度提高了10000倍。我们在图像分割基准数据集BSDS500上进行了实验，以定量分析GS与其他最先进算法的性能。这个基准数据集也在MS++论文[ 14]中使用过，它包含500个图像和六个不同的人工标记分割。为了进行客观比较，我们调整了图像分割（无监督）算法的所有参数，包括GS的h。对于图像分割实验，我们将所有图像转换为像素的（R，G，B）值的3维NumPy数组。我们在每个图像上实现了GS以及MS++、α-MS++、MS、SLIC和Quickshift，并分别计算了每个人工标记分割的ARI和Fowlkes-Mallows（FM）[ 9]聚类得分。为了比较，我们基于所有六个人工标记分割计算了ARI和FM的平均得分。注意，我们使用（r，g，b）输入执行了GS图像分割。然而，结果没有显著不同。因此，我们只报告了（r，g，b）情况下的结果。GS在ARI和FW方面与（r，g，b，x，y）在500个BSDS500图像中的488个和492个图像上的性能相似。在图5中，我们展示了GS与其他算法在这些得分方面的性能比较，并在表2中报告了所有算法的平均运行时间。如图5和表2所示，GS在大多数情况下提供了比其他算法更好的结果。此外，它比其他算法更快：分别比MS++、α-MS++、MS、SLIC和Quickshift快80倍、40倍、50000倍、2.5倍和900倍。04.3. 目标跟踪0本节展示了GS基于目标跟踪算法与CS和MS++的鲁棒性的比较。在这个实验中，我们考虑了[ 26]中的三个视觉跟踪器基准问题。在目标跟踪中，注意0算法平均运行时间（秒）0α-MS++ 1.2810表2.对BSDS500基准图像的图像分割算法运行时间进行了比较。GS的平均运行时间比其他竞争对手（MS++、α-MS++、MS、SLIC和Quickshift）分别提高了80倍、40倍、50000倍、2.5倍和900倍。0我们已经针对每个视频序列数据集单独调整了GS、MS++和CS的参数，而不是针对每个序列的每一帧。在图6中，我们描述了这些算法在基准问题上的性能。如图6所示，当CS周围有颜色相似的对象时，它通常无法跟踪对象。而MS++和GS不依赖周围环境，因为它们可以通过在线性时间内找到相邻的相似网格单元来调整颜色分布。因此，MS++和GS对光照和颜色的变化更具鲁棒性。然而，MS++无法适应快速移动的对象的跟踪窗口。因此，它会丢失对象或跟踪窗口会缩小。由于这个问题，MS++不适用于具有快速移动对象的实际应用。GS中的跟踪窗口自适应方案解决了这个问题。因此，GS可以通过在错过对象时更新跟踪窗口，或在场景变化时对象大小发生变化时准确地跟踪这些快速移动的对象。通过分析所有算法的性能，我们可以得出结论，GS是比MS++和CS更好的视觉跟踪器。我们还在完整的OTB100数据集[26]上进行了实验。我们在表3中详细比较了GS与最近开发的OTB100s跟踪算法的性能。根据结果，GS始终优于其他算法。此外，我们还将展示GS如何为未标记的训练数据集提供用户无关的标签。我们已将GS作为USOT跟踪器（ICCV，2021）中的候选框生成器（称为USOT-GS）进行了整合。根据表3，USOT-GS在OTB100数据集上的性能优于USOT和USOT*。GS的跟踪准确性与当前最先进的技术相媲美。0在这里，我们列出了OTB100的AUC（曲线下面积）和平均距离精度（P）在20个像素处的结果。在表3中，我们突出显示了GS与12个最先进的跟踪模型的性能。根据结果，GS始终优于其同行。此外，我们还将展示GS如何为未标记的训练数据集提供用户无关的标签。我们已将GS作为USOT跟踪器（ICCV，2021）中的候选框生成器（称为USOT-GS）进行了整合。根据表3，USOT-GS在OTB100数据集上的性能优于USOT和USOT*。GS的跟踪准确性与当前最先进的技术相媲美。Meanshift++CamshiftGridShiftMeanshift++CamshiftGridShift81380帧1 帧16 帧48 帧62 帧1260帧1 帧6 帧15 帧42 帧680图6.对均值漂移++、Camshift和GridShift在目标跟踪上的比较。在这里，Camshift在两种情况下都无法跟踪对象，因为用户必须为算法提供对象的颜色范围，以创建颜色直方图。然而，这些信息通常是不完整、有偏差和不准确的。另一方面，MS++和GS使用图像分割后找到的对象的颜色像素的网格单元。虽然MS++的性能优于Camshift，但在一些帧之后它无法有效地适应跟踪窗口，因此无法跟踪快速移动的对象。GS在两种算法中表现更好，因为它在引入所提出的跟踪窗口自适应方案后获得更好的稳定性。0由于以下原因，GS是一种比较先进的跟踪器。（1）为了在后续序列中检测目标对象，GS使用网格单元bin，该网格单元bin是对目标对象进行聚类的结果。另一方面，颜色直方图需要预先计算的掩码或完全基于用户输入的颜色范围，这可能存在缺陷甚至偏差。在这种情况下，网格单元可以作为检测目标的更好选择。（2）其次，由于GS在聚类中实现了加速，它可以通过在线性时间内找到并添加新的网格单元到参考网格单元bin中，从而适应颜色分布或场景变化，因此更具鲁棒性。（3）我们还提出了一个窗口大小自适应方案，逐渐更新窗口框，使其与对象的距离变近或变远。05. 结论0我们引入了一种简单但更快的模式寻找算法GS，用于低维大规模数据集。我们在无监督聚类和图像分割中实现了该算法。0年龄分割应用。在准确性和效率方面，GS的性能优于MS++，而GS比MS++快40倍（比MS快40000倍）。此外，GS在准确性和计算时间方面提供了比其他流行的图像分割算法如SLIC、Quickshift和Felzenszwalb更好的结果。0我们还提出了一种基于GS的新的目标跟踪算法。所提出的算法的性能优于流行的CamShift算法和MS++，因为它可以通过重新计算新帧的网格单元来有效地适应场景变化的颜色分布。因此，由于较低的计算成本和更准确的结果，GS可以应用于现代计算机视觉问题。0致谢：本研究得到了韩国教育部资助的国家研究基金会通过基础科学研究计划（2021R1I1A3049810）的支持。81390参考文献0[1] Radhakrishna Achanta，Appu Shaji，KevinSmith，Aurelien Lucchi，Pascal Fua和SabineS¨usstrunk。与最先进的超像素方法相比，Slic超像素更好。IEEE模式分析与机器智能交易，34（11）：2274-2282，2012年。1，3，60[2] John G Allen，Richard YD Xu，Jesse SJin等。使用CamShift算法和多个量化特征空间进行目标跟踪。在ACM国际会议论文集系列中，卷100，页码3-7。Citeseer，2004年。10[3] Danny Barash和DorinComaniciu。非线性扩散、自适应平滑、双边滤波和均值漂移的共同框架。图像视觉计算，22：73-81，2004年。10[4] Siavash Arjomand Bigdeli，Matthias Zwicker，PaoloFavaro和MeiguangJin。用于图像恢复的深度均值漂移先验。在NIPS，2017年。10[5] Gary RBradski。计算机视觉人脸跟踪用于感知用户界面。1998年。10[6] YizongCheng。均值漂移、模式寻找和聚类。IEEE模式分析与机器智能交易，17（8）：790-799，1995年。20[7] D. Comaniciu，V. Ramesh和P.Meer。基于核的目标跟踪。IEEE模式分析与机器智能交易，25（5）：564-577，2003年。10[8] Pedro F. Felzenszwalb和Daniel P.Huttenlocher。高效基于图的图像分割。国际计算机视觉杂志，59：167-181，2004年。1，30[9] Edward B Fowlkes和Colin LMallows。比较两个分层聚类的方法。美国统计协会杂志，78（383）：553-569，1983年。70[10] Dong Huang，Chang-Dong Wang，Jian-ShengWu，Jian-Huang Lai和Chee-KeongKwoh。超可扩展谱聚类和集成聚类。IEEE知识与数据工程交易，32（6）：1212-1226，2