# Order contour points in clockwise

I want to describe shape of an object using contour points descriptor. Given a silhouette (image black white of an object), I extrait the contour points using EdgeDetect[] fonction. After that, I need to order these points as clockwise order starting from a given point p.

I try like this: 1) get the centroid. 2) Apply that as an offset to every point(subtract from the array) 3) For each point treat X and Y as real and imaginary and convert to Polar. bundle these as a cluster with angle first 4) Sort the array that this creates. 5) For each point convert back to X and Y 6) Add the offset back on. In this case some points does not respect the order. here is my code: ![image used1

    centroid =
ComponentMeasurements[silhouette, "Centroid"][[All, 2]] // Flatten
contourImage = EdgeDetect[silhouette];

contourData = ImageData[contourImage];

coordContourData = PixelValuePositions[contourImage, 1];

normalizedContourData = (coordContourData[[#]] - centroid) & /@
Range[1, Length[coordContourData]];

angles = Table[
N[ArcTan[normalizedContourData[[i, 1]],
normalizedContourData[[i, 2]]/Degree]], {i, 1,
Length[normalizedContourData]}]
orderedcontourpoints = coordContourData[[Ordering[angles]]];

emptyImage = Image[Table[0, {i, 1, 600}, {j, 1, 800}]];

Manipulate[
ReplacePixelValue[emptyImage,
orderedcontourpoints[[1 ;; i]] -> 1], {i, 1, Length[angles], 1}]


I need to rectify this problem and I need to start from a given point, for example the point in the left having the same y as the centroid. Any suggestions please?

• I think that I have to add the norm r as a second sorted criteria. – BetterEnglish Oct 6 '14 at 21:53
• I don't have time to look at your code but it sounds like you should use FindShortestPath: positions = PixelValuePositions[EdgeDetect@img, 1]; Graphics[ Line[ positions[[ Last@FindShortestTour[positions] ]] ] ] (cycle the list until it starts with your point, reverse it if necessary) – C. E. Oct 7 '14 at 1:34
• If by "respect the order" you mean what I think you mean, then the whole method will only work if the region is star-shaped (in the mathematical sense of that term) with respect to the centroid. – Daniel Lichtblau Oct 8 '14 at 14:59
• @DanielLichtblau, thanks, I responsed the question – BetterEnglish Oct 9 '14 at 2:41
• @DanielLichtblau, my response fail on some silhouettes. – BetterEnglish Oct 27 '14 at 20:34

This function can be used to generate the contour points in the clockwise order. The starting point is fixed as the left point having the same y as the centroid of the contour.

ContourBasedFeature[silhouette_] :=
Module[{centroid, startpoint, positions, contourPoints, order,
clockwiseorder}, (
centroid =
ComponentMeasurements[silhouette, "Centroid"][[All, 2]] // Flatten;
positions = PixelValuePositions[EdgeDetect@silhouette, 1];
startpoint =
Select[positions, #[[2]] == Ceiling[centroid[[2]]] && #[[1]] <
Ceiling[centroid[[1]]] &];
contourPoints =
Join[startpoint, DeleteCases[positions, startpoint // Flatten]];
order = contourPoints[[Last@FindShortestTour[contourPoints]]];
If[order[[1, 2]] > order[[2, 2]],
Join[{order[[1]]}, order[[Range[Length[order], 2, -1]]]],
order
]
)]


I call the function using the below silhouette noted sil22.

emptyImage = Image[Table[0, {i, 1, 300}, {j, 1, 400}]]
clockwiseorder = ContourBasedFeature[sil22]
Manipulate[
ReplacePixelValue[emptyImage, clockwiseorder[[1 ;; i]] -> 1], {i, 1,
Length[clockwiseorder], 1}]