一种联合像素与超像素的交互式图像分割方法

技术领域

本发明涉及图像处理技术领域，具体涉及一种联合像素与超像素的交互式图像分割方法。

背景技术

图像分割是图像处理中的一个基本问题，其主要目的是将感兴趣目标从复杂背景中提取出来，以便进行目标检测、跟踪、识别以及场景分析等，在模式识别与计算机视觉等领域中有着十分广泛的应用。根据用户是否提供先验知识，可将图像分割方法分为自动分割方法和交互式分割方法。对于那些类型多样、内容复杂的自然图像，交互式分割方法使得分割结果更符合并且能够直接反应用户的主观意愿，因此逐渐被受到重视。其中，GraphCut交互式分割方法因其具有全局最优、数值鲁棒性强、执行效率高、分割加权图的拓扑结构自由以及N-D图像分割能力等，而获得了研究者们的广泛关注。

一个优秀的交互式图像分割系统必须满足尽量少的用户交互、尽量短的反馈时间以及尽可能准确的分割结果等条件。GraphCut算法是将像素点作为节点构建一个加权有向图，然后利用最大流最小割算法进行全局求解。遗憾的是，该算法仅利用图像灰度信息，而未考虑颜色信息，以致当图像内容较复杂时，其分割结果并不理想；然而当前景和背景在灰度信息上十分接近时，为获得理想的分割结果GraphCut算法通常需要用户输入大量的交互信息；此外，由于是将像素点作为节点，随着图像尺寸的增大，由此构建的图模型中的节点数目大幅度增多，从而导致最大流最小割算法的执行需要耗费大量时间。针对这些缺点，Li等人提出了Lazy Snapping分割算法。该算法首先采用分水岭(WaterShed)算法对图像进行预分割，将分割区域作为节点重新构建一个加权有向图，然后采用最大流最小割算法进行全局求解，最后再采用一套手动调整方案使得分割结果更为准确。美中不足的是，该算法也存在几个主要问题：由于WaterShed算法仅利用灰度图像的梯度信息，过分割现象严重，并且其预分割结果中的区域数仍然较多；该算法利用颜色均值表征每个区域，这种表示方式过于简单，无法准确表示每个区域的颜色分布；在建模过程中选用了较为简单的K-Means聚类算法，其聚类效果受初始条件及干扰因素影响较大；在交互过程中该算法需要大量的粗调和微调操作，使得整个交互过程过于繁琐等。

相对WaterShed算法而言，MeanShift分割算法借助其优秀的分割性能而得到了更为广泛的研究及应用。该算法充分利用了颜色信息，其过分割现象较轻，并且分割区域数得到了明显减少。Ning等人利用MeanShift算法进行预分割，并采用颜色直方图表示每个区域，提出了一种基于最大相似度的区域合并(MSRM)算法。不同于最大流最小割算法，MSRM算法利用一种区域自动合并机制完成了彩色图像分割。但本发明的发明人经过研究发现，该算法仅考虑区域间的相似度，而未考虑各区域与交互信息间的相互关系，并在区域合并过程中需要多次统计区域颜色直方图以及多次计算区域间的相似度，使得整个算法的时空开销较大；另外，MSRM算法没有考虑MeanShift算法的过分割问题，因此在目标边缘存在着大量误分割。

为简化用户交互过程，Rother等人提出了GrabCut算法。该算法根据用户标记的矩形区域建立初始前景和背景模型，由于矩形区域内部同时包含前景信息和背景信息，因此该算法通过迭代以学习的方式来不断更新前景和背景模型，直到全局求解得到的能量收敛时迭代停止。但本发明的发明人经过研究发现，由于GrabCut算法仅确定出背景区域，而没有准确确定出前景区域，因此初始背景模型建立准确与否将直接影响最终的分割结果。

因此，针对前述方法存在的一些问题，设计一种高效而精准的交互式图像分割方法显得尤为重要。

发明内容

针对现有图像分割方法中存在的技术问题，本发明提供一种联合像素与超像素的交互式图像分割方法，该方法通过将像素信息和超像素信息有机结合，来提高现有交互式图像分割方法的执行效率，以及在尽量少的用户交互条件下获得更为准确的分割结果。

为了解决上述技术问题，本发明采用了如下的技术方案：

一种联合像素与超像素的交互式图像分割方法，该方法包括以下步骤：

S1、采用MeanShift算法对输入图像进行预分割，以完成超像素提取，并采用颜色直方图对每个超像素进行建模，以准确表示超像素的颜色分布；

S2、根据用户输入的交互信息，以超像素为节点建立图模型，并采用最大流最小割算法进行全局求解，以完成超像素级分割过程；

S3、在超像素级分割结果的基础上，采用形态学操作在目标边缘构造一个窄带区域；

S4、在构造好的窄带上为前景和背景区域分别建立相应的前景和背景模型，并对窄带区域以像素点为节点建立图模型，最后再次采用最大流最小割算法进行全局求解，以完成像素级分割过程。

进一步，所述步骤S2包括以下步骤：

S21、由用户输入交互信息，标记为目标的超像素集合记为F，标记为背景的超像素集合记为B，未标记超像素集合记为U；

S22、将步骤S1中得到的预分割图像以超像素为节点表示成一个有向加权图G＝(V,E,W)，其中V表示图中节点的集合，对应图像中的每个超像素；E表示图中边的集合，对应图像中连接相邻超像素间的边；W表示图中边的权重，用于表示相邻节点被划分到同一类属的倾向程度；对于任意两相邻超像素i和j，利用其颜色直方图，采用巴氏距离计算其相似度δ(i,j)，并用于表示该两相邻超像素边的权重；

S23、根据用户输入的交互信息采用颜色直方图分别对前景和背景进行建模，并构造两个虚拟节点：对应前景模型的source节点和对应背景模型的sink节点；其中，集合V中的任意节点与source和sink节点所形成边的权重分别表示该节点隶属于前景和背景的倾向程度；对于未标记超像素i，利用其颜色直方图，采用巴氏距离分别计算其与source节点和sink节点的相似度δ(i,F)和δ(i,B)；

S24、针对上述图模型，定义如下能量函数：

其中，第一项为区域信息项，用于度量各超像素与交互信息间的相似程度；第二项为边缘信息项，用于度量超像素间的相似程度；区域信息项和边缘信息项的定义分别如下：

b(ι_i,ι_j)＝λ·δ(i,j)>

其中，ι_i表示节点i的类属编号，ι_i＝1对应于前景，ι_i＝0对应于背景，表示超像素节点的邻域集合，λ为控制参数；

在以上建立好的图模型基础上，执行最大流最小割算法即可获得基于超像素级的全局最优解。

进一步，所述步骤S3包括以下步骤：

S31、记由步骤S2分割得到的二值图像为S，通过对二值图像S进行形态学腐蚀操作，即可得到仅含目标的区域S_F＝SΘb，相应像素集合记为TrimapForeground；其中b为(2d+1)×(2d+1)大小的正方形结构元素，式中d为正整数；

S32、对二值图像S进行形态学膨胀操作，并与目标区域S_F做差运算即可得到一个同时含有目标和背景的窄带区域S_U＝(S⊕b)-(SΘb)，相应像素集合记为TrimapUnknown；

S33、仅含背景信息的区域可表示为S_B＝S-(S_U+S_F)，相应像素集合记为TrimapBackground，这样就可以得到一个三元掩模图像，其中包括已建立好的窄带区域S_U。

进一步，所述步骤S4包括以下步骤：

S41、将步骤S3中得到的目标区域S_F和背景区域S_B分别看作虚拟source节点和虚拟sink节点，然后采用主成分分析法分别对其建立前景混合高斯模型和背景混合高斯模型，高斯个数均设为K；

S42、以像素点作为节点对步骤S3中得到的窄带区域建立图模型，并对式(5)能量函数中的区域信息项和边缘信息项进行如下重新定义：

其中，dist(i,j)表示像素点i和j的空间距离，I_i表示像素点i的颜色信息，I_j表示像素点j的颜色信息，在建立图模型过程中采用8邻域，因为λ≥b(ι_i,ι_j)，所以可取κ＝8λ+1；参数σ用来控制颜色信息差异程度，D_x(i)表示第i个像素点在前景或背景模型中分布情况，其中x∈{F,B}，其值可从下式计算得到：

其中，表示在前景或背景的混合高斯模型中第k个高斯分布所占权重，和分别表示前景或背景模型中第k个高斯分布的均值和协方差矩阵，表示协方差矩阵的行列式；

在以上建立好的图模型基础上，执行最大流最小割算法即可获得基于像素级的全局最优解。

与现有技术相比，本发明提供的联合像素与超像素的交互式图像分割方法具有以下优点：

第一、本发明采用MeanShift算法进行预分割，由此构造的有向图其节点数目得到大幅度减少，从而有效提高了最大流最小割算法的执行效率；对于每个超像素，采用了更为有效的颜色直方图表示方式，并且前景和背景模型同样采用颜色直方图来表示，而不再需要进行额外的建模过程；另外，由于超像素为用户交互提供了指导信息，以致本发明仅需少量的交互信息并在较短时间内即可得到比较理想的分割效果。

第二、在建立图模型的过程中，本发明不仅考虑到了区域间的相似程度，而且还考虑到各区域与前景和背景间的相似程度，由于充分利用了交互信息，因而使得分割结果更为准确；另外，各相邻区域间的相似度仅需计算一次，然后交由最大流最小割算法进行处理，以得到超像素级分割结果，从而使得本方法的时空开销得到了进一步大幅度降低。

第三、由于MeanShift算法在分割过程中难免存在边界泄露问题，导致部分分割区域同时跨越前景和背景两部分以致出现误分割，本发明利用形态学操作在超像素级分割结果边缘部分构造一个窄带区域，然后对该窄带区域以像素为节点建立图模型并执行最大流最小割算法，从而有效提高了边缘部分分割精度。

附图说明

图1是本发明提供的联合像素与超像素的交互式图像分割方法流程示意图。

图2是本发明提供的在超像素级分割结果基础上建立窄带区域的示意图。

图3是本发明提供的对Flower图像由用户输入的交互信息示意图。

图4是本发明提供的对Flower图像分别采用GraphCut、Lazy Snapping、GrabCut、MSRM和本发明提供方法所得到的分割效果图。

图5是本发明提供的对Dogs图像由用户输入的交互信息示意图。

图6是本发明提供的对Dogs图像分别采用GraphCut、Lazy Snapping、GrabCut、MSRM和本发明提供方法所得到的分割效果图。

具体实施方式

为了使本发明实现的技术手段、创作特征、达成目的与功效易于明白了解，下面结合具体图示，进一步阐述本发明。

请参考图1所示，本发明提供一种联合像素与超像素的交互式图像分割方法，该方法包括以下步骤：

S1、采用MeanShift算法对输入图像进行预分割，以完成超像素提取，并采用颜色直方图对每个超像素进行建模，以准确表示超像素的颜色分布。作为具体实施方式，输入一幅彩色图像，采用MeanShift算法对其进行预分割从而获得超像素；由于每个超像素的区域面积相对较大，因此本发明采用颜色直方图对每个超像素进行建模，以准确表示超像素的颜色分布情况。设颜色直方图大小为n³，对于彩色图像I中的任意像素点p＝(x,y)，其像素值记为I(p)＝(r,g,b)，对其量化后新的颜色值表示为：

I′(p)＝(r/l)·n²+(g/l)·n+(b/l)>

其中，/为取整操作，本实施例中n取16即可获得较好的结果。

然后统计每个超像素(假设编号为i)中所有像素点量化后颜色值k＝I′(p)出现的次数L_i(k)，其中k∈[0,n³)，并对其归一化后即可得到最终的颜色直方图H_i，相应的颜色值k对应直方图值H_i(k)计算如下：

其中N_i为第i个超像素中的像素总数，即

S2、根据用户输入的交互信息，以超像素为节点建立图模型，并采用最大流最小割算法进行全局求解，以完成超像素级分割过程。作为具体实施例，所述步骤S2包括以下步骤：

S21、由用户输入交互信息，标记为目标的超像素集合记为F，标记为背景的超像素集合记为B，未标记超像素集合记为U；

S22、将步骤S1中得到的预分割图像以超像素为节点表示成一个有向加权图G＝(V,E,W)，其中V表示图中节点的集合，对应图像中的每个超像素；E表示图中边的集合，对应图像中连接相邻超像素间的边；W表示图中边的权重，用于表示相邻节点被划分到同一类属的倾向程度；

对于任意相邻超像素i和超像素j，其颜色直方图分别为H_i和H_j，本发明采用巴氏距离计算其相似度，并用于表示该两相邻超像素边的权重：

其中δ(i,j)越大，表示超像素i和超像素j的颜色直方图越相近，对应两区域也就越相似，则超像素i和超像素j属于同一类属的概率也就越大，否则超像素i和超像素j属于同一类属的概率也就越小。

S23、根据用户输入的交互信息采用颜色直方图分别对前景和背景进行建模，并构造两个虚拟节点：对应前景模型的source节点和对应背景模型的sink节点；其中，集合V中的任意节点与source和sink节点所形成边的权重分别表示该节点隶属于前景和背景的倾向程度。对于用户提供的交互式信息即目标F和背景B，采用步骤S1中的颜色直方图分别对其建立目标和背景模型，记为H^F和H^B。

对于未标记超像素i，利用其颜色直方图，分别计算其与source节点和sink节点的相似度，这里同样采用巴氏距离来分别计算与目标F和背景B的相似度：

S24、本发明不仅考虑超像素间的相似性，而且还考虑了各超像素与交互信息的关系，因此针对上述图模型，定义如下能量函数：

其中，第一项为区域信息项，用于度量各超像素与交互信息间的相似程度；第二项为边缘信息项，用于度量超像素间的相似程度；区域信息项和边缘信息项的定义分别如下：

b(ι_i,ι_j)＝λ·δ(i,j)>

其中，ι_i表示节点i的类属编号，ι_i＝1对应于前景，ι_i＝0对应于背景，表示超像素节点的邻域集合，λ为控制参数；

在以上建立好的图模型基础上，执行最大流最小割算法即可获得基于超像素级的全局最优解。

S3、在MeanShift算法得到超像素中由于存在着一定的过分割现象，以致在前述超像素分割结果中的目标边缘部分并不光滑，存在着一定的误分割，因此本发明在超像素级分割结果的基础上，采用形态学操作在目标边缘构造一个窄带区域，对目标边缘部分区域进行二次分割，从而进一步提高分割精度。作为具体实施例，所述步骤S3包括以下步骤：

S31、记由步骤S2分割得到的二值图像为S，如图2(a)所示。为了在目标边缘建立一个窄带区域，本发明首先对二值图像S进行形态学腐蚀操作，即可得到仅含目标的区域S_F＝SΘb，相应像素集合记为TrimapForeground，如图2(b)中的白色区域；其中b为(2d+1)×(2d+1)大小的正方形结构元素，式中d为正整数，实施例中d∈[2,5]；

S32、然后对二值图像S进行形态学膨胀操作，并与目标区域S_F做差运算即可得到一个同时含有目标和背景的窄带区域S_U＝(S⊕b)-(SΘb)，相应像素集合记为TrimapUnknown，如图2(b)中的灰色区域；

S33、而仅含背景信息的区域可表示为S_B＝S-(S_U+S_F)，相应像素集合记为TrimapBackground，如图2(b)中的黑色区域，这样就可以得到一个三元掩模图像(TrimapForeground、TrimapBackground、TrimapUnknown)，其中包括已建立好的窄带区域S_U。

S4、在构造好的窄带上为前景和背景区域分别建立相应的前景和背景模型，并对窄带区域以像素点为节点建立图模型，最后再次采用最大流最小割算法进行全局求解，以完成像素级分割过程。作为具体实施例，所述步骤S4包括以下步骤：

S41、将步骤S3中得到的目标区域S_F和背景区域S_B分别看作虚拟source节点和虚拟sink节点，然后采用主成分分析(PCA)法分别对其建立前景混合高斯模型和背景混合高斯模型，高斯个数均设为K，实施例中K＝5；所述前景混合高斯模型和背景混合高斯模型的具体建立方法如下：

S411、根据前景F或背景B的像素颜色信息，计算其协方差矩阵∑_F或∑_B，并对其进行特征分解，提取主成分或主方向，即最大特征值所对应的特征向量，样本数据在该主方向上投影值具有最大方差，然后利用样本数据在主方向上的投影结果将整个分布空间平均分成两个子空间；

S412、在所有子空间中选择具有最大投影方差分布的子空间，计算该子空间内所有样本的协方差矩阵，对其进行特征分解，提取主方向，并沿该方向将此子空间平均分成两个新的子空间；重复本步骤S412，直到得到K个子空间为止；

S413、最后分别计算K个子空间中样本数据的均值、协方差矩阵以及分布所占权重，即可最终得到前景或背景各自的混合高斯模型。

S42、由于窄带区域S_U面积通常很小，故其所含像素数很少，为了解决MeanShift算法带来的过分割问题并进一步有效提高窄带区域的分割准确度，本发明以像素点作为节点仅对步骤S3中得到的窄带区域建立图模型，在此图模型基础上执行最大流最小割算法即可获得基于像素级的全局最优解，即最终的像素级分割结果。不同于步骤S2中基于超像素级的图模型的建立，对于此基于像素级的图模型建立中的两项能量即区域信息项和边缘信息项进行了如下重新设计，即对式(5)能量函数中的区域信息项和边缘信息项进行如下重新定义：

其中，dist(i,j)表示像素点i和j的空间距离，I_i表示像素点i的颜色信息，I_j表示像素点j的颜色信息，在建立图模型过程中采用8邻域，因为λ≥b(ι_i,ι_j)，所以可取κ＝8λ+1；参数σ用来控制颜色信息差异程度，D_x(i)表示第i个像素点在前景或背景模型中分布情况，其中x∈{F,B}，其值可从下式计算得到：

其中，表示在前景或背景的混合高斯模型中第k个高斯分布所占权重，和分别表示前景或背景模型中第k个高斯分布的均值和协方差矩阵，表示协方差矩阵的行列式。

请参考图3、图4、图5和图6所示，具体为对Flower图像和Dogs图像分别采用GraphCut、Lazy Snapping、GrabCut、MSRM和本发明提供方法的分割结果对比。对于Flower图像，为公平起见，GraphCut、Lazy Snapping、MSRM和本发明提供方法使用了相同的交互信息，具体如图3(a)所示，而GrabCut算法所使用的交互信息如图3(b)所示。对于Dogs图像，GraphCut、Lazy Snapping和MSRM三种方法使用了相同的交互信息，具体如图5(a)所示，GrabCut算法所使用的交互信息如图5(b)所示，由于超像素为用户提供了指导信息，因此本发明提供方法仅需更少的交互信息，如图5(c)所示。从图4和图6中的分割结果对比可以看出，由GraphCut、Lazy Snapping和MSRM三种方法得到的分割结果中所提取的目标信息均不完整，具体如图4和图6中的(a)、(b)和(c)所示；而由MSRM方法得到的结果中所提取的目标边缘却存在着误分割，具体如图4和图6中的(d)所示；相比较而言，由本发明提供方法得到的结果中所提取的目标分割更为完整准确，具体如图4和图6中的(e)所示。

与现有技术相比，本发明提供的联合像素与超像素的交互式图像分割方法具有以下优点：

第一、本发明采用MeanShift算法进行预分割，由此构造的有向图其节点数目得到大幅度减少，从而有效提高了最大流最小割算法的执行效率；对于每个超像素，采用了更为有效的颜色直方图表示方式，并且前景和背景模型同样采用颜色直方图来表示，而不再需要进行额外的建模过程；另外，由于超像素为用户交互提供了指导信息，以致本发明仅需少量的交互信息并在较短时间内即可得到比较理想的分割效果。

第二、在建立图模型的过程中，本发明不仅考虑到了区域间的相似程度，而且还考虑到各区域与前景和背景间的相似程度，由于充分利用了交互信息，因而使得分割结果更为准确；另外，各相邻区域间的相似度仅需计算一次，然后交由最大流最小割算法进行处理，以得到超像素级分割结果，从而使得本方法的时空开销得到了进一步大幅度降低。

第三、由于MeanShift算法在分割过程中难免存在边界泄露问题，导致部分分割区域同时跨越前景和背景两部分以致出现误分割，本发明利用形态学操作在超像素级分割结果边缘部分构造一个窄带区域，然后对该窄带区域以像素为节点建立图模型并执行最大流最小割算法，从而有效提高了边缘部分分割精度。

最后说明的是，以上实施例仅用以说明本发明的技术方案而非限制，尽管参照较佳实施例对本发明进行了详细说明，本领域的普通技术人员应当理解，可以对本发明的技术方案进行修改或者等同替换，而不脱离本发明技术方案的宗旨和范围，其均应涵盖在本发明的权利要求范围当中。