CN 43-1258/T P ISSN 1007-130X
计算机工程与科学
COM P U T ER EN GIN EERIN G &SCIEN CE
2009年第31卷第12期 Vo l 131, N o 112, 2009
文章编号:1007-130X (2009) 12-0058-04
图像分割算法研究综述
Survey on the Methods of Image Segmentation Research
何 俊, 葛 红, 王玉峰HE Jun, GE Hong, WANG Yu -f eng
(华南师范大学计算机学院, 广东广州510631)
(School of Computer Science, South C hina Normal University, Guangzhou 510631, China)
摘 要:图像分割是图像处理中的一个经典难题, 也是图像处理和计算机视觉领域中的基本技术。目前, 广大研究者在图像分割领域里已提出了上百种分割方法, 每种分割方法只局限特定的分割对象, 至今没有一种通用的方法。本文综述了近年在图像分割技术上出现的常用图像分割算法以及它们的优缺点, 展望了图像分割的前景和面临的挑战。
Abstract:Imag e seg mentat ion is not only a classical puzzle fo r r esear chers but a lso the impor tant part o f imag e analysis and t he co mputer v ision f ield. N ow adays, hundr eds of met ho ds hav e been put forw ard to the imag e segmentatio n, and each o f the met ho ds is used for special segmented objects. T her e is no t a general method fo r imag e segment as yet. T he r ecent w idely used metho ds for imag e seg mentat ion are summa rized in this paper , and the prospect s and challeng es of imag e seg mentat ion are discussed.
关键词:图像分割; 区域生长; 活动边缘; 聚类分析; 遗传算法
Key words:image seg mentation; r eg io nal gr ow ing; active conto ur ; cluster ing analy sis; g enetic algo rit hm doi:10. 3969/j. issn. 1007-130X. 2009. 12. 017中图分类号:T P391. 4
文献标识码:A
像、成像方式以及成像中的可变因素和不变因素(如噪声和
*
1 引言
所谓图像分割是指根据灰度、彩色、空间纹理、几何形
状等特征把图像划分成若干个互不相交的区域, 使得这些特征在同一区域内, 表现出一致性或相似性, 而在不同区域间表现出明显的不同[1]。简单地讲, 就是在一幅图像中, 把目标从背景中分离出来, 以便于进一步处理。图像处理技术在航空航天、生物医学工程、工业检测、机器人视觉、公安司法、军事制导、文化艺术、地理测绘等领域受到广泛重视, 并取得了重大的开拓性成就, 使图像处理成为一门引人注目、前景远大的新型学科。
纹理等) , 这些都会在很大程度上影响后继的分割。
现今国内外广泛使用的图像分割方法主要可分为基于阈值分割、基于变形模型分割、基于区域生长分割、基于聚类法分割、基于遗传算法分割等。
2. 1 基于阈值的图像分割
阈值分割法是一种传统的图像分割方法, 因其实现简单、计算量小、性能较稳定而成为图像分割中最基本和应用最广泛的分割技术。
阈值分割法的基本原理是:通过设定不同的特征阈值, 把图像像素点分为具有不同灰度级的目标区域和背景区域的若干类。它特别适用于目标和背景占据不同灰度级范围的图像[2], 已被应用于很多领域, 其中阈值的选取是图像阈值分割方法中的关键技术。
从其发展历程上来看主要有O tsu 提出的最大类间方差法[3], 它被认为是阈值分割中的经典算法。Kaptur 等提出的最佳熵阈值方法[4], 此算法无需先验知识, 且对于呈非理想双峰直方图的图像也可以进行较好的分割。但是, 该
2 图像分割方法归纳及性能
图像分割的研究多年来一直受到人们的高度重视, 分割算法也层出不穷, 对于图像分割算法的分类依据也不统一。图像分割方法的选择, 在很大程度上依赖于特定的图
*
收稿日期:2008-06-12; 修订日期:2008-10-30
作者简介:何俊(1978) , 男, 湖南邵阳人, 硕士生, 研究方向为数字图像处理; 葛红, 博士, 副教授, 研究方向为人工免疫网络和数字图像处理; 王玉峰, 研究方向为数字图像处理。
通讯地址:510631广东省广州市天河区华南师范大学计算机学院葛红; T el:[1**********]; E -mail:hejun_723@126. com Address:School of Computer Science, South Chin a Normal University, Gu angz hou, Gu angdong 510631, P. R. Chin a
算法在确定阈值, 特别是多阈值时, 存在计算量相当大、分割结果对阈值的变化较为敏感等不足。Do yle 提出的P -tile 法[5]是早期的基于灰度直方图的自动阈值选择方法。该方法计算简单, 抗噪声性能较好。其不足之处是要预先知道给定目标与整幅图像的面积比P, 因此在P 未知或P 随不同图像改变时, 该方法不适用。1984年Dunn 等提出了均匀化误差阈值选取方法[6]。肖超云等在结合Otsu 与信息熵的各自优点的基础上提出了一种基于O tsu 准则及图像熵的阈值分割算法[7]。汤凌等人提出一种基于人工免疫的图像分割算法[8], 该算法在生物免疫的思想上加入了人工免疫算子, 不但能找到最优的阈值, 而且分割时间是传统的1. 8%。
基于阈值分割法虽然简单, 但在阈值的选取很大程度上影响图像分割的效果, 它只考虑像素本身的灰度值, 而不考虑图像的空间分布, 这样其分割结果就对噪声很敏感, 对从事图像分割的人员的先验知识依赖过强。虽然目前出现了各种基于阈值分割的改进算法, 图像分割的效果有所改进, 但在阈值的设置上还是没有很好的解决方法, 若将智能遗传算法应用在阈值筛选上, 选取能最优分割图像的阈值, 这可能是基于阈值分割的图像分割法的发展趋势。
取得了一些相关成就, 如文献[17]提出了一种用于解决传统的参数活动轮廓模型(Snake 模型) 难于处理自动分割医学图像的弱边界问题的基于最小方差Snake 模型的医学图像分割方法; 文献[18]提出了一种基于遗传算法的双T _Snake 模型图像分割方法, 以有效地解决初始位置过于敏感的问题。该方法在对左心室M R I 图像的分割中得到了证明, 效果较好。
2. 3 基于区域增长法的图像分割
区域增长是一种已受到计算机视觉界广泛关注的图像分割方法。这种方法把一幅图像分成许多小区域开始。这些初始的区域可能是小的领域甚至是单个像素。在每个区域中, 对不经过适当定义的能反映一个物体内成员隶属程度的性质进行计算, 用于区分不同物体内像素的性质。对相邻区域的所有边界进行计算, 决定所属区域并合并到其所属区域, 这样一个迭代过程将具有相似性的像素集合起来构成一个区域, 即这种相似性质的像素区域不断地增大。它是一种典型的串行区域分割方法, 其特点是将处理过程分解为多个顺序步骤, 其中后续步骤的处理要根据对前面步骤的结果进行判断后确定[19]。
采用区域生长法的关键在于种子点的位置选择、生长准则和生长顺序。此方法最简单的形式是先人工给出一个种子点, 然后提取出和此种子点具有相同灰度值的所有像素。P ohle 等把待分割区域像素值看作一个正态分布, 先用原始区域生长算法估算出分布参数, 再将该参数应用到第二遍生长过程中, 从而获得更好的结果[20]。为了克服大多数区域生长算法对于初始种子点的选取顺序和位置敏感的问题, Zheng 等开发出不需种子点的自动分割算法[21]; 于水等将图像的纹理信息和灰度信息融合在区域生长的标准中[22]; L aw 等把平面的区域生长算法扩展到三维空间[23]; 文献[24]将模糊理论和优化算法应用到区域生长算法中; 文献[25]将各向异性滤波技术和区域生长算法结合, 并在算法中加入自适应参数的自适应区域生长算法对医学图像进行分割。
区域生长法存在的不足之处是:
(1) 如何定义区域一致性准则;
(2) 其分割结果和种子点的选择有很大关系;
(3) 对噪声很敏感, 可能形成孔状甚至是根本不连续的区域;
(4) 对面积不大的区域分割效果较好, 如果对面积较大的区域进行分割, 则计算速度就会减慢;
(5) 对于图像中不相邻而灰度值相同或相近的区域, 不能一次分割出来, 只能一次分割一个区域;
(6) 很容易产生过图像过分割现象, 分水岭算法可以说就是典型的代表。
2. 2 基于变形模型的图像分割
1987年, K ass M 、W itkin A 和T erzopulo s D 发表的论文/Snakes :A ctiv e Contour M odels 0[9]促使变形模型很快发展成为图像分割中最活跃和最成功的研究领域之一。变形模型可分为两类, 即参数变形模型[10]与几何变形模型[11]。参数变形模型在变形过程中以显式参数的形式表达曲线或曲面, 允许与模型直接交互, 且表达紧凑, 利于模型快速实时地实现。但是, 该方法难以处理在变形过程中发生拓扑结构的变化, 如曲线的分裂或融合等问题。相反, 几何变形模型可自然地处理拓扑结构的变化, 该方法基于曲线演化理论和水平集方法。这些变形模型的能量方程一般有两种类型的能量项:外力能量和内力能量, 其变形过程就是这两种力量彼此消长的过程, 最后达到平衡或达到其它的约束条件。这种能量公式在建立前要找好对象的边界, 首先在图像区域初始化参数曲线, 然后在两力的作用下将其移动到势能最小点[14]。所有的经典Snakes 算法和活动边缘模型依赖边缘终止函数和图像的梯度|▽u0|, 因为要终止曲线进化, 所以这此变形模型仅能检测图像边缘用梯度定义的图像目标。在实际应用中, 图像的不连续的梯度是有界的, 同时边缘终止函数在图像的边缘永远不趋于零, 这时活动轮廓将穿过图像边缘。文献[15]提出了一种没有边缘终止函数即不依赖图像的梯度来停止图像的分割过程, 依靠M umfor d -Shah 分割技术[16]来控制图像分割的终止条件。这种变形模型分割法既能检测有梯度的图像又能检测没有梯度的图像, 也就是说它能检测有光滑边界的图像, 甚至还能检测边缘不连续的图像。
变形(Snake) 模型对噪声和对比度不是很敏感, 能将目标从复杂背景中分割出来。但是, 该模型存在天然缺点:其一是变形模型对初始轮廓的选取很敏感, 初始轮廓的选取能影响分割的效果; 其二是能量函数的设定, 它决定变形曲线的走势, 即影响分割效果; 其三是分割终止条件的设定。近几年来广大研究者在这个领域做了大量的科研工作, 也
[12]
[13]
2. 4 基于聚类法的图像分割
聚类法是图像分割中较为实用的方法, 首先将像素灰度等性质映射到根据一定的规则分为几个区域的特征空间, 然后根据体素的性质判定其所属的区域, 并对此加以标记, 进行分割。
聚类总体上可包括硬聚类、概率聚类、模糊聚类等方法。目前最常用的聚类方法是模糊C -2均值算法[26](Fuzz -
y C -2means Clustering , 简称FCM ) , 它是一种基于模糊理论的图像分割方法, 该法实际上是两次寻优的迭代过程, 首先由C -2均值聚类得到聚类中心的次最优解, 在此基础上再由FCM 进行模糊聚类, 最终得到图像的最优模糊分割。隶属函数的设计是整个模糊算法的关键所在。此算法具有较好的收敛性, 结果受初值的设置影响不大。由于医学图像本质上存在模糊性(如CT 图像同一组织灰度值的含糊性, 容积效应引起的边缘、形状的模糊性及运动伪影造成图像的不确定性等) , 因而聚类法更适合采用对图像不确定性有较好描述能力的模糊理论。国内外很多研究者将模糊理论应用于图像增强、图像分割及边缘检测中, 取得了优于传统图像处理方法的结果[27]。Chen 等[28]就是用一种基于K 平均聚类算法和基于知识的形态学运算技术来对心脏CT 图像进行自动分割。
聚类分析必须解决的两个关键问题就是:(1) 如何评定样本之间的类似程度;
(2) 如何根据样本之间的类似程度将给定的样本集划分为不同的群。
聚类分割中对图像特征的提取、相似度的计算和正确的聚类方法是基于聚类图像分割的研究关键。文献[29]在对聚类分析进行综合分析的基础上提出了一种具有强大记忆库核聚类人工免疫算法, 文献[30]提出了一种基于人工免疫的灰度图像多阈值自动分割方法。能自我学习自我记忆的聚类分析算法将是图像处理中的一个研究热点。
作用是快速分割出前列腺的边界, 他们对22例前列腺超声图像进行识别实验, 得到了很好的结果, 其平均误差是6. 2mm 。文献[18]将遗传算法有效地运用到骨髓细胞图像分割。
将遗传算法运用到图像处理主要是考虑到遗传算法具有与问题领域无关且快速随机的搜索能力。其搜索从群体出发, 具有潜在的并行性, 可以进行多个个体的同时比较, 能有效的加快图像处理速度。但是, 遗传算法也有其缺点:搜索所使用的评价函数的设计、初始种群的选择有一定的依赖性等。要是能够结合一些启发算法进行改进且遗传算法的并行机制的潜力得到充分的利用, 这是当前遗传算法在图像处理中的一个研究热点。
3 分割算法的评价
近年对分割算法的性能评价和比较得到了图像分割领域的广泛重视, 分割评价不仅改进和提高了现有算法的性能而且优化分割, 对新的技术也有指导意义。
评价方法应达到以下基本要求:
(1) 应采用尽可能反映客观世界的真实情况和实际应用的共同特点的图像进行测试, 以使评价结果具有可比性; (2) 应采用不仅可以摆脱人为因素且能精准描述算法性能的评价准则;
(3) 评价标准应具有通用性, 即要适于评价不同类型的分割算法且适合各种应用领域。
评价分割算法的关键之处在于:其一是分析分割算法的机制或实验分割算法的途径; 其二是用来评判算法的性能准则。
2. 5 基于遗传算法的图像分割
遗传算法(G enetic A lg or ithms, 简称GA ) 是1973年由美国教授H olland 提出的, 是一种借鉴生物界自然选择和自然遗传机制的随机化搜索算法, 是仿生学在数学领域的应用。其基本思想是, 模拟由一些基因串控制的生物群体的进化过程, 把该过程的原理应用到搜索算法中, 以提高寻优的速度和质量[31]。此算法的搜索过程不直接作用在变量上, 而是在参数集进行了编码的个体, 这使得遗传算法可直接对结构对象(图像) 进行操作。整个搜索过程是从一组解迭代到另一组解, 采用同时处理群体中多个个体的方法, 降低了陷入局部最优解的可能性, 并易于并行化。搜索过程采用概率的变迁规则来指导搜索方向, 而不采用确定性搜索规则, 而且对搜索空间没有任何特殊要求(如连通性、凸性等) , 只利用适应性信息, 不需要导数等其他辅助信息, 适应范围广。
遗传算法擅长于全局搜索, 但局部搜索能力不足, 所以常把遗传算法和其他算法结合起来应用。1996年Sahiner 等
[32]
4 结束语
目前, 图像分割方法正朝着自动、精确、快速、自适应性和鲁棒性的目标发展。追求智能化分割、最优化分割、自主学习分割将成为这一领域的新热点, 遗传算法在分割领域受到强烈的关注, 人们将具有全局最优的遗传算法与最佳信息、最大类间差等相结合自动寻找最优阈值进行分割, 将遗传算法与聚类分析相结合应用于基于区域生长分割的最优化初始种群的选取, 并引入自主学习功能使分割向自动、启发式方向发展。
参考文献:
[1] 章毓晋. 图像分割[M ]. 北京:科学出版社, 2001.
[2] 王新成. 高级图象处理技术[M ]. 北京:中国科学技术出版
社, 2000.
[3] Otsu N. A T hres hold S election M ethod from Gray Level His -togram [J ]. IEEE T rans on Sy stem M an and Cybernetics, 1979, 9(1) :62-66
[4] 罗西平, 田捷. 图像分割方法综述[J ]. 模式识别与人工智能,
1999, 9(3) :300-312.
[5] Kittler J, Illin gw orth J. M inimu m Error Th res holding [J ].
Pattern Recognition, 1986, 19(1) :41-47.
[6] Dunn S M , H arw ood D, Davis L S. Local Estimation of the U -niform E rror T hres hold [J]. IEEE T ran s on PAM I, 1984, 6
用遗传算法来寻找乳房X 线造影片的可疑区域。他
们认为GA 可以提供多功能的直线及非线性设计的分类
器, 而不影响选择的效力。与逐步搜索相比, G A 的寻优全面, 使分割更彻底, 但并不增加运算量。2000年Chen 等[33]把遗传算法应用到心脏超声波图像的分割中, 以用来弥补主动轮廓法的缺陷, 建立了一种自学习分割框架) ) ) T aguchi 逼近。用该法对人工合成图像和真正的超声波图像进行的实验得到了很好的结果, 其有效性通过了方差分析的验证。1999年A rambula 等利用GA 的快速寻优能力来进行前列腺的自动化识别工作, GA 在这里所起的
[34]
(6) :742-745.
[7] 肖超云, 朱伟兴. 基于Otsu 准则及图像熵的阈值分割算法
[J ]. 计算机工程, 2007, 33(14) :188-190.
[8] 汤凌, 郑肇葆, 虞欣. 一种基于人工免疫的图像分割算法[J].
武汉大学学报(信息科学) , 2007, 32(1) :67-70. [9]
Kas s M , Witkin A, T erz opu los D. Snakes:Active Contour M od els [J]. Int . l Journ al of C om puter Vision, 1987, 1(4) :321-331.
[10] C oh en L D. On Active Contour M odels an d Balloon s [J].
C VGIP:Image Un der, 1991, 53(2) :112-218.
[11] Caselles V, Catte F, TColl, et al. A Geometric M odel for Ac -tive Contours[J]. Numeric Mathematik, 1993, 66(1) :1-31.
[12] Kimia B B, T an nenb aum A R, Zu cker S W. Sh apes,
S hocks ,
and
Deformations
I:
T he
Components
of
T w o2Dimensional Sh ape and th e Reaction -Diffusion S pace [J ]. In t . l J ou rnal of C om puter Vision, 1995, 8:189-224.
[13] Osh er S, Seth ian J. Fronts Propagating w ith Cu rvature De -penden t S peed:Algorithms Bas ed on H am ilton -J acob i For -mu lations [J]. Comput Ph ys, 1988, 79(1) :12-49.
[14] 刘新, 潘振宽, 李新照, 等. 医学图像分割技术中变形模型方
法的研究综述[J]. 计算机应用研究, 2006, 23(8) :14-18.
[15] C han T F, Vese L A. Active C ontour s With ou t Edges [J].
IEEE T rans on Image Processing, 2001, 10(2) :266-277.
[16] M umford D, S hah J. Optimal Appr oximation by Piecew is e
S mooth Fun ctions and Ass ociated Variation al Problems[J]. C om mun Pu re Appl M ath, 1989, 42(5) :577-685.
[17] 周昌雄, 于盛林. 基于最小方差S nak e 模型的医学图像分割
[J ]. 生物医学工程杂志, 2007, 24(1) :32-35.
[18] 张建伟, 罗剑, 夏德深. 一种基于遗传算法的双T _Snake模型
图像分割方法[J]. 中国图像图形学报, 2005, 10(1):38-42.
[19] Lu Yingli, Jiang T ianzi, Zang Yufen g. Region Grow ing
M ethod for th e Analys is of Functional M RI Data [J]. Neuro Image, 2003, 20(1) :455-465.
[20] Pohle R , T -Nnies K D. A New Approach for M ode-l Bas ed
Adaptive Region Gr ow ing in M edical Image Analysis [C]M Proc of the 9th Int . l Conf on Computer Analysis an d Pat -terns, 2001:238-246.
[21] Zheng L, Jin J. H ugues T 1U nseeded Region Grow in g for
3Dimage Segm entation [J]. Journ al of Res earch and Practice in Information T echnology, 2001(2) :31-37.
[22] Yu Sh ui, M a Fanyu an. M edical Image S egmentation M ethod
Based on Information Fu sion [J]. Journ al of Com puter -A-i ded Des ign &Com puter Grap hics, 2001, 13(12) :1073-1076.
[23] Law T Y, H en g P A. Automated Extraction of Bronch us
from 3D CT Images of Lun g Based on Genetic Algorithm and 3D Region Grow ing[C]M Proc of SPIE, 2000:906-916.
[24] You Jianjie, Zh ou Zeming, Pheng Ann H eng, et al. S imula -ted Ann ealing Based Simplified Snakes for Weak Edge M ed-i cal Imag e Segm entation[J]. Journal of Image and Graphics, 2004, 9(1) :11-17.
[25] 陆剑锋, 林海, 潘志庚. 自适应区域生长算法在医学图像分
割中的应用[J ]. 计算机辅助设计与图形学学报, 2005, 17(10) :2168-2173.
[26] U dupa J K, Wei L, S amarasekera S, et al. M u ltiple Sclero -sis Lesion Qualification Using Fuzzy -Connectedness Prin c-i
ple[J]. IEEE Trans on M ed Imaging, 1997, 16(5) :598-609.
[27] Ven Katesw arlu N B, Raju P S V S K. Fast Isodata Cluste -ring Algorithms [J]. Pattern Recognition, 1992, 25(3) :335-342.
[28] Chen C W, Lu o J, Park er K J , et al. Ackn ow ledge Based
Approach To Volu metric M edical Im age Segmentation[C]M Proc of IEEE Int . l Conf on Image Processing, 1994:493-497.
[29] 葛红. 免疫算法及核聚类人工免疫网络应用研究[D]. 中国
优秀博士论文.
[30] 李彬, 田联房, 毛宗源. 基于人工免疫的灰度图像多阈值自
动分割[J]. 计算机工程与设计, 2007, 28(1) :106-108.
[31] Holland J . Genetic Algori thms and the Optimal Allocati ons of
Trials [J]. SIAM Journal on Computing, 1973, 2(2):43-46.
[32] Sahiner B, Chan H P, W ei D, et al. Image Featur e Selec -tion by A Genetic Algorithm:Application to Classification of M ass and Norm al Breast Tis sue[J]. M ed Ph ys, 1996, 23(10) :1671-1684.
[33] Chen D, Sun Y. A S elf -Learning S egmentation Framew or k
T he T aguchi Approach [J ]. Comput M ed Imaging Graph, 2000, 24(5) :283-296.
[34] Arambula C F , Davies B L. Automated Pr os tate Recogn-i
tion:A Key Pr ocess for Clinically Effective Robotic Prosta -tectomy[J ]. M ed Biol E ng C om put, 1999, 37(2) :236-243.
(上接第40页)
从表2中可以看出, 本文方法对当前位置的预测所产
生的误差是可以让人们接受的。
7 结束语
本文提出了基于触发式的移动对象位置信息发送方法, 管理大量移动对象的服务器采用这种方法可节约大量的系统资源。此方法在生成的当前运动轨迹中存在着一定的误差, 支持移动对象当前位置带误差的查询, 我们可以根据需要, 选择不同的阈值将误差控制在一定的范围之内。下一步工作应进一步完善服务器的查询功能, 更好地支持这种位置信息发送方法, 使移动对象的位置查询更加精确。
参考文献:
[1] Abadi D J, Carney D, Cetintemel U, et al. Aurora:A New
M odel and Architecture for Data Stream M anagem ent [J ]. VLDB Journ al, 2003, 12(2) :120-139.
[2] 丁晓丽, 郝忠孝. 移动对象的建模和查询[J]. 齐齐哈尔大学
学报(自然科学版) , 2005, 21(1) :50-54.
[3] 卢炎生, 查志勇, 潘鹏. 一种改进的移动对象的时空数据模型
[J]. 华中科技大学学报(自然科学版) , 2006, 34(8) :32-35. [4] 莫国端, 刘开弟. 函数逼近论方法[M ]. 北京:科学出版社,
2003.
[5] T rajcevs ki G, W olfs on O, H u C , et al . M anagin g Un certainty
in M oving Objects Databases [J ]. ACM T rans on Database Sys tem, 2004, 5(1) :115-123.
[6] 郭薇, 郭菁, 胡志勇. 空间数据库索引技术[M ]. 上海:上海
交通大学出版社, 2006.
CN 43-1258/T P ISSN 1007-130X
计算机工程与科学
COM P U T ER EN GIN EERIN G &SCIEN CE
2009年第31卷第12期 Vo l 131, N o 112, 2009
文章编号:1007-130X (2009) 12-0058-04
图像分割算法研究综述
Survey on the Methods of Image Segmentation Research
何 俊, 葛 红, 王玉峰HE Jun, GE Hong, WANG Yu -f eng
(华南师范大学计算机学院, 广东广州510631)
(School of Computer Science, South C hina Normal University, Guangzhou 510631, China)
摘 要:图像分割是图像处理中的一个经典难题, 也是图像处理和计算机视觉领域中的基本技术。目前, 广大研究者在图像分割领域里已提出了上百种分割方法, 每种分割方法只局限特定的分割对象, 至今没有一种通用的方法。本文综述了近年在图像分割技术上出现的常用图像分割算法以及它们的优缺点, 展望了图像分割的前景和面临的挑战。
Abstract:Imag e seg mentat ion is not only a classical puzzle fo r r esear chers but a lso the impor tant part o f imag e analysis and t he co mputer v ision f ield. N ow adays, hundr eds of met ho ds hav e been put forw ard to the imag e segmentatio n, and each o f the met ho ds is used for special segmented objects. T her e is no t a general method fo r imag e segment as yet. T he r ecent w idely used metho ds for imag e seg mentat ion are summa rized in this paper , and the prospect s and challeng es of imag e seg mentat ion are discussed.
关键词:图像分割; 区域生长; 活动边缘; 聚类分析; 遗传算法
Key words:image seg mentation; r eg io nal gr ow ing; active conto ur ; cluster ing analy sis; g enetic algo rit hm doi:10. 3969/j. issn. 1007-130X. 2009. 12. 017中图分类号:T P391. 4
文献标识码:A
像、成像方式以及成像中的可变因素和不变因素(如噪声和
*
1 引言
所谓图像分割是指根据灰度、彩色、空间纹理、几何形
状等特征把图像划分成若干个互不相交的区域, 使得这些特征在同一区域内, 表现出一致性或相似性, 而在不同区域间表现出明显的不同[1]。简单地讲, 就是在一幅图像中, 把目标从背景中分离出来, 以便于进一步处理。图像处理技术在航空航天、生物医学工程、工业检测、机器人视觉、公安司法、军事制导、文化艺术、地理测绘等领域受到广泛重视, 并取得了重大的开拓性成就, 使图像处理成为一门引人注目、前景远大的新型学科。
纹理等) , 这些都会在很大程度上影响后继的分割。
现今国内外广泛使用的图像分割方法主要可分为基于阈值分割、基于变形模型分割、基于区域生长分割、基于聚类法分割、基于遗传算法分割等。
2. 1 基于阈值的图像分割
阈值分割法是一种传统的图像分割方法, 因其实现简单、计算量小、性能较稳定而成为图像分割中最基本和应用最广泛的分割技术。
阈值分割法的基本原理是:通过设定不同的特征阈值, 把图像像素点分为具有不同灰度级的目标区域和背景区域的若干类。它特别适用于目标和背景占据不同灰度级范围的图像[2], 已被应用于很多领域, 其中阈值的选取是图像阈值分割方法中的关键技术。
从其发展历程上来看主要有O tsu 提出的最大类间方差法[3], 它被认为是阈值分割中的经典算法。Kaptur 等提出的最佳熵阈值方法[4], 此算法无需先验知识, 且对于呈非理想双峰直方图的图像也可以进行较好的分割。但是, 该
2 图像分割方法归纳及性能
图像分割的研究多年来一直受到人们的高度重视, 分割算法也层出不穷, 对于图像分割算法的分类依据也不统一。图像分割方法的选择, 在很大程度上依赖于特定的图
*
收稿日期:2008-06-12; 修订日期:2008-10-30
作者简介:何俊(1978) , 男, 湖南邵阳人, 硕士生, 研究方向为数字图像处理; 葛红, 博士, 副教授, 研究方向为人工免疫网络和数字图像处理; 王玉峰, 研究方向为数字图像处理。
通讯地址:510631广东省广州市天河区华南师范大学计算机学院葛红; T el:[1**********]; E -mail:hejun_723@126. com Address:School of Computer Science, South Chin a Normal University, Gu angz hou, Gu angdong 510631, P. R. Chin a
算法在确定阈值, 特别是多阈值时, 存在计算量相当大、分割结果对阈值的变化较为敏感等不足。Do yle 提出的P -tile 法[5]是早期的基于灰度直方图的自动阈值选择方法。该方法计算简单, 抗噪声性能较好。其不足之处是要预先知道给定目标与整幅图像的面积比P, 因此在P 未知或P 随不同图像改变时, 该方法不适用。1984年Dunn 等提出了均匀化误差阈值选取方法[6]。肖超云等在结合Otsu 与信息熵的各自优点的基础上提出了一种基于O tsu 准则及图像熵的阈值分割算法[7]。汤凌等人提出一种基于人工免疫的图像分割算法[8], 该算法在生物免疫的思想上加入了人工免疫算子, 不但能找到最优的阈值, 而且分割时间是传统的1. 8%。
基于阈值分割法虽然简单, 但在阈值的选取很大程度上影响图像分割的效果, 它只考虑像素本身的灰度值, 而不考虑图像的空间分布, 这样其分割结果就对噪声很敏感, 对从事图像分割的人员的先验知识依赖过强。虽然目前出现了各种基于阈值分割的改进算法, 图像分割的效果有所改进, 但在阈值的设置上还是没有很好的解决方法, 若将智能遗传算法应用在阈值筛选上, 选取能最优分割图像的阈值, 这可能是基于阈值分割的图像分割法的发展趋势。
取得了一些相关成就, 如文献[17]提出了一种用于解决传统的参数活动轮廓模型(Snake 模型) 难于处理自动分割医学图像的弱边界问题的基于最小方差Snake 模型的医学图像分割方法; 文献[18]提出了一种基于遗传算法的双T _Snake 模型图像分割方法, 以有效地解决初始位置过于敏感的问题。该方法在对左心室M R I 图像的分割中得到了证明, 效果较好。
2. 3 基于区域增长法的图像分割
区域增长是一种已受到计算机视觉界广泛关注的图像分割方法。这种方法把一幅图像分成许多小区域开始。这些初始的区域可能是小的领域甚至是单个像素。在每个区域中, 对不经过适当定义的能反映一个物体内成员隶属程度的性质进行计算, 用于区分不同物体内像素的性质。对相邻区域的所有边界进行计算, 决定所属区域并合并到其所属区域, 这样一个迭代过程将具有相似性的像素集合起来构成一个区域, 即这种相似性质的像素区域不断地增大。它是一种典型的串行区域分割方法, 其特点是将处理过程分解为多个顺序步骤, 其中后续步骤的处理要根据对前面步骤的结果进行判断后确定[19]。
采用区域生长法的关键在于种子点的位置选择、生长准则和生长顺序。此方法最简单的形式是先人工给出一个种子点, 然后提取出和此种子点具有相同灰度值的所有像素。P ohle 等把待分割区域像素值看作一个正态分布, 先用原始区域生长算法估算出分布参数, 再将该参数应用到第二遍生长过程中, 从而获得更好的结果[20]。为了克服大多数区域生长算法对于初始种子点的选取顺序和位置敏感的问题, Zheng 等开发出不需种子点的自动分割算法[21]; 于水等将图像的纹理信息和灰度信息融合在区域生长的标准中[22]; L aw 等把平面的区域生长算法扩展到三维空间[23]; 文献[24]将模糊理论和优化算法应用到区域生长算法中; 文献[25]将各向异性滤波技术和区域生长算法结合, 并在算法中加入自适应参数的自适应区域生长算法对医学图像进行分割。
区域生长法存在的不足之处是:
(1) 如何定义区域一致性准则;
(2) 其分割结果和种子点的选择有很大关系;
(3) 对噪声很敏感, 可能形成孔状甚至是根本不连续的区域;
(4) 对面积不大的区域分割效果较好, 如果对面积较大的区域进行分割, 则计算速度就会减慢;
(5) 对于图像中不相邻而灰度值相同或相近的区域, 不能一次分割出来, 只能一次分割一个区域;
(6) 很容易产生过图像过分割现象, 分水岭算法可以说就是典型的代表。
2. 2 基于变形模型的图像分割
1987年, K ass M 、W itkin A 和T erzopulo s D 发表的论文/Snakes :A ctiv e Contour M odels 0[9]促使变形模型很快发展成为图像分割中最活跃和最成功的研究领域之一。变形模型可分为两类, 即参数变形模型[10]与几何变形模型[11]。参数变形模型在变形过程中以显式参数的形式表达曲线或曲面, 允许与模型直接交互, 且表达紧凑, 利于模型快速实时地实现。但是, 该方法难以处理在变形过程中发生拓扑结构的变化, 如曲线的分裂或融合等问题。相反, 几何变形模型可自然地处理拓扑结构的变化, 该方法基于曲线演化理论和水平集方法。这些变形模型的能量方程一般有两种类型的能量项:外力能量和内力能量, 其变形过程就是这两种力量彼此消长的过程, 最后达到平衡或达到其它的约束条件。这种能量公式在建立前要找好对象的边界, 首先在图像区域初始化参数曲线, 然后在两力的作用下将其移动到势能最小点[14]。所有的经典Snakes 算法和活动边缘模型依赖边缘终止函数和图像的梯度|▽u0|, 因为要终止曲线进化, 所以这此变形模型仅能检测图像边缘用梯度定义的图像目标。在实际应用中, 图像的不连续的梯度是有界的, 同时边缘终止函数在图像的边缘永远不趋于零, 这时活动轮廓将穿过图像边缘。文献[15]提出了一种没有边缘终止函数即不依赖图像的梯度来停止图像的分割过程, 依靠M umfor d -Shah 分割技术[16]来控制图像分割的终止条件。这种变形模型分割法既能检测有梯度的图像又能检测没有梯度的图像, 也就是说它能检测有光滑边界的图像, 甚至还能检测边缘不连续的图像。
变形(Snake) 模型对噪声和对比度不是很敏感, 能将目标从复杂背景中分割出来。但是, 该模型存在天然缺点:其一是变形模型对初始轮廓的选取很敏感, 初始轮廓的选取能影响分割的效果; 其二是能量函数的设定, 它决定变形曲线的走势, 即影响分割效果; 其三是分割终止条件的设定。近几年来广大研究者在这个领域做了大量的科研工作, 也
[12]
[13]
2. 4 基于聚类法的图像分割
聚类法是图像分割中较为实用的方法, 首先将像素灰度等性质映射到根据一定的规则分为几个区域的特征空间, 然后根据体素的性质判定其所属的区域, 并对此加以标记, 进行分割。
聚类总体上可包括硬聚类、概率聚类、模糊聚类等方法。目前最常用的聚类方法是模糊C -2均值算法[26](Fuzz -
y C -2means Clustering , 简称FCM ) , 它是一种基于模糊理论的图像分割方法, 该法实际上是两次寻优的迭代过程, 首先由C -2均值聚类得到聚类中心的次最优解, 在此基础上再由FCM 进行模糊聚类, 最终得到图像的最优模糊分割。隶属函数的设计是整个模糊算法的关键所在。此算法具有较好的收敛性, 结果受初值的设置影响不大。由于医学图像本质上存在模糊性(如CT 图像同一组织灰度值的含糊性, 容积效应引起的边缘、形状的模糊性及运动伪影造成图像的不确定性等) , 因而聚类法更适合采用对图像不确定性有较好描述能力的模糊理论。国内外很多研究者将模糊理论应用于图像增强、图像分割及边缘检测中, 取得了优于传统图像处理方法的结果[27]。Chen 等[28]就是用一种基于K 平均聚类算法和基于知识的形态学运算技术来对心脏CT 图像进行自动分割。
聚类分析必须解决的两个关键问题就是:(1) 如何评定样本之间的类似程度;
(2) 如何根据样本之间的类似程度将给定的样本集划分为不同的群。
聚类分割中对图像特征的提取、相似度的计算和正确的聚类方法是基于聚类图像分割的研究关键。文献[29]在对聚类分析进行综合分析的基础上提出了一种具有强大记忆库核聚类人工免疫算法, 文献[30]提出了一种基于人工免疫的灰度图像多阈值自动分割方法。能自我学习自我记忆的聚类分析算法将是图像处理中的一个研究热点。
作用是快速分割出前列腺的边界, 他们对22例前列腺超声图像进行识别实验, 得到了很好的结果, 其平均误差是6. 2mm 。文献[18]将遗传算法有效地运用到骨髓细胞图像分割。
将遗传算法运用到图像处理主要是考虑到遗传算法具有与问题领域无关且快速随机的搜索能力。其搜索从群体出发, 具有潜在的并行性, 可以进行多个个体的同时比较, 能有效的加快图像处理速度。但是, 遗传算法也有其缺点:搜索所使用的评价函数的设计、初始种群的选择有一定的依赖性等。要是能够结合一些启发算法进行改进且遗传算法的并行机制的潜力得到充分的利用, 这是当前遗传算法在图像处理中的一个研究热点。
3 分割算法的评价
近年对分割算法的性能评价和比较得到了图像分割领域的广泛重视, 分割评价不仅改进和提高了现有算法的性能而且优化分割, 对新的技术也有指导意义。
评价方法应达到以下基本要求:
(1) 应采用尽可能反映客观世界的真实情况和实际应用的共同特点的图像进行测试, 以使评价结果具有可比性; (2) 应采用不仅可以摆脱人为因素且能精准描述算法性能的评价准则;
(3) 评价标准应具有通用性, 即要适于评价不同类型的分割算法且适合各种应用领域。
评价分割算法的关键之处在于:其一是分析分割算法的机制或实验分割算法的途径; 其二是用来评判算法的性能准则。
2. 5 基于遗传算法的图像分割
遗传算法(G enetic A lg or ithms, 简称GA ) 是1973年由美国教授H olland 提出的, 是一种借鉴生物界自然选择和自然遗传机制的随机化搜索算法, 是仿生学在数学领域的应用。其基本思想是, 模拟由一些基因串控制的生物群体的进化过程, 把该过程的原理应用到搜索算法中, 以提高寻优的速度和质量[31]。此算法的搜索过程不直接作用在变量上, 而是在参数集进行了编码的个体, 这使得遗传算法可直接对结构对象(图像) 进行操作。整个搜索过程是从一组解迭代到另一组解, 采用同时处理群体中多个个体的方法, 降低了陷入局部最优解的可能性, 并易于并行化。搜索过程采用概率的变迁规则来指导搜索方向, 而不采用确定性搜索规则, 而且对搜索空间没有任何特殊要求(如连通性、凸性等) , 只利用适应性信息, 不需要导数等其他辅助信息, 适应范围广。
遗传算法擅长于全局搜索, 但局部搜索能力不足, 所以常把遗传算法和其他算法结合起来应用。1996年Sahiner 等
[32]
4 结束语
目前, 图像分割方法正朝着自动、精确、快速、自适应性和鲁棒性的目标发展。追求智能化分割、最优化分割、自主学习分割将成为这一领域的新热点, 遗传算法在分割领域受到强烈的关注, 人们将具有全局最优的遗传算法与最佳信息、最大类间差等相结合自动寻找最优阈值进行分割, 将遗传算法与聚类分析相结合应用于基于区域生长分割的最优化初始种群的选取, 并引入自主学习功能使分割向自动、启发式方向发展。
参考文献:
[1] 章毓晋. 图像分割[M ]. 北京:科学出版社, 2001.
[2] 王新成. 高级图象处理技术[M ]. 北京:中国科学技术出版
社, 2000.
[3] Otsu N. A T hres hold S election M ethod from Gray Level His -togram [J ]. IEEE T rans on Sy stem M an and Cybernetics, 1979, 9(1) :62-66
[4] 罗西平, 田捷. 图像分割方法综述[J ]. 模式识别与人工智能,
1999, 9(3) :300-312.
[5] Kittler J, Illin gw orth J. M inimu m Error Th res holding [J ].
Pattern Recognition, 1986, 19(1) :41-47.
[6] Dunn S M , H arw ood D, Davis L S. Local Estimation of the U -niform E rror T hres hold [J]. IEEE T ran s on PAM I, 1984, 6
用遗传算法来寻找乳房X 线造影片的可疑区域。他
们认为GA 可以提供多功能的直线及非线性设计的分类
器, 而不影响选择的效力。与逐步搜索相比, G A 的寻优全面, 使分割更彻底, 但并不增加运算量。2000年Chen 等[33]把遗传算法应用到心脏超声波图像的分割中, 以用来弥补主动轮廓法的缺陷, 建立了一种自学习分割框架) ) ) T aguchi 逼近。用该法对人工合成图像和真正的超声波图像进行的实验得到了很好的结果, 其有效性通过了方差分析的验证。1999年A rambula 等利用GA 的快速寻优能力来进行前列腺的自动化识别工作, GA 在这里所起的
[34]
(6) :742-745.
[7] 肖超云, 朱伟兴. 基于Otsu 准则及图像熵的阈值分割算法
[J ]. 计算机工程, 2007, 33(14) :188-190.
[8] 汤凌, 郑肇葆, 虞欣. 一种基于人工免疫的图像分割算法[J].
武汉大学学报(信息科学) , 2007, 32(1) :67-70. [9]
Kas s M , Witkin A, T erz opu los D. Snakes:Active Contour M od els [J]. Int . l Journ al of C om puter Vision, 1987, 1(4) :321-331.
[10] C oh en L D. On Active Contour M odels an d Balloon s [J].
C VGIP:Image Un der, 1991, 53(2) :112-218.
[11] Caselles V, Catte F, TColl, et al. A Geometric M odel for Ac -tive Contours[J]. Numeric Mathematik, 1993, 66(1) :1-31.
[12] Kimia B B, T an nenb aum A R, Zu cker S W. Sh apes,
S hocks ,
and
Deformations
I:
T he
Components
of
T w o2Dimensional Sh ape and th e Reaction -Diffusion S pace [J ]. In t . l J ou rnal of C om puter Vision, 1995, 8:189-224.
[13] Osh er S, Seth ian J. Fronts Propagating w ith Cu rvature De -penden t S peed:Algorithms Bas ed on H am ilton -J acob i For -mu lations [J]. Comput Ph ys, 1988, 79(1) :12-49.
[14] 刘新, 潘振宽, 李新照, 等. 医学图像分割技术中变形模型方
法的研究综述[J]. 计算机应用研究, 2006, 23(8) :14-18.
[15] C han T F, Vese L A. Active C ontour s With ou t Edges [J].
IEEE T rans on Image Processing, 2001, 10(2) :266-277.
[16] M umford D, S hah J. Optimal Appr oximation by Piecew is e
S mooth Fun ctions and Ass ociated Variation al Problems[J]. C om mun Pu re Appl M ath, 1989, 42(5) :577-685.
[17] 周昌雄, 于盛林. 基于最小方差S nak e 模型的医学图像分割
[J ]. 生物医学工程杂志, 2007, 24(1) :32-35.
[18] 张建伟, 罗剑, 夏德深. 一种基于遗传算法的双T _Snake模型
图像分割方法[J]. 中国图像图形学报, 2005, 10(1):38-42.
[19] Lu Yingli, Jiang T ianzi, Zang Yufen g. Region Grow ing
M ethod for th e Analys is of Functional M RI Data [J]. Neuro Image, 2003, 20(1) :455-465.
[20] Pohle R , T -Nnies K D. A New Approach for M ode-l Bas ed
Adaptive Region Gr ow ing in M edical Image Analysis [C]M Proc of the 9th Int . l Conf on Computer Analysis an d Pat -terns, 2001:238-246.
[21] Zheng L, Jin J. H ugues T 1U nseeded Region Grow in g for
3Dimage Segm entation [J]. Journ al of Res earch and Practice in Information T echnology, 2001(2) :31-37.
[22] Yu Sh ui, M a Fanyu an. M edical Image S egmentation M ethod
Based on Information Fu sion [J]. Journ al of Com puter -A-i ded Des ign &Com puter Grap hics, 2001, 13(12) :1073-1076.
[23] Law T Y, H en g P A. Automated Extraction of Bronch us
from 3D CT Images of Lun g Based on Genetic Algorithm and 3D Region Grow ing[C]M Proc of SPIE, 2000:906-916.
[24] You Jianjie, Zh ou Zeming, Pheng Ann H eng, et al. S imula -ted Ann ealing Based Simplified Snakes for Weak Edge M ed-i cal Imag e Segm entation[J]. Journal of Image and Graphics, 2004, 9(1) :11-17.
[25] 陆剑锋, 林海, 潘志庚. 自适应区域生长算法在医学图像分
割中的应用[J ]. 计算机辅助设计与图形学学报, 2005, 17(10) :2168-2173.
[26] U dupa J K, Wei L, S amarasekera S, et al. M u ltiple Sclero -sis Lesion Qualification Using Fuzzy -Connectedness Prin c-i
ple[J]. IEEE Trans on M ed Imaging, 1997, 16(5) :598-609.
[27] Ven Katesw arlu N B, Raju P S V S K. Fast Isodata Cluste -ring Algorithms [J]. Pattern Recognition, 1992, 25(3) :335-342.
[28] Chen C W, Lu o J, Park er K J , et al. Ackn ow ledge Based
Approach To Volu metric M edical Im age Segmentation[C]M Proc of IEEE Int . l Conf on Image Processing, 1994:493-497.
[29] 葛红. 免疫算法及核聚类人工免疫网络应用研究[D]. 中国
优秀博士论文.
[30] 李彬, 田联房, 毛宗源. 基于人工免疫的灰度图像多阈值自
动分割[J]. 计算机工程与设计, 2007, 28(1) :106-108.
[31] Holland J . Genetic Algori thms and the Optimal Allocati ons of
Trials [J]. SIAM Journal on Computing, 1973, 2(2):43-46.
[32] Sahiner B, Chan H P, W ei D, et al. Image Featur e Selec -tion by A Genetic Algorithm:Application to Classification of M ass and Norm al Breast Tis sue[J]. M ed Ph ys, 1996, 23(10) :1671-1684.
[33] Chen D, Sun Y. A S elf -Learning S egmentation Framew or k
T he T aguchi Approach [J ]. Comput M ed Imaging Graph, 2000, 24(5) :283-296.
[34] Arambula C F , Davies B L. Automated Pr os tate Recogn-i
tion:A Key Pr ocess for Clinically Effective Robotic Prosta -tectomy[J ]. M ed Biol E ng C om put, 1999, 37(2) :236-243.
(上接第40页)
从表2中可以看出, 本文方法对当前位置的预测所产
生的误差是可以让人们接受的。
7 结束语
本文提出了基于触发式的移动对象位置信息发送方法, 管理大量移动对象的服务器采用这种方法可节约大量的系统资源。此方法在生成的当前运动轨迹中存在着一定的误差, 支持移动对象当前位置带误差的查询, 我们可以根据需要, 选择不同的阈值将误差控制在一定的范围之内。下一步工作应进一步完善服务器的查询功能, 更好地支持这种位置信息发送方法, 使移动对象的位置查询更加精确。
参考文献:
[1] Abadi D J, Carney D, Cetintemel U, et al. Aurora:A New
M odel and Architecture for Data Stream M anagem ent [J ]. VLDB Journ al, 2003, 12(2) :120-139.
[2] 丁晓丽, 郝忠孝. 移动对象的建模和查询[J]. 齐齐哈尔大学
学报(自然科学版) , 2005, 21(1) :50-54.
[3] 卢炎生, 查志勇, 潘鹏. 一种改进的移动对象的时空数据模型
[J]. 华中科技大学学报(自然科学版) , 2006, 34(8) :32-35. [4] 莫国端, 刘开弟. 函数逼近论方法[M ]. 北京:科学出版社,
2003.
[5] T rajcevs ki G, W olfs on O, H u C , et al . M anagin g Un certainty
in M oving Objects Databases [J ]. ACM T rans on Database Sys tem, 2004, 5(1) :115-123.
[6] 郭薇, 郭菁, 胡志勇. 空间数据库索引技术[M ]. 上海:上海
交通大学出版社, 2006.