【简介】均值平移算法与道路图像分割方法探讨

均值平移算法与道路图像分割方法探讨均值平移算法与道路图像分割方法探讨均值平移（MS，Meanshift）算法是一种有效的统计迭代算法，由 Fukunaga[1]于1975 年首次提出来的.但是直到1995年,Cheng[2]论文的发表才使该算法引起人们的研究兴趣,他 改进了MS算法中的核函数和权重函数，并将其应用于聚类和全局优化，扩大了该算法的适 用范围，从而掀起了研究和应用均值平移算法的热潮，代表性的文章是2002年Comaniciu的 文章[12]. 作为一种有效的统计迭代算法,均值平移算法的收敛性研究是应用的基础, Comaniciu[4]、李乡儒[13]等人分别对均值平移算法的收敛性进行了证明.近年来,均值平 移算法已被成功应用于非刚体目标跟踪、图像分割、滤波、边缘提取和信息融合等图像处 理的多个领域.该算法是一种非参数的核密度估计理论,是在概率空间中求解概率密度极值 的优化算法.它让每个点平移到密度函数的局部极大值处,即均值平移向量的方向与数据的 密度梯度估计方向一致.这种方法可以实现无监督、非参数的聚类[7]一、理论1 核密度估计非参数概率密度估计方法的核心思想是：某一点处的概率密度可以通过该点附近的一个小区域样本来估计。

Parzen [13] 推广了这种思想，并提出了基于核的密度估计方法定义定义 1.1：令 X 是 n 维欧式空间 Rn，xX，如果映射 k：[0, ]R 和 K：XR 满足关系（1.1  2K xckx） 且 k（x）非负、不增、分段连续，称 K（x）为核函数，k（x）为 K（x）的轮廓函数其 中，c 是一个比例因子 定义定义 1.2：令 xi, i = 1, 2, … , n 为 d 维空间中的 n 个样本点，在一个 d 维的超立方体中，采用核函数对某一向量 x 的概率密度估计定义为式（1.2）： （1.2） 11ˆni if xKxxnH式中： （1.3） 11 22KxKxHHHH 为 d×d 的带宽矩阵，对于带宽矩阵 H 的选择，一般有两种，分别是对角形矩阵 H = diag [, …,] 或者成比例的单位矩阵 H = h2I2 1h2 dh在式（1.2）中，核函数 K（x）的作用是控制样本点对概率密度估计的权值，常用的核函数有可微分的 Epanechnikov 核和高斯核两种，（1.4）  212 1, 120 , other 1, 01 0, 1EEdxxKxvxxkxx （1.5）   2212exp21exp2dGGKxxkxx－若令带宽矩阵 H = h2I，式（1.2）转化为，（1.6） 11ˆn i hd ixxfxKnhh如核函数使用式（1.5）的高斯核，则式（1.6）进一步转化为：（1.7）  2, 1211ˆexp22n i h Kd dixxfxhnh引入轮廓函数的概念，式（1.7）变形为，（1.8） 2,211ˆ 2n i h Kddixxfxkhnh2 密度梯度估计类似于 Parzen 的思想，Fukunaga 和 Hostetler [ ]利用密度估计的梯度作为对密度梯度的估计。

有， （2.1）  ,,222122 122211ˆˆ2222h Kh Kn i iddin i inii dndiiifxfxxxxx khnhxxx khxxkxhxxnhkh   令（2.2）  g xkx  将式（2.2）带入式（2.1） ，有（2.3）   22 1,22211,,22ˆ 22ˆn i inii h Gddniiih Gh Gxxx ghxxfxgxhxxnhghfx MSxh  式中：f(x)为目标概率密度，k(x)为核函数，h 为核宽x 为目标的中心像素坐标，xi为 x 的邻域像素坐标由式（2.3）可以看出，左边圆括号中的内容与目标的概率密度成比例，而右方括号部分即为均值平移向量，分别表达为式（2.4）和式（2.5）（2.4） 2,211ˆ 2n i h Gddixxfxghnh（2.5） 21,21n i i ih Gn iixxx ghMSxx xxgh再将式（2.3）变形为，（2.6）    2 , ,,ˆˆ2h K h Gh GhfxMSxfx对于给定点 x，其密度估计为一常数，所以式（2.6）可以理解为均值平移向 ,ˆ h Gfx量 总是指向样本密度梯度估计最大化的方向。

 ,h GMSx ,ˆ h Kfx二、基于均值平移理论的图像分割研究 图像处理包括低层次的图像复原，图像增强等，较高层次的图像处理是指图像分析， 图像理解，其输出的是对图像的描述，理解和分类在处理工程中，感兴趣的是如何对目 标进行描述，着眼点是图像中的某个目标区域，而不是针对单个的像素点图像分割就是 实现图像从低层次到高层次的一个重要过程 图像分割技术的研究多年来一直受到人们的高度重视，每年有相当多的研究成果，然 而到目前为止并没有统一的分类方法，通常根据各自的处理策略，实现方法，应用目的等 进行不同的分类 根据分割过程处理策略的不同，把图像分割分为并行算法和串行算法根据实现技术 的不同，把图像分割分为基于图像直方图的分割方法（阈值分割，聚类等） ，基于领域的分 割方法（边缘检测，区域生长） ，基于物理性质的分割技术（利用光照特性和物体对称性等） ， 根据使用知识的特点和层次分为直接针对灰度值操作（边缘检测，区域等，直接对当前图 像数据进行操作，可以使用先验知识） ，与基于模型操作（基于 Snake 模型，基于组合优化 模型，基于目标集合模型与统计模型等，建立在先验知识的基础上）的分割技术。

此外， 根据应用目的的不同，图像分割可以分为粗分割和细分割两大类，根据分割对象属性的不 同，可以分为灰度图像和彩色图像分割根据是否借助一定区域内像素灰度变换模式，可以分为纹理图像分割和非纹理图像分割，根据分割对象的状态不同，图像分割可以分为静 态图像分割和动态图像分割 图像在分割后的处理，如特征提取，目标识别等都依赖于图像分割的质量基本的方 法有阈值法，边缘检测和区域提取，越来越多的学者将数学形态学、模糊理论，遗传算法， 小波变换，机器学习等理论运用到图像分割中，产生了结合特定数学方法和针对特殊图像 的先进分割技术分割出的图像应满足均匀性和连通性的条件其中均匀性是指该区域中 的所有像素点应满足基于灰度，纹理，颜色或其他某种特征的相似性准则，即边界所分开 区域中的内部特征或属性是一致的，而不同区域内部的特征或属性是不同的连通性是指 区域内的任意两点存在相互连通的路径 2.1 均值平移算法在图像中应用基础：给定 n 个点则在点 x 处，用定义的核函数和的正对称,,, 1,niRxdiL)(xKdd 窗宽矩阵 H 得到多变量密度估计算子表达式为：（2.7） 11ˆni if xKxxnH式中： （2.8） 11 22KxKxHHH为 d 维有界核函数，且在模式空间的紧致集上满足：  K x为    1,0,, lim0,ddddT KKRRRxK x dxxK x dxxx K x dxc IxK xc 常数。

实际应用中，窗宽矩阵 H 和核函数的选择对聚类结果有直接的影响，选择单位矩阵的倍数阵 H = h2I 和可微分的核函数 Epanechnikov 核，通过线性密度的梯度估计得到密度的梯度为：  ,,2 ( )2 ( )ˆˆ12[]()21[])()ikikh Kh Kid xSxdx id xSxdxfxfxdxxn h chndxxn h chn  （2.9）其中 表示 d 维特征空间中半径为 h，中心在,包含个数据点，体积为的超球( )hSxxxnd dhc体其中就是在超球体中计算得到的核密度估计，后面部分定( ())xd dn n h c( )hSx( )1[]iki xSxxxxn义为均值平移向量 ( )hMx代入上式，得到：2( )( )2( )hhf xMxdf x    2 , ,,ˆˆ2h K h Gh GhfxMSxfx（2.10）可知，在点 x 处的密度梯度方向与均值偏移矢量的方向一致，从而可以通过求 MS 矢量的方向来得到梯度的方向，进而得到密度最大的点，即聚类算法的模式点2.2 均值平移滤波 对应于图像滤波，经过色彩空间的转化可以在空间-色彩联合域的 5 维特征空间（2 维 空间和 3 维色度）中获得若干点，每个点对应图像中的每个像素，表达该像素的空间位置 和色彩信息。

在空间位置和色彩信息均相近的像素点，在该 5 维特征空间中也相似，因此， 只需在 5 维空间进行聚类，得到聚类结果后再反向映射到图像中，就可以达到图像平滑的 目的具体算法如下：设和 ，是 5 维特征空间中均值平移处理前后的像素点，对图像中每个ixizni,, 1L像素点：1、初始化 j=1 和；ijxy 2、在以为中心的超球体中计算实现窗口中心的偏移，jy1,1)(1 jjxnyjySxi jj直到满足设定的收敛条件，记收敛为：ciyy,3、给赋值，将收敛的色彩值赋给当前像素：,其中，上角标 s 和 r 分iz),(,r cis jiyxz 别表示向量的空间和排列部分均值平移分割 均值平移分割就是先对一幅图像进行均值平移滤波，然后把空间上相邻，色度域上差别小的区域合并起来用和，表示 5 维特征空间中均值平移滤波处理前后ixizni,, 1L的像素点，表示分割后图像中第 个像素的标签具体过程如下：iLi1、对图像运行均值平移滤波并保存关于的 d 维收敛点，即的所有信息；izciiyz,2、把所有空域距离小于，色度域距离小于的组合起来生成聚类shrhizmjjCL1}{3、对每一个，分配。

miL1}{jiiCzjL4、选择:消除那些包含少于 M（设定的一个阈值）个像素点的空间区域困难点： 1. 不同的颜色空间，核函数，窗的大小，阈值产生的分割效果是不一样的，需要寻找一种 自适应的参数调整方法来满足不同光照度和光强环境下的道路分割效果； 2. 融合其他方法来提高该方法的自适应能力部分参考文献：[1] Tuceryan M. Analysis T. The Handbook of Pattern Recognition and Computer Vision. 2nd ed., World Scientific Publishing Co.,1998. 207−248.[2] Randen T, John HH. Filtering for texture classification: A comparative study. IEEE Trans. on Pattern Analysis and Machine Intelligence, 1999,21(4):291−311. [3] Ilonen J, Kamarainen JK, Paalanen P, Hamouz M, Kittler J, Kalviainen H. Im。