8

Imagine I have the two dimensional image of a hotdog. I can draw a straight line on the hotdog between its two ends. Call this the midline. One of its properties is that it is the axis about which the (2D) hotdog has the lowest moment of inertia.

Now if I bend the hotdog in an arc, this midline will also distort.

Given a picture of the bent hotdog, how can I determine this bent midline? The algorithm should tolerate a modest amount of noise in the image.

Marc
  • 5,315
  • 5
  • 30
  • 36
  • 1
    Are the ends "round"? I mean: are circles good approximations for the ends? – Dr. belisarius Dec 30 '10 at 10:31
  • to some extent. Circles are a good approximation for the ends, but the diameter of those circles is probably not the same as the width of the "hotdog" – Marc Jan 03 '11 at 17:38

4 Answers4

5

If I understand your question, you want a line through your object where every point is in the middle of the object, i.e. if you start from any point on the midline and walk in a direction perpendicular to the midline, you have to walk the same distance in both directions until you meet the border of the object:

Hotdog with midline

(this is just an illustration - probably not the geometrically correct midline!)

My quick&dirty solution would be to start with a middle axis (that can easily be calculated from first and second-order moments) and refine it by taking each point on this line and find the nearest border points on a line perpendicular to the current direction at that point, and move the point to the geometric center of these two points:

Hotdog iteration 0

If you do this for every point, you should get a better approximation for the midline.

I said this was quick&dirty, because I'm not sure if simply repeating this procedure always converges to a stable solution. It probably depends on how you calculate the perpendicular direction of the midline in the presence of bends and kinks.

One way around this is to use a more physically-inspired model:

  • Calculate a distance transform for the inside of your object (the distance of each point to the closest border point)
  • Find a smooth line through the object that maximizes the path integral of the distance transform image:

Distance transform

To find this line, I would use an algorithm similar to active contours/snakes:

  • Start with the middle axis
  • Apply two forces to each point:
    • One force "pushes" the line in the direction of the gradient of the distance transform (i.e. away from the closest border)
    • The other force counters the stretching and bending of the snake, so it keeps a smooth shape where there is no clear distance transform gradient. (Google for active contour - this is fairly standard CV stuff, you'll find lots of good articles about it.)
  • Repeat until convergence or some fixed iteration limit is reached

You'll need to adjust a few parameters for these smoothness of the curve (as always with active contours), but your chances to get a well-defined and well-behaved approximation are far better than with the simple approach above.

Niki
  • 15,662
  • 5
  • 48
  • 74
  • Plus 1 for any solution involving snakes! ;-) – Throwback1986 Dec 29 '10 at 21:09
  • I like the idea of the iterative algorithm, but I think it would fail for the endpoints. I think you are right to do some kind of distance minimization with an additional energy term to penalize kinkiness of the contour. But you might still need something to anchor the endpoints at regions of high curvature. I'll work on it. – Marc Jan 03 '11 at 17:41
  • 1
    @Marc: The idea of the energy minimization was that near the endpoints, the distance gradient should be parallel to the midline, so it would have no effect on the snake. In these areas, the elasticity of the snake would be dominant, so it *should* extrapolate the hotdog-shape towards the endpoints. But that's all theory, of course. – Niki Jan 03 '11 at 19:20
  • Got it to work, as you suggested. I did the standard active contour thing, with the distance transform as the energy potential (negative inside the contour and positive outside it). Good tips! – Marc Jan 07 '11 at 22:47
3

Maybe you can skeletonize your bent hotdog.

You first have to thresold it, then use a thinning algorithm.

Here are some cool links:

http://xphilipp.developpez.com/contribuez/Skeleton-Algorithm.pdf http://www-prima.inrialpes.fr/perso/Tran/Draft/gateway.cfm.pdf http://www.geometrictools.com/Documentation/Skeletons.pdf

Nicolas Repiquet
  • 9,097
  • 2
  • 31
  • 53
  • skeletonization doesn't work, as it produces spurs near the ends of the "hotdog". I need a clean line that passes from endpoint to endpoint, and I'm most interested in these two ends, which is exactly where skeletonization fails. medial midline has a similar problem – Marc Dec 29 '10 at 16:33
2

If the skeletonizing approach doesn't work, you are probably looking at a harder problem - which brings up a number of questions: how constrained are your shapes? are they always convex? etc. Depending upon the answers, you might consider parameterizing the shape.

For starters, I would consider computing a convex hull (google QHull) and then determine a Delaunay triangulation of the shape. From there, I believe you could compute a Voronoi diagram and achieve the midline you need. Note: this is a lot of work - given this level of effort, it might helpful to see if a simple skeletonization can be tweaked enough to be sufficient.

Throwback1986
  • 5,887
  • 1
  • 30
  • 22
0

You're probably looking for the Voronoi diagram, which will give you all the points that are equidistant from the shape "hot dog" edges -- e.g. the path/spine/ridge/midline down the middle.

And here's an image to help visualize it: http://vision.ai.uiuc.edu/~sintod/images/research/VoronoiDiag.png

Mapping this image to your example, the heavy blue outlines are your "hot dog" shapes, and the thin blue spine/midline in the interior is given by the Voronoi diagram. The points on that midline ridge are equally distant from the heavy blue edges.

payne
  • 13,833
  • 5
  • 42
  • 49
  • yeah, but if you look at the ends of the narrow region, you'll see there's no well-defined midline from the voroni diagram. I think the problem with all of these algorithms is that they're essentially pseudo-local-- the voroni diagram/delaunay triangulation/skeletinization of a round end looks roughly the same regardless of the orientation of the rest of the object connecting to the end; as nikie realized, the hard part is continuing the midline on from the central region to the end in a reasonable manner. – Marc Jan 25 '11 at 13:47
  • I understand what you're saying, but I think you might be able to deal with that by sorting and/or filtering the resulting set of Voronoi edges. For example, if you sort descending the Voronoi edges by their distance (precisely, maximum distance), you'l end up with the "midline" edges first. Then you could threshold cut what you want. I've used Voronoi diagrams for a problem like yours -- I'm glad to help. – payne Jan 25 '11 at 14:05