Density Based Shoeprint Images Clustering Algorithms

Shoeprints are very important evidences of criminal investigations.Since the amount of shoeprint images acquired from crime scene is very large,it is one of the most urgent tasks that the criminal technology faces to cluster the shoeprint images automatically.The quality of the shoeprint images varies widely and the shapes of different clusters are various.In this work,we propose the shoeprint images clustering algorithms based on density.The main works of this thesis are as follows:1)An adaptive clustering algorithm for shoeprint images based on DBSCAN is proposedWe improve the DBSCAN algorithm based on the characteristics of shoeprint images and propose an adaptive clustering algorithm for shoeprint images which is named as MDBSCAN algorithm.MDBSCAN algorithm starts at the densest point.For each core point,we not only require the number of points in its neighborhood is larger than a given threshold,but also require the proportion of the same cluster points in its neighborhood is large enough.Considering the characteristics of shoeprint database and according to the relationship between the points and their neighbors,the input parameters of DBSCAN algorithm are determined automatically.Experiments on two kinds of public available datasets and one real shoeprint database show that the proposed algorithm performs better than compared algorithms.2)A hierarchical clustering algorithm for shoeprint images based on DBSCAN is proposedMDBSCAN algorithm is not appropriate for the datasets with great differences in density.Thus we propose a hierarchical clustering algorithm for shoeprint images based on DBSCAN which is named as HDBSCAN.Hierarchical structure is employed in HDBSCAN.In each clustering level,the input parameters of DBSCAN are determined automatically according to the relationship of points and their neighbors,at the same time for core points HDBSCAN require the proportion of the same cluster points in its neighborhood is large enoughApplying HDBSCAN algorithm on real shoeprint database composed of 16938 images,the purity reaches more than 90%.Meanwhile,we do experiments on two kinds of public available datasets and the purity reaches more than 95%.3)A clustering algorithm of shoeprint images based on the densest point is proposedWhen the distance of one point to two core points in different classes are less than the density-reachable distance,neither MDBSCAN nor HDBSCAN algorithm fails to judge the relationship between the point and the two core points.The classification of such data points is determined by the orders,which may lead to wrong clustering results.Thus we propose a clustering algorithm of shoeprint images based on densest points.In this algorithm,we first calculate the densest point of each class,and then cluster data points in two steps based on the densest points.We do experiments on real shoeprint database composed of 16938 images and the purity is 90.88%.Moreover,the algorithm performs better than compared algorithms on two kinds of public available datasets.Experimental results on public available datasets and real shoeprint images database show that the proposed algorithm is robust and have high accuracy.