一种基于加权切比雪夫距离的图像分割方法

毛 鑫，蔡江辉，张素兰

(太原科技大学 计算机科学与技术学院，太原 030024)

近年来计算机视觉受到了越来越多的关注，图像分割作为计算机视觉的热度也一度飙升。图像分割的任务是将图像分成若干个互不重叠的子区域，从而使得同一个子区域内元素相似性较高，不同的子区域间元素相似性较低。传统图像分割方法[1]主要分为：基于区域、基于边界、基于数学形态学、基于神经网络、基于活动轮廓模型、基于遗传算法和基于图论等。其中基于区域的分割方法，是按照对应的相似性度量将原始图像分成不同的区域，主要包括种子区域生长法，区域分裂合并法、分水岭算法等。

图像分割技术得到了广泛的应用，例如关于发现混合纤维网中纤维的分布情况，梁振江[2]在全局阈值法和局部自适应阈值法的基础上对图像分割算法进行了改进。王思怡[3]等人也针对井道图像抽析问题提出了基于Grabcut算法的井道图像抽析方法，它可以精确确定数据区域，同时可以迅速将目标和背景分离出来。肖晓明[4]等人也提出了一种基于图像强度阈值和自适应切割的图像增强方法。将图像直方图根据图像亮度阈值信息分为亮区域直方图和暗区域直方图，使得增强后的图像不仅有完整的细节像素信息，同时与原始图像的内容大程度一致。但上述算法都不同程度地存在一些局限性，例如基于Grabcut算法的井道图像抽析方法使用Grabcut函数需要根据传入的所需参数，进行前景与背景分离，并结合Otsu算法进行最终图像分割，但是会因识别错误的边界，产生误分割现象。所以相似性度量方法的选取会直接影响整体图像分割算法的效率。

在大多数图像数据集采集过程中，往往会因为采集机器的材料属性，工作环境，电子元器件等因素，或是周围环境的亮度，潮湿度，背景等因素造成图像中存在少量干扰真实图像的噪声信息。传统滤波去噪方法例如算术平均滤波法和中位值平均滤波法，存在运行速度较慢，占用内存较大等问题。并且传统的图像分割相似性度量仅仅局限于距离度量或是颜色空间的度量[5]，所获得的图像信息较为单一，使得一些重要的图像信息容易被忽略。同时，相似性距离的度量方式会直接影响图像分割算法的最后结果。基于传统切比雪夫距离度量方式的图像分割一般存在忽略各个像素信息分量的协方差，期望等不一致性的问题。

针对以上提出的局限性，本文提出了基于加权切比雪夫距离的图像分割算法，解决了去噪过程中运行时间较长的问题，也在一定程度上改善了传统切比雪夫距离的局限性。本文先将扫描到的像素矩阵进行阈值去噪，得到基于RGB颜色空间的特征向量，然后再使用加权切比雪夫距离公式进行相似性度量，其中权值被选择为每个像素特征向量标准差的幂，标准差向量由GT数据[6]估算得到。最终将相似性度量得到的相似矩阵作为谱聚类算法的输入，得出图像分割结果图像。

1 相关研究

1.1 加权切比雪夫距离

在数学中，切比雪夫距离是一种定义在向量空间上的度量方法。它也被称为棋盘距离，即棋子从一个位置移到另一个位置需要走的步数大小。

切比雪夫距离可简单理解为各坐标数值差的最大值。从数学的角度来说，一致范数(或上确界范数)可以派生出切比雪夫距离。切比雪夫距离的应用场景十分广泛，张琳[7]利用切比雪夫距离来建立模糊相似矩阵，并结合传递闭包法对学生的考试成绩进行了聚类处理；杨威[8]等人提出了一种基于利用切比雪夫距离的密度计算方法与传统Kmeans相结合，根据切比雪夫距离的计算方法来计算数据源中数据点的密度，不断迭代，有效地提升了Kmeans算法的性能。传统切比雪夫距离的公式如下：二维平面两点A(x1,y1)与B(x2,y2)间的切比雪夫距离为式(1):

d12=max(|x1-x2|,|y1-y2|)

(1)

也可表示为式(2)：

(2)

加权切比雪夫距离在MS-VTA算法[9]中用于监督分类处理，以最小切比雪夫距离确定了输入像素的类别。本文将加权切比雪夫距离作为相似性度量方式，用于构成对应图像的相似矩阵。加权切比雪夫距离公式如下：

(3)

式(3)中，L代表图像像素维数,σ代表使用GT数据计算出的对应L维向量的标准差向量，dij为像素点i和像素点j的加权切比雪夫距离。

2 相似矩阵的构造

相似矩阵的建立是ISWCD算法的核心步骤，包括两个部分，第一部分是在RGB颜色空间中使用颜色空间的像素信息、梯度信息和邻域信息进行阈值去噪处理，提取特征向量。第二部分中，使用加权切比雪夫距离对特征向量进行相似性度量。本文通过对去噪后RGB颜色空间上的像素特征向量进行加权切比雪夫距离的计算，得出最后的相似矩阵。

2.1 颜色空间

颜色空间是在标准情况下对色彩进行说明的一种方式，其独立的三个特征r、g和b构成了空间坐标。除RGB颜色空间之外，还有HSV、HSI、LAB等颜色空间，由于大多数的图像信息保存在RGB颜色空间中，当使用其他颜色空间进行特征提取时，需要将空间模型相互转换，从而增加实验的计算成本。因此，选择RGB颜色空间作为本文的颜色空间。

在RGB颜色空间中，首先将扫描到的数据图像像素矩阵进行去噪处理；然后，根据输入的mixb阈值分辨出梯度值突变的像素点的位置或是否为噪声点。若像素点在邻域内或边界上则保留；若为噪声，则将该点删除。

2.2 距离度量

为提高相似矩阵的精确性，对颜色空间的特征向量进行基于距离的相似性度量，常用的距离度量方式有欧式距离、曼哈顿距离、切比雪夫距离、欧式距离、马氏距离、汉明距离、余弦距离等。本文选取了加权切比雪夫距离作为图像分割距离度量方式，并与余弦距离和马氏距离进行实验结果的对比。

马氏距离[10]D2是一种广义的平方距离，基于多元正态分布理论，综合考量三个参数：均方差、均值和协方差。马氏距离能够综合整体的多元指标，从而对相应任务做出判定[11]，其在空气检测、材料资源探测、环境污染研究等方面有广泛的应用。马氏距离的核心计算公式为：

(4)

(5)

其中S为原始数据的协方差矩阵，表示为：

(6)

其中Skl计算公式为：

(7)

余弦距离[12]近年来广泛应用于文本分类等多维空间中。例如将两篇文章向量化，余弦距离可以生成两篇文章向量的夹角，能够避免较高维度下，由于文章长度不同而导致的计算距离不准确问题。两个向量间的余弦距离公式如下：

其中dij为余弦距离，表示为：

(8)

其中φij计算公式为：

(9)

3 基于加权切比雪夫距离的图像分割算法ISWCD

本节将对ISWCD图像分割算法进行详细介绍，3.1节阐述本算法的基本思想，并在3.2节详细描述ISWCD算法步骤。

3.1 基本思想

本文提出一种基于加权切比雪夫距离的图像分割算法，其步骤如下：首先，提取阈值去噪后的RGB颜色空间的特征向量；然后，使用加权切比雪夫距离计算相似矩阵；最后，将相似矩阵输入到谱聚类算法中，得出图像分割结果。

ISWCD算法的第一步是先将待处理原始图像扫描至像素矩阵，同时获得对应的梯度信息，因为梯度值突变的位置容易产生边界点或噪声点，所以当梯度值大于所设定的梯度阈值时，需要进行下一步识别，即将其邻域空间分割成4*4的区域，然后，对邻域内的像素点个数进行统计，若大于所设定的邻域阈值时，则说明该点位于区域内；若等于阈值，则说明该点为边界点；若小于阈值，则说明该点位噪声点，需将这个点的像素信息删除。遍历处理过整个图像之后，对得到的RGB像素矩阵进行特征提取，得到多个特征向量。其次将特征向量和加权切比雪夫距离计算公式(3)计算出对应的相似矩阵R.这里使用的是加权后的切比雪夫距离，相较于传统的切比雪夫距离多了权值的计算。最后，对距离度量得到的相似矩阵进行谱聚类，得出图像分割结果。聚类算法的输入为相似矩阵R，其中rij代表i点与j点之间的相似性，数值的高低对应代表着相似程度的高低。

3.2 算法描述与分析

本文提出一种基于加权切比雪夫距离的图像分割算法，第一步提取阈值去噪后的RGB颜色空间的特征向量，其中根据邻域阈值mixb进行阈值去噪，第二步，将提取出的特征向量使用加权切比雪夫距离计算，得到对应的相似矩阵，最后，将相似矩阵输入到谱聚类算法，使用knn计算相似矩阵R，由R计算度矩阵D和对应的拉普拉斯矩阵L，对L进行标准化处理D-1/2LD-1/2，对标准化后的矩阵进行特征值分解，然后将特征向量作为输入进行K-means聚类，从而得到聚类结果即图像分割结果。算法的伪代码如下所示：

算法1 ISWCD算法(Image Segmentation based on Weighted Chebyshev Distance)输入: 图像D；邻域阈值mixb

输出：结果图像ai

For给定图像D像素点do

提取像素矩阵W

计算W中的梯度值h

IFh发生突变then

将附近区域按4*4邻域进行分割，并计算邻域内像素个数q

IFq

该像素点为噪声点，去除该点

得到处理后的像素矩阵W1

对W1进行特征提取，输出由r值，g值和b值构成的特征分量k.

For所有特征分量kdo

用公式(7)、(8)、(9)、(3)

计算出基于不同距离度量方式的三个相似矩阵R1,R2和R3；

将R1,R2和R3分别输入到谱聚类中

ForR1,R2和R3do

Ri=Ri- diag(diag(R))

D=diag(sum(Ri)

L=D^(-.5)*R*D^(-.5)

找到前K个特征向量并排序，得到矩阵X

Xsq = Xuse.*Xuse

divmat=repmat(sqrt(sum(Xsq')'),1,2)

Y=Xuse./divmat

将归一化后的矩阵Y输入到Kmeans聚类中

输出聚类结果图像ai

本文提出的阈值去噪方法相较于常用的滤波去噪法计算速度更快，只需遍历像素点并进行比对，若梯度突变则进行邻域扫描，可以在完成任务的基础上较大程度地减少计算难度。同时对RGB颜色空间进行特征提取也提高了整体算法的效率。为减少后续步骤的计算量，选取较大的像素矩阵中的对于图像分割最有效的特征信息，从而实现对像素颜色空间的维数压缩。

4 实验分析

本文实验环境为WINDOWS 10操作系统，Intel(R)Core(TM)i3-4030U的CPU和4.0GB内存，从图像分割的精确率和效率两个方面对ISWCD算法进行评估。

4.1 数据描述

本文使用两个数据集进行实验,其中第一个数据集是Berkeley大学提供的BSDS300图像数据集[13]，其中包含200张训练图，300张测试图，分为color和gray两个文件夹，保存格式为seg.第二个数据集是来自国际计算机竞赛PASCAL VOC挑战赛的VOC2012数据集，提供了类别层面和个体层面的标注，包含人、动物、交通工具等20个类别，该数据集适用于图像分类，分割和检测任务。BSDS300和VOC2012数据集描述如表1所示。

表1 数据集描述Tab.1 Descriptions of data sets

本文首先从两个数据集中选出五张具有代表性的图像如图1所示，并利用其进行范例实验。其中数据(a)是人像图像，轮廓简单，但亮度较低。数据(b)是动物图像，皮色分布较为复杂，亮度中等。数据(c)、(d)和(e)都是环境图像，但图(c)侧重于测试算法在图像整体亮度低，轮廓较为模糊的情况下的鲁棒性。图(d)为光线正常的环境图像，方便与其他环境系列图像进行对比。图(e)的图像是受气候影响较大时的数据图像，测试的是有较多噪声存在时算法的鲁棒性。其图像的具体数据描述如表2所示，包括数据的分辨率、位深度和图像大小。

图1 图像A-EFig.1 ImageA-E

表2 五个图像数据的描述Tab.2 Descriptions of five image data

4.2 精确率

本次实验利用表1所示的两个数据集将ISWCD算法与其他三个算法(Otsu、CDA、MDA)进行精确率比较。其中Otsu为图像分割经典算法，CDA和MDA是在ISWCD算法的基础上使用不同的距离度量方式余弦距离(Cosine Distance Algorithm,CDA)和马氏距离(Markov Distance Algorithm,MDA).参数mixb的初始化选取极大影响噪声点识别的精确率，经过多次实验，mixb为15时去噪效果较好，所以将mixb初始值设为15.

精确率PA(Pixel Accuracy)表示分割正确的像素占总像素的比例，如公式(10)所示，其中，k表示分割区域的个数，Pij表示本属于区域i但被分割为区域j的像素点数量，Pii表示分割正确的数量。

(10)

图1中的五幅图像数据在四种算法下的实验结果如图2-图6所示，均包含四个子图a、b、c和d，分别为对应图像使用Otsu算法、MDA算法、CDA算法和ISWCD算法进行图像分割的结果，图6(e)为mixb=13时的ISWCD算法实验结果。表4为四种算法在两个数据集下的精确率均值。图像A-E在四种算法下的分割精确率如表3和图7所示，其中，ISWCD算法在数据C下分割的精确率较低，但是其精确率整体高于其他三个算法。由于图像数据C整体亮度较低，图像边界较为模糊，因此在提取时像素信息时容易忽略接近于背景色的物体轮廓。

同时，由于图像E中的干扰信息过多，ISWCD算法和Otsu算法都出现了不同程度的过分割现象，使得真正的目标信息受到一定程度的干扰。该图像中的噪声点较密集，需要降低mixb阈值的大小，将过于密集的区域进行邻域去噪处理。而ISWCD算法可以通过重新设置阈值mixb，从而缓解过分割现象，同时体现出ISWCD算法的鲁棒性。如图6(e)所示，将mixb改为13后,过分割现象减轻，效果优于mixb=15时的ISWCD算法和Otsu算法。

图2-图6中，因Otsu算法采用灰度处理，所以在最后的图像分割结果中仅呈现出图像轮廓和像素点位置信息。本文将RGB颜色空间的特征向量与距离度量方法综合考量，保存了关键像素点的像素值大小，因此，ISWCD算法、CDA算法和MDA算法都在一定程度上保存了色彩信息。

图2 图像A的四种图像分割算法结果Fig.2 Results of four image segmentation algorithms of image A

图3 图像B的四种图像分割算法结果Fig.3 Results of four image segmentation algorithms of image B

图4 图像C的四种图像分割算法结果Fig.4 Results of four image segmentation algorithms of image C

图5 图像D的四种图像分割算法结果Fig.5 Results of four image segmentation algorithms of image D

图6 图像E的四种图像分割算法结果Fig.6 Results of four image segmentation algorithms of image E

通过对比图7、表3和表4中不同算法的精确率可知，加权切比雪夫距离呈现出的相似矩阵能够更精确地提取出较多关键图像信息，最终图像分割的精确率较高。

表3 四种算法在图像A-E下的精确率Tab.3 The accuracy of the four algorithms underimages A to E

图7 四种算法在图像A-E下的精确率Fig.7 The accuracy of four algorithms under images A to E

表4 四种算法在两个数据集下的精确率Tab.4 The accuracy of four algorithms under two data sets

4.3 效率

为全方面评估图像分割算法，本节将效率作为第二个评估参数。图8和表5为四种算法在图像A-D下的运行时间对比，表6为四种算法在数据集1、2下的运行时间对比。由统计结果可知，ISWCD算法的运行时间最短，效率明显高于其它三种算法，CDA算法和MDA算法的图像分割精确率较低，但其运行效率普遍高于Otsu算法。

由图8和表5可知,图像D的四种图像分割算法运行时间普遍大于其他四幅图像。图像越大，扫描的像素矩阵越大，计算量增加，所以运行时间较长。因此，对像素矩阵进行特征提取能够提高图像分割速度。

图8 四种算法在图像A-E下的运行时间Fig.8 The running time of four algorithms under images A to E

表5 四种算法在图像A-E下的运行时间(s)Tab.5 The running time of four algorithms under images A to E(s)

表6 四种算法在两个数据集下的运行时间(s)Tab.6 The running time of four algorithms on two data sets(s)

5 结论

本文提出了一种基于加权切比雪夫距离的图像分割算法，首先，对原始图像进行阈值去噪处理，删除检测出的噪声点；然后，在RGB颜色空间内对像素矩阵进行特征提取，对提取出的特征向量进行加权切比雪夫距离度量，得出对应的相似矩阵；最后，根据相似矩阵通过谱聚类进行图像分割，得到对应的结果图像。实验结果表明了本文方法的有效性,对部分图像出现的过分割现象仍然需要进行进一步研究。