with Extension of Segmentation Methods

Abstract

Edge detectors are studied in the paper. The visual range of the spectrum is the most informative for humans in terms of evolution. The division of boundary detectors is effective in a number of tasks. In particular, in this paper, the authors test the effectiveness of these methods from a subjective point of view. The article collects for comparison the results of the most popular methods of defining boundaries. Several images from a standard open source database are presented for analysis. Boundary/edge search methods were chosen to perform pattern recognition and scene analysis experiments because contours are usually the most informative and redundant features of the image being processed. The following methods are considered in the work. The Sobel filter is a discrete differential filter that calculates the approximate value of the gradient or gradient rate for the brightness of the image. The Previta filter is a border selection method in image processing that calculates the maximum response on a plurality of convolution cores to find the local orientation of the border in each pixel. The Roberts filter is one of the earliest boundary selection algorithms that calculates the sum of the squares of the differences between diagonally adjacent pixels. The Canney method is a boundary detection operator that uses a multi-step algorithm to detect a wide range of boundaries in images. The Canny Boundary Detector algorithm is not limited to calculating the image gradient. Only the maximum points of the image gradient remain in the border contour. Note that the Prewitt and Sobel method was studied in three versions in order to see all the positive and negative components of these filters. Edge detectors, fingerprints, data processing.

Keywords

• Methods

1. Introduction

Boundary selection is widely used to solve the following practical problems: car number recognition [ 1 ], cartography [ 2 ], clustering, medicine [ 3 ], finding text, figures or complex objects, such as people in the image [ 4 ]. Known methods for identifying the boundaries of objects in the image and proposed a method for identifying fingerprints.

Image segmentation is the division of an image into areas that are not similar in some way. It is assumed that the areas correspond to real objects or their parts, and the boundaries of the areas correspond to the boundaries of objects. Segmentation plays an important role in the tasks of image processing and computer vision [ 5 ]. Segmentation is necessary in pattern recognition and scene analysis, as contours are usually the most informative and redundant features of the image being processed.

In the recognition process, recognition accuracy and shorter response times are always desirable when it is necessary to identify a person in a system with a database consisting of millions of fingerprints. In some systems, the size of the database is constantly increasing. EMAIL: (M.

Nazarkevych); [e-mail]

2022 Copyright for this paper by its authors.

Segmentation of low quality images is a difficult task. Accurate segmentation of fingerprint images directly affects the efficiency of extracting small details. If more background areas are included in the segmented fingerprint of interest, more false functions appear. If some foreground areas are excluded, useful features may be missed. For image segmentation, methods based on various statistical and probabilistic models, cluster analysis methods, threshold and gradient methods, and graph theory methods were most widely used [ 6 ].

Threshold selection is a major problem with segmentation algorithms. Using different segmentation thresholds allows you to get different results. Automatic selection of the optimal threshold is a very difficult task. The proposed method allows you to segment the image without selecting a threshold. At the same time the base of segments allowing to store their attributes for the subsequent analysis is formed.

When using traditional clustering methods, the feature space of image elements is divided into areas (clusters) and R( )=1 , when all are included in one cluster. All are distributed in clusters, and then the connected elements of one cluster are combined into segments In this method, homogeneity is considered first of all.

Image segmentation is typically used to highlight objects and borders (lines, curves, etc.) in images. The result of image segmentation is a set of segments that together cover the entire image, or a set of contours selected from the image. All pixels in a segment are similar in some characteristic or calculated property, such as color, brightness, or texture. Neighboring segments differ significantly in this characteristic [ 7 ].

Boundary selection [ 8 ] is one of the important tasks of computer vision. The difficulty of solving this problem is due to the sensitivity of the methods to noise [ 9 ], brightness variance and to the intersection of objects. Given the non-stationary conditions of obtaining input images and the high sensitivity of algorithms for their processing to noise in the input data, there is a need to build a deterministic process of applying a particular algorithm. It should be noted that in the practical application of the Kenny algorithm, researchers focused on the analysis of each type of input data separately, without comparing the results between different types of images.

Segmentation is usually understood as the process of finding homogeneous areas in an image. This step is very difficult and is generally not fully algorithmized for arbitrary images. Note that one of the most effective methods of building areas involves the selection of starting points or with the help of an operator (centroid binding algorithm), or automatically. The method of watersheds based on the search for local minima with the subsequent grouping of areas around them in terms of connectivity is effective here [ 10 ].

2. Development of a Method for Finding Boundaries to Construct Contours of Minutions in Fingerprints

The purpose of finding boundaries in finding boundaries (curves) is to change the brightness or color [ 11 ]. In the future, the contours of objects are constructed from the boundaries, and from them scenes. The input data for the algorithm are images with coordinates x, y, where each element contains three color components - red, green and blue, denoted x,y red(I), x,y green(I), blue(I ) x,y . The result of the algorithm is a matrix , , each element of which is equal to 1, if the pixel with coordinates (x, y) is the limit of 1, or 0.

The solution of this problem must meet the requirements [ 12 ] of which the following:  The algorithm must find as many boundaries as possible present in the image.  The found boundaries should be as close as possible to the real boundaries.  One real boundary should not create several parallel boundaries at the output.  Noise should not create non-existent boundaries.

To check the result of the algorithm, it is necessary to find the real boundaries of objects in the image and construct a reference matrix , ,, then calculate the degree of similarity of matrices φ by the formula = | 1, | ∑ , {1, ℎ 0, ℎ , = , , ≠ , (1) where | , | is the number of elements in the matrix E.

Since the known methods of identifying the boundaries of objects in the image are based on the analysis of a photograph in shades of gray, it is necessary to convert a color image into a halftone [ 13 ]. You can use object boundary identification methods for this image. Converting to grayscale is performed for each pixel of the color image.

To eliminate the influence of inhomogeneous illumination of the image, it is advisable to exclude the general background from it and increase its contrast [ 14 ]. Exclusion from the general background image is carried out in two stages. The first image forms a background image, and the second subtracts the background image matrix from the main image represented by the two-dimensional matrix. The value of each pixel of the background image is the arithmetic mean of the intensities of neighboring pixels. The number of adjacent pixels is selected depending on the thickness of the boundaries of the papillae of the fingers.

Contrast adjustment is performed by “stretching” the initial brightness range to the range from the minimum possible to the maximum possible brightness.

One of the classical methods of determining the boundaries of objects in the image can be used to highlight the boundaries of the papillae of the fingers [ 15 ]. Such methods include the Sobel filter [ 16 ], the Previta filter [ 17 ], the Roberts filter [ 18 ], the Lapsassian-Gaussian filter [ 19 ] and the Canney method [ 20 ].

The Sobel filter is a discrete differential filter that calculates the approximate value of the gradient or the norm of the gradient for the brightness of the image. The Sobel filter is based on the convolution of the image by small integer filters in the vertical and horizontal directions.

The Previta filter is a border selection method in image processing that calculates the maximum response on a plurality of convolution cores to find the local orientation of the border in each pixel. This method of selecting borders is still a substitution of border templates, because the image is mapped to a set of templates, and each represents some orientation of the border. The size and orientation of the border in a pixel is determined by a pattern that best corresponds to the local area of the pixel.

The Roberts filter is one of the earliest boundary selection algorithms that calculates the sum of the squares of the differences between diagonally adjacent pixels. This can be done by convolving the image with two cores. The conversion of each pixel by a Roberts filter can show a derived image along non-zero diagonals, and the combination of these converted images can also be considered as a gradient from the top two pixels to the bottom two.

The Laplace-Gaussian filter is an analogue of the continuous Laplace operator, defined as a relation on a graph or a discrete grid. The discrete Lapsasian-Gaussian is defined as the sum of the second derivatives and is calculated as the sum of the color intensity differences on the neighbors of the central pixel.

The Canny method is a boundary detection operator that uses a multi-step algorithm to detect a wide range of boundaries in images. The Canny boundary detector algorithm is not limited to calculating the image gradient. Only the maximum points of the image gradient remain in the border contour. Boundary direction information is used to delete points right next to the boundary and not to break the boundary itself in the area of local gradient maxima.

We will evaluate the methods of identifying the boundaries of objects by determining the degree of discrepancy (1).

= +| − |+ + ℎ (2) where is the accuracy factor that characterizes the quality of the method, – is the actual number of bubbles in the photo, obtained by reference manual calculation, – is the number of bubbles identified by the appropriate method of determining the boundaries, – is the number of unidentified bubbles (errors of the first kind), ℎ – the number of misidentified bubbles (errors of the second kind). Maximizing the value of the accuracy factor indicates the best identification results [ 21 ]. The best identification results were shown by the Canney method. Its results at this stage of the study are acceptable for solving the problem of automation of obtaining and processing statistical information. To compare the two histograms, we use Pearson's criterion 2 s: 2 = ∑ =1 ( − )

2 where is Pearson's criterion, is the number of identified bubbles corresponding to the ith interval of radii, yi is the actual number of bubbles corresponding to the ith interval of radii, k is the number of data columns (intervals of the range of admissible radius) [ 22 ].

3. Application of the

Kenny

Algorithm to

Highlight the

Boundaries of

Fingerprints

Kenny's algorithm is an operator for selecting image boundaries. Kenny's goal was to develop an (3) (4) (5) , = , ∙ , , , , = 2 2 1 2 2

2+ 2 =

1 159 4 2 4 ||5 2 4 9 9 4 12 5 12 15 12 5 4 9 9 4 12 2 4 5|| 4 2 where is the scattering coefficient.

The Kenny operator uses Gaussian erosion with σ=1.4

The search for gradients is to mark the boundaries where the gradient becomes most important. They can have different directions, so the Kenny algorithm uses four filters to identify horizontal, vertical, diagonal edges in a blurred image. optimal algorithm for detecting boundaries that satisfy three criteria.

1. Good detection (Kenny interpreted this property as increasing the signal-to-noise ratio). 2. Good localization (qualitative detection of the border position).

3. A single solution for one boundary.

The main stages of the basic algorithm:

Convert a color image to grayscale.

The color image is converted to shades of gray. Constants in front of the corresponding color components x,y red( , ), green( , ) and blue( , ) obtained empirically, taking into account the physiological characteristics of human perception of color. The algorithm is sensitive to noise in the image, therefore, to remove the noise used a Gaussian = σ , where , is output pixel; x,y; I is input pixel; x, y pixel coordinates; , , is a Gaussian filter given by the formula where Sx,y is output pixel, Ix,y is input pixel, x, y are pixel coordinates, , , is Gaussian filter, which is given by the formula:

The angle of inclination of the gradient is rounded and can take on values 0, 45, 90, 135. = √ 2 + 2 Θ = (

)

4. Implementation of the Sobel Algorithm for Highlighting the Boundaries of

Fingerprints

The marginal areas of digital photography represent statistically complex curves in the image, along which there is a sharp change in brightness. It is proposed to use the Sobel operator as an algorithm for selecting edges [ 23 ]. This algorithm is based on calculating the approximate value of the brightness gradient. The advantage of the Sobel operator is the simplicity of calculations. The algorithm is based on image convolution in two directions - horizontal and vertical. The formation of a gradient image using the Sobel operator occurs according to the following rules: ( , ) = ‖∇ ( , )‖ = √ 12 +

22 = ( , ) ∙

5. Implementation of the Prewitt Algorithm for Highlighting the Boundaries of Fingerprints

Prewitt [ 24 ] is a method of finding contours in image processing, which calculates the maximum limit of a set of convolution of cores to detect the local orientation of the edge for each pixel. The Prewitt Edge Detector file is an appropriate way to estimate the size and orientation of an edge. Although Differential Gradient Edge Detection requires a fairly time-consuming calculation to estimate orientation by magnitudes in the x and y directions, Previtt edge detection obtains orientation directly from the nucleus with the maximum response. The set of cores is limited to eight possible orientations; however, experience shows that the most direct estimates are not much more accurate. On the other hand, a set of cores requires eight convolutions for each pixel, while a set of cores in the gradient method requires only two, one core is sensitive to the edges in the vertical direction and one to the horizontal direction, as shown in Fig. 1.

This algorithm works on the principle of determining the maximum response on the set of matrices used to detect the local orientation of the boundaries in each pixel. Various matrices are used for this purpose. You can get eight from one matrix by rearranging its coefficients. The maximum value of each pixel is the pixel in the resulting image. Its values an be in the range from 1 to 8, depending on which matrix gave the greatest result. This method is also called border pattern substitution. The image is mapped to a set of templates, each of which shows the location of the borders. Then the location of the border in the pixel is formed by a pattern that most closely matches the nearby pixel in the neighborhood.

6. Experimental Investigations

Experimental studies of the separation of the edges of the papillomas of the fingers were performed on the basis of the Prewitt method, and the separation of the border by the Prewitt method along the X and Y axes, the Sobel algorithm horizontally and vertically was studied, and the boundaries were separated by the Canney method. The results of the experiments are shown in Fig. 2, 3 and 4 for three different fingerprint samples. Visually, different results are observed, but each of the processed fingerprints has its own positive aspects of recognition. Before applying the edge selection methods, it is advisable to filter the image from the effects of noise, which are described in [ 25, 26 ]. The hardware used in this study in preparation for the experiments is shown in [ 27, 28 ]. In general, the construction of the information system is built in [ 29 ]. Real-time synchronization for computer vision systems is presented in [ 30 ]. Statistical estimates of the developed experiments are taken from [ 31 ], but in this study are not given. [ 32 ] shows machine learning tools for fingerprint identification.

7. Conclusions

The paper shows the experiment as an element of pre-processing or for subjective evaluation [3336]. In addition, this study shows the possibility of applying these methods in other areas [ 14, 25, 37– 40 ]. The effectiveness of the considered methods in new / other areas is planned to be investigated in further works. The paper mentions the procedure of objective evaluation of efficiency and shows the way to the implementation of automatic fingerprint comparison.

The fact that in some conditions or for certain tasks a certain method is more effective than another, and in others on the contrary - this is normal. And, it is these experiments that have roughly shown which method is the most effective for extracting informational features from fingerprints and we can work with them further. And which is inefficient and no need to spend effort on it when solving problems of automatic analysis of fingerprints.

8. References

[35] Boyko, I., Petryk, M., Fraissard, J. Investigation of the electron-acoustic phonon interaction via the deformation and piezoelectric potentials in AlN/GaN resonant tunneling nanostructures. 2021, 156, 106928 [36] Petryk, M.R., Boyko, I.V., Khimich, O.M., Petryk, M.M. High-Performance Supercomputer Technologies of Simulation and Identification of Nanoporous Systems with Feedback for nComponent Competitive Adsorption. Cybernetics and Systems Analysisthis, 2021, 57(2), pp. 316–328 [37] TajDini, M., et al., Wireless Sensors for Brain Activity—A Survey. In Electronics, Vol. 9, Issue 12, 2092. MDPI AG., 2020. https://doi.org/10.3390/electronics9122092 [38] Hu, Z. B., et al., Authentication System by Human Brainwaves Using Machine Learning and Artificial Intelligence. In Advances in Computer Science for Engineering and Education IV, 374–388, 2021. https://doi.org/10.1007/978-3-030-80472-5_31 [39] Boyko, I., Mudryk, I., Petryk, M., Petryk, M. High-Performance Adsorption Modeling Methods with Feedback-Influynces in n-component Nanoporous Media. 2021 11th International Conference on Advanced Computer Information Technologies, ACIT 2021 - Proceedingsthis link is disabled, 2021, pp. 441–444 [40] Mashkov, O., Krak, Y., Babichev, S., Bardachov, Y., Lytvynenko, V. Preface Lecture Notes on Data Engineering and Communications Technologiesthis link is disabled, 2022, 77, pp. v–vi

References

[1] Mohammed , B. N. , & Ahmad , H. B. ( 2021 ). Advanced car-parking security platform using Arduino along with automatic license and number recognition . Academic Journal of Nawroz University , 10 ( 1 ), 1 - 6 .

[2] Idrissi , A. , Saadi , M. , Manar , A. , Astati , Y. , Harrouchi , L. , & Nacer , J. E. ( 2021 ). Contribution of aeromagnetic cartography and lithostratigraphic studies to the identification of blind faults and the Cambrian deposits geometry in Jbel Saghro (eastern Anti-Atlas, Morocco) . Bollettino di Geofisica Teorica ed Applicata , 62 ( 1 ).

[3] Zhu , H. , Zhao , Y. , Wang , X. , & Xu , Y. ( 2021 ). Research on Data Analysis of Traditional Chinese Medicine with Improved Differential Evolution Clustering Algorithm . Journal of Healthcare Engineering , 2021 .

[4] Tang , J., Han, X. , Tan , M. , Tong , X. , & Jia , K. ( 2021 ). Skeletonnet: A topology-preserving solution for learning mesh reconstruction of object surfaces from rgb images . IEEE Transactions on Pattern Analysis and Machine Intelligence.

[5] Nazarkevych , M. , Dmytruk , S. , Hrytsyk , V. , Vozna , O. , Kuza , A. , Shevchuk , O. , ... & Sheketa , V. ( 2021 ). Evaluation of the effectiveness of different image skeletonization methods in biometric security systems . International Journal of Sensors Wireless Communications and Control , 11 ( 5 ), 542 - 552 .

[6] Wu , Z. , Li , C. , Li , M. , & Lim , A. ( 2021 ). Inertial proximal gradient methods with Bregman regularization for a class of nonconvex optimization problems . Journal of Global Optimization , 79 ( 3 ), 617 - 644 .

[7] Logoyda , M. , Nazarkevych , M. , Voznyi , Y. , Dmytruk , S. , & Smotr , O. ( 2019 ). Identification of Biometric Images using Latent Elements . CEUR Workshop Proceedings . EID: 2 - s2 . 0 - 85074659529

[8] Versaci , M. , & Morabito , F. C. ( 2021 ). Image edge detection: A new approach based on fuzzy entropy and fuzzy divergence . International Journal of Fuzzy Systems , 1 - 19 .

[9] Dronjuk I , Nazarkevych M , Troyan O. The modified amplitude-modulated screening technology for the high printing quality . InInternational Symposium on Computer and Information Sciences 2016 Oct 27 (pp. 270 - 276 ). Springer, Cham. DOI: 10 .1007/978-3- 319 -47217-1_ 29

[10] Torre , V. , & Poggio , T. A. ( 1986 ). On edge detection . IEEE Transactions on Pattern Analysis and Machine Intelligence, (2) , 147 - 163 .

[11] Ziou , D. , & Tabbone , S. ( 1998 ). Edge detection techniques-an overview. Pattern Recognition and Image Analysis C/C of Raspoznavaniye Obrazov I Analiz Izobrazhenii , 8 , 537 - 559 .

[12] Canny , J. ( 1986 ). A computational approach to edge detection . IEEE Transactions on pattern analysis and machine intelligence, (6) , 679 - 698 .

[13] Dronyuk I , Nazarkevych M , Poplavska Z . Gabor filters generalization based on ateb-functions for information security . InInternational Conference on Man-Machine Interactions 2017 Oct 3 (pp. 195 - 206 ). Springer, Cham.

[14] Nazarkevych , M. , Hrytsyk , V. , Voznyi , Y. , Marchuk , A. , Vozna , O. Method of detecting special points on biometric images based on new filtering methods . // 2021, CEUR Workshop Proceedings 2923, pp. 243 - 251

[15] Nazarkevych , M. , Lotoshynska , N. , Brytkovskyi , V. , Dmytruk , S. , Dordiak , V. , & Pikh , I. ( 2019 , September) . Biometric Identification System with Ateb-Gabor Filtering . In 2019 XIth International Scientific and Practical Conference on Electronics and Information Technologies (ELIT) (pp. 15 - 18 ). IEEE.

[16] Sudharshan , K. M. ( 2021 ). Design of a Sobel Edge Detection Algorithm on FPGA . Turkish Journal of Computer and Mathematics Education (TURCOMAT) , 12 ( 12 ), 2458 - 2462 .

[17] Munawar , H. S. , Aggarwal , R. , Qadir , Z. , Khan , S. I. , Kouzani , A. Z. , & Mahmud , M. A. ( 2021 ). A gabor filter-based protocol for automated image-based building detection . Buildings , 11 ( 7 ), 302 .

[18] Kang , M. , Xu , Q. , & Wang , B. ( 2008 ). A roberts' adaptive edge detection method . Journal of xi'an jiaotong university , 42 ( 10 ), 1240 - 1244 .

[19] Kong , H. , Akakin , H. C. , & Sarma , S. E. ( 2013 ). A generalized Laplacian of Gaussian filter for blob detection and its applications . IEEE transactions on cybernetics , 43 ( 6 ), 1719 - 1733 .

[20] Kistenev , Y. V. , et al. ( 2019 , March). Medical diagnosis using NIR and THz tissue imaging and machine learning methods . In Dynamics and Fluctuations in Biomedical Photonics XVI (Vol. 10877 , p. 108770J ). International Society for Optics and Photonics.

[21] Nazarkevych , M. , Oliiarnyk , R. , Nazarkevych , H. , Kramarenko , O. , & Onyshschenko , I. ( 2016 , August) . The method of encryption based on Ateb-functions . In 2016 IEEE First International Conference on Data Stream Mining & Processing (DSMP) (pp. 129 - 133 ). IEEE.

[22] Bogdan , M. ( 1995 ). Data driven versions of pearson's chisquare test for uniformity . Journal of statistical computation and simulation , 52 ( 3 ), 217 - 237 .

[23] Vincent , O. R. , & Folorunso , O. ( 2009 , June). A descriptive algorithm for sobel image edge detection . In Proceedings of informing science & IT education conference (InSITE) (Vol. 40 , pp. 97 - 107 ).

[24] Yang , L. , Wu , X. , Zhao , D. , Li , H. , & Zhai , J. ( 2011 , October) . An improved Prewitt algorithm for edge detection based on noised image . In 2011 4th International congress on image and signal processing (Vol. 3 , pp. 1197 - 1200 ). IEEE.

[25] V. Hrytsyk , Andrii Grondzal, Andrij Bilenkyj . Augmented reality for people with disabilities // CSIT' 2015 . - IEEE. - Lviv . - 14 -17 Sept . - p. 188 - 191 .

[26] Dronyuk , I. , Nazarkevych , M. , & Fedevych , O. ( 2015 , October) . Synthesis of Noise-Like Signal Based on Ateb-Functions. In International Conference on Distributed Computer and Communication Networks (pp. 132 - 140 ). Springer, Cham.

[27] Tsmots , I. , Teslyuk , V. , & Vavruk , I. ( 2013 , February) . Hardware and software tools for motion control of mobile robotic system . In 2013 12th International Conference on the Experience of Designing and Application of CAD Systems in Microelectronics (CADSM) (pp. 368 - 368 ). IEEE.

[28] Tsmots , I. , Tsymbal , Y. , Khavalko , V. , Skorokhoda , O. , Tesluyk , T. ( 2018 , August) . Neural-like means for data streams encryption and decryption in real time . In 2018 IEEE Second International Conference on Data Stream Mining & Processing (DSMP) (pp. 438 - 443 ). IEEE.

[29] Medykovskyy , M. O. , Pasyeka , M. S. , Pasyeka , N. M. , Turchyn , O. B. ( 2017 , September) . Scientific research of life cycle performance of information technology . In 2017 12th International Scientific and Technical Conference on Computer Sciences and Information Technologies (CSIT) (Vol. 1 , pp. 425 - 428 ). IEEE.

[30] Hrytsyk , V. , Nazarkevych , M. ( 2021 , May). Real-Time Sensing, Reasoning and Adaptation for Computer Vision Systems . In International Scientific Conference “ Intellectual Systems of Decision Making and Problem of Computational Intelligence” (pp. 573 - 585 ). Springer, Cham.

[31] Lytvyn , V. , et al. ( 2019 ). Development of the quantitative method for automated text content authorship attribution based on the statistical analysis of N-grams distribution . Eastern-European Journal of Enterprise Technologies , 6 ( 2 ), 28 - 51 . DOI: 10 .15587/ 1729 - 4061 . 2019 .186834

[32] Lytvyn , V. , et al. ( 2019 ). Design of a recommendation system based on Collaborative Filtering and machine learning considering personal needs of the user . Eastern-European Journal of Enterprise Technologies , 4 ( 2 ), 6 - 28 . DOI: 10 .15587/ 1729 - 4061 . 2019 .175507

[33] Nazarkevych , M. , et al. Evaluation of the effectiveness of different image skeletonization methods in biometric security systems // 2021, International Journal of Sensors, Wireless Communications and Control 11 ( 5 ), pp. 542 - 552 ; https://doi.org/10.2174/ 2210327910666201210151809

[34] Hrytsyk , V. , Nazarkevych , M. , Real-Time Sensing , Reasoning and Adaptation for Computer Vision Systems , ISDMCI 2021: Lecture Notes in Computational Intelligence and Decision Making , pp 573 - 585