一种优化的并行流域分割算法  

An Improved Parallel Watershed Algorithm for Image Segmentation

作　　者：周海芳[1] 杨学军[1] 刘衡竹[1] 唐宇[2] 

机构地区：[1]国防科学技术大学计算机学院,长沙410073 [2]国防科学技术大学电子科学与工程学院,长沙410073

出　　处：《计算机研究与发展》2005年第4期640-646,共7页Journal of Computer Research and Development

基　　金：国家"八六三"高技术研究发展计划基金项目(2002AA1Z2101);教育部财政专项基金项目(CG2003GA001

摘　　要：流域变换(又称分水岭变换)是数字形态学中用于图像分割的一种有效的方法.但是经典的流域算法具有很强的递归性质,直接并行化效率很低.首先,分析比较了已有并行算法的优缺点,然后从基于距离的流域变换定义入手,提出了一种优化的并行流域分割算法.该算法给出了新的区域关系图的定义,并利用了基于下降距离的方法的局部性;通过引入伪种子点使得各子域之间区域生长和合并的过程相对独立,基本消除了重复泛洪带来的开销;同时可直接生成分水岭.实验表明,提出的算法在执行时间和可扩展性两方面都得到了优化,并拓展了算法的适应性.Watershed transform is a classical and effective method of image segmentation in mathematical morphology. Nevertheless classical watershed algorithms have strong recursive nature, so straightforward parallel ones have a very low efficiency. Firstly, the advantages and disadvantages of some existing parallel algorithms are analyzed. Then, an improved parallel watershed algorithm is presented based on the definition of watershed transform with condition of distance. For this algorithm, a new definition of components graph is described and good locality of algorithm is developed in use of lower distance. Through introducing pseudo-seed pixels, the process of region growing and region merging is separated, and for this reason the cost of re-flooding is eliminated. At the same time, the algorithm presented can create watershed lines directly. As the experiments show, the algorithm optimizes both running time and relative speedup, and has more strong flexibility.

关 键 词：流域变换 图像分割 区域关系图 伪种子点 并行 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构] TP391.41[自动化与计算机技术—计算机科学与技术]