Locating Multiple Circles with the “new” CircleSegmentor

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”. 

Raw Image

Original Raw Image

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.

Canny Edge Extration after m9 median filtering

Canny Edge Extration after m9 median filtering

Circle Segmentor Gradients Setup Tab

The setup dialog shows the Prefilter performing median filtering on the image and the Canny Edge detection parameters.

Gradient Setup

Gradient Setup

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.

Ransac Raw Centers Candidates

Ransac Raw Centers Candidates

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.

Multistage kMeans Clustering

Multistage kMeans Clustering

Clusters configuration

The cluster configuration is shown below:

Cluster configuration tab

Cluster configuration tab

Cluster Zoom

The cluster zoom shows how the convex hull selects the primary cluster based on density and calculates a pretty good center of gravity.

Clusters Zoom

Clusters Zoom

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.

Locates all circles with sub pixel accuracy and handles occlusion

Locates all circles with sub pixel accuracy and handles occlusion

It is fast – 17 circles in 100 ms on a quad-core laptop computer.

Read more http://www.linkedin.com/groups/Need-help-in-image-segmentation

%d bloggers like this: