基于随机森林和随机游走的交互式图像分割
作者: 吕律
摘要:基于随机游走的交互式图像分割在计算相邻像素相似度时,仅考虑了颜色空间的差异。针对这一问题,利用图像中广泛存在的对称结构,提出一种基于随机森林进行对称检测的方法。通过基于相似边的特征,将对称检测转化为结构化标签问题。在得到对称轴的基础上,通过期望最大算法,建立对称轴与相邻像素之间的关系,以提高交互式分割的精确度。实验表明,该方法不仅能有效地提取图像中的对称轴,而且能得到较高精度的交互式分割结果。
关键词:交互式图像分割;随机森林;随机游走;对称检测;期望最大算法
中图分类号: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]的权值计算如下: