Fingerprint verification using the traveling salesman problem solution and decomposition of the vicinity of the minutiae

Abstract

The article presents an example of verification of the fingerprint database by the method of solving the problem of a salesman using the decomposition of the neighborhood of the nearest minutes. The solution of this problem is resistant to linear, angular deformations, mixing of points. This method provides the correct solution for a small number of points, for a large number of points there is a cross section of the contours, the solution is not optimal. Therefore, to reduce the processing time and calculate the metric, a modified algorithm for solving the problem by the method of branches and boundaries, namely the alignment and exclusion of arcs on each cycle of the optimal route. Verification is based on the creation of local structures for each minute of the imprint, because it is the local structures that are resistant to deformation. Building global structures very often does not lead to good quality indicators, as there is a problem with the centering of the entire sample. A complete list of tests of fingerprint database templates during their verification by this method has been carried out. The use of decomposition of characteristic features provides greater stability when adding false and erasing true minutes. The results of the article show the values of pairwise comparisons of two templates for true and false tests. The indicators of false rejection rate (FRR), false access rate (FAR), single equivalent error rate (EER) were studied.