logo资料库

基于聚类算法的图像分割技术综述.pdf

第1页 / 共12页
第2页 / 共12页
第3页 / 共12页
第4页 / 共12页
第5页 / 共12页
第6页 / 共12页
第7页 / 共12页
第8页 / 共12页
资料共12页,剩余部分请下载后查看
基于聚类算法的图像分割技术综述 马义德 钱志柏 陈 娜 (兰州大学信息工程学院 兰州 730000) 【摘要】 图像分割是指将一幅图像分解成若干互不相交区域的集合,其实质是一个像素的聚类过程。 本文以图像分割的聚类实质为线索,对近几年国内外最新的图像分割算法进行了综述,指出了聚类在这个 领域的重要性。 关 键 词 图像分割; 聚类; 特征 Survey on Clustering-Based Image Segmentation Technique Ma Yide Qian Zhibai Chen na (The School of Information Science & Engineering of Lanzhou University, Lanzhou 730000) Abstract Image segmentation denotes a process by which a raw image is partitioned into non-overlapping regions. And it is essentially a process of pixel clustering. Based on the clustering fact of image segmentation, this paper makes a survey on recent global algorithms about image segmentation. We show the importance of clustering in this field. Key words image segmentation; clustering; feature 1 引言 根据抽象程度和处理方法的不同,图像技术可以分为三个层次:图像处理、图像分析和 图像理解,这三个层次的有机结合也可以称为图像工程。图像处理是较低层的操作,主要在 图像像素级上进行操作。有代表性的图像处理技术包括图像降噪、图像编码和图像分割。 图像分割是一种关键的图像处理技术。作为后续图像分析和图像理解的基础,图像分割 技术一直是图像理论发展的瓶颈之一。另一方面,图像分割在实际中的应用非常广泛,对图 像目标的提取、测量都离不开图像分割,分割的准确性直接影响后续任务的有效性,因此具 有十分重要的意义。 图像分割又是一种特殊的图像处理技术。像素级的图像处理可以分成两类,一类是针对 像素值的处理,另一类是把像素分类的处理。图像降噪技术、图像编码技术、数字水印技术 等虽然各有其特点和应用领域,但其实质都是针对像素值的操作。不同于这些技术,图像分 割,其实质是一个按照像素属性(灰度、纹理、颜色等)进行聚类的过程。 基于此,许多聚类算法被应用于图像分割领域并取得了较为满意的效果。但由于图像数 据的特殊性,并不是所有的聚类算法都能直接应用于图像分割,有的算法需要改进,有的算 法根本不适合这个领域的分类;而且,有的分割算法中分类思想体现的比较明显,一些则不 明显。也就是说,聚类算法应用于图像分割领域是有其特点的。 图像分割的研究多年来一直受到人们的高度重视,借助各种理论,至今已提出了上千 种分割算法,而且这方面的研究仍在积极进行。但同时它也是一个经典难题,到目前为止既 不存在一种通用的图像分割方法,也不存在一种判断是否分割成功的客观标准[付峰,应义 _______________________________________________________________________________www.paper.edu.cn
斌]。因此现在已提出的算法大都是针对具体问题的,并没有一种适合于所有图像的通用分 割算法。同样地,分割的定义也不仅有一种。资料[1]中的定义比较明确地体现了分割技术 的分类的思想: 令集合 R 代表整个图像区域,对 R 的分割可看作将 R 分成 N 各满足以下五个条件的非 空子集(子区域)R1,R2,••• RN: 1) N =U1 i Ri = ; R 2) 对所有的 i 和 j,i≠j,有 Φ≠Rj ; Ri I 3) 对 i=1,2,••• N,有 P(R)=TRUE; 4) 对 i≠j,有 P( Ri U Rj )=FALSE; 5) 对 i=1,2,••• N,Ri 是连通的区域 其中 P(Ri)是对所有集合 Ri 中元素的逻辑谓词, Φ 代表空集。 而且,对分割效果进行评判的标准和对算法分类的标准尚不统一。文献[2]把分割方法 按照数据驱动和模型驱动进行分类,文献[3]把分割算法分成阈值法、区域生长法、松弛法、 边缘检测法,以及分裂合并法,文献[4]和文献[5]都认为有四个主要方法:阈值法、边缘检 测法、区域生长法、边缘区域综合法。本文作者认为,文献[2]中模型驱动方法利用的先验 知识不可能完全独立于数据,阈值法和区域生长法从分割技术的分类实质来看是有共性的。 所以笔者倾向于把图像分割技术分成基于边缘的技术和基于区域的技术,而阈值法属于基于 区域的方法之一。基于边缘的算法通常可以产生光滑的边缘,但是其实现依赖边缘检测子得 到闭合的边缘[6],而这点在实际图像中很难保证;基于区域的技术尽管在边界上可能产生 错误的分割,但由于其较好的鲁棒性和技术上的相对简易,仍具有更为广泛的适用范围,而 且基于区域的分割方法对分类实质的表现也是比较明朗的。由此,本文偏重于介绍基于区域 的分割技术。 文献[7]提出区域生长法和分开-合并法都属于基于区域的方法,文献[8]提出基于区域的 方法主要分为区域生长法和特征向量聚类法。本文试图使基于区域的方法包括尽可能全面的 内容,而且更明朗地体现分类思想,笔者将之分为灰度空间的聚类和像素空间的聚类。灰度 空间的聚类几乎可以等同于所谓的阈值法,而区域生长法、分开-合并法以及特征向量聚类 法等都属于在像素空间聚类的情况。不同于已有的分割综述[2] [9][10][11],本文将分别从灰 度空间聚类和像素空间聚类这两方面进行介绍,而且重点是近几年最新的图像分割算法。 在这之前,我们有必要先简单探讨一下聚类技术。 2 聚类分析 聚类分析是当今飞速发展的数据采掘和探查性数据分析中一个极为重要的技术[12], 它 被广泛地应用于工程、生物、心理、计算机视觉和遥感等领域。笼统的说,聚类算法是将一 组分布未知的数据进行分类, 尽可能地使得同一类中的数据具有相同的性质, 而不同类的数 据其性质各异,其目的是寻找隐藏在数据中的结构。 完整的聚类过程可以由图1表示。由图1可以看出,最终聚类的有效性和适应性不仅仅取 决于聚类算法本身,还取决于用于聚类的特征和其相似性的度量,而且聚类输出的反馈有可 能影响前两步的特征选取和相似度的计算。 中国科技论文在线_______________________________________________________________________________www.paper.edu.cn
特征选择/提取 相似度度量 反馈 图1 几种常用的聚类技术包括[13]:分层聚类算法,混合解析模式查询算法,最近邻域聚类 聚类 算法,模糊聚类算法,人工神经网络聚类算法,遗传聚类算法。 这里仅介绍一种经常被应用于图像分割的典型的聚类算法—模糊C均值(FCM)算法。 FCM 是基于(1)式目标函数的非线性迭代优化方法。它通过目标函数来测定聚类的效果, 将最佳的聚类结果对应于目标函数的极值点。 J (U, V) = ∑∑ u ( ik m ) || vx − k i 2|| (1) n c k 1 = i 1 = u ik = ( ( c ∑ j 1 = || || m k vx − vx − k || || i j m 1 − 2 ) − ) 1 (2) x k (3) v i n ) ik u ∑ ( k 1 == n u ∑ ( m ) ik k 1 = 其中,uik代表xk属于第i类的隶属度,vi表示第i类的聚类中心,(1)式求和的第二项是 本次迭代中数据和聚类中心的距离。迭代终止的条件是||U(t)-U(t-1)||小于预先设定的阈值ε。 聚类算法经常被应用的领域有:模式识别,信息恢复,数据挖掘,图像分割。在聚类分 析中,数据结构与产生它的物理系统紧密联系在一起,而相应的物理系统的工作原理是多式 多样的,这就造成了要被聚类的数据的多样性,对聚类算法的要求相应也就不一样了。比如 说,在不同的应用领域,用于聚类的选取的特征是不同的。图像数据的特点是数据量大,信 息冗余度高,对分类问题有先验知识可供参考,这些特点对用于分割的聚类算法提出了新的 要求。 3 灰度空间的聚类 本文作者在另一篇文章中曾经基于分类思想指出对阈值的理解:如果只把图像分成目标 和背景两类,而且仅考虑像素的灰度,这就是一个在一维空间中把数据分成两类的问题。通 过在灰度空间完成聚类,得到两个聚类中心(这两个聚类中心利用灰度值表征),聚类中心 连线的中点便是阈值。显然这个概念也可以轻松地延扩至多阈值和动态阈值的情况。 阈值分割法的特点是原理清晰、易懂,算法实现简单、运算量小,分割效果较好,对于 对比度分明的图像分割效果几乎与其他大运算量的算法相当。阈值法利用的是每个像素的灰 度信息和整幅图像的灰度分布,通常情况下仅处理直方图就可以得到阈值[14] [15] ~~。图像 间的差距可以有多种衡量标准[16],由此人们可以通过定义不同的差距度量方法来构造不同 中国科技论文在线_______________________________________________________________________________www.paper.edu.cn
的目标函数以测度分割效果,最佳阈值就是对应于求取目标函数的极值。文献[17]指出了图 像的偏态指标和 Fisher 评价函数可以作为图像分割阈值选取的准则函数。 由于灰度图像本身所具有的模糊性,以及基于模糊逻辑的推理方式更接近人类的真实思 维和决策,因此,可以采用图像的某些模糊测度作为分割的依据。其实质就是将图像从空间 域转换到模糊性质域的一个映射。T. Chaira 等人通过假定阈值,构造和原图像相同大小的理 想阈值图像(ideal threshold image),基于直方图利用 Gamma 分布确定原图像每个灰度的隶 属度,然后计算理想阈值图像和原图像之间的模糊散度(fuzzy divergence)[18],最后把最 佳阈值设定为使模糊散度最小的假定阈值。Orlando 利用灰度级的相似度分割直方图[19], 这与常见的的基于判决函数最小化的方案不同。两个模糊子集表征目标或背景,首先在直方 图上建立一个模糊域,然后分派模糊域每一个元素(灰度)至每一个模糊子集,对这两个模 糊子集分别进行模糊指标(index of fuzziness)度量,当两个子集的模糊指标值相等时,即 为最佳分割。 Kuo-Sheng Cheng 把图像分割视作基于全体灰度分布的像素聚类[20],所以,需要最小 化的能量函数便定义为类内灰度级的平均距离。对于一个有 N 个灰度级和 C 个目标的图像, 此方法将涉及 N·C 个神经元,利用 CHNN(竞争 Hopfield 神经网络)来极小化该能量函数 可达到分割图像的目的。此方法不依赖于图像的大小,为了能量函数的迅速收敛引入了胜者 取全(WTA)机制进行训练。陈燕新等人对此方法进行了改进[21],引入了类内的均匀性这 个度量。根据灰度分布动态调整聚类数目,直至到达预定的均匀性度量。其优点在于不必预 知图像所需的分割类数。冯晓毅等人进一步对该方法进行改进[22],提出了利用 CHNN 对二 维灰度向量聚类进行图像分割的方法,兼顾了图像地邻域相关信息及图像的边缘特性。 模糊 Kohonen 聚类网络(FKCN)是一种自组织模糊神经网络,它将 FCM 的概念引入 Kohonen 网络的学习机制中。自适应模糊 Kohonen 聚类网络(AFKCN)是一个单向全连接 的两层网络,其输入层节点数为样本矢量的维数,输出层节点数为所需聚类数。对灰度图像 分割来说,就是要根据其灰度特征自动确定图像的灰度聚类数。王磊等人通过引入直方图 [23],完成学习空间从像素空间到灰度空间的转换,并且提出一种从图像的灰度直方图提取 图像的灰度聚类数和初始聚类中心的方法。 结合模糊集理论和人工神经网络的图像分割,是当前图像分割研究的新方向。自适应共 振理论(ART)神经网络通过警戒值的调整,可以按任意精度对输入矢量进行分类。模糊自 适应共振理论(FART)神经网络是一种自组织模糊神经网络,文献[24]以图像灰度的模糊 特征作为 FART 的输入,通过对图像灰度的分类来实现对图像的分割。从聚类的目标来说, 这个方法不同于一般的通过求取目标函数极值来确定分割阈值的方法,但由于其利用的模糊 信息仍旧是来自于灰度的分布,也就是直方图,所以我们还是把这种方法归属于在灰度空间 聚类的技术。 Otsu 提出的最大类别方差算法又称为大津阈值分割[25],是在判决分析最小二乘法原理 的基础上导出的,使类内方差最小而使类见方差最大,算法比较简单,是一种普遍关注的阈 值选取方法。Kurita 等人用最大相关准则解释了 Otsu 方法[26],指出假设直方图服从正态分 布且二个子分布的方差相等,则基于条件分布的最大相关原则的阈值分割方法与 Otsu 的分 割方法等价。对 Otsu 方法感兴趣的学者对此方法进一步提出了一些改进方法[26][27][28]。 其中文献[28]的二维 Otsu 阈值分割算法充分利用了图像像素与其邻域的空间相关信息而具 有比仅利用灰度值方图的一维阈值分割算法更强的抗噪声能力。而且通过改变传统算法中二 维灰度值方图上区域的划分来达到减少运算量和该进分割效果的目的。改进算法充分考虑了 对角线附近阈值矢量点的区域内的概率分布,同时考虑了传统二维阈值分割算法中包含的像 素灰度和灰度邻域平均值相差较大的点。 为了控制图像分割造成的信息丢失,人们在图像分割理论和实践领域引入了信息论中的 中国科技论文在线_______________________________________________________________________________www.paper.edu.cn
最大熵准则 [29] [30] [31] [32] 。其中 H.D. Cheng 和 J.R. Chen 等人利用 FCM 方法和在一维 直方图上求取最大熵的方法求得阈值[29]。后来,H.D. Cheng 和 Y.H. Chen 等人基于模糊相 关和最大模糊熵原则,又指出二维直方图可以区分拥有相同灰度值不同邻域特征的像素 [30],提出一种在二维直方图上进行模糊分类的方法。 Francis H. Y. Chan 等人针对背景不平坦的图像提出了一种动态阈值算法[33][34],原图 像 I(x,y)被动态阈值 T(x,y)分类成一个标号图像(label image)L(x,y): L(x,y)= I(x, if 1 if 0 I(x, y) y) > ≤ T(x, T(x, y) y)    (4) 不特殊说明的阈值分割都是利用全局阈值进行分割,它和动态阈值的区别可以利用图 2 表示。 (a) (b) (c) (d) 中国科技论文在线_______________________________________________________________________________www.paper.edu.cn
(e) (f) 图 2 其中,(a)是原始图像;(b)是相应的二维曲面(2-D surface)[33];(c)是全局阈值分割的 结果;(d)是全局阈值对应的二维曲面,由于它不随像素坐标变化,事实上它是一个平面;(e) 是动态阈值分割的结果;(f)是动态阈值对应的二维曲面,我们看到它是随像素坐标缓慢变化 的。 全局阈值分割相当于用(d)中的阈值平面去分类(b)的二维曲面,动态阈值分割相当于用 (f)中的动态阈值曲面去分类(b)的二维曲面。对于这幅大米图像,显然动态阈值要比全局阈 值分割的效果要好。 直方图是像素空间到灰度空间的映射,这是一个多到一的映射,就是说不同的图像是可 以有相同的直方图统计的。而基于直方图的阈值分割技术利用的仅仅是像素的灰度信息,也 就是说把像素的聚类问题转化成一个灰度的聚类问题来解决,这样就降低了运算量和算法的 复杂度。前文提到图像信息的高度冗余,或者说像素间的强烈相关,决定了仅仅利用像素的 灰度进行分割操作是一种信息的浪费或不充分。动态阈值算法的有效性已经初步显示了考虑 图像中像素局部信息的必要性。下一节我们将把视角从直方图扩展到整幅图像,探讨学者们 是怎样在像素空间聚类而完成图像分割任务的。 4 像素空间的聚类 人类视觉系统的研究表明,人眼在识别物体时总是离不开物体所在的周围环境。所以图 像中灰度的局部变化对于图像处理是相当重要的信息[6]。如果在某些特定的尺度上观察图 像,比如说把图像信号通过一个带通滤波器,滤波的结果将使图像的局部信息更好的被表达 [35]。通过一个多尺度分解,轮廓信息可以在大尺度图像上保留下来,细节或者突变信息可 以在中小尺度(mid- to small scales)上体现。基于多尺度图像特征聚类的分割方法渐渐得到了 人们的关注 [27][36][37][ 38][39][40[41][42]。 Cor J. Veenmande 等人指出图像的分割可以通过几个尺度上的聚类逐级地实现[39]。在 像素级的聚类是最小尺度的聚类,假设聚类的结果是集合 A1、A2 •••••• AN,在此基础上在 更大一个尺度上继续聚类的过程,得到 B1、B2 •••••• BM,如此类推,直到一个终止条件满 足为止。显然,不同尺度上的聚类不应该同等对待,所以 Cor J. Veenmande 的方法除了利用 类内方差最小化作为聚类判据,在较小尺度下两类的合并的过程中,还在类间方差上引入了 抑制项。M. Egmont-Petersena 等人的综述中[40]提到了大量应用于分层的分割方案神经网络 技术:位于低层的神经网络在较粗的级别上分类像素的特征,其结果作为高层神经网络的输 中国科技论文在线_______________________________________________________________________________www.paper.edu.cn
入,使之在较细的级别上聚类,最终完成图像的分割。John M.Gauch 在多个尺度上研究图 像的梯度[41],根据梯度进行聚类达到区域分割的目的。Mahmoud Ramze Rezaee 利用金字 塔模型把图像分层[36],每一层再被分成几个区域,然后利用 FCM 方法聚类金字塔产生的 分割区域产生最终的分割图像。姬光荣等人提出一种具有局部性和与分析目标结构尺度自适 应的、依赖于内禀性结构模式的图像分解方法[42]。基于这种分解方法得到一组分解图像, 首先对每一幅分解图像进行灰度分割,然后按“由细到粗”的顺序对分解图像的分割图像进 行并运算,这也可以看作是一个多尺度结构模式的分层次分割。 小波分析理论在近十几年内得到了数学界和工业界的广泛重视,而基于小波理论的多尺 度分析理论(Multiresolution Analysis)则被广泛应用于信号处理、图像处理等领域。小波理 论已经在图像压缩领域获得了公认的成功,JEPG2000 标准便是最好的例子。第 2 节中提到 聚类的有效性和适应性取决于特征向量,Zhongchao SHI 也指出图像分割的效率很大程度上 取决于用于聚类的特征的选取[6],而多尺度分析小波显然具有这种提取多尺度特征的本领 [Hyeokho Choi]~~[]。Xiao-ping Zhang 和 Mita D.Desai 基于多尺度小波分析的理论提出一种 在复杂背景条件下分割连续明亮目标(Bright Targets)的算法[43]。他们在若干个尺度上分 解原始图像,得到相应的子图像,然后利用贝叶斯分布理论分析各自的直方图,自适应的得 到原图像的分割阈值。后来 Xiao-ping Zhang 自己指出,离散小波变换(DWT)不可能得到 精确的边界[44],进而提出一种利用离散小波包(DWP)的方案,获得了边界的精确定位。 Zhongchao SHI 同样利用多分辨率小波理论从金字塔模型中提取边缘和奇异点[6],提出了一 种由粗到细(coarse-to-fine)图像分割方案。James Z. Wang 等人的方案利用了高频小波系数 及其统计量作为图像的特征[45],将特征向量聚类完成粗分割,最后的操作是平滑边界和去 除独立的小区域。Surya Pemmaraju 等人利用多分辨率小波分解重构原始图像,保留了显著 特征[46],而噪声得到了抑制。他的聚类工具选取了 AFLC(adaptive fuzzy leader clustering), 这种聚类方案的初始化过程有点类似前文提到的 ART 网络。吴高洪和章毓晋等人[47]利用 小波变换得到特征矢量,然后根据特征矢量中各个分量的离散程度来对其本身进行加权,从 而使离散程度相对较小的特征分量在分类的作用得到加强,而使离散程度相对较大的特征分 量在分类中的作用的得到减弱。 近几年,基于图论的图像分割方法也是人们感兴趣的领域之一。这种方法的关健在于加 权图(weighted graph)的构造[48],其中顶点代表图像的像素或者区域,边缘的权代表相邻 的像素或者区域的相似度。以最优化某些价值函数为目标,完成图的划分(partition)。针对 图像分割中的聚类问题,Jianbo Shi 和 Jitendra Malik 没有把局部特征和一致性度量作为解 决问题的关键,而是着眼于提取整幅图像的特征[49],为了度量不同分类之间的总体不相似 性和各个类之内的相似性的总和,他们提出了归一化切割判据(normalized cut criterion)。 Song Wang 和 Jeffrey Mark Siskind 主张以切割率(cut ratio)作为价值函数[48]。O. Veksler 的方法通过在一个像素周围构造一组既互不连接又相互嵌套的像素集,可以自动聚类相邻的 小区域[50]。耿伯英等人提出一种将超图理论与图像的空-频特征分析相结合的图像分割算法 [51]。 在无监督聚类领域,广泛应用的一种技术是 WTA 神经网络。参与 WTA 竞争的是对应 每个局部表达(local representation)的单个神经元。相对于一个神经元代表一个目标的局部 表达方式,分布表达(distributed representation)方式中的每个目标对应一组神经元。目标 的若干个特征分别被一组神经元的每个神经元所表达。哪种表达方式更适合于目标的表达, 是神经科学一项重要的分歧。有足够的证据显示,局部表达方式面临着神经生物学理论上的 困难[52][53]。在图像处理领域,WTA 仅仅能产生一个获胜的像素或者获胜的区域,而不是 一个获胜的目标。但是人眼只能注意多个目标中的一个目标,所以在目标级别上进行选择是 相当重要的, WTA 对此无能为力,而诸如图像分割等复杂的视觉计算要求一种目标级别的 中国科技论文在线_______________________________________________________________________________www.paper.edu.cn
选择机制的出现。基于振荡相关理论,Terman 等人提出一种局部振荡全局抑制振荡神经网 络(LEGION),利用振荡元的同步振荡实现了像素的聚类进而完成图像分割。DeLiang Wang 等人对 LEGION 进一步改进,提出了一种动态耦合神经振荡网络(DCNON)[54]。在这分 割图像的过程中,DCNON 定义了四种邻域用于聚类像素,对区域内部像素和区域边界处像 素有不同的聚类标准,因而在分割图像的同时对噪声有很好的抑制作用。据笔者所知, DCNON 是唯一的一种在区域增长的过程中能区分区域内部和区域边界的方法,所以有必要 引起足够的重视。 在哺乳动物视觉表层神经上加上 40Hz 的同步脉冲,仿效其实验结果,人们提出了脉冲 耦合神经网络(PCNN)模型并将其发展。Izhikevich 在数学上严格证明了实际的生物细胞 模型与 PCNN 模型是一致的[55],也就是说将之应用于图像分割等领域是有其生物学上的依 据的。 阈值函数 Vθ θα 1 ijLβ+ ijθ ijF ijU ∏ 0 1 ijY 阶跃函数 图 3 脉冲耦合神经元模型 Eckhorn 的连接域模型是 PCNN 应用于图像处理的基础。Johnson 等人对该模型的修改 使 其 更 适 合 于 图 像 处 理 方 面 的 应 用 。 后 来 学 者 继 续 对 该 模 型 进 行 改 进 [56][57][58][59][60][61]。本文只介绍 Robert D. Stewar 的改进模型,这种方案将 PCNN 模型 用于区域增长的分割算法[56]。PCNN 模型用于图像处理,一个神经元对应一个像素。图 3 是单个神经元的模型表达。整个网络的运行机制是下列四个等式的循环迭代: tLij )( = ∑ )( tYij Nij − d (5) tUij )( = Gij [ 1 + β t )( ⋅ Lij(t) ] (6) Yij t )( = 1   0  if tUij )( otherwise ≥ Tij t )( Tij t )( = t )( ω   Ω  pulse to yet otherwise (7) (8) 其中L为连接输入,(5)式后边第一项是在八邻域内求和,第二项是一个起到平滑作用 的抑制项;U为内部活动项,Gij是像素的灰度,连接系数ß是随时间变化的;输出Yij是内部 活动项和阈值的比较;阈值T不再采用传统的指数衰降,没有点火的神经元的阈值设为没有 点火的神经元对应的像素的灰度的最大值, Ω 代表一个比较大的值,保证每个神经元仅点 火一次。 中国科技论文在线_______________________________________________________________________________www.paper.edu.cn
分享到:
收藏