1 Introduction

Biometric [13, 36] is a combination of two words i.e. bio meaning life and metrikos meaning measurement. Thus, it can be defined as any physical and/or behavioral characteristic of a person which can uniquely identify a person or identity. There has been numerous applications of this concept in access control, border immigration control, corpse identification, surveillance, forensic sectors [36], human computer interaction [50], behavior analysis [6] etc. Due to these burgeoning applications of biometric system, researchers from various communities such as pattern recognition, statistics, machine learning, computer vision and so on have come together to solve this fascinating problem. In a typical biometric recognition system, a user presents his biometric such as face [50], fingerprint[34], iris[31], voice [9] etc. to the system and recognition is performed by matching the test entity against the stored representations. Biometric recognition is typically performed with the help of digital images captured by some biometric sensor such as camera. Since the biometric images involve high dimensions and only few samples for an identity are available for training, this leads to the problem of curse of dimensionality or Small Sample Size (SSS) [2] in literature.

SSS problem can be alleviated by either increasing the number of samples or by reducing the dimensions of the biometric image. Due to the intricacies involved in collection of biometric samples, this option is less feasible. On the other hand, it is viable to reduce the dimensions of biometric image using some dimension reduction technique. A comprehensive survey of linear dimensionality reduction techniques is carried out by Cunningham and Ghahramani [5]. Several techniques such as Locality Preserving Projection (LPP) [11], principal component analysis (PCA) [33], canonical correlation analysis (CCA) [12], Fisher’s linear discriminant analysis [7], multidimensional scaling [4], slow feature analysis (SFA) [46, 47] etc are presented in their research work [5]. It is shown that the linear dimensionality reduction can be modeled as a matrix optimization problem. Besides, some methods based on selection and weighting of facial features are also proposed in literature by Leng et al. [24, 25] in which weighted discrimination power analysis has been employed in Discrete Cosine Transform (DCT) domain for feature extraction. Locality Preserving Projection (LPP) is a simple and popular technique of dimensionality reduction in which the data points are assumed to lie on a high dimensional manifold. The objective in LPP is to find optimal linear approximation to the Eigenfunctions of the Laplace Beltrami operator on the manifold. LPP has been successfully applied in face and handwriting recognition [11], palm vein verification [1] etc.

With increasing popularity of the biometric systems, there has been a growing concern over security and privacy of people. This is due to the fact that biometrics are permanently associated with a person in contrast to credit cards and passwords which can be blocked and reissued when stolen. If the biometric pattern is stolen by some intruder, then it is highly probable that he can deceive the biometric recognition system and gain access to secure areas. To overcome these limitations, the concept of cancelable biometric [32] have been suggested in literature . In cancelable biometric, an individual is issued a biometric template which is subsequently used by that individual for recognition instead of the original biometric. If this template is stolen or compromised, the same can be reissued in the same way as credit card or password etc. Several techniques have been suggested for cancelable biometric template generation in literature. A comprehensive survey of cancelable biometric template generation is given by Patel et al. [32] in which cancelable biometric techniques have been broadly classified into ten categories viz. (i) Non-invertible Geometric Transforms (ii) Random Projections (iii) Cancelable Biometric Filters (iv) Bioconvolving (v) Bloom Filters (vi) Knowledge Signatures (vii) Biohashing Methods (viii) Random Permutations (ix) Salting Methods and (x) Hybrid Methods.

Noninvertible Geometric Transforms morph the biometric image by employing some transformation in signal or feature space [3, 38, 39]. The drawback of these methods is unstability i.e. a small change in the original biometric may lead to large variations in generated biometric template after transformation thereby affecting the overall performance. In Random Projection Methods, a biometric template is projected to a lower dimension using a matrix whose elements are independently realized random variables. This matrix is chosen such that the distances between any two feature points is preserved in the transformed sample space. See [35] for details where some matrices are defined which satisfy these criteria. Two dimensional cancelable biometric methods [26, 29] have also been suggested under this category in which the whole biometric image is used as feature matrix instead of converting the original biometric image. Savvides et al. [42] suggested cancelable biometric filters where the original biometric images are convolved with user specific convolution kernel and these encrypted images are used to generate a filter called minimum average correlation energy (MACE). During enrollment, users are also assigned a personal identification number (PIN). The user presents the biometric template and PIN simultaneously to the system for recognition. Bioconvolving [30] is another biometric template generation method which is particularly applicable in scenarios where set of sequence can be employed to represent a biometric template e.g. signature. In this method, a key vector d = [d0d1 ...dk] is formed such that dk > dk− 1 and d0 and dk are set to 0 and 100 respectively. Based on this key, the original sequence is broken into k mutually exclusive segments. These segments are then linearly convoluted to obtain the transformed sequence. Recently, bloom filters [40] have also been successfully applied for biometric template generation. A bloom filter is a probabilistic data structure that supports membership queries on a set. The key advantage of these filters is that a high level of security is provided while much affect on the recognition accuracy. Behavioral biometrics such as voice is also vulnerable to be copied and misused. Knowledge signatures [49] is a scheme in which a person is allowed to sign on a group’s behalf such that if the biometric is compromised, then it can not be identified exactly the person whose voice is represented by the biometric template. This scheme employs factorization of large integers and hence privacy of the user is protected. Biohashing [44] methods extend random projection methods where some feature extraction method such as wavelet transform is employed before computing the inner product with identity specific tokenized random number (TRN).

In most of the above categories, the recognition accuracy is negatively affected as the representation used for performing recognition is altered in order to ensure the privacy and security of the concerned individuals. Random permutation [35, 51] is another biometric template generation method and it encompasses only rearrangement of features and recognition accuracy is not much affected. Zuo et al. [51] have suggested four random permutation methods called GRAY-COMBO, BIN-COMBO, GRAY-SALT and BIN-SALT. In GRAY-COMBO, the original biometric is transformed by first shifting the rows circularly using random offsets and then adding the rows randomly. In BIN-COMBO, the same operation is performed on the iris codes by random shifting and XOR-ing. In GRAY-SALT, a completely artificial pattern equal to the size of original image is added to the original image to get the cancelable biometric image. In BIN-SALT, the artificial pattern is converted into binary pattern using a threshold and is added to the original pattern. Uhl et al. [10] have also suggested another random permutation method in which the original biometric image is first divided into rectangular patches and then these rectangular patches are permuted randomly to obtain the encoded biometric image.

There are some methods based on hash codes such as PalmHash Code [28], 2D PalmHash Codes [20, 22], PalmPhasor Code [23], 2-D PalmPhasor [27] etc. which have been effectively employed for cancelable biometric recognition. Here, Conjugate 2D PalmHash code [20] is used in multimodal scenario while other methods are employed in unimodal scenario. Another approach for addressing cancelable biometric system is based on biometric cryptosystem. A popular method under this category is suggested by Leng et al. [21] in which two hybrid cancelable palm print cryptosystems has been proposed based on palm print texture code, dubbed row-alone and row-co-occurrence Fuzzy Vaults. There are some other recent methods based on synthetic minutiae [8], Noise embedding [19], Index-of-Max Hashing [14], Random Distance [16], electrocardiogram (ECG) [48] which has been suggested for cancelable biometric template generation.

To address the issues of security and privacy of user’s data and simultaneously achieving good recognition accuracy, in this paper, we propose a novel method called Random Permutation Locality Preserving Projection (RP-LPP). The main contribution of the work is two-fold:

  • A novel method for cancelable biometric recognition based on Random Permutation (RP) and Locality Preserving Projection (LPP) is proposed.

  • The mathematical relationship between the eigenvalues and eigenvectors of the original biometric image and its randomly permuted version is exploited for carrying out cancelable biometric recognition.

The rest of the paper is organized as follows: Section 2 provides a brief overview of the LPP algorithm. Section 3 presents the proposed method. In this section, we show how random permutations can be employed to generate encrypted biometric template and hence LPP is applied without affecting the classification accuracy. Experimental Setup is given in Section 4 while Results and Discussion are given in Section 5. Here, the analysis pertaining to the security of the biometric template, quality, classification accuracy and computational complexity of the proposed techniques is presented. Finally, conclusion of the research work is given in Section 6.

2 Locality preserving projection

Let \(\mathbf {x} \in \mathbb {R}^{d}\) be a column vector representing an image in a d dimensional space and there are c identities {1,2,3,..., c} such that each identity has Ni images. Thus, total number of training images is \(N = {\sum }_{i=1}^{c}N_{i}\). Further, it is also assumed that \(\mathbf {x}_{1}, \mathbf {x}_{2},...,\mathbf {x}_{N} \in {\mathscr{M}}\) where \({\mathscr{M}}\) in a non-linear manifold embedded in \(\mathbb {R}^{d}\).

To reduce the dimensionality of images, He and Niyogi [11] have proposed an algorithm called Locality Preserving Projection (LPP). The outline of the algorithm is as follows:

Step 1: Construction of Adjacency Graph

Let the data samples x1, x2,..., xN represent the nodes of a graph G. Then, xi and xj are connected by an edge if they are close to each other depending upon any of the following criteria:

  • (a)𝜖-neighbourhood: Here, two vectors xi and xj are said to be neighbours if ||xi −xj||2 < 𝜖 where norm is the Euclidean norm in \(\mathbb {R}^{n}\).

  • (b)knearest neighbours: Here, two vectors xi and xj are said to be neighbours if xi is among k nearest neighbours of xj or vice versa.

Step 2: Construction of Weight Matrix

Here, the weight matrix S is a sparse symmetric matrix of size N × N with Sij as the weight joining the nodes xi and xj. There are two possible ways for defining Sij i.e.

  • (a)Heat Kernel: If xi and xj are connected, put

    $$ S_{ij} = e^{\frac{||\mathbf{x}_{i} - \mathbf{x}_{j}||^{2}}{\gamma}} $$
    (1)

    where \(\gamma \in \mathbb {R}\) is a user defined parameter to control the weight values.

  • (b)Simple Minded: Here Sij = 1 if xi and xj are neighbours and 0 otherwise.

Step 3 : Finding the Eigenmaps

The main objective of LPP is to find such a transformation V such that the connected points in the original space stay as close to each other as possible in the transformed space. Thus, LPP aims to minimize the following objective function:

$$ \sum\limits_{ij} (\mathbf{y}_{i} - \mathbf{y}_{j})^{2} \mathbf{S}_{ij} $$
(2)

where yi is the representation of xi in the transformed space. Hence, the criterion function for LPP is given as follows [11]

$$ J(\mathbf{V}_{LPP}) {=}^{\quad \arg \quad \min}_{\mathbf{V}^{T}\mathbf{X}\mathbf{D}\mathbf{X}^{T}\mathbf{V}=\mathbf{I}} \mathbf{V}^{T}\mathbf{X}\mathbf{L}\mathbf{X}^{T}\mathbf{V} $$
(3)

where X = [x1x2 ... xN], D is a diagonal matrix with \(D_{ii} = {\sum }_{j}W_{ij}\), representing the sum of weights in rows or columns. L = D −W is the Laplacian matrix.

The solution to the criteria in (3). Obtain the eigenvalue decomposition of the following generalized eigenvector problem:

$$ \mathbf{X}\mathbf{L}\mathbf{X}^{T}\mathbf{v} = \lambda\mathbf{X}\mathbf{D}\mathbf{X}^{T}\mathbf{v} $$
(4)

Let the solution to the (4) is given by eigenvectors v1, v2...vl corresponding to the eigenvalues λ1 < λ2 < ... < λl. Hence the original face images are represented in a lower dimensional embedding as follows:

$$ \mathbf{x}_{i} \rightarrow \mathbf{y}_{i} = \mathbf{V}_{LPP}^{T}\mathbf{x}_{i} \quad where \quad \mathbf{V}_{LPP} = [\mathbf{v}_{1}, \mathbf{v}_{2} ... \mathbf{v}_{l}] $$
(5)

Now the transformed data points matrix Y is given by the following equation:

$$ \mathbf{Y} = \mathbf{V}_{LPP}^{T}\mathbf{X} $$
(6)

Hence the dimensionality of the original data samples is reduced from \(\mathbb {R}^{d}\) to \(\mathbb {R}^{l}\).

3 Proposed method

Cancelable biometric must possess two important criteria i.e. viz. non-invertibe and revocable. In the proposed method, we find a low dimensional representation of the given training images using LPP [11]. This low dimensional representation corresponds to the coefficients corresponding the chosen eigenvectors and are non-invertible. Thus, instead of storing original biometric images, one can store the extracted features of an image. The second criterion of revocability is achieved by employing a random permutation matrix. A random permutation matrix is an identity matrix whose rows or columns are randomly exchanged in such a manner that each row and each column has only one entry as 1 while all others are 0.

Now, we see how revocable biometric pattern can be issued to an individual based on the proposed method.

3.1 Random permutation locality preserving projection (RP-LPP)

Since LPP [11] involves converting the biometric image to a column vector, in this proposed technique, the training images are pre multiplied with a random permutation matrix \(\mathbf {P} \in \mathbb {R}^{d \times d}\) which permutes the original features of an identity. This process generates a cryptic pattern (where pattern ∈ {face, fingerprint, iris, voice etc.}) and is issued to the user. This biometric pattern is completely revocable and can be reissued if compromised. The cyptic pattern \(\mathbf {z} \in \mathbb {R}^{d}\) corresponding to a biometric image \(\mathbf {x} \in \mathbb {R}^{d}\) is computed using the following equation.

$$ \mathbf{z} = \mathbf{P}\mathbf{x} $$
(7)

A sample face image and its corresponding cryptic face is shown in Fig. 1. The major contribution of our research work is the relationship between eigenvalues and eigenvectors of original biometric images and cryptic patterns. The eigenvalues possessed by the original biometric images and the cryptic pattern are same while the eigenvectors of the cryptic patterns are randomly permuted version of the eigenvectors of the original biometric images according to the random permutation matrix P. The mathematical formulation of the relationship is given in the following subsection.

Fig. 1
figure 1

Sample face Image (left) and its corresponding cryptic face (right) generated using RP-LPP

Full size image

3.1.1 Theoretical analysis of relationship between lPP and RP-LPP

Suppose each of the training data vector xi(i = 1,2,..., N) as given in Sect. 2 is permuted with the random permutation matrix P so that the resulting training data after permutation is represented by zi as follows:

$$ \mathbf{z}_{i} = \mathbf{P}\mathbf{x}_{i} $$
(8)

Hence, the criterion function of LPP as given in (2) is modified as follows:

$$ \begin{array}{@{}rcl@{}} V^{\prime} &{=}&{~}^{\text{arg~min}}_{\mathbf{V}} \frac{1}{2}\sum\limits_{ij} (\mathbf{y}_{i} - \mathbf{y}_{j})^{2} \mathbf{S}_{ij} \\ &=& \frac{1}{2}\sum\limits_{ij} {(\mathbf{V}^{T} \mathbf{z}_{i} - \mathbf{V}^{T}\mathbf{z}_{j})}^{2} S_{ij} \\ &=& \frac{1}{2}\sum\limits_{ij} {(\mathbf{V}^{T} \mathbf{z}_{i} - \mathbf{V}^{T}\mathbf{z}_{j})}^{T} {(\mathbf{V}^{T} \mathbf{z}_{i} - \mathbf{V}^{T}\mathbf{z}_{j})} S_{ij} \\ &=& \frac{1}{2}\sum\limits_{ij} {(\mathbf{z}_{i}^{T} \mathbf{V} - \mathbf{z}_{j}^{T}\mathbf{V})} {(\mathbf{V}^{T} \mathbf{z}_{i} - \mathbf{V}^{T}\mathbf{z}_{j})} S_{ij} \\ &=& \frac{1}{2}\sum\limits_{ij} {(\mathbf{V}^{T}\mathbf{z}_{i}S_{ij}\mathbf{z}_{i}^{T}\mathbf{V} - \mathbf{V}^{T}\mathbf{z}_{i}S_{ij}\mathbf{z}_{j}^{T}\mathbf{V} - \mathbf{V}^{T}\mathbf{z}_{j}S_{ij}\mathbf{z}_{i}^{T}\mathbf{V} + \mathbf{V}^{T}\mathbf{z}_{j}S_{ij}\mathbf{z}_{j}^{T}\mathbf{V})} \\ &=& \frac{1}{2}\sum\limits_{ij} {(2\mathbf{V}^{T}\mathbf{z}_{i}S_{ij}\mathbf{z}_{i}^{T}\mathbf{V} - 2\mathbf{V}^{T}\mathbf{z}_{i}S_{ij}\mathbf{z}_{j}^{T}\mathbf{V})} \\ &=& \sum\limits_{ij} (\mathbf{V}^{T}\mathbf{z}_{i}S_{ij}\mathbf{z}_{i}^{T}\mathbf{V} - \mathbf{V}^{T}\mathbf{z}_{i}S_{ij}\mathbf{z}_{j}^{T}\mathbf{V}) \\ &=& \sum\limits_{i}\mathbf{V}^{T}\mathbf{z}_{i}M_{ii}\mathbf{z}_{i}^{T}\mathbf{V} - \sum\limits_{ij}\mathbf{V}^{T}\mathbf{z}_{i}S_{ij}\mathbf{z}_{j}^{T}\mathbf{V}) \\ &=& \mathbf{V}^{T}\mathbf{Z}\mathbf{M}\mathbf{Z}^{T}\mathbf{V} - \mathbf{V}^{T}\mathbf{Z}\mathbf{S}\mathbf{Z}^{T}\mathbf{V} \\ &=& \mathbf{V}^{T}\mathbf{Z}(\mathbf{M} - \mathbf{S})\mathbf{Z}^{T}\mathbf{V} \\ &=& \mathbf{V}^{T}\mathbf{Z}\mathbf{L}\mathbf{Z}^{T}\mathbf{V} \end{array} $$

where M is a diagonal symmetric matrix and the entries at diagonals are row or column sums of Sij i.e. \(\mathbf {M}_{ii} = {\sum }_{j}\mathbf {S}_{ij}\). The matrix L = M −S is the popular Laplacian matrix. The matrix M gives information about the relative importance of the data points i.e. bigger the value of Mii, more important is yi. Therefore, like [11], we also impose a constraint as follows:

$$ \mathbf{Y}^{T}\mathbf{M}\mathbf{Y} = 1 \implies \mathbf{V}^{T}\mathbf{Z}\mathbf{M}\mathbf{Z}^{T}\mathbf{V} = \mathbf{I} $$
(9)

Hence, the overall criterion of the proposed method becomes:

$$ J(\mathbf{V^{\prime}}) =^{\quad \arg \quad \min}_{\mathbf{V}^{T}\mathbf{Z}\mathbf{D}\mathbf{Z}^{T}\mathbf{V}=\mathbf{I}} \mathbf{V}^{T}\mathbf{Z}\mathbf{L}\mathbf{Z}^{T}\mathbf{V} $$
(10)

or

$$ J(\mathbf{V^{\prime}}) =^{\quad \arg \quad \min}_{\mathbf{V}^{T}\mathbf{P}\mathbf{X}\mathbf{D}\mathbf{X}^{T}\mathbf{P}^{T}\mathbf{V}=\mathbf{I}} \mathbf{V}^{T}\mathbf{P}\mathbf{X}\mathbf{L}\mathbf{X}^{T}\mathbf{P}^{T}\mathbf{V} $$
(11)

The above criterion is equivalent to (3) provided:

$$ \mathbf{V}_{LPP} = \mathbf{P}^{T}\mathbf{V^{\prime}} $$
(12)

This can be rewritten as:

$$ \mathbf{V^{\prime}} = \mathbf{P}\mathbf{V}_{LPP} $$
(13)

Thus, the transformation matrix \(\mathbf {V^{\prime }}\) obtained after random permutation of the training images is simply the randomly permuted transformation matrix VLPP obtained with original training images.

3.1.2 Applicability of RP-LPP as cancelable biometric

From the above discussion, relationship between original and randomly permuted face images is revealed. But it is unacceptable to employ a single random permutation matrix P for all the identities enrolled in the biometric recognition system. This will cause problems if the biometric template of any identity is compromised, then all the identities must be issued some new biometric template which is impractical. Thus to overcome this, each identity is issued a separate biometric template along with a key called personal identification number (PIN). When the user provides the cryptic pattern to the recognition system, he also presents the PIN issued to him during enrolment. This PIN determines the permutation matrix Pi corresponding to that person and the appropriate transformation matrix \(\mathbf {V^{\prime }}_{i}\) is obtained corresponding to that person as given below:

$$ \mathbf{V^{\prime}}_{i} = \mathbf{P}_{i}\mathbf{V}_{LPP} $$
(14)

First the biometric template is converted into a column vector and then the above transformation matrix directly converts the biometric template into feature vector without converting it to original face image. After obtaining the features, the identity of the person is determined by matching the features with the database. If either the biometric pattern or the PIN or both are not in order, then the user is rejected.

3.2 Applicability of RP-LPP in single sample scenario

The performance of the biometric recognition system depends on the number of training images available for training and it increases as more number of training images are available [18]. But due to the intricacies involved in collecting biometric samples in real life scenarios, it is presumed that the feature extraction method should perform well with small number of training images per identity. This leads to an interesting problem when only a single training image is available and this problem is known as one sample per person problem. A survey of one sample per person in the domain of face recognition is carried out by Tan et al. [43]. When only one sample is available, then several techniques as given in Kumar et al. [18] fail to work. However, the proposed method is applicable in such scenarios.

4 Experimental set-up

To demonstrate the effectiveness of the proposed techniques, we have performed experiments of three freely available datasets including face, iris and ear biometric. The details of the datasets is given in Table 1.

Table 1 Summary of datasets used in experiments
Full size table

ORL [41] face dataset consists of facial images of 40 different identities with 10 images per person. The images of some identities were captured at different points of time with varying illumination and facial expressions. These expressions include open or closed eyes, smiling or not smiling, or the face images have glasses / no glasses). The facial images in ORL dataset are gray level images with size of 112 × 92 pixels.

UBIRIS [37] is an iris database released by University of Beira, Portugal. It consists of 1877 gray scale images of 241 identities. These images are incorporated with several noise factors in order to evaluate the robustness of the algorithms. We have selected 5 images per person for experiments resulting into a total of 1205 images. These images are resized to half of the original size i.e. 75 × 100.

IITD [17] is a database consisting of ear images of IIT Delhi students and staff members. The database was collected from people in the age group 14-58 years. The original database has 471 images of size 204 × 272. The database also provides automatically segmented and cropped images of 125 people consisting of 493 ear images each of size 180 × 50. We have selected 3 images of each person for our experiments resulting into a total of 375 images.

Sample images of one identity from each of the face, iris and ear datasets are shown in Fig. 2. The performance of the proposed techniques is evaluated in terms of the quality of the cancelable biometric template, security provided by cryptic patterns generated using RP-LPP, average classification accuracy and average training time of the algorithm. The training images from each identity is selected randomly and the remaining images are used as testing set. This process is repeated 40 times to achieve a stable classification accuracy and average training time. All the experiments are performed on Intel Xeon E3 CPU 2.4 GHz with Windows 8.1 and 16 GB main memory.

Fig. 2
figure 2

Sample images of an identity from ORL [41] (top), UBIRIS [37] (middle) and IITD [17] (bottom) datasets

Full size image

5 Results and discussion

In this section, we critically analyse the performance of the proposed method i.e. RP-LPP both qualitatively and quantitatively with other state-of-the-art methods viz. GRAY-COMBO (GC), GRAY-SALT(GS) and BLOCK-REMAPPING(BR). We have obtained the cryptic pattern using the compared methods and then features are extracted using LPP. Finally, recognition is performed using Nearest Neighbour (NN) rule. The performance of the proposed methods is analysed using security of biometric template generated using the proposed techniques against the brute force attack. The quality of cryptic patterns generated by the proposed methods is also compared with the above-mentioned methods. Further, we present and discuss average classification accuracy and compare it with state-of-the-art methods. The average training time required by the proposed techniques is also shown. RP-LPP is trained using only few training images from each identity so as to tackle SSS problem.

5.1 Analysis of cryptic patterns

5.1.1 Security against brute force attack

Here, we analyse the cryptic patterns or biometric templates produced using the proposed RP-LPP method both qualitatively and quantitatively. Some examples face, iris and ear images with their corresponding biometric templates produced using GRAY-COMBO (GC), GRAY-SALT (GS), Block-Remapping (BR) and the proposed RP-LPP are shown in Figs. 3, 4 and 5 respectively. It is apparent from these figures that the quality of cryptic patterns generated using the proposed Random Permutations is better in comparison to all other compared methods. It is also observed that the cryptic pattern generated by other methods (GC,GS,BR) leave some information which can be exploited to know the original biometric pattern and thus are vulnerable. However, the cryptic patterns generated using the proposed techniques leave no room for such kind of guessing. It can be further observed from Figs. 3, 4 and 5 that there is no pattern whatsoever when biometric template is generated using RP-LPP and biometric templates generated from the proposed method is completely revocable and can be reissued if compromised.

Fig. 3
figure 3

Sample face images with corresponding cryptic patterns generated using Gray Combo, Gray Salt, Block Remapping and RP-LPP respectively(left to right) on ORL Face Dataset

Full size image
Fig. 4
figure 4

Sample iris images with corresponding cryptic patterns generated using Gray Combo, Gray Salt, Block Remapping, RP-LPP respectively(left to right) on UBIRIS Iris Dataset

Full size image
Fig. 5
figure 5

Sample ear images with corresponding cryptic patterns generated using Gray Combo, Gray Salt, Block Remapping, RP-LPP respectively(left to right) on IIT Delhi Ear Dataset

Full size image

As biometric template generated using the proposed techniques is a random permutation of the features of original biometric template, the robustness of the biometric template can be estimated from the image size say d = a × b. As in RP-LPP, each biometric image is represented as a column vector, the brute force attack requires d! iterations (where d = a × b) which is extremely hard to break in practice. For a typical biometric template of size 100 × 100, the number of possible iterations shall be of the order of 10000! which is a very large number. In addition to this, the PIN which is issued to the identity further makes it harder to break the encryption.

Let us suppose that we have fastest supercomputer at our disposal with a speed of 100 Peta FLOPS ≈ 1017 floating point operations per second and assume that matrix multiplication requires 1 basic step. Then it requires (a × b)! iterations for the random permutation matrix in case of RP-LPP. Furthermore, random permutation matrix multiplication with the image converted to column vector requires d2 multiplications where d = a × b in RP-LPP. We know that there are 86400 sec. (= 24 × 60 × 60) in a day. The time required to brute force the cryptic patterns generated using the proposed techniques is given in Table 2. It can be easily observed from the Table that it will take several centuries to break the cryptic pattern using brute force attack thereby ensuring the high security of the biometric template. The least time to break the biometric template is for UBIRIS iris dataset when RP-LPP is employed for generating the biometric template. But, it still requires 1025792 years which is very high. Hence, the proposed techniques generate highly secure biometric patterns.

Table 2 Time required to break the cryptic pattern of brute force attack
Full size table

5.1.2 Non-invertibility of generated templates

One of the essential requirement of cancelable biometric template is that it is non-invertible. In the proposed approach, the generated template and the PIN is provided by the user to the system for authentication. This information is used to determine the permutation matrix and hence extract the features which are used for authentication without any control of the user. This information is further used to extract the distinguishing few features (typically 20 as shown in experimental results) out of a large number of features as discussed. Reconstruction of the biometric image using these 20 features is very hard. Even if an intruder gets access to these 20 features, then reconstruction shall result in cancelable biometric image which is extremely difficult to decode in limited time. This proves that the generated templates using the proposed method are non-invertible.

5.1.3 Correlation analysis

Here, we analyse the correlation between generated templates by changing the random permutation matrix P. The analysis is similar to [15]. The transformed templates are diverse if the correlation between any two generated templates is low and is computed as :

$$ R = \frac{\sum(T_{1} - \bar{T}_{1})(T_{2} - \bar{T}_{2})}{\sqrt{(T_{1}-\bar{T}_{1})^{2}+(T_{2}-\bar{T}_{2})^{2}}} $$
(15)

where T1 and T2 are the generated templates with \(\bar {T}_{1}\) and \(\bar {T}_{2}\) representing the mean template values respectively. We have chosen a sample image from each of the datasets as shown in Table 3. Then 10 different templates are generated by changing the random permutation matrix. For each pair of the generated templates, correlation coefficient is determined using above equation and average of the absolute value of correlation is reported in the last row of the Table 3. It can be readily observed that the average absolute correlation is less than 2% across all the datasets which clearly indicates that no mutual information is available between any two generated templates. This average value is also known as Correlation Index(CI) of the dataset. The proposed method is able to achieve good CI on all the datasets.

Table 3 Average absolute correlation index
Full size table

5.2 Classification accuracy

The classification accuracy measures the percentage of identities correctly classified by some technique or algorithm. This classification accuracy of a technique depends on factors such as the number of training images used, the number of dimensions in the transformed representation. The technique which gives better performance with few number of training images is of real significance. In our experiments, we have kept the number of training images less than 6 and the number of reduced dimension only upto 20. These can be modified according to the application at hand. We have measured the classification accuracy of the proposed techniques on ORL, UBIRIS and IITD datasets and is shown in Figs. 6, 7 and 8 respectively. This average classification accuracy is obtained after 40 random runs as explained in previous section. In the rest of this section classification accuracy means average classification accuracy unless otherwise stated.

Fig. 6
figure 6

Classification Accuracy on ORL face dataset

Full size image
Fig. 7
figure 7

Classification Accuracy on Ubiris iris dataset

Full size image
Fig. 8
figure 8

Classification Accuracy on IITD ear dataset

Full size image

The training images for each identity in ORL [41] face dataset are varied from 1 to 6. The classification for each case is shown in Fig. 6. It can be easily observed that the classification accuracy for RP-LPP is better than all other compared methods. It is interesting to note that the classification accuracy of RP-LPP is more than 60% when a single training images per identity is used. This classification accuracy further increases to more than 70% with 6 training images. Also, the classification accuracy of other methods is less than 25% across all the scenarios considered here.

For experiments on UBIRIS [37] iris dataset, the training images are varied from 1 to 4 as shown in Fig. 7. RP-LPP outperforms all other methods in all cases. The increases in classification accuracy is almost linear with the number of reduced dimension. It can be noticed that with a single training image, RP-LPP achieves a classification accuracy of approximately 50% which increases to almost 70% when the number of training images increase to 4.

The classification accuracy on IITD [17] ear dataset is shown in Fig. 8. As only few training images are available in the dataset, we could use only 1 or 2 images of each identity as the training images. However, the classification accuracy of the proposed techniques is encouraging and similar observations as that on ORL and UBIRIS are observed on this dataset also. A classification accuracy of 65% is achieved by RP-LPP when 2 training images are used. The proposed techniques perform better than other methods. At some places, the classification accuracy slightly decreases at few places. Thus, we can say that the increase in number of reduced dimensions does not guarantee an increase in the classification accuracy. But the classification accuracy generally increases with increase in the number of reduced dimension. On all the datasets, RP-LPP performs best in all cases.

5.3 Training time

The average training time of proposed method RP-LPP and other compared methods on all the datasets as shown in Table 4. It can be readily observed that the training time of the proposed method is less in comparison to other methods on all the datasets except two cases on ORL dataset (where no. of training image(s) are 1 and 5). Further, it is also noticed that the training time of various techniques increases with increase in number of training images. This comparison also supports the superiority of the proposed method.

Table 4 Training time (sec.) required by proposed method on ORL, UBIRIS and IITD dataset
Full size table

6 Conclusion

In this paper, we presented a simple and powerful techniques based on random permutations. The proposed techniques RP-LPP is applicable to cancelable biometric recognition in which the identities are issued a biometric template which we call cryptic pattern based on random permutation matrices along with a PIN. The identities present both the cryptic pattern and the PIN in order to be recognized by the system. If any of the two is incorrect, then the identity is rejected by the system. Experimental results demonstrate the effectiveness of the proposed techniques. The cryptic pattern generated by RP-LPP is highly secure and it will take centuries to break the code using brute force attack. Even if the biometric template is compromised, the same can be reissued. The proposed technique is also applicable to scenarios where only single sample per person is available for training. Another key advantage of the proposed method is that no image registration is required during enrolment. The performance of the proposed techniques are measured on three freely available face, iris and ear datasets against other random permutation methods. The performance was found to be better in terms of quality and security of cryptic patterns, average classification accuracy and average training time. RP-LPP outperforms other methods in terms of classification accuracy and training time. Further, experimental results demonstrate the robustness of the proposed techniques across different biometrics.