NEW PROSPECTS IN-LINE DETECTION BY DYNAMIC-PROGRAMMING

The detection of lines in satellite images has drawn a lot of attentio n within the last 15 years. Problems of resolution, noise, and image u nderstanding are involved, and one of the best methods developed so fa r is the F algorithm of Fischler, which achieves robustness, rightnes s, and rapidity. Like other methods of dynamic programming, it consist s of defining a cost which depends on local information; then a summat ion-minimization process in the image is performed. We present herein a mathematical formalization of the F algorithm, which allows us to e xtend the cost both to cliques of more than two points (to deal with t he contrast), and to neighborhoods of size larger than one (to take in to account the curvature). Thus, all the needed information (contrast, grey-level, curvature) is synthesized in a unique cost function defin ed on the digital original image. This cost is used to detect roads an d valleys in satellite images (SPOT).