Separation of Overlapped Fingerprints for
Forensic Applications

J.Vanitha; S.Thilagavathi

Separation of Overlapped Fingerprints for Forensic Applications

J.Vanitha¹, S.Thilagavathi²
Assistant Professor, Dept. Of ECE, VV College of Engineering, Tisaiyanvilai, Tamilnadu, India

Related article at Pubmed, Scholar Google

Visit for more related articles at International Journal of Advanced Research in Electrical, Electronics and Instrumentation Engineering

Abstract

Normally, fingerprint images contain a single fingerprint or a set of non overlapped fingerprints. There may be situations where overlapped fingerprint can be obtained. It can be frequently encountered in the latent fingerprint lifted from crime scenes. It is essential to separate those overlapped fingerprint into its component fingerprints. The challenging work in separating overlapped fingerprint is the separation of mixed orientation field into its component orientation field. In this paper, Relaxation labelling algorithm is proposed to perform the task of separation. Initially, we use Local fourier analysis method in order to estimate the initial orientation field. Then Relaxation labelling algorithm is employed to detach the initial orientation field. Finally, by using Gabor filter the required component fingerprints are obtained.

Keywords

Fingerprint separation, latent fingerprints, orientation field, Relaxation labelling, Gabor filter.

INTRODUCTION

Fingerprint refers to the friction ridge skin of human finger or its impression. A fingerprint is a type of oriented texture with locally smooth and intervening ridges and valleys. Fingerprints are both unique and permanent, making it an ideal biometric trait for person identification. Fingerprint recognition has been successfully deployed in various applications, such as entry control, time and attendance, computer login, forensics, and airport security. One challenging problem now-a-days is the processing and matching of overlapped fingerprints. When the same location of a surface is touched by two or more fingerprints at different times, the developed latent image may contain overlapped fingerprints. It may also occur in the live scan fingerprint images when the surface of fingerprint sensors contains residue of preceding fingerprints.

Verifinger is unable to segment the two component fingerprints and thus he fails to extract the ridges in the overlapped region. Thus it creates a challenge to the existing fingerprint recognition algorithm. Forensic scientists have proposed a method to separate overlapped fingerprints using the gold material. This technology is very interesting and is not convenient since it works only for some specific fingerprints. Fan et al. proposed an algorithm to separate overlapped fingerprints based on image enhancement using a manually marked orientation field. However, it is tedious and time consuming for us to manually mark the orientation field of each component fingerprint in the overlapped fingerprint image. Geng et al. proposed to use morphological component analysis to separate overlapped fingerprints. Experimental results showed that their algorithm can only separate that component fingerprint which dominates the overlapped image. Singh et al. suggested the use of independent component analysis (ICA) to separate overlapped fingerprints, but they did not provide a separation algorithm.

In this paper, we proposed an algorithm to separate overlapped fingerprints and evaluated it using both real overlapped latent fingerprints and simulated overlapped fingerprints. The algorithm is based on two assumptions which are both reasonable and practical.

1.The overlapped fingerprint image consists of atmost two fingerprints.

2. There exist differences between the orientation fields of the two component fingerprints in the overlapped area.

The proposed algorithm consists of the following three steps:

1.Region segmentation: The overlapped fingerprint image is divided into background region, overlapped region,non overlapped regions of two component fingerprints.

2.Initial orientation field estimation: By using Local Fourier analysis method the initial orientation field of the given overlapped fingerprint image is estimated.

3.Orientation field separation: A relaxation labeling method is then employed to label the initial orientation field in to two classes. Based on the result, the initial orientation field is decomposed into two component orientation fields.

4.Fingerprint separation: Finally, the two component fingerprints are separated by employing Gabor filters.

In the Fig 1, it shows the flow model for the proposed algorithm.

OVERLAPPED FINGERPRINT SEPARATION

REGION SEGMENTATION:

The region masks are manually marked for the two overlapped fingerprints. Manually marking region mask is a common practice in latent fingerprint community. The overlapped fingerprint image consists of two regions, the overlapped region and the non overlapped region of two component fingerprints. The overlapped region is the common region of the two masks and it contains the overlapped part of the two fingerprints and the non overlapped region contains only one fingerprint.

In the Fig.2, it gives the procedure to divide the regions.

An overlapped fingerprint image is segmented into non overlapping blocks of 16x16 pixels. The block in the overlapped region is called overlapped block and the block in the non overlapped region is called non overlapped block. There exists one dominant orientation in the non overlapped block and two dominant orientations in the overlapped block.

INITIAL ORIENTATION FIELD ESTIMATION:

A Fingerprint orientation field is a matrix, whose value at (x,y) denotes the dominant ridge orientation at point (x,y) [2]. The orientation field of an overlapped fingerprint image is different from that of the orientation field of a single fingerprint image in that it contains one dominant orientation in the non overlapped region and two dominant orientations in the overlapped region. In this paper, we have assumed that the region masks of the component fingerprints have been manually marked. After the creation of region mask we have used Local Fourier analysis method in order to extract the initial orientation field.

We have taken the input overlapped fingerprint image and then is divided in to non overlapping blocks of 16x16 pixels. The ridge present in an each block can be represented by a 2D sine wave. Centered at each block, the local image in the 64x64 window is then multiplied by a Gaussian function (σ = 16). The discrete Fourier transform (DFT) F(u,v) of the resulted image is computed and the amplitude of the low frequency components is set to zero. Also, the local maxima points with the largest amplitude are found in the frequency domain. Each point can be represented by a 2D sine wave w(x,y)= a. sin(2Πf(sin(θ)x + cos(θ)y) + Φ), where a, f, θ, Φ represents the amplitude, frequency, orientation and phase respectively. It can be determined by the below formulas,

In the Fig.3, it shows the estimation of two dominant orientations in an overlapped block.

ORIENTATION FIELD SEPARATION:

The initial orientation field thus contains two dominant orientations in each overlapped block. In this paper, we have proposed the relaxation labelling algorithm in order to separate the initial orientation field in to two orientation fields corresponding to the two individual fingerprints.

Relaxation labeling is an iterative procedure. It computes the label assignment P iteratively until it is convergent. The process initially starts with some initial probabilities such as 0.6, 0.4........The algorithm specifies how the label probabilities are updated at each instant. It is explained in Algorithm 1.

Separating overlapped orientation field

1.Problem modelling: The initial orientation field O0 is a m x n x 2 matrix. Thus the object set is O=(O1,O2) and the label set is Λ=(1,2). To separate the initial orientation field we have to label each object of O with exactly one label 1 or 2 of Λ.

2.Building Compatility Coefficients: It is known to us that the efficiency of the relaxation process is greatly affected by the choice of compatibility coefficients. The compatibility coefficient matrix RIJ = R(i.n.2+j.2+k)(i`.n.2+j`.2+k`) between object O(i,j,k) and O(i’,j’,k’) is defined as

Where s is the support when the object O(i,j,k) and O(i’,j’,k’) have the same label and 1-s is the support for different labels. Thus, S is computed as

Merging orientation fields: It is efficient for the user if we separate only in the overlapped region. This is based on two considerations. First, there is only one orientation in the non overlapped region. Second, processing only the overlapped region can save much computation time. The two separated orientation fields in the overlapped area should be merged with the two orientation fields in the nonoverlapped area to finalise the orientation field separation process. The boundary Bj, j=1,2, between M0 and Mn,j(x,y) is defined as

Where D is the parameter that controls the width of the boundary, here we are assigned it as D=6 blocks.

in the overlapped region; c) one of the non overlapped orientation fields; d) the other non overlapped orientation field. (e)- (h) are the corresponding region masks of (a)-(d) respectively

In the Fig.4, it gives orientation field in the overlapped and non overlapped region

Fig 5: (a): Boundary between the overlapped region and one of the two nonoverlapped regions

(b): Boundary between the overlapped region and the other nonoverlapped region.

There are two possible combinations that can be chosen to merge the orientation fields. The two possible combinations are: (i) Oo,1 with On,1 and Oo,2 with On,2, and (ii) Oo,1 with On,2 and Oo,2 with On,1. For each combination, we compute the compatibility defined as,

If C1 < C2, we choose the first combination, otherwise we choose the second combination. After obtaining the two component orientation fields the averaging filter is used to remove noise in each of the two orientation fields.

In the Fig 7. and Fig 8, it shows the Separating overlapped fingerprints by Gabor

The Proposed algorithm is given below:

Initialization: set t=0, obtain initial label probabilities:

P(0) = (p1(0),p2(0),.....,pN(0)).

While true do

1) Selection of labels :

For i= 1,2,...,N do

Choose a label at random based on the current label probabilities pi(t).

End

2) Calculation of responses:

For i= 1,2,.....,N do

Let q be the label selected for Oi in step 1) and compute the response βiq to Oi as

Βiq = (1/N) ΣjRij(q,sj),

Where sj is the label selected for object Oj in step 1).

End.

3) Updating of label probabilities:

For i= 1,2,...,N do

Let q be the label selected for Oi in step 1) and Pi(t) is updated as

Piq(t+1) = Piq(t) + αβiq(1 – Piq(t)),

Pir(t+1) = Pir(t) - αβiqPir(t), r≠q.

End

4) Iteration:q

If probability vectors have converged then

Break.

End

Else

t = t+1.

End

FINGERPRINT SEPARATION

Contextual filtering using 2D Gabor filters is very effective for fingerprint enhancement [2]. Two important parameters of 2D Gabor filters are local ridge orientation and frequency. When the ridge orientation field and ridge frequency map are obtained, Gabor filtering can connect the broken ridges and remove intervening ridges. Finally, two overlapping fingerprints have been successfully separated.

CONCLUSION

Overlapped fingerprints which are encountered from the crime scenes are not of good quality. However, separating the overlapped fingerprints is a very challenging problem for the existing algorithms. We have proposed a relaxation labeling algorithm for separating overlapped fingerprints. Byapplying the relaxation labelling algorithm over the initial orientation field output obtained from the Local fourier analysis we obtain two separated orientation fields. Then the two component fingerprints are separated by filtering the overlapped fingerprint image using the Gabor filter.

References

F.Chen, J.Feng, A.K.Jain, J.Zhou and J.Zhang,”Separating overlapped fingerprints,” IEEE Trans. On Information forensics and security, vol.6, no.2, June 2011.
D. Maltoni, D. Maio, A.K.Jain, and S. Prabhakar, Handbook of Fingerprint Recognition (Second Edition). New York: springer, 2009.
L. Hong, Y. Wan, and A.K.Jain, “Fingerprint image enhancement: Algorithm and performance evaluation,” IEEE Trans. Pattern Anal. Mach. Intell., vol.20, no.8, pp.777-789, Aug.1998.
A.K. Jain and J. Feng,” Latent palmprint matching,” IEEE Trans. Pattern Anal. Mach. Intell., vol.31, no.6, pp.1032-1047, Jun 2009.
M.Pelillo, F.Abbattista, and A. Maffione,” Evolutionary learning for relaxation labeling processes,” in Proc. AI*IA, 1993, pp.230-241.
M.Pelillo and M. Refice,”Learning compatibility coefficients for relaxation labeling processes,” IEEE Trans. Pattern Anal. Mach. Intell., vol.16, no.9, pp.933-945, sep.1994.
J.Zhou and J. GU,” A model – based method for the computation of fingerprints,” IEEE Trans. Image Process. vol. 13, no.6, pp.821-835, Jun.2004.
Y.Wang, J. Hu, and D.Philips,”A fingerprint orientation model based on 2D Fourier expansion(FOMFE) and its application to singular-point detection and fingerprint indexing,” IEEE Trans. Pattern Anal. Mach. Intell., vol.29, no.4, pp.573-585, Apr.2007.
A.Rosenfeld, R.A.Hummel, and S.W. Zucker, “Scene labeling by relaxation operations,” IEEE Trans. Sys., Man, Cybern. vol.6, no.6, pp.420- 433, Jun. 1976.
M. Thathachar and P.Sastry,” Relaxation labeling with learning automata,” IEEE Trans. Pattern Anal. Mach. Intell., vol.8, no.2, pp.256-268, Feb.1986.
J. Daugman, “Uncertainty relation for resolution in space, spatial frequency and orientation optimized by two-dimensional visual cortical filters,” J.Opt.Soc.Amer.A, vol.2, no.7, pp.1160-1169, 1985.