Portal de Periódicos da CAPES

Artigo Produção Nacional Revisado por pares

BIBTEX RIS

Robust partitioning and indexing for iris biometric database based on local features

2018; Institution of Engineering and Technology; Volume: 7; Issue: 6 Linguagem: Inglês

10.1049/iet-bmt.2017.0130

2047-4946

Emad Taha Khalaf, Muamer N. Mohammad, Kohbalan Moorthy,

Biometric Identification and Security

IET BiometricsVolume 7, Issue 6 p. 589-597 Research ArticleFree Access Robust partitioning and indexing for iris biometric database based on local features Emad Taha Khalaf, Corresponding Author Emad Taha Khalaf pcc13010@stdmail.ump.edu.my Soft Computing and Intelligent System Research Group, Faculty of Computer Systems and Software Engineering, Universiti Malaysia Pahang, 26300 Kuantan, Pahang, MalaysiaSearch for more papers by this authorMuamer N. Mohammad, Muamer N. Mohammad The State Company for Internet Services, Ministry of Communications of Iraq, Baghdad, IraqSearch for more papers by this authorKohbalan Moorthy, Kohbalan Moorthy Soft Computing and Intelligent System Research Group, Faculty of Computer Systems and Software Engineering, Universiti Malaysia Pahang, 26300 Kuantan, Pahang, MalaysiaSearch for more papers by this author Emad Taha Khalaf, Corresponding Author Emad Taha Khalaf pcc13010@stdmail.ump.edu.my Soft Computing and Intelligent System Research Group, Faculty of Computer Systems and Software Engineering, Universiti Malaysia Pahang, 26300 Kuantan, Pahang, MalaysiaSearch for more papers by this authorMuamer N. Mohammad, Muamer N. Mohammad The State Company for Internet Services, Ministry of Communications of Iraq, Baghdad, IraqSearch for more papers by this authorKohbalan Moorthy, Kohbalan Moorthy Soft Computing and Intelligent System Research Group, Faculty of Computer Systems and Software Engineering, Universiti Malaysia Pahang, 26300 Kuantan, Pahang, MalaysiaSearch for more papers by this author First published: 15 June 2018 https://doi.org/10.1049/iet-bmt.2017.0130Citations: 7AboutSectionsPDF ToolsRequest permissionExport citationAdd to favoritesTrack citation ShareShare Give accessShare full text accessShare full-text accessPlease review our Terms and Conditions of Use and check box below to share full-text version of article.I have read and accept the Wiley Online Library Terms and Conditions of UseShareable LinkUse the link below to share a full-text version of this article with your friends and colleagues. Learn more.Copy URL Share a linkShare onFacebookTwitterLinkedInRedditWechat Abstract Explosive growth in the volume of stored biometric data has resulted in classification and indexing becoming important operations in image database systems. Consequently, researchers are focused on finding suitable features of images that can be used as indexes. Stored templates have to be classified and indexed based on these extracted features in a manner that enables access to and retrieval of those data by efficient search processes. This paper proposes a method that extracts the most relevant features of iris images to facilitate minimisation of the indexing time and the search area of the biometric database. The proposed method combines three transformation methods DCT, DWT and SVD to analyse iris images and extract their local features. Further, the scalable K-means++ algorithm is used for partitioning and classification processes, and an efficient parallel technique that divides the features groups causing the formation of two b-trees based on index keys is applied for search and retrieval. Moreover, search within a group is achieved using a proposed half search algorithm. Experimental results on three different publicly iris databases indicate that the proposed method results in a significant performance improvement in terms of bin miss rate and penetration rate compared with conventional methods. 1 Introduction Iris-based biometric systems have many advantages over other biometric traits. For example, because the iris is protected inside the human body, it is less susceptible to environmental factors than fingerprints, and it cannot be surgically manipulated without significant risk to the vision. Further, iris-based biometric systems have proven to be highly accurate in person recognition systems [1]. An ideal biometric system should be highly accurate, convenient to use, and easily scalable to a large population [2]. The major obstacles that hinder the design and development of such systems are currently the focus areas of active research. One such major obstacle is the number of false acceptances, which increases geometrically with the size of the biometric database [3]. Further, the time required to claim identification is directly proportional to the size of the database. Consequently, the emphasis recently is on reducing the search space in order to improve the performance of biometric systems. However, to reduce the search space, an efficient classification and indexing scheme is required. Most existing index methods either produce high-dimensional feature vectors for indexing, which not only increases the computational complexity in indexing, but also increases the logical database size, such as [4, 5] or produce an insufficient number of features, which leads to misclassification and false indexing, such as [6, 7]. The partitioning and classification problem has two aspects: (i) extraction and (ii) clustering [8]. The first aspect of the problem is caused by the ambiguity of extracting important biometric features to distinguish among different biometrics and the relations between them. Three popular transformation methods [discrete cosine transform (DCT), discrete wavelet transform (DWT), and singular vector decomposition (SVD)] are used for this task. These methods analyse each block of an iris image and extract the most distinguishing texture features as well as increase the number of features for efficient classification and partitioning for the iris database by using the scalable k-means++ algorithm to divide the data into groups of similar features. The remainder of this paper is organised as follows. Section 2 discusses related work. Section 3 outlines the proposed system and its modules. Section 4 discusses the experimental results obtained on three different databases. Section 5 presents concluding remarks. 2 Related work The iris database indexing task is challenging because of the high dimensionality of the extracted features. Although many texture feature extraction methods have been proposed for iris authentication, studies reporting the use of such methods for the retrieval of biometric data with high-dimensional features from a huge database are scarce. Jayaraman et al.[4] developed a hierarchical method to efficiently collect iris data from large iris databases. Their method employs the iris colour to index the database, and the iris texture to retrieve the iris images from the indexed iris database. The method initially chooses a set comprising iris images that are similar to the query by applying the indexing technique. Next, the index value is computed by averaging the intensity values of all red and blue pixels. Finally, the kd-tree structure is applied to store the iris data. The features of iris texture from the chosen images were employed to detect the identity of the query image. In fact, the iris texture features were extracted via the speed up robust features [9] algorithm. Colour indexing schemes are not recommended for iris indexing owing to their high dimensionality (computational complexity). Further, most conventional texture indexing and partitioning schemes use an insufficient number of features for partitioning and classification [6]. Some techniques for extracting characteristics have been recommended for iris identification based on texture features. Mukherjee and Ross [10] proposed an indexing method based on the signed pixel level difference histogram (SPLDH). In their proposed method, the iris texture is first divided into blocks. Next, a histogram is created for each block with signed variances (pixels with same location in both adjacent blocks). As with the IrisCode technique [10], the method incorporates attributes at ∼256 dimensions. Nevertheless, determination of histogram dimensionality still appears to be an open problem. Mehrotra et al. [11] extracted local features using the scale-invariant feature transform (SIFT) from noise independent annular iris images. During indexing, they used keypoints to obtain the indices of the hash table. Then, upon determining some primary keys, the high-dimensional (124-dimension) features of SIFT were analysed (with the primary keys) by applying geometric hashing. The technique utilises a relatively large number of primary keys (∼100) that contain trait vectors with high dimensions. The major drawbacks of IrisCode (averaging of column/block/row and principal component analysis), SIFT, and SPLDH are the associated high computational cost and unreliable statistics. In addition, these indexing methods depend on partitioning of biometric data sets [10]. Such techniques are not able to separate the data sets uniformly. The consequent varying partition sizes cause search results to differ. Hence, these techniques are neither efficient nor sufficiently accurate for practical applications. Si et al. [12] proposed a method that first detects the eyelash to enhance the iris segmentation accuracy. They stated that this operation is performed as the eyelash is misclassified as texture by several algorithms. The proposed method is based on the directional filters of the eyelash, which is based on the observation that every eyelash usually grows along a single direction or with a small deflection which can be observed from two directions close to each other. A connection rule is then formed in order to reduce the loss as well as detect the eyelash. Based on the connection rule, the eyelash can be removed according to their position. The second part is feature extraction, which is performed based on the multi-scale and multi-orientation data fusion strategy after two-dimensional (2D) Gabor filtering, which describes both the scale and direction of the iris texture features. Rathgeb et al. [16] proposed an efficient indexing scheme based on the histogram of energy derived from the texture of the iris, which is used to index the iris database. First, DCT is used to divide the normalised iris image into subbands, with each being formed using the energy histogram. Then, the images with similar energy value are grouped using the equal-size histograms. The global key for each image arranged in Morton order is then used to traverse the B-tree during database preparation. The key represents the bin number that contains the subband value. Images with the same key are stored together in the same leaf node. During the query process, the key of the iris image is generated to traverse the tree until the end of the leaf node in order to retrieve the stored templates. The result is then compared with the retrieved templates in order to find the best match. Dey and Samanta [6] proposed an indexing approach based on Gabor energy features to retrieve iris biometric templates. In their approach, the Gabor energy features are calculated from different scales and orientations of the iris texture in order to generate a 12-dimensional index key for the iris image. The values of the index keys of all individuals are then used to create an index space. From the index space and the index key of the query image, a candidate set is retrieved. Then, the retrieved candidates are ranked according to their occurrences. The identity of the query template is then compared. Mehrotra [7] proposed two methods for indexing iris databases. The first method involves using the energy histogram of DCT coefficients to form a B-tree. The second method involves indexing geometric hashing of SIFT keypoints. The proposed indexing is based on the local features of keypoints. The geometric hashing indexing scheme [14] is employed to detect the keypoints. Following preprocessing of the acquired iris image and its transformation into a fixed size normalised image, multi-resolution subband coding of the DCT coefficients is performed to extract the energy features from the rectangular block. Then, an indexing key is created from the energy histogram of the extracted features. This indexing key is used to organise the B-tree and to store the iris templates with similar texture feature at the leaf node. Barbu and Luca [5] proposed an iris indexing and retrieval model developed based on the concept of histogram of oriented gradients (HOG)-based image feature extraction. In their model, the HOG is commonly used as a feature descriptor for object-class detection. This technique has been proven to be very effective for human identification as well. In the method, the HOG characteristics of colour images are determined and an HOG-based feature vector built. The K-D-tree, which is modelled as a binary tree, is then used as an indexing solution for image descriptors [15] in order to analyse high-dimensional data. The space is recursively partitioned into two subspaces by the K-D trees. Each non-leaf node generates a splitting hyperplane that divides the space into two [15]. The points to the left/right of the hyperplane are represented by the left/right subtree of that node. The hyperplane direction is chosen in the following manner. Each node of the tree is associated with one of the K-dimensions, where the hyperplane is perpendicular to the dimensional axis. For example, if the x-axis is selected for a particular split, all points residing in the subtree with X values lower than that of the node would appear in the left subtree. Otherwise, they would appear in the right subtree. Here, the hyperplane is prescribed based on the x-value of the point. In this case, its normal vector is parallel to the x-axis. Those points within the HOG-based feature vectors are then added into the K-D tree structure (analogous to appending an element to a search tree). Therefore, the tree is traversed from the root level, and its direction is dependent on the insertion location of the point. Once the child-node is located, a new point is added. Its location is dependent on the orientation of the splitting plane containing the new node. Rathgeb et al. [16] proposed a method that uses generic iris recognition systems developed by Bowyer et al. [17] to extract binary feature vectors upon conducting row-wise analysis of normalised iris textures. (It is important to note that iris-codes typically represent 2D binary feature vectors.) In their proposed method, the binary matrix is divided into K equal-size blocks (i.e. w × h bits). A bloom filter is then extracted from each block in such a manner that the transformed iris-code B consists of K bloom filters, i.e. B = {b1, b2, …, bK}. The column sequence of the block is then sequentially transformed to decimal indexes and bits in order to map a block to B, which is set to one. Instead of using several hash functions, H:{0, 1}h → {0, 1}h is used, i.e. the size of the image set and the inverse image set of H are equal. The transform is performed by mapping each column ci∊{0, 1}h, i = 1, … , w, to the index of its decimal value. According to Rathgeb et al., the transform is alignment-free (at least to a certain degree), i.e. alignment of generated templates is not necessary during comparison. Within certain blocks, the same number of columns are mapped to identical indexes of B, i.e. self-propagating errors due to misalignment of iris-codes are removed. However, those radial neighbourhoods persist and the misalignment of iris-codes at block boundaries tends to result in the distribution of several potentially matching columns within various blocks. These blocks are mapped to the neighbouring B. 3 Proposed method The stored biometric templates should be classified and indexed based on the extracted features in a manner that facilitates efficient access and retrieval. By combining the three transformation algorithms DWT, DCT, and SVD, the proposed method is able to extract a sufficient number of relevant local features from iris images for classification and indexing of the biometric database. The local features are extracted from each image block by dividing the image into 8 × 8 blocks. DWT is then used to decompose the blocks into seven subbands in order to reduce the computational complexity as well as to provide useful discrimination between textures. Next, DCT is used to transform from the space domain to the frequency domain in order to separate each subband into parts (or spectral subbands) of varying importance. Finally, SVD is applied to decompose each transformed subband into three simple transformations: V*, Σ, and U. This method selects the first two singular values (SVs) from the Σ matrix of each subband, where the most important feature of an image is associated with the largest singular vector value. The selected features of all blocks are then combined to form the features vector of the image. Subsequently, the features of each subband of all images are partitioned logically based on similarity such that images having similar texture patterns are grouped for more accurate matches. For partitioning-based clustering, the scalable K-means++ (K-means||) algorithm is utilised because of its promising speed and scalability. In the conventional (existing) methods, the energy value of each subband is used as a local feature to divide all images into logical groups (see [6, 7]). This technique can lead to false indexing and partitioning owing to insufficient number of features representing the iris image. In addition, using a high-dimensional feature vector for indexing (e.g. [4, 5]) complicates the search and retrieval processes. The procedures utilised in the proposed method are outlined below (see Fig. 1). Figure 1Open in figure viewerPowerPoint Robust partitioning and classification based on the most relevant local features of iris 3.1 Iris image preprocessing In the first stage of iris recognition, the actual iris region is isolated. A preprocessing algorithm is applied to determine the boundary of the iris within the eye image and extract the iris portion (region of interest). In addition, some parts that are not useful for analysis (e.g. eyelid and pupil) are removed to ease processing (see Fig. 2). The preprocessing stage involves iris segmentation, normalisation, and enhancement. Figure 2Open in figure viewerPowerPoint Iris segmentation and normalisation 3.1.1 Segmentation For iris segmentation, the Canny edge detection operator and the circular Hough transformation [18] are utilised. 3.1.2 Iris normalisation Upon segmenting the image, the Daugman's rubber sheet model [19] is used for normalisation by converting the iris disk to a rectangular region of predetermined size. 3.1.3 Image enhancement The image is enhanced before feature extraction by using the contrast-limited adaptive histogram equalisation algorithm [19, 20]. 3.2 Feature selection In this paper, a robust method is proposed for selecting the most discriminating features of the iris and increasing the number of selected features. Whereas conventional methods use the total energy value to partition and index the iris database [13], the proposed algorithm extracts the local features for each image (see Fig. 3). Figure 3Open in figure viewerPowerPoint Block diagram of extracting local features of iris image 3.3 Dividing the image The first feature extraction step is division of the image into 8 × 8 blocks. The subimages in textural features can then be analysed in more detail [21]. Each block is treated individually to isolate its most relevant. Analysing a small block is useful for image processing and image compression [22]. The n × n block discrete transform of an image f(x,y) of size Su × Sv results in a 2D array of the same size as the input image. 3.4 Applying DWT The next step is to apply the two-level DWT on each 8 × 8 block. Each block is decomposed into seven subbands [23]; specifically, LL 2, HL 2, LH 2, HH 2, HL 1, LH 1, and HH 1 (see Fig. 4). DWT is attractive because of its relatively low computational complexity. Furthermore, it has been observed that multi-resolution decomposition provides useful discrimination between textures. Figure 4Open in figure viewerPowerPoint Two-level 2D-DWT decomposition process In general, the wavelet transform can be expressed by the following equation: (1) 3.5 Applying DCT In this step, DCT is applied on each DWT subband. DCT is one of the best image transformation methods. DCT is an orthogonal transformation method that transforms all subbands, slicing the image space domain into the frequency domain (similar to discrete Fourier transform). In addition, only a few data points are required to represent the slicing image. The generated coefficients of DCT can be easily quantised; therefore, the block compression performance is promising. DCT decomposes each subband image into spectral subbands of different importance (while retaining the visual quality of the image) [23, 24]. Fig. 5 shows the DCT transformation process. Figure 5Open in figure viewerPowerPoint Transform image domain using DCT DCT encoding: Here, the 2D DCT is used and the general equation for 2D (8 × 8 block) DCT can be written as follows: (2) where (3) Otherwise DCT uses different block sizes for BDCT. However, the transformation takes place independently, resulting in multiple BDCT coefficient arrays. In order to adopt these coefficients in the indexing and matching model, they are quantised to integers. 3.6 Applying SVD SVD is applied to a set of blocks (of varying sizes) for BDCT at all second-level subbands. Two orthogonal unitary matrices are obtained and a diagonal matrix constitutes the SVs of the matrix of subbands. In an image, the important features can be expressed by a series of SVs along the diagonal. In the proposed indexing model, the 8 × 8 block is decomposed into seven subbands by the two-level DWT. For uniform saving format, the first two SVs can be applied to the expression features of each subband image, for a matrix A with m rows, n columns, and rank r (r ≤ n ≤ m), A can be factorised into three matrices [25], (4) and (5): (4) where matrix U is an m × m orthogonal matrix, matrix V an n × n orthogonal matrix, and Σ an m × n diagonal matrix with SVs on the diagonal with non-negative numbers (5) where . 3.7 Singular vector feature selection Next, the important features Fi,j are selected. The seven subbands are expressed as {S1, S2, S3, S4, S5, S6, and S7}, where the sizes of S1, S2, S3, and S4 are 2 × 2. The sizes of S5, S6, and S7 are 4 × 4. In conventional methods, only one value can be assigned as the energy value for each subimage [11, 13]. Therefore, these methods are inaccurate in their expression of the energy value of the 4 × 4 subbands of S5, S6, and S7. In the proposed indexing model, the first two SVs (σ1, σ2) from the Σ matrix are selected to represent each subband (see Fig. 6), where the singular vector expresses the feature for all subband images. It is important to note that the most important feature of an image can be expressed by the largest singular vector value [26, 27]. Figure 6Open in figure viewerPowerPoint Selected singular values of each block 3.8 Feature vector creation for iris image Following extraction of the features of each block, the SVs σ1 of all blocks belonging to a particular subband are grouped [13] as defined in the below equation: (6) A similar procedure is applied for SV σ2 (see Fig. 7), resulting in seven 2D features, Fi,j. Each feature pair represents the key used for the partitioning and search processes. Figure 7Open in figure viewerPowerPoint Creating features vector of iris image from its blocks 3.9 Database partitioning and classification The next process is partitioning of the database into several groups in order to speed up the database search process by reducing the search space. The database should be logically partitioned such that images having similar texture patterns are indexed together. In the proposed method, the subbands of all images are divided into groups. The proposed partitioning and classification approach is shown in Fig. 8. Figure 8Open in figure viewerPowerPoint Proposed partitioning and classification approach image 3.9.1 Clustering In cluster analysis, the k-means algorithm can be used to divide the input data set into k partitions (clusters) [28], where clustering is the process of organising similar objects into groups. A cluster is therefore a collection of objects which are similar to each other and dissimilar to the other objects [29]. This is exemplified by distance-based clustering, which uses a metric function to determine if objects are ‘close’ to each other. In the proposed approach, the scalable K-means++ algorithm is used to find groups in the data. The algorithm operates iteratively to assign each data point to one of the K groups based on the features provided. Data points are clustered based on feature similarity. The outcomes of the K-means++ clustering algorithm are (i) centroids of the K clusters, which can be used to label new data; and (ii) labels for the training data (each data point is assigned to a single cluster). Rather than defining groups before looking at the data, clustering can be used to find and analyse the groups that have formed organically. The ‘Choosing K’ section describes the clustering process and how the number of groups can be determined. Scalable K-means++: Apache Spark has implemented a parallel version of the K-means++ method, called K-means|| [30]. The method has been characterised in terms of speed and scalability via testing. By taking advantage of the MapReduce model for computation, it is faster than the traditional K-means, as well as GMM. K-means|| manages noisy outliers and reduces the number of iterations. The main difference between K-means++ and K-means|| is the initialisation technique used with the centroids. K-means|| is initiated by randomly choosing the first centroid as a starting point with uniform distribution, C←c1. The initial cost of the clustering is computed after this selection: ϕ = ϕx(C), where ϕx(C) = x∊X d2(x,C). Then, each x∊X is sampled with probability px = l•d2(x,C) ϕx(C) in log ϕ iterations. The sampled points are then added to (C). The number of points for each iteration is set as one. In the final step of the algorithm, a total of l log ψ points are obtained, which are clustered in k centres. The algorithm for this process is outlined in Fig. 9. Figure 9Open in figure viewerPowerPoint Scalable K-means++ (K-means||) Apache Spark is used in the K-means|| method, where the user must determine the following parameters: desired number of clusters, k; maximum number of iterations where the algorithm could be executed, max iterations; and number of iterations needed to execute the algorithm completely, runs. The parameter initialisation mode indicates the initialisation type. Further, a set of centres can be introduced using the initial model option. Finally, the number of steps that will be executed during the K-means++ phase, the initialisation steps, also a predefined error threshold for convergence, must be specified. The operations are summarised as follows. First, the data are distributed to multiple slave nodes. The main node is used to prepare the environment of the algorithm, where the slave nodes are assigned to run the loop in line 4 of Algorithm 1 in a parallel manner. In the loop, a total of 2000 points (on average) for each run are sampled, with a probability proportional to their squared distances from the centres. Upon finishing the loop, more than k candidate centres were obtained for each run. By the number of points in the data set mapped, each candidate centre is weighed to it. Finally, the local K-means++ algorithm is executed on the weighted centres in order to filter the candidates. The final classification/clustering of the new input data is achieved using the final resulting centroids. The set of initially anonymous data points is effectively turned into a set of data points, each with a class identity. In the context of the current partitioning and classification method, those subbands in the same group exhibiting similar feature values are placed together in order to have more accurate matches. 3.10 Arrangement of the database The databases should be indexed and organised for efficient search and retrieval. The proposed steps are as follows: Step 1: Identify a global key for each stored image. The key value represents the group number that includes its subband features and combined key value (via Morton order traversal) which is more accurate [14]. Step 2: In order to prepare the database for the search processes, each group is ranked in ascending order based on the first SV σ1. Step 3: Following ranking of all groups, each group is divided into two bins (bin1 contains σ1 features and bin2 contains σ2 features). Step 4: The database is distributed into two B-tree structures, and the generated global key is used to traverse the two B-trees. Step 5: The images are stored at the leaf nodes of the two B-trees (shown in Fig. 10). Figure 10Open in figure viewerPowerPoint One of the two B-trees structure used to store the bins 3.11 Proposed search and retrieval technique The proposed search method is based on the half search method and a parallel search technique in order to improve the search process within each bin of features. The feature groups are separated and distributed into two databases, both of which are organised as B-tree based on the global index key of the images. The search for the query image is carried out by the global key, which is used to traverse a leaf node of the tree to reach the specific group. Upon reaching the bin, the proposed half search method is used to search for and retrieve the candidates inside