Automatic extraction of ridge and valley axes using the profile recognition and polygon-breaking algorithm

For most interpreters working on two-dimensional data or maps, a line-drawing process to depict linear and curvilinear features is often needed. One of the main difficulties in simulating human insight in such a process by computer is that the human eye is able to consider data trends within a wide range on the map. A program based on the profile recognition and polygon-breaking algorithms is introduced in this paper to extract automatically ridge and valley axes. The two algorithms are capable of simulating human performance in the line-drawing process over a range of conditions. The program starts from a profile recognition process which takes all the points close to the possible axes as targets and connects them as a belt of closed polygons. Then, a polygon-breaking process resolves the belt into a continuous line, and a smoothing process further makes the line as smooth as one depicted manually. The program has been applied to the topography of Taiwan and has been successful in extracting ridge and valley systems. It also has shown some potential in solving the problems of line drawing for other purposes and for other kinds of data. (C) 1998 Elsevier Science Ltd. All rights reserved.