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

An Improved Parallel Watershed Algorithm for Image Segmentation

流域变换(又称分水岭变换)是数字形态学中用于图像分割的一种有效的方法.但是经典的流域算法具有很强的递归性质,直接并行化效率很低.首先,分析比较了已有并行算法的优缺点,然后从基于距离的流域变换定义入手,提出了一种优化的并行流域分割算法.该算法给出了新的区域关系图的定义,并利用了基于下降距离的方法的局部性;通过引入伪种子点使得各子域之间区域生长和合并的过程相对独立,基本消除了重复泛洪带来的开销;同时可直接生成分水岭.实验表明,提出的算法在执行时间和可扩展性两方面都得到了优化,并拓展了算法的适应性.

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.