摘要:目的 鞋印是刑事侦查的重要物证之一,如何对积累的大量鞋印花纹图像进行自动归类管理是刑事技术迫切需要解决的问题之一。与其他类图像不同,鞋印花纹图像具有种类多但数目未知、同类花纹分布不均匀且同类花纹数目少的特点。基于鞋印花纹图像的这些特点,用目前典型的聚类算法对鞋印花纹图像集进行聚类,并不能取得很好的效果。在对鞋印花纹图像进行分析的基础上,提出一种K步稳定的鞋印花纹图像自动聚类算法。方法 对已标记的鞋印花纹图像进行统计发现,各类鞋印花纹之间在特征空间上存在互不相交的区域(本文称为隔离带)。算法的核心思想是寻找各类鞋印花纹之间的隔离带,来将各类分开。过程为:以单调递增或递减的方式调整特征空间中判定两点为一类的阈值,得到数据集的多次划分;若在连续K次划分的过程中,某一类的成员不发生变化,则说明这K次调整是在隔离带中进行的,即聚出一类,并从数据集中删除已标记的数据;选择下一个阈值对剩余的数据集进行划分,输出K步不变的类;依此类推,直到剩余数据集为空,聚类完成。结果 在两类公开测试数据集和实际鞋印花纹数据集上进行实验,本文算法的主要性能指标都超过典型算法,其中在包含5792枚实际鞋印花纹数据集上的聚类准确率和F-Measure值分别达到了99.68%和95.99%。结论 针对鞋印花纹图像特点,提出了一种通过寻找各类之间的隔离带进行自动聚类的算法,并在实际应用中取得了很好的效果。且算法性能受参数的变化以及类的形状影响较小。本文算法同样适用于具有类似特点的其他数据集的自动聚类。

关键词:鞋印花纹图像  聚类  隔离带  K步稳定  可达半径  类集成树  任意形状类

AbstractObjective Shoeprints serve as vital evidence in forensic investigations, and determining how a massive amount of shoeprint images can be clustered automatically through long-term accumulation has become one of the urgent tasks of criminal technology. Unlike other image sets, the number of shoeprint categories is not only considerable but also unknown. Shoeprint images in the feature space are distributed inhomogeneously and sparsely, but the quantity of each class is low. For these reasons, most existing clustering algorithms cannot satisfactorily cluster shoeprints. In this study, an automatic clustering method is proposed to divide shoeprint sets effectively based on an analysis of the distribution of shoeprint images in the feature space. Method Through statistics on labeled shoeprint-image databases, we found that shoeprint sets of different patterns do not intersect, and a blank region, where no shoeprints exist, is present between every two classes. Blank regions are called margins in this paper. The core objective of the proposed algorithm is to determine the margins between classes and use them to divide a shoeprint set. The process involves the following steps:1) dividing the shoeprint set with monotonically increasing or descending thresholds, which are used to classify two shoeprint images into the same cluster; 2) searching for the cluster that does not change with K consecutive partitions; 3) outputting the stable cluster and removing the shoeprints belonging to the output stable cluster from the dataset; 4) choosing the next threshold and dividing the remaining dataset; 5) returning to step 2) until the remaining set is empty. Result Experimental results on two kinds of publicly available databases and one real shoeprint database which comprises 5792 images, have shown that the proposed algorithm outperforms state-of-the-art clustering algorithms on common clustering evaluation measures. The precision and F-measure of the proposed algorithm on the real shoeprint database are approximately 99.68 and 95.99 percent, respectively. Conclusion In this study, based on the distribution of shoeprint images in the feature space, an automatic clustering algorithm that searches for margins between clusters to divide a dataset is proposed. The proposed algorithm achieves a comparable or even better performance on clustering a shoeprint dataset than its competitors. Experiments have also shown that the performance of the algorithm is less sensitive to the parameter and shape of the clusters. The algorithm can also be applied to clustering other datasets of images with characteristics similar to those of shoeprint images.

Key wordsshoeprint image  clustering  margin  K-steps stabilization  reachable radius  cluster aggregation tree  clusters of arbitrary shape

文章编号： 0258_7106 (2016) 01_0018_15 中图分类号： P618.41 文献标志码：A

投稿时间：2015-08-17修订日期：2016-01-11 改回日期：2015_07_11

基金项目

**通讯作者耿新霞， 女， 1979年生， 助理研究员， 成矿规律研究方向。 Email： gen gxinxia@cags.ac.cn