A probabilistic method for extracting chains of collinear segments

We present a probabilistic method for linking together edge segments into collinear chains. From simple assumptions concerning the underlying probability densities of segment lengths, positions, and orientations, a probability density is determined for a measure of the deviation of a junction from perfect collinearity. For each pair of segments passing a battery of preliminary screening tests, we compute the probability that its deviation would be smaller than the one observed if the two lines were generated at random. The junctions that pass the tests and for which this probability is sufficiently small define a connectivity matrix of collinear segments. Chains of collinear segments are extracted from the connected components of this matrix and validated by computing their global probabilities of nonaccidental occurrence. The procedure is repeated iteratively with the new chains included in the segment data base, which allows bridging progressively larger gaps, until no more chains can be formed. The global probability of nonaccidental occurrence of each hypothesized chain is computed by taking into account the mutual dependencies of junction probabilities; a power simplification is presented that reduces from exponential to linear the complexity of taking such dependencies into account. We further show that the bayesian dependency theory used for computing junction probabilities in a chain naturally leads to the Gestalt principle of regularity. The procedure is demonstrated on real-world images. (C) 1999 Academic Press.