Finding Total Coin Using Kmeans and Hough Transform Algorithms

We can apply 3 algorithms for classifying and detecting the circular objects in an image.
-Kmeans
-Tracking images
-Hough Transformation 

 Kmeans 
K-means clustering aims to partition n observations into k clusters in which each observation belongs to the cluster with the nearest mean, serving as a prototype of the cluster. It is proper for  compact cluster algorithm  and sensitive to outliers and noise .Calculation of the number of clusters is small, makes it faster than hierarchical clustering and uses only numeric attributes .Disadvantages of   Kmeans algorithm to determining the number of clusters k is so hard.
 -Set of feature vectors X={x1,x2,…xn}
 -Our feature for circle detection is “Area”s in image.
 -The number of clusters to be detected->K
 -For finding coin in an image our number of cluster is K=5 (1TL,0.5TL,0.25,0.1,0.05)

There are 5 different clusters for classification and Kmeans use these as input values.Kmeans groups objects according their areas.

K-Means can be put the same objects into different classes so it is not effective solution for us. 

 Tracing The Objects

Kmeans has not accuracy enough for us and we give an order for classifying the coins.

1-Grayscale of image

2-Imfill of image

3-Removing the noise (with 50 strelldisk)

4-Tracing extrerior boundaries of objects (bwboundaries) 

5-Regionprops measures a set of properties for each connected component (object) in the binary image BW, which must be a logical array

6-Tracking object is not effective solution for segmentation problem

7-We have to ignore noncircle objects in image and have to seperate the overlapping circles 

Circular Hough Transformation

The circular hough transform is a circle extraction technique used in image process and computer vision. It is the best way of finding total coins in an image and detecting the circles by using voting procedure. If  the radius R value of the circles in an image is known, the search area can be reduced to one dimension from two dimensions. The objective is to find the (a,b) coordinates of the centers.

  a=x-R cos(t) 

 b=y-R sin(t)

Firstly we read the image, then we create binary image and remove it from the noise. Finally we find the boundaries (Sobel) and determine which objects that are round.

 


Circle parameters for the circular Hough transform: The points on the circle (x,y) in image space is mapped onto a line in the accumulator.

 

The centerpoints are represented as red cells in the parameter space drawing. Overlap of circles can cause spurious centers to also be found, such as at the blue cell.In different radius internal Hough Transform detect different circles below:

    r2 =  ( x – a )2 + ( y – b )2

    a=x-R cos(t)

    b=y-R sin(t)

Applying Circular Hough Transformation  on Coins Image:

Find the distance of image by imdistline function.We obtain the possible R values interval 90-170:

 1632≈90*170

Circular Hough Transformation  Matlab Code

1-In Circular Hough Transform Method we dont use Area and we use Radius values of coins Matlab Code Below

%Hough Transform

function totalAmount = findCoins(imName)

res= imread(imName);

figure; imshow(res);

resizeRate = 1;

%res = imresize(res,resizeRate, 'nearest');

% I = rgb2gray(res);

% coin1 = im2bw(I);

% bw=imfill(~coin1,4,'holes');

%res,[90 170] değeri res,[90 200] olursa daha çok circle tarar

[centers, radii, metric] = imfindcircles(res,[90 170], ...

 'ObjectPolarity','dark','Sensitivity',0.95,'Method','twostage');

%viscircles(centers, radii,'EdgeColor','b');

nCoins = size(centers,1);

total = 0;

for n=1:nCoins

    X=centers(n,1); Y=centers(n,2);

    radius = radii(n,1);

   

    if radius>150

        text(X-10,Y,'1 TL');

        total=total+1;

    elseif 135<radius

         text(X-10,Y,'0.5 TL')

        total=total+0.5;

    elseif 125<radius

         text(X-10,Y,'0.25 TL')

        total=total+0.25;

    elseif 115<radius

         text(X-10,Y,'0.1 TL')

        total=total+0.1;

    else

         text(X-10,Y,'0.05 TL')

        total=total+0.05;

    end

end

hold on

title(['Toplam: ',num2str(total),'TL'])

totalAmount = total;

end

The Output Of Code:

Comparing Accuracy of Algoritms

	Accuracy	time
Kmeans	0.50	0.2 min
RegionProps	0.71	0.8 min
Hough Transform	0.86	1.2 min

Other Applications of  Hough Transformation  

 Human made construction (ancient city )detection : Regular shapes can be detected on the map or google earth values such as a  resecarhing in West BlackSea -Zonguldak Çaycuma Tios Ancient city. The researchers verify this method to finding  Billaios ancient river.

Earthquake fault line detection: Boundary map of Adapazari obtained from application boundary algorithm.Fault traces formed by combining the lineaments.

Red blood cell detection: Segmentetaion and determining the number of red blood cells for anemia disease .

Irish Segmentation: Human eyes could use for identity detection. A sample reseach use UBIRIS.v1 dataset (241 eyes-1977 irish sample) they assume the r radius of human eye between 0,1-0,8 cm.

      Ball detection in sport events(football,voleyball) 

Özge ATASEVEN