计算机和互联网的兴起带来的数据膨胀不可避免,照相机等设备的更新换代使得图片的尺寸越来越大,给图像处理带来了越来越大的内存消耗和计算负担。而且,图片尺寸的变大不代表图片中内容数量的增加,而是内容的表达越来越精细。所以,对于一些纯色的区域,拥有成百上千相同颜色的像素,而它们本属于同一物体,在认知上是一致的,却逐像素点的去分析,这就造成的信息的冗余和计算的浪费。所以,是否存在预处理方法,可以提前把图像中相似的像素聚合到一起,作为一个整体去分析?答案是存在的,这样的预处理方法,叫做超像素分割。超像素分割,也称为过分割,目的在于根据像素间的相似性,提前把图像分割成多个区域。从而在后续的图像分析算法中,可以不再以像素为单位,而是以区域为单位提取其特征。这将极大的减少了图像分析算法的存储和计算复杂度,使得超像素分割最近成为一个很热的研究领域。在这篇文章中,我们的重点就是研究性能更好的超像素分割算法。以往的超像素方法主要分成两种:基于图分割的算法和基于梯度的算法。对于基于图分割的算法,它们往往先从图像中获取一个无向图结构,再通过优化基本图分割能量方程,不断的对无向图进行分割,直到生成最后的超像素分割结果为止。不同的算法有不同的图分割能量方程定义,以及不同的优化方法。然而,即使是最简单的能量方程,在求解过程中也是一个NP-hard的问题,并且是在整个全局图像去求解的,需要占用很高的时间复杂度。对于基于梯度的方法,一般先选取一定数量的像素点作为种子点,然后利用其它像素到种子点的距离(差异性)对其它的像素点进行聚类。然而,不管是使用基于颜色和坐标的欧式距离,还是基于路径的测地距离,它们对图像中边缘信息的保护并不理想。而且,往往需要多次相同的迭代计算,才能将超像素分割结果在保护图像边缘上收敛到好的效果,这就导致了基于梯度的算法运行效率十分低下。最近,一种新的距离定义——树距离进入了我们的视野。如果把图像视为一个无向图结构,结点由像素组成,边由像素之间的四领域关系组成,边的权重是邻接像素的颜色差。从无向图当中,我们可以提取一个最小生成树MST,因为大权重的边(往往在边缘部分)在建树过程中会被去除,所以最小生成树结构可以突出图像中的边缘信息。树距离,是定义在MST中的距离,由MST上的两个结点之间相连接的路径决定。由于路径是通过一系列权重最小的边所连接的,所以可以避开权值大的边(已被去除的边),使得定义在MST上的树距离能够更好的描述边缘两测(不同区域)像素之间的差异性,在保边性图像平滑,立体视觉匹配领域得到了广泛的应用。在这篇文章中,我们基于树距离设计了一种能够更好的保护图像中边缘信息的超像素分割算法。该算法包括对图像单层分割的步骤和多层分割的策略。对于单层的超像素分割,首先:一种类似于泊松采点的方法被用于在最小生成树上均匀的采取种子点,作为类中心点;然后:我们使用最近邻的方法,把每一个剩余的像素点基于树距离分类给其最近的类中心点。然而,如果一次产生的分割数量很少,会导致类中心点的数量减少,类中心点的间距变大,使得累积计算的树距离受图像纹理的影响增大。因此,在本文中,我们提出了多层分割的结构,随着层数的增加逐渐减少超像素分割的数量,并在最后一层得到想要的分割数量。在每一层的分割中,我们都会平滑分割后的纹理区域,从而减少树距离受图像纹理区域的影响。随着层数增加,超像素分割的数量成指数下降,所以算法运行时间主要集中在图像的前几层分割中,时间复杂度和图像像素成线性关系。在伯克利图像分割数据库上的实验可以证明,相比于现有的流行算法,我们的超像素分割对图像局部信息有更好的保护能力,同时也拥有更高的时间效率。