此生不换独家通信专业资料-70

通信专业资料

西安邮电学院

毕业设计(论文)开题报告

计算机 学院 计算机科学与技术专业 07 级 01 班

课题名称： 基于分裂合并的

图像分割算法研究

学号：04051050

指导教师： 吕 建 平

报告日期： 2010年12月10日

通信专业资料

1.本课题所涉及的问题及应用现状综述 图像分割是指把图像分解成各具特性的区域并提取出感兴趣目标的技术 和过程，它是计算机视觉领域的一个重要而且基本的问题，分割结果的好坏将 直接影响到视觉系统的性能。因此从原理、应用和应用效果的评估上深入研究 图像分割技术具有十分重要的意义。基于边缘检测方法种类繁多，主要包括基 于EDGE函数、检测微小结构、四叉树分解和阈值分割的方法实现对图像的边缘 检测及提取。而基于区域的图像分割方法主要包括区域生长法和分裂-合并分 割方法。 一般的的图像分割处理可以用EDGE函数， 而特定的图像应用阈值分割、 检测微小结构和四叉树分解比较简单。 对图像分割来说，如果不利用关于图像或所研究目标的先验知识，任何基 于数学工具的解析方法都很难得到很好的效果。因此，在更多的时候，人们倾 向于重新设计一个针对具体问题的新算法来解决所而临的图像分割问题。 这在 只有少量图像样本的时候，利用各种先验知识，设计一个具有针对性的算法进 行图像分割是比较容易的。但是当需要构建一些实用的机器视觉系统时，所面 临的将是具有一定差异性、 数量庞大的图像库， 此时如何很好的利用先验知识， 设计一个对所有待处理图像都适用的分割算法将是一件非常困难的任务。其 次，由于缺乏一个统一的理论作为基础，同时也缺乏对人类视觉系统(human vision system,HVS)机理的深刻认识，构造一种能够成功应用于所有图像的 统一的图像分割算法，到目前为止还是难以实现的。 现实生活中在分割一幅图像时，多是依据经验和直觉去选择方法，通过反 复实践来找到一种最佳的方法。与计算机科学技术的确定性和准确性相比，图 像分割更像是一种艺术行为，有经验的人能比较容易的选用出适当的方法，使 不同的图像都得到最佳的分割效果。但是，当要处理的图像十分庞大时，图像 分割就像是流水线上的一道简单工序，这种艺术行为就显得无能为力了。随着 图像技术和多媒体技术的发展，包括图像、音频和视频等信息的多媒体数据己 经广泛用于Internet和企事业信息系统中，而且越来越多的商业活动、信息表 现和事务交易中都将包括多媒体数据，自然也就包含了大量的图像，基于内容 的图像检索(intent based image retrieval,CBIR)的广泛应用就是一个例子， 这些常

常都是以图像分割作为基础的。 近年来，随着各学科许多新理论和新方法的提出，人们也提出了许多结合 一些特定理论、方法和工具的图像分割技术.由于图像分割技术至今尚无通用 的自身理论，所以每当有新的数学工具或方法提出来，人们就尝试着将其用于 图像分割，因而提出了不少特殊的算法.比如说:基于数学形态学的图像分割 方法基、于模糊理论的图像分割方法 、基于神经网络的图像分割方法、基于 支持向量机的图像分割方法、基于图论的图像分割方法 、 基于免疫算法的图 像分割方法、基于粒度计算理论的图像分割方法。 在传统的图像分割方法基础上，也有了新的改进。比如说：基于改进遗传 算法的分裂合并图像分割算法，对传统图像分割算法进行了改进和扩充,提出 了一种将改进的自适应遗传算法与合并分裂法相结合的图像分割算法； 研究分 裂合并算法的优化方法,并提出相应的并行化方案。修改了图像在区域合并阶 段中原有的最佳合并原则,增加了满足合并条件的相邻区域的匹配率,减少算 法迭代次数。为解决合并阶段的负载不平衡提出了一种新方法;同时针对分裂 阶段的负载不平衡,提出了一种新的分裂合并算法并行方案,并分析了两种并 行方案在负载平衡,通信复杂度及可扩展性的差异。

通信专业资料

2.本课题需要重点研究的关键问题、解决的思路及可行性分析 区域跟踪是寻找具有相似性的像素群， 他们对应某种实体世界的平面或物 体，它的方法是从某一像素出发按照属性一致性原则，这个一致性可以是灰度 级、彩色、组织、梯度或其他特性等逐步地增加像素，既区域增长，对由这些 像素组成的区域使用某种均匀测度函数测试其均匀性，若为真，则继续扩大区 域，知道均匀测度为假。常用的方法有区域分割、区域生长发和区域分裂合并 法。 区域生长和分裂合并是两种典型的串行分割技术， 在分割过程中后续步骤 的处理要根据前面步骤的结果进行判断而确定。 区域增长的基本思想是将具有 相似特性的象素合并起来从而构成区域。 首先为每个需要分割的区域选择一个 或一些种子象素作为生长起点， 然后按一定的生长规则将其周围与之特性相同 或相似的象素合并到种子象素所在的区域中，把这些新象素作为种子继续生 长，直到没有满足条件的象素可以被合并。区域生长算法的关键是初始种子点 的选取和生长规则的确定。算法的优点在于计算简单，对于均匀的连通目标有 很好的分割效果，缺点是需要人为设定种子点，对噪声敏感，可能导致区域出 现空洞。 分裂合并算法的基本思想是从整幅图像开始通过不断分裂合并

来得到 各个区域。分裂合并算法的关键是分裂合并准则的设计，这种算法对复杂图像 的分割效果较好，但算法复杂，计算量大，分裂可能破坏区域的边界。 分裂合并法被认为是一种较为有效实用的分割方法。 其基本思想是先确定 一个分裂合并的准则,即区域特征一致性的测度,当图像中某个区域的特征不 一致时就将该区域分裂成4 个相等的子区域,当相邻的子区域满足一致性特征 时则将它们合成一个大区域,直至所有区域不再满足分裂合并的条件为止.当 分裂到不能再分的情况时，分裂结束，然后它将查找相邻区域有没有相似的特 征，如果有就将相似区域进行合并，最后达到分割的作用。理论上用户必须为 每个区域设定一个种子，种子的选择可以根据图像自方图自动完成。灰度值与 直方图波峰相对应的像素，可以作为种子，有时一个图像区域有多个种子，这 就需要将具有相同灰度统计特性的相邻图像区域合并. 区域分割法有个性质：如果原始图像为正方形N×N,N为2的乘方，那么分 裂所得的所有区域都是正方形M×M,M也是2的乘方。其生成的图像可用四叉树 表示。 可以是先从整幅图像开始通过不断分裂得到各个区域。 实际中常先把图像 分成任意大小不断重叠的区域，然后再合并或分裂这些区域以满足分割的要 求。 R R 11 12 R R 2 R R R R R 14 1 2 3 4 R3 R 4 R 11

R 12

R 13

R 14

(a) 四叉树分裂

(b) 四叉树结构

通信专业资料

最常见的方法四叉树分解法。设R代表整个正方形图像区域图所示，P代表 逻辑谓词。 从最高层开始， 把R连续地分裂成越来越小的1/4的正方形子区域Ri, 并且始终使P(Ri)=TRUE。换句话说，如果P(Ri)=FALSE那么就将图像分为4等分。 如此类推，直到Ri为单个像素。如果仅仅允许使用分裂，最后有可能出现相邻 的两个区域具有相同的性质但并没有合成一体的情况。为解决这个问题，在每 次分裂后允许其后继续分裂或合并。 这里合并只合并那些相邻且合并后组成的 新区域满足逻辑谓词P的区域。 总结前面所述的基本分裂合并算法步骤如下: ①对任一个区域，如果P(Ri)=FALSE就将其分裂成不重叠的4等分; ②对相邻的两个区域Ri和Rj创门也可以大小不同，即不在同一层，如果条 件

P Ri R j TRUE

满足，就将它们合并起来;

③如果进一步的分裂或合并都不可能了，则结束。 小结：分裂合并算法得到的区域比单纯用分裂法得到的区域紧凑，但不能 用四叉树进行区域描述，但这个问题是可以解决的，最直接的办法是延迟合并 过程。先分裂，分裂结束后得到用四叉树表示的区域，最后将邻近的四叉树区 域作合并处理。

通信专业资料

说明： 本报告必须由承担毕业论文(设计)课题任务的学生在毕业论文(设计) 正式开始的第1周周五之前独立撰写完成，并交指导教师审阅。