A minimum cost approach for segmenting networks of lines

The extraction and interpretation of networks of lines from images yields important organizational information of the network under consideration. In this paper, a one-parameter algorithm for the extraction of line networks from images is presented. The parameter indicates the extracted saliency level from a hierarchical graph. Input for the algorithm is the domain specific knowledge of interconnection points. Graph morphological tools are used to extract the minimum cost graph which best segments the network. We give an extensive error analysis for the general case of line extraction. Our method is shown to be robust against gaps in lines, and against spurious vertices at lines, which we consider as the most prominent source of error in line detection. The method indicates detection confidence, thereby supporting error proof interpretation of the network functionality. The method is demonstrated to be applicable on a broad variety of line networks, including dashed lines. Hence, the proposed method yields a major step towards general line tracking algorithms.