14-08-2012, 03:11 PM
MINUTIAE CLUSTERING
MINUTIAE CLUSTERING .docx (Size: 449.31 KB / Downloads: 29)
Clustering is a process whereby a set of objects is divide into several groups(clusters) which each of the members of a cluster is in someway similar and is different from the members of other clusters. Bifurcation points (that are found in the minutia extraction step) are given as input and clustering algo. is used to make clusters of bifurcation points. The true bifurcation points are clustered into different clusters using the following algorithms. Both these algorithms results in different clusters.
Algorithm:
Step 1: Select ‘k’ centroids randomly, each of which initially represents a cluster mean or center
Step 2: Calculate the Euclidian distance of each object from the cluster centroids and then assign each object to its nearest cluster.
Step 3: Recompute the centroid for each cluster
Step 4: Repeat steps 2-3 until there is no change in the centroid.
Grid-based Clustering
The grid-based clustering [7, 8, 9, 10] approach uses a multi-resolution grid. It employs a divide and conquer principle where it divides the image into grids and then merge the grids to form a cluster. This scheme can extract clusters efficiently with reduced number of comparisions. The image is divided into number of grids and the size of each grid is taken as 20x20(experimentally). Number of bifurcation points present in a grid is termed as grid density, which is found out for each grid. If grid density >= min_pts (where min_pts = 2 experimentally found), then the grid is termed as core grid. Adjacent core grid are then merged to form a cluster. Then recursion procedure is done till all adjacent core grid are merged to form a bigger cluster. Each cluster is then represented by the mean of the bifurcation points belonging to that cluster. Centroid of each cluster is used to generate a graph.
Graph Formation
Graph formation is the most important step in the index based searching technique. In this project, to generate the graph, the cluster centroids are selected as the set of vertices V={vi} i=1,2…,n where n is the number of clusters. There will be an edge between vertices vi and vj,
(i≠ j) if the Euclidian distance between vi and vj is greater than a predefined threshold value T.
.