Abstract
Filling gaps in contour lines after scanning and segmentation is a significant challenge in GIS data preparation. This paper proposes a novel method for the automatic or semi-automatic reconstruction of broken contour lines in binary images. Key innovations include multiple incremental back-tracing for stable direction estimation, a gradient-based angle constraint mechanism, a weighted matching metric combining Euclidean distance and deviation angle, and bidirectional parabola control. Experimental results demonstrate that this method achieves higher accuracy and completeness compared to existing benchmarks.
Introduction
Topographic maps are vital for Geographic Information Systems (GIS), yet much historical data remains in paper format. Converting these to digital vector data involves scanning and segmentation, which frequently results in broken contour lines. These interruptions occur due to text labels, map symbols, or noise from the scanning process. Existing automated tools often fail to bridge these gaps correctly, leading to false connections or missed complex geometries like sharp turns. This paper introduces a robust pipeline to automate this reconstruction with high precision.
Proposed Methodology
The proposed method moves beyond simple distance-based heuristics by incorporating geometric logic and hierarchical processing.
Multiple Incremental Back-tracing
To accurately reconnect a broken line, the algorithm must determine its "true" direction. Simple local pixel analysis is often susceptible to noise. The authors employ a multiple incremental back-tracing technique. By analyzing the line at various lengths from the endpoint and calculating a weighted average, the system identifies a stable directional heading that represents the line's actual trajectory rather than local pixel jitter.
Max Constraint Angle Control (Gradient Ranks)
Rather than applying a single rigid threshold for line curvature, the method uses "gradient ranks." It adopts an "easy-to-hard" strategy, first connecting gaps with minimal deviation angles. In subsequent passes, the angular constraints are gradually relaxed. This prevents the algorithm from making erroneous high-angle connections early in the process that could interfere with more certain reconstructions later.
Weighted Matching Metric
To select the optimal endpoint pair for connection, a matching score ($D_i$) is calculated. This metric combines the weighted Euclidean distance between points and the deviation angle between their respective headings. This ensures that the chosen connection is both geographically proximal and geometrically consistent with the flow of the contour lines.
Bidirectional Parabola Control
Standard algorithms often struggle with "hairpin" curves or parabolas where the line makes an acute turn. The authors implemented specific direction code logic to identify these parabolic shapes, allowing the system to bridge gaps even when the endpoints point toward each other at sharp angles.
Experimental Results
The method was evaluated against the well-known Samet’s method using three complex map samples characterized by high curve density and overlapping features.
- Accuracy: The proposed method achieved 100% accuracy across all test samples, successfully avoiding the "false connections" that plagued the benchmark (which dropped to 93% accuracy in some tests).
- Completeness: The system filled 97% to 99% of all gaps. In one sample, it successfully reconstructed 100 out of 101 gaps, significantly outperforming the benchmark's 91.
- Qualitative Performance: Visual inspection confirmed that the new method handles steep parabolas and large gaps without creating illegal line intersections.
Conclusion
The proposed reconstruction method offers a significant improvement in the automation of topographic map digitization. By prioritizing geometric stability and using a hierarchical constraint model, it achieves near-perfect accuracy and high completeness. While more computationally intensive than simpler methods, its ability to reduce manual correction time makes it a valuable tool for large-scale GIS data production. Future work will focus on optimizing the algorithm's efficiency for high-resolution datasets.
Summary updated