基于测地距离的超像素分析算法

颜玉杰，刘向阳

(河海大学 理学院，江苏 南京 211100)

0 引 言

超像素是指具有相似纹理、颜色、亮度等特征的相邻像素构成的具有一定视觉意义的不规则像素块。图像分割是按照灰度、频谱、纹理等特性把图像空间划分成一定数量区域的过程，是近年来快速发展的一种图像预处理技术。相比于传统处理方法中的基本单元——像素，超像素更有利于局部特征的提取与结构信息的表达，并且能够大幅度降低后续处理的计算复杂度，在计算机视觉领域尤其是图像分割中得到了广泛的应用。

近年来，很多学者提出了超像素分析算法。超像素生成算法大致可分为基于图论的算法和基于梯度下降的算法两类，具有代表性的基于图论的超像素分析算法有Shi等人提出的Ncut(normalized cuts)算法,利用轮廓特征和纹理特征递归地进行图分割；Liu等人提出了基于熵率算法，通过最大化目标函数以实现分割；Bergh等人提出了基于能量驱动的SEEDS算法；Chen等实现了一种基于NC的线性谱聚类(LSC)算法；Gong等基于差分进化(DE)提出差分进化超像素(DES)算法。对于基于梯度下降法，已有的研究有Vincent等人提出的分水岭(watersheds)算法,是一种基于拓扑理论的数学形态学分割算法；Comaniciu等人提出的Mean-shift算法，是一个迭代模态搜索的过程；Achanta等人提出的SLIC(simple linear iterative clustering)算法,是基于颜色和距离相似性进行超像素分割，该算法思想简单，可以生成大小均匀、形状规则的超像素；Zhao等提出一种改进SLIC搜索策略的超像素快速线性迭代聚类FLIC算法；Ban等提出一种高斯混合模型(GMM)的超像素算法。其中SLIC是目前最为经典、简单的算法，该算法比现有算法更快，有着更高的记忆效率，展示了目前最优的边界贴合度。它是采用

k

均值聚类算法生成超像素，在图像上大致均匀地选取

k

个像素点，计算

k

个超像素内所有像素点的平均向量值，重新得到

k

个聚类中心，然后不断更新聚类中心，直到收敛的过程。

该文提出了一种归属于第一类的基于测地距离的超像素分析算法，该算法是定义初始划分区域内局部密度最大的像素点作为种子点，然后由种子点出发计算测地距离，完成超像素划分的过程。和传统算法相比，该算法的优点在于：生成超像素的形状紧凑度更高，并且边界贴合度也更接近于SLIC算法。

1 图像测地距离与Fast Marching算法

1.1 图像测地距离

n

维空间中，曲面上任意两点之间测地线的长度称之为测地距离。该文把测地距离应用于图像分析，就是因为测地距离是计算空间中任意两点的曲面最短距离，可以更好地描述联通的像素点的局部相似性。具体表达式如下：

(1)

式中，

I

表示输入图像，

d

为空间上任意两点

z

、

z

的测地线的距离，

D

为像素点

z

的测地距离，

P

表示

z

、

z

两点间所有路径的集合，

M

为二值掩码，‖Γ(

s

)‖:R→R表示这样的一条路径，其中参数

s

∈[0,1]，Γ(

s

)=∂Γ(

s

)

/

∂

s

，

u

=Γ(

s

)

/

‖Γ(

s

)‖。

测地距离的计算方法主要有两大类，一类是基于图的方法，将曲面看作是一个图，把在图上计算最短距离扩展到计算曲面上的测地距离。另一类是基于样本的方法，设定这里的曲面是离散可微的，许多微分几何中的方法可以用来计算曲面上的测地距离。当前流行的算法主要运用了两类偏微分方程模型：

(1)程函方程(双曲型方程)：

‖∇

u

‖=1

(2)

(2)热方程(抛物型方程)：

(3)

其中，波传播问题可以转化成求解程函方程的问题，而热扩散问题可以转化成求解热方程的问题。

1.2 Fast Marching算法

Fast Marching算法就是一种波传播方法，旨在通过求解正交网格离散化的程函方程获得测地距离的近似，具体公式如下：

‖∇

u

(

z

,

z

)‖=

C

in Ω,

C

>0

u

=

g

(

z

,

z

) on Γ

(4)

它是一种在矩形正交网格上以

O

(

M

log

M

)步为单位求解椭圆方程的数值算法，其中

M

是网格点的总数，Ω是R中的定义域，

C

是给定的已知函数，边界条件是

u

=

g

(

z

,

z

)，此处的边界是域Ω的边界，可以是一个特定的曲线或者曲面。解这个程函方程的中心思想是使用数值方法中的逆向有限差分来近似拟合，从而得到近似的数值解。

2 基于测地距离的超像素分析算法

2.1 初始化种子点

对于一幅大小为

M

*

N

的图像

I

，图像中每个像素的颜色在CIELAB颜色空间[

l

a

b

]中表示，其取值范围是已知的，而像素的位置[

x

y

]的取值范围随着图像的尺寸变化而变化，所以每个像素点的五维向量表示为[

x

y

l

a

b

]。如果简单定义像素点间的距离为

xylab

空间中的五维欧氏距离将导致不同超像素大小的聚类行为不一致。对于较大的超像素，空间距离远超过颜色距离，因此空间距离会比颜色距离更重要，这样会产生紧凑的超像素，而对于较小的超像素，情况刚好相反。为了权衡这两个距离，该文添加了一个颜色权重

ω

。计算初始区域内每个像素点的局部密度，将局部密度最大值

ρ

对应的像素点作为种子点，目的就是为了选取相对比较大的平滑区域的中心。2014年Alex Rodriguez在新聚类算法(DP算法)中提出了局部密度概念。对于局部密度这个指标的计算,首先要计算出像素点集

z

={

z

,

z

,…,

z

*}中任意两点间的欧氏距离：

(5)

再将像素点的局部密度定义为“数据集中到该点距离小于截断距离

d

的数据点个数”。该文采用高斯核函数计算局部密度，这样计算不同的数据点具有相同的局部密度值的概率会更小。即：

(6)

其中，

d

为截断距离，是算法中的可变参数。

2.2 图像测地距离计算

由上述步骤选取的种子点出发，该文基于引入代价函数的Fast Marching算法计算搜索范围内像素点间的测地距离。在处理一幅大图像时，Fast Marching算法由多个初始点出发计算测地距离的时间代价太大，因此该文设计了一种新的算法，不再是从整体上计算一个图像多个起始点的测地距离，而是缩小了每个种子点的搜索范围来计算测地距离，最后将得到的距离矩阵进行整合。

2.2.1 算法代价函数

设定义在二维平面上的曲线是其法线方向向上的速度

v

，如果曲线经过种子点

z

的时间为

T

，那么在路径规划中最小代价求解问题的Eikonal方程通常写成：‖

T

(

z

,

z

)‖

v

(

z

,

z

)=1

(7)

其中，

T

(

z

,

z

)为时间距离函数，为拓展代价函数，该算法定义的代价函数为：

(8)

通过上述方程再结合式(5)可以求解时间距离函数，进而可通过Fast Marching算法求得种子点与其余像素点之间的测地距离。

2.2.2 测地距离的计算

对于任意一个种子节点

z

，利用Fast Marching算法计算像素点间的测地距离。初始化源点距离为0，其他顶点距离为Inf:

d

(

z

)=0,

d

(

d

)=∞(

l

≠

s

)，设置源点状态为Open，其他顶点状态为Far，查找集合Open中距离值最小的顶点

z

，将其状态更新为Dead，将顶点

z

相邻状态为Far的顶点状态更新为Open，然后开始进行循环迭代，查找顶点

z

相邻状态为Open的顶点

z

，遍历顶点

z

的一环邻域三角面片，利用Eikonal方程计算顶点

z

的距离值

d

，记录

d

，通过循环不断地更新顶点

z

的距离值

d

(

z

)=min{

d

(

z

),

d

}，重复上述过程，就可以计算出每个种子节点

z

的测地距离

D

。种子节点

z

的搜索范围变小，会导致有些像素点的测地距离被重复计算，对于某个像素点

z

的测地距离

D

,

D

,…,

D

，定义该像素点的测地距离为min{

D

,

D

,…,

D

}，(

q

为该像素点被重复计算的次数)。如此，就可以得到与原图像同等大小的

M

*

N

的距离矩阵。

2.3 超像素划分

本节主要提出了一种基于图标签的标记方法，旨在通过此算法，将已标记簇标签的局部密度最大的像素点的标签传递给所有剩余像素点，迭代此过程直到所有像素点拥有相应的标签为止，形成最终的超像素划分。使用该算法可以动态地将局部密度最大的像素点同时对剩余未分配标签的像素点进行标记。记种子点

z

的八邻域内的像素点集为{

z

,

z

,…,

z

}，从中找到未标记的且与种子点的测地距离最小的像素点

z

，那么

z

的标签就赋给像素点

z

，具体公式如下：

(9)

其中，

L

(

z

)表示种子点

z

的标签，约束条件为

H

:|

D

-

D

|<|

D

-

D

|,(

r

,

e

∈[1,8],

r

≠

e

)，其中|

D

-

D

|表示像素点

z

、

z

之间测地距离差的绝对值，该公式可以判定当像素点自身已有簇标签的时候可以将簇标签

L

(

z

)传递至未标记的像素点

L

(

z

)，如此完成一次标记。重复上述步骤，直到每个像素点都有对应的标签，即完成超像素的划分。

2.4 流程图

该算法主要分为以下几个步骤进行，首先是基于指定的

k

值将图像划分成大致均匀的长方形区域；然后计算每个区域像素点的局部密度，将局部密度最大的像素点作为种子点；再从种子点出发，计算像素点间的测地距离；最后根据测地距离，找到像素点的标签，完成超像素划分。算法流程如图1所示。

图1 算法流程

3 实验结果及分析

为了验证文中超像素分析算法的性能,在Berkeley Benchmark标准数据集上选取10张有代表性的图片进行了对比实验，验证算法包括文中算法、SLIC、SEEDS、Watershed等。评价标准包括ASA、SRC等。实验中取数据集中所有两点间距离值的1%～2%。

3.1 评价标准

利用可达分割精度(ASA)参数计算超像素分割算法的效率，并将超像素与地面真值分割的标签进行比较。ASA参数定义为：

(10)

考虑到超像素边界与人工标记边界存在误差，在人工标记边界的24邻域寻找超像素的标签。另外，紧密度是衡量超像素的重要评价指标，Giraud在2017年提出新的形状规律准则(SRC)以描述超像素的形状紧凑度。SRC考虑了形状凸性、平衡再分配和轮廓光滑三种形状规则属性。形状规律性标准定义如下：

(11)

式中，

Z

={

Z

,

Z

,…,

Z

}，

Z

为第

k

个超像素，CR(

Z

)为圆形凸包覆盖率，

V

(

Z

)为最小位置与最大位置方差比值。

3.2 算法参数分析

文中算法需设置的参数有超像素数量

k

和像素点的颜色权重

ω

。通过调整参数可以使得分割结果更加符合预期，对于每幅图的评价结果取算数平均数作为该算法在某超像素数量下的最终评价值。为了便于评价，把超像素数量设置为

k

=1 000，观察可达分割精度ASA、形状规律准则SRC在

ω

改变时所发生的变化(见图2)。

图2 参数ω调整结果

由实验结果可知，当颜色权重

ω

设置过小时，可达分割精度ASA的值较低，会导致超像素的边界与图像边界贴合度不高，而超像素规整度SRC较高，为了权衡这两者，设置

ω

=0

.

5，超像素分割的结果会更好。由图3可知，当超像素数量

k

设置的较大时，超像素的紧凑度与精确度都可以达到一个较高的值，对于处理更大的图像时，文中算法会取得一个更优的结果。

图3 参数k调整结果

3.3 实验结果比较与分析

为了便于评价，超像素数量值统一设置为1 000、2 000、3 000、4 000、5 000。对所有的分割结果，分别利用上述两种评价标准进行评价，对每幅图的评价标准取算数平均数作为该算法在某超像素数量下的最终评价值。图4、表1分别为ASA、SRC指标的比较结果。图5为SLIC、SEEDS、Watershed和文中算法以

k

=1 000、

k

=3 000为示例划分图像的结果。

图4 不同超像素算法的ASA对比

表1 不同超像素算法的SRC对比

(a) k=1 000 (b)k=3 000

由上述图表可以看出，文中算法生成的超像素规整度明显优于其他算法，而可达分割精度ASA也与其他算法相接近。综合上述，文中算法生成的超像素整体效果较好，预计在处理更大的图像时，会取得一个更好的效果。

由图5的划分结果可以看出，文中算法与SLIC算法得到的超像素形状更为规整，对于图像中不平滑的区域，SLIC算法所得超像素不能保持更好的形状规律准则，而文中算法却在保持分割精度的同时，使得所得超像素的规整度更优。

4 结束语

该文提出了一种基于测地距离的超像素分析算法，大量实验结果表明，算法的分割精度较好，当预期分割数较大时其ASA值优于SLIC算法，并且该算法生成的超像素形状规整度更好。综合来看，提出的基于测地距离的超像素分析算法的划分结果较好，且能稳定生成形状规整的超像素。接下来会进一步优化该算法，加快算法的运行速度以及提升超像素的分割精度。