-Means Based Fingerprint Segmentation with Sensor Interoperability

Abstract

A critical step in an automatic fingerprint recognition system is the segmentation of fingerprint images. Existing methods are usually designed to segment fingerprint images originated from a certain sensor. Thus their performances are significantly affected when dealing with fingerprints collected by different sensors. This work studies the sensor interoperability of fingerprint segmentation algorithms, which refers to the algorithm's ability to adapt to the raw fingerprints obtained from different sensors. We empirically analyze the sensor interoperability problem, and effectively address the issue by proposing a -means based segmentation method called SKI. SKI clusters foreground and background blocks of a fingerprint image based on the -means algorithm, where a fingerprint block is represented by a 3-dimensional feature vector consisting of block-wise coherence, mean, and variance (abbreviated as CMV). SKI also employs morphological postprocessing to achieve favorable segmentation results. We perform SKI on each fingerprint to ensure sensor interoperability. The interoperability and robustness of our method are validated by experiments performed on a number of fingerprint databases which are obtained from various sensors.

1. Introduction

An important preprocessing step in an automatic fingerprint recognition system is the segmentation of fingerprint images [1, 2]. Effective segmentation cannot only reduce the time of subsequent processing, but also significantly improve the reliability of feature extraction. Segmentation is the decomposition of an image into various components. A captured fingerprint image usually consists of two components, which are called the foreground and the background. The foreground is the component that originated from the contact of a fingertip with the sensor, and the noisy area usually around the borders of the image is called the background.

A number of fingerprint segmentation methods are known from literature, which can be roughly divided into block-wise methods [3–12] and pixel-wise methods [13–16]. Block-wise methods first partition a fingerprint image into nonoverlapping blocks of the same size, and then classify the blocks into foreground and background based on the extracted block-wise features. Pixel-wise methods classify pixels through the analysis of pixel-wise features. The commonly used features in fingerprint segmentation include gray-level features, orientation features, frequency domain features, and so forth.

Depending on whether the label information is used, the fingerprint segmentation methods can also be treated as unsupervised [4, 10, 14, 15, 17] and supervised ones [6–9, 11, 13, 16]. Unsupervised segmentation usually chooses an appropriate threshold for a certain feature; according to the threshold, the blocks or pixels are divided into background and foreground. Note that unsupervised segmentation does not require any label information. Supervised methods train linear or nonlinear classifiers based on labeled pixels or blocks. The classifier is then used to predict new blocks or pixels. Note that most existing methods are designed to segment fingerprints originated from a certain sensor; while the models have to be retrained as the sensor changes (It is worth noting that the various fingerprint databases are usually collected by different sensors.).

The problem of biometric sensor interoperability has attracted a lot of research interest during the past few years [18–27]. Sensor interoperability refers to "the ability of a biometric system to adapt to the raw data obtained from a variety of sensors" [18]. Fingerprint recognition systems, which are usually designed for fingerprints originating from a certain sensor, also suffer from the sensor interoperability problem. The performances of fingerprint segmentation, enhancement, and matching may drop significantly when dealing with fingerprints collected by different sensors, due to the various image qualities, resolutions, and gray-levels.

Ross and Jain [18] raised the sensor interoperability problem in fingerprint recognition by matching fingerprint images originated from an optical sensor and a solid-state sensor, respectively. The experiments showed that the matching performance drastically decreases as the sensor changes. Later, the work in [19, 20] tried to improve sensor interoperability of fingerprint matcher through a Thin Plate Splines (TPS) based nonlinear calibration scheme. More works dedicated in this research field can be found in [21–27].

Note that one of the assumptions in interoperable fingerprint matching is that the fingerprint images have been properly segmented. However, fingerprint segmentation also suffers from the sensor interoperability problem. On one hand, a feature obtained from different sensors may be confused, resulting in that a block or a pixel may be considered foreground under the view of one sensor while classified as background from another sensor. On the other hand, most segmentation methods train and test on one fingerprint database collected by a certain sensor, and it is inevitable to retrain the models when dealing with other databases. Therefore, the sensor interoperability problem has to be properly addressed by designing robust fingerprint segmentation methods especially for applications with various sensors. However, to the best of our knowledge, existing works for sensor interoperability problem mainly focus on the area of fingerprint matching, leaving the sensor interoperability problem in fingerprint segmentation remains untouched. A recent work [28] studied the feature selection for sensor interoperable fingerprint segmentation, but it is a different problem from the one we addressed here.

This work first empirically analyzes the sensor interoperability problem in fingerprint segmentation. To effectively address this problem, we propose a -means based segmentation method called SKI, that is, segmentation based on -means for sensor Interoperability. SKI clusters foreground and background blocks of a fingerprint image based on the -means algorithm. Here a fingerprint block is represented by a 3-dimensional feature vector consisting of block-wise coherence, mean, and variance (which are abbreviated as CMV). SKI employs morphological postprocessing to achieve favorable segmentation results. We perform SKI on each fingerprint to ensure sensor interoperability. The sensor interoperability and robustness of SKI are validated by experiments performed on a number of fingerprint databases which are obtained from various sensors.

This paper is organized as follows. Section 2 raises the sensor interoperability problem through empirical studies. Section 3 proposes the SKI method, followed by experiments reported in Section 4. Finally, Section 5 concludes this work and discusses future directions.

2. The Sensor Interoperability Problem

Due to the various imaging principles, fingerprints obtained from different sensors usually have different resolutions, sizes, and feature distributions. For example, the two images shown in Figure 1 are originated from two different sensors, and it can be observed that the background gray-level of the left image is higher than the right one. Thus, we would not be able to achieve desirable segmentation accuracy on the two fingerprint images simultaneously if a fixed threshold is set for gray-level mean.

Figure 1

Two fingerprint images originated from two different sensors.

In order to investigate the influence of various sensors on the segmentation performance, we randomly select fingerprints from a number of open databases and analyze the feature histograms and distributions of these fingerprints. Firstly, each fingerprint image is partitioned into nonoverlapping blocks of the same size, and for each block, the coherence, mean, and variance features are extracted. Then the blocks are manually labeled into two classes: foreground blocks and background blocks. Here three volunteers were asked to label the segmented blocks, and then we used a majority voting scheme to decide the ground truth labels: a block is regarded as foreground if two or more volunteers consider it as foreground; otherwise, the block is background. Finally we draw histogram and distribution for the labeled blocks of images originating from same sensor as well as from different sensors, and investigate sensor interoperability problem existing in current fingerprint segmentation methods.

2.1. Features

The features of coherence, mean, and variance (i.e., CMV) are proposed in [13] to capture texture and gray-level information of local image area around a pixel. Here we modify the definition of CMV and represent each block with a 3-dimensional feature vector consisting of block-wise coherence, mean, and variance. In detail, a fingerprint image is partitioned into nonoverlapping blocks with the same size of  pixels ( is a positive integer, , usually , 12, 16), and for each block, the coherence, mean, and variance are extracted as follows.

(1) Coherence

The coherence measures how well the pixel gradients in a block are pointing in the same direction. The block-wise coherence is defined as

(1)

where , ,, and is the local gradient of a pixel based on Sobel operator with masks and , respectively. We set if .

(2) Mean

Let denotes the gray-level of a pixel in block , then the block-wise mean for is given by

(2)

(3) Variance

The block-wise variance for block is defined as

(3)

where is defined the same as in (2).

In addition, we normalize the CMV values into using Min-max normalization in order to carry on the following processes.

2.2. Fingerprint Databases

Experiments in this subsection are conducted using three open fingerprint databases, that is, FVC2000 [29], FVC2002 [30], and FVC2004 [31]. Each open database is composed of 4 subdatabases, where the first 3 subdatabases are collected from three different types of sensors, and the last subdatabase is generated synthetically. For example in FVC2000, four subdatabases imply the up-to-date fingerprint sensing techniques: DB1 and DB2 were collected from two small-size and low-cost sensors, that is, optical sensor and capacitive sensor; DB3 was collected from a higher quality large area optical sensor; DB4 was synthetically generated. Each database consists of a training set of 80 images and a test set of 800 images. The sensors used in the open databases are presented in Table 1.

Table 1 FVC fingerprint database sensor list.

In our experiments, we randomly select 10 fingerprint images from each real subdatabase to construct a database containing 90 images, and the empirical studies are described in the next subsection.

2.3. Experiments and Analysis

We partition each of the 90 fingerprint images into nonoverlapping blocks with the same size of , and manually label the foreground blocks and background blocks. The numbers of foreground/background blocks in every subdatabase are listed in Table 2. In the following, we will compare the CMV histograms and distributions of a single fingerprint, fingerprints from the same subdatabase, fingerprints from the same database, and fingerprints from different databases, respectively.

Table 2 Average number of foreground and background blocks over the 10 images selected from each subdatabase.

We first investigate the CMV histograms and distribution for each fingerprint image. We give a sample result in Figure 2 which shows the CMV histograms and distribution of 81_3.tif in FVC2000 DB1. It shows that for a fair-quality fingerprint image, the CMV distribution of foreground and background blocks are separated into two distinguished clusters. The CMV histograms also show that even under a single view of coherence (mean or variance), the foreground and background blocks are still statistically separable. Actually in most cases, the foreground and background blocks collected from a single fingerprint are statistically separable, and thus, a good segmentation performance can be achieved for this single fingerprint image.

Figure 2

CMV histograms and distribution of FVC2000 DB1 81_3. tif.

Then we compare the CMV distribution of a single fingerprint with that of the 10 fingerprints in the same subdatabase. For example, Figure 3 shows the CMV histograms and distribution of the 10 fingerprints in FVC2000 DB1. Compared with Figure 2 and experimental results of the other 9 fingerprints in FVC2000 DB1, we can see that the feature distributions of multiple fingerprints from the same subdatabase are consistent. Thus, it is not difficult to understand that traditional segmentation methods can achieve good segmentation performance on fingerprint images in the same subdatabase.

Figure 3

CMV histograms and distribution of the 10 fingerprints in FVC2000 DB1.

For fingerprints obtained from different sensors, the extracted feature may be confused due to the various image qualities, resolutions, and gray-levels. For example, Figure 4 shows the CMV histograms and distribution of fingerprints in the three subdatabases of FVC2000. It can be found that the CMV distributions of the three subdatabases overlap with each other. Therefore, when dealing with fingerprints collected by different sensors, traditional fingerprint segmentation methods cannot guarantee good performance without adjusting thresholds or retraining classifiers; and this is primarily caused by the sensor interoperability problem.

Figure 4

CMV histograms and distribution of the fingerprints in FVC2000 DB1, DB2, and DB3.

Figure 5 provides the CMV histograms and distribution of all the 90 fingerprints. It shows that the overlaps become more and more complex as the number of different sensors increases, under which situation the segmentation turns out to be more and more difficult.

Figure 5

CMV histograms and distribution of all the 90 fingerprints.

As mentioned before, the sensor interoperability problem should be properly addressed in order to deal with different sensors. However, existing methods are usually designed to segment fingerprints originated from the same sensor, and the model must be changed to achieve desirable performance for other sensors. For example, Chen et al. [8] proposed to segment fingerprints with a linear classifier trained on block-wise features of clusters degree, mean, and variance, and the parameter settings for FVC2002 DB1 and FVC2002 DB3 are [3.723, , 0.071, ] and [1.152, , 0.067, ], respectively. Therefore, facing with the sensor interoperability problem in fingerprint segmentation, a good fingerprint segmentation algorithm must be robust enough to handle the diversity produced by various sensors.

3. The Proposed Method

Two directions can be employed to address the sensor interoperability problem: () extracting features with interoperability and () designing segmentation methods with interoperability. Our recent work [28] follows the first strategy, and this paper proposes a new segmentation method SKI using unsupervised clustering technique.

Clustering has been attracting a lot of research interests in data mining and pattern recognition community. Unsupervised clustering explores structures in data without the need of labeled information [32]. Indeed, fingerprint segmentation can be regarded as a two-class clustering task, and the goal is to distinguish the foreground cluster from the background one. Thus, a clustering algorithm can be performed on each fingerprint image and the segmentation can be achieved accordingly. This procedure not only avoids training a universal model for one or more fingerprint databases, but also weakens the impact of various sensors on the segmentation performance. Inspired by this, we propose SKI which is an effective clustering-based fingerprint segmentation method with sensor interoperability. The next subsection describes the -means algorithm, following by which SKI is detailed.

3.1. The -Means Algorithm

Depending on the clustering rules, existing clustering algorithms can be roughly divided into three categories: hierarchical clustering, partition based clustering, and grid-based clustering. The -means algorithm proposed by MacQueen [33] is a commonly used partition-based clustering method. The process of -means is presented as follows. Firstly, -means chooses the number of clusters, that is, , and determines the cluster centroids; then it assigns each data point to the nearest cluster center and recomputes the new cluster centers, and this produce is repeated until some convergence criterion is met (usually that the assignment has not changed). The main advantages of this algorithm are its simplicity and speed which allows it to run on large datasets.

In our fingerprint segmentation task, the background blocks and foreground blocks of most fingerprints (fair quality) fall into two clusters with high density (as shown in Figures 2 and 3), and the number of clusters can be directly set to be 2. Also, the statistical separability of the two clusters helps the -means algorithm to achieve good clustering performance.

3.2. SKI

We first partition the fingerprint images into nonoverlapping blocks with the same size of , and the block-wise CMV are extracted according to (1), (2), and (3) to form the feature vectors. Then for each fingerprint image, -means is performed to cluster the blocks into two clusters, that is, background and foreground cluster. Since the outputs of -means are two clusters without specifying background or foreground, we need a preliminary classification process to determine which cluster indicates the foreground blocks. Here we consider the 8 neighborhoods of the center (with respect to the fingerprint image) fingerprint block, and the cluster that receives the most votes is assigned to be foreground. For example, let cluster 1 and cluster 2 denote the output of -means; if 6 of the 8-neighborhood blocks belong to cluster 2 and the other 2 belong to cluster 1, then cluster 2 will be regarded as the foreground cluster. SKI also employs morphological postprocessing to eliminate noisy blocks. Noisy blocks are usually presented as "isolated" background or foreground blocks. Here an isolated block is defined as a foreground block with less than four foreground neighborhoods (out of the 8 neighborhoods) or a background block with less than four background neighborhoods. We relabel the isolated foreground (or background) blocks to be background (or foreground) and repeat this process until the assignments no longer change. The framework of SKI is presented in Figure 6.

Figure 6

Framework of SKI.

4. Experiments

We first compare SKI with state-of-the-art methods to show the effectiveness of the proposed method. Then the performance of SKI using different feature combinations is studied. In the end of this section, we show the sensor interoperability and robustness of SKI with some sample segmentation results. All the experiments are conducted on a Pentium 4 machine with a 2.0 GHz CPU and 1 GB memory.

4.1. Comparison to State-of-the-Art Methods

In the experiments, SKI is compared with Chen's method [8], which is a representative block-wise segmentation method and trains a linear classifier for segmentation. The linear classifier uses the criteria of minimal number of misclassified blocks. For each of the subdatabase of FVC2002, we randomly select a number (according to [8], 5 for DB1, 10 for DB2, and 30 for DB3) of fingerprint images to train a linear classifier using Chen's method, and then SKI and Chen's method are used to segment 10 other randomly selected fingerprints. Note that SKI does not require any training process. Following [8], the segmentation performance is measured by error rate, which is defined as the proportion of misclassified blocks:

(4)

where denotes the number of misclassified blocks in the evaluated fingerprints, and is the total number of blocks.

The segmentation error rates are presented in Table 3, where the smallest error rate on each subdatabase has been boldfaced. It shows that SKI is superior to Chen's method on all the subdatabase.

Table 3 Average segmentation error rates (mean ± standard deviation).

We also conduct statistic -tests to gain further insight. For each of the subdatabase, a paired -test at 95% significance level is conducted on the recorded error rate series and the results are reported in Table 4. Here is the indicator of significance. () indicates that SKI is significantly better (worse) than Chen's method, and means that there is no significant difference between the two methods. is the probability for rejecting the hypothesis that "SKI significantly outperforms Chen's method". Table 4 clearly shows that SKI significantly outperforms Chen's method on all the subdatabase. With the above observations we can conclude that SKI is a highly effective method for fingerprint segmentation.

Table 4 Statistic -tests results of SKI against Chen's method.

Apart from the segmentation performance, computational time is also an important factor in an automatic fingerprint recognition system. Table 5 reports the average off-line training time and on-line segmentation time of SKI as well as Chen's method. Although the on-line segmentation time of SKI is about twice as that of Chen's method, SKI has three advantages over Chen's method: (i) there is no training stage in SKI, (ii) no label information is required by SKI as an unsupervised learning method, and most importantly, (iii) SKI performs better when dealing with the sensor interoperability problem.

Table 5 Average off-line training time and on-line segmentation time (in seconds) of SKI and Chen's method.

We also test the cross-database segmentation performance of Chen's method. Here cross-database segmentation refers to the segmentation of fingerprint images from one subdatabase using a classification model trained on another subdatabase. Note that in previous experiments, we have trained three linear classifiers on the 5, 10, and 30 fingerprints of DB1, DB2, and DB3, respectively. Here we denote the classifiers as Classifier1, Classifier2, and Classifier3, and evaluate their performances on cross-databases. Besides, we train a Classifier4 on the abovementioned 45 fingerprint images. The results are presented in Table 6, where the smallest error rate on each subdatabase has been boldfaced.

Table 6 Average error rates of Chen's method for cross-database segmentation.

Table 6 shows that the linear classifier achieves the best performance on the subdatabase from which the classifier is trained. If a segmentation method is trained on a mixture of databases, its results might be better to some extent, but usually not as good as using the classifier to train samples and test samples from the separated subdatabase. Furthermore, it would be troublesome to retrain the classifier when using a new sensor in real production environment. In contrast, SKI avoids this problem by performing the -means algorithm on each fingerprint.

4.2. Using Different Feature Combinations

In this subsection, we perform SKI using different feature combinations, that is, coherence only, mean only, variance only, the combination of coherence and mean, and the combination of coherence, mean, and variance. We conduct this experiment using a representative fingerprint image, which is 82_1.tif from FVC2000 DB3. Table 7 reports the segmentation error rates. The segmentation results are shown in Figure 7, where Figure 7(a) is the original image, and Figures 7(b)–7(f) are the segmented images using different feature combinations. The results show that SKI achieves better performance using CMV features as compared with the other feature combinations. Thus, we can conclude that, for fair quality fingerprints, using only gray-level information or texture information may achieve desirable segmentation results; however, it is suggested to use CMV when dealing with noisy fingerprints.

Table 7 Segmentation error rates of SKI on fingerprint image FVC2000 DB3 82_1.tif using different feature combinations.

Figure 7

Segmentation results of SKI on fingerprint image FVC2000 DB3 82_1. tif using different feature combinations, that is, coherence only, mean only, variance only, the combination of coherence and mean, and the combination of coherence, mean, and variance.Orignal imageSegmented image using coherence onlySegmented image using mean onlySegmented image using variance onlySegmented image using coherence and meanSegmented image using CMV

4.3. Sample Segmentation Results

Some sample segmentation results of SKI are presented in Figure 8. Here the fingerprint images are collected from different subdatabases of FVC2000, FVC2002, FVC2004, NIST4, and NJU2001(Fingerprint database of Nanjing University. The sensor type is ZY202-B; the resolution is 500 dpi with size .), where different fingerprints are captured by different sensors. Desirable segmentation results are achieved on these fingerprints, reflecting that SKI is a robust method with interoperability dealing with various sensors.

Figure 8

Sample segmentation results of SKI.

5. Conclusion

This work studies the sensor interoperability problem in fingerprint segmentation. We investigate the problem by analyzing traditional segmentation methods without sensor interoperability. We then propose a robust segmentation method called SKI to segment fingerprint images captured from different sensors. SKI is applicable to network based fingerprint recognition systems (in which fingerprint sensors may vary for different users), since it avoids adjusting threshold or retraining classifier for various sensors. To the best of our knowledge, this is the first work tackling the sensor interoperability problem in fingerprint segmentation. Experimental results also show the sensor interoperability, robustness, and effectiveness of SKI.

Most existing fingerprint segmentation methods are statistically based, which require labeled foreground and background blocks as prior knowledge. They study the feature distribution of the labeled foreground and background blocks (or pixels) to assign thresholds or train classifiers for the segmentation of new fingerprint images. It has been shown that their performances are limited when dealing with fingerprints collected by various sensors simultaneously since the feature values are usually statistically inseparable, which has been known as the sensor interoperability problem in fingerprint segmentation. The SKI method proposed in our research effectively addresses this problem by taking the following two advantages. On one hand, our method is not a statistical-based method as it applies -means algorithm on each fingerprint. We can segment a fingerprint with SKI as long as we have well-defined features to distinguish foreground blocks from background blocks for this particular image. In this work, we choose coherence, mean, and variance to describe texture information and grey-level information of a fingerprint block, respectively, which contribute to separate the foreground cluster from the background cluster even for fingerprints obtained from different sensors. On the other hand, there are naturally two clusters in the fingerprint segmentation task, that is, foreground cluster and background cluster, and as a result, we can directly set the cluster number as 2 in the -means algorithm, helping SKI to achieve high accuracy clustering with relatively small time consumption.

Note that the processing time of the -means algorithm mainly depends on the choice of initial cluster centroids. Thus, we will try to speed up SKI by automatically selecting a background block and a foreground block as the initial centroids. Besides, we find in our experiments that coherence is a feature with sensor interoperability. In so saying, under the view of coherence, the background and foreground blocks of a fair-quality fingerprint image are statistically separable, even though they are collected from various sensors. Our method takes advantages of this characteristic when dealing with the fingerprint sensor interoperability problem. Therefore, extracting other features with sensor interoperability is another promising way to further improve the performance of SKI.