# Image processing: extracting ordered contour

Continuing the question How to extract the edge from a set of points and its answer by Simon Woods, I would like to ask if there is a way to extract the boundary of

obtained as

ToExpression@Import@"http://pastebin.com/raw.php?i=741qaDt2";
boundary = Complement[spiel, Intersection @@
Outer[Plus, {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}, spiel, 1]];


ordered in such a way that

ListPlot[boundary,Joined->True]


would give a polygon outlining the shape? The points extracted the way they are in the answer are not ordered along the boundary:

It would be even better to know if it is possible with MorphometricComponents[], because images I am working on look like that:

With MorphometricComponents[] one can extract perimeter lenghts, baricenters and whatever he likes for the components, but not the ordered perimeter points themselves.

So the question is if there is a way to do that? Just to be clear: for each region in the picture, I would like to have the ordered coordinates of the points of the boundary boundary={{x1,y1},{x2,y2},...} such that ListPlot[boundary,Joined->True] would give polygons outlining the shapes.

-
This is probably not going to solve your problem completely, but it's good to know about FindCurvePath (look it up) –  Szabolcs Mar 31 '14 at 16:24
@Szabolcs Indeed, that is a quick solution. Using ListPlot[boundary[[FindCurvePath[boundary][[1]]]], Joined -> True] I get an ordered curve. The question remains about MorphometricComponents[]. –  Szczypawka Mar 31 '14 at 16:28
Unfortunately it doesn't always find the "right" ordering, and sometimes it returns several disjoint curves. So it's probably not good as a general solution. –  Szabolcs Mar 31 '14 at 16:32
@Szabolcs Agreed. The idea is that you know how the curve goes when you have the original image. And I'm thinking about a way not to lose this information. When you come to the boundary the way it is described, you have already lost it. –  Szczypawka Mar 31 '14 at 16:34
Maybe a TSP? Might not be fully robust, but should probably take you most of the way... –  The Toad Mar 31 '14 at 17:12

To my knowledge, it is not directly possible to compute the outline of objects with the provided morphological image processing functions. I use the outline of connected components very often too, mostly for visualising, but I think something like this should really be included in ComponentMeasurements.

Since you know that the distance between outline pixel will always be smaller equal Sqrt[2] in a 4 neighbourhood and that your outline pixel will always be a closed contour, you can easily implement this functionality by yourself. With an eroded and padded version of your image (to make more objects):

img = ImagePad[Erosion[Import["http://i.stack.imgur.com/tmKw2.png"], 1], 5]


the implementation of such an algorithm is straight forward. Calculate the morphological perimeter with erosion/dilation or with MorphologicalPerimeter to get all the boundary pixel. For one object, you start at any boundary pixel, exclude it from the rest and find the next closest pixel. Then this pixel is your new starting point and you repeat until there are no pixels left. If you want a closed line contour, don't forget to append your very first pixel to the final sorted list:

createPath[pts_] :=
Append[NestList[
Function[data, With[{fst = First[data], rst = Last[data]},
{Extract[rst, #], Delete[rst, #]} &[
Nearest[rst -> Automatic, fst, 1]]
]], {First[pts], Rest[pts]}, Length[pts] - 1][[All, 1]],
First[pts]]


Then you need a small wrapper function to calculate the morphological perimeter and convert them into pixel positions

extractPaths[img_Image] :=
MorphologicalPerimeter[img, CornerNeighbors -> False]], "Mask"][[All, 2]]},
]


Now you can use extractPaths to get a list of all object outlines:

HighlightImage[img, Flatten[extractPaths[img], 1]]


-
A good solution, thank you! Just one more question: do you see a way how to assure that all the contours are passed in the same direction: clockwise or counterclockwise? –  Szczypawka Apr 1 '14 at 13:02

The problem can be posed as a Traveling Salesman Problem, where we have a salesman starting at a city (or a point) and has to visit every other city once while minimizing his total distance.

pts = boundary[[Last@FindShortestTour[boundary, Method -> "CCA",
DistanceFunction -> ManhattanDistance]]];
Show[
ListPlot[spiel, PlotStyle -> Gray],
ListLinePlot[pts, PlotStyle -> Red]
]


I'm not sure if this is guaranteed to work under all circumstances (especially in regions with a "pinch" zone, like the figure 8), but for the examples shown in your blob, it should work.

-