Ridge lines and valley lines are the most important terrain feature lines

which delineate skeleton structures of terrain.The automatic extraction of them from digital elevation models (DEM) is of great significance in applications such as relief automated generalization

hydrological analysis and geographical information system

and can also provide matching features for terrain model simplification and sample-based terrain synthesis.For most traditional algorithms

feature lines can only be filtered based on their length by eliminating endmost short branches

and it is difficult to accurately control the saliency of extracted feature lines.Because feature lines are usually modeled as trees

and break-all-loop algorithms such as polygon breaking and minimum spanning tree are commonly used

ringlike features such as craters cannot be correctly extracted without notches.Therefore

a new algorithm for saliency-controllable topographic feature line extraction from DEM was proposed based on feature saliency. Our algorithm consisted of five steps.First

feature points were extracted by the global profile scan algorithm which can better eliminate noise and pseudo feature points

and feature saliency of each feature point was calculated according to its height

ambilateral height drops and slopes.Second

feature connectivity was enhanced by feature extension based on feature directions of feature points.Third

feature point set was thinned to be one-pixel-wide with an improved Hilditch algorithm

in which a neighborhood scan process was added when finding a point that can be deleted

and among all points satisfying remove conditions in the neighborhood

the one with the smallest feature saliency was chosen to be deleted.In such a way

thinning result had almost nothing to do with the global scanning sequence

and salient feature points could be preserved.Fourth

feature graph was constructed by taking feature points as nodes and adding edges to all neighboring ones.It was highly likely that many loops existed in the graph

and most of them were redundant small ones.In order to support extraction of ringlike features

we broke small loops while preserving big ones.A loop detecting and breaking algorithm was devised to handle all kinds of loops

such as nested loops

loops containing common sides and loops with no interior points.In the end

feature graph was decomposed into branches and feature lines were constructed by assembling consecutive branches

requiring that all branches inside a feature line had similar feature saliencies and directions of neighboring branches were consistent.Then

feature saliency of each feature line was calculated

based on which all feature lines were sorted in descending order.And by selecting a certain number of headmost feature lines in the sorted list

it was simple to implement feature saliency-based filtering. To validate the effectiveness of the proposed algorithm

a comparison with the existing feature saliency-based topographic feature line extraction algorithm was made by extracting some most significant feature lines from real DEM data.The proposed algorithm can extract feature line trunks more accurately and can effectively avoid overextension of trunks

which is attributed to the new feature graph decomposition strategy.In terms of saliency-based control

by simultaneously considering feature line length

average and maximum feature saliency of all feature points on the line

the new formula of feature saliency calculation for feature lines is more reasonable

and so the proposed algorithm can provide more accurate control over the saliency of extracted feature lines.To verify the proposed loop detecting and breaking algorithm

intermediate results before and after loop breaking were shown

and a synthesized DEM with a big crater was tested.Results show that the proposed algorithm can well preserve the large ridge line loop while breaking all small redundant ones.Because differences in thinning results for real DEM data are at pixel level and can hardly be perceived by eye

so a comparison was made based on a man-made example of 2-pixel-wide feature point band to exemplify the proposed improved thinning algorithm.And the improved algorithm deletes feature points with smaller feature saliency which means true features are more likely to be preserved. The proposed algorithm can effectively extract ridge and valley lines with controllable saliency

which are consistent with human eye observation

and can support terrains with ringlike features.The main contributions include three points.First

by exploiting the proposed feature graph decomposition algorithm and applying the devised formula to calculate feature saliency of feature lines

decomposition results become more reasonable

and more precise control over the feature saliency of extracted feature lines can be provided.Second

a novel algorithm was proposed to detect all redundant small loops while preserving large ones

and it can handle all complex loop cases.At last

a further improvement upon the improved Hilditch algorithm was made based on feature saliency

so that more salient feature points will be retained and the resulting skeleton lines may be more accurate for feature point bands of 2 or 3 pixel wide.However

there are several shortcomings of the proposed algorithm.First

there are many parameters which are set mainly based on experience.Especially

the branch feature saliency dissimilarity threshold used in feature graph decomposition should be carefully tuned

which has a great influence on experimental results.Second

compared with some break-all-loop algorithms such as minimum spanning tree

the loop detecting and breaking algorithm is inefficient and it becomes a bottleneck of the whole algorithm.Future work includes improving the efficiency of the loop detecting and breaking algorithm as well as parameter optimization and automatic parameter setting.