This page is a part of the Computer Vision Wiki. The wiki is devoted to computer vision, especially low level computer vision, digital image analysis, and applications. The exposition is geared towards software developers, especially beginners. The wiki contains discussions of computer vision and related issues, mathematics, algorithms, code snippets, source code, and compiled software. Copyright © Intelligent Perception

Lengths of curves

From Computer Vision Wiki

Jump to: navigation, search

Problem

How do we measure the length of a curve in a digital image?

First, why do we need that? Consider this image. Suppose we want use computer vision to count nuts and bolts separately. Suppose we have detected and captured these objects. We can find their areas. However, since some of these objects have about the same size in terms of the area, we have to look at their shapes. We want to be able to evaluate shapes of objects and the most elementary way to do it is to compare their areas to their perimeters. The ability to compute lengths becomes crucial.

Specifically, we use roundness of objects.

Roundness = 4π*area/perimeter2

The roundness will tell circles from squares and squares from elongated rectangles, as follows.

Roundness of circle = (4π* πr2)/(2πr)2 = 1
Roundness of square = (4π*a2)/(4a)2 = π/4 = .785
Roundness of 1:5 rectangle = (4π*(b*5b))/(12b)2 = 5π/36 = .436

Observe that the results are independent of resolution. This allows one to evaluate shape separate from size.

Enlarge
Length of a digital curve.

In binary images, objects appear as collection of pixels. Curves are represented as sequences of points. It seems “obvious” that the length of the curve should be the total sum of distances between consecutive points. It is our concern however that the same “physical” curve will have different digital representations - depending on the image's resolution and the curve's orientation with respect to the grid. For the length to be a meaningful characteristic of the "physical" curve, all representation should have the same length – approximately. More precisely, as the resolution increases the lengths of the digital representations should converge to the "true" length of the curve. (It is easy to show that the area and other related characteristics of objects are independent of digital representation, see Measuring objects).

In particular, the length should be independent from the orientation of the curve with respect to the grid of the image. As analysis below shows, this is not the case if we adopt this definition of length.

Analysis

Let's take the direct approach:

The length is the total sum of distances between consecutive points.
The perimeter of a square and that of the inscribed circle are the same.
Enlarge
The perimeter of a square and that of the inscribed circle are the same.

Here is a simple example: the perimeters of a square and the inscribed circle are the same! Indeed, it takes exactly as many vertical (and horizontal) steps to get from the left end of the circle to the top - no matter whether you make just one turn or many. The curve isn't really a curve...

Let's consider another example in more detail. If r is the size of the pixel, a line segment of length a will be represented by roughly a/r pixels… but only if it is placed horizontally or vertically! If it is placed diagonally, there will be √2*a/r pixels arranged in the staircase pattern.

Horizontal orientation: length = a
Diagonal orientation: length = √2*a = 1.42a

Conclusion: the length depends on the orientation of the curve with respect to the grid of the image.

The result is that the digital length of a curve may vary by 40%. Observe that the error is independent from resolution. If you overlook this difference, the consequences may be disastrous.

The roundness is supposed to be lower for elongated objects, like bolts. This works perfectly well in the continuous domain but in the digital domain it is possible to think of very different shapes with both area and perimeters exactly same.

Diagonally oriented square with side a: 
  area = a2, perimeter = 4√2*a. 
Horizontally oriented rectangle with sides b=(√2-1)a and b'=(√2+1)a=5b: 
  area = a2, perimeter = 4√2*a.

Thus, a horizontally oriented rectangle with proportions about 1-to-5, just as in the image above, will have the same measurements as a diagonally oriented square. We can't tell a bolt from a nut…

Let’s review. Computing lengths of horizontal and vertical segments produces correct results. Computing lengths of diagonal segments leads to a 40% error.

Breaking a curve into "short" curves.
Enlarge
Breaking a curve into "short" curves.

A possible solution may be to break the curve into larger pieces. Every time we have a triple of consecutive points arranged in a triangle we should replace 1+1=2 in the computation with √2. The result is that now all 45 degree segments have correct lengths!







Segment with 30 degree slope.
Enlarge
Segment with 30 degree slope.

But what about 30 degree segments? Consider segments with 2 horizontal steps followed by 1 vertical.

“True” length = √(22+12) = √5 = 2.24. 
Old method: length = 3
New method: length = 1+√2 = 2.41.

The error is almost 8%!

[In the last computation, the length of a single 3 step segment = 1/2 the length of two 3 step segments = 1/2(2+√2+√2) = 1+√2.]

This error appears to be generally acceptable. For example in ImageJ, a square rotated to 30 degree has roundness (circularity) equal 70, instead of 80. Pixcavator produces a similar result. Elsewhere (MATLAB for example) lenghts are intended to be computed by curve fitting. This approach has to face the same issues as discussed on this section.

Exercise. If the relative error for the lenght is n%, what is the relative error for the roundness?


"Short" curves, building blocks.
Enlarge
"Short" curves, building blocks.

Now we need to take into account this new type of segment. Then we have three types: horizontal/vertical, diagonal, and now 2-straight-then-turn (same length as "diagonal"). To compute the length of a curve we break it into segments of the three types and add their lengths.

Next we try an angle between 0 and 30 degrees – there will still be an error. And so on. This suggests that there is no exact method to compute the length by breaking it into smaller pieces.

The problem is explored in paper On Local Definitions of Length of Digital Curves [1] by Mohamed Tajine and Alain Daurat. One breaks a digital curve into a sequence of “small” (n steps) curves, each small curve is assigned a length (it does not have to be the distance from the beginning to the end), then the length of the original curve is the sum of those. As the resolution approaches 0, the length computed this way should converge to the “true” length. The paper proves that in general it does not! The error remains the same regardless of the resolution, no matter how large n is.

The conclusion is the following:

There is no exact method to compute the length of a curve in a digital images.

...by traversing it only one time. And

The error is remains constant with increased resolution.

Here is a simple "explanation". Once n is chosen, the number of possible angles that curves of n steps can generate is finite. Meanwhile slopes of segments run (continuously!) from 0 to 360 degrees. No matter how large n is, there will be a segment that is not taken care of...

Solution

As n increases, the accuracy improves. This is a good news because it allows one to produce meaningful results in shape evaluation. If you know the accuracy that will be appropriate in your application, you can choose n that will guarantee it. However, consider this warning:

Beware of the propagation of error!

This is how the problem is solved:

  • Given n, we build the collection of all n-curves (curves with exactly n steps).
  • Each n-curve is assigned a length equal to the distance from the beginning to the end.

Next:

  • A given digital curve is represented as a sequence of n-curves (plus possibly one shorter) glued together end to end.
  • The length of this digital curve is the sum of lengths of these curves.

It is clear that all it takes to compute the length is a single run along the curve.

The computation of roundness is implemented in Pixcavator 2.4. The algorithm takes into account the number of steps (perimeter) and the number of turns (curvature). This is sufficient for exact computation of lengths of both horizontal/vertical and diagonal segments.

Exercise. Suggest a formula for the "adjusted" perimeter as a combination of perimeter and curvature.

The image above is an example of computation of roundness with Pixcavator 2.4.

First thing to notice is that the roundness of squares is independent of their orientation. Large squares have roundness close to 80. Because of the error of the computation of the perimeter, so do large circles. Nonetheless, in spite of this error Pixcavator successfully distinguishes between circles/squares and elongated objects.

The roundness starts to distinguish circles (90) and squares (still 80) as they get larger (600x600).

In the next example to remove the noise from the analysis (area limit 17) we set the roundness limit at 55. The result is the last image.

For more examples, see Roundness.

Personal tools