Image processing: extracting ordered contour

Question

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.

Answer 1

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["https://i.sstatic.net/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] := 
 With[{masks = ComponentMeasurements[MorphologicalComponents[
       MorphologicalPerimeter[img, CornerNeighbors -> False]], "Mask"][[All, 2]]},
  createPath[Position[Transpose@Reverse@Normal[#], 1]] & /@ masks
]

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

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

Answer 2

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.