A minimum cost approach for segmenting networks of lines

The extraction and interpretation of networks of lines from images yields i mportant organizational information of the network under consideration. In this paper, a one-parameter algorithm for the extraction of line networks f rom images is presented. The parameter indicates the extracted saliency lev el from a hierarchical graph. Input for the algorithm is the domain specifi c knowledge of interconnection points. Graph morphological tools are used t o 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 spuri ous vertices at lines, which we consider as the most prominent source of er ror in line detection. The method indicates detection confidence, thereby s upporting error proof interpretation of the network functionality. The meth od is demonstrated to be applicable on a broad variety of line networks, in cluding dashed lines. Hence, the proposed method yields a major step toward s general line tracking algorithms.