基于改进的K?means聚类算法水下图像边缘检测

赵凤娇　贺月姣

摘 要： 边缘检测被广泛用于图像分析与处理中，由于水的吸收和散射效应，传统的边缘检测算法对于水下图像得不到较好的效果。在此应用一种新的方法来得到较准确的水下图像边缘，首先，将原始图像使用暗原色先验算法进行处理得到较清晰的水下图像；然后，使用梯度幅值边缘检测算法检测出初始边缘，在初始边缘上检测出端点，使用改进的K?means聚类算法对端点进行分类，从而确定背景和目标灰度值接近的区域作为窗口；最后，在窗口内使用梯度幅值检测边缘，通过多个窗口的并集得到最终边缘。实验结果表明，边缘检测效果得到明显的改善。

关键词： 边缘检测； 暗原色先验； 图像分析； K?means

中图分类号： TN911.73?34 文献标识码： A 文章编号： 1004?373X（2015）20?0089?03

Abstract： Edge detection is widely used in image analysis and processing. The traditional edge?detection algorithms are always ineffective to underwater images due to the absorption and scattering nature of seawater. A new approach is used in this paper to obtain the accurate edges of underwater images. Firstly， the original image is processed with the dark primary colour prior algorithm to get the clearer image. Then， the initial edge is calculated by the gradient magnitude edge detecting algorithm， the endpoints in the initial edge of the image are detected， and the modified K?means clustering algorithm is used to classify the endpoints to determine the region where the gray?scale of background and target is approximate as the window. Finally， the edge is detected in the window by the adaptive gradient magnitude， and then the final edge is got by union set of multiple windows. The edge detection result is significantly improved.

Keywords： edge detection； dark primary colour prior； image analysis； K?menas

图像边缘检测是图像处理与分析中最基础的内容之一，被广泛用于特征描述、图像分割、图像增强、模式识别以及图像压缩等。因此，边缘检测在图像处理与分析中成为一个研究热点，新的理论和方法不断地被提出。目前经常使用的算法有Roberts，Sobel，Prewitt， LoG，Canny，Kirsch等，但这些经典的边缘检测方法不能很好地用于水下图像。本文使用一种改进的边缘检测算法来得到较准确的水下图像边缘。

1 图像处理：暗原色先验

由于水体对光的吸收效应和散射效应使得水下图像有严重的非均匀亮度和细节模糊、信噪比很低、对比度明显变差，因而水下图像极不理想。本文使用暗原色先验方法得到相对清晰地原始图像。

1.1 水下光的物理特性

根据 McCartney model[1]， 图像模型如下：

[Ix=Jxtx+A[1-tx]] （1）

式中：I为输入的场景图像；J为场景辐射率；A为大气光成分；t为光线透射率。

透射率t可表示为：

[tx=e-a+bdx] （2）

式中：a为吸收系数；b为散射系数；d（x）是景物深度。

1.2 暗原色先验

根据Hes research[2]，该理论认为：在绝大多数户外无雾图像的局部区域里，至少存在一些像素，其一个颜色通道的强度值很低。He统计了5 000多幅图像，暗原色通道的统计结果如图1所示。大约75%的暗原色通道的像素值为0，90%的像素值低于0.25。

1.3 暗原色先验算法

算法流程图[3]如图2所示。在水下图像中，限定的局部区域内存在至少一个颜色通道的强度值很低，假设这个区域为Ω（x），则水下图像J的暗原色可表示为：

2 边缘检测

2.1 初始边缘检测

首先使用Sobel[4]算法检测出初始边缘，将边缘细化[5]为一个像素。将细化后的边缘作为初始边缘并记为einit。

2.2 端点标记

端点标记算法：

（1） 取初始二值边缘einit上的一个像素值为1的边缘像素点Q；

（2） 将该像素点的8邻域内的像素值按照顺序展开成一维数组，并在该一维数组中寻找模式“01”个数C；

（3） 将当前像素点的值Q和C做“与”运算，若计算结果为1，则说明该点是端点，否则不是；

（4） 取下一个没有检测过的的边缘点，循环执行步骤（2）与步骤（3），直到所有边缘点被检测完。

2.3 确定窗口大小

使用K?means聚类算法[6]对检测出的N个端点进行分类，假设初始边缘端点为{（x1，y1），（x2，y2），…，（xN，yN）}，使用改进的K?means聚类算法将N个边缘端点分成k类，若第i（i=1，2，…，k）个分类的集合为[Ci=（x1i，y1i），（x2i，y2i），…，（xni，yni）]，则第i个窗口上下左右边界分别为：

[wui=miny1i，y2i，…yni；]

[wdi=maxy1i，y2i，…yni；]

[wli=minx1i，x2i，…xni；]

[wri=maxx1i，x2i，…xni；]

因此[wi=wli：wri，wui：wdi]。

K?means算法的基本思想是初始随机给定k个聚类中心，按照最邻近原则把待分类样本点分到各个聚类中。然后按平均法重新计算各个聚类的质心，从而确定新的聚类中心。一直迭代，直到类心的移动距离小于某个给定的值。

根据Tou and Gonzalez[7]传统K?means算法步骤如下：

（1） 选取k个初始聚类中心z1（1），z2（1），…，zk（1）。

（2） 计算每个点到聚类中心的距离，将每个点聚类到离该点最近的聚类中去，即若[||x-zj（k）||<||x-zi（k）||]，则[x∈Cjk， j=1，2， …，k；i≠j；]Cj（k）表示聚类中心为zj（k）的样本集。

（3） 重新计算聚类中心zj（k+1）：

[zjk+1=1Njx∈Cjkx， j=1，2， …，k]

式中：Nj表示样本集Cj（k）的样本个数。

（4） 如果[zjk+1=zjk， j=1，2， …，k]，停止迭代；否则转到步骤（2）。

改进的聚类算法[8]：传统的K?means聚类算法要求必须先给出分类个数k，然后随机选取k个对象作为初始聚类中心，并且算法对初始值敏感，对于不同的初始值，可能会导致不同的聚类结果。本文对传统的K?means算法进行改进，通过计算得出较好的聚类个数与聚类中心，改进步骤如下：

（1） 将分类端点转换为7个不同维数的二维矩阵；

（2） 计算每一维数矩阵的平均值，平均值相同的舍去其中一个，然后将平均值升序排序；

（3） 平均值个数与平均值分别作为聚类个数与聚类中心。

2.4 获取最终边缘

将初始边缘基础上找到的聚类区域映射到原始图像，然后对原始图像中的相应区域使用梯度幅值边缘检测算法监测区域内的边缘，可得到区域内较好的边缘效果；若要得到整幅图像的边缘，则只需要将每个区域的边缘和初始边缘求并集即可。假设第i个窗口内检测到的边缘为eωi，则将初始边缘和每个窗口区域内的边缘求并集即可得到最终的边缘e，即[e=i=1keinit∪eωi]。

3 实验结果

在海洋实验中，获得图片如图3（a）所示，经过暗原色先验算法进行处理过的图像如图3（b）所示。经过Sobel，Canny[9]，Prewitt[10]和改进算法所得到的边缘图像如图3（c）～（f）所示。实验结果显示，Sobel和Prewitt算法均不能获得相对较完整的图像边缘，Canny算法可以得到完整的边缘，可是存在太多的冗余边缘，细节较多。本文算法相比于传统算法有较大改善，不但去除了很多不必要的冗余，而且可检测到相对完整的边缘。

4 结 论

本文提出了一种新方法用于处理水下不清晰图像，并获得相对较完整的边缘。实验结果显示暗原色先验算法可以有效的去除后向散射噪声，增强图像的分辨率和对比度。传统的边缘检测方法对于检测水下图像边缘效果不理想，改进的算法可以检测出相对完整的边缘。

参考文献

[1] MATTIS M P， PESKIN M E. Systematics of πN scattering in chiral soliton models [J]. Physical Review D， 1985， 32（1）： 58?62.

[2] HE K， SUN J， TANG X. Single image haze removal using dark channel prior [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2011， 33（12）： 2341?2353.

[3] WANG Z， ZHENG B， TIAN W. New approach for underwater image denoise combining inhomogeneous illumination and dark channel prior [C]// Proceedings of Oceans?St. [S.l.]： IEEE， 2013：111?116.

[4] ZHAO Jingdong， ZHAO Jingxiu. An improved self?adaptable algorithm of edge?detection based on the gradient magnitude[J]. Optoelectronic Technology， 2009， 2： 5?10.

[5] ZHANG T Y， SUEN C Y. A fast parallel algorithm for thinning digital patterns [J]. Communications of the ACM， 1984， 27（3）： 236?239.

[6] VASSILVITSKII S. K?Means： algorithms， analyses， experiments[M]. Stanford， CA USA： Stanford University，2007.

[7] TOU J T， GONZALEZ R C. Pattern recognition principles [M]. [S.l.]： Addison?Wesley Publishing Company， 1974.

[8] SAMMA A S B， SALAM R A. Adaptation of K?means algorithm for image segmentation [J]. World Academy of Science， Engineering and Technology， 2009， 50： 58?62.

[9] 王植，贺赛先.一种基于Canny理论的自适应边缘检测方法[J].中国图象图形学报，2005，9（8）：957?962.

[10] GONZALEZ R C， WOODS R E， EDDINS S L. Digital image processing using Matlab [M]. India： Pearson Education， 2004.