基于最小栅栏距离的图像超像素分割方法

2020-07-20

西华大学学报（自然科学版） 2020年4期

（西华大学无线电管理技术研究中心，四川成都 610039）

超像素分割作为图像处理的主要手段，已在大量的计算机视觉中得到广泛应用，例如对象跟踪[1]、语义分割[2]、图像理解[3]等。作为视觉算法的前端处理，超像素分割有3 个主要的性能需求：1）分割有效性，即分割区域需要尽可能准确贴合对象的边界；2）计算有效性，即处理时间尽可能短；3）区域紧致性，即形状尽可能规则。

已有的超像素分割方法一般分为2 类：基于聚类的超像素分割、基于图论优化的超像素分割。前者首先初始化聚类中心，然后加入聚类元素并更新中心，逐步迭代直到收敛，如TuberPixels(TP)[4]、simple linear iterative clustering(SLIC)[5]。然而这类方法基于颜色空间的欧式距离计算像素相似性，导致模糊对象边界及复杂纹理区域分割边界贴合度低。后者将图像邻接像素构建为图结构，采用图论优化方法获得紧致贴合的分割边界。该类方法聚焦邻接像素的相似关系，忽略了像素与种子点的位置关系，导致分割区域缺乏规则性与紧致性。上述2 类方法或采用基于迭代更新的优化策略或采用基于复杂的图理论优化方法，导致分割时间耗费较多。

针对以上问题，本文提出一种基于最小栅栏距离的快速超像素分割方法。直观上，像素到种子中心的距离由其最短路径上的最大颜色强度差异决定。一方面，最大颜色差异的计算避免了传统测地距离像素误差累积的问题；另一方面，最小栅栏距离的计算更多的只需要采用像素强度值大小，提高了计算效率。另外，本文采用优先队列实现像素的线性访问，获得了O(n)的线性时间复杂度。在BSDS500 图像分割数据集上进行实验对比，验证了本文方法相比现有主流方法的优越性。

1 超像素分割算法

超像素分割方法一般可分为2 类：基于聚类的方法和基于图论的方法。

1.1 基于聚类的超像素分割算法

基于聚类的算法首先初始化超像素中心点，然后逐步采用添加类别像素成员的方式扩张超像素区域，并通过多次迭代达到收敛。例如，TP[4]方法初始化种子点并扩张超像素的边界直到梯度最大的边界。由于引入了基于水平集的曲率代价项以维持区域的规则性，所以不规则对象及复杂背景下的分割性能较低。Achanta 等[5]提出了基于快速K-means[6]算法的SLIC，通过约束聚类中心的搜索空间，获得了快速的分割性能，同时能生成均匀、紧致的超像素区域。SNIC[7]采用非迭代的架构增强区域的连通性，克服了SLIC[5]中潜在的区域不连通的问题。LSC[8]将特征分解与K-means 算法融合，得到了全局感知一致性的超像素分割。为了更准确逼近图像的特征本质，Ye 等[9]提出了基于查询的测地距离的超像素分割方法，它在高维空间上计算测地距离，更好地刻画了自然图像流形空间的像素相似性，然而由于其复杂的高维特征计算，所以其计算复杂度过高。为了适用于深度学习的视觉应用，Jampani 等[10]及Yang 等[11]分别提出了基于深度学习的超像素分割算法。前者[10]采用深度卷积网络提取像素的卷积特征，再用后续的迭代聚类算法获得超像素分割结果。后者[11]采用全卷积网络[12]直接预测像素的超像素标签，避免了迭代运算，提高了计算效率。然而它们均需要GPU进行特征计算，限制了其方法的适用性。

1.2 基于图论的超像素分割算法

基于图论的算法是将图像像素构建为图结构并将图像分割问题构建为最小代价的割边寻优问题。例如，Shi 等[13]提出采用normalized cuts（NC）来平衡不同分割区域的面积大小，从而保证分割区域的规则性。然而高维度的矩阵分解将导致计算有效性随着图像尺度的增加急剧下降。Felzenszwalb等[14]提出了基于图的图像分割（graph-based image segmentation），它基于分割区域内部的最小类间差异来构建最小生成子树，以此作为最终的超像素区域，其运算速度较快，超像素的边界贴合度高，但由于缺乏种子点定位，所以分割区域不规则，同时由于采用最小类间差异及最大类内差异，所以弱边界及复杂噪声背景下的分割边界贴合度低。Liu 等[15]提出的entropy rate superpixel（ERS）同样将图像像素构建为图上随机的熵率和平衡项2 个部分组成的目标函数，熵率部分使得超像素的结构均匀且紧凑，平衡项使得超像素具有相差不大的像素个数。然而该算法的运算复杂度较高，限制了其作为预处理算法的实时性应用。RPS[16]通过构造对象边界点的最小代价边来获得超像素边界，获得了规则区域的超像素分割区域，但是由于其采用水平垂直约束，因此分割精度下降。

基于聚类方法的超像素分割采用欧式距离构建像素相似性测量，容易在模糊边界处产生较高的分割误差。基于图论的方法采用测地距离以构建像素对之间的相似性，容易导致路径上的误差累积，使得噪声背景下分割性能降低。本文提出的采用最小栅栏距离的方法，不仅具有测地距离的最短路径优势，克服传统测地距离的误差累积的缺点，而且能更多地使用逻辑比较运算，避免了大量的乘除运算，提高了运算效率。

2 基于最小栅栏距离的超像素分割

针对传统测地距离容易产生误差累积、计算效率低的问题，本文提出了一种最小栅栏超像素分割算法。首先介绍了最小栅栏距离的定义，然后提出了基于快速行军法计算栅栏距离的O(n)线性时间复杂度的最优化方法。

2.1 最小栅栏距离

最小栅栏距离（minimum barrier distance，MBD）用来测量图像像素p到种子点集合S的最小测地距离，它被广泛用来表征像素与图像边界的连通性[17－18]。给定灰度图像I,定义像素p到某个种子点sk的路径为P=[p1,p2,···,pn]，其中pi－1与pi相互邻接构成一条连续路径，则最小栅栏测地距离表达为像素到种子点集合的所有路径集合中的最短路径。具体地，定义最小栅栏测地距离为

式中，p(0)=t，p(n)=sk。因而，点p到sk的最小栅栏测地距离表示从所有p到sk的候选路径中选择路径上强度差异最小的路径。给定种子像素集S=[s1,s2,···,sK]，像素p到种子集合S的最小栅栏测地距离为

式中p(n)属于S，表示为选择从像素t到所有种子集合S的路径集合中一条最小栅栏距离的测地路径。

由于单通道的灰度图像不能很好地体现对象与背景的边界差异，因而定义彩色图像上的最小栅栏距离，为

式中c∈C，为图像I通道RGB 中的一个。

2.2 线性复杂度的超像素分割优化算法

MBD 距离计算的优势在于降低了大量的乘法和平方运算，从而提高了访问中单次像素的计算速度。同时，为了获得线性时间复杂度，需要把对图像像素访问和操作的次数降低到线性次数O(n)。这里采用快速行军法（fast marching）[19]逐步扩张超像素成员，对像素采用单次扫描以快速生成超像素分割区域。给定基于规则网格采样的初始种子点S=[s1,s2,···,sK]，采用优先队列Q，实现返回当前访问下最小栅栏距离的最小成员。另外，采用2 个向量U及L来存储当前路径下像素i到种子k的最大强度及最小强度。

式中：C是通道数；D(p)记录当前像素p到种子点集S的最小栅栏距离。算法流程如图1 所示。其中，ck=I(p)为RGB 颜色特征，xk为空间位置xy的坐标值。另外，采用向量Lab记录p在最小栅栏距离下对应的种子点标签。

图1 基于最小栅栏距离的图像超像素分割方法

3 实验

本文采用MATLAB 平台在数据集BSDS500上进行实验验证。与当前的主流方法进行实验对比，并在achievable segmentation accuracy (ASA)、boundary recall (BR)、undersegmentation error (UE)以及运行时间等客观量化指标上进行评估。当前的主流方法包括：NC[13]、linear spectral clustering(LSC)[8]、SLIC[5]、TP[4]、FH[14]、regularity preserved superpixels (RPS)[16]等。

表1 给出了不同方法在100 块超像素分割下的客观评价指标。在性能指标方面，ASA、BR 是越高越好，UE、Time 是越低越好。可见，LSC[8]、SLIC[5]获得了前2 名的分割性能，这是因为它们均采用迭代优化框架对超像素中心进行更新使得能量值更低，从而获得了更好的分割性能。与LSC 相比，本文方法（MBD）在3 个指标上都接近于LSC 方法，同时在运行时间上，MBD 获得了最少运行时间。在ASA、BR 及UE 方面，MBD 明显优于TP[4]、RPS[16]。这是由于：TP[4]采用曲率规则项约束分割区域的紧致性从而造成分割边界贴合度低；RPS[16]采用了垂直水平边界交叉点的最短路径连线，约束了其不规则形状的分割性能。一方面，MBD 由于采用了基于MBD 的距离测度，导致优化过程中无法随意改动中心，因此限制了其分割边界贴合度的精确性；另一方面，MBD 避免了其他方法采用的多次迭代直到收敛的优化方式，提高了运算效率，因此执行时间比其他方法更短。

表1 不同算法在100 块超像素下的分割性能指标

图2 示出了不同方法在100 块超像素分割区域下的一些主观结果。图2 中每个子图从上向下依次排序为第1 幅图、第2 幅图、第3 幅图、第4 幅图。可以看出，本文方法不仅获得了高的边界贴合度，同时获得了规则紧致的分割区域，验证了本文方法的有效性。例如：第1 幅图中，相比其他方法，MBD 完整地分割了地面的道路区域；第2 幅图中，MBD、FH[14]、LSC[8]和ERS[15]能够分割出支架；第3 幅图中，MBD 能够精确完整地分割出太阳，相反，其他大多数方法未有效分割出太阳；第4 幅图中，MBD 准确地分割出了沙发的边缘。综上所述，本文方法对于具有较强结构性的目标区域有较好的分割性能。这是由于采用了基于最小栅栏距离能有效区分相同颜色目标的边界结构信息，而基于欧式空间距离的分割方法无法检测到结构边界，因而降低了分割性能。图中还可以看出，FH[14]、LSC[8]、ERS[15]能够较好地贴合对象边缘，但是得到的分割区域缺乏规则性，而本文方法不仅可以获得相对高的边缘贴合度，还保持了较强的区域规则性。