Algorithms for matching segments [closed]

Question

What are the best algorithms to match segments?

I'm trying to match corresponding segments from two map sources, one less accurate but with segment names, and one more accurate without segment names. I want to semi-automatically apply the segment names to the more accurate map.

The requested algorithm has quite a vague description because a "match" is not well defined, and many factors (orientation, relative length, distance) might have different weight in different scenarios; However, I'm looking for a basic knowledge about the general approaches for handling this problem.

I seek working implementations for an open-source environment (PostGIS, shapely, etc).

Sample segments : See description below images.

Answer 1

The Hausdorff distance may be used: matching segments could be 'close' segments according to this distance. It is quite simple to compute on segments.

A free java implementation is available in JTS - see JTS Distance Package. You may also have a look at the JCS Conflation Suite (now abandoned, copy of sources e.g. at https://github.com/oschrenk/jcs).

Answer 2

I don't know what would be the "best," because that will depend on the particulars of your segments.

A generally good approach is to hash the segments into crucial geometric information. This would include, at a minimum, location of the center (x,y), orientation (0 to 180 degrees), and length. With appropriate weights applied, and some finessing of the orientation (because 180 "wraps around" back to 0), you could then apply almost any statistical clustering algorithm to the collection of all segments. (K-means would be a good option, but most hierarchical methods ought to work well. Such cluster analyses tend to be fast and easy to apply.) Ideally, the segments will occur in pairs (or singletons for unmatched segments) and the rest is easy.

One way to deal with the orientation issue is to make a copy of the labeled segments. Add 180 degrees to the orientation of the first copy, if it is less than 90, and otherwise subtract 180 degrees from the orientation. This enlarges your dataset (obviously) but otherwise does not change the algorithm in any way.

Weights are needed because differences of coordinates, lengths, and orientations can mean quite different things concerning the similarities of their corresponding segments. In many applications differences among segments arise from differences in locations of their endpoints. As a rough approximation, we can expect typical variation in segment lengths to be about the same as typical variation between their endpoints. Therefore, the weights associated with x, y, and length should be about the same. The tricky part is weighting orientation, because orientation cannot be equated with distance and, even worse, short segments would be more likely to be mis-oriented than long segments. Consider a trial-and-error method that equates a few degrees of misorientation to the size of a typical gap between segments and then adjusts that until the procedure seems to work well. For guidance, let L be a typical segment length. A change of orientation by a smallish angle t degrees will sweep out a distance of approximately L/2 * t / 60 (the 60 approximates the number of degrees in one radian), which is L/120 times t. That suggests starting with unit weights for x, y, and length and a weight of L/120 for the orientation.

In summary, this suggestion is:

1. Make copies of the labeled segments (as described in the paragraph on finessing the orientation).

2. Convert each segment into the quadruple (x, y, length, L/120 * orientation) where L is a typical segment length.

3. Perform a cluster analysis of the quadruples. Use a good statistical package (R is free).

4. Use the cluster analysis output as a lookup table to associate labeled segments with nearby unlabeled segments.

Answer 3

I worked on a project with a similar requirement about 5 years ago. It involved combining coordinates from street centerlines (with relatively high coordinate precision) with Highway Performance Monitoring System (HPMS) traffic network links.

At the time the FHWA didn't provide any tools to do this sort of thing. That may have changed, you might want to check. Even if you aren't working with highway data, the tools might still be relevant.

I wrote it with ArcGIS, but the algorithm should work in opensource, as long as it provides tracing capabilities similar to ISegmentGraph:

// features is a collection of features with higher geometry
// Links are a collection features with attributes but low res geometry
For each Link in lowResFeatureclass
    point startPoint = SnapToClosestPoint(Link.StartPoint, hiResfeatures);
    if(startPoint == null)
       continue;
    point endPoint = SnapToClosest(Link.EndPoint, hiResfeatures);
    if(endPoint == null)
       continue;
    polyline trace = Trace(hiResfeatures,startPoint,endPoint);
    if(polyline != null)
    {
        // write out a link with high precision polyline
        Write(Link,polyline);
    }
Next Link

Answer 4

If you tear apart one of the linestrings to compare and test if the vertexpoints is within some distance from the other linestring to compare you can control the test in many ways.

those examples work in PostGIS (who could guess)

First, if we say that there is a match if all vertex points in a linestring in table_1 is 0.5 meters (map units) or closer to a linestring in table_2:

SELECT a.id, b.id FROM
(SELECT ST_NPoints(the_geom) as num_of_points,
(ST_Dumppoints(the_geom)).geom as p, id FROM table_1) a 
INNER JOIN 
table_2 b 
ON ST_DWithin(a.p, b.the_geom, 0.5) GROUP BY a.id, b.id
HAVING COUNT(*)=num_of_points;

Then we can say that there is a match if more than 60% of the vertex_points in a linestring in table_1 is within distance of a linestring in table_2

SELECT a.id, b.id FROM
(SELECT ST_NPoints(the_geom) as num_of_points, 
(ST_Dumppoints(the_geom)).geom as p, id FROM table_1) a 
INNER JOIN 
table_2 b 
ON ST_DWithin(a.p, b.the_geom, 0.5) GROUP BY a.id, b.id
HAVING COUNT(b.id)/num_of_points::float > 0.6

Or we can accept that one point is not in range:

SELECT a.id, b.id FROM
(SELECT ST_NPoints(the_geom) as num_of_points, 
(ST_Dumppoints(the_geom)).geom as p, id FROM table_1) a 
INNER JOIN 
table_2 b 
ON ST_DWithin(a.p, b.the_geom, 0.5) GROUP BY a.id, b.id
HAVING COUNT(b.id)-num_of_points <= 1;

You will also have to run the query with table_1 and table_2 in reversed roles.

I don't know how fast it will be. ST_Dumppoints is currently a sql-function in PostGIS and not a C-function which makes it slower than it should have to be. But I think it will be quite fast anyway.

Spatial indexes will help a lot for ST_Dwithin to effective.

Answer 5

I've written code to handle sloppy line segment matching (and overlap them) in Boundary Generator. I wrote up the (fairly elementary) math behind it here: http://blog.shoutis.org/2008/10/inside-boundary-generator-computational.html. The code is open source & linked from that blog post.

The code follows a really simple approach:

• A segment-segment test that will tell you whether two line segments overlap within given angle and distance tolerances, and the amount of overlap.
• A quick'n'dirty spatial index that eliminates the need to test every line segment in the dataset against all other line segments in the dataset.

The main advantage of this approach is you get nicely precise knobs for valid angle, distances, and overlap length; on the downside, it isn't a way of generally measuring the similarity of two line segments so it's much harder to e.g. do statistical clustering to determine likely matches -- you're stuck with the precise knobs.

I'm guessing that with sufficient SQL chops you could cram the segment-segment test into a WHERE clause.

Answer 6

I've implemented a rough prototype for map matching here, which is relative easy to use. It is based on the open source routing engine and written in Java. The used algorithm is described here.