基于随机森林和随机游走的交互式图像分割

摘要：基于随机游走的交互式图像分割在计算相邻像素相似度时，仅考虑了颜色空间的差异。针对这一问题，利用图像中广泛存在的对称结构，提出一种基于随机森林进行对称检测的方法。通过基于相似边的特征，将对称检测转化为结构化标签问题。在得到对称轴的基础上，通过期望最大算法，建立对称轴与相邻像素之间的关系，以提高交互式分割的精确度。实验表明，该方法不仅能有效地提取图像中的对称轴，而且能得到较高精度的交互式分割结果。

关键词：交互式图像分割；随机森林；随机游走；对称检测；期望最大算法

中图分类号：TP391.41        文献标识码：A

文章编号：1009-3044（2023）31-0014-04

开放科学（资源服务）标识码（OSID）

0 引言

图像分割是图像处理的基础性问题，是图像理解的基石，可以被应用于自动驾驶系统中的街景识别与理解，无人机系统中的着陆点识别[1]。近几年基于深度学习的语义分割（semantic segmentation） ，即对图像中表达的语义（不同的物体）进行分割，取得了很高的精确度[2]。但是对于下面2种情况，如果没有人的交互，还是很难达到满意的效果。1） 在背景比较杂乱的情况下，图像中的物体有很多细小的枝节（如图1中的鹿角）；2） 需要将物体的不同部分进一步划分（如图1的鹿头和黑色的颈部划分为同一个部分）。交互式图像分割正是研究解决这一类问题的方法。

交互式图像分割与图像分割的区别在于，需要人在图像中用不同颜色标注出需要分开的区域[3]，如图1中不同颜色的点（黄色和绿色点），下文称之为交互点。因为深度学习是一种端到端的学习方法，现有的深度学习方法还没办法处理交互点这种先验知识[4]。现有文献也没有采用深度学习方法进行交互式图像分割，所以本文提出的是一种基于随机游走（random walk） 的方法。

现有基于随机游走的交互式图像分割方法是一种非监督的分割方法，根据图像中相邻像素的相似度计算转移概率矩阵，当随机游走达到稳定时，得到图像中的像素所对应的人工标注[1]。虽然图像分割是一种非监督的问题，但是利用图像中的对称结构，可以提高分割的效果。如图1所示，人工标注的点，落在了对称区域（鹿角的主干，鹿的颈部），该区域可以作为人工标注处理，与该区域相邻点的相似度也应该相应提高。所以将人工交互点扩展到这些交互点所在的对称区域，直观上通过增加了交互点的数量，应该能提高分割的精度。现有的交互式图像分割文献，并没有利用图像中的对称性进行分割，于是本文提出一种基于对称区域改进现有的随机游走方法，并通过实验表明比现有方法的结果更好。

对称检测在图像处理中不是一个热门的研究领域，相关的文献比图像分割要少得多[5]。这些研究的共同特点是提出不同的图像特征，基于这些特征计算图像中的对称轴。现有的数据集SYMMAX-300[5]，数据量很小，不适合深度学习方法（关于利用深度学习方法处理交互式图像分割和对称检测，本文在最后一节结束语，作为未来的研究进行讨论）。通过仔细分析这些文献中的图像特征，可以发现现有方法并没有考虑对称区域的边界的相似性（如图2（a） 边ab与cd） 。本文提出的方法利用相似边界等多种特征，改进了随机森林算法进行对称检测，最后通过实验证明，比现有方法的结果更好。综上所述本文的工作有以下2点：1） 通过图像中的相似边等多种特征，改进随机森林算法得到对称轴；2） 利用对称区域，改进随机游走算法得到图像的分割区域。

1 基于随机森林的对称检测

本节首先介绍现有的对称检测方法，然后介绍本文改进的对称检测方法。

1.1 现有对称检测方法

在现有关于对称检测的文献中，SYMMAX-300[5]是广泛被使用的数据集。这些研究的共同特点是通过以下2步检测图像中的对称信息：1） 提取不同的图像特征；2） 基于标注了对称信息的数据集和1中提取的特征，通过不同的学习算法得到对称模型。现有文献中用的特征主要有：尺度不变特征变换（Scale-invariant feature transform，SIFT） 特征：图形的颜色、材质等特征。其中Tsogkas等人提出的一种专门针对对称问题的直方图特征[5]，因为1.2节本文方法用到了这种特征，所以简要介绍一下。

以图像中的点（x，y）为中心作边长为a的正方形区域，并分割成三个相邻的面积相等的矩形，即矩形的边长为a和a/3。对于任意两个矩形，可以定义相异度函数[DHi，j（x，y）]（该相异度函数就是直方图特征）：

[DHi，j=12t（Ri（t）-Rj（t））2Ri（t）+Rj（t）]            （1）

其中，[i，j∈{1，2，3}]表示三个矩形的标号。[Ri]、[Rj]分别表示矩形i和矩形j区间中的直方图（histogram） ，t是直方图中的分组数，实验中t=64。

1.2 基于随机森林的对称检测

从前面对直方图特征的介绍可以知道，因为计算的是矩形区域，所以现有方法没有考虑到对称区域的边界是相似的（图2（a） 中边ab，cd，中间的实线是对称轴），并且相似边到对称轴区域的颜色，材质是相似的（图2（a） 中区域abs2s1，区域cds2s1） 。本节方法的第1个贡献是提出多种基于相似边的特征。随机森林是利用多种特征进行分类、回归较好的方法[6]，但是对称轴是1条曲线（图2是示意图，简化为直线），不是简单的分类数值，或者回归数值，本节方法的第2个贡献是提出一种方法，改进随机森林，计算对称轴这种结构化的目标。

1） 基于相似边的特征。现有的数据集（SYMMAX-300） 只包含对称轴信息，如果人工提取对称轴相应的相似边数据，不仅困难而且非常费时。所以，本方法利用相似边与对称轴的关系，去掉明显不相似的边，从而得到基于相似边的特征。

图2（a） （b） 是数据集中2种主要的对称模式，相似边（ab，cd） 反转对称，相似边（ef，gh） 平移对称，对称轴窗口取8×8像素，所以对称轴都是弧度较小的曲线或者近似的直线。首先构造候选区域，先通过现有边缘检测方法提取对称轴两侧的边，下文称之为候选边，分别连接候选边的两个端点得到两条直线（ac，bd） ，对称轴至少要与其中1条相交。当与两条直线相交时（如图2（a）） ，区域abs2s1和区域cds2s1是候选区域；当只与1条直线相交时（如图2（b） 中间实线是对称轴，虚线是延长线），区域efs4s3和区域ghs4s3是候选区域。候选区域的面积是第一种特征。

过候选边上一点（如图2（a） 点k） 做垂直于对称轴的线段作为距离di（如图2（a） kl） ，平均距离[d=i∈Edi/|E|]是第2种特征，其中，[i∈E]表示边E上所有的点，|E|表示边上所有点的个数。

将候选边所在窗口（8×8像素）中的边自上而下扫描，每1行向左和向右扩大1个像素，即将边变粗，变粗后的边的面积为S1和S2。该面积是第三种特征。

将不满足下面三个条件的候选边去掉，剩下的就是相似边：

[|A1-A2|min{A1，A2}<20% ，       |d1-d2|min{d1，d2}<20% ， ]

[max{S1⋂S2}min{S1，S2}>70%]   （2）

其中，A1、A2表示对称轴两侧候选区域的面积，d1、d2表示对称轴两侧候选区域的平均距离，[max{S1⋂S2}]表示S1、S2分别反转和不反转共4种情况下最大的相交的面积。

训练模型时，对称轴是已知的。但是测试时，对称轴是要计算的目标未知。这时已知的是8×8像素区域，计算对称轴是否在这个区域。分别连接候选边的2个端点构造直线L1、L2，然后连接L1和L2的中点，以这条线为对称轴，并通过（2） 式中3个条件得到相似边。

通过（2） 式去掉不相似的候选边后，剩下的候选边即相似边，该相似边对应的候选区域即为对称区域。连接相似边的中点和对称轴上任一点的距离记为ds（如图2（a） 中ms的距离），这是第4种特征。ds与水平线的夹角[α]是第5种特征。分别连接相似边两个端点和对称轴上任一点围成的区域是第6种特征（如图2（a） 中区域csd） 。基于第6种特征区域，可以得到相应的颜色，材质的直方图特征（第7种特征），即[DHLi，j]、[DHai，j]、[DHbi，j]、[DHti，j] （其中L、a、b分别是CIELAB颜色空间中的L、a、b信息，t是材质）。材质t的计算采用文献[7]中的方法。

2） 计算对称轴。前面已经介绍了对称轴（如图2（a）） 所示是一条曲线，既不是分类数值，也不是回归数值。通过分析对称轴数据集，可以发现非水平对称（如图2（a） 所示）的情况下，每行只占1个像素值。水平对称是指对称轴是一条水平线，这时每列只占一个像素。图2（c） 将对称轴所在的8×8像素目标区间按行分为8行，或者按列分为8列。所以计算对称轴相当于在每一行（或者一列）8个像素中找出对称轴的那个像素，即分类问题。于是可以将对称轴所在区域（8×8像素）分为按行或者按列划分两种情况，每种情况根据不同的行（列）建立相应的随机森林模型。下面，首先给出按行或者按列进行计算的判定条件。

训练时，因为对称轴是已知的，连接对称轴两个端点所得直线与水平线的夹角[β]，[β>20°]按行计算，否则按列计算。测试时，因为对称轴未知，连接相似边两个端点所得直线与水平线的夹角[γi]，[i∈SEγi/|SE|>20°]按行计算，否则按列计算，其中[i∈SE]表示该对称轴对应的所有相似边，|SE|表示相似边的个数。

对于第i行（或者第i列），针对不同行（列）构造相应的特征。基于第3、4、5、6、7种特征，构造随机森林中每一个节点的函数：

[h（x，θj）=[f（x，k）<τ]， θj=（k，τ），k=3，4，5，6，7f（x，3）=max{S1⋂S2}min{S1，S2}， f（x，4）=|ds1-ds2|min{ds1，ds2}，f（x，5）=|α1-α2|min{α1，α2}， f（x，6）=|AS1-AS2|min{AS1，AS2}，f（x，7）=DH*i，j， *=L，a，b，t]   （3）

其中，[.]是指示函数，[τ]表示阈值，k对应第几种特征。训练决策树时，对于一个节点和训练集[Sj⊂X×Y]，目标是找到[h（x，θj）]中的[θj]能够很好地将数据进行划分。数据划分的标准是信息增益：

[Ij=H（Sj）-k∈{L，R}SkjSjH（Skj）]   （4）

其中，[SLj={（x，y）∈Sj|h（x，θj）=0}]，[SRj=Sj＼SLj]，[H（S）=-ypylog（py）]，py表示S中标记为y的概率。通过最大化Ij可以计算出[θj] 。

2 基于随机游走的交互式图像分割

本节介绍利用前面得到的对称轴与相似边，对传统随机游走模型进行改进。

Grady对于交互式图像分割问题，首先提出随机游走算法[8]。他通过无向图[G=（V，E）]对图像进行建模，其中节点[v∈V]，边[e∈E⊆V×V]。每一个节点[vi]代表图像像素[xi]，边[eij]表示[vi]与其相邻的8个节点[vj]构成的边，[wij]表示随机游走通过边[eij]的权值。

[wij=exp（-||Ii-Ij||2σ）]   （5）

其中，[Ii]和[Ij]分别表示节点[xi]和[xj]对应于CIELAB颜色空间的值。实验中[σ]是控制参数，令[σ=22]。D是对角矩阵，其中[Dii=di]，[di=j～iwij]表示节点[vi]的度， [i～j]表示与[vi]相邻的节点[vj]。因为在第1节计算得到对称轴和相似边，当交互点落在对称区域（图2（a） 区域abdc） ，该区域的所有点被作为交互点处理（即具有相同的标签）。并将对称区域的面积（区域中的像素个数）增大1倍，相应区域记为V，区域V中节点[vi]到[vj]的权值计算如下：