Locating circles is a classic challenge in machine vision. On the LinkedIn group “Computer Vision” – Axel Laurent posted the following :
“I would like to divide this image http://www.casimages.com/img.php?i=140418103439198305.jpg in several sub-images where in each sub-image containt a circular object. I used hough transformed to detect the circal object center and then I used watershed to segment the image but due to the importance of noise that doesn’t work”.
A heated discussion – 59 posts are received so far – started immediately and I posted a solution to the post based on the Scorpion Vision tool CircleSegmentor.
We have since then upgraded CircleSegmentor one of the major tools in Scorpion Vision Software with a new powerful clustering step based on kMeans method – this increased the robustness and in some cases tripled the speed of our fine point and click solution.
1. Extract Canny Edge from the Image after median filter m9
The following images shows canny edges after median filtering – this shows that it is possible to focus on two “circles” the inner dark circle or the larger grey circle.
Circle Segmentor Gradients Setup Tab
The setup dialog shows the Prefilter performing median filtering on the image and the Canny Edge detection parameters.
3. Ransac RawCenter Extraction
The next step in CircleSegmentor circle detection is to estimate the circle clusters or rawmatches with a Ransac algorithm where we use the diameter and the edge angle to estimate circle center candidates – these are shown in blue. The setup is defined in the Search Setting in the Gradient Tab – see above.
4. Multistage kMeans Clustering
The next and new feature is to cluster the rawmatches and calculate a cluster center of gravities – COGs. The advantage of the clustering is to qualify the centers by rawmatch density or a user specified cost function – thus avoiding timeconsuming circle model validations.
The cluster configuration is shown below:
The cluster zoom shows how the convex hull selects the primary cluster based on density and calculates a pretty good center of gravity.
5. Final Circle Match based on Cluster COG
The final step is to iterate the located clusters. For each cluster the center of gravity is used as a starting point for circle matching. A circle model is defined and matched with the PolygonMatch algorithm thats fits the edge points to a circle with sub-pixel accuracy. Circle 7 and 14 shows that the algorithm handles occlusion.
It is fast – 17 circles in 100 ms on a quad-core laptop computer.