基于降采样归一化割的多尺度分层分割方法研究

童昊浩　吴克伟

摘要：图像分割作为计算机视觉的中层任务，常建立在目标轮廓特征的基础上，但是局部轮廓检测器的结果难以保证其产生封闭轮廓。为获得完整的分割区域，归一化割方法提供一种将局部轮廓结果转化为图像分割结果的处理途径。传统的归一化割方法由于长特征向量的聚类导致计算耗时长、内存占用多。在轮廓特征的基础上，考虑轮廓的全局推断，提出一种归一化割的改进方法——降采样归一化割，以减少图像分割过程中的计算耗时。通过多尺度空间下的层级校准，准确定位多个尺度下的区域边界进行区域合并，从而得到更准确的多层分割图。

关键词：分层分割；降采样归一化割；尺度空间；层级校准；区域合并

DOIDOI：10.11907/rjdk.151428

中图分类号：TP317.4

文献标识码：A 文章编号文章编号：16727800（2015）008019003

0 引言

分割可看作是一种把图像分成若干区域的方法。分割问题和轮廓检测问题是相关的，但是两者又不完全一样。一般情况下，基于局部外观特征的轮廓检测器[1]不能保证产生闭合的轮廓，因此不能将图像的一部分划分成区域，但是分割区域可以根据边界恢复得到闭合轮廓，因此图像分割常建立在目标轮廓特征的基础上进行区域划分。

近年来，图论（Graph Theory）是研究分割的一个热点[2]。归一化割（Normalizedcut，Ncut）[3]是基于图论的分割方法之一。特征向量计算是归一化割中聚类算法的计算瓶颈，特征向量的高效计算成为研究重点。Sharon等[4]提出了一种替代方法来改进归一化割方法的计算效率。这种方法受代数多重网格的启发，通过选择节点的子集迭代粗化原谱图。Taylor[5]提出了一种技术：使用一个简单的分水岭过分割用以减少特征向量大小问题，其不足之处是提高计算效率的同时牺牲了目标准确度。Maire 和Yu[6]提出了一种新型的多网格求解器，用于产生多尺度空间特征向量，利用粗糙尺度的解加速精细尺度的特征向量计算。

本文使用图像的尺度空间结构。相比于多尺度求解，本文方法简单地降低了空间尺度，在退化空间上求解，并将解进行升采样保留图像结构，使得在保持性能的前提下计算更加简洁、快速，即降采样归一化割，这使得归一化割的效率大大提高。同时，采用一种多尺度层级校准的方法用于区域合并，从而得到更准确的分层分割图。

1 改进归一化割

归一化割方法是高性能轮廓检测器的一个关键全局化机制[1]。虽然功能强大，但其计算成本、存储需求较高，限制了它的可扩展性[7]。本文介绍一种高效的降采样归一化割方法，不仅充分保留了轮廓检测性能，而且具有低存储需求及特征向量计算效率提升20倍的优点。

1.1 降采样归一化割

归一化割主要是依据给定的编码像素之间的相似性建立关联矩阵A，并定义对角线矩阵Bii=∑jAij，求解线性系统的广义特征向量（B-A）v=λBv。由于矩阵A很大，即使有先进的求解器，直接计算也具有较大的计算成本和存储需求。

本文采用利用多尺度性质技术以有效得到近似解。定义pixel_decimate（A），表示关联矩阵中对应降采样图像的行列索引，也就是说，如果i=pixel_decimate（A），则A[i，i]{JP是一个降采样矩阵，对应图像的行和列交替去除。由于像素大量减少，计算A[i，i]的特征向量效果并不理想，但是计算降采样的平方关联矩阵A2[i，i]的特征向量是和A的特征向量相似的。因为在降采样之前，平方关联矩阵A2[i，i]使得每个像素的信息都传播到了其领域之中，即使降采样后依然保留了所有像素的信息。通过A[：，i]TA[：，i]有效计算A2[i，i]，并计算A2[i，i]的特征向量，然后通过与A[：，i]相乘升采样这些特征向量回到原始图像的尺度空间。这种平方和降采样的操作可以在轻微降低准确度的情况下大大提高效率。

本文将这种改进归一化割算法称为降采样归一化割（Downsampled NormalizedCuts，DNCuts），其中D是平方和降采样操作的循环次数。降采样归一化割反复应用平方和降采样操作，并利用标准的归一化割求解器ncuts（AD，K），计算最终的降采样矩阵AD及其对应的K个最小特征向量，并重新升采样这些特征向量。

1.2 轮廓全局推断

轮廓全局推断的关键在于使用从归一化割中获得的特征向量。文献[1]展示的是目前世界领先的局部轮廓检测器之一，将其轮廓检测结果lE作为谱图划分的输入，使用轮廓中间线索，即两像素连接线间的置信度最大值，建立稀疏对称仿射矩阵A，如图1所示。连接所有位于固定半径r中的像素i和j，进行关联计算：

其中，ij为连接i和j的分割线段且ρ为常量，设置r=5，ρ=0.1。

为了引入全局信息，定义Bii=∑jAij并根据1.1节中的降采样归一化割，求解（B-A）v=λBv的广义特征向量v0，v1，...，vn，对应于n+1最小特征值λ（实验中取n=5）。观察到特征向量本身携带了全局轮廓信息（见图1）。视每个特征向量vk为一幅图像，将其与高斯方向导数滤波器在多个方向θ上卷积，获得定向信号θvk（x，y）。来自不同特征向量的信息提供给轮廓检测器的谱成分，并在方向上取最大值作为谱信号：

其中，权重为1/λk的动机来自广义特征向量问题并作为质量弹簧系统[9]的物理解释，λk=2。

信号lE和sE传递不同的信息（局部轮廓线索和全局轮廓线索），简单的线性结合足够获取两者的优势。最终轮廓边缘置信度被写作局部边缘置信度和谱信号的加权和：

其中，权值δ通过训练图像使用梯度上升学习获得。

2 多尺度分层分割

首先采用分水岭转换（Watershed Transform）从边缘置信度图中产生一组初始区域，即生成超像素图，在超像素图的基础上利用轮廓权值建立一个层次性分割。设图像的分割区域划分为多个领域S=Sii。一个分割层级结构定义如下的一系列族区域S*，S1，...，SL：①S*是最精细级别的超像素块集合；②SL是整个区域；③粗糙级区域是精细级区域的联合。层次结构中每个级别Si都被分配一个实值索引λi，这个索引可以通过树状图来表示。在区域树中，每个结点的高度是其索引值。对于分层分割，本文将这种表示称为超度量轮廓图（Ultrametric Contour Map，UCM），这个超度量轮廓图中每条轮廓的权值即为该轮廓两边区域合并的索引值[8]。这种表示方式将轮廓检测和多层图像分割问题统一起来，超度量轮廓图中的一个阈值λi产生分割块Si。这种算法使得区域树的每个级别上具有视觉线索的同质性，超度量轮廓图的轮廓权值可以理解为区域差异性的度量手段。分层分割示例如图2所示。

尺度空间是计算机视觉中一种强大的处理策略。将它用于两种不同的方式，开发一种高效、可扩展和高精度分割算法：①加速谱图划分；②创建对齐的分割层级。下面介绍如何通过校准来创建对齐的分割层级。

2.1 层级校准

对于超像素图的区域合并，需要校准对齐分割层级。选择在多层结构中均匀采样K层级，并依次将它们的图像边缘重构为超度量轮廓图。假设有两种不同的分割块R=Rii和S=Sjj。定义分割块R映射至区域Sj∈S的标准为大多数标记的位置区域。

则R投影至S上

为了将一个超度量轮廓图映射至目标分割块S，要在层级的每个级别定义π（UCM，S）。

迭代这个操作，递归地将超度量轮廓图投影到一组目标分割块S1*，...，SN*。两个这样的映射构成可以表示为如下公式：

2.2 多尺度层级

通过升采样和降采样原始图像构造一个N尺度的多分辨率空间金字塔，每一个尺度均应用单尺度分割器分割图像。根据2.1节层级校准递归转换所有更粗糙级的超度量轮廓图边界的权值。校准后，图像有一组固定的边界位置，每个边界对应N个权值中的一个，对应不同的尺度。将此转换为二值边界分类问题，并利用逻辑回归训练一个分类器，用于合并N个权值到一个单一的边缘概率估计值，得到最终的超度量轮廓图，其中每个层级都对应一个级别的层级分割。

3 实验结果与分析

实验采用的数据集为Carnegie Mellon University的轮廓检测和分割数据集[10]。对于分割算法，其评价策略多种多样。多种基于区域的度量标准包括：信息变化（Variation of Information， VI）、兰德指数（Rand Index， RI）、分割覆盖（Covering）。

图3给出了CMU数据集上部分gpbucm和gEucm的超度量轮廓图结果，其中图3（d）为OIS（optimal image scale）分割结果，即每张图分别取最优阈值时的最优分割图。从整体上看，gEucm的超度量轮廓图与gpbucm的超度量轮廓图相比，具有更好的视觉轮廓感官效果，分割块对应目标更准确，并且运动目标边缘更加显著，更加贴近于数据集中的手工标记轮廓。

为考察gEucm的综合性能，采用Covering、PRI和VI三种评估策略进行定量分析。表1显示了CMU数据集上Covering、PRI和VI三种性能评估指标。其中，每个指标均有两个值：ODS和OIS。ODS（optimal dataset scale）指测试结果在整个数据集上取同一阈值得到的性能指标，OIS（optimal image scale）指测试结果在每个数据上取最优阈值得到的整个数据集的平均性能指标。理论上，Covering和PRI的值越大，分割性能越好，VI值越小性能越好。从表1可以看出，gEucm和gpbucm的性能明显好于传统归一化割方法Ncuts，而gEucm和gpbucm在Covering和PRI上的指标基本一致（个别指标gEucm略好）。而在VI指标上，gEucm要好于gpbucm（VI值更低）。从指标的本义上来说， gEucm的测试结果和真实手工标记差异较小。定量分析结果与定性结果基本一致。

除了考察gEucm的综合性能外，本文还对gEucm和gpbucm的检测效率进行了测算。表2显示的是两者在单幅图像上（640x480）的平均检测时间。可以看出本文方法由于在降采样归一化割过程中，特征向量计算时间比传统归一化割方法快了20倍，使得在整体检测效率上有了较大提升。实验表明，本文方法在保证分割性能的前提下大幅提高了检测效率。

4 结语

针对归一化割中特征向量计算耗时长的问题，本文采用在退化空间中降采样归一化割，对传统的归一化割方法进行改进，以减少图像分割过程的计算耗时，并对轮廓进行全局推断。通过多尺度空间下的层级校准，准确定位多个尺度下的区域边界进行区域合并，将轮廓置信度图转换成超度量轮廓图，从而得到更准确的多层分割图。实验表明，本文方法检测得到的超度量轮廓图具有较好的视觉边界感官效果。在定量分析中，本文方法在保证分割性能的前提下大幅提高了检测效率。本文的多尺度分层分割方法还可用于后续的高层视觉任务中，如从分割结果中提取目标候选用于目标识别和跟踪任务中，并应用到具体实际环境（如交通监控）中。下一步研究重点是提高本分析方法在执行目标检测、视频跟踪等高层视觉任务时的鲁棒性、高效性和准确性。

参考文献参考文献：

[1] ARBELAEZ P， MAIRE M， FOWLKES C，et al. Contour detection and hierarchical image segmentation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2011， 33（5）： 898916.

[2] 王梅， 李玉鑑， 全笑梅. 图像分割的图论方法综述[J]. 计算机应用与软件， 2014， 31（9）： 112.

[3] SHI J， MALIK J. Normalized cuts and image segmentation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2000， 22（8）： 888905.

[4] SHARON E， GALUN M， SHARON D，et al.Hierarchy and adaptivity in segmenting visual scenes[J]. Nature， 2006， 442（7104）： 810813.

[5] TATLOR C J. Towards fast and accurate segmentation[C]. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition.Portland， OR， United states： IEEE， 2013： 19161922.

[6] MAIRE M， YU S X. Progressive multigrid eigensolvers for multiscale spectral segmentation[C]. Proceedings of the IEEE Conference on Computer Vision. Sydney， NSW， Australia： IEEE， 2013： 21842191.