基于超像素的木材表面缺陷图像分割算法1)

胡峻峰 赵亚凤 曹军

(东北林业大学，哈尔滨，150040)

责任编辑:张 玉。

图像分割技术是木材缺陷图像分类的关键，分割的效果决定了之后特征提取的可靠程度以及最后分类的精度。图像分割作为缺陷分类的第一步，通过分割可以得到典型的缺陷区域，对这些区域再提取特征，样本学习和有监督分类。快速而精确的图像分割是正确在线分类的前提。

当前，对图像分割时多数以像素为单位对图像进行处理，图片较大时算法效率低，不符合在线要求。而人类视觉的着重点并不是像素，单一的某个像素点并不具有什么特定的意义，只有当包含一定特征的若干个像素点组合在一起时，人类视觉才能从中得到有效的信息。2003年，Feng Renxiao 等最早提出了超像素的概念。所谓超像素，是将许多具有相似性的像素点组合在一起进行处理，这个像素点的集合称之为超像素，利用像素与像素之间位置相邻，且颜色、亮度、纹理的相似程度，对像素进行分组，从而获取分组中所包含的可以进一步进行图像分割的有效信息，并保持原有图像中目标的边界信息，使后续图像处理任务的复杂程度大大降低。大量的研究工作表明，超像素技术已成功应用于图像处理任务，如:图像分割［1］、目标定位［2］、图像分类［3］、人体估计［4］、边缘提取［5］等。本文主要研究了基于SLIC(简单线性迭代聚类)的超像素分割方法，并对此算法进行了改进，将其更好的应用到木材缺陷提取中去。

1 SLIC 超像素分割

SLIC 算法在运算过程中，依据颜色相似程度和距离临近程度对像素进行聚类，得到相对紧凑并且特征规则的超像素。基于SLIC 的超像素分割算法，利用了同质区域内像素特征的相似性以及相邻的不同区域之间的边界信息，高效的生成了一个个结构紧凑、同质性强的超像素。基于SLIC 的超像素分割算法，适应性较好、分割结果的同质性较高，该分割算法已经广泛运用到图像分割、目标定位、人体模型估计、深度估计等众多领域。

2009年，Achanta 等在原有超像素分割的基础上，提出了简单线性迭代聚类算法。基于SLIC 的超像素分割算法，实现了基于像素颜色特征和像素空间位置特征的相似性聚类;该算法为了更好的表述图像的信息，将图像映射到CIELAB(国际照明委员会提出的一种颜色系统)颜色空间，并以此进行超像素分割。SLIC 算法在5 种维度［l，a，b，x，y］中进行计算，其中［x，y］是像素的坐标位置。CIELAB 是由CIE(国际照明委员会)制定的一种色彩模式，Lab颜色空间是被广泛认为的感知距离最小的颜色空间。Lab 空间取坐标［l，a，b］，其中:l 代表亮度;正数a 的为红色，负数的a 为绿色;正数的b 为黄色，负数的b 代表蓝色;它可以将任何颜色量化的表示在Lab 颜色空间中。

该算法的输入是超像素的个数(K)，对于1 幅像素数目为N 的图像，每个超像素的大小为K/N。对于超像素非常标准的图像而言，超像素与超像素的距离

该算法的计算过程:首先选择K 个超像素的聚类中心，接着在图像的xy 平面上选取一个2S ×2S的空间作为每个集群中心的搜索区域。

Ds是每个像素的色彩特征距离和空间位置特征距离的和，该值通过超像素距离(S)归一化得到。Ds中引入的变量m 用于控制超像素的紧密度，m 越大，空间距离越近，聚类越紧密。m 的范围可选在［1，40］。该值在实验中大致符合最大CIELAB 感知距离，并且很好地平衡了色彩相似度和空间邻近度。设定SLIC 分割块数k =100、m =20，对死节、活节、虫眼样本进行分割(见图1)。

图1 3 种缺陷样本分割效果

2 DBSCAN 超像素合并

DBSCAN(Density- Based Spatial- Clustering of Application with Noise，具有噪声的基于密度的聚类方法)［6］是一种简单的基于密度的聚类算法［7］。该算法利用类的高密度连通性，能快速发现任意形状的空间聚类。算法基本思想，在一定半径的区域中包含的样本数大于一定数目时，这些样本归于一个类。

算法主要有2 个参数，一个为阈值(Eps)，另一个是控制类生成的最小样本数(minPts)［7］。样本可分为核心点、边界点和噪声点。样本P 在阈值(Eps)范围内可达的样本数大于或等于minPts，则P为核心点。如果P 是核心点在阈值范围内的邻居点，且以P 为中心的Eps范围内包含的样本数小于minPts，则为边界点;既不是边界点，也不是核心点的样本，为噪声点。

根据样本之间的关联强弱，可以将样本之间的关系分为直接密度可达、密度可达、密度相连。样本q在以核心点P 为中心的簇内，则称q 与P 直接密度可达。若q 与P 不能直接密度可达，但有一个中间样本m 与这2 个样本都直接密度可达，则称q 与P 密度可达。比密度可达更弱的关联是密度相连，q 与P 之间有至少2 个的中间样本，则q 与P 密度相连。

首先，从数据库样本集中找到任意样本P，并查找样本集中阈值(Eps)范围内的所有样本;如果样本数大于或等于minPts，则P 为核心点，则以P 为中心，在Eps范围内的邻居与核心点共同形成一个簇。如果在簇内其他点也为核心点，以这些核心点为中心的簇将与之合并。如果样本P 在阈值范围内的样本数小于minPts，且不能与别的样本点直接密度可达，P 为噪声点。该聚类算法，是反复寻找从核心样本直接密度可达的样本，并将其加入到该簇，对核心点依据距离进行聚簇;同时，将所有与核心点相对距离最近的边界点也聚集到包含核心点的簇中。不断地进行聚类，直到完成对所有点的处理，符合条件的点完成聚簇;否则就标记为噪声点，最终排除掉噪声点，完成整个聚类过程。

算法步骤:

(1)检查样本库中未处理的样本P，如果P 没有标记归入某个簇或者标记为噪声，检查其邻域Nε(p)，若Nε(p)包含的样本数大于或等于minPts，建立新的簇C，并Nε(p)中的所有点标记为C。

(2)对C 中其他还没被处理的对象q，检查其邻域Nε(q)，如果Nε(q)包含样本数不小于minPts，将Nε(q)中没归入任何簇的样本加入C。

(3)重复(2)，继续检查刚才建立的簇C 中是否包含没有被处理的样本，直到簇C 中不再加入任何新样本。

(4)重复(1)～(3)，直到所有样本都归入了某个簇或标记为噪声。

可见，该算法可以在有噪声的数据中发现任意形状的聚类，但其时间复杂度较高，不适合于在线聚类，算法中对每个数据样本都进行邻域查询，是其时间性能低效的主要原因。本文主要从快速性方面改进算法，使之适应于缺陷图像的分割。

在计算数据样本之间的距离时，可以选择欧式距离。假设超像素分割后区域个数为N，给定数据集X={xm，m=1、2、…、N}，X 中的样本用5 个描述属性［Lmean，amean，bmean，ˉ，ˉ］表示，其中:Lmean、amean、bmean分别表示3 个颜色分量的块平均值为超像素块中心坐标。

可以通过距离d(xi，xj)衡量样本xi、xj之间的相似度，d(xi，xj)越小，样本xi、xj的相似度就越强;d(xi，xj)越大，样本xi、xj的相似度就越弱。利用与SLIC 聚类类似的距离信息，计算区域块在5D 空间的距离:

式中:dLab(xi，xj)为区域i、j 在颜色空间的相似度距离测量;Lmean、amean、bmean为颜色区域在L、a、b 颜色分量的均值;dxy(xi，xj)为区域i、j 的中心距离为区域中心位置;d(xi，xj)为合并后的距离;m1为距离权值。

笔者在分析缺陷图像时，发现SLIC 过分割后的小区域中，缺陷块与背景块的距离，明显大于背景块之间或者缺陷块之间的距离，而背景数量远大于缺陷数量。如果在算法开始计算区域块之间的距离，并对每个区域块与其他区域块的距离求和，缺陷图像块的距离和会明显大于背景块。

分割后，死节块数为107、活节块数为125、虫眼块数为106。由于像素大小为512 ×512，而颜色范围为0～255，并且在缺陷分割时，主要考虑颜色影响，距离权重选择时，选择m1=0.1。对分割后的每个区域求距离和(见图2)。

由图2可见:有区域块距离和出现极大值，该极大值为缺陷中心，对于图像中的距离最大区域，给其标志为Imax。在算法中，将该区域块作为聚类中心点，利用DCSCAN 算法，根据其他区域与该区域距离关系进行聚类。从距离矩阵中提取出极大值这列数据(见图3)。

图3 Imax 与其他区域距离关系

由图3可见:图2中峰值出现的区域块，与图3中谷值出现的区域块大部分重合。本文中设定区域和阈值(ThreSumdist)、Imax 距离阈值(ThreMaxdist)，区域i 同时满足Sumdist(i)大于ThreSumdist，且Maxdist(i)小于ThreMaxdist 两个条件，同DBSCAN 算法中Eps值的作用。

为了提高算法的运算速度，从2 个方面对算法进行改进:一个是利用最大区域距离和，判断出缺陷的中心，并以此为样本中心进行聚类，最快速度找到目标中心;二是在程序处理过程中，不重复处理已经处理过的点。从样本集中取出一个样本，判断它是否被处理过，如果没有，则检查其邻域Nε(p)，若Nε(p)包含的样本数不小于minPts，建立新的簇C，并Nε(p)中的所有点标记为C;重复以上过程，直到判断它可达范围内的所有数据，并将它们全部标记为已处理。如果已处理并标记，跳过该点进行下一个点的操作。所有数据都标记为已处理后，最后根据2 个簇是否可达来合并2 个簇。

利用以上步骤对图像进行超像素合并，确定阈值ThreSumdist=6 ×104、ThreMaxdist =1600，3 类图像分割效果见图4。修改阈值参数ThreSumdist =105、ThreMaxdist=3000，其分割效果见图5。

从以上结果可以看出:第二类阈值能较好的合并虫眼和死节图像，第一类阈值能较好的合并活节图像。主要因为:死节和虫眼缺陷的颜色特征与背景相比，有很大的差距;而活节缺陷的颜色与背景较为接近。主要利用颜色方差聚类，阈值较小时，能清晰的分离出活节缺陷，但此阈值时，虫眼和死节缺陷会将周围又较小变化的背景图像误分为缺陷;在阈值较大时，能较好的分离出死节和虫眼，但该阈值对应的活节图像合并，会有一部分信息丢失。由于图像颜色本身的差异，很难找到一个合适的参数能同时区分活节、死节和虫眼。由于在线分选时，3 类图像会随机出现，不能手动调整阈值，这需要找到阈值可调的算法，保证阈值的自动调整。

图4 第一类阈值的分割结果

图5 第二类阈值的分割结果

3 自适应阈值改进

目前很多学者提出了各种改进方法，针对自适应阈值确定也提出了很多算法;基于迭代寻优的算法能很好的得到分割阈值，但不满足在线要求。笔者对区域距离和的数据排序后发现，不同类型的缺陷，从最大值到最小值的曲线，呈现出2 种不同斜率的直线特性，其中斜率较大的为缺陷块，斜率较小的直线表现出背景块的性质。对中心区域与其他区域的距离排序也得到类似的特性(见图6、图7)。

图6 区域距离和降序排序曲线

图7 Imax 区域块与其他区域距离排序曲线

尽管死节、活节、虫眼在曲线特征上有差别，不同类型有着不同的斜率，但这些曲线都能很清晰的表现出转折点，该转折点离大斜率直线和小斜率直线的距离和最小，为缺陷和背景的分割点。笔者对以上的曲线拟合成2 条直线，求2 条直线的相交点，即为需要的离群点，该离群点即为分割图像的阈值。

基于以上的思想，自适应阈值的快速DBSCAN超像素合并算法步骤为:

(1)计算距离矩阵。利用距离计算公式，计算出超像素区域块之间的距离，构建距离矩阵D(i，j)，i、j≤N，N 为超像素块的数量。该矩阵是1 个对称矩阵，且对角线的值为0，需要计算的距离数量为N(N-1)/2。

(2)提取聚类中心区域。对距离矩阵的每行或者每列求和，得出每个区域的距离和Ds(i)，i≤N;求和的同时做最大值比较，记录距离和最大值对应的区域块K，将区域块K 设为缺陷中心区域;从距离矩阵中提取d(K，j)，j≤N，或者d(i，K)，i≤N，记为Dmax(i)，i≤N。

(3)自适应分割阈值提取。对Ds(i)和Dmax(i)排序，对排序后数据做前半段和后半段数据的直线拟合，计算2 条直线的交点，记为分割点。对2 组数组做同样的操作，得到2 个阈值。

(4)改进DBSCAN 算法的快速合并。minPts固定，设为3，并设置(3)中的2 个阈值为距离半径Eps1和Eps2，以区域K 为中心和起始点，在Ds(i)数组和Dmax(i)数组中，寻找半径范围内的直接密度可达点;如果数目大于minPts，对这些区域标记并合并为簇。按顺序搜寻其他点，已经被标记的不做运算直接忽略。对于没有标记的点，按照DBSCAN 算法判断是否为核心点，不为核心点的标记为噪声点，直到所有的数据全部标记。

利用以上的步骤，得到分割后的图像(见图8)。由图8可见:对于这3 类图像，自适应阈值分割能获得较好的效果;每类图像的分割边缘，比手动阈值的分割边缘更清晰和准确。该合并算法中最大的计算量为距离矩阵的计算，由于区域数量远小于像素点个数，算法复杂度低。在配置为intel 酷睿处理器、主频为2.2 GHz、内存为2.0 GB 的PC 机上，基于matlab2013b 平台，运算时间为0.20 s。

图8 自适应阈值聚类的分割结果

4 结束语

本文利用超像素分割算法SLIC 算法对有缺陷图像进行预分割，有较快的分割速度和好较好的边缘准确性。分析了DBSCAN 聚类用于该类超像素合并中算法的复杂度，固定阈值不适用于本文3 种图像的分割。笔者从提高算法速度和自适应阈值2方面对算法进行改进，提出了自适应阈值的快速DBSCAN 超像素合并，结果显示:对于3 类缺陷都能很好的分割，并且算法复杂度低。本文中的快速分割算法，基于SLIC 的分割及合并，时间在0.35 s 左右，能满足在线分选的要求。

［1］ Thompson David R，Mandrake Lukas，Gilmore M S，et al.Superpixel endmember detection［J］.IEEE Transactions On Geoscience And Remote Sensing，2010，48(11):4023-4033.

［2］ Miˇcušík Branislav，Košecká Jana.Multi-view superpixel stereo in urban environments［J］.International Journal of Computer Vision，2010，89(1):106-119.

［3］ Liu Bin，Hu Hao，Wang Huanyu，et al.Superpixel-based classification with an adaptive number of classes for polarimetric SAR Images［J］.IEEE Transactions On Geoscience And Remote Sensing，2013，51(2):907-924.

［4］ Li Shifeng，Lu Huchuan，Ruan Xiang，et al.Human body segmentation based on deformable models and two-scale superpixel［J］.Pattern Analysis and Applications，2012，15(4):399-413.

［5］ Fu Keren，Gong Chen，Yang Jie，et al.Superpixel based color contrast and color distribution driven salient object detection［J］.Signal Processing:Image Communication，2013，28(19):1448-1463.

［6］ 冯少荣，肖文俊.DBSCAN 聚类算法的研究与改进［J］.中国矿业大学学报，2008，37(1):105-111.

［7］ Liu Zhenhua，Jiang Zhenquan，Zuo Rusong.Study of fussy clustering of enginering geological environment with GIS［J］.Journal of China University of Mining ＆ Technology，2003，13(2):196-200.