图像分割是一种底层的图像处理技术,它根据特定的特征将图像分离为连通的有意义区域,可以广泛应用在图像及视频的高级处理任务中。图像分割技术经过几十年的发展,形成了众多的方法、繁杂的类别和海量的文献,但是与人眼视觉特征相一致的全局分割问题一直得不到解决。在这些方法中,基于图论最小生成树的方法利用区域比较准则和最小生成树算法分割图像,具有获取全局特征的能力,计算速度快,是一种可以作为应用研究的分割方法之一。本文的工作主要基于此算法。为了提高此算法应用的可能性,我们需要更改算法及优化程序,提高其全局分割效果和计算速度。本文在分析基于最小生成树分割算法概念、原理、数据结构和实现方式的基础上,发现其运算瓶颈为边的数目,也就是图中实际计算的节点数目。因此本文利用图像局部特征相似的特性,使用N×N, N=1,2,3大小的自适应像素块映射为单个计算节点,大大降低了实际计算的节点和边的数目,从而降低了核心算法的计算复杂度。为了适应块结构,本文更改了邻域系统,提出了基本连接和超连接的层次。基本连接保证了相邻区域的邻近性,而超连接提供了区域之间的连续性。这种两层的连接方式提高了算法获取全局特征的能力,获得了既不过分割也不欠分割的效果,接近图像对象的数目,减少了原算法分割区域的数目。另外,为了分析基于最小生成树算法的结构,本文将其分为三个阶段:前处理、核心算法和后处理。原算法大部分的计算负担集中在核心算法上,算法结构极不均衡。因此,本文在保证三个阶段接口不变的基础上,将构造图的过程从核心算法阶段转移到前处理阶段,均衡了计算量,增加了算法并行处理的能力。图像进行分层分析和表达由来已久,具有在不同分辨率下表现图像内容的优势。金字塔图像分割方法是一种分层的分析方法,其突出优点是可以累积局部特征,从而表现全局特征。金字塔分为规则金字塔和非规则金字塔,后者可以克服前者的刚性特点,与图像内容相适应,成为金字塔图像分割算法的主要实现形式。人们提出了不同的非规则金字塔数据结构和缩减方法,但是大多数比较复杂。本文利用基于最小生成树分割算法计算速度快、结构简单、有效进行区域比较的优势,将其作为缩减核应用到非规则金字塔结构中,形成一种快速有效的块嵌入非规则金字塔分割算法。为了将金字塔高度控制在合理范围内,提高缩减因子,本文在第零层使用块结构加快其收敛速度,并提出了一种快速的邻近区域搜索方法以有效地构造高一层的边。试验结果表明,新的算法具有良好的分割效果和计算速度。块嵌入非规则金字塔分割算法使用区域的特征平均值代替父节点的特征值,降低了噪声对算法的影响,从而无需额外的去噪方法,消除了原算法的高斯滤波参数。本文使用权重的最大最小差值代替原算法抑制小区域的参数,可以在每层上自动适应图像的特征。另外,在构造块结构的过程中,本文使用图像的标准差作为比较准则,从而无需输入块构造参数。金字塔累积局部特征的本质可以去除合并小区域的步骤,从而消除了最小区域参数。本文的这些工作使块嵌入非规则金字塔分割算法成为一个参数独立的自动分割算法,有利于实际应用。良好的分割效果与快速计算速度使分割算法进行实时应用成为可能。本文在高清数字电视解码器片上系统平台软硬件工作的基础上,分析了基于MIPS处理器的嵌入式平台在时间和空间上的运算资源优化,尝试将基于最小生成树的图像分割算法进行嵌入式移植。在回顾算法改进的基础上,本文对程序代码进行运行时间和空间上的优化,包括运行时间剖析、缓存优化、调用关系优化和动态内存分析等,以软件IP的形式移植到基于MIPS开发平台Malta板上。分割程序建立在一个嵌入式软件系统上,包括启动程序、Linux操作系统、API和库等,以主机控制目标板的方式运行,通过网络远程读写图像文件。