Take the 2-minute tour ×
Geographic Information Systems Stack Exchange is a question and answer site for cartographers, geographers and GIS professionals. It's 100% free, no registration required.

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.

Working implementations for open-source environment (PostGIS, shapely, ...) are warmly welcome.

Sample segments : See description below images.

share|improve this question
    
Could you post a snapshot of your data to provide an overview of the segment density and how different they are? –  julien Jan 31 '11 at 12:03
1  
I've posted some illustrations on flickr, see link. –  Adam Matan Jan 31 '11 at 12:41
    
You might try searching for "conflation". –  Kirk Kuykendall Jan 31 '11 at 15:45
add comment

5 Answers

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 here. You may also have a look at the JCS Conflation Suite.

share|improve this answer
1  
Does this consider segment orientation too? Maybe in some extended version? –  underdark Jan 31 '11 at 12:57
    
Segment orientation is considered implicitly: segments with very different orientations have a big Hausdorff distance. An additional rule may be added to ensure 2 matched segments have close orientations. –  julien Jan 31 '11 at 13:03
2  
Hausdorff distance is also in PostGIS, from GEOS, so it is the same algorithm as JTS –  Nicklas Avén Jan 31 '11 at 13:14
    
Excellent news ! –  julien Mar 10 '11 at 15:14
add comment

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.

share|improve this answer
    
great answer as usual. –  George Feb 1 '11 at 15:10
add comment

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
share|improve this answer
add comment

Here comes an idea

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.

HTH Nicklas

share|improve this answer
1  
+1 This is very similar to the approach I finally used (will post an answer soon). –  Adam Matan Feb 1 '11 at 12:22
add comment

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.

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

Cheers!

share|improve this answer
    
+1 This is a nice approach; building the quadtree makes it computationally superior. But care is needed in the details: when determining segment proximity or similarity (instead of intersection), you need to account for the fact that your data structure does not provide a unique representation of a segment: the segment originating at x, in direction v, of length t is equally well the segment originating at x + t v in direction -v of length t. –  whuber Feb 1 '11 at 15:38
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.