Determine the midline of a bent, elongated region

问题:

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.

回答1:

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:

(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:

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:

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.

回答2:

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

回答3:

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.

回答4:

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.