基于邻域MeanShift的彩色图像滤波算法

摘 要：

在空间域与色彩域中分别给定移动窗口半径的适当值，把空间位置处于当前数据点的圆邻域内的色彩数据作为算法的样本数据，利用窗口半径固定且独立于空间位置的核函数对色彩数据进行均值偏移(MeanShift)聚类，用聚类中心更新当前位置的图像数据，克服了空间域与色彩域结合的MeanShift图像滤波模型窗口半径难于恰当选取以适应图像尺寸变化的困难。实验证明了该算法的有效性。

ス丶词：

彩色图像滤波；MeanShift算法；空间域；色彩域；窗口半径

ブ型挤掷嗪牛 TP301.6；TP391.41

文献标志码：A

英文标题

Color image filtering algorithm based on neighborhood MeanShift

び⑽淖髡呙

HE Xiping

び⑽牡刂(

College of Computer Science and Information Engineering, Chongqing Technology and Business University, Chongqing 400067, China

英文摘要

)

Abstract:

Given proper values of shift windows in spatial domain and color domain respectively, the color data were filtered by means of MeanShift clustering, during which the color data in the rcircular neighboring domain of current data point were used as the clustering samples. Then image data at current position were updated with the cluster center newly obtained. This algorithm overcomes the difficulty to choose proper window radius for the model of MeanShift filtering combining spatial domain and color domain to adopt the possible variation of image size. Finally, the experimental results verify the validity of MeanShift filtering.

英文关键词

Key words:

color image filtering; MeanShift algorithm; spatial domain; color domain; window radius

0 引言

特征数据滤波一直是计算机视觉领域的重要研究课题之一，而统计建模方法是其最常见的实用技术。其中，无参数概率密度估计相对于用含参数函数对特征数据建模具有明显的优越性：不必事先知道特征空间数据服从的概率分布函数的形式，能较好地适应实际的计算机视觉问题所涉及的密度分布函数多变量、多峰的特点；以特征数据统计分布为匹配依据，估计结果收敛于数据，不会出现大偏差。常见的无参数估计技术有直方图法、最近邻域法和核密度估计法。核密度估计和直方图技术类似，相对于直方图法，多了一个用于平滑数据的核函数。

MeanShift算法是一种计算机视觉领域优秀的密度梯度的无参数估计方法，由Fukunaga和Hostetler于1975年提出［1］，但直到1995年Cheng将它引入计算机视觉领域才引起国内外学者们的广泛兴趣。在文献［2］中，Cheng对基本的MeanShift算法做了推广：首先，Cheng定义了一族核函数，使得随着样本与被偏移点的距离不同，偏移量对均值偏移向量的贡献也不同；其次，Cheng还设定了一个权重系数，使得不同的样本点重要性不一样，扩大了MeanShift的适用范围。

Comaniciu和Meer等人［3-5］对MeanShift算法在图像滤波、分割和跟踪中的应用都做了较早的研究。近年来，MeanShift算法作为一种快速收敛的统计迭代算法，已广泛应用于计算机视觉领域，如模式识别与聚类分析［2］、特征空间分析［5］、图像分割［8-10］、滤波［11］、信息融合［12］等。对MeanShift的应用研究，在目标跟踪领域国内外研究者［3-7］最多，而跟踪目标大小随时间发生变化时核函数窗口半径的自适应技术是目前的研究热点［7,13-14］。

对MeanShift图像滤波的研究不多，仅文献［11］在空间位置与色彩数据组合形成的高维图像数据空间利用均匀核函数对图像滤波做了研究；但对于高维特征空间，该方法计算量相当大，且因图像尺寸的差异，要合理平衡空间位置与色彩值对均值偏移向量的计算结果的影响权重，也不宜用统一的核函数窗口半径及收敛容差进行迭代计算，对空间位置与色彩值使用统一的密度估计核函数也是不太恰当的。文献［15］对空间位置与色彩分别选择核函数，但大大增加了计算时间复杂性。

本文给出一种基于邻域meanshift聚类的彩色图像滤波算法，在空间域与色彩域中分别给定移动窗口半径的适当值，把空间位置处于当前数据点的圆邻域内的色彩数据作为算法的样本数据，利用窗口半径固定且独立于空间位置的核函数对色彩数据进行MeanShift聚类，用聚类中心更新当前位置的图像数据，克服了空间域与色彩域结合的MeanShift图像滤波模型中窗口半径难于恰当选取以适应图像尺寸变化的困难，算法对目标旋转和缩放都有了一定的适应能力；同时也由于只用了一个核函数，致使迭代计算的时间复杂性大大降低。

1 滤波与特征数据处理

在MeanShift滤波迭代计算中，邻域空间信息与邻域像素色彩分布信息是判识像素是否噪声的重要依据，也是决定MeanShift向量收敛方向的重要信息。针对彩色图像滤波问题，特征数据不仅要包含目标像素的色彩数据，而且必须包含与目标像素的色彩数据耦合的空间信息数据。

1.1 图像数据空间

彩色图像数据空间可表示为I= {xi = (si, ci) | si ∈S N 2,ci∈C 3, C={0, 1, 2,…,255}, i=1,2, 3, … ,n}。其中，si表示第i像素的空间坐标，ci表示第i像素的色彩数据，C 3表示算法选择的色彩空间(如RGB, YCbCr, HSV, L*a*b*等）。特别地，对于灰度图像，C 3=L，图像函数g(s)可表示为：

Иs∈S

g(s)=c∈C3(1)

其中S与C 3分别表示图像数据空间域与色彩域。

1.2 滤波与数据邻域

由于图像g(s)在有限邻域内的连续性，滤波算法只需在数据空间中目标数据的一个有限邻域内对色彩数据进行统计分析。因此首先应综合权衡统计分布的客观性要求和计算复杂性适当降低要求，选择大小适当的空间邻域半径r，rЭ梢圆皇苤朴谕枷翊笮。而是一个相对客观的常量；其次，要在目标邻域Is,r内根据色彩密度分布对目标按式(3)进行估计。

Is,r={(s, c) | (s, c)∈I, s∈U(s,r)S}(2)

(,)=f(Is,r)(3)

其中:U(s,r)表示以空间位置s为中心r为半径的圆邻域，f为特定滤波算法。И

设Cs,r={c |(s, c)∈Is,r}，本文滤波算法是按式(4)基于MeanShift的邻域色彩的聚类算法估算的。

(s,)=ms(Is,r)=Cluster(Cs,r)(4)

┑2期

何希平：基于邻域MeanShift的彩色图像滤波算法

┆扑慊应用 ┑31卷

2 MeanShift滤波算法

2.1 MeanShift算法原理

给定d维空间Rd上n个数据点的集合X={xi}i=1, 2,…,n，其未知概率密度函数为p(x)，K(x)为多元核密度估计函数简称核函数，窗口半径(也称为带宽)为h，则在xУ愕母怕拭芏裙兰疲ㄓ置Pazen窗估计）可表示为：

ИP^(x)=1nhd∑ni=1Kx-xih(5)

核函数K(x)是对称、单峰和有限局部支撑的。所谓单峰的是指从中心向边缘其值迅速衰减为0；而有限局部支撑指超过一定窗口的点其值为0。核函数都遵循以下的基本性质。

1)非负性：Иx∈Rd，K(x)≥0。И

2)规范性：А要RdK(x)dx=1А＊

3)对称性：А要RdxK(x)dx=0А＊

4)指数权衰减性：И┆limx∞xdK(x)=0А＊

利用核函数的可微性，由密度梯度估计恒等于核密度估计的梯度，对式(5)取梯度，令g(x)=-k′(x)(称为k(x)的影子)有：

ЙP^h,g(x)=2ck,dnhd+2∑ni=1(x-xi)k′x-xih2=2ck,dnhd+2∑ni=1gx-xih2∑ni=1xigx-xih2∑ni=1gx-xih2－x(6)

式(6)暗示了MeanShift核密度估计算法，令

ИP^h,g(x)=cg,dnhd∑ni=1gx-xih2(7)

mh,g(x)=∑ni=1xigx-xih2∑ni=1gx-xih2－x=12h2cP^h,k(x)P^h,g(x)(8)お

其中：cg,d为归一化常数，c=ck,d/cg,d。通过反复迭代:

yk+1=yk+mh,g(yk)(9)

mh,g(x)构成快速收敛于0的局部均值偏移向量，而局部均值朝附近数据样本密集的区域移动,如图1所示。

图片

图1 均值偏移算法的直观描述

MeanShift算法用于在特征空间搜索“模式(mode)”或数据分布的最高密度点。MeanShift迭代算法的一般步骤如下：

1)初始化随机种子和搜索窗口；

2)计算窗口质心(均值)；

3)平移搜索窗口到均值；

4)重复第2)、3)步直到局部均值收敛。

2.2 核密度函数窗口尺度选择

核密度函数窗口尺度选择是一个非常重要的问题，选择策略非常值得考究。h过小，导致密度参差不齐；h过大，导致数据的过度平滑。对于归一化数据，h的最佳选择取决于样本容量n。n越小，核函数越宽；n越大，核函数越窄，┆limn∞ h(n)=0。オ

最佳核函数与最佳窗口尺度选择可以通过最小化误差平方的积分的平均值实现――假如知道密度函数，通常可参考如下准则：

hopt=43n15σ≈1.06n－15(10)

2.3 图像滤波

为充分参照目标近邻像素的色彩分布对目标像素估计的影响权重，选用高斯轮廓函数：

k(x)=e－12x；x≥0(11)

则:

g(x)=k′(x)=－12e－12x；x≥0(12)

在目标像素(s,r)的邻域Is,r中对色彩域Cs,r C 3中数据以c为初始中心进行MeanShift聚类。用于彩色图像滤波的算法实现步骤如下。

1)给定邻域半径r与核窗半径h，令i=1。

2)对xi ∈I，令x=xi=(s, c) 根据Is,r确定Cs,r。

3)迭代计算。通过核函数计算窗口所覆盖的色彩域Cs,r的质心（均值）c′。

c′=∑ck∈Cs,rckgc-ckh2∑ck∈Cs,rgc-ckh2(13)

当|c-c′|≥ε 时，令c=c′反复计算式(13)。

4)令xi= (s, c′), i=i+1。

5)当xi ∈I时，重复2）~4），直到遍历图像数据集IА＊

3 实验与结果分析

对算法实验效果的分析，可以通过对比分析图像的直观效果、峰值信噪比(Peak SignaltoNoise Ratio, PSNR)、相似系数等实现。借助于向量夹角的余弦，用式(14)计算两幅图像的相似度RА＊

R=cos θ=I・I^I・I^(14)

对多幅不同尺寸的彩色图像做了多次滤波实验，并从直观效果和定量分析两个方面验证了本文算法的有效性。

3.1 实验结果

实验时，首先对原图像添加了高斯白噪声（均值0，标准差10），然后取MeanShift滤波的邻域半径r为5，颜色核函数窗口半径25，实验统计结果见表1。

表格(有表名)

表1中，PSNR1与PSNR2分别表示噪声图像与结果图像的峰值信噪比，R0表示原图与滤波结果图像的相似性系数，R1表示噪声图像与滤波结果图像的相似性系数。И

为准确分析噪声图与滤波结果图的差别，求了两图的差，并在直角坐标系下做出了直观图，如图3所示。

同时，为将本文算法与其他滤波算法对比，本文选择了与高斯低通滤波算法进行对比实验（高斯滤波器标准差也取10），结果如图4及表2所示。

П2中，R0表示原图与滤波结果图像的相似性系数，R1表示噪声图像与滤波结果图像的相似性系数。И

图片

图4 Lena图滤波结果对比

表格(有表名)

表2 Lena图实验结果对比统计数据表

滤波算法邻域半径PSNRR0R1

MeanShift513.809B40.998B90.997B1

高斯低通513.067B70.994B90.992B4

3.2 结果分析

由直观效果图及PSNR、相似系数的对比可见，MeanShift滤波算法不仅能有效抑制噪声，提高图像质量，而且还能保持滤波结果图与原图的高度相似性，与其他滤波算法相比，能更好地保持图像细节（如不连续性）不被模糊。

此外，本文对算法随核函数窗口半径的变化的效果也做了对比实验。Ы峁发现，核函数窗口半径h取值越大，滤波结果图越模糊，但变化不显著；h取值越小，滤波结果图相对于噪声图的变化越不明显。邻域半径r越大，算法耗时变化不明显，但会引起结果稍微变模糊。И

由于MeanShift滤波是基于密度梯度最大变化方向分析的统计方法，虽然从效果角度看，具有明显的优势，但是其时间效率仍然不如传统的邻域均值滤波器，这在一定程度上限制了它的实时应用推广。

4 结语

本文算法综合了邻域均值平滑与局部最优解的特性，用局部收敛的最大密度数据作为滤波结果,既平滑了尖峰噪声，又降低了MeanShift滤波算法的时间复杂性，克服了均值滤波器与高斯滤波器使图像变模糊并不保持区域边缘特征的不连续性的缺陷，在高精确度的图像处理中具有明显的应用推广意义。

げ慰嘉南:

［1］

FUKANAGA K, HOSTETLER L. The estimation of the gradient of a density function, with applications in pattern recognition［J］. IEEE Transactions on Information Theory, 1975, 21(1): 32-40.

［2］

CHENG YIZONG. MeanShift, mode seeking and clustering［J］. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1995, 17 (8): 790-799.

［3］

COMANICIU D, RAMESH V, MEER P. Realtime tracking of nonrigid objects using MeanShift［C］// Proceedings of IEEE Conference on Computer Vision and Pattern Recognition. Washington, DC: IEEE Computer Society, 2000: 142-149.

［4］

COMANICIU D, RAMESH V. MeanShift and optimal prediction for efficient object tracking［C］// Proceedings of the IEEE International Conference on Image Processing. Washington, DC: IEEE Computer Society, 2000:70-73.

［5］

COMANICIU D, MEER P. MeanShift: A robust approach towards feature space analysis［J］. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2002, 24(5): 603- 619.

［6］

COLLINS R T. MeanShift blob tracking through scale space［C］// Proceedings of the Conference on Computer Vision and Pattern Recognition. Washington, DC: IEEE Computer Society, 2003: 18-20.

［7］

彭宁嵩，杨杰，刘志,等. MeanShift跟踪算法中核函数窗宽的自动选取［J］.软件学报, 2005, 16(9): 1542-1550.

［8］

陈允杰，张建伟，王利,等.基于改进的MeanShift算法虚拟人脑图像分割［J］.计算机辅助设计与图形学学报, 2008, 20(1): 55-60.

［9］

汤杨，潘志庚，汤敏,等.基于分级MeanShift的图像分割算法［J］.计算机研究与发展, 2009, 46(9): 1424-1431.

［10］

廖建勇,郭斯羽,黄梓效.基于MeanShift聚类的最大熵图像分割方法［J］.计算机仿真, 2009, 26(9): 187-189.

［11］

COMANICIU D, MEER P. MeanShift analysis and applications［C］// Proceedings of the IEEE International Conference on Computer Vision. Washington, DC: IEEE Computer Society, 1999: 1197-1203.

［12］

COMANICIU D. Nonparametric information fusion for motion estimation［C］// Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. Washington, DC: IEEE Computer Society, 2003: 59-66.

［13］

覃剑,曾孝平,李勇明.基于边界力的MeanShift核窗宽自适应算法［J］.软件学报, 2009, 20(7): 1726-1734.

［14］

耿振伟,粟毅,郁文贤.一种快速自适应的均值漂移聚类算法［J］.信号处理, 2009, 25(1): 153-156.

［15］

SUBBARAO R, MEER P. Nonlinear MeanShift over riemannian manifolds［J］. International Journal of Computer Vision, 2009, 84(1): 1-20.