Abstract: Watershed transform is a classical and effective method of image segmentation in mathematical morphology. Nevertheless classical watershed algorithms have stron g 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 al gorithm, 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 algorit hm presented can create watershed lines directly. As the experiments show, the a lgorithm optimizes both running time and relative speedup, and has more strong f lexibility.