Table of Contents
- See Also
- opals::ILineTopology
Aim of module
Provides different line merging and topology correction tools for cleaning line networks derived via automatic edge detection.
General description
Many application require a continuous and topologically correct line network. Automatic line detection procedures (e.g. based on the Canny algorithm, cf. Module EdgeDetect) result in line networks which need post-processing for fulfilling the above aim of topological consistency and completeness. In the context of topographic mapping structure lines denoting surface slope discontinuities or even height jumps are of crucial importance. They can be regarded as the relevant linear features to portrait the landscape. Whereas full automation is hard to achieve for anthropologically shaped landscapes and manual editing might become necessary to achieve full completeness and correctness Module LineTopology aims at minimizing the manual editing effort by providing multiple line merging and topology correction strategies. Figure 1 shows vectorized line segments resulting from Canny edge detection highlighting the basic problems: (a) gaps in the line course and (b) line nodes/junctions
To overcome the above mentioned shortcomings Module LineTopology offers the following strategies (parameter method)
- merge: Line merging based on best-suited-line-connection analysis. In multiple iterations (maxIter) the locally optimal line connection is searched by evaluating multiple criteria like gap distance, horizontal and vertical line straightness, etc.
- longest: This processing modes aims at finding the longest continuous line course based on a bi-directional graph (i.e. Dijkstra algorithm). All lines along the shortest path through the graph are connected.
- clean: The line topology is considered incorrect if any lines intersect between line nodes. Simple and complex intersections at line nodes (V-, T-, and X-junctions) are explicitly tolerated. Inconsistent line networks (in the above sense) are automatically cleaned by opening line violating the topological correctness.
Details: Line merging
Module LineTopology tries to closing small gaps between individual line parts (snapRadius). As the reliability of automatically detected line paths tends to be poorest at the line ending, not only the very endpoints are considered as line connection candidate points but also points at the line end range (revertDist, revertIntervall). For merging two free ending lines the following issues need to be considered:
- Finding the optimum connection line between two adjacent lines
- Finding the locally optimum line progression if more the two lines are involved (e.g. Y- or X-shaped junctions)
- Maintaining topological correctness (Avoiding crossings with other lines of the network when establishing a new line connection).
For merging two adjacent line endings the optimum line connection is found by analysing all candidate connections in the end range of both lines. For each connection the following parameters are checked:
- Length of line connection (smaller gaps are favoured)
- Horizontal and vertical angular difference between line directions at the candidate points:
- Straightness of line ending (rectilinear lines are favoured)
- Distance between line connection candidate point and corresponding line end point (points near the line end are favoured)
- Lateral distance of imaginary line extensions (to avoid merging of misaligned lines)
Each of the above mentioned parameters is scaled as an individual weight between 0 and 1 and the overall weight of a single connection candidate is obtained by multiplying all individual weights. The user can influence the rating by assigning scale factors for the individual weights (parameter group: weight factor options; dist, angle, revertDist, straightness, perpDist). Figure 2 shows an example where a small angular difference was favoured over a small connection-point-to-line-end-point (i.e. revert) distance.
If more than two lines are located within the line connection search area, the optimum line connection pair needs to be determined. As illustrated in Figure 3 a and b different line connections are found depending on the processing sequence. In Module LineTopology the lines are first ordered by descending length. The connecting line found for the longer line 1a in Figure 3a, however, is suboptimal as the connection between line 2 and 3 (Figure 3b) is favourable. Therefore the basic merging strategy outlined above is embedded in a generation based analysis. Starting with line 1b and the found connection candidate (line 3), the candidate selection is extended using line 3. Analysis of the end of line 3 reveals a better connection (to line 2) than was found before for line 1a. In general the described strategy results in globally optimal line connections. However, due to performance considerations the maximum number of search generations can be limited with parameter searchGeneration.
To avoid crossings within the line network introduced by establishing a new line connection, a triangular irregular network (TIN) is constructed from the initial line strings. Each line segment is hereby inserted as a constraint edge in a Delaunay triangulation. By default, a connection candidate is rejected if the connection intersects a contraint edge of the TIN (preventIntersection). Figure 4 shows an example; the green connection line candidate is rejected because it intersects the interjacent line.
Details: Longest path
The general idea of processing method longest is to establish those line connections which results in the longest continuous path. First, all lines are ordered by descending length. Starting with the longest line, all line parts sharing a common end point (line intersections) or even exhibiting a small gap are inserted into two directed graphs (one in forward and one in backward direction). Lines are recursively inserted into the graph if the gap distance (snapRadius) and the line progression direction (-opalsparam{maxAngleDev}) are within the acceptable limits. The search for additional connection candidates is then repeated at the end of each inserted line. Original (i.e. input) line strings are hereby inserted as edges and line connections as nodes into the graph. In case of adjacent lines (i.e. end point of 1st line = start point of 2nd line) an additional dot-shaped node is inserted. Finally the Dijkstra algorithm is used to find the shortest path connecting all nodes. For both graphs (forward and backward direction), the nodes featuring the longest path length are chosen and all lines on these specific paths are connected. Subsequently, all original line parts contributing to the described longest path line merge are removed from the line stack and processing is continued with the next longest line (part). The procedure is repeated until the line stack is empty or no more line connection are found. Figure 5 shows a practical example.
Details: Topology cleaning
With processing method clean double lines or line segments can be automatically removed. Furthermore, erroneous line intersections are automatically detected and broken open by introducing a small gap (omitDist). Please note, intersections of two lines in a common node are accepted and, thus, the lines are not split up in this case.
Typical workflow
The envisaged application of Module LineTopology is to post-process line vector data stemming from automatic edge detection, in particular with Module EdgeDetect and Module Vectorize. In this specific setup small gaps between otherwise continuous line paths, line crossings, and dangling line segments are likely. Whereas there is no one-for-all strategy yielding optimal results for every case, the following approaches have proven to be successful:
- Variant 1:
- 1st call: Method longest with snapRadius=0 to identify and link the most prominent routes
- 2nd call: Method merge with snapRadius>0 to find locally optimal line connections
- Variant 2:
- 1st call: Method merge with snapRadius>0 to first establish the locally optimal line connections
- 2nd call: Method longest with small snapRadius=0 to identify the longest possible continuous routes.
Usage of processing method clean is advisable after manually editing the line vector data to double check and (re)establish topological correctness of the line network.
Parameter description
Remarks: mandatory
Possible values: merge ..... Best candidate merging strategy (iterative) longest ... Merge lines based on recursive longest line strategy (Dijkstra) clean ..... Build topologically correct line networks
There are three different processing methods
Remarks: default=10
Specifies the minimum length of a line after concatenation
Remarks: default=0
Line simplification using the Douglas-Peucker algorithm is applied to the input structure line dataset. For each line only those line vertices are preserved which are necessary to ensure that the diviation of the simplified from the original line is smaller than the specified thresh9old. Please note that line simplification is carried out before line topology processing.
Remarks: optional
If specified, additional equidistant vertices are inserted between the original line nodes. Please note that the optinal line vertex densification is carried out onbly after line topology processing.
Remarks: default=0
Specifies the search radius for line concatenation
Remarks: default=50 15
Requires two values to specify the maximum bend angle between adjacent line parts in horizontal (value(1)) and vertical (value(2)) direction.
Remarks: default=5
Specifies the average distance for end segment computation
Remarks: default=0.6
Specifies the minimum weight to accept the best candidate
Remarks: default=0
The relative weight lead specifies a minimum lead of the best candidate to the second best candidate. Only if the lead is higher than the relWeightLead, the candidate can be accepted. If relWeightLead = 0, no check is performed.
Remarks: default=10
Specifies the maximum number of iterations for serching the locally optimal line connection
Remarks: default=0
Up to which distance from the line end to the inside of the line new optimal connections to other lines can be establised. Possible new end points are computed based on revert interval.
Remarks: default=1
Discretisation interval of computing new possible end points for new optimal connections to other lines. These are computed up to the given revert distance from the line end to the inside of the line.
Remarks: default=1
Number of search generations/iterations to find the optimal line connection. Although the line merge process is a local algorithm, finding connection in mutliple generations helps to find the global optimum of all line connection
Remarks: default=1
Prevent interesection of lines by setting this parameter to 'true'
Remarks: default=1
Remarks: default=1
Remarks: default=1
Remarks: default=1
Remarks: default=0
In case short end line segments emerge after building a clean topological line network (eg. because T-formed line interesection have not been snapped), these end segments will be removed if their length is shorter than given threshold. Setting the parameter to 0 deactivates the end segment omit check.
Examples
The data used in the following example can be found in the $OPALS_ROOT/demo/
directory. As a prerequisite the data of (flyover.laz
) are imported into an OPALS data manager, a DTM grid is calculated, the DTM slope map is calculated and processed with opalsEdgeDetect, and finally the resulting binary raster is vectorized:
A common routine to get a complete and topologically correct line network is to use the following three steps:
The processing in step 1 is done to establish line connections that result in long continuous paths.
In the second step the module tries to close small gaps between different lines depending on the specified snapRadius.
Step 3 again performs the longest path method to identify the longest possible continuous routes. The input DTM shading, all intermediate and final products of the above example are displayed in Figure 5.
References
G. Mandlburger, J. Otepka, C. Briese, W. MÃ¼cke, G. Summer, N. Pfeifer, S. Baltrusch, C. Dorn, H. Brockmann: Automatische Ableitung von Strukturlinien aus 3D-Punktwolken. in: "DreilÃ¤ndertagung der SGPF, DGPF und OVG: LÃ¶sungen fÃ¼r eine Welt im Wandel", T. Kersten (ed.); Publikationen der Deutschen Gesellschaft fÃ¼r Photogrammetrie, Fernerkundung und Geoinformation e.V., Band 25 (2016), ISSN: 0942-2870; 131 - 142.
- Date
- 9.2.2017