Algorithm To Quantify The Difference Of Line Segment Paths

Question

Say I have two line segment paths, such as a subset of the examples below. How can I quantify the difference between them?

1. |__
2. \_
3. __
4. /\
5. \/
6. |
7. _

The two paths may have a different number of segments, and the length of each segment and the angle between them is variable.

I was thinking it would be good to establish a coordinate system and define the segments as nodes and edges. The difference could perhaps be quantified by the operations needed to transform one into the other, similar to the Levenshtein distance algorithm. Unfortunately the operation space is huge. Any ideas? Thanks!

Answer 1

I'll go a bit further than what @awoodland pointed out: how you quantify it depends entirely on why you want to quantify the difference.

Are you looking to come up with a unique (at least, likely to be unique) number like a hash code for a line segment path? Or are you trying to quantify line segment paths to say, "this path is more complex (or longer, or has more acute angles) than that path"?

If you want to create a hash code, I would suggest creating two 32-bit CRCs (or something similar): one for the segment lengths and one for the angles. Once you've computed those CRCs, put them together in a 64-bit value with the angles in the high 32 bits and the lengths in the low 32 bits. Depending on the number of segments, perhaps a single CRC value would do: for each segment, add the length and then the angle between it and the next segment.

Note that the above is likely to give you a unique number for each path, but not guaranteed to.

If you want to quantify the complexity of the line segment path ... I don't have a lot of ideas.

Answer 2

You could draw them into fixed size images and then use Euclidean distance to compare the images.

Or you could measure the total length and sum the absolute value of the angles (as well as the signed angles perhaps) as a measure. Something based on this would have the nice property of being invariant to the orientation of the shape (if you wanted that!).

How you quantify it somewhat depends on why you want to quantify the difference between them.

Answer 3

You can look at this paper :

http://www.vision.ee.ethz.ch/~calvin/Publications/ferrari07pami.pdf

In this paper we are using kAS (a generalization of segments pairs : you can have multiple segments connected to each others) for object detection. We introduce a descriptor for these sets of segments that you can use to describe your pairs.

Our descriptor is not rotation invariant so it might not suit you.

Answer 4

If you use operations:

• Add corner and segment
• Remove corner and segment
• Stretch segment (with weight of the difference)
• Bend corner (with weight of the difference)

You would still be able to use Levenshtein distance while still being in n^2 time.

Encode the segments as following [segment, corner]*. So it would be:

[length, rotation] [length, rotation]...

Where rotation is respective to the segment pointing direction.

Calculating stretching and bending is quite obvious. Value[i-1, j-1] + stretch + bend.

Calculating add/remove. Add Value[i,j-1] + Cost of adding, remove Value[i-1, j] + cost of removal.