Detect corner coordinates of a non-convex polygon in clockwise order MATLAB

Question

I have some images which includes both convex as well as non-convex polygons. Each image contains exactly one polygon. I need to detect the corner coordinates and need to sort them in clock-wise or counter-clockwise order. For convex polygons, I use Harris corner detection for detecting corners and convexhull for sorting the points. But i dont have any idea on how to sort non-convex polygon. As my inputs are images, i think some Image Processing Technique might help to sort them out by moving alongside the edge of the polygon. Is there any way with least complexity?

Example Image:

I have named the corners randomly.

Expected output:

I expect Corner coordinates in this order 1 3 5 9 4 2 8 7 6 10 or 1 10 6 7 8 2 4 9 5 3. You can start at any point, not necessarily 1

Edit 1:

After rayryeng's solution, which works for all convex polygons as well as for some non-convex polygon, there are some non-convex polygons which doesn't go well with his algorithm.

Here is an example

Answer 1

Another approach is to use bwdistgeodesic to find order the corners by their distance along your edge. This should work for any polygon where you can detect a continuous edge.

We start by loading in the image from Stack Overflow and converting it into a black and white image to make it easier to find the edge

A = imread('http://i.stack.imgur.com/dpbpP.jpg');
A_bw = im2bw(A,100/255);  %binary image
A_bw1 = imcomplement(A_bw);   %inverted binary image

The bwmorph function provides a lot of options for manipulating black and white images. We're going to use the remove option to find the edge of our polygon, but you could also use another edge detector if you prefer.

%Find the edges
A_edges = bwmorph(A_bw, 'remove');
[edge_x, edge_y] = find(A_edges');

Let's visualize the edges we detected

figure; imshow(A_edges);

Okay, we have a nice clear continuous edge. Now let's find the corners. I use corner, but you could substitute your favorite corner detector

A_corners = corner(A_bw1, 'QualityLevel',.3);

Let's visualize our initial corner ordering

figure; imshow(A_bw1);
hold on
plot(A_corners(:,1), A_corners(:,2), 'r.', 'MarkerSize', 18)
text(A_corners(:,1), A_corners(:,2), strsplit(num2str(1:length(A_corners))), 'Color', 'g', 'FontSize', 24);
hold off

Another thing you might not notice, is that they are not directly on the edges. I'll start by finding the closest point along the edge to each corner point, and then I'll visualize corners in red and the closest edge points in green.

[~, ind] = min(pdist2(A_corners, [edge_x, edge_y]), [], 2);
A_edge_corners = [edge_x(ind), edge_y(ind)];

figure; imshow(A_edges);
hold on;
plot(A_corners(:,1), A_corners(:,2), 'r.', 'MarkerSize', 18)
plot(A_edge_corners(:,1), A_edge_corners(:,2),'g.', 'MarkerSize', 18)
hold off;

To calculate the distance around the edge for each corner, we'll use the corner point approximation, A_edge_corners (green point) on the edge rather than the corner point itself A_corners (red point).

Now we have all the pieces we need to use bwdistgeodesic. This function finds the distance to a seed point for each non-zero pixel in a black and white image. We are interested in the distance from an initial corner to each point on the edge. Let's try it out.

% Calculate distance from seed corner
first_corner = A_edge_corners(1,:);
D = bwdistgeodesic(A_edges, first_corner(1), first_corner(2));
figure; imagesc(D);

We're starting from the right most corner and the pixels moving away from the corner increase in value. But this isn't quite what we want. If we order the corners using these values, we end up with an ordering in distance from the initial point.

[~, corner_order] = sort(D(sub2ind(size(D), A_edge_corners(:,2), A_edge_corners(:,1))));
A_corners_reorder1 = A_corners(corner_order, :);

figure; imshow(A_bw1);
hold on
plot(A_corners_reorder1(:,1), A_corners_reorder1(:,2),'r.', 'MarkerSize', 18)
text(A_corners_reorder1(:,1), A_corners_reorder1(:,2), strsplit(num2str(1:length(A_corners))), 'Color', 'g', 'FontSize', 24);
hold off

To solve this problem, we just have to break the edge so that the ordering only goes in one direction from the initial point. If you are interested in a clockwise or a counter-clockwise ordering, you would need to break the edge according to a set of rules depending on the orientation of the edge. If the direction doesn't matter you can simply find an adjacent pixel to the initial corner, and break the edge there.

%Break the edge into one path by removing a pixel adjacent to first corner
%If the corner is near the edge of the image, you would need to check for
%edge conditions
window = A_edges(first_corner(2)-1:first_corner(2)+1, first_corner(1)-1:first_corner(1)+1);
window(2,2) = 0; %Exclude the corner itself
[x, y] = find(window, 1);
A_edges(first_corner(2)+x-2, first_corner(1)+y-2) = 0;  

figure; imshow(A_edges);
hold on;
plot(first_corner(1), first_corner(2), 'r.', 'MarkerSize', 18)
hold off;

Now the distance from the initial point along the edge can only follow one path

%Find order the pixels along edge
D = bwdistgeodesic(A_edges, first_corner(1), first_corner(2));
figure; imagesc(D);

This gives us the desired ordering of edges

[~, corner_order] = sort(D(sub2ind(size(D), A_edge_corners(:,2), A_edge_corners(:,1))));
A_corners = A_corners(corner_order, :);

figure; imshow(A_bw1);
hold on
plot(A_corners(:,1), A_corners(:,2),'r.', 'MarkerSize', 18)
text(A_corners(:,1), A_corners(:,2), strsplit(num2str(1:length(A_corners))), 'Color', 'g', 'FontSize', 24);
hold off

This method also works on polygons that are unbalanced with respect to the centroid, such as the second demo image.

For fun, I present a third image, which has a vertex on the opposite side of the centroid, as a clearer example of an unbalanced polygon. My method also correctly parses this image.

Answer 2

This is a common problem in image processing. The typical answer is to find the centroid of the shape, and find the angle between the centroid and each corner point. You would make sure that the angles are represented so that they range between [0,360) degrees. Once you have this, you sort the angles then use the resulting order to determine the order of the points.

The image that you presented requires a bit of pre-preprocessing so I can start working on it. I read in the image directly from StackOverflow, then I invert the image so that the black star becomes white. I also need to remove the numbers, so I employ bwareaopen to remove any small areas of text. Once that's done, I perform a corner detection on this image via corner, and I set the QualityFactor to 0.3 so I can detect the 10 corners. Very specifically:

%// Read image from StackOverflow
im = rgb2gray(imread('http://i.stack.imgur.com/dpbpP.jpg'));

%// Threshold the image and area open it
im_thresh = im <= 100;
im_open = bwareaopen(im_thresh, 50);

%// Detect corner points
out = corner(im_open, 'QualityLevel', 0.3);

%// Show the image with the corner points
imshow(im_open);
hold on
plot(out(:,1), out(:,2), 'r.')

im_open contains our final processed image. This is what I get:

---

Now, let's find the centroid. This can simply be done by finding the coordinates of the non-zero locations, and finding the average of each dimension:

[rows, cols] = find(im_open);
cenX = mean(cols);
cenY = mean(rows);

cenX and cenY contain the (x,y) locations of the centroid of the image. Just to be sure we have it right:

imshow(im_open);
hold on;
plot(cenX, cenY, 'r.', 'MarkerSize', 18);

We get:

Very nice. Now, out in the earlier code contains (x,y) points of the corner points. All you have to do is determine the angle from the centroid to each corner point, then sort the angles. You would use this sorting order to rearrange the corner points to give you your arranged points. If you want clockwise, you would need to sort the values in ascending order. If you want counter-clockwise, you would need to sort in descending order. I'll leave that up to you on what you want to decide, but I'll write code that will allow you to do both. Therefore, simply do this:

%// Determine angles (in degrees)
angles = atan2d(out(:,2) - cenY, out(:,1) - cenX);

%// Any negative angles, add 360 degrees to convert to positive
angles(angles < 0) = 360 + angles(angles < 0);

%// Sort the angles
[~,ind] = sort(angles); %// clockwise
%[~,ind] = sort(angles, 'descend'); %// counter-clockwise

%// Re-arrange the corner points to respect the order
out_reorder = out(ind,:);

Now the final test is to plot these points and also plot a number beside each point to see if we got it right. That can be done by:

%// Show image
imshow(im_open);
hold on;
%// Show points
plot(out_reorder(:,1), out_reorder(:,2), 'r.', 'MarkerSize', 18);

%// Place a textbox at each point and show a sequence number
for idx = 1 : size(out_reorder,1)
    text(out_reorder(idx,1), out_reorder(idx,2), num2str(idx), 'FontSize', 24, 'Color', 'green');
end

We get:

Looks good to me! As such, out_reorder gives you the corner points so that they follow either a clockwise order, or counter-clockwise order. Each row that you encounter in succession gives you the next point that naturally follows the clockwise or counter-clockwise order you seek.

Also take note of where the numbering starts. The angle of 0 is defined by a horizontal line that points to the east with respect to the centroid. Therefore, the closest point to 0 as we are starting in ascending order is where you see the number 1. After the 1, you see that it sweeps in clockwise order until we run out of corner points.