论文解读：Adaptive Nonlocal Random Walks for Image Superpixel Segmentation

论文链接：
DOI：10.1109/TCSVT.2019.2896438

提出了一种新的基于自适应非局部随机游走(ANRW)算法的超像素分割方法。
图像超像素分割算法主要有三个步骤（方法基于随机游走模型）：
第一步，通过基于梯度的方法产生种子点来生成初始超像素。
第二步，提出了ANRW算法，通过调整非局部随机游走(NRW)来获得初始超像素，以获得更好的图像分割和超像素分割。
第三步，将这些小的超像素进行合并，得到最终规则且紧凑的超像素。
实验验证，与现有的方法作比较，有更好的超像素性能。

超像素是一种对颜色、纹理等特征相似的像素进行聚类的图像分割方法。例如使用超像素而不是像素作为预处理步骤来加速图像应用的计算。
处理视频帧之间的关系，如果直接以像素作为基本处理单元，会耗费大量的时间，需要很大的存储空间。采用超像素作为预处理单元，可以减少计算时间和内存。然而，如果一种超像素方法没有很好的规则性和边界依附性，就会对像素级的精度性能产生负面影响。

现有的超像素算法：
归一化切割、基于图的分割、伪布尔优化(PB)、熵率超像素分割(ERS)、Turbo-Pixel、懒惰随机游走(LRW)、FastSCSP、SLIC和超快通过量化的超像素提取（USEQ）。

超像素分割算法难点：
提出一种形状规则、边界粘附性好的图像超像素方法仍具有挑战性。

随机游走方法的好处特点：
与其他超像素分割方法相比，随机游走考虑了相邻像素之间的关系，能够处理复杂的纹理信息和弱边界。然而，这些基于随机游走的算法的性能对初始种子点很敏感，即靠近种子的空间点往往比远离种子的空间点与种子的相似度更高。

NRW的不足
针对以往基于随机游走的超像素分割算法的不足，提出了一种基于ANRW的超像素分割算法。ANRW是基于非局部随机游走(NRW)的一种新的随机游走方法。NRW算法不仅可以像大多数随机游走算法一样保证平坦区域的均匀性，而且可以利用K-近邻(KNN)链接点来探索像素和种子之间的全局关系。KNN链接可能会在超像素分割中产生许多小部分，这是由全局链接引起的。

ANRW的改进

• 一是基于梯度的种子生成方法。对种子进行均匀采样，以保持形状规则的超像素。然后根据像素的梯度，将种子调整到均匀区域，避免了种子落入边界造成的边界丢失。
• 二是调整NRW的转移矩阵。希望确保边界上特征完全不同的两个像素不落入同一个超像素，因此我们降低了相似度较低的像素对的过渡可能性(从一点到另一个像素)。该行动可在大多数边界上加设“屏障”，以加强边界，并阻止随机行走的人穿过边界。通过调整NRW的转移矩阵，我们的方法即使在一些弱边界上也能达到更好的边界粘附性，并且结果对种子不那么敏感。最后一种是融合方法来细化小尺寸的超像素。我们采取从粗到精的策略，首先将局部区域内最相似的小部分合并到最相似的大部分中，然后将剩余的极小部分随机合并到相邻的大部分中。
• 三是给出了图1中的四个超像素结果，表明所提出的算法对于复杂形状的目标具有良好的边界粘附性。

图1.我们的ANRW的超像素结果。这里，从上到下，超像素的数量大约是200和600

本文的主要贡献如下：

• 提出了一种新的自适应非局部随机游走(ANRW)算法，该算法考虑了像素间的全局关系，增强了超像素分割的边界。
• 提出了一种新的基于梯度的种子生成方法，以保持超像素的规则性，减少边界丢失。
• 提出了一种新的超像素细化方法，采用由粗到精的策略对较小的超像素进行合并。

• 第一类，基于聚类方法，如归一化切割(NCuts)、基于图的分割、SLIC和Turbo像素。
• 第二类，基于优化方法，如图割、格割、PB、ERS和USEQ。
• 第三类，基于其他模型，如FastSCSP、LRW和DBSCAN。

但以上方法都分别由不足之处。

SubRW和NRW
传统的随机游走方法只利用局部邻域构造转移矩阵，这就是随机游走模型对种子点非常敏感的原因。亚马尔可夫随机游走(subMarkov Random Walk，SubRW)模型是通过在图中添加一些辅助节点，利用这些辅助节点，加入一些先验信息，以获得更好的图像分割结果，这些辅助节点可以帮助像素与不相连的点建立关系，但是先验信息的加入比较困难，不能直接应用于超像素分割。与SubRW相比，NRW在随机游走中加入了KNN方法。具体地说，它使用KNN来寻找与整个图像中的像素信息相似的点。这些点称为像素的KNN链接或非本地邻居。在超像素分割中，这种非局部邻域可以减少种子点对分割结果的影响。

1. 生成基于梯度的初始种子；
2. 通过ANRW得到初始超像素；
3. 通过局部合并操作来提炼超像素。

符号表示
N1表示所需的超像素数。[h，w]表示输入图像的大小。n=h×w是输入图像中的像素数。x_k(k=1，2，···，N)表示图像中的像素，对应的坐标为[hx_k，wx_k]。

初始种子
使用所有像素的梯度来帮助我们选择种子，每个像素都有可能被选为种子，这可以使大部分种子处于平滑区域。
将图像分割成N1个均匀的部分，并用part_i(i=1，2，···，N₁)来表示每个部分。然后选择每个零件中心的点作为初始种子点。定义S={S₁，S₂，···，S_N1}为初始种子点集合，其中SIIS位于局部，坐标为[hs_i，ws_i]。然后计算图像中每个像素的梯度，其中[hg’(X_k)，wg’(X_k)]表示像素xk的梯度的绝对值。我们用[hg(X_k)，wg(X_k)]表示x_k及其8个邻近点之间的梯度绝对值之和，它可以反映x_k周围一小部分的光滑性。设计了一个函数f(X)来计算每个点的得分，并用得分来选择最终的种子点S’。

其中α是平衡gra(X_k)和dis(X_k)的值的常量。gra(X_k)是使种子点位于平滑区域的约束。dis(X_k)是使种子点尽可能靠近每个部分的中心(即初始种子的位置)以获得规则的超像素形状的约束。DIS(X_K)和α还保证同一部分的所有分数都不同。我们根据以下规则选择最终的种子：如果f(X_k)是Parti中得分最小的，则选择x_k个∈粒子作为Part_i的种子。主要步骤总结在算法1中。

初始种子点和最终种子点的示例如**图2(A)和(B)**所示。

超像素初始化
首先在给定的图像I(x)上定义一个图G=(V，E)，它表示一个包含一组节点V和边E⊆V×V的加权图。然后，每个像素x_i由我们的无向图中的顶点v_i∈V唯一地表示，其中对于v_i上连接的所有边，每个顶点的度计算为d_i=P_jω_ij。边权重ω_ij衡量两个相邻节点V_i和V_j之间的相似度。与NRW不同的是，我们对NRW中的边权重进行了一些调整。我们将NRW中的边权重表示为ω’_ij，它由下式获得下面的高斯权重函数：

其中g_i和g_j表示两个节点V_i和V_j处的图像强度值，σ是用户定义的参数。µ是一个小常数。ω’_ij的取值介于0和1之间，这意味着当ω’_ij=1时，x_i和x_j具有相同的图像强度值。
为了减少物体边界落在超像素内部的情况，我们设计了一种自适应调整策略来提高边界粘附性。我们用NKIND表示ω0的不同值的个数，用ω0排序以升序表示这些值。如果N_kind较大，则反映图像中有大量具有不同颜色的点。我们将使用ω’排序的中值来生成最终的边权重ω。我们将自适应ω定义如下：

其中λ和δ是常量。该策略不仅大大降低了随机游走过程中越过边界的可能性，而且降低了种子的敏感度。图3给出了两个超像素分割结果。我们可以看到，我们的调整方法可以帮助我们检测到更多的边界，并获得更好的边界粘附性。

ANRW包含与NRW中的KNN链接边相同的另一种边权重。对于KNN-连接边e_ij，我们用ω_ij^KNN表示。当超像素的大小较小时，使用过多的kNN链接点可能会生成错误的边界。否则，当超像素的大小较大时，使用较少的kNN链接点将会错过一些边界。然后，提出了一种根据超像素大小自适应选择k近邻连接点个数的方法。在实验中，我们选择了$\sqrt {N/N1}$N/N1​的KNN连接点。我们使用像素x_i的特征向量V_i来计算KNN权重，如下所示：

用VL-FEAT中的快速近似最近邻库(FLANN)来计算特征空间中的KNN。FLANN首先根据图像建立k维树(k-d树)，然后利用k-d树寻找kNN点。非局部权重ω_ij^KNN定义为：


对于像素X_i，kNN连接点可能离它很远，所以我们不仅要考虑颜色的相似性，还要考虑它们之间的空间距离。图4中示出了KNN链接点和本地邻居，其中例如仅示出了4个KNN链接点。然后，我们使用E⁸来表示8-相邻像素，E^KNN表示KNN链接。我们定义边权重矩阵W={ω_ij，ω_ij^KNN}如下：

将局部权值乘以10的目的是为了确保具有相似特征的局部邻居比kNN具有更强的影响力。根据对文献用于图像分割的随机游动(Random walks for image segmentation)、基于约束拉普拉斯优化的交互式分割(Interactive segmentation using constrained Laplacian optimization)中随机游动算法的分析，我们将组合拉普拉斯矩阵L定义为：

狄里克莱问题公式定义为：


经过上面的步骤，得到了像素属于种子点的概率X^u。概率表示像素与种子的相似性。然后，我们为种子分配不同的标签，并将相同的标签分配给所有种子中概率最大的未标记像素。在分配标签之后，我们得到了初始超像素。算法2总结了主要步骤。

优化初始超像素

自适应非局部随机游走可能会生成大量较小的超像素，并且它不强制超像素的连通性。如图5所示，我们有两种不同的方式(图5(B)和图5©)来合并**图5(A)**右上角的像素。请注意，随机合并小部件会降低性能。因此，我们提出了一种由粗到精的方法来细化初始超像素。我们首先根据颜色和位置信息对小部件进行重新分配。在这一阶段，大多数小部分可以合并成与它们最相似的超像素，但少数非常小的部分仍然需要合并。现在我们可以直接将这些部分随机合并到与其相邻的超像素中，因为这样的小部分对结果没有太大影响。

在第一个合并阶段，我们定义了两个常量，如下所示：
其中，PA2是正则超像素的近似面积，Areathresh是区分连通部分的阈值。如果一个超像素的像素数小于面积，我们就把这个超像素看作是一个小的超像素，需要合并成一个较大的超像素。

图5(A)的重新标记结果如图6所示。重新标记超像素后，我们开始合并小部分。我们将重新标记的连通部分分为区域和区域两类。如果一个连通的点的数量部分小于面积，我们将其分配到集合区域中，否则我们将其分配到另一个集合区域中。

将区域中的所有部分合并成区域，将面积(K)表示为面积的一部分，并使用属于面积(K)的像素的色距(K)和坐标

参数分析
将α设置为0.5时，是希望平衡渐变对种子选择的影响。将2σ