Thinning Algorithms Analysis Minutiae Extraction with Terminations and Bifurcation Extraction from the Single-Pixeled Thinned Biometric Image

Thinning Algorithms Analysis Minutiae Extraction with Terminations and Bifurcation Extraction from the Single-Pixeled Thinned Biometric Image

Bhargavi Devi PottluaraiSharmila Kasinathan 

Department of Computer Science, Vels Institute of Science, Technology, & Advanced Studies, Chennai 600117, India

Corresponding Author Email: 
bhargavimowly@gmail.com
Page: 
225-230
|
DOI: 
https://doi.org/10.18280/i2m.210603
Received: 
28 October 2022
|
Revised: 
21 November 2022
|
Accepted: 
1 December 2022
|
Available online: 
31 December 2022
| Citation

© 2022 IIETA. This article is published by IIETA and is licensed under the CC BY 4.0 license (http://creativecommons.org/licenses/by/4.0/).

OPEN ACCESS

Abstract: 

Biometrics is the automatic identification of individuals based on physiological and behavioral characteristics. In today's technologically advanced digital world, it is regarded as the new digital key. There are two operating modes for biometric systems: identification and verification. The most popular biometric modalities are fingerprints, which are employed in many different industries and professions. Three distinct thinning methods are examined in this study. The proposed work looks into how thinning affects fingerprints, as well as minutiae extraction and texture feature analysis. To improve the quality of the fingerprints, thinning techniques such as Zhang- Suen's, Halls, and Guo Halls have been used. In terms of minutiae extraction, the thinning methods were compared. The minutiae points obtained were used to elaborate on the precision rate of fingerprints after processing. The simulations were run, and the experimental data was examined.

Keywords: 

fingerprint, minutiae, minutiae extraction, texture features, thinning

1. Introduction

Individuals are born with indelible qualities and idiosyncratic characteristics that are suitable for a biometric system. A vast number of modalities have been introduced as a result of the enormous benefits. Fingerprints and Iris [1], for example, have been used for over a century and are thus widely recognized as an exceptional method of recognition. Facial recognition, palm prints, iris scans, voice recognition, DNA, signature, hand geometry, and gait recognition are some of the other modalities used in various fields. According to Galton's taxonomy, ridges are curving lines that tend to form a loop, a whorl, a delta, or an arch. Fingerprint & Iris identification is accomplished in two ways: by studying and computing ridge patterns, and by extracting minutiae [2, 3]. Extraction of minutiae can improve identification and matching accuracy. As a result, it is increasingly commonly utilized. Minutiae extraction can be done with a minutiae extractor, such as the rGiaule's fingerprint & Iris extractor, although more sophisticated algorithms have been developed and employed. To achieve precision in minutiae extraction, a fingerprint must be meticulously preprocessed [4]. The previous study compares thinning methods, providing a quick insight of the quality of fingerprint that will be obtained after thinning. Binarization, direction, and thinning are the three stages of preprocessing. Before entering this stage of preprocessing, a fingerprint and iris image is checked to see if it is RGB or grayscale. An RGB image is one in which the red, green, and blue components of a single matrix pixel are defined. True color images are also known as RGB images. A grayscale image consists of 256 values. Its value range is from 1 to 255. Before being delivered to the preprocessing channel, an RGB image is converted to grayscale. Binarization of grayscale images is the process of converting a 256-value image to a matching image with only 0's and 1's, where 0 represents ridges and 1 represents furrows or valleys. Binary images are easy to store and edit because each pixel is converted to a single valued pixel. To generate a binary image, each pixel value of a grayscale image is compared to a threshold value. If the grey value of a pixel is less than the threshold value, the value is set to zero; otherwise, the value is set to one [5-9]. The next critical step in preprocessing is to translate the original grayscale image and the binary image. In a binarized image, the fingerprint ridges are frequently thick, making minutiae plotting difficult. Thinning is the process of reducing the width of each ridge to one pixel. A minutiae point can be extracted more easily from a perfectly thinned image than from a binarized image. Skeletonization is a type of image thinning in which pixels on the image's boundary are removed while the image's continuity is maintained [5-8, 10, 11].

Thinning images are the important requirement is one of the following reasons:

  • In case of high latency networks, this technique is used for the reduction of data.
  • Pattern processing time can be reduced.
  • Thinned patterns are useful to perform shape analysis.

The preprocessing and postprocessing procedures are demonstrated in this article. The thinning process is carried out using the Zhang-(ZS) Suen's and Guo-algorithms, Hall's which shape the pixels to a single pixel thickness range and identify any clustered patches of abnormalities that are observed in order to classify them as normal or abnormal. The bag of clusters is built using neighborhood k-means clustering. It implemented feature extraction through thinning in order to obtain precise location of erosion in the nerve or ridge values in the image [6-8]. Thinning algorithm plays a vital role in image processing and pattern recognition because of it simplifying nature. Images of different types are analyzed using this frequently used method. Thick object is converted to thin skeleton is the important reduction method in thinning algorithm. Zheng and Suen algorithms are the popular thinning algorithm.

In mathematical way, it can be defined as follows. Let P be a plane set, the boundary is B, and P represents a point in P. N is a nearest neighbour on the boundary B relies on P such that this is an only point greater than any other points. P is called as skeletal point of P iff P has 2 or more neighbours. The union of all skeletal points is called the skeleton or medial axis of P.

For diminishing, two different procedures are utilized, and the minutiae are extracted individually for each approach. The succeeding is how the paper is organized: Section 2 provides an ephemeral indication of image preparation and the methods that aid in the thinning process. Section 3 describes the texture feature analysis, which explains why thinning is an unavoidable step in fingerprint & iris processing. Section 4 describes the extraction of minutiae in relation to the thinning algorithms employed. Section 5 concludes the work.

2. Image Processing

Image processing (Figure 1) is the process of performing operations on an image to improve it or extract useful information from it. It is a type of signal processing in which an image is input and an image or image characteristics/features are output.

Figure 1. Image processing

The images are merged by simply concatenating the reconstructed images as in Figure 2. There are, however, fusion layers that can be implemented. Sensor-level, feature-level, decision-level, and Matching Notch level are the four levels. The degrees of fusion are divided into pre-mapping and post-mapping, with the sensor-level and feature-level falling under the pre-mapping classification and the latter two falling under the post-mapping classification. Data integration occurs before to stratification in pre-mapping blend, and data integration occurs subsequently charting into matching score/ decision space in post-mapping fusion. This process of integrating modalities aids in the acquisition of a new identity for the individual, hence increasing access security [9-14].

Figure 2. (a) Gray image and (b) RGB image

Image processing necessitates improving the quality of images before they are used in applications. A good quality biometric image is clear and free of noise, whereas medium and poor-quality images have a relative amount of noise, scar, and increased entropy. However, regardless of image quality, it should go through the preprocessing process for precise feature selection and extraction. A simulative processing can take into account various types of images, including RGB images, grayscale images, and binary value images. These images can then be classified for further processing into analogue or digital effectuation methods.

3. Thinning Algorithm

The Zhang Suen's -algorithm is an iterative procedure that makes multiple passes over each fingerprint pixel. This technique is repeated until the fingerprint ridge width no longer varies. Zhang-procedure Suen's algorithm is applied to a block of pixels in a given matrix with a centre value of one and eight neighbors. B is the sum of all the selected matrix's values (p). A(p) is given by the 8-neighborhood of the matrix p, which contains exactly one 4-connected component of 1's. The Hall's algorithm 6,18, on the other hand, is a parallel thinning algorithm that thins the fingerprint ridges while maintaining image connection [15-19]. The Zhang-Suen algorithm thinned the image, whereas the Hall algorithm skeletonized it as in Figure 3. The minutiae retrieved for the two algorithms resulted in a significant reduction in minutiae points, allowing for faster fingerprint processing. A parallel thinning for Zhang-Suen 3 x 3 neighborhood model is shown in below:

P8

P2

P3

P7

P1

P4

P6

P1

P5

The algorithm consist of two iterations, removing the pixels of south east boundary and north west corner pixels and vice versa.

Thinning algorithm for Zhang-Suen and Hall algorithms are given in algorithm 1 & 2.

To extract the skeleton of a picture, the method should first remove all contour pixels instead of those belonging to the skeleton. In phase-1, the contour point p1 is removed from the pattern, if it satisfies the following conditions:

(a) 2 R(p1) 6

(b) R(p1) = 1

(c) p2 × p4 × p6 = 0

(d) p4 × p6 × p8 = 0

In phase-2, the contour point p1 is deleted from the pattern, if it satisfies the following conditions:

(a) 2 B(p1) 6

(b) RA(p1) = 1

(c’) p2 × p4 × p8 = 0

(d’) p2 × p6 × p8 = 0

Figure 3. Thinning process flow

Zhang-algorithm Suen's is run on a block of pixels with a centre value of one and eight neighbours with values of zero. The sum of all the values of the chosen matrix is given by B in the algorithms described below (p). A(p) is given by the matrix p's 8-neighborhood, which contains exactly one 4-connected component of 1's. Endpoints are preserved, and this algorithm is not affected by contour noise. This algorithm is fast and guarantees the connectivity of the refined curve. This algorithm runs two sub-iterations in which the pixels that meet the conditions are deleted.

The Guo-Hall’s, Zhang-Suen’s thinning methodologies through the sliding Neighborhood application thoroughly aids in filtering and explicitly extracting the features from the fused biometric image. Richard. W. Hall developed this parallel thinning algorithm for image thinning. A fully parallel algorithm may have difficulty preserving image connectivity. However, this algorithm helps to overcome connectivity issues by partially serialising the algorithm by breaking the given iteration into distinct sub-iterations and was thus successful in preserving an image's connectivity.

Algorithm 1: Zhang-Suen’s Thinning algorithm

While points are deleted do

for all pixels p(i,j) do

if (2<=B(p) <=6) & (A(p) ==1)

Apply one of the following

a) (i-1) *(i, j+1) *(i+1, j) = 0 in odd iterations

b) (i-1, j) *(i, j+1) *(i, j-1) = 0 in even iterations

Apply one of the following

a) (i, j+1) *(i+1, j) *(i, j-1) = 0 in odd iterations

b) (i-1, j) *(i+1, j) *(i, j-1) = 0 in even iterations

then

Delete

p(i,j)

end if

end for

end while

end

Algorithm 2. Hall’s Thinning algorithm

While points are deleted do for all pixels

p(i,j) do

Determine delectability of pixel

if(1< B(p) < 7) & (A(p) = = 1)

then p(i,j) =

deletable end if end for

for all pixels p(i,j) do

if ((i-1,j) = (i+1,j) = 1 and (i,j+1) is deletable) &

((i,j+1) = (i,j-1) = 1 and (i+1,j) is deletable) &

((i,j+1),(i+1,j+1),(i+1,j) are deletable) then Do not

Delete p(i,j)

end if

end for

end while

end

The work is evaluated in MATLAB and all the images are labeled in Figure 4. In the first step, input image is given, then binarized image is converted from the input image. Then thinning using zang-suen method and Hall method is included for comparison. The experimental evaluation proves that the proposed method works well than the other two methods.

Figure 4. The various results relating to the analysis of thinning obtained in MATLAB

4. Sliding Neighborhood Operation with Crossing Number

The sliding neighborhood operation and crossing number technique are used to select the centroid and matrix to be used on the thinned image in order to identify the minutiae points. A sliding neighborhood is created pixel by pixel. In an image matrix, the neighborhood is a rectangle block that moves from one-pixel value to the next. The block moves from the left to the right of the matrix as it is slid. Always use the number 1 for the middle pixel.

Even Matrix

In an even matrix, the center point is formed by the leftmost pixel.

Odd Matrix

An odd matrix's center points are formed by the centre pixel.

Matrix of NXN

The center pixel in the matrix is the pixel closest to the left top pixel. If there are no values for the initial center pixel, the pixels surrounding it are padded with zero.

The milieu is now preferred, and the principles associated with it are generated using the crossing number procedure outlined in section IV. These values are then compared to the classified values in the algorithm to determine the terminations and bifurcations of the fingerprint image [20-24].

Connectivity for minutiae extraction

The connectivity of pixels for minutiae extraction has been done by using bwlabel in matlab. The connectivity of a matrix A is done by the following method:

The bwlabel in matlab, labels all the connected components, here (1,4) and (4,1) can be connected and hence labeled 1 and 2 respectively. (1,4) and (2,4) can be connected as well, so the next sequence after 2 is numbered consecutively in both cells. The next connectivity can be between (1,4) and (4,4) or (4,1) and (4,4) [25]. The best procedures for preprocessing and postprocessing are done and the thinning process is carried out using the Zhang-(ZS) Suen's and Guo-algorithms, Hall's which shape the pixels to a single pixel thickness range and identify any clustered patches of abnormalities that are observed in order to classify them as normal or abnormal. The bag of clusters is built using neighborhood k-means clustering. It implemented feature extraction through thinning in order to obtain precise location of erosion in the nerve or ridge values in the image [26-28]. The images are merged by simply concatenating the reconstructed images. There are, however, fusion layers that can be implemented. Sensor-level, feature-level, decision-level, and Matching Notch level are the four levels. The degrees of fusion are divided into pre-mapping and post-mapping, with the sensor-level and feature-level falling under the pre-mapping classification and the latter two falling under the post-mapping classification.

The unique and peculiar step which is followed by this algorithm is the initial checking of the deletability of the pixels. Once this condition is completed, it was observed that all the deletable pixels were deleted in parallel. The pixels that remained were kept only to preserve the connectivity in an image. Here B(p) denoted the summation of all values in the selected matrix. A(p) denotes the count of only one four connected components in p’s 8-neighborhood. The table given above shows the steps in the Hall’s algorithm. The first step checks for the deletability of the pixel p (i, j) following certain conditions. The first condition is to check for the summed-up value. If the value was between 1 and 7 and if there exist only one 4-connected component in p’s 8-neighborhood then it that pixel is deletable. The next set of conditions preserves the pixels in the vertical and horizontal two-width rectangle. The condition to check if pixels p4, p5 and p6 are deletable is to preserve a pixel in a 2 X 2 square.

5. Conclusions

Biometric modality image processing is a common domain that is studied and researched. Nonetheless, this research uses the new combination of iris and fingerprint biometrics to provide a more secure method of transmission and authentication. The suggested study also underlines the importance of using pre-processing technologies that improve feature extraction accuracy for future entailments. The difference in thinning between the automated and algorithmic processes was clear, with the built-in iterative morphing process producing a more thinned structure of the modalities and the Guo-algorithm Hall's producing a skeletonized outcome of the fused modality. The proposed work looks into how thinning affects fingerprints, as well as minutiae extraction and texture feature analysis The proposed methodology involves a merged biometric modality to enhance the authenticity of biometric image processing. The Guo-Hall’s, Zhang-Suen’s thinning methodologies through the sliding Neighborhood application thoroughly aids in filtering the features from the fused biometric image. In future, we plan to investigate the present study using hybrid deep learning strategies with the state of the arts methodologies.

  References

[1] Ross, A.A., Nandakumar, K., Jain, A.K. (2006). Handbook of Multibiometrics (Vol. 6). Springer Science & Business Media.

[2] http://www.fbi.gov/about-us/cjis/fingerprints_biometrics/biometric-center-of-excellence/modalities/fingerprint, accessed on 11 October 2022.

[3] Najeeb Ahmed, G., Kamalakannan, S., Kavitha, P. (2022). A machine learning approach for stochastic pattern analysis for the measurement of time-series datasets. Instrumentation Mesure Métrologie, 21(5): 199-205. https://doi.org/10.18280/i2m.210505

[4] Fan, Z., Lu, J., Rong, Y. (2016). Automated blood vessel segmentation of fundus images using region features of vessels. In 2016 IEEE Symposium Series on Computational Intelligence (SSCI), Athens, pp. 1-6. https://doi.org/10.1109/SSCI.2016.7849956 

[5] Jayachitra, S., Karthihadevi, M., Mariammal, G., Pushparaj, T. (2020). Implementation of morphological operation through intercept based euclidean distance algorithm. International Journal of Innovative Technology and Exploring Engineering, 9(4): 2472-2475. http://doi.org/10.35940/ijitee.C9051.029420

[6] Abraham, A., Thampi, S.M. (2012). Intelligent informatics. In International Symposium on Intelligent Informatics. http://dx.doi.org/10.1007/978-3-642-32063-7

[7] Deng, W., Iyengar, S.S., Brener, N.E. (2000). A fast parallel thinning algorithm for the binary image skeletonization. The International Journal of High Performance Computing Applications, 14(1): 65-81. https://doi.org/10.1177/109434200001400105

[8] Saha, P.K., Borgefors, G., di Baja, G.S. (2016). A survey on skeletonization algorithms and their applications. Pattern Recognition Letters, 76: 3-12. https://doi.org/10.1016/j.patrec.2015.04.006

[9] Virdaus, I.K., Mallak, A., Lee, S.W., Ha, G., Kang, M. (2017). Fingerprint verification with crossing number extraction and orientation-based matching. In Proc. 2017 Int. Conf. Next Gener. Comput., pp. 113-115.

[10] Palagyi, K., Kuba, A. (1998). A hybrid thinning algorithm for 3D medical images. Journal of Computing and Information Technology, 6(2): 149-164. 

[11] Das, S., Roy, A. (2016). Signature verification using rough set theory based feature selection. Computational Intelligence in Data Mining, 2: 153-161. https://doi.org/10.1007/978-81-322-2731-1_14

[12] Uddin, S., Haque, I., Lu, H., Moni, M.A., Gide, E. (2022). Comparative performance analysis of K-nearest neighbour (KNN) algorithm and its different variants for disease prediction. Scientific Reports, 12(1): 6256. https://doi.org/10.1038/s41598-022-10358-x

[13] Bataineh, B. (2018). An iterative thinning algorithm for binary images based on sequential and parallel approaches. Pattern Recognition and Image Analysis, 28(1): 34-43. https://doi.org/10.1134/S1054661818010030

[14] Bhatia, N. (2010). Survey of nearest neighbor techniques. arXiv preprint arXiv:1007.0085. 

[15] Hassanat, A.B., Abbadi, M.A., Altarawneh, G.A., Alhasanat, A.A. (2014). Solving the problem of the K parameter in the KNN classifier using an ensemble learning approach. arXiv preprint arXiv:1409.0919. 

[16] Gou, J., Ma, H., Ou, W., Zeng, S., Rao, Y., & Yang, H. (2019). A generalized mean distance-based k-nearest neighbor classifier. Expert Systems with Applications, 115: 356-372. https://doi.org/10.1016/j.eswa.2018.08.021

[17] Chicco, D., Jurman, G. (2020). Machine learning can predict survival of patients with heart failure from serum creatinine and ejection fraction alone. BMC Medical Informatics and Decision Making, 20(1): 1-16. https://doi.org/10.1186/s12911-020-1023-5

[18] Smith, J.W., Everhart, J.E., Dickson, W., Knowler, W.C., Johannes, R.S. (2011). In Proceedings of the Annual Symposium on Computer Application in Medical Care. 261 (American Medical Informatics Association). 

[19] Cherif, W. (2018). Optimization of K-NN algorithm by clustering and reliability coefficients: application to breast-cancer diagnosis. Procedia Computer Science, 127: 293-299. https://doi.org/10.1016/j.procs.2018.01.125

[20] Lamba, A., Kumar, D. (2016). Survey on KNN and its variants. Int. J. Adv. Res. Comput. Commun. Eng., 5: 430-435. https://doi.org/10.17148/IJARCCE.2016.55101

[21] Uddin, S., Khan, A., Hossain, M.E., Moni, M.A. (2019). Comparing different supervised machine learning algorithms for disease prediction. BMC Medical Informatics and Decision Making, 19(1): 1-16. https://doi.org/10.1186/s12911-019-1004-8

[22] Kumar, H., Kaur, P. (2011). A comparative study of iterative thinning algorithms for BMP images. International Journal of Computer Science and Information Technologies (IJCSIT). 

[23] Ali, M.A. (2012). An efficient thinning algorithm for arabic ocr systems. Signal & Image Processing, 3(3): 31. https://doi.org/10.5121/sipij.2012.3303

[24] Saeed, K., Albakoor, M. (2009). Region growing based segmentation algorithm for typewritten and handwritten text recognition. Applied Soft Computing, 9(2): 608-617. https://doi.org/10.1016/j.asoc.2008.08.006

[25] Ogiela, L. (2008). Syntactic approach to cognitive interpretation of medical patterns. In International Conference on Intelligent Robotics and Applications, Springer, Berlin, Heidelberg, pp. 456-462. https://doi.org/10.1007/978-3-540-88513-9_49 

[26] Xue, Z., Ming, D., Song, W., Wan, B., Jin, S. (2010). Infrared gait recognition based on wavelet transform and support vector machine. Pattern Recognition, 43(8): 2904-2910. https://doi.org/10.1016/j.patcog.2010.03.011

[27] Li, D., Wu, X., He, X. (2014). Depth-based thinning: A new non-iterative skeletonization algorithm for 2D digital images. In 2014 9th IEEE Conference on Industrial Electronics and Applications, pp. 1193-1197. https://doi.org/10.1109/ICIEA.2014.6931347

[28] Dong, J., Lin, W., Huang, C. (2016). An improved parallel thinning algorithm. In Proc. IEEE Int. Conf. on Wavelet Analysis and Pattern Recognition (ICWAPR), pp. 162-167. http://dx.doi.org/10.1109/ICWAPR.2016.7731637