彩色图像分割是将彩色图像分解为有意义且同质区域的过程，它是后续图像处理和分析的关键步骤，是模式识别和计算机视觉领域一个重要课题。近年来，随着彩色图像分析和处理技术的应用，非监督彩色图像分割方法被广泛研究。

基于超像素的非监督彩色图像分割方法^[1]，如区域增长法、聚类法等具有高效的分割优势，被广为关注。如Shi等人^[2]提出的Normalized cut (Ncut)方法将图像分割问题看成超像素区域的增长问题，利用归一化准则测量相邻超像素间的相似性，从而将同类的超像素进行合并，然而该方法因受归一化先验的限制，有时需强行分割一致性较好的完整区域。SAS(segmentation by aggregating superpixels)超像素聚类算法^[3]更多地考虑非局部超像素间的空间关系，算法鲁棒性较好。Deng等人^[4]进一步将颜色量化信息与空间相关性结合提出J-SEGmentation (JSEG)，分割出颜色纹理一致性的区域，但颜色量化信息的使用导致多样形状的区域易产生过分割。

另一方面，信息熵的阈值分割方法近年来被广泛地用于图像分割，它利用模糊理论对图像中模糊不确定的像素分类，基本思想是将阈值选取的过程，看成搜索图像最大模糊熵时隶属度函数参数的过程。Fang等人^[5]将主动轮廓模型与模糊c-划分熵方法(c≥2)结合，用于红外目标提取，然而在复杂背景下，熵的信息度量精度不高。Chen等人^[6]用最大模糊相关准则取代常用的模糊熵准则，提出最大模糊相关c-划分，有效地度量模糊划分的适当性，取得了较好的分割结果。然而实验结果表明，随着划分数c的增加，运行时间呈指数增长。Tang等人^[7]提出基于递推策略的快速模糊相关计算方法，有效地去除最大模糊相关搜索时的冗余计算，但算法仍然存在以下问题：1)该分割方法实质为阈值的分割方法，没有考虑像素的空间相关性，分割结果存在孤立的噪声；2)划分数c需人工指定，仍为半监督的分割方法；3)仅能用于灰度图像的分割，无法用于彩色图像，限制了最大模糊相关分割的应用范围。

为解决上述问题，本文提出了模糊相关图割2-划分的非监督层次化彩色图像分割方法，首先将图像划分为若干超像素；随后将快速模糊相关算法与图割相结合，构成模糊相关图割2-划分算子，解决单一阈值分割结果存在孤立噪声的问题；最后选择彩色图像中合适的区域及通道，对超像素实施迭代2-划分，直到算法收敛。

算法主要贡献有以下两点：1)将最大模糊相关与图割相结合，使基于全局的阈值分割方法与基于局部的空间相关算法互补不足；2)采用了新的层次化分割策略，使最大模糊相关算法能应用于彩色图像，并自适应地确定彩色图像的划分数，实施非监督的分割。

本文算法的流程图如图 1所示，各步骤概要说明如下：

1) 基于SLIC的超像素分割。由于层次化彩色图像分割算法是通过迭代实施单步的最大模糊相关图割2-划分操作完成。为此，在预处理阶段，采用计算耗时小，参数设置简单的SLIC(simple linear iterative clustering)算法^[8]将彩色图像分割为若干超像素，减少图像基元的数目，提高后续算法的效率。

2) 快速最大模糊相关计算。实验表明最大模糊相关2-划分相比于常用的最大模糊熵分割具有更高的精度，但最优阈值的搜索耗时较长，采用Tang等人^[7]提出的快速递推策略能有效去除冗余计算，提高效率。

3) 模糊相关图割2-划分。直接实施模糊相关2-划分操作，并没有考虑像素的空间相关性，分割结果仍存在孤立噪声，为此利用最大模糊相关来引导图割实施，构建模糊相关图割2-划分算子。

4) 非监督层次化彩色图像分割。利用单步模糊相关图割2-划分算子对彩色图像实施非监督的层次化分割，直到算法收敛为止。

为了提高算法的效率，在实施层次化分割之前，使用SLIC算法将彩色图像预分割为数量可控，形状规则的超像素。由文献[8]可知，该算法将彩色图像转换为CIELAB颜色空间和2维($x $, $ y$)坐标下的5维特征向量(l, a, b, $x $ , $ y$)，对5维特征向量构造相应的度量标准，以便将像素聚类为超像素。主要过程为初始化种子点和相似度衡量两个步骤。其中种子点初始化的步骤是将包含n个像素的图像，预分为e个超像素种子点，种子点的间距$S = \sqrt {n/e} $。随后用$D$衡量像素点间的相似度，即

$ D = {d_{{\rm{lab}}}} + \frac{m}{s}{d_{xy}} $

(1)

式中，$D$值越小，两个像素点相似度越高。$m$为调节参数，平衡空间信息与颜色值在相似度衡量中的比例。${d_{{\rm{lab}}}}$和${d_{xy}}$分别为种子点与度量像素点颜色差异和空间距离，详细的实施参考文献[8]。

为了更好地度量图像划分的适当性，采用Chen提出的最大模糊相关准则来搜索使目标和背景的模糊集S_o和S_b准确划分时的最优阈值^[6]。采用梯形函数及其反函数来定义目标和背景隶属度函数${\mu _{\rm{o}}}$和${\mu _{\rm{b}}}$，其中${\mu _{\rm{b}}}$=1-${\mu _{\rm{o}}}$，${\mu _{\rm{o}}}$为

$ {\mu _{\rm{o}}}\left( k \right) = \left\{ {\begin{array}{*{20}{c}} 1&{k \le g}\\ {\frac{{k-c}}{{g-c}}}&{g < k < c}\\ 0&{k \ge c} \end{array}} \right. $

(2)

式中，$k$为像素的灰度，满足0≤$k$≤255。$g$, $c$为梯形函数的形状参数，满足0≤$g$ < $c$≤255。

则S_o和S_b集合的划分概率为

$ \left\{ \begin{array}{l} {P_{\rm{o}}} = \sum\limits_{k = 0}^{255} {{\mu _{\rm{o}}}\left( k \right)p\left( k \right)} \\ {P_{\rm{b}}} = \sum\limits_{k = 0}^{255} {{\mu _{\rm{b}}}\left( k \right)p\left( k \right)} \end{array} \right. $

(3)

式中，$p\left(k \right) = \frac{{{f_k}}}{n}$，$k$=0, 1, …, 255，f_k为图像中灰度级为$k$的像素个数。

根据最大模糊相关的定义，图像总模糊相关为

$ \begin{array}{l} C\left( {g, c} \right) =- \ln \left[{{{\sum\limits_{k = 0}^{255} {\left( {\frac{{{u_{\rm{o}}}\left( k \right)p\left( k \right)}}{{{P_{\rm{o}}}}}} \right)} }^2}} \right] - \\ \;\;\;\;\;\;\;\;\ln \left[{\sum\limits_{k = 0}^{255} {{{\left( {\frac{{{u_{\rm{b}}}\left( k \right)p\left( k \right)}}{{{P_{\rm{b}}}}}} \right)}^2}} } \right] \end{array} $

(4)

搜索使$C$($g$, $c$)最大的$g$^*, $c$^*值，可获得分割图像的最优阈值T=0.5($g$^*+$c$^*)。这里采用文献[7]中的递推策略来加速搜索，即将式(4)改写为多个独立求和项相加的形式，分别对求和项实施递推计算，保存瞬间递推值，用于最大模糊相关$C$($g$, $c$)穷举搜索。

利用最大模糊相关求得的阈值实施图像的2-划分，没有考虑像素的空间相关性，导致分割结果存在孤立噪声，如图 2所示。对图 2(a)的摄影初始图像实施SLIC超像素分割后得到图 2(b)，在图 2(b)的基础上，进一步实施最大模糊相关的阈值分割^[6]，其结果如图 2(c)所示，箭头标出了存在的孤立噪声。为了获得更平滑的分割结果，将空间相关的图割^[9]与模糊相关^[6]结合，构建单步2-划分。

首先构建一个由源点、汇点，及超像素作为节点的图。所有超像素节点均与源点和汇点相连，连接的边权重由数据项${E_{{\rm{data}}}}$由最大模糊相关时S_o和S_b集合概率来设置，以便用模糊相关的阈值分割结果来引导图割即

$ {E_{{\rm{data}}}} = \left\{ \begin{array}{l} -\log \sum\limits_{k = 0}^{255} {{h_R}\left( k \right){\mu _{\rm{o}}}\left( k \right)} \;\;\;\;{l_R}为目标\\ -\log \sum\limits_{k = 0}^{255} {{h_R}\left( k \right){\mu _{\rm{b}}}\left( k \right)} \;\;\;\;{l_R}为背景 \end{array} \right. $

(5)

式中，${l_R}$是区域$R$的标号，${{h_R}}$($k$)为区域$R$内像素的归一化直方图。

为了确保相邻节点间标号的一致性，连接相邻节点的边，用平滑项${E_{{\rm{smooth}}}}$表示，本文用Boykov等人^[9]的定义来设置，即

$ {E_{{\rm{smooth}}}} = {10^{\frac{{{I_{{\rm{Rmax}}}} - {I_{{\rm{Rmin}}}}}}{{255}}\alpha }}\exp \left( { - \frac{{{{\left( {{I_p} - {I_q}} \right)}^2}}}{{2{\sigma ^2}}}} \right) $

(6)

式中，${{I_p}}$和${{I_q}}$为相邻超像素节点的平均灰度值。$\sigma $为相邻超像素区域的灰度方差，其值在[0, 1]范围内，本文中默认为1。参数φ为相似度常量，随着所选标号区域的灰度范围而变化。${{I_{{\rm{Rmax}}}}}$和${{I_{{\rm{Rmin}}}}}$分别为所选标号区域中的最大和最小平均灰度值，$\alpha $为调节参数，本文默认设置为14。

图割构建完成后，采用最大流最小割算法^[10]将超像素节点划分为属于源点和汇点的两类，即给超像素分配最佳的目标或背景标签。实施模糊相关图割2-划分后，分割结果在确保空间一致性的基础上去除了孤立的噪声，如图 2(d)所示。

然而上述模糊相关图割2-划分，不能对彩色图像实施分割，且图像的划分数也无法自适应确定。如图 2，初始图像为灰度图像，划分数2在分割前已确定。这是由于模糊相关算法中模糊集合的划分概率，总模糊相关等信息均是在图像灰度直方图的基础上进行统计的，面对有三通道的彩色图像，选择哪个通道实施分割，自动分割算法收敛的条件都需要合理地解决。

为此，设计自顶向下的层次化分割策略，迭代地对图像实施单步模糊相关图割2-划分，有效完成了非监督层次化彩色图像分割。其核心思想是迭代地在彩色图像的l、a、b通道中选择最佳的通道，实施单步模糊相关图割2-划分，直到分割结果接近原图，算法停止。

整个层次化的分割过程我们可以构造一个自顶向下的k-d树来记录，如图 3所示，首先将输入的彩色图像看做根节点，对l、a、b三通道分别实施单步的模糊相关图割2-划分，将超像素分为目标和背景两大区域。选择分割质量最佳的通道分割结果作为孩子节点，即最佳分割结果中，标号为目标和背景区域分别作为根节点的左右孩子节点。这里选用平方根误差(MSE)^[11]评价不同通道下分割彩色图像的质量，即

$ \begin{array}{l} \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;{\rm{MSE = }}\\ \frac{1}{{3N}}\sum\limits_H {\sum\limits_{i = 1}^R {{N_i}} \left( {{\omega _i}-2{m_i}f\left( {{h_i}} \right) + f{{\left( {{h_i}} \right)}^2}} \right)} \end{array} $

(7)

式中，$H$为l、a、b通道。$R$为超像素的个数。对于当前第$i$个超像素，${{N_i}}$为超像素中的像素个数，${{m_i}}$为像素灰度均值，${{\omega _i}}$为超像素中像素的灰度平方均值，${{h _i}}$为当前超像素$i$的标号，函数${f\left({{h_i}} \right)}$为标号${{h_i}}$的所有超像素灰度均值。

如图 3，初始图在l、a、b通道的分割结果如图 3(b)—(d)，初始图像的b通道分割结果的MSE最大，因此将其目标和背景区域视为左右孩子节点，即白色花朵目标对应图 3(a)的输入花朵区域为左孩子节点。灰色背景区域对应图 3(a)的输入背景区域为右孩子节点。为了清楚凸显叶子节点所代表的区域，左右叶子节点中无关区域已用深色遮盖。至此已生成了k-d树的第1层。

随后将挑选当前这两个叶子节点即图 3(a)的输入花朵和背景区域中的一个节点来实施进一步的2-划分。首先，对当前的一个叶子节点所代表的区域，分别尝试l，a，b三通道的模糊相关图割2-划分，并用MSE评估分割质量，选取分割质量最佳的某一通道的分割结果作为当前叶子节点进一步分割后的结果，如对花朵区域，进一步实施3个通道的2-划分，其中b通道的分割结果最优。同理，图 3(a)的背景区域在l通道分割的结果最优。随后，对比所有叶子节点进一步分割的最佳结果，选择分割质量最优的节点生成其对应的左右孩子节点。如背景区域在l通道的分割结果较花朵区域在b通道分割结果更优，故选取背景区域节点，并按照图 3(d)l通道的分割结果，生成相应的左右孩子节点，即k-d树的第2层。算法将不断重复上述过程，即不断选取当前所有叶子节点中的分割质量最优的节点，生成左右孩子节点，直到算法收敛为止。注意，将叶子节点代表的区域分割为2个标号的子区域时，MSE用当前节点区域的超像素来计算，实际操作时，选取分割前后 $\Delta {\rm{MSE}} $下降最大的叶子节点作为父节点来生成孩子节点，$\Delta {\rm{MSE}} $计算公式为

$ \begin{array}{l} \Delta {\rm{MSE}}\left( h \right) = \frac{1}{{3N}}\sum\limits_D {\sum\limits_{k \in {{\bf{\Omega }} _h}} {{N_k}} (-2{\mu _k}(f\left( {{y_k}} \right)-} \\ \;\;\;\;\;\;\;\;f\left( {y{'_k}} \right)) + f{\left( {{y_k}} \right)^2}-f{\left( {y{'_k}} \right)^2}) \end{array} $

(8)

式中，${{{\bf{\Omega }}_h}}$为标号$h$区域中所包含的超像素集合。${{y_k}}$和${y{'_k}}$为超像素分割前后的标号。

上述算法收敛的条件为：进一步的模糊相关图割2-划分操作不会引起叶子节点$\Delta {\rm{MSE}} $大幅度变化时停止，这里我们将设置阈值T来控制算法，即当$\Delta {\rm{MSE}} $ < T，对所有的叶子节点成立时，算法停止。如图 4所示，当算法停止时，生成自顶向下的k-d树，其中选择继续分割的节点将进一步生成左右孩子节点，而算法结束时，当前所有的叶子节点构成了输入彩色图像的最佳分割结果。

使用Berkeley分割数据库中的300幅带有真实分割结果的彩色图像来验证算法的有效性，并与基于超像素的半监督层次化彩色图像分割方法，如SAS^[3]、Ncut^[2]，非监督的彩色图像分割方法，如JSEG^[4]相比较。此外还对模糊相关图割2-划分的有效性，SLIC中种子点个数e的选取进行讨论。所有算法均在2.4 GHz CPU, 8 GB内存的条件下，使用Matlab R2015a编程实现。各算法的参数均选用文中默认设置，本文算法参数T=19，e=500。量化的评价指标除了选用MSE以外，还采用SAS^[3]、Ncut^[2]中使用的4种主流的评价函数：1)概率边缘指数(PRI); 2)信息变化指数(VOI); 3)全局一致性误差(GCE); 4)边缘替代错误率(BDE)评估不同算法的分割结果。其中，PRI越大，VOI、GCE、BDE越小，分割结果与真实分割结果越接近。

首先选取了海星、赛车、鞋子、教堂4幅图像来展示本文层次化分割过程。图 5为4幅彩色图像的层次化分割过程，可见，本文算法能自动地选择最优的划分数将彩色图像划分为有意义的区域，4幅图像的划分数分别为3，4，4。如图 5中海星经2次单步模糊相关图割2-划分后将图像分为3类。

图 6显示了本文算法与SAS^[3]、Ncut^[2]、JSEG^[4]算法的视觉分割结果，从中可见SAS算法和Ncut算法存在目标区域不完整，信息丢失的情况，如SAS分割的赛车图像，其地面的白色跑道丢失，完整的海星区域被分成了4个不同区域。Ncut算法则明显丢失了海星及赛车目标。JSEG算法存在过分割现象，如鞋子和教堂图像的分割结果中存在过多无用的细节信息，并没有分割出有意义的完整目标。而本文算法在完整地分割出有意义目标区域的同时，清晰地保留了目标边界，分割结果更加精确。

由式(8)的MSE指标对图 6中各算法的分割结果进行量化评估，其结果如图 7所示，可见本文算法具有最低的MSE值，分割质量最好。

进一步采用4种算法对Berkeley数据库中300幅彩色图像实施分割，统计的PRI、VOI、GCE、BDE结果如表 1所示。

从表 1可以看出，SAS算法测得的PRI最大，VOI、GCE、BDE最小，分割质量最好，本文算法排名第二，较JSEG、Ncut有较大的PRI，较小的VOI、GCE、BDE。这是由于SAS算法不但为半监督分割方法，还利用纹理、边缘、颜色等特征来引导分割，精度更高。相比而言，本文算法仅利用颜色信息来实施非监督分割，虽然分割效果劣于SAS算法，但较半监督的Ncut算法，非监督的JSEG算法，分割精度有显著提高。

为了验证模糊相关图割2-划分操作的有效性，本节将对比2.2节中的最大模糊相关算法^[6]与2.3节中的模糊相关图割2-划分算法的分割结果，由于这两种算法只能对灰度图像实施分割，故选取了药品、田野、摄影3幅灰度图像进行验证。视觉分割的结果如图 2和图 8所示，从左到右依次是初始图像，SLIC超像素分割结果，以及在超像素分割的基础上实施最大模糊相关分割结果和模糊相关图割2-划分的结果。从中可以看出本文设计的模糊图割2-划分操作不但能去除孤立的噪声，还能确保空间一致性，如图 8(c)中田野图像的矩形红框里孤立的噪声，在图 8(d)的图割结果中被去除。图 8(c)中药品图像的矩形红框里不完整的胶囊区域，在图割结果中完整提取，在20幅灰度图像上验证算法性能，并选用文献[12]中F指标量化分割质量及分割结果的完整性，实验表明最大模糊相关算法的F值平均为32.46，而模糊相关图割2-划分算法的F值平均为9.67，由于F值越小分割结果越好，因此融入图割后的模糊相关算法显然有更高分割精度。

SLIC的超像素分割算法是非监督层次化模糊相关图割算法的预处理步骤，SLIC中种子点个数e的设置将影响分割精度。图 9(a)分别显示了e为300，500，800时的超像素结果，图 9(b)显示了相应的最终分割结果。可见，当e值为800时，超像素的面积较小，图像细分程度较高，在相同阈值T的约束下，产生过分割结果。而当e值为300时，超像素面积较大，相同T时，产生欠分割的结果。e值为500时，目标和背景能较完整地提取。大量的实验也表明，e值为500时，算法的分割精度最高。

算法各部分的运行时间如下：1) SLIC超像素分割，运行时间约为4 s; 2)快速的模糊相关计算，由于该步骤利用Tang等人^[7]提出的递推策略，效率较高，运行时间约为0.2 s; 3)基于模糊相关图割2-划分操作，由于它利用了最大模糊相关的递推结果快速设置了图割的数据项，后续实施的最大流最小割求解策略能在线性时间内给超像素分配最佳标签，约为0.5 s; 4)层次化彩色图像分割过程，仅在叶子区域内迭代实施2-划分算子，层次化分割过程时间为7 s。本文算法总运行时间约为12 s左右，较彩色图像分割算法Ncut、JSEG的运行时间(分别约为30 s，15 s)而言，分割效率提高了近20%。相比文献，仅利用最大模糊相关实施灰度图像的全局分割策略^[6](运行时间约为10 s)，本文算法的运行时间略长，这主要是由于算法利用单步的模糊相关图割操作实施层次化彩色图像分割。

综上可见，本文算法复杂度取决于模糊相关图割2-划分实施的次数。由文献[7]可知，最大模糊相关的计算复杂度为O(n²)，假设单步2-划分操作的次数为t，则本文算法的计算复杂度为O(n²)t。

基于模糊相关图割的非监督层次化彩色图像分割方法，能自动确定图像的划分数，实施自顶向下的层次化分割。首先将图像划分为若干超像素，随后构建快速模糊相关图割2-划分算子，并选择合适的通道及区域，对超像素实施迭代的单步2-划分，直到算法收敛为止。结果表明，仅利用颜色信息引导的层次化分割策略，其分割精度明显优于Ncut、JSEG彩色图像分割方法，运行时间约为12 s左右，扩展了模糊相关算法在彩色图像分割中的应用。