Current Issue Cover

邹昆,翁宏章,李文生(电子科技大学中山学院计算机学院, 中山 528402;电子科技大学计算机科学与工程学院, 成都 611731)

摘 要
目的 基于数字高程模型(DEM)的地形山脊线和山谷线提取对地形模型简化、基于样本的地形合成和地形地貌研究有重要意义,针对许多传统算法无法对所提取特征线的显著度进行方便准确的控制,以及不支持环形特征线提取的问题,提出一种新的显著度可控的DEM地形特征线提取算法。方法 首先利用全局断面扫描算法提取特征点并计算各特征点的显著度,然后根据特征点的特征方向进行特征延伸以增强特征连通性,接着采用改进的Hilditch细线化算法对特征点集合进行细线化处理,之后为相邻特征点添加特征边,构成特征图,利用环路检测与破环算法检测特征图中的环路,并破除冗余小环路,最后根据分支显著度的相似度和分支方向一致性进行特征图分解,计算分解得到特征线的显著度并筛选得到最终特征线。结果 使用真实DEM数据提取最显著的若干条特征线,与现有的基于特征显著度的地形特征线提取算法进行对比,本文算法对特征图的分解能够更准确地提取主干特征线,而基于显著度的特征线筛选控制也更加准确合理。对提出的环路检测与破环算法进行实验验证,该算法能保留大的山脊线环路,破除小的冗余环路。结论 实验结果表明,本文算法能有效实现显著度可控的山脊线和山谷线自动提取,提取结果与人眼观察结果基本一致,同时能够支持含有环形特征的地形。
Saliency-controllable topographic feature line extraction from DEM

Zou Kun,Weng Hongzhang,Li Wensheng(School of Computer Engineering,Zhongshan Institute,University of Electronic Science and Technology of China,Zhongshan 528402,China;School of Computer Science and Engineering,University of Electronic Science and Technology of China,Chengdu 611731,China)

Objective 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.Method 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.Result 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.Conclusion 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.