Approximate shape with polygons

Question

From a PNG image containing a transparent region and a color region, I would like to create a polygon with N-sides (N is customizable), approximating the best possible edge of the image. I want this polygon defined by a series of vectors.

For example, consider the following image: + link to plus . I can determine the edges of the image by counting for each pixel the number of transparent pixels around it. I get the following matrix:

 0000000000000000 0000053335000000 0000030003000000 0000030003000000 0000020002000000 0533210001233500 0300000000000300 0300000000000300 0300000000000300 0533210001233500 0000020002000000 0000030003000000 0000030003000000 0000053335000000 0000000000000000 0000000000000000 

I think, based on this matrix, I would have to get the coordinate of all the angles and, therefore, get the vectors, but I can’t figure out how to do this. In this case, I want my program to return:

 [7,2]->[11,2] [11,2]->[11,6] [11,6]->[15,6] ... 

Do any of you have a suggestion or link for this?

Ultimately, I would also like an approximate angle other than 90 and 0, but this is really the second step.

Answer 1

I think you will find in CV Toolkit a number of tools that may be useful to you. You will do your best to use these resources, and not minimize your own decision.

Two functions that I think you are interested in when extracting are edges and corners.

Edges , like what you did, can lead you to the outline of the figure. You are probably not interested in Edge Detection methods right now. They convert your image into a binary image of the edge / space. Instead, you'll want to explore the Hough Transform , which can give you endpoints for each of the lines of your image. If you are dealing with well-defined, strong, straight lines, it seems to you that this should work well. You marked your question as Ruby, so maybe you can take a look at OpenCV (OpenCV is written in C, but there is ruby-opencv and javacv for binding). Here is the Hough Transform documentation for OpenCV . However, one thing might seem that the Hough transform does not give you lines that connect. It depends on the regularity / irregularity of the actual lines of your image. Because of this, you may need to manually connect the endpoints of the lines to the structure.

Corners may work well enough for images such as the one you provided. Standard Harris angle detection algorithm. Like the Hough transform, you can use this technique to return the “most important” functions in the image. This method is known for giving consistent results even for different images of the same object. Thus, it is often used for pattern recognition and the like. However, if your images are as simple as those provided, you may be able to extract all corners of the form in this way. Obtaining the shape of the image then would simply have to tie the dots in a meaningful way, taking into account your predetermined N sides.

You should definitely play with both of these spaces and see how they work, and you could use both shared and better results.

As an aside, if your image is really color / intensity on transparent, you can convert your image to a “binary image” . Please note that this is not only binary data. Instead, this means that you represent only two colors, one of which is represented by 0 , and the other by 1 . This opens up a whole set of tools that work on halftones and binary images. For example, the matrix of numbers you calculate manually above is called distance conversion and can be performed quite easily and efficiently using tools such as OpenCV.

Answer 2

Hough transform is a standard technique for finding lines, polygons and other shapes based on many points. This may be exactly what you are looking for here. You can use the Hough transform to search for all possible line segments in an image, and then group adjacent line segments to get a set of polygons closer to the image.

Hope this helps!

Answer 3

In such a simple situation, you can perform the following three steps: find the centroid of your figure, sort the objects of interest based on the angle between the x axis and the line formed by the current point and the centroid, and go through the sorted points.

Given the situation, the x-coordinate of the center of gravity is the sum of the x-coordinates of each point of interest divided by the total number of objects of interest (respectively, for the y-coordinate of the centroid). To calculate angles, just use atan2, available in almost any language. Your interests are those that are represented as 1 or 5, otherwise it is not an angle (based on your input).

Do not be fooled that Hugh will solve your question, that is, he will not give the sorted coordinates that you are after. This is also an expensive method. In addition, given your matrix, you already have such ideal information that no other method will beat (the problem, of course, repeats such a good result as you presented), in those cases, Hugh may be useful).

My Ruby is pretty bad, so take the following code as a recommendation for your problem:

 include Math data = ["0000000000000000", "0000053335000000", "0000030003000000", "0000030003000000", "0000020002000000", "0533210001233500", "0300000000000300", "0300000000000300", "0300000000000300", "0533210001233500", "0000020002000000", "0000030003000000", "0000030003000000", "0000053335000000", "0000000000000000", "0000000000000000"] corner_x = [] corner_y = [] data.each_with_index{|line, i| line.split(//).each_with_index{|col, j| if col == "1" || col == "5" # Cartesian coords. corner_x.push(j + 1) corner_y.push(data.length - i) end } } centroid_y = corner_y.reduce(:+)/corner_y.length.to_f centroid_x = corner_x.reduce(:+)/corner_x.length.to_f corner = [] corner_x.zip(corner_y).each{|c| dy = c[1] - centroid_y dx = c[0] - centroid_x theta = Math.atan2(dy, dx) corner.push([theta, c]) } corner.sort! corner.each_cons(2) {|c| puts "%s->%s" % [c[0][1].inspect, c[1][1].inspect] } 

This leads to:

 [2, 7]->[6, 7] [6, 7]->[6, 3] [6, 3]->[10, 3] [10, 3]->[10, 7] [10, 7]->[14, 7] [14, 7]->[14, 11] [14, 11]->[10, 11] [10, 11]->[10, 15] [10, 15]->[6, 15] [6, 15]->[6, 11] [6, 11]->[2, 11] 

What are your vertices clockwise, starting from the bottom left side (in Cartesian coordinates, starting at (1, 1) in the left-most lower position).