CN1818927A

CN1818927A - Fingerprint identification method and system

Info

Publication number: CN1818927A
Application number: CNA2006100652975A
Authority: CN
Inventors: 车全宏; 陈书楷; 李治农
Original assignee: Beijing Zhongkong Technology Development Co ltd
Current assignee: Entropy Technology Co Ltd
Priority date: 2006-03-23
Filing date: 2006-03-23
Publication date: 2006-08-16
Anticipated expiration: 2026-03-23
Also published as: WO2007107050A1; CN100412883C

Abstract

The invention relates to a fingerprint identification method and a fingerprint identification system. In order to solve the problems of low identification rate and low identification speed of the existing identification method, the method comprises two steps of fingerprint feature extraction and feature matching: the characteristic extraction step is as follows: collecting a fingerprint image, and preprocessing and normalizing the fingerprint image; calculating a blocking directional diagram, extracting singular points, calculating a directional diagram, segmenting a background area and refining the singular points; filtering and enhancing the image; calculating ridge line density; binarizing and refining the image, extracting minutiae, verifying the minutiae, and deleting pseudo minutiae; the fingerprint minutiae, singular points, average ridge density and block directional diagram characteristics are finally compressed into a fingerprint characteristic template for storage; the characteristic matching step is as follows: collecting an on-site fingerprint image, and extracting fingerprint minutiae, singular points, average ridge density and block directional diagram characteristics of the on-site fingerprint image according to the steps; and comparing the fingerprint minutiae, singular points, average ridge density and block directional diagram characteristics of the fingerprint characteristic template and the field fingerprint image, and judging whether the finger is the same finger or not according to the similarity of the two characteristics. The method has the advantages of high recognition rate, high recognition speed, high reliability and strong operability.

Description

Fingerprint identification method and system

技术领域technical field

本发明涉及一种生物识别方法，特别是涉及一种指纹识别方法与系统。The invention relates to a biological identification method, in particular to a fingerprint identification method and system.

背景技术Background technique

目前，用于个人身份识别的指纹识别方法各异，但是，现有指纹识别方法都普遍存在识别率低，识别速度慢的问题。At present, there are different fingerprint identification methods used for personal identification, but the existing fingerprint identification methods generally have the problems of low identification rate and slow identification speed.

发明内容Contents of the invention

本发明的目的在于克服现有技术的上述缺陷，提供一种识别率高，识别速度快的指纹识别方法，本发明的目的还在于提供实施该方法的识别系统。The purpose of the present invention is to overcome the above-mentioned defects of the prior art, and provide a fingerprint recognition method with high recognition rate and fast recognition speed. The purpose of the present invention is also to provide a recognition system for implementing the method.

为实现上述目的，本发明指纹识别方法的特别之处在于由指纹特征提取和特征匹配两个步骤组成：In order to achieve the above object, the special feature of the fingerprint identification method of the present invention is that it consists of two steps of fingerprint feature extraction and feature matching:

特征提取步骤是：采集指纹图像，对指纹图像进行预处理和规格化；计算分块方向图提取奇异点，计算方向图、分割背景区域并细化奇异点；图像的滤波与增强；计算脊线密度；二值化图像并细化，提取细节点，细节点验证，删除伪细节点；指纹细节点、奇异点、平均脊密度和块方向图特征最终被压缩成为指纹特征模板存储；The feature extraction steps are: collect the fingerprint image, preprocess and normalize the fingerprint image; calculate the block direction map to extract singular points, calculate the direction map, segment the background area and refine the singular points; filter and enhance the image; calculate the ridge line Density; binarize the image and refine it, extract minutiae points, verify minutiae points, and delete false minutiae points; fingerprint minutiae points, singular points, average ridge density and block orientation map features are finally compressed into fingerprint feature template storage;

特征匹配步骤是：采集现场指纹图像，按上述步骤提取现场指纹图像的指纹细节点、奇异点、平均脊密度和块方向图特征；对比指纹特征模板与现场指纹图像的指纹细节点、奇异点、平均脊密度和块方向图特征，通过两者特征的相似度来判断是否是同一手指。此指纹识别方法具有识别率高，识别速度快的优点。The feature matching step is: collect the on-site fingerprint image, and extract the fingerprint minutiae point, singular point, average ridge density and block direction map features of the on-site fingerprint image according to the above steps; compare the fingerprint feature template and the fingerprint minutiae point, singular point, The average ridge density and block pattern features are used to judge whether they are the same finger or not by the similarity of the two features. This fingerprint recognition method has the advantages of high recognition rate and fast recognition speed.

作为优化，特征匹配步骤是：As an optimization, the feature matching step is:

分别计算数据库模板和现场指纹模板中细节点对连线距离、细节点对连线与细节点方向的夹角和细节点对连线的角度；规定细节点对连线距离上限值和下限值，删除细节点对连线距离大于此上限值和小于此下限值的细节点对数据，得到一个较小范围的细节点对数据U；Calculate the minutiae point-to-line distance, the angle between the minutiae point-to-line and the minutiae direction, and the angle of the minutiae-to-line in the database template and the on-site fingerprint template; specify the upper limit and lower limit of the minutiae point-to-line distance value, delete the minutiae point pair data whose distance between the minutiae point pair is greater than this upper limit and less than this lower limit value, and obtain a smaller range of minutiae point pair data U;

采用直方图计算旋转角度；Use the histogram to calculate the rotation angle;

把来自数据库的指纹模板的各个角度参数，包括细节点角度、奇异点角度、分块方向图和匹配细节点对U中的连线方向等，按照上一步计算的角度进行旋转，使得它同现场采集的指纹模板具有一致方向：Rotate the angle parameters of the fingerprint template from the database, including minutiae point angle, singularity point angle, block orientation diagram, and the connection direction in the matching minutiae point pair U, etc., according to the angle calculated in the previous step, so that it is the same as the on-site The collected fingerprint templates have a consistent direction:

从U中删除掉对应细节点角度差大于一个指定值的匹配点对，使U中的匹配细节点对只包含最可靠的匹配细节点对；Delete the matching point pairs whose corresponding minutiae point angle difference is greater than a specified value from U, so that the matching minutiae point pairs in U only contain the most reliable matching minutiae point pairs;

同样的方法，计算行列方向的直方图，计算所有匹配细节点对的对应细节点的行列座标差的统计直方图，找出这两个数组中的最大值点，就是两个指纹模板在进行旋转角度对齐后的平移量；In the same way, calculate the histogram in the row and column direction, calculate the statistical histogram of the row and column coordinate difference of the corresponding minutiae points of all matching minutiae point pairs, and find the maximum point in the two arrays, that is, the two fingerprint templates are in progress. The amount of translation after the rotation angle is aligned;

把来自数据库的指纹模板的各个位置参数，包括细节点坐标、奇异点座标、块方向位置等，进行平移，两个指纹模板完全对齐；Translate each position parameter of the fingerprint template from the database, including minutiae point coordinates, singular point coordinates, block direction position, etc., and the two fingerprint templates are completely aligned;

从U中删除掉包含行列座标差大于一个指定值的细节点对的匹配对，这些匹配对的相似度累加起来得到两个指纹模板细节点集的最终相似度；Delete the matching pairs containing the minutiae point pairs whose row and column coordinate difference is greater than a specified value from U, and the similarity of these matching pairs is added up to obtain the final similarity of the minutiae point sets of the two fingerprint templates;

计算出全局特征的相似度：Calculate the similarity of global features:

奇异点相似度是两两比对奇异点的位置、方向和类型，得到的相似度相加；The similarity of singular points is the sum of the similarities obtained by comparing the position, direction and type of singular points in pairs;

平均脊密度相似度是两个指纹模板脊密度的差并取倒数；The average ridge density similarity is the difference between the ridge densities of the two fingerprint templates and the reciprocal;

块方向图的相似度是在两个指纹模板有效区域的公共部分，计算方向的差值，累加后平均并取倒数；The similarity of the block direction graph is the common part of the effective area of the two fingerprint templates, calculate the difference of the direction, accumulate and average and take the reciprocal;

最后的两个指纹模板的相似度由上面的局部和全局特征相似度融合而成；The similarity of the last two fingerprint templates is fused by the above local and global feature similarities;

进行一对多的识别时，先将数据库中指纹模板的平均脊密度进行排序，对现场指纹进行识别时，先与数据库中的平均脊密度最接近的指纹模板进行匹配，以加快识别速度；平均脊密度是整个指纹图像的平均脊密度。When performing one-to-many identification, first sort the average ridge density of the fingerprint templates in the database, and when identifying on-site fingerprints, first match the fingerprint template with the closest average ridge density in the database to speed up the identification; The ridge density is the average ridge density of the entire fingerprint image.

作为优化，指纹特征提取时：指纹图像表示为一个二维矩阵，每一个像素就是矩阵的一个元素，取值为0～255，矩阵的维度就是图像的宽和高；As an optimization, when extracting fingerprint features: the fingerprint image is represented as a two-dimensional matrix, each pixel is an element of the matrix, the value is 0 to 255, and the dimension of the matrix is the width and height of the image;

指纹的细节点是指指纹脊线上的端点或者分叉点，指纹细节点包括如下特征：座标xy-表示在指纹图像中的位置；类型t-表示是脊线的端点还是分叉点；方向d-表示细节点的方向，若是端点型的细节点，则该方向的从细节点位置指向脊线，若是分叉型细节点，则该方向从细节点位置指向分叉后的两条脊线的中间；脊密度g-表示在该细节点附近的脊线的平均密度；脊曲率c-表示脊线方向在此处的变化程度；The minutiae point of the fingerprint refers to the endpoint or bifurcation point on the fingerprint ridge line, and the fingerprint minutiae point includes the following features: coordinate xy-represents the position in the fingerprint image; type t-represents whether it is the endpoint of the ridge line or the bifurcation point; Direction d-indicates the direction of the minutiae. If it is an endpoint-type minutiae, then the direction points from the minutiae position to the ridge line. If it is a bifurcated minutiae, then the direction points from the minutiae position to the two ridges after the bifurcation The middle of the line; ridge density g-indicates the average density of ridge lines near the detail point; ridge curvature c-indicates the degree of change of ridge line direction here;

分块方向图：是把指纹图像分成BLOCK_SIZE×BLOCK_SIZE大小的互不相交的小块，对每一块小图像，计算出脊线的平均方向，从而得到大小为Block direction map: divide the fingerprint image into small disjoint blocks of BLOCK_SIZE×BLOCK_SIZE size, and calculate the average direction of the ridge line for each small image, so that the size is

(HEIGHT/BLOCK_SIZE)×(WIDTH/BLOCK_SIZE)的分块方向图；分块方向图刻画指纹图像的全局脊线走向；另外，在分块方向图上用一个非法的方向值表示对指纹图像分割后的背景区域；(HEIGHT/BLOCK_SIZE) × (WIDTH/BLOCK_SIZE) block orientation diagram; the block orientation diagram depicts the global ridge direction of the fingerprint image; in addition, an illegal direction value is used on the block orientation diagram to indicate that the fingerprint image is segmented the background area of

奇异点：指纹图像上有一些地方的脊线方向不连续，这些地方称为指纹的奇异点，其特征有：座标x y，表示在指纹图像中的位置；类型t，奇异点分为核心点、双核心点以及三角点三种；方向d，表示沿着该方向远离奇异点时，指纹脊线方向变化最小。脊密度c，表示在该奇异点附近的脊线的平均间隔距离。Singular point: There are some places on the fingerprint image where the direction of the ridge line is discontinuous. These places are called singular points of the fingerprint. Its characteristics are: coordinate x y, indicating the position in the fingerprint image; type t, the singular point is divided into core There are three kinds of points, double-core points and triangular points; the direction d indicates that when the direction is far away from the singular point, the direction of the fingerprint ridge changes the least. The ridge density, c, represents the average distance between the ridges around the singular point.

作为优化，图像预处理和规格化是首先对图像进行均匀值滤波，使图像更加平滑，然后，对图像进行格式化；计算分块方向图提取奇异点是在块方向图上，先计算每一点的Poincare Index：As an optimization, image preprocessing and normalization is to first perform uniform value filtering on the image to make the image smoother, and then format the image; calculate the block orientation map to extract singular points on the block orientation map, first calculate each point Poincare Index:

${pindex pindex}^{n no} = = \frac{11}{π π} {Σ Σ}_{i i = = 00}^{n no} τ τ (({O o}_{((i i + + 11)) mod mod n no} - - {O o}_{i i}))$

$τ τ ((k k)) = = \{\begin{matrix} k k,, if if | | k k | | < < \frac{π π}{22},, \\ π π + + k k,, if if | | k k | | < < \frac{π π}{22},, \\ π π - - k k,, otherwise otherwise \end{matrix}$

其中，n为周围像素点的个数，O_i表示第i个点的方向；先取半径为1，即周边的8个点来计算Poincare Index，得p1，如果其Poincare Index非零，再以半径2，即周边的外一层来计算Poincare Index，得p2：p1与p2相同，说明该点是一个奇异点，若p1为1则是核心点型奇异点，若p1为-1则是三角点，若p1为2则是双核型奇异点；若p2与p1不同，但p2＞0，p1＞0，则是双核型奇异点；其他情况则不是奇异点。Among them, n is the number of surrounding pixel points, and O _i represents the direction of the i-th point; first take the radius as 1, that is, calculate the Poincare Index from the surrounding 8 points, get p1, if its Poincare Index is non-zero, then use the radius 2. Calculate the Poincare Index on the outer layer of the periphery, and get p2: p1 is the same as p2, indicating that the point is a singular point. If p1 is 1, it is a core point singular point, and if p1 is -1, it is a triangular point , if p1 is 2, it is a dual-nucleate singularity; if p2 is different from p1, but p2>0, p1>0, it is a dual-nuclei singularity; otherwise, it is not a singularity.

作为优化，计算方向图、分割背景区域并细化奇异点是：规格化后的图像，计算第一点的脊线方向，并同时计算出脊线方向的一致性，取得方向图，重新确定奇异点位置，从这些奇异点的原始位置出发，找到奇异点的精确位置，在新的位置，计算出新的奇异点方向。As an optimization, calculating the orientation map, segmenting the background area and refining the singular point is: after normalizing the image, calculate the ridge direction of the first point, and at the same time calculate the consistency of the ridge direction, obtain the orientation map, and re-determine the singularity Point position, starting from the original position of these singular points, find the precise position of the singular point, and calculate the new direction of the singular point at the new position.

作为优化，图像的滤波与增强是：通过各向异性滤波器处理后，得到增强的指纹图像；计算脊线密度是：先计算指纹脊线密度图，再对脊线密度图进行33×33的均值滤波。As an optimization, the filtering and enhancement of the image is: after being processed by an anisotropic filter, the enhanced fingerprint image is obtained; the calculation of the ridge line density is: first calculate the fingerprint ridge line density map, and then perform a 33×33 ridge line density map Mean filtering.

作为优化，二值化图像并细化是：用33×33均值滤波后的图像作为自适应的阀值来二值化增强后的图像；然后把二值化的图像细化成单点宽度的脊线图；图像细化是图像中的每一个黑色像素有8个相邻点，根据它们来判断当前点是否应该被改为白色。这样经过多次的重复扫描，直到没有一个黑色点被改成白色，就得到了细化的指纹脊线图。As an optimization, binarize the image and refine it: use the 33×33 mean-filtered image as an adaptive threshold to binarize the enhanced image; then refine the binarized image into a ridge with a single point width Line image; image thinning means that each black pixel in the image has 8 adjacent points, and it is judged based on them whether the current point should be changed to white. After repeated scanning in this way, until none of the black dots are changed to white, a refined fingerprint ridge map is obtained.

作为优化，提取细节点是：先消除毛刺和噪声，即通过扫描细化的脊线图，跟踪脊线，如果从脊线起点到终点的像素距离小于一个设定的阀值，就把它从细化图上抹去；然后，提取出细节点：即对图像上的任何一个黑色点，如果其相邻的8个点中，任选一个起始点，按顺时针方向扫描一周回到起始点，其颜色的变化如果是2次的话，说明该点是一个终结型细节点；如果是4次以上的话，该点是分叉型细节点，其他情况则可以忽略，通过扫描有效的指纹图像区域，得到了所有的细节点；As an optimization, the extraction of detail points is: first eliminate burrs and noise, that is, by scanning the refined ridge line map, track the ridge line, if the pixel distance from the starting point to the end point of the ridge line is less than a set threshold, it will be removed from Erase on the thinning map; then, extract the detail points: that is, for any black point on the image, if one of the 8 adjacent points is selected, a starting point is selected, and a circle is scanned in a clockwise direction to return to the starting point , if the color change is 2 times, it means that the point is a terminal minutiae point; if it is more than 4 times, the point is a bifurcated minutiae point, and other cases can be ignored. By scanning the effective fingerprint image area , get all the detail points;

在细节点处跟踪脊线，得到脊线的方向；细节点的脊线曲率，用方向的变化来表示，在指纹图像的方向图上，用该点附近的方向与该点的方向差值来计算曲率。Track the ridge line at the minutiae point to get the direction of the ridge line; the curvature of the ridge line at the minutiae point is expressed by the change of direction, and on the direction map of the fingerprint image, the difference between the direction near the point and the direction of the point is used to calculate Calculate the curvature.

作为优化，细节点验证和删除伪细节点是：任意一个细节点，若存在来一个细节点与之距离小于一个设定值D1，则删除该细节点；如一个端点型细节点与来一个端点型细节点距离小于一个设定值D2，且它们方向相反，则同时删除这两个细节点；如果一个端点型细节点与一个分叉型细节点距离小于一个设定值D3，且它们方向相反，则同时删除这两个细节点；如果一个细节点离指纹图像的无效区域小于一个设定值D4，且方向朝外，则删除该细节点；通过上述删除得到最终的细节点。As an optimization, the minutiae verification and deletion of pseudo-minutiae is: any minutiae, if there is a minutiae whose distance is less than a set value D1, then delete the minutiae; such as an endpoint minutiae and an endpoint If the distance between an end-type detail point and a bifurcation-type detail point is less than a set value D3, and their directions are opposite, the two detail points will be deleted at the same time. , then delete these two minutiae points at the same time; if a minutiae point is less than a set value D4 from the invalid area of the fingerprint image, and the direction is outward, then delete the minutiae point; the final minutiae point is obtained through the above deletion.

一种用于实施本发明指纹识别方法的识别系统，其特别之处在于包括指纹采集器、指纹识别系统、识别或和控制信号输出机构；其中包括指纹图像存储器、指纹图像处理器和指纹特征数据存储器；指纹图像处理器是利用要求1-9之一所述方法对指纹图像进行处理和识别。其具有识别率高，识别速度快，可靠性强，可操作性强的优点。An identification system for implementing the fingerprint identification method of the present invention, which is particularly characterized in that it includes a fingerprint collector, a fingerprint identification system, an identification or and a control signal output mechanism; including a fingerprint image memory, a fingerprint image processor, and fingerprint feature data Memory; the fingerprint image processor uses the method described in one of requirements 1-9 to process and identify the fingerprint image. It has the advantages of high recognition rate, fast recognition speed, strong reliability and strong operability.

其中：指纹细节点的特征表示(x，y，t，d，g，c)包含较多信息，有利于提高系统的识别率；指纹奇异点的特征表示(x，y，t，d，g)包含较多信息，有利于提高系统的识别率；平均脊线密度G作为一个全局特征，可以以此进行索引，辅助识别以加快速度。指纹的块方向图作为一个全局特征保存在指纹模板中，在比对过程中进行块方向图比对，其相似度融合到最后的结果中；奇异点的提取方法，可以快速计算出准确的奇异点位置和特征；各向异性滤波器用于增强指纹图像，效果很好；滤波器受指纹图像上的各点方向调制后，采用卷积的方法，对该点进行滤波。由于每一点的滤波器核都受到该点方向的调制，因此滤波的效果比对图像分块滤波要好得多；通过保存各个方向的各向异性滤波器系数，使得可以在卷积时，使用查表法。大大提高了滤波的速度；指纹比对的流程，指纹模板匹配的最后的相似度通过融合各种特征的相似度得到，这使得结果更为可靠；细节点对齐方法，该方法通过估计初步匹配的细节点连线对的变换参数，对估值进行统计生成的直方图中找到最终的变换参数。Among them: the feature representation (x, y, t, d, g, c) of fingerprint minutiae points contains more information, which is conducive to improving the recognition rate of the system; the feature representation of fingerprint singular points (x, y, t, d, g ) contains more information, which is beneficial to improve the recognition rate of the system; as a global feature, the average ridge density G can be indexed to assist recognition to speed up. The block orientation graph of the fingerprint is stored in the fingerprint template as a global feature, and the block orientation graph is compared during the comparison process, and its similarity is fused into the final result; the singular point extraction method can quickly calculate the accurate singularity The point position and characteristics; the anisotropic filter is used to enhance the fingerprint image, and the effect is very good; after the filter is modulated by the direction of each point on the fingerprint image, the convolution method is used to filter the point. Since the filter kernel of each point is modulated by the direction of the point, the filtering effect is much better than that of image block filtering; by saving the anisotropic filter coefficients in each direction, it is possible to use the query during convolution. table method. The speed of filtering is greatly improved; the process of fingerprint comparison, the final similarity of fingerprint template matching is obtained by fusing the similarity of various features, which makes the result more reliable; the method of minutiae point alignment, which estimates the initial matching The transformation parameters of the line pairs of the detail points, and the final transformation parameters are found in the histogram generated by statistics of the estimates.

采用上述技术方案后，本发明指纹识别方法具有识别率高，识别速度快，可靠性强，可操作性强的优点。After adopting the above technical solution, the fingerprint identification method of the present invention has the advantages of high identification rate, fast identification speed, strong reliability and strong operability.

附图说明：Description of drawings:

图1是本发明指纹识别方法中三种奇异点的示意图；Fig. 1 is the schematic diagram of three kinds of singular points in the fingerprint recognition method of the present invention;

图2是本发明指纹识别方法的流程图；Fig. 2 is the flowchart of fingerprint recognition method of the present invention;

图3是本发明指纹识别方法中p1的周边8个点的示意图；Fig. 3 is a schematic diagram of 8 points around p1 in the fingerprint identification method of the present invention;

图4是是本发明指纹识别方法中p2的周边12个点的示意图；Fig. 4 is a schematic diagram of 12 points around p2 in the fingerprint identification method of the present invention;

图5是本发明指纹识别方法中方向为零的各向异性滤波器核的示意图；5 is a schematic diagram of an anisotropic filter kernel whose direction is zero in the fingerprint recognition method of the present invention;

图6是本发明指纹识别方法中8个相邻点转换为表索引号22的构造示意图；Fig. 6 is the structure diagram that 8 adjacent points are converted into table index number 22 in the fingerprint recognition method of the present invention;

图7是本发明指纹识别方法中三种主要的细化脊线噪声图；Fig. 7 is three kinds of main refinement ridge line noise figures in the fingerprint recognition method of the present invention;

图8是本发明指纹识别方法中终结型细节点的相邻8点的颜色变化图；Fig. 8 is a color change diagram of 8 adjacent points of terminal minutiae in the fingerprint identification method of the present invention;

图9是本发明指纹识别方法中分叉型细节点的相邻8点的颜色变化图；Fig. 9 is a color change diagram of 8 adjacent points of bifurcated minutiae points in the fingerprint identification method of the present invention;

图10是本发明指纹识别方法中细节点对之间的连线图；Fig. 10 is a connection diagram between minutiae point pairs in the fingerprint identification method of the present invention;

图11是本发明指纹识别方法中的原指纹图像；Fig. 11 is the original fingerprint image in the fingerprint recognition method of the present invention;

图12是本发明指纹识别方法中的正规化后的指纹图像；Fig. 12 is the normalized fingerprint image in the fingerprint identification method of the present invention;

图13是本发明指纹识别方法中的指纹的方向图；Fig. 13 is the orientation diagram of the fingerprint in the fingerprint identification method of the present invention;

图14是本发明指纹识别方法中的指纹的增强图像；Fig. 14 is the enhanced image of the fingerprint in the fingerprint recognition method of the present invention;

图15是本发明指纹识别方法中的指纹的二值化图像；Fig. 15 is the binary image of the fingerprint in the fingerprint recognition method of the present invention;

图16是本发明指纹识别方法中的指纹的细化脊线图。Fig. 16 is a thinned ridge diagram of the fingerprint in the fingerprint identification method of the present invention.

下面结合附图和具体实例作更进一步的说明：Below in conjunction with accompanying drawing and concrete example for further description:

指纹识别算法涉及两个最主要的步骤：特征提取和特征匹配。The fingerprint recognition algorithm involves two main steps: feature extraction and feature matching.

特征提取：指纹的图像处理以及提取指纹全局和局部特征，并保存为指纹模板；Feature extraction: image processing of fingerprints and extraction of global and local features of fingerprints, and save them as fingerprint templates;

特征匹配：把两个指纹特征模板进行比对，得到一个匹配分数，然后根据这个分数决定两个指纹是否同一。Feature matching: Compare two fingerprint feature templates to get a matching score, and then determine whether the two fingerprints are identical based on this score.

一、特征提取1. Feature extraction

1、概念和约定1. Concepts and conventions

1)指纹图像的表示1) Representation of fingerprint image

指纹图像表示为一个二维矩阵，每一个像素就是个矩阵的一个元素，取值为(0～255)，矩阵的维度就是图像的宽WIDTH和高HEIGHT。指纹图像上的i行j列的灰度值表示为I_ij。The fingerprint image is represented as a two-dimensional matrix, each pixel is an element of the matrix, and the value is (0-255), and the dimension of the matrix is the width WIDTH and height HEIGHT of the image. The gray value of row i and column j on the fingerprint image is expressed as I _ij .

2)局部特征的表示2) Representation of local features

指纹的局部特征是指指纹脊线上的端点或者分叉点，称为指纹的细节点。指纹细节点包括如下特征(x，y，t，d，g，c)：The local feature of the fingerprint refers to the endpoint or bifurcation point on the fingerprint ridge line, which is called the minutiae point of the fingerprint. The fingerprint minutiae includes the following features (x, y, t, d, g, c):

座标xy：表示在指纹图像中的位置；Coordinate xy: indicates the position in the fingerprint image;

类型t：表示是脊线的端点还是分叉点；Type t: indicates whether it is the endpoint of the ridge or the bifurcation point;

方向d：表示细节点的方向。若是端点型的细节点，则该方向的从细节点位置指向脊线；若是分叉型细节点，则该方向从细节点位置指向分叉后的两条脊线的中间。Direction d: Indicates the direction of the minutiae point. If it is an end-type minutiae, then the direction from the minutiae point to the ridge; if it is a bifurcated minutiae, then this direction points from the minutiae to the middle of the two bifurcated ridges.

脊密度g：表示在该细节点附近的脊线的平均密度。脊线的间隔距离越大，密度就越小；Ridge density g: Indicates the average density of ridges near the minutiae point. The greater the distance between the ridges, the lower the density;

脊曲率c：表示脊线方向在此处的变化程度Ridge curvature c: Indicates how much the direction of the ridge changes here

3)全局特征的表示3) Representation of global features

分块方向图block pattern

把指纹图像分成BLOCK_SIZE×BLOCK_SIZE大小的互不相交的小块，对每一块小图像，计算出脊线的平均方向，从而得到大小为Divide the fingerprint image into disjoint small blocks of BLOCK_SIZE×BLOCK_SIZE size, and calculate the average direction of the ridge line for each small image, so that the size is

(HEIGHT/BLOCK_SIZE)×(WIDTH/BLOCK_SIZE)的分块方向图。块方向图刻画了指纹图像的全局脊线走向，把作为指纹图像的全局特征进行存储，用于以后的比对。另外，在分块方向图上用一个非法的方向值表示对指纹图像分割后的背景区域(此处没有指纹图像，或指纹图像质量太差)。(HEIGHT/BLOCK_SIZE)×(WIDTH/BLOCK_SIZE) block direction map. The block orientation graph depicts the global ridge direction of the fingerprint image, and stores the global features of the fingerprint image for future comparison. In addition, an illegal direction value is used on the block direction map to indicate the background area after the fingerprint image is segmented (there is no fingerprint image here, or the quality of the fingerprint image is too poor).

奇异点Singularity

指纹的脊线方向具有连续性的特征，即相邻位置的脊线方向一般来说是一致的、或者是变化不大。然而，指纹图像上也有一些地方的脊线方向不连续，这些地方称为指纹的奇异点。The ridge direction of the fingerprint is characterized by continuity, that is, the ridge directions of adjacent positions are generally consistent or have little change. However, there are some places where the ridge direction is discontinuous on the fingerprint image, and these places are called singular points of the fingerprint.

奇异点的特征有(x，y，t，d，c)：x y座标：表示在指纹图像中的位置。类型t：如图1所示，奇异点分为核心点1-1、双核心点1-2以及三角点1-3三种。方向d：表示沿着该方向远离奇异点时，指纹脊线方向变化最小。脊密度c：表示在该奇异点附近的脊线的平均间隔距离。平均脊线密度是整个指纹图像的平均脊线密度。The characteristics of the singular point are (x, y, t, d, c): x y coordinates: represent the position in the fingerprint image. Type t: As shown in Figure 1, there are three kinds of singular points: core point 1-1, double core point 1-2, and triangle point 1-3. Direction d: indicates that the direction of the fingerprint ridge changes the least when it is away from the singular point along this direction. Ridge density c: Indicates the average distance between ridges near the singular point. The average ridge density is the average ridge density of the entire fingerprint image.

2、算法流程2. Algorithm process

2.1流程图，请见附图2。2.1 Flowchart, please refer to attached drawing 2.

2.2图像预处理和规格化2.2 Image preprocessing and normalization

首先对图像进行3×3的均值滤波，使得图像更加平滑。Firstly, the image is filtered by 3×3 mean value to make the image smoother.

${R R}_{i i,, j j} = = \frac{{Σ Σ}_{y the y = = i i = = w w}^{i i + + w w} {Σ Σ}_{x x = = j j = = w w}^{j j + + w w} {I I}_{y the y,, x x}}{{((w w + + 11))}^{22}}$

其中，I_y，x是原始图像，R_y，x是平滑后的图像，这里取w＝1。Wherein, I _{y, x} is the original image, R _{y, x} is the smoothed image, here w=1.

然后，对图像进行规格化：Then, normalize the image:

${R R}_{i i,, j j} = = \frac{255255 (({I I}_{i i,, j j} - - {Min Min}_{i i,, j j}))}{{Δ Δ}_{i i,, j j}}$

Min_i，j＝I_i，j-Var_i，j Min _i,j = I _i,j -Var _i,j

Max_i，j＝I_i，j+Var_i，j Max _i,j =I _i,j +Var _i,j

Δ_i，j＝Max_i，j-Min_i，j Δi _,j =Max _i,j -Min _i,j

${Var Var}_{i i,, j j} = = \frac{{Σ Σ}_{y the y = = i i - - w w}^{i i + + w w} \overset{j j + + w w}{\underset{x x = = j j - - w w}{Σ Σ}} | | {I I}_{y the y,, x x} - - {S S}_{y the y,, x x} | |}{{((w w + + 11))}^{22}}$

其中S_y，x是原图像经过5×5的均值滤波的图像，Var的计算中，取一个较大的邻域w＝80。Among them, S _{y, x} is the image filtered by the mean value of 5×5 from the original image. In the calculation of Var, a larger neighborhood w=80 is taken.

2.3计算分块方向图提取奇异点2.3 Calculate the block direction map to extract singular points

分块方向图的计算与完整计算方向图的计算一样，只不过只计算分块的中心位置的方向就可以了，计算方向图的计算在下面会专门介绍。The calculation of the block direction diagram is the same as the calculation of the complete calculation direction diagram, except that only the direction of the center position of the block is calculated. The calculation of the calculation direction diagram will be specially introduced below.

在块方向图上，计算每一点的Poincare Index：On the block direction graph, calculate the Poincare Index of each point:

其中，n为周围像素点的个数，O_i表示第i个点的方向。为了保证计算的可靠性，先取半径为1，即周边的8个点来计算Poincare Index，得p1，如果其Poincare Index非零，再以半径2，即周边的外一层来计算Poincare Index，得p2。其中p1的周边8个点的示意图见附图3，p2的周边12个点的示意图见附图4。Among them, n is the number of surrounding pixel points, and O _i represents the direction of the i-th point. In order to ensure the reliability of the calculation, the Poincare Index is first calculated with a radius of 1, that is, the 8 surrounding points, and p1 is obtained. If the Poincare Index is non-zero, then the Poincare Index is calculated with a radius of 2, that is, the outer layer of the surrounding area. p2. The schematic diagram of 8 points around p1 is shown in attached drawing 3, and the schematic diagram of 12 points around p2 is shown in attached drawing 4.

存在如下情况：The following situations exist:

p1与p2相同，说明该点是一个奇异点，若p1为1则是核心点型奇异点，若p1为-1则是三角点，若p1为2则是双核型奇异点；若p2与p1不同，但p2＞0，p1＞0，则是双核型奇异点；其他情况则不是奇异点。p1 is the same as p2, indicating that the point is a singular point, if p1 is 1, it is a core point singular point, if p1 is -1, it is a triangle point, if p1 is 2, it is a dual-core singular point; if p2 and p1 different, but p2>0, p1>0, it is a dual-nuclear singularity point; other cases are not singularity point.

2.4计算方向图、分割背景区域并细化奇异点2.4 Calculate the direction map, segment the background area and refine the singular points

对规格化后的图像，通过下式计算每一点的脊线方向O_i，j For the normalized image, the ridge direction O _{i, j} of each point is calculated by the following formula

${G G}_{i i,, j j}^{xx xx} = = {(({G G}_{i i,, j j}^{x x}))}^{22},, {G G}_{i i,, j j}^{yy yy} = = {(({G G}_{i i,, j j}^{y the y}))}^{22},, {G G}_{i i,, j j}^{xy xy} = = {G G}_{i i,, j j}^{x x} {G G}_{i i,, j j}^{y the y}$

${G G}_{i i,, j j}^{x x} = = (({I I}_{i i - - 11,, j j + + 11} - - {I I}_{i i - - 11,, j j - - 11})) + + 44 (({I I}_{i i,, j j + + 11} - - {I I}_{i i,, j j - - 11})) + + (({I I}_{i i + + 11,, j j + + 11} - - {I I}_{i i + + 11,, j j - - 11}))$

${G G}_{i i,, j j}^{y the y} = = (({I I}_{i i + + 11,, j j - - 11} - - {I I}_{i i - - 11,, j j - - 11})) + + 44 (({I I}_{i i + + 11,, j j} - - {I I}_{i i - - 11,, j j})) + + (({I I}_{i i + + 11,, j j + + 11} - - {I I}_{i i - - 11,, j j + + 11}))$

${g g}_{i i,, j j}^{xx xx} = = \frac{{Σ Σ}_{y the y = = i i - - w w}^{i i + + w w} {Σ Σ}_{x x = = j j - - w w}^{j j + + w w} {G G}_{y the y,, x x}^{xx xx}}{{((22 w w + + 11))}^{22}},, {g g}_{i i,, j j}^{yy yy} \frac{{Σ Σ}_{y the y = = i i - - w w}^{i i + + w w} {Σ Σ}_{x x = = j j - - w w}^{j j + + w w} {G G}_{y the y,, x x}^{yy yy}}{{((22 w w + + 11))}^{22}},, {g g}_{i i,, j j}^{xy xy} = = \frac{{Σ Σ}_{y the y = = i i - - w w}^{i i + + w w} {Σ Σ}_{x x = = j j - - w w}^{j j + + w w} {G G}_{y the y,, x x}^{xy xy}}{{((22 w w + + 11))}^{22}}$

${O o}_{i i,, j j} = = {tan the tan}^{- - 11} \frac{22 {g g}_{i i,, j j}^{xy xy}}{{g g}_{i i,, j j}^{xx xx} - - {g g}_{i i,, j j}^{yy yy}}$

并同时计算出脊线方向的一致性C_i，j And at the same time calculate the consistency C _i,j of the ridge direction

${m m}_{i i,, j j} = = \sqrt{{g g}_{i i,, j j}^{xx xx} + + {g g}_{i i,, j j}^{yy yy}}$

${C C}_{i i,, j j} = = \{\begin{matrix} \frac{\sqrt{{(({g g}_{i i,, j j}^{xx xx} - - {g g}_{i i,, j j}^{yy yy}))}^{22} + + 44 {g g}_{i i,, j j}^{xy xy 22}}}{{g g}_{i i,, j j}^{xx xx} + + {g g}_{i i,, j j}^{yy yy}},, if if {m m}_{i i,, j j} &GreaterEqual; &Greater Equal; Threshold Threshold \\ 00,, otherwise otherwise \end{matrix}$

Threshold为一个设定的阀值，C_i，j＝0表示此处是指纹图像背景区域。Threshold is a set threshold value, and C _{i, j} =0 means that this is the background area of the fingerprint image.

由上面的块方向图得到的指纹的奇异点的位置是不精确的，可以使用现在取得的方向图，重新确定这些奇异点位置。从这些奇异点的原始位置出发，在其附近可以找到C_i，j最小值点，就是奇异点的精确位置了，在新的位置，计算出新的奇异点方向。The positions of the singular points of the fingerprint obtained from the above block orientation map are inaccurate, and the positions of these singular points can be re-determined using the obtained orientation map. Starting from the original positions of these singular points, you can find the point of minimum value of C _{i, j} in the vicinity, which is the exact position of the singular point, and calculate the new direction of the singular point at the new position.

2.5图像的滤波与增强2.5 Image filtering and enhancement

设计一个各向异性滤波器：Design an anisotropic filter:

$h h ((x x,, y the y,, θ θ)) = = ρ ρ ((x x,, y the y)) exp exp ((- - \frac{{((x x cos cos θ θ + + y the y sin sin θ θ))}^{22}}{{δ δ}_{11}^{22}} - - \frac{{((x x sin sin θ θ - - y the y cos cos θ θ))}^{22}}{{δ δ}_{22}^{22}}))$

$ρ ρ ((x x,, y the y)) = = \{\begin{matrix} a a,, if if {x x}^{22} + + {y the y}^{22} \leq \leq {r r}^{22} \\ 00,, otherwise otherwise \end{matrix}$

其中，r为有效半径，通常取6，a为幅值系数，通常取1024，δ₁ ²和δ₂ ²是滤波器的形状控制参数，通常取为8和1。θ是该滤波器的调制方向。方向为零的各向异性滤波器核请见附图5。从而，可以使用如下公式计算增强的指纹图像(卷积)：Among them, r is the effective radius, usually 6, a is the amplitude coefficient, usually 1024, δ ₁ ² and δ ₂ ² are the shape control parameters of the filter, usually 8 and 1. θ is the modulation direction of this filter. See Figure 5 for an anisotropic filter kernel whose direction is zero. Thus, the enhanced fingerprint image (convolution) can be calculated using the following formula:

${R R}_{i i,, j j} = = \frac{{Σ Σ}_{y the y = = i i - - r r}^{i i + + r r} {Σ Σ}_{x x = = j j - - r r}^{j j + + r r} h h ((x x - - i i,, y the y - - j j,, {O o}_{y the y,, x x})) {I I}_{y the y,, x x}}{{Σ Σ}_{y the y = = i i - - r r}^{i i + + r r} {Σ Σ}_{x x = = j j - - r r}^{j j + + r r} h h ((x x - - i i,, y the y - - j j,, {O o}_{y the y,, x x}))}$

为了快速地计算上式，预先计算并保存所有角度的滤波系数h，和上式中的分母项，具体计算时查表来与图像直接进行卷积。In order to quickly calculate the above formula, pre-calculate and save the filter coefficient h of all angles, and the denominator item in the above formula. When calculating, look up the table to directly convolve with the image.

2.6计算脊线密度图2.6 Calculate the ridge density map

如下式计算指纹脊线的密度图D：The density map D of the fingerprint ridge is calculated as follows:

${D D.}_{i i,, j j} = = \frac{{Σ Σ}_{y the y = = i i - - w w}^{i i + + w w} {Σ Σ}_{x x = = j j - - w w}^{j j + + w w} {P P}_{y the y,, x x}}{{Σ Σ}_{y the y = = i i - - w w}^{i i + + w w} {Σ Σ}_{x x = = j j - - w w}^{j j + + w w} {C C}_{y the y,, x x}} g g \frac{255255 Koef Koef (({O o}_{i i,, j j}))}{KoefP KoefP}$

${P P}_{i i,, j j} = = \{\begin{matrix} 11,, if if {Σ Σ}_{y the y = = i i - - w w}^{i i + + w w} {Σ Σ}_{x x = = j j - - w w}^{j j + + w w} {I I}_{y the y,, x x} &Element; &Element; [[{Threshold Threshold}_{bottom bottom},, {Threshold Threshold}_{top top}]] \\ and and [[i i,, j j]] is not in the bad area is not in the bad area \\ 00,, otherwise otherwise \end{matrix}$

${C C}_{i i,, j j} = = \{\begin{matrix} 11,, [[i i,, j j]] is not in the bad area is not in the bad area \\ 00,, otherwise otherwise \end{matrix}$

指纹的脊线密度是非常连续的，因此对脊线密度图D_i，j再进行33×33的均值滤波以消除噪声。The ridge line density of the fingerprint is very continuous, so 33×33 mean value filtering is performed on the ridge line density map D _{i, j} to eliminate the noise.

2.7二值化图像并细化2.7 Binarize the image and refine it

根据如下公式对增强后的图像进行二值化：Binarize the enhanced image according to the following formula:

${R R}_{i i,, j j} = = \{\begin{matrix} 00,, if if {I I}_{i i,, j j} < < {S S}_{i i,, j j} \\ 255255,, otherwise otherwise \end{matrix}$

其中，S_i，j是对增强后的指纹图像用一个33×33的均值滤波后的图像，用这个图像作为自适应的阀值来二值化指纹图像。Among them, S _{i, j} is an image filtered by a 33×33 mean value for the enhanced fingerprint image, and this image is used as an adaptive threshold to binarize the fingerprint image.

然后把二值化的图像细化成单点宽度的脊线图。算法是：考虑图像中的每一个黑色像素的8个相邻点，根据它们来判断当前点是否应该被改为白色。这样经过多次的重复扫描，直到没有一个黑色点被改成白色，就得到了细化的指纹脊线图。The binarized image is then thinned into a single point width ridge map. The algorithm is: consider the 8 adjacent points of each black pixel in the image, and judge whether the current point should be changed to white or not based on them. In this way, after repeated scanning many times, until none of the black dots are changed to white, a refined fingerprint ridge map is obtained.

二值化图像中，一个黑色像素的8个相邻点总共可以有256种情形，实际的计算中可以通过查表了快速判断。建立一个256个元素的表如下：In the binarized image, there can be a total of 256 situations for the 8 adjacent points of a black pixel, which can be quickly judged by looking up the table in actual calculation. Create a table with 256 elements as follows:

{0，0，0，0，0，0，0，1，0，0，0，0，0，0，1，1，0，0，0，0，0，0，0，0，0，0，0，0，1，0，1，1，0，0，0，0，0，0，0，0，0，0，0，0，{0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0 ,0,0,0,1,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,

0，0，0，0，0，0，0，0，0，0，0，0，1，0，0，0，1，0，1，1，0，0，0，1，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，1，0，0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,1,0,1,1,0,0,0,1,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,

0，0，0，0，0，0，0，1，0，1，0，0，0，0，0，0，0，0，0，0，0，0，1，0，0，0，0，0，0，0，1，0，0，0，1，0，1，0，0，0，0，1，0，0，0，1，0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0, 0,0,0,0,0,1,0,0,0,1,0,1,0,0,0,0,1,0,0,0,1,

0，0，0，0，0，0，0，1，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，1，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,

0，0，0，0，0，0，0，0，0，1，0，1，0，1，0，0，0，0，0，0，0，0，0，0，0，0，1，0，0，0，0，0，0，0，1，0，0，0，0，0，0，0，1，1，0，1，0,0,0,0,0,0,0,0,0,1,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0, 0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,1,0,1,

0，0，0，0，0，0，0，0，0，0，0，0，1，0，0，0，0，0，0，0，1，0，0，0，1，0，1，0}其值为1表示是否要把当前像素应该被改为白色，表的索引用如下方式构造：8个相邻点转换为表索引号22(二进制的00010110)，请见附图6。0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,1, 0, 1, 0} whose value is 1 indicates whether the current pixel should be changed to white, and the index of the table is constructed in the following way: 8 adjacent points are converted into table index number 22 (binary 00010110), please refer to the attached Figure 6.

2.8提取细节点2.8 Extract detail points

由于图像的噪声，细化后的指纹脊线图存在有毛刺现象和噪声，所以在提取细节点时，必须把它们先消除掉，否则就会提取出很多假细节点。三种主要的细化脊线噪声图请见附图7。Due to the noise of the image, there are burrs and noises in the thinned fingerprint ridge map, so when extracting minutiae, they must be eliminated first, otherwise many false minutiae will be extracted. See Figure 7 for the three main refinement ridge noise maps.

通过扫描细化的脊线图，跟踪脊线，如果从脊线起点到终点的像素距离小于一个设定的阀值，就可以把它从细化图上抹去。By scanning the thinned ridge map and tracking the ridge line, if the pixel distance from the start point to the end point of the ridge line is less than a set threshold, it can be erased from the thinning map.

然后，可以非常方便地提取出细节点：Then, minutiae points can be extracted very conveniently:

对图像上的任何一个黑色点，如果其相邻的8个点中，任选一个起始点，按顺时针方向扫描一周回到起始点，其颜色的变化如果是2次的话，说明该点是一个终结型细节点；如果是4次以上的话，该点是分叉型细节点，其他情况则可以忽略。终结型细节点的相邻8点的颜色变化是2次：6-＞7，7-＞0，请见附图8；分叉型细节点的相邻8点的颜色变化多于4次：1-＞2，2-＞3，3-＞4，4-＞5，6-＞7，7-＞0，请见附图9。For any black point on the image, if one of the 8 adjacent points is selected as a starting point, scan clockwise for a week and return to the starting point, if its color changes twice, it means that the point is A terminal detail point; if it is more than 4 times, the point is a fork-type detail point, and can be ignored in other cases. The color changes of the 8 adjacent points of the terminal minutiae are 2 times: 6->7, 7->0, please see attached picture 8; the color changes of the 8 adjacent points of the bifurcated minutiae are more than 4 times: 1->2, 2->3, 3->4, 4->5, 6->7, 7->0, please see Figure 9.

这样，通过扫描有效的指纹图像区域，得到了所有的细节点。在细节点处跟踪脊线，可以得到脊线的方向。In this way, by scanning the effective fingerprint image area, all minutiae points are obtained. Tracking the ridge line at the minutiae point can get the direction of the ridge line.

细节点的脊线曲率，可以用方向的变化来表示。在指纹图像的方向图上，用该点附近的方向与该点的方向差值来计算曲率：The curvature of the ridge line of the minutiae point can be represented by the change of direction. On the orientation map of the fingerprint image, the curvature is calculated by the difference between the orientation near the point and the orientation of the point:

$\underset{{x x}^{22} + + {y the y}^{22} &NotEqual; &NotEqual; 00}{\underset{{x x}^{22} + + {y the y}^{22} < < {r r}^{22}}{Σ Σ}} | | {O o}_{i i + + x x,, j j + + y the y} - - {O o}_{i i,, j j} | |$

其中，r是半径常数，通常取10.Among them, r is the radius constant, usually 10.

2.9细节点验证2.9 Verification of details

至此得到的细节点，由于图像噪声的缘故，还是有很多伪细节点在里面，需要进一步剔除。考虑如下情况：The details obtained so far, due to image noise, still have a lot of pseudo-details in it, which need to be further eliminated. Consider the following situation:

考虑任意一个细节点，若存在来一个细节点与之距离小于一个设定值D1，则删除该细节点；Consider any detail point, if there is a detail point whose distance is less than a set value D1, delete the detail point;

如一个端点型细节点与来一个端点型细节点距离小于一个设定值D2，且它们方向相反，则同时删除这两个细节点；If the distance between an end-type minutiae point and an end-type minutiae point is less than a set value D2, and their directions are opposite, delete these two minutiae points at the same time;

如果一个端点型细节点与一个分叉型细节点距离小于一个设定值D3，且它们方向相反，则同时删除这两个细节点；If the distance between an end-type minutiae point and a bifurcation-type minutiae point is less than a set value D3, and their directions are opposite, delete the two minutiae points at the same time;

如果一个细节点离指纹图像的无效区域小于一个设定值D4，且方向朝外，则删除该细节点。If a minutiae is less than a set value D4 from the invalid area of the fingerprint image, and the direction is outward, the minutiae is deleted.

这样得到最终的细节点。This gets the final detail point.

指纹细节点和其他全局特征最终被压缩成为指纹特征模板存储。Fingerprint minutiae and other global features are finally compressed into fingerprint feature template storage.

二、指纹匹配方法2. Fingerprint matching method

细节点匹配方法是基于细节点连线的。The minutiae matching method is based on minutiae connection.

考虑一个指纹图像上的两个细节点m_i，m_j的连线，定义：Consider the line connecting two minutiae points m _i and m _j on a fingerprint image, defined as:

d_ij为线段的长度，即两个细节点之间的距离；d _ij is the length of the line segment, that is, the distance between two detail points;

a_i和b_j分别为连线与细节点方向的夹角；a _i and b _j are the angles between the connection line and the direction of the detail points;

u_ij为连线的角度。u _ij is the angle of the connecting line.

细节点对之间的连线，如附图10所示。The connection lines between pairs of detail points are shown in Figure 10.

把这样的线段作为指纹细节点匹配的基本单位，来比较两个指纹图上的细节点对。对于一个细节点对，d_ij、a₁、a₂和两个细节点的类型t、曲率c、脊密度g都是平移不变的和旋转不变的。由此，可以比对这些量，来确定两个细节点对的相似性。Take such a line segment as the basic unit of fingerprint minutiae matching to compare minutiae pairs on two fingerprint maps. For a minutiae pair, d _ij , a ₁ , a ₂ and the type t, curvature c, and ridge density g of the two minutiae points are all translation-invariant and rotation-invariant. Therefore, these quantities can be compared to determine the similarity of two minutiae point pairs.

对于现场指纹模板上的细节点对(m_i1，m_j1)和数据库中指纹模板上的细节点对(m_i2，m_j2)，定义细节点对的“相似度”如下：For the minutiae point pair (m _i1 , m _j1 ) on the on-site fingerprint template and the minutiae point pair (m _i2 , m _j2 ) on the fingerprint template in the database, the “similarity” of the minutiae point pair is defined as follows:

$D D. = = {cof cof}_{11} | | {d d}_{{i i}_{11} {j j}_{11}} - - {d d}_{{i i}_{22} {j j}_{22}} | | + + {cof cof}_{22} ((| | {a a}_{{i i}_{11}} - - {a a}_{{i i}_{22}} | | + + | | {b b}_{{j j}_{11}} - - {b b}_{{j j}_{22}} | |))$

$+ + {cof cof}_{33} ((| | {c c}_{{i i}_{11}} - - {c c}_{{i i}_{22}} | | + + | | {c c}_{{j j}_{11}} - - {c c}_{{j j}_{22}} | |)) + + {cof cof}_{44} ((| | {g g}_{{i i}_{11}} - - {g g}_{{i i}_{22}} | | + + | | {g g}_{{j j}_{11}} - - {g g}_{{j j}_{22}} | |))$

$+ + {cof cof}_{55} ((| | {t t}_{{i i}_{11}} - - {t t}_{{i i}_{22}} | | + + | | {t t}_{{j j}_{11}} - - {t t}_{{j j}_{22}} | |))$

其中，cof₁，cof₂，cof₃，cof₄，cof₅为正的常系数。d，a，b分别如前面定义，c，g，t分别是每个细节点的曲率、脊密度和类型代码(分叉型细节点为1，终端型细节点为0)。当D小于一个给定的值ThresholdD时，便认为这两个细节点对相匹配。Among them, cof ₁ , cof ₂ , cof ₃ , cof ₄ and cof ₅ are positive constant coefficients. d, a, b are defined as before, and c, g, t are the curvature, ridge density and type code of each minutiae (1 for bifurcated minutiae and 0 for terminal minutiae). When D is less than a given value ThresholdD, the two minutiae pairs are considered to match.

如果一个指纹图像有N个细节点，则可以产生C(N，2)个细节点对，要把他们同另一个指纹图的M个细节点产生的C(M，2)个细节点对逐一比对，就需要进行C(M，2)×C(N，2)次比对，若M＝N＝80，则要比对的次数是39942400，这会非常慢，所以，有必要在比对前做一下限制。规定两个值ThresholdD1，ThresholdD2，只考虑连线长度介于这两个值之间的细节点对。这可以大大降低比对所花的时间。If a fingerprint image has N minutiae points, then C(N, 2) minutiae point pairs can be generated, and they must be compared with C(M, 2) minutiae point pairs generated by M minutiae points of another fingerprint image one by one For comparison, it is necessary to perform C(M, 2)×C(N, 2) times of comparison. If M=N=80, the number of times of comparison is 39942400, which will be very slow. Therefore, it is necessary to compare Do some restrictions on the front. Specify two values ThresholdD1, ThresholdD2, only consider the minutiae point pairs whose connection length is between these two values. This can greatly reduce the time it takes to compare.

从D的计算公式中，很容易看出：如果第一项的计算结果大于ThresholdD，不用计算后面的项就知道两个细节点对不相匹配，因此可以先把两个指纹中的细节点对按照其连线长度d进行排序，就可以在一个连线长度d的小邻域内进行比对。这大大加快了计算速度。From the calculation formula of D, it is easy to see that if the calculation result of the first item is greater than ThresholdD, it is known that the two minutiae pairs do not match without calculating the following items, so the minutiae points in the two fingerprints can be paired first. Sorting according to the length d of the connection can be compared in a small neighborhood of the length d of the connection. This greatly speeds up calculations.

忽略掉不相匹配的细节点对，会得到了一个相匹配的细节点对列表：Ignoring unmatched minutiae pairs, a list of matching minutiae pairs is obtained:

$U u = = {{{μ μ}_{{i i}_{11} {j j}_{11},, {i i}_{22} {j j}_{22}} = = (({l l}_{{i i}_{11} {j j}_{11}},, {l l}_{{i i}_{22} {j j}_{22}},, {S S}_{{i i}_{11} {j j}_{11},, {i i}_{22} {j j}_{22}})) | | {D D.}_{{i i}_{11} {j j}_{11},, {i i}_{22} {j j}_{22}} < < ThresholdD ThresholdD}}$

${S S}_{{i i}_{11} {j j}_{11} {i i}_{22} {j j}_{22}} = = 11 - - \frac{{D D.}_{{i i}_{11} {j j}_{11},, {i i}_{22} {j j}_{22}}}{ThresholdD ThresholdD}$

其中l_i1j1是个来自现场指纹模板的细节点对(m_i1，m_j1)及其连线，l_i12j2是个来自数据库的指纹模板的细节点对(m_i2，m_j2)及其连线，D是这两对细节点对间的“距离”，S为两对细节点对间的相似度。Among them, l _i1j1 is a minutiae point pair (m _i1 , m _j1 ) and its connection line from the on-site fingerprint template, l _i12j2 is a minutiae point pair (m _i2 , m _j2 ) and its connection line from the fingerprint template in the database, and D is The "distance" between the two pairs of minutiae points, S is the similarity between the two pairs of minutiae points.

采用如下方法，从这个列表来计算两个指纹模板的相似度：Use the following method to calculate the similarity of two fingerprint templates from this list:

1、采用直方图法计算旋转角度1. Use the histogram method to calculate the rotation angle

设定一个一维数组{H_d|0≤d＜360}，其下标表示从0～359的角度，每个元素如下式计算：Set a one-dimensional array {H _d |0≤d<360}, its subscript indicates the angle from 0 to 359, and each element is calculated as follows:

${H h}_{d d} = = \underset{{μ μ}_{{i i}_{11} {j j}_{11} {i i}_{22} {j j}_{22}} &Element; &Element; U u}{Σ Σ} {S S}_{{i i}_{11} {j j}_{11} {i i}_{22} {j j}_{22}} g g (({σ σ}_{d d} (({d d}_{{i i}_{11}} - - {d d}_{{i i}_{22}})) + + {σ σ}_{d d} (({d d}_{{j j}_{11}} - - {d d}_{{j j}_{22}}))$

其中，σ_d是在d取值为1，其他都取值为0的单位冲击函数。可见，{H_d}实际上是所有匹配细节点对的对应细节点的角度差的统计直方图。找出这个数组中的最大值点，就是需要的两个指纹模板的旋转角度θ。Among them, σ _d is a unit impact function that takes the value of d to be 1 and the other values to be 0. It can be seen that {H _d } is actually a statistical histogram of the angle difference of the corresponding minutiae points of all matching minutiae point pairs. Find the maximum point in this array, which is the rotation angle θ of the two fingerprint templates required.

2、把来自数据库的指纹模板的各个角度参数，包括细节点角度、奇异点角度、分块方向图和匹配细节点对U中的连线方向等，按照上一步计算的角度进行旋转，使得它同现场采集的指纹模板具有一致方向：2. Rotate the various angle parameters of the fingerprint template from the database, including minutiae angles, singular point angles, block orientation diagrams, and matching minutiae point pair U directions, etc., according to the angle calculated in the previous step, so that it The same direction as the fingerprint template collected on-site:

(d_i+θ)mod360→d_i (d _i +θ)mod360→d _i

3、从U中删除掉对应细节点角度差大于一个指定值的匹配点对，这样，U中的匹配细节点对就只包含了最可靠的匹配细节点对。3. Delete the matching point pairs whose corresponding minutiae point angle difference is greater than a specified value from U, so that the matching minutiae point pairs in U only contain the most reliable matching minutiae point pairs.

4、同样的方法，计算行列方向的直方图4. In the same way, calculate the histogram in the row and column direction

设定两个一维数组{HX_dx}和{HY_dy}：Set two one-dimensional arrays {HX _dx } and {HY _dy }:

{HX_dx|-MaxDim≤dx≤MaxDim}{HX _dx |-MaxDim≤dx≤MaxDim}

${HX HX}_{dx dx} = = \underset{{μ μ}_{{i i}_{11} {j j}_{11} {i i}_{22} {j j}_{22}} &Element; &Element; U u}{Σ Σ} {S S}_{{i i}_{11} {j j}_{11} {i i}_{22} {j j}_{22}} g g \frac{{σ σ}_{dx dx} (({x x}_{{i i}_{11}} - - {x x}_{{i i}_{22}})) + + {σ σ}_{dx dx} (({x x}_{{j j}_{11}} - - {x x}_{{j j}_{22}}))}{22}$

{HY_dy|-MaxDim≤dy≤MaxDim}{HY _dy |-MaxDim≤dy≤MaxDim}

${HY HY}_{dy dy} = = \underset{{μ μ}_{{i i}_{11} {j j}_{11} {i i}_{22} {j j}_{22}} &Element; &Element; U u}{Σ Σ} {S S}_{{i i}_{11} {j j}_{11} {i i}_{22} {j j}_{22}} g g \frac{{σ σ}_{dy dy} (({y the y}_{{i i}_{11}} - - {y the y}_{{i i}_{22}})) + + {σ σ}_{dy dy} (({y the y}_{{j j}_{11}} - - {y the y}_{{j j}_{22}}))}{22}$

可见，{HY_dy}、{HX_dx}实际上是所有匹配细节点对的对应细节点的行列座标差的统计直方图。找出这两个数组中的最大值点，就是需要的两个指纹模板的在进行旋转角度对齐后的平移量(x₀，y₀)。It can be seen that {HY _dy } and {HX _dx } are actually statistical histograms of the row and column coordinate differences of the corresponding minutiae points of all matching minutiae point pairs. Finding the maximum value point in these two arrays is the required translation amount (x ₀ , y ₀ ) of the two fingerprint templates after alignment of the rotation angles.

5、把来自数据库的指纹模板的各个位置参数，包括细节点坐标、奇异点座标、块方向位置等，进行平移5. Translate each position parameter of the fingerprint template from the database, including minutiae point coordinates, singular point coordinates, block direction position, etc.

$(\begin{matrix} {x x}_{i i} \\ {y the y}_{i i} \end{matrix}) + + (\begin{matrix} {x x}_{00} \\ {y the y}_{00} \end{matrix}) &RightArrow; &Right Arrow; (\begin{matrix} {x x}_{i i} \\ {y the y}_{i i} \end{matrix})$

现在，两个指纹模板就完全对齐了。Now the two fingerprint templates are perfectly aligned.

6、从U中删除掉包含行列座标差大于一个指定值的细节点对的匹配对，这样，U中的细节点对的匹配对是完全匹配的。把从这些匹配对的相似度累加起来就是两个指纹模板细节点集的最终相似度S_m。6. Delete the matching pairs containing the minutiae point pairs whose row-column coordinate difference is greater than a specified value from U, so that the matching pairs of the minutiae point pairs in U are completely matched. The sum of the similarities from these matching pairs is the final similarity S _m of the minutiae point sets of the two fingerprint templates.

7、上面的计算中，也已经通过平移和旋转，把全局特征对齐。此时，可以很简单地计算出全局特征的相似度。7. In the above calculation, the global features have also been aligned through translation and rotation. At this point, the similarity of global features can be calculated very simply.

奇异点相似度S_s：两两比对奇异点的位置、方向和类型，得到的相似度相加；Singular point similarity S _s : Comparing the position, direction and type of the singular point two by two, the obtained similarity is added;

平均脊密度相似度S_g：两个指纹模板脊密度的差并取倒数；Average ridge density similarity S _g : the difference between the ridge densities of two fingerprint templates and take the reciprocal;

块方向图的相似度S_d：在两个指纹模板有效区域的公共部分，计算方向的差值，累加后平均并取倒数。The similarity S _d of the block orientation graph: in the common part of the effective area of the two fingerprint templates, calculate the difference of the orientation, accumulate and average and take the reciprocal.

8、最后的两个指纹模板的相似度由上面的局部和全局特征相似度融合而成：8. The similarity of the last two fingerprint templates is formed by the fusion of the above local and global feature similarities:

S＝k_mS_m+k_sS_s+k_gS_g+k_dS_d S＝k _m S _m +k _s S _s +k _g S _g +k _d S _d

其中，k_m，k_s，k_g，k_d是各种特征匹配相似度的权重系数。Among them, k _m , k _s , k _g , and k _d are weight coefficients of matching similarities of various features.

注意，平均脊密度相似度S_g的计算就是两个平均脊密度的差，因此，如果是进行一对多的识别，则可以把数据库中的指纹模板先根据平均脊密度G来排序，对现场指纹进行识别的时候，就可以优先与数据库中的平均脊密度最接进的指纹模板进行匹配，这样，由于数据库中的指纹模板是根据G索引的，因此可以大大加快识别过程。Note that the calculation of the average ridge density similarity S _g is the difference between two average ridge densities. Therefore, if one-to-many identification is performed, the fingerprint templates in the database can be sorted according to the average ridge density G, and the on-site When the fingerprint is identified, it can be preferentially matched with the fingerprint template with the closest average ridge density in the database. In this way, since the fingerprint template in the database is indexed according to G, the identification process can be greatly accelerated.

处理过程中的指纹图像请见附图：Please see the attached image for the fingerprint image during processing:

其中：附图11是原指纹图像，附图12是正规化后的图像，附图13是方向图，附图14是增强图像，附图15是二值化图像，附图16是细化脊线图。Among them: accompanying drawing 11 is the original fingerprint image, accompanying drawing 12 is the normalized image, accompanying drawing 13 is the orientation map, accompanying drawing 14 is the enhanced image, accompanying drawing 15 is the binarized image, accompanying drawing 16 is the thinning ridge line graph.

用于实施本发明指纹识别方法的指纹识别系统包括指纹采集器、指纹识别系统、识别或和控制信号输出机构；其中包括指纹图像存储器、指纹图像处理器和指纹特征数据存储器；指纹图像处理器是利用要求1-9之一所述方法对指纹图像进行处理和识别。The fingerprint identification system for implementing the fingerprint identification method of the present invention includes a fingerprint collector, a fingerprint identification system, identification or and a control signal output mechanism; wherein it includes a fingerprint image memory, a fingerprint image processor and a fingerprint feature data memory; the fingerprint image processor is The fingerprint image is processed and identified by using the method described in one of claims 1-9.

Claims

1, a kind of fingerprint recognition method is characterized in that being made up of two steps of fingerprint feature extraction and feature matching:

The feature extraction steps are: collect the fingerprint image, preprocess and normalize the fingerprint image; calculate the block direction map to extract singular points, calculate the direction map, segment the background area and refine the singular points; filter and enhance the image; calculate the ridge line Density; binarize the image and refine it, extract minutiae points, verify minutiae points, and delete false minutiae points; fingerprint minutiae points, singular points, average ridge density and block orientation map features are finally compressed into fingerprint feature template storage;

The feature matching step is: collect the on-site fingerprint image, and extract the fingerprint minutiae point, singular point, average ridge density and block direction map features of the on-site fingerprint image according to the above steps; compare the fingerprint feature template and the fingerprint minutiae point, singular point, The average ridge density and block pattern features are used to judge whether they are the same finger or not by the similarity of the two features.

2. The fingerprint identification method according to claim 1, wherein the feature matching step is:

Calculate the minutiae point-to-line distance, the angle between the minutiae point-to-line and the minutiae direction, and the angle of the minutiae-to-line in the database template and the on-site fingerprint template; specify the upper limit and lower limit of the minutiae point-to-line distance value, delete the minutiae point pair data whose distance between the minutiae point pair is greater than this upper limit and less than this lower limit value, and obtain a smaller range of minutiae point pair data U;

Use the histogram to calculate the rotation angle;

Rotate the angle parameters of the fingerprint template from the database, including minutiae point angle, singularity point angle, block orientation diagram, and the connection direction in the matching minutiae point pair U, etc., according to the angle calculated in the previous step, so that it is the same as the on-site The collected fingerprint templates have a consistent direction:

Delete the matching point pairs whose corresponding minutiae point angle difference is greater than a specified value from U, so that the matching minutiae point pairs in U only contain the most reliable matching minutiae point pairs;

In the same way, calculate the histogram in the row and column direction, calculate the statistical histogram of the row and column coordinate difference of the corresponding minutiae points of all matching minutiae point pairs, and find the maximum point in the two arrays, that is, the two fingerprint templates are in progress. The amount of translation after the rotation angle is aligned;

Translate each position parameter of the fingerprint template from the database, including minutiae point coordinates, singular point coordinates, block direction position, etc., and the two fingerprint templates are completely aligned;

Delete the matching pairs containing the minutiae point pairs whose row and column coordinate difference is greater than a specified value from U, and the similarity of these matching pairs is added up to obtain the final similarity of the minutiae point sets of the two fingerprint templates;

Calculate the similarity of global features:

The similarity of singular points is the sum of the similarities obtained by comparing the position, direction and type of singular points in pairs;

The average ridge density similarity is the difference between the ridge densities of the two fingerprint templates and the reciprocal;

The similarity of the block direction graph is the common part of the effective area of the two fingerprint templates, calculate the difference of the direction, accumulate and average and take the reciprocal;

The similarity of the last two fingerprint templates is fused by the above local and global feature similarities;

When performing one-to-many identification, first sort the average ridge density of the fingerprint templates in the database, and when identifying on-site fingerprints, first match the fingerprint template with the closest average ridge density in the database to speed up the identification; The ridge density is the average ridge density of the entire fingerprint image.

3. The fingerprint identification method according to claim 2, wherein when the fingerprint feature is extracted: the fingerprint image is represented as a two-dimensional matrix, each pixel is an element of the matrix, and the value is 0 to 255, and the dimension of the matrix is the image width and height;

The minutiae point of the fingerprint refers to the endpoint or bifurcation point on the fingerprint ridge line, and the fingerprint minutiae point includes the following features: coordinate xy-represents the position in the fingerprint image; type t-represents whether it is the endpoint of the ridge line or the bifurcation point; Direction d-indicates the direction of the minutiae. If it is an endpoint-type minutiae, then the direction points from the minutiae position to the ridge line. If it is a bifurcated minutiae, then the direction points from the minutiae position to the two ridges after the bifurcation The middle of the line; ridge density g-indicates the average density of ridge lines near the detail point; ridge curvature c-indicates the degree of change of ridge line direction here;

Block direction map: divide the fingerprint image into small disjoint blocks of BLOCK_SIZE×BLOCK_SIZE size, and calculate the average direction of the ridge line for each small image, so that the size is

(HEIGHT/BLOCK_SIZE) × (WIDTH/BLOCK_SIZE) block orientation diagram; the block orientation diagram depicts the global ridge direction of the fingerprint image; in addition, an illegal direction value is used on the block orientation diagram to indicate that the fingerprint image is segmented the background area of

Singular point: There are some places on the fingerprint image where the direction of the ridge line is discontinuous. These places are called singular points of the fingerprint. Its characteristics are: coordinate x y, indicating the position in the fingerprint image; type t, the singular point is divided into core There are three kinds of points, double-core points and triangular points; the direction d indicates that when the direction is far away from the singular point, the direction of the fingerprint ridge changes the least. The ridge density, c, represents the average distance between the ridges around the singular point.

4, according to the described fingerprint identification method of claim 3, it is characterized in that image preprocessing and normalization are to carry out average value filter to image at first, make image smoother, then, image is formatted; The point is on the block direction graph, first calculate the Poincare Index of each point:

{pindex pindex}^{n no} = = \frac{11}{π π} {Σ Σ}_{i i = = 00}^{n no} τ τ (({O o}_{((i i + + 11)) mod mod n no} - - {O o}_{i i}))

τ τ ((k k)) = = \{\begin{matrix} k k,, if if | | k k | | < < \frac{π π}{22},, \\ π π + + k k,, if if | | k k | | < < \frac{π π}{22} \\ π π - - k k,, otherwise otherwise \end{matrix},,

Among them, n is the number of surrounding pixel points, and O _i represents the direction of the i-th point; first take the radius as 1, that is, calculate the Poincare Index from the surrounding 8 points, get p1, if its Poincare Index is non-zero, then use the radius 2. Calculate the Poincare Index on the outer layer of the periphery, and get p2: p1 is the same as p2, indicating that the point is a singular point. If p1 is 1, it is a core point singular point, and if p1 is -1, it is a triangular point , if p1 is 2, it is a dual-nucleate singularity; if p2 is different from p1, but p2>0, p1>0, it is a dual-nuclei singularity; otherwise, it is not a singularity.

5. The fingerprint identification method according to claim 1, 2, 3 or 4, characterized in that calculating the direction map, segmenting the background area and refining the singular points is: calculating the ridge direction of the first point on the normalized image, At the same time, the consistency of the ridge direction is calculated, the direction map is obtained, and the position of the singular point is re-determined. Starting from the original position of these singular points, the precise position of the singular point is found, and the new singular point direction is calculated at the new position.

6. The fingerprint identification method according to claim 1, 2, 3 or 4, characterized in that the filtering and enhancement of the image is: after being processed by an anisotropic filter, the enhanced fingerprint image is obtained; the calculation of the ridge line density is: first Calculate the fingerprint ridge density map, and then perform 33×33 mean filtering on the ridge density map.

7. The fingerprint identification method according to claim 1, 2, 3 or 4, characterized in that the binarization and refinement of the image is: using the 33×33 average filtered image as an adaptive threshold to binarize and enhance The final image; then refine the binarized image into a ridge map with a single point width; image refinement is that each black pixel in the image has 8 adjacent points, and according to them, it is judged whether the current point should be changed to White. In this way, after repeated scanning many times, until none of the black dots are changed to white, a refined fingerprint ridge map is obtained.

8. The fingerprint identification method according to claim 1, 2, 3 or 4, characterized in that the extraction of minutiae points is: first eliminate burrs and noises, that is, trace the ridges by scanning the thinned ridge map, if from the ridges If the pixel distance from the start point to the end point is less than a set threshold, it will be erased from the thinning map; then, the detail points are extracted: that is, for any black point on the image, if its adjacent 8 points , choose a starting point, and scan clockwise for a week to return to the starting point. If the color change is 2 times, it means that the point is a terminal detail point; if it is more than 4 times, the point is a point. The fork-shaped minutiae can be ignored in other cases, and all the minutiae are obtained by scanning the effective fingerprint image area;

Track the ridge line at the minutiae point to get the direction of the ridge line; the curvature of the ridge line at the minutiae point is expressed by the change of direction, and on the direction map of the fingerprint image, the difference between the direction near the point and the direction of the point is used to calculate Calculate the curvature.

9. The fingerprint identification method according to claim 1, 2, 3 or 4, characterized in that the minutiae verification and deletion of false minutiae is: any minutiae, if there is a minutiae whose distance is less than a set value D1, then delete the minutiae point; if the distance between an end-type minutiae point and an end-type minutiae point is less than a set value D2, and their directions are opposite, then delete the two minutiae points at the same time; if an end-type minutiae point is connected to If the distance of a bifurcated minutiae point is less than a set value D3, and their directions are opposite, delete the two minutiae points at the same time; if a minutiae point is less than a set value D4 from the invalid area of the fingerprint image, and its direction is outward, Then delete the minutiae; the final minutiae is obtained through the above deletion.

10. A fingerprint identification system, characterized in that it includes a fingerprint collector, a fingerprint identification system, an identification or control signal output mechanism; it includes a fingerprint image memory, a fingerprint image processor and a fingerprint feature data memory; the fingerprint image processor uses The method described in one of requirements 1-9 processes and recognizes fingerprint images.