JP4304722B2 - Deformation estimation method, deformation estimation apparatus, and deformation estimation program - Google Patents

Description

  The present invention relates to collation of image data, and more particularly to a deformation estimation method, a deformation estimation apparatus, and a deformation estimation program for identifying line figures such as fingerprints and characters.

  As a conventional device for recognizing line image patterns such as fingerprints and characters, a conventional technique that uses feature points such as end points and branch points of lines to obtain corresponding feature points and superimposes them for comparison. It has been proposed in Kaihei 10-240932 (Patent Document 1) and JP-A-10-105703 (Patent Document 2).

Further, conventional techniques for correcting graphics deformation and comparing images are disclosed in Japanese Patent Laid-Open Nos. 02-187895 (Patent Document 3), Japanese Patent Laid-Open No. 05-081412 (Patent Document 4), and Japanese Patent Laid-Open No. 06-004671. (Patent Document 5), Japanese Patent Application Laid-Open No. 08-030783 (Patent Document 6) and Japanese Patent Application Laid-Open No. 08-147411 (Patent Document 7).
JP-A-10-240932 Japanese Patent Laid-Open No. 10-105703 Japanese Patent Application Laid-Open No. 02-188785 JP 05-081412 A Japanese Patent Laid-Open No. 06-004671 Japanese Patent Application Laid-Open No. 08-030783 Japanese Patent Laid-Open No. 08-147411

  However, the conventional techniques have the following problems.

  In the conventional techniques described in Japanese Patent Application Laid-Open No. 10-240932 (Patent Document 1) and Japanese Patent Application Laid-Open No. 10-105703 (Patent Document 2), since the whole figure is overlaid and compared, the characters are deformed. If the fingerprint is deformed at the time of imprinting, it cannot be correctly identified.

  Also, Japanese Patent Application Laid-Open No. 02-187885 (Patent Document 3), Japanese Patent Application Laid-Open No. 05-081412 (Patent Document 4), Japanese Patent Application Laid-Open No. 06-004671 (Patent Document 5), Japanese Patent Application Laid-Open No. 08-030783 (Patent Document 5). In the conventional technique described in Document 6) and Japanese Patent Application Laid-Open No. 08-147411 (Patent Document 7), the entire figure is the same even when the figure is deformed by correcting and comparing the deformation as the whole figure. This can be dealt with in the case of the deformation. However, when the method of deformation differs from part to part, it is necessary to increase an allowable error, and there is a problem that identification becomes inaccurate.

  An object of the present invention is to provide a deformation estimation method, a deformation estimation apparatus, and a deformation estimation program that can solve the above-described problems of the prior art and can accurately identify an input figure even if there is a deformation.

In order to achieve the above object, the deformation estimation method of the present invention relates feature points between two fingerprints, estimates a parameter representing deformation so that the associated feature points overlap, and determines the parameter representing the deformation. , Rotation, parallel movement, contraction expansion, and shear strain parameters, and by substituting the parameters indicating the contraction expansion into a predetermined expression with a predetermined peripheral compression ratio as a coefficient, the energy of the contraction expansion is obtained. And determining a shear strain energy by substituting a parameter representing the shear into a predetermined formula having a constant indicating a predetermined shear rate as a coefficient, and summing the energy of the contraction and expansion and the energy of the shear strain. The size of the deformation is defined as follows, and the validity of the deformation is verified by whether or not the size of the deformation is larger than a predetermined value.

In the present invention of claim 2, when the magnitude of the deformation is larger than a predetermined value, the feature points are associated again until the magnitude of the deformation becomes smaller than the predetermined value. The method is characterized by estimating an appropriate deformation as a finger .

で表し、ここで、ｂは平行移動を表し、行列Ａが収縮膨張、回転、煎断を表す、
前記収縮膨張のパラメータを、

前記剪断歪のパラメータを

で表し、
周辺圧縮率Ｋと剪断率μを用いて、前記変形の大きさを

と表すことを特徴とする。 In the third aspect of the present invention, when the feature points of the two fingerprints are (x, y) and (X, Y), the parameter representing the deformation is:

Where b represents translation and matrix A represents contraction, expansion, rotation, and breakage,
The contraction and expansion parameters are

The shear strain parameters

Represented by
Using the peripheral compression rate K and shear rate μ, the size of the deformation is

It is characterized by expressing .

The deformation estimation apparatus of the present invention according to claim 4 associates feature points between two fingerprints, estimates a parameter representing deformation so that the associated feature points overlap, and rotates the parameter representing the deformation The energy of contraction and expansion is determined by substituting the parameter indicating the contraction and expansion into a predetermined expression using a predetermined peripheral compression ratio as a coefficient, and decomposing the parameter into parallel movement, contraction and expansion, and shear strain . The shear strain energy is determined by substituting the parameter representing the shear into a predetermined formula having a constant indicating a predetermined shear rate as a coefficient, and deformed as the sum of the contraction expansion energy and the shear strain energy. And the validity of the deformation is verified based on whether or not the deformation is larger than a predetermined value.

In the fifth aspect of the present invention , when the magnitude of the deformation is larger than a predetermined value, the feature points are associated again until the magnitude of the deformation becomes smaller than the predetermined value. The method is characterized by estimating an appropriate deformation as a finger .

で表し、ここで、ｂは平行移動を表し、行列Ａが収縮膨張、回転、煎断を表す、
前記収縮膨張のパラメータを、

前記剪断歪のパラメータを

で表し、
周辺圧縮率Ｋと剪断率μを用いて、前記変形の大きさを

と表すことを特徴とする。
In the present invention of claim 6, when the feature points of the two fingerprints are (x, y) and (X, Y), the parameter representing the deformation is:

Where b represents translation and matrix A represents contraction, expansion, rotation, and breakage,
The contraction and expansion parameters are

The shear strain parameters

Represented by
Using the peripheral compression rate K and shear rate μ, the size of the deformation is

It is characterized by expressing .

The deformation estimation program of the present invention according to claim 7 associates feature points between two fingerprints, estimates a parameter representing deformation such that the associated feature points overlap, and rotates the parameter representing the deformation The energy of contraction and expansion is determined by substituting the parameter indicating the contraction and expansion into a predetermined expression using a predetermined peripheral compression ratio as a coefficient, and decomposing the parameter into parallel movement, contraction and expansion, and shear strain . The shear strain energy is determined by substituting the parameter representing the shear into a predetermined formula having a constant indicating a predetermined shear rate as a coefficient, and deformed as the sum of the contraction expansion energy and the shear strain energy. And a computer can execute a deformation estimation process for verifying the validity of the deformation based on whether the deformation is larger than a predetermined value. The features.

In the present invention of claim 8, when the size of the deformation is larger than a predetermined value, the feature points are associated again until the size of the deformation becomes smaller than the predetermined value. The method is characterized by estimating an appropriate deformation as a finger .

で表し、ここで、ｂは平行移動を表し、行列Ａが収縮膨張、回転、煎断を表す、
前記収縮膨張のパラメータを、

前記剪断歪のパラメータを

で表し、
周辺圧縮率Ｋと剪断率μを用いて、前記変形の大きさを

と表すことを特徴とする。 In the present invention of claim 9, when the feature points of the two fingerprints are (x, y) and (X, Y), the parameter representing the deformation is:

Where b represents translation and matrix A represents contraction, expansion, rotation, and breakage,
The contraction and expansion parameters are

The shear strain parameters

Represented by
Using the peripheral compression rate K and shear rate μ, the size of the deformation is

It is characterized by expressing.

  In the present invention, the feature point information of the inspection graphic that is the graphic to be inspected and the feature point information of the model graphic that is the comparison source graphic are received, and the deformation occurring in the inspection graphic is estimated and estimated. By correcting the deformation and comparing the inspection figure with the corrected deformation and the model figure and calculating the similarity, the inspection figure and the model figure can be accurately identified even if the inspection figure is deformed. it can.

  Hereinafter, embodiments of the present invention will be described in detail with reference to the drawings.

  FIG. 1 is a block diagram showing the configuration of the pattern matching apparatus according to the first embodiment of the present invention.

  Referring to FIG. 1, the pattern matching apparatus according to the present embodiment includes an inspection graphic input unit 20 that inputs data of an inspection graphic that is a graphic to be inspected, and a model that inputs data of a model graphic that is a comparison source graphic. A graphic input unit 30, a data processing unit 10 that executes pattern matching processing, and an output unit 40 that outputs processing results are provided.

  The data processing unit 10 includes a deformation estimation unit 11, a deformation correction unit 12, and a similarity determination unit 13. Each of these units generally operates as follows.

  The deformation estimation unit 11 compares the feature point of the inspection graphic input from the inspection graphic input unit 20 with the feature point of the model graphic input from the model graphic input unit 30, and the overall generated in the inspection graphic. Estimate the content of the deformation.

  The deformation correction unit 12 creates an inspection graphic in which the deformation is corrected by applying correction for eliminating the deformation to the inspection graphic based on the data of the deformation content estimated by the deformation estimation unit 11.

  The similarity determination unit 13 compares the inspection graphic with the deformation corrected by the deformation correction unit 12 and the model graphic, calculates the similarity of both graphics, and outputs the calculated similarity to the output unit 40.

  Next, the operation of the present embodiment will be described in detail with reference to the drawings.

  FIG. 2 is a flowchart for explaining pattern matching processing according to the present embodiment. FIG. 3 is a flowchart for explaining the processing of the deformation estimation unit 11 of the present embodiment.

  Referring to FIG. 2, in the pattern matching process of the present embodiment, first, an inspection graphic that is a graphic to be inspected and a model graphic that is a comparison source graphic are converted into an inspection graphic input unit 20 and a model graphic input unit. 30 is input (step 201).

  In the input of each figure, for example, a method of inputting feature point information indicating the characteristics of each figure extracted in advance, image data of each figure is inputted, and the inspection figure input unit 20 and the model figure input unit On the 30th side, a method of extracting information on the feature point and sending it to the data processing unit 10 can be used.

  For example, when applied to character recognition, the character image data to be examined is input to the inspection graphic input unit 20 and the character data registered in the dictionary is input to the model graphic input unit 30. Can be adopted.

  Also, for example, when applied to fingerprint recognition, input fingerprint image data to be examined who is the fingerprint to the inspection graphic input unit 20 and input the fingerprint data registered in the fingerprint database to the model graphic input unit 30. That's fine.

  In this way, the inspection graphic input unit 20 may input the feature point information of the inspection graphic extracted in advance, or the inspection graphic itself may be input and the feature point information extracted by the inspection graphic input unit 20 You may decide to do it. Similarly, the model graphic input unit 30 may input feature point information of the model graphic extracted in advance, or may input the model graphic itself and extract feature point information by the model graphic input unit 30. It may be.

  Here, as characteristic points of the inspection graphic and the model graphic, a point where the line is interrupted (end point), a branching point (branching point), a crossing point (intersection), and the like can be used as the characteristic points. Further, data such as the position of the feature point and the direction of the line in contact with it can be used as the feature quantity that is data indicating the degree of the feature at each feature point. In addition, information such as the value of the curvature of a tangent line and the curvature of an adjacent line, the arrangement of neighboring feature points, and the number of lines intersecting with neighboring feature points may be added to the feature quantity.

  Next, each graphic data input to the inspection graphic input unit 20 and the model graphic input unit 30 is transferred to the deformation estimation unit 11 of the data processing unit 10. The deformation estimation unit 11 compares the feature point information of the inspection graphic input from the inspection graphic input unit 20 with the feature point information of the model graphic input from the model graphic input unit 30, and the deformation occurring in the inspection graphic. Is estimated (step 202).

  The deformation estimation unit 11 selects a pair of feature points that are considered to be the same feature points in both figures, and estimates the deformation that has occurred in the inspection figure based on the displacement of their arrangement in both figures.

  Here, the deformation occurring in the figure is, for example, when the character registered in the dictionary is compared with the character input by the camera or the like in character recognition, and is photographed by the camera or the like input to the inspection graphic input unit 20 The image of the character that has been subjected to the optical distortion at the time of input. Also, in fingerprint recognition, when fingerprint data to be examined as to who the fingerprint is is input to the inspection graphic input unit 20 and fingerprint data registered in the fingerprint database is input to the model graphic input unit 30, the inspection graphic is also a model graphic. Has also undergone deformation during stamping.

  Here, it is not possible to obtain the deformation received by the inspection graphic and the deformation received by the model graphic only by the inspection graphic and the model graphic, but the difference in the positional relationship between the individual feature points in both of them is detected. As a result, a combination of the reverse deformation of the deformation received by the model figure and the deformation received by the inspection figure is detected, and this deformation is applied in the opposite direction to deform the inspection figure to match the model figure. Can be estimated.

  Next, the deformation correction unit 12 corrects the deformation of the inspection graphic by applying to the inspection graphic a deformation having a reverse relationship to the deformation estimated by the deformation estimation unit 11 (step 203).

  Next, the similarity determination unit 13 compares the inspection graphic obtained by correcting the deformation obtained by the deformation correction unit 12 with the model graphic, and calculates the similarity between the two graphics (step 204).

  Then, the output unit 40 outputs the similarity calculated by the similarity determination unit 13 (step 205).

  Further, in step 203, the estimation is performed by the deformation estimation unit 11 in addition to the method of correcting the deformation of the inspection graphic by applying the deformation opposite to the deformation estimated by the deformation estimation unit 11 to the inspection graphic. It is also possible to adopt a method of matching the deformation of the model graphic and the inspection graphic by applying the deformation to the model graphic. In the same manner, in step 204, both figures can be compared and the similarity between both figures can be calculated.

  Next, the deformation estimation process in step 202 of FIG. 2 will be described in detail with reference to FIG.

  Referring to FIG. 3, first, the inspection graphic feature point information input from the inspection graphic input unit 20 is compared with the model graphic feature point information input from the model graphic input unit 30, and the corresponding feature point is obtained. By sequentially registering the determined feature point pairs as deformation estimation feature point pairs, a deformation estimation feature point pair list is created (step 301).

  In this step 301, for example, one arbitrary feature point a is selected from the inspection graphic feature points, and one arbitrary feature point b is selected from the model graphic feature points, and the difference between the feature amounts of the feature points a and b is obtained. If the difference between the feature amounts is equal to or less than a predetermined threshold value, the feature point is determined to be a corresponding feature point, and the feature point a of the inspection figure and the feature point b of the model figure determined to be the corresponding feature point Are registered in the feature point pair list for deformation estimation.

  In the deformation estimation feature point pair list, as shown in the example of FIG. 4, pairs of corresponding feature points of the feature point a of the inspection figure and the feature point b of the model figure are registered.

  Next, the deformation that best matches the feature point pairs registered in the deformation estimation feature point pair list is estimated (step 302).

  Here, a deformation model indicating the content of the deformation is prepared in advance according to the nature of the input figure, and the one that best matches the feature point pair is selected from the plurality of prepared deformation models. It is possible to use a method or a method in which a deformation model is prepared in advance corresponding to various parameter values and a parameter value that best matches each feature point pair is obtained.

  For example, when applied to fingerprint recognition, it is assumed that the finger is an elastic body, the elastic deformation is represented by parameters (parallel movement, contraction, expansion, rotation, shearing), and the fingerprint input from the inspection figure input unit 20 The position of each feature point when elastic deformation indicated by each parameter is registered in the deformation estimation feature point pair list, and the elastic deformation is performed so that the position of the feature point is best matched by this elastic deformation. Determine the parameters.

  Next, the estimated deformation is verified, and if the deformation is valid, the deformation is output (step 303).

  In the verification of the validity of this step 303, for example, when the estimated elastic energy of deformation is larger than a predetermined value, the estimated deformation is too large and the deformation model to be used is changed. Thus, it is possible to start from the creation of the deformation estimation feature point pair list.

  Next, the deformation estimation process by the deformation estimation unit 11 of the present embodiment will be described using a more specific example.

  Here, using the example of the model figure shown in FIG. 5 and the example of the inspection figure shown in FIG. 6, the deformation of the inspection figure is estimated, and whether or not the inspection figure is the same figure as the model figure is determined. The processing for checking will be described. In the model figure of FIG. 5, a1 to a4 are feature points of the model figure, and in the inspection figure of FIG. 6, b1 to b4 are feature points of the inspection figure.

  First, the inspection figure and the model figure are overlapped as shown in FIG. 7, and the feature points a1 to a4 of the model figure and the feature points b1 to b4 of the inspection figure are compared, and those that are considered to be the same feature points (a1, b1) , (A2, b4), (a3, b2), (a4, b4), (a4, b5). FIG. 8 illustrates these pairs.

  Here, considering that the inspection figure is deformed, it is necessary to allow for a certain amount of error, and the correspondence of feature points may not be completely understood, but at that time, what seems to correspond , (A2, b4), (a4, b4), and (a4, b5), and allow for overlap. Then, as shown in the example of FIG. 4, these pairs, p1: (a1, b1), p2: (a2, b4), p3: (a3, b2), p4: (a4, b4), p5: A list in which (a4, b5) is registered: a deformation estimation point pair list CL is recorded (step 301).

  Here, the coordinates of the feature points of the model figure are (x, y), the coordinates of the feature points of the inspection figure are (X, Y), and the model figure as a whole uses a 2 × 2 matrix α and a two-dimensional vector β. Suppose that it is subjected to uniform elastic deformation as expressed in the equation (1).

  Among the pairs p1 to p5 registered in the deformation estimation feature point pair list, the feature point pair position of the model figure of the i-th pair pi is (xi, yi), and the feature point position of the inspection figure is (Xi, Yi). When the feature point at (xi, yi) on the model figure is subjected to the elastic deformation represented by the equation (1), it moves to the position represented by the equation of FIG.

  When the difference between this position and (Xi, Yi), that is, when the model figure is deformed as shown in Equation 1, the difference in position from the pair pi is ei in Equation (3).

  The total E of the positional differences (squares) of the pairs p1 to p5 registered in the deformation estimation feature point pair list is expressed by the following equation (4).

  It is assumed that α and β that minimize the total position difference E are obtained and A and b are obtained respectively. Since the sum of the errors of the corresponding feature points at this time is the smallest, the deformation shown in the equation (5) using this A and b is the pair registered in the deformation estimation feature point pair list. This is the deformation that best matches.

  Therefore, it can be estimated that the deformation | transformation which has arisen in the test | inspection figure is represented by several 5 (step 302). FIG. 9 shows the model figure subjected to the estimated deformation and the inspection figure superimposed.

  The parameters and energy for this deformation are obtained as follows. The vector b in Expression 5 represents translation, and the matrix A represents contraction / expansion, rotation, and shear. When λ0, λ1, and λ2 are expressed as shown in Equations 6, 7, and 8, the elastic energy F is expressed as shown in Equation 9 (in Equation 9, K represents the peripheral compression ratio, and μ represents the shear rate) (It is a constant determined by the material).

  Note that rotation and parallel movement are merely movements of position and do not contribute to elastic energy. λ0 is a parameter corresponding to contraction and expansion (“0” when neither contracted nor expanded, a negative value when contracted, and a positive value when expanded). , Λ1 and λ2 are parameters corresponding to shear strain (“0” when not distorted at all, and the absolute value increases as the strain increases).

  If the parameters of the elastic energy and elastic deformation obtained here are too large as the deformation assumed in the inspection graphic, it is inappropriate as the deformation occurring in the inspection graphic, so the deformation is estimated again ( Step 303).

  For example, when the figure to be inspected is a fingerprint, a palm print, or the like, the object to be inspected is not a well-stretched object such as rubber, so there is a limit to the contraction / expansion, and the contraction / expansion where λ0 can be considered as a predetermined finger If this range is exceeded, the estimate is discarded. In addition, since there is a limit to the distortion of such fingerprints and palm prints, if λ1 and λ2 exceed the range of distortions that can be considered as fingerprints or palm prints, the estimation is similarly discarded. Similarly, if the elastic energy itself is not within the range of values assumed for fingerprints or palm prints, the estimation is discarded.

  As the next processing when the estimation is rejected, processing for changing the deformation model, processing for executing deformation estimation again after changing the method of creating the deformation estimation feature point pair list, and the like can be considered.

  Here, an example of changing the deformation model will be described.

  For example, assuming that the finger is a tighter rigid body than an elastic body, consider a deformation model of the rigid body (since the rigid body does not deform, only translation and rotation are considered). First, assuming that the object is a rigid body, the model graphic and the inspection graphic are converted so that the difference in the position of each feature point pair becomes small. FIG. 10 is a diagram in which the model graphic and the inspection graphic are superimposed on the conversion result.

  Next, in FIG. 10, since the feature point pairs p2: (a2, b4) and p5: (a4, b5) registered in the feature point pair list for deformation estimation are separated after the deformation, Delete from the feature point pair list for estimation. Further, as shown in FIG. 11, when (a2, b3) is deformed, it becomes close, so that it is additionally registered in the deformation estimation feature point pair list, and the deformation estimation feature point pair list is p1: (a1, b1), p3: (a3, b2), p4: (a4, b4), and p6: (a2, b3).

  Here, a method of finishing the estimation process is also possible, but a method of estimating the deformation by reapplying the elastic deformation model closer to the actual finger that was first used as the deformation model of the finger is also possible. FIG. 12 shows an estimation using the modified feature point list for deformation estimation p1: (a1, b1), p3: (a3, b2), p4: (a4, b4), p6: (a2, b3) It is the figure which gave elastic deformation.

  In this way, by repeating each of the pair selection, deformation estimation, and deformation verification processes, the correctness of the selection of feature point pairs is gradually increased. Estimate deformation.

  If the deformation is estimated, the inverse transformation of the equation (5) expressed by the equation (10) is applied to the feature point (X, Y) of the inspection graphic so that the deformation is corrected and can be directly compared with the model graphic. It can be converted to the coordinates (x, y) of the feature point. By comparing the inspection figure with the deformation corrected and the model figure, the similarity between the inspection figure and the model figure is calculated, and the inspection figure and the model figure are the same Judge whether it is a shape.

  Also, feature point pairs whose positions are separated by a predetermined threshold or more when the estimated deformation is applied are deleted from the above-described deformation estimation feature point pair list, and there are no feature point pairs to be estimated a predetermined number of times or to be deleted. By repeating the above, a method of narrowing down feature point pairs registered in the deformation estimation feature point pair list to a more reliable one is also possible.

  As described above, in the present embodiment, the deformation occurring in the inspection figure is estimated and the deformation is corrected, and the inspection figure corrected for the deformation is compared with the model figure to collate both figures. Therefore, even if the inspection graphic is deformed (and there is a difference in deformation between the inspection graphic and the model graphic), the inspection graphic and the model graphic can be strictly identified and collated.

  Next, a second embodiment of the present invention will be described in detail with reference to the drawings.

  FIG. 13 is a block diagram showing the configuration of the pattern matching apparatus according to the present embodiment, and FIG. 14 is a flowchart for explaining the pattern matching processing of the present embodiment.

  As shown in FIGS. 13 and 14, the difference of the present embodiment from the first embodiment is the function of the deformation estimation unit 11a in the data processing unit 10a. Further, the pattern matching processing of the present embodiment is the same as that of the first embodiment except that steps 401 and 402 are newly added after step 202.

  In the deformation estimation process of the present embodiment shown in FIG. 14, first, the same process as the deformation estimation process of the first embodiment is executed to estimate the deformation occurring as a whole in the inspection graphic (step 202). ). Next, the figure is divided into predetermined small areas (step 401), and deformation estimation processing is performed for each area in the same manner as in step 202 to estimate deformation in each area (step 402).

  Here, in the estimation result of the deformation in each small region, when it is not considered that only the small region is deformed peculiarly due to the property of the inspection object, (step 303 in the first embodiment) The validity of the estimation may be verified (as in). For example, after estimating the deformation for each small region, the validity of the estimation is evaluated by evaluating the relationship with the deformation estimated in the neighborhood region and the relationship with the deformation estimated as a whole. For example, a method such as re-estimation is possible.

  In addition, a method of repeating the estimation process by sequentially reducing the target area after estimating the deformation occurring as a whole in the inspection graphic can be similarly implemented. For example, when applied to fingerprint recognition, a force is applied to a part of a finger at the time of imprinting, and the method of deformation may differ from part to part. In such a case, the processing in steps 401 and 402 of the present embodiment The deformation can be estimated for each part.

  As described above, according to the present embodiment, in addition to the effects of the first embodiment, it is possible to correspond to a graphic whose deformation method is different for each part, and to estimate the erroneous deformation. Can be reduced.

  Next, a third embodiment of the present invention will be described in detail with reference to the drawings.

  FIG. 15 is a block diagram showing the configuration of the pattern matching apparatus according to the present embodiment, and FIG. 16 is a flowchart for explaining the pattern matching processing of the present embodiment.

  As shown in FIGS. 15 and 16, the difference of the present embodiment from the first embodiment is the function of the deformation estimation unit 11b in the data processing unit 10b. The pattern matching process according to the present embodiment is the same as the first embodiment except that steps 601, 602, and 603 are newly added after step 202.

  In the deformation estimation process of this embodiment shown in FIG. 16, first, the same process as the deformation estimation process of the first embodiment is executed to estimate the deformation generated as a whole in the inspection graphic (step 202). ). Next, the degree of concentration of feature points in the vicinity of an arbitrary feature point is measured (step 601). As shown in FIG. 17, an area having a predetermined size around an arbitrary feature point of interest is defined as the neighborhood of the feature point of interest, and the concentration of the feature points in the neighborhood is measured. It is.

  If there are feature point pairs whose number is greater than or equal to a predetermined threshold (step 602), the deformation estimation process similar to that of step 202 is applied to the vicinity of the feature point pair, thereby the vicinity around the feature point. Is estimated from a pair of feature points in the vicinity (step 603).

  As described above, in the present embodiment, by performing partial deformation estimation processing at locations where feature points are concentrated, it is possible to cope with figures that have different deformation methods for each part, and erroneous deformation is performed. It reduces the possibility of estimation.

  Further, when there is no feature point pair of a predetermined threshold or more in the vicinity of the feature point (step 602), it is not necessary to perform the deformation estimation process in the vicinity, and the deformation estimated as the entire inspection figure in step 202 is performed. Use.

  And based on the deformation | transformation estimation by step 202 and step 603, a test | inspection figure (or model figure) can be transformed (step 203), and the similarity of both figures can be calculated (step 204).

  In this embodiment, the validity of the estimation is evaluated by estimating the deformation for each feature point and evaluating the relationship with the deformation estimated around neighboring feature points and the relationship with the deformation estimated as a whole. If an invalid deformation is estimated (as in step 303 of the first embodiment), the estimation can be redone.

  As described above, according to the present embodiment, in addition to the effects of the first embodiment, it is possible to correspond to a graphic whose deformation method is different for each part, and to estimate the erroneous deformation. Can be reduced.

  Also, the deformation estimation processes of the second embodiment and the third embodiment can be implemented in combination with each other.

  In addition, the pattern matching apparatus of each said embodiment is the deformation | transformation estimation part 11, the deformation | transformation estimation part 11a, the deformation | transformation estimation part 11b, the deformation | transformation correction | amendment part 12, the similarity determination part 13, etc. in the data processing part 10, 10a, 10b. In addition to realizing the functions and other functions in hardware, it can be realized by loading a pattern matching program, which is a computer program having each function, into the memory of the computer processing apparatus.

  FIG. 18 is a diagram showing an embodiment of a configuration including a recording medium on which the pattern matching program of the present invention is recorded.

  The pattern matching program is stored in a recording medium 90 such as a magnetic disk, a semiconductor memory, or the like. Then, each function described above is realized by loading the data processing unit 10c, which is a computer processing device, from the recording medium and controlling the operation of the data processing unit 10c. As a result, the data processing unit 10c executes processing by the data processing units 10, 10a, and 10b in the first, second, and third embodiments under the control of the pattern matching program.

  Although the present invention has been described with reference to the preferred embodiments and examples, the present invention is not necessarily limited to the above-described embodiments and examples, and various modifications can be made within the scope of the technical idea. Can be implemented.

It is a block diagram which shows the structure of the pattern collation apparatus by the 1st Embodiment of this invention. It is a flowchart for demonstrating the process of the pattern collation of the 1st Embodiment of this invention. It is a flowchart for demonstrating the process of the deformation | transformation estimation part of the 1st Embodiment of this invention. It is a figure which shows the feature point pair list for deformation | transformation estimation of one Example of this invention. It is a figure which shows the model figure of one Example of this invention. It is a figure which shows the test | inspection figure of one Example of this invention. It is the figure which piled up the model figure and inspection figure of one Example of this invention. It is a figure which shows the feature point pair in the model figure and test | inspection figure of one Example of this invention. It is the figure which superimposed the model figure and the inspection figure which gave the estimated deformation | transformation of one Example of this invention. It is the figure which superimposed the moved model figure and test | inspection figure of one Example of this invention. It is a figure which shows the feature point pair in the moved model figure and test | inspection figure of one Example of this invention. It is the figure which superimposed the model figure and the inspection figure which gave the estimated deformation | transformation of one Example of this invention. It is a block diagram which shows the structure of the pattern collation apparatus by the 2nd Embodiment of this invention. It is a flowchart for demonstrating the process of the pattern matching of the 2nd Embodiment of this invention. It is a block diagram which shows the structure of the pattern collation apparatus by the 3rd Embodiment of this invention. It is a flowchart for demonstrating the pattern matching process of the 3rd Embodiment of this invention. It is a figure for demonstrating the measurement of the concentration degree of the feature point in the vicinity of the feature point of the 3rd Embodiment of this invention. It is a figure which shows one Example of a structure provided with the recording medium which recorded the pattern collation program of this invention.

Explanation of symbols

10, 10a, 10b, 10c Data processing unit 11, 11a, 11b Deformation estimation unit 12 Deformation correction unit 13 Similarity determination unit 20 Inspection graphic input unit 30 Model graphic input unit 40 Output unit 90 Recording medium

Claims (9)

Associate feature points between two fingerprints,
Estimating a parameter representing deformation so that the associated feature points overlap;
A parameter representing the deformation,
Decomposed into parameters representing rotation, translation, shrinkage expansion, shear strain,
By substituting the parameter representing the contraction and expansion into a predetermined formula having a predetermined peripheral compression ratio as a coefficient, the energy of contraction and expansion is determined,
The shear strain energy is determined by substituting the parameter representing the shear into a predetermined formula having a constant indicating a predetermined shear rate as a coefficient,
Define the magnitude of deformation as the sum of the energy of the contraction and expansion and the energy of the shear strain,
A deformation estimation method, wherein validity of a deformation is verified based on whether or not the size of the deformation is larger than a predetermined value. If the size of the deformation is greater than a predetermined value,
The deformation estimation method according to claim 1, wherein an appropriate deformation as a finger is estimated by re-associating feature points until the deformation size becomes smaller than the predetermined value . When the feature points of the two fingerprints are (x, y) and (X, Y), the parameter representing the deformation is

Where b represents translation and matrix A represents contraction, expansion, rotation, and breakage,
The contraction and expansion parameters are

The shear strain parameters

Represented by
Using the peripheral compression rate K and shear rate μ, the size of the deformation is

The deformation estimation method according to claim 1, wherein: Associate feature points between two fingerprints,
Estimating a parameter representing deformation so that the associated feature points overlap;
A parameter representing the deformation,
Decomposed into parameters representing rotation, translation, shrinkage expansion, shear strain,
By substituting the parameter representing the contraction and expansion into a predetermined formula having a predetermined peripheral compression ratio as a coefficient, the energy of contraction and expansion is determined,
The shear strain energy is determined by substituting the parameter representing the shear into a predetermined formula having a constant indicating a predetermined shear rate as a coefficient,
Define the magnitude of deformation as the sum of the energy of the contraction and expansion and the energy of the shear strain,
A deformation estimation apparatus that verifies the validity of a deformation based on whether or not the size of the deformation is larger than a predetermined value. If the size of the deformation is greater than a predetermined value,
The deformation estimation apparatus according to claim 4, wherein an appropriate deformation as a finger is estimated by re-associating feature points until a deformation size becomes smaller than the predetermined value . When the feature points of the two fingerprints are (x, y) and (X, Y), the parameter representing the deformation is

Where b represents translation and matrix A represents contraction, expansion, rotation, and breakage,
The contraction and expansion parameters are

The shear strain parameters

Represented by
Using the peripheral compression rate K and shear rate μ, the size of the deformation is

The deformation estimation apparatus according to claim 4, wherein Associate feature points between two fingerprints,
Estimating a parameter representing deformation so that the associated feature points overlap;
A parameter representing the deformation,
Decomposed into parameters representing rotation, translation, shrinkage expansion, shear strain,
By substituting the parameter representing the contraction and expansion into a predetermined formula having a predetermined peripheral compression ratio as a coefficient, the energy of contraction and expansion is determined,
The shear strain energy is determined by substituting the parameter representing the shear into a predetermined formula having a constant indicating a predetermined shear rate as a coefficient,
Define the magnitude of deformation as the sum of the energy of the contraction and expansion and the energy of the shear strain,
A deformation estimation program for causing a computer to execute a deformation estimation process for verifying the validity of a deformation depending on whether or not the size of the deformation is larger than a predetermined value. If the size of the deformation is greater than a predetermined value,
8. The deformation estimation program according to claim 7, wherein an appropriate deformation as a finger is estimated by re-associating feature points until the deformation size becomes smaller than the predetermined value . When the feature points of the two fingerprints are (x, y) and (X, Y), the parameter representing the deformation is

Where b represents translation and matrix A represents contraction, expansion, rotation, and breakage,
The contraction and expansion parameters are

The shear strain parameters

Represented by
Using the peripheral compression rate K and shear rate μ, the size of the deformation is

Claim 7 wherein deformation estimating program, characterized in that expressed as.

Images