A nearest neighbor graph based watershed algorithm

A novel watershed transformation defined on the nearest neighbor graph (NNG) is proposed. The NNG is considered as a relief map and some geographic features are defined. The proposed algorithm is not only defined for image segmentation but also utilized to refine the partition result. An image is transformed into the NNG and then partitioned by discovering the defined geographic features in the first step. The initial partition result is transformed into the NNG again and then recursively distilled by the proposed algorithm. In the final result, the proposed algorithm is effective for capturing most of objects, even though they are textured regions that are perceptually homogeneous.