[优秀论文]基于图论的图像分割及其嵌入式应用研究.pdf

上海交通大学
博士学位论文
基于图论的图像分割及其嵌入式应用研究
姓名:谭志明
申请学位级别:博士
专业:信号与信息处理
指导教师:郑世宝
20070701
摘要基于图论的图像分割及其嵌入式应用研究图像分割是一种底层的图像处理技术,它根据特定的特征将图像分离为连通的有意义区域,可以广泛应用在图像及视频的高级处理任务中。图像分割技术经过几十年的发展,形成了众多的方法、繁杂的类别和海量的文献,但是与人眼视觉特征相一致的全局分割问题一直得不到解决。在这些方法中,基于图论最小生成树的方法利用区域比较准则和最小生成树算法分割图像,具有获取全局特征的能力,计算速度快,是一种可以作为应用研究的分割方法之一。本文的工作主要基于此算法。为了提高此算法应用的可能性,我们需要更改算法及优化程序,提高其全局分割效果和计算速度。本文在分析基于最小生成树分割算法概念、原理、数据结构和实现方式的基础上,发现其运算瓶颈为边的数目,也就是图中实际计算的节点数日。因此本文利用图像局部特征相似的特性,使用琋,笮〉淖允视ο袼乜映射为单个计算肖点,大大降低了实际计算的说愫捅叩氖浚佣档土撕诵乃法的计算复杂度。为了适应块结构,本文更改了邻域系统,提出了基本连接和超连接的层次。基本连接保证了相邻区域的邻近性,而超连接提供了区域之间的连续性。这种两层的连接方式提高了算法获取全局特征的能力,获得了既不过分割也不欠分割的效果,接近图像对象的数目,减少了原算法分割区域的数目。另外,为了分析基于最小生成树算法的结构,本文将其分为三个阶段:前处理、核心算法和后处理。原算法大部分的计算负担集中在核心算法上,算法结构极不均衡。因此,本文在保证三个阶段接口不变的基础上,将构造图的过程从核心算法阶段转移到前处理阶段,均衡了计算量,增加了算法并行处理的能力。图像进行分层分析和表达由来已久,具有在不同分辨牢下表现图像内容的优势。金字塔图像分割方法是一种分层的分析方法,其突出优点是可以累积局部特征,从
而表现全局特征。金宁塔分为规则金宁塔和非规则金字塔,后者可以克服前者的刚性特点,与图像内容相适应,成为金字塔图像分割算法的主要实现形式。人们提出了不同的非规则金字塔数据结构和缩减方法,但足大多数比较复杂。本文利用基于最小生成树分割算法计算速度快、结构简单、有效进行区域比较的优势,将其作为缩减核应用到非规则金字塔结构中,形成一种快速有效的块嵌入非规则金字塔分割算法。为了将金字塔高度控制在合理范围内,提高缩减因子,本文在第零层使用块结构加快其收敛速度,并提出了一种快速的邻近区域搜索方法以有效地构造高一层的边。试验结果表明,新的算法具有良好的分割效果和计算速度。块嵌入非规则金字塔分割算法使用区域的特征平均值代替父节点的特征值,降低了噪声对算法的影响,从而无需额外的去噪方法,消除了原算法的高斯滤波参数。本文使用权重的最大最小差值代替原算法抑制小区域的参数,可以在每层上自动适应图像的特征。另外,在构造块结构的过程中,本文使用图像的标准差作为比较准则,从而无需输入块构造参数。金字塔累积局部特征的本质可以去除合并小区域的步骤,从而消除了最小区域参数。本文的这些工作使块嵌入非规则金字塔分割算法成为一个参数独立的自动分割算法,有利于实际应用。良好的分割效果与快速计算速度使分割算法进行实时应用成为可能。本文在高清数字电视解码器片上系统平台软硬件工作的基础上,分析了基于处理器的嵌入式平台在时间和空间上的运算资源优化,尝试将基于最小生成树的图像分割算法进行嵌入式移植。在回顾算法改进的基础上,本文对程序代码进行运行时问和空间上的优化,包括运行时问剖析、缓存优化、调用关系优化和动态内存分析等,以软件的形式移植到基于开发平台迳稀7指畛绦蚪⒃谝桓銮度胧软件系统上,包括启动程序、僮飨低场和库等,以主机控制目标板的方式运行,通过网络远程读写图像文件。关键词:图像分割,图论,最小生成树,金字塔分割,非规则金字塔,缩减核,优化,嵌入式平台,软件
.甌.—琋,甌琧琾,甊瓵瑃瑃..甇篴,,,,.:
舢舳咖鷏甧咖佗甈瑆甌嘶遰甌..甒埘錓鷄篶甅·觚璯:,,甌甌觩·,,琣甌,痶甀瑃。瑃。..
,,.,篿甒琣./猘甌,.,,,琧,,,.,
术语中英文对照表按级合并按点合并边边图标签保持结构的收缩—包含关系饱和度保留节点比较谓词不用人为干预的彩色图像采样率残差图超连接垂直关系存储系统底层比例切割差别
固件归一化归一化切割独立的连续区域独立节点端点对偶边收缩对偶对对偶面缩减甪对偶图对偶图收缩多重边多项式时间方向线非规则金字塔非连续性分层图感兴趣目标感知组合高级高清晰度电视格式塔心理学工作层关联矩阵非保留—,,
规则金字塔函数头函数尾合并一寻找—缓存灰度图像汇集汇节点加