图小波变换在图像分割中的应用研究

王 林，樊淋杰

(西安理工大学 自动化与信息工程学院，陕西 西安 710048)

图小波变换在图像分割中的应用研究

王 林，樊淋杰

(西安理工大学 自动化与信息工程学院，陕西 西安 710048)

在图像处理领域中，图像分割占有举足轻重的地位。传统的基于小波变换的图像分割算法，仅在规则域内能够有效地检测出图像的边缘信息。为了在不规则域内能够有效地检测出图像的边缘信息，提出一种基于图小波变换的图像分割算法。首先，将图像转换成图，在图域进行研究；然后，利用图小波变换进行图像分割。实验结果表明，与传统边缘算法相比，该算法用于图像分割，不仅能够有效地检测出图像边缘信息，而且对噪声具有较好的鲁棒性。

图论；图小波变换；图像分割

0 引言

图像分割是模式识别、计算机视觉、图像处理领域中的基础和关键。图像分割的质量直接影响到图像分析的效果[1-2]。所谓图像分割是根据灰度、颜色、纹理和形状等特征把图像分成若干个特定的、互不交迭的、具有独特性质的区域。各区域的并集是整个图像，各区域的交集为空，并且这些特征在同一区域内呈现相似性，而在不同区域间呈现明显的差异性[3]。常用的图像分割方法包括：阈值分割法、边缘检测法、区域分割法、图论分割法等[4]。

图像分割技术近几十年来飞速发展，引起人们广泛关注。许多研究工作由原来的规则域拓展到不规则域[5-6]。尤其是图论分割法成为国内外研究人员的重点研究对象之一。基于图论的图像分割是一种自上而下的全局分割方法，其主要思想是将一幅原始图像映射成一个加权、无向图，该图像中的像素对应于图中的节点，像素之间的关系对应于节点间的边，像素间的相关程度(差异性或相似性)对应于边的权重[7]。然后在所建立的图上利用分割准则对图中的节点进行划分，进而完成对图像的分割。

ZAHN C[8]提出一种基于图的最小生成树的图像分割方法，主要是通过将图中权值最小的边分割开来构造子图从而得到分割结果，此方法主要考虑图的局部特征，导致分割效果不理想。之后MALIK J等人[9]提出了一种归一化分割算法，其考虑到了图像所分区域内部的自相似性，具有捕捉图像非局部特性的能力，分割效果得到很大提高，但是计算复杂度较高。FELZENSZWALB P F等人[10]提出了一种快速算法，通过评估图的边缘值来寻找一个分段之间边界的依据，提高了分割速度，但稳定性不够。BOYKOV Y Y等人[11]对于N维图像提出了半自动分割方法，主要考虑节点之间的边以及目标与背景之间的明显部分，然后利用图割来获取特定目标的边界，此方法扩展了处理图像的维数，但分割速度较低。GRADY L等人[12]提出基于等周算法的全自动图像分割方法，主要通过寻找最小等周率来进行图像分割，此方法分割速度和稳定度均有了一定的提高。

近几年，研究人员对图论分割算法进行了改进。强轲楠[13]提出一种基于图论使用蚁群算法分割图像的算法，本算法分割图像的分割效果较为精确，计算复杂度较低。杨丹丹等人[14]提出一种基于图论和多尺度分析的图像分割算法，本算法分割效果较好，但存在一定的时间复杂度和一定的过分割现象。吴秋红等人[15]提出一种基于图论和FCM(模糊C均值聚类，Fuzzy C Means)的图像分割算法，该算法不仅保证了图像分割质量，而且提高了图像分割速度。田利平等人[16]提出了一种基于图论最小生成树和阈值的图像分割算法，不但改善了分割效果，而且提高了分割效率。

由于图小波变换提供了类似于传统小波变换的多尺度分析，而且在不规则域内能够有效地检测出图像的边缘信息，因此提出一种基于图小波变换的图像分割算法。在本文中，将介绍如何利用图小波变换对定义在图上的函数进行不规则性检测；对于图像分割问题，会对图小波变换进行调整来开发一种替代工具。首先，将一幅图像映射成图。其次，利用图小波变换[17]来获取图上节点间的小波系数。然后，对这些小波系数进行阈值处理，从而识别出图像中相应的边缘像素。最后，通过采样图像来评估本文提出算法对噪声的鲁棒性，并将其与现有的算法进行比较来评估本文提出算法的性能。

1 基础理论(图小波变换)

CROVELLA M等人[17]早期定义了图小波变换(Graph Wavelet Transform, GWT)，用于总结网络交通信息，其利用跳邻居节点的信息对传统小波变换中的平移和缩放操作进行调整。

(1)

为了满足基本条件：

(2)

则归一化常数Cj,k需要满足如下条件：

(3)

因此，小波信号Ψj,k可写成：

(4)

(5)

设g:V→R为图上节点的任意函数，Ψj,k为小波信号，则图小波变换可定义如下：

(6)

ψj,h=(j+1)∫Ij,hψ(x)dx

(7)

2 研究方法

2.1 将图像映射成图

图像中相邻像素的强度值沿着连续段移动平缓变化，像素强度值的突变部分可以看作两个不同像素集群之间的边缘。一个二维、无向、稀疏图G=(V,E)可以由灰度图像IM×N映射形成，如下：

(1)图像中像素点形成图的节点：I(m,n)→Vi，其中m∈{1,2,…,M}，n∈{1,2,…,N}，i=M(n-1)+m。

(2)图像中相邻像素点之间的关系形成图中节点之间的边：

Ei,j=h(I(mi,ni),I(mj,nj))

(8)

h(I(mi,ni),I(mj,nj))=

(9)

其中τ∈{1，2，…,N}，i≠j。τ值决定了相邻像素的范围。例如，τ=1，那么相邻像素由8个最近邻像素组成。

(3)图像像素的强度值形成定义在图上的节点函数：

f(Vi)=I(m,n)

(10)

其中，I(m,n)为图像像素的强度值。

2.2 计算小波系数

利用GWT结合哈尔小波(j=1)的方法对图计算小波系数Wi。由于哈尔函数是最简单的小波函数，并且可以有效地检测出信号的突变部分，因此选择哈尔小波对图像进行研究分析。此外，由于更高的尺度小波分解需要考虑更多的相邻像素，然而感兴趣的只是第一尺度的分析，因此选择j=1。

2.3 阈值处理

根据得到阈值的方法的不同，可将阈值分为以下几种类型，如图1所示。

图1 阈值处理分类

对计算得到的小波系数进行局部阈值处理，从而确定图像边缘的像素：

(11)

其中Wi为对应于节点vi的小波系数，t为设定的阈值。

3 实验及结果分析

实验对象：下载的猫图像；实验环境：MATLAB(R2009b)。

首先，将下载的猫图像转换为灰度图像；然后，利用如前面所述方法形成图以及相应的函数。分别利用GWT、Canny和Sobel三种算法对猫图像进行图像分割处理，得出结果如图2所示。由图2可以看出，利用GWT算法能够有效地检测出图像的边缘，然而利用其他两种算法可能会导致图像边缘的部分像素丢失。

图2 猫原图像以及利用GWT、Canny、Sobel方法对猫原图像分割的结果

图3 对猫原图像进行一阶哈尔小波分解且阈值化后的结果

对于常规的二维离散小波变换(2D-DWT)来说，其细节系数对应于图像的高频细节部分，近似系数对应于图像的低频近似部分。为了说明GWT和2D-DWT之间的区别，利用2D-DWT对实验对象进行处理。首先，通过丢弃一阶哈尔小波分解的低频近似系数来重构图像。然后，对得到的图像进行硬阈值化处理，得出结果如图3所示。由图3可以看出，利用2D-DWT对图像进行分割，会导致图像边缘的部分像素丢失。

通过设置τ= 1 、τ= 2，噪声级别分别为10 dB、20 dB、30 dB，针对不同图结构对边缘检测性能的影响分别进行了评估，得出结果如图4所示。通过观察实验结果得出：选择τ= 2，对噪声提供了更好的鲁棒性，即增加τ值会导致产生更多的相邻像素，同时表现出小波系数的平滑效应。

图4 令τ= 1 、τ= 2，噪声级别为10 dB、20 dB、30 dB，对猫原图像进行边缘提取后的结果

4 结论

本文提出一种利用图小波变换进行图像分割的方法。实验结果表明，图小波变换结合第一尺度哈尔小波，这一方法对定义在任意图上函数的变化点(对应于图像的边缘)进行检测非常有效。图的结构直接影响到方法的鲁棒性。未来工作是，在不同尺度下利用不同的母小波函数进行研究，也会考虑利用不同的方法由图像构造图。

[1] 杜雯超, 陈其松, 周莹. 基于分段自适应遗传算法的图像阈值分割[J]. 微型机与应用, 2015, 34(3): 58-62.

[2] 隋然, 潘点飞. 基于分段自适应遗传算法的图像阈值分割[J]. 微型机与应用, 2015, 34(14): 45-47.

[3] 李余钱, 苏光大. 基于邻域处理器自适应图像分割高速实现[J]. 电子技术应用, 2016, 42(2): 99-101.

[4] 柳欢欢, 姚明海, 王宪保. 基于小波变换的GrabCut图像分割[J]. 计算机系统应用, 2014, 23(8): 154-157.

[5] SHUMAN D I, NARANG S K, FROSSARD P, et al. The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains[J]. IEEE Transactions on Signal Processing Magazine, 2013, 30(3): 83-98.

[6] HAMMOND D K, VANDERGHEYNST P, GRIBONVAL R. Wavelets on graphs via spectral graph theory[J]. Applied and Computational Harmonic Analysis, 2011, 30(2): 129-150.

[7] DAVID I SHUMAN, BENJAMIN RICAUD, PIERRE VANDERGHEYNST. Vertex-frequency analysis on graphs[J]. Applied & Computational Harmonic Analysys, 2016,40(2):260-291.

[8] ZAHN C. Graph theoretical methods for detecting and describing gestalt clusters[J]. IEEE Transactions on Computation, 1971, 20(1): 68-86.

[9] Shi Jianbo, MALIK J. Normalized cuts and image segmentation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2000, 22(8): 888-905.

[10] FELZENSZWALB P F, HUTTENLOCHER D P. Efficient graph-based image segmentation[J]. International Journal of Computer Vision, 2004, 59(2): 167-181.

[11] BOYKOV Y Y, JOLLY M P. Interactive graph cuts for optimal boundary & region segmentation of objects in Nd images[C]. Eighth IEEE International Conference on Computer Vision, 2001: 105-112.

[12] GRADY L, SCHWARTZ E L. Isoperimetric graph partitioning for image segmentation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2006, 28(3): 469-475.

[13] 强轲楠. 基于图论的蚁群算法在图像分割中的应用[J]. 计算机光盘软件与应用, 2012,48(14):105-106.

[14] 杨丹丹, 王卫星, 廖一鹏. 基于多尺度分析及图论归一化割的矿岩颗粒图像分割及应用[J]. 四川大学学报, 2015, 47(1): 118-124.

[15] 吴秋红, 吴谨, 朱磊，等. 基于图论和FCM的图像分割算法[J]. 液晶与显示, 2016, 31(1): 112-116.

[16] 田利平, 谢忠和. 基于阈值和图论的图像分割算法研究[J]. 宁德师范学院学报, 2016, 28(1):62-65.

[17] CROVELLA M, KOLACZYK E. Graph wavelets for spatial traffic analysis[C]. Twenty-Second Annual Joint Conference of the IEEE Computer and Communications, 2003: 1848-1857.

Application of graph wavelet transform in image segmentation

Wang Lin, Fan Linjie

(School of Automation and Information Engineering, Xi’an University of Technology, Xi’an 710048, China)

In the field of image processing, image segmentation occupies a pivotal position. The traditional image segmentation algorithm based on wavelet transform can only effectively detect the image edge information on regular domains. In order to be able to effectively detect the image edge information on irregular domains, the paper proposes the image segmentation algorithm based on Graph Wavelet Transform. The images are firstly transformed to the graph domain and the graph wavelet transform is used for image segmentation. Experimental results prove that proposed algorithm can not only effectively detect the image edge information, but also has better noise robustness compared with the traditional edge algorithms for image segmentation.

graph theory; graph wavelet transform; image segmentation

TP391

A

10.19358/j.issn.1674- 7720.2017.08.013

王林，樊淋杰.图小波变换在图像分割中的应用研究[J].微型机与应用，2017,36(8)：39-41，44.

2016-11-26)

王林(1963-)，男，博士，教授，主要研究方向：复杂网络、大数据理论与应用、无线传感器及计算机应用。

樊淋杰(1988-)，通信作者，男，硕士研究生，主要研究方向：通信网络理论与物联网技术。E-mail: 846495390@qq.com。

________________________