Last time we have seen how to identify key points in an image. I was then thinking to use machine learning techniques to recognize the roles played by each point. I played for a while with Weka, a tool which make very easy to experiment with different Machine Learning algorithms. To identify the features to use in the classification I used this strategy:
- I draw two concentric circles around the points of interest: one close and one further away
- I identified the intersection of the contour to which the key point belonged and the concentric circles
- I splitted the circles in 12 parts and counted how many intersections were falling into each of those parts
- I then used those 24 values for the classification
..if simple heuristics can do…
However I realized that there was no actual need for machine learning. I could instead very simple heuristics. After all I was just looking for the corners of the rectangles so I considered only points which had two intersections for the closest and the farthest circle. Then I considered the angle of this intersection, basically looking for something around 90°. Then considering the orientation of the corner I classified it as a top-left, top-right, bottom-left or bottom-right corner.
Once I have classified the points I started looking for top-left corners and considered matching bottom-right corners. I just took the closest one in the right direction. Once I have a pair of top-left and bottom-right corners I know where to look for the missing corners: the top-right is supposed to have an x equal to the one of the bottom-right point and an y equal to the one of the top-left corner, viceversa for the bottom-left point. If I can find these two points where I am looking for them I consider the rectangle complete.
Finally I have just to check if I recognized overlapping rectangles: in that case I just throw away the smaller ones.
This algorithm is not perfect but I get decent results:
Why I am not using OpenCV
When we are manipulation images OpenCV is the obvious answer, however I did not get good result with it. It seems that the typical algorithms for detecting rectangles are confused by the fact the contourns I found are not rectangles. This is because of the connections between rectangles (the lines linking the rectangles). I tried a few thing but I did not get any good result. In addition to that OpenCV is written in C/C++ and that basically means that deploying it is much more cumbersome. My current solution is Java based and that means that I can easily run it on every possible platform without headaches. I will have another look at OpenCV and I am very open to suggestion. In fact a friend of mine just gave me a couple of nice ideas to try.
Code, where is the code?
You know, words are nice and all but the only thing that really matters is code. You can grab it on GitHub, here: https://github.com/ftomassetti/SketchModel
| Reference: | Recognizing hand-written rectangles in an image from our JCG partner Federico Tomassetti at the Federico Tomassetti blog. |
