The k-max distance in graphs and images

In this paper, we propose a new distance called the k-max distance that is intended for graphs and images. The length of a path is defined as the sum of the k maximum arc weights along the path. The distance between two nodes is the length of the shortest path between them. We show that the k-max distance is a metric. The algorithm for computing the k-max distance is presented. Certain positive properties of the k-max distance are shown, namely in the context of measuring the distances for image segmentation. The comparison with the geodesic distance, the max-arc distance, the minimum barrier distance, and the random walker technique is carried out in the segmentation of real-life images.