A method, an apparatus for fingerprint matching

Fingerprint matching method and equipment technical field

[0001] The present invention generally relates to the field of fingerprint matching. In particular, the present invention relates to a method, device, and computer program product for searching a database including data related to multiple fingerprints.

Background technique

[0002] Prior art fingerprint identification devices and methods use a person's fingerprint as an image read by an image sensor or such device to identify the person. The image sensor reads the fingerprint of the person to be recognized, and saves an image of the read fingerprint. The image can be checked by an algorithm for identification purposes. Check the degree of matching between the fingerprint image and the fingerprint image previously registered in the database. This can be done by comparing the fingerprint image with a large number of fingerprint images stored in the database. If the matching degree is equal to or greater than the threshold, the person's identity is verified. The pattern matching method can be used to calculate the degree of matching between two fingerprint images.

[0003] In the prior art, a linear search of the entire database can be performed during fingerprint matching. Using this approach, a full search of the database potentially involves millions or more of comparisons, which in general reduces the speed of fingerprint matching processing.

[0004] There are previously known methods, such as the Henry classification system, which classifies fingerprints into main families based on the fingerprint structure. However, it is generally difficult to make this classification without safe human intervention.

[0005] Moreover, the problem that arises when trying to find an unknown fingerprint in the fingerprint database is that the fingerprints extracted from the same finger at different times are almost never the same. The changes in the texture may depend on, but not limited to, for example:

[0006] The plasticity of the finger, for example, the fingerprint when the finger is pressed hard on the surface is different from the fingerprint when the finger is only lightly pressing on the surface;

[0007] The fingerprint is distorted due to moisture, dirt, humidity, etc. on the surface or on the finger;

[0008] The size of the contact area between the finger and the surface;

[0009] The rotation angle of the finger.

[0010] Therefore, it is advantageous to search not only for the same fingerprint pattern but also for similar or similar patterns when searching the database during fingerprint matching. However, using the linear search method mentioned above to find similar or similar patterns in the database generally basically reduces the speed.

[0011] Therefore, an improved fingerprint search method, device, and computer program product are advantageous to increase the speed of finding a match when searching a database that includes data related to multiple fingerprints.

Summary of the invention

[0012] Correspondingly, the present invention preferably seeks to alleviate, alleviate or remove one or more of the above-identified defects and shortcomings in the art, one by one or in combination.

[0013] According to a first aspect of the invention, there is provided a method for searching a database including data related to a plurality of fingerprints. The method includes identifying at least two feature points in an image of an unknown fingerprint; generating multiple attributes based on the at least two feature points; assigning a number including multiple digits to each of the multiple attributes; Digitally generate a digital representation of the fingerprint; and use the digital representation as a search argument when searching a database; where the digital table

CN 101512552 Β

The display is generated by at least partially interleaving the plurality of digits.

[0014] The interleaving may include interleaving a plurality of digits so that the digits in the digital representation are arranged in an interlaced or interlaced form.

[0015] The allocation may include allocating a number including a plurality of bits to each of the plurality of attributes.

[0016] The interleaving may include interleaving the most important bit among the plurality of bits.

[0017] The interleaving may include interleaving all the bits in the plurality of bits.

[0018] The interleaving may include bit-by-bit interleaving of the plurality of bits.

[0019] The interleaving may include arranging multiple bits in the digital representation in order of importance from the most important bit to the least important bit.

[0020] In one embodiment, the allocation may include dividing each binary digit a3 a₂ a] _a(nb₃ b₂ bbg c₂cj co, d₃ d₂ dj d₀... N₃ N₂Let N° be assigned to each of the multiple attributes, and the generation may include generating the digital representation by arranging multiple bits in the following order: N₃... d₃c₃ b₃ a₃ N₂... d₂ c₂ b₂ a₂ N_P .. dj 5 bj day 1 N. · · · CIq Cq t) Q o

[0021] In another embodiment, the allocation may divide each binary digit 83 a₂ a₁ a₀>b₃ b₂Dagger blood heart c₂ 5 c₀>d₃ d₂ dj d₀... N₃ N₂ Nj N° is assigned to each of multiple attributes, and the generation may include generating the digital representation by arranging multiple bits in the following order: a₃ b₃ c₃d₃... N₃ a₂ b₂ c₂ d₂... N₂ a₁ b₁ 5 d_P .. Nj a₀bo ^cod₀... N₀o

[0022] In yet another embodiment, the allocation may include dividing each binary digit a to a₆ a₅ a₄ a₃ &_2&1 a₀, b₇b₆ b₅ b₄ b₃ b₂ bj b₀>c₇ c₆ c₅ c₄ c₃ c₂ 5 c₀ d₇ d₆ d₅ d₄ d₃ d₂ Mountain d₀... N₇ N₆N₅ N₄ N₃ N₂ Called N. Assigned to each of a plurality of attributes, and the generation may include generating the number table by arranging the plurality of bits in the following order: N₇... d₇ c₇ b₇ a₇ N₆... d₆ c₆b₆ a₆N₅... d₅ c₅ b₅ a₅ N₄... d₄ c₄ b₄ a₄ N₃... d₃^c3 b₃ a₃ N₂... d₂ c₂b₂ 3-2 Ν]...d[C[ b]a,₁ N_o... d₀ c₀ b₀ a. .

[0023] In another embodiment, the allocation may include converting each unary digit a to a₆ a₅ a₄ a₃ &_2&1 a₀, b₇ b₆ b₅ b₄ b₃ b₂ bj b₀>c₇ c₆ c₅ c₄ c₃ c₂ 5 c₀ d₇ d₆ d₅ d₄ d₃ d₂ Mountain d₀... N₇ N₆N₅ N₄ N₃ N₂ Called N. Allocate to each of a plurality of attributes, and the generation may include the generation of a child by arranging the plurality of bits in the following order: Είγ by C7 dy... N7 cig bg Cg dg... Ng C5 d^.. . N5 aq d^... N4 cig

<td>^C3 small 3···[0024]</td><td>,N₃ a₂ b₂ c₂ d₂... N₂ a_x b_x c_x .. N_x a₀ b₀ c₀ d₀... N₀o In another embodiment, the allocation may include dividing each binary digit a? a₆ a₅ a₄ a₃ a?ai a₀&gt; b₇</td>

b₆ b₅ b₄ b₃ b₂ bj b₀>c₇ c₆ c₅ c₄ c₃ c₂ 5 c₀ d₇ d₆ d₅ d₄ d₃ d₂ Mountain d₀... N₇ N₆N₅ N₄ N₃ N₂ Called N. Assigned to each of multiple attributes, and the generating may include generating the digital representation by arranging the multiple bits in the following order: a₇ a₆ a₅ a₄ a₃ a₂ a₁ a₀ a₇ b₇ c₇d₇... N₇ b₆ c₆ d₆... N₆ b₅ c₅ d₅... N₅ b₄ c₄

[0025] The method may also include masking out at least some of the least important bits of the plurality of bits.

[0026] The method may further include, after the allocating step, grouping the multiple attributes into multiple subsets composed of each attribute. Then, the generating may include generating a plurality of digital representations of the fingerprint based on the subset of attributes, wherein each digital representation may be generated by at least partially interleaving the plurality of digits. Moreover, the use may include using these multiple digital representations as search arguments when searching the database.

[0027] According to the second aspect of the invention, there is provided a computer program product, which includes a program that causes the computer system to execute the method described in the first aspect of the invention when these program instructions are run on a computer system with computer capabilities.

CN 101512552 Β

Order instructions. The computer program product may be embedded in a recording medium, stored in a computer memory, embedded in a read-only memory, or carried on an electrical carrier signal.

[0028] According to a third aspect of the invention, a device for searching a database including data related to multiple fingerprints includes: an identification unit adapted to identify at least two feature points in an image of an unknown fingerprint; The first generating unit is suitable for generating multiple attributes based on the at least two characteristic points; the assigning unit is suitable for assigning a number including multiple digits to each of the multiple attributes; the second generating unit is suitable for A digital representation for generating the fingerprint based on the assigned number; and a search unit adapted to use the digital representation as a search argument when searching the database. The second generating unit is adapted to generate the digital representation by at least partially interleaving the plurality of digits.

[0029] According to the fourth aspect of the invention, there is provided a use of the method, device or computer program product of any aspect of the invention. The use of the method, the device, or the computer program product can be, for example, crime scene investigation, police control, verification equipment at airports, industrial parks, or buildings, or customs clearance systems.

[0030] Other embodiments of the invention are defined in the dependent claims.

Description of the drawings

[0031] Other objects, features and advantages of the invention will appear from the following detailed description of the embodiments of the invention, see these drawings, in which:

[0032] FIG. 1 is a graphical representation of a fingerprint and its characteristic points;

[0033] FIG. 2 is a graphical representation of parameter data that is the feature of the fingerprint feature points in FIG. 1;

[0034] FIG. 3 is a flowchart illustrating a method according to an embodiment of the present invention;

[0035] FIG. 4A is a table;

[0036] FIG. 4B is another table;

[0037] FIG. 5 is a block diagram of a device according to an embodiment of the present invention; and

[0038] FIG. 6 is a block diagram of a computer program product according to an embodiment of the present invention.

Detailed ways

[0039] The embodiments described below disclose the optimal mode and enable those of ordinary skill in the art to implement the invention. The different features in these embodiments can be combined in ways other than those described below. The invention can be embodied in many different forms and should not be construed as being limited to the embodiments described in the text. Of course, these embodiments are provided so that this disclosure is detailed and complete, and the scope of the invention is fully conveyed to those skilled in the art, and the invention is only defined by the appended patent claims.

[0040] One embodiment of the method will be described below. The method generally includes the following steps: identifying feature points; generating attributes; assigning numbers; generating representations; and using the representations when searching the database. Each of these steps will be described below.

[0041] Identifying feature points involves identifying two or more feature points in an unknown fingerprint image.

[0042] Generating attributes involves generating multiple attributes based on these two or more feature points.

[0043] Assigning a number involves assigning a number including a number of numbers, such as a number of binary digits (bits), to each of a plurality of attributes.

[0044] Generating a representation involves generating a digital representation of the fingerprint based on the assigned number. The digital representation is generated by at least partially interleaving the plurality of digits. Correspondingly, the digits in the digital representation can be

CN 101512552 Β

The inside is arranged in an interlaced or alternating form. Therefore, the generation of the digital representation can be referred to as interleaving the digits of the multiple digits into a single digital representation.

[0045] Using the representation when searching a database involves searching a database that includes data related to multiple fingerprints by using a digital representation as a search argument.

[0046] In an embodiment, the method further includes, after the assignment, grouping the multiple attributes into multiple subsets composed of the attributes. In this embodiment, the generation involves generating multiple digital representations of the fingerprint based on a subset of the attributes. Moreover, the use then involves the use of multiple digital representations as search arguments when searching the database.

[0047] The test result is that the fingerprint is represented by the one or more numbers, and it is possible to find similar shapes in a database including data related to multiple fingerprints at an improved speed than the prior art solutions. Or similar properties. As a result, it is possible to perform a speed-improved search in the sorted list of the database. In fact, the speed can be improved according to some embodiments of the invention, with speed factor improvements up to and including approximately 100.

[0048] Fingerprint

[0049] FIG. 1 illustrates a representation of a portion of a fingerprint 10, such as a human fingerprint. The fingerprint 10 is typically represented by one or more attributes, which are the characteristics of the collected feature points associated with the fingerprint 10, and these feature points are usually called "minutiae points". These feature points associated with the fingerprint 10 are typically obtained from the image of the fingerprint 10 using, for example, image processing techniques, and all of these image processing techniques can be implemented by the embodiments of the invention. Different image processing techniques for this purpose are known in the prior art and can be implemented by a person of ordinary skill in the art.

[0050] The characteristic points of the fingerprint 10 can be determined or obtained from the singular points in the ridge pattern of the fingerprint 10. As illustrated in FIG. 1, the ridge pattern may include singular points, such as ridge end points or ridge bifurcations. Point A is an example of the end point of the ridge, and points B and C are an example of the bifurcation of the ridge. As illustrated in Figure 2, each local feature point can be represented by the coordinates (X, y) of the local feature in a reference system, which is shared by all local feature points in a given fingerprint image.

[0051] During the fingerprint matching process, two or more feature points in the unknown fingerprint 10 are identified. Then, multiple attributes are generated based on these two or more identified feature points. Each of these multiple attributes is generally unique to the identified feature point, and thus can be used as a feature of the unknown fingerprint 10 at least in the vicinity of the identified feature point.

[0052] Properties

[0053] There are many different types of attributes, namely biometric attributes, all of which can be used or implemented by embodiments of the present invention. Hereinafter, some examples of attributes are described so that this disclosure is detailed and complete for those skilled in the art, and can implement the embodiments of the present invention. However, the examples mentioned below are not intended to limit the scope of the invention.

[0054] The attribute may be the distance D associated with a pair of feature points. In particular, the distance D associated with a specific pair of feature points can represent the distance of a straight line drawn between two identified feature points.

[0055] The attribute may be the local direction θ of the ridge pattern at the coordinates (x, y) of each of the identified feature points. In particular, the local direction θ associated with a specific feature point may indicate the direction of the ridge line, or the slope of the image at the specific feature point relative to a straight line drawn from the specific feature point to another feature point. It should be understood that the slope at a certain point (x, y) generally points to the direction in which the pixel value changes significantly in the vicinity of the point, which is typically regarded as an edge criterion.

[0056] The attribute may be the angle α of the ridge pattern at the coordinates (X, y) of each of the identified feature points. In particular, the angle α associated with a specific feature point can represent the first direction relative to the straight line drawn from the specific feature point to another feature point at the specific feature point and the relative distance from the specific feature point to another feature point. The ridge of the straight line is drawn in this

CN 101512552 Β

The angle between the second direction at a specific feature point.

[0057] The attribute may be a ridge count RC associated with a pair of feature points. In particular, the ridge line count RC associated with a given pair of feature points may be the number of ridge lines intersected by a straight line drawn between corresponding feature points.

[0058] The attribute may be the area Ao associated with three or more identified feature points

[0059] As an example, FIG. 2 shows some attributes, which are the characteristics of the fingerprint 10 in the vicinity of the feature point ABC where the unknown fingerprint 10 is recognized. In this example, the attributes include D₂> D₃> θ 9 2, π, α], α?, α 3, and Α. In addition, attributes can include ridge count RC_ab, RC_ac, RC_bc (Not shown), here RC_abRepresents the number of ridges intersected by the straight line drawn between feature points A and B, where RC_acRepresents the number of ridges intersected by the straight line drawn between feature points A and C, and here RC_bcRepresents the number of ridge lines intersected by the straight line drawn between feature points B and C.

[0060] Fang Di

[0061] FIG. 3 illustrates one embodiment of a method for searching a database including data related to a plurality of fingerprints. The database can be, for example, a large database. Large databases generally include millions of records, such as tens of millions of records or more.

[0062] In the first step, step 301, two or more feature points in an image of an unknown fingerprint 10 are identified. These two or more feature points can be obtained or determined from the singular points in the ridge pattern of the unknown fingerprint 10. The step 301 of identifying feature points may include extracting these feature points.

[0063] In the next step, step 302, based on the two or more feature points identified in the unknown fingerprint 10 in step 301, multiple attributes are generated, that is, two or more attributes. The step 302 of generating multiple attributes may include grouping or collecting two or more feature points into one or more subsets (such as triples). Each subset can be associated with two or more feature points. For each subset that can be selected, one or more attributes can be generated as a feature of the selected subset.

[0064] The one or more attributes generated in step 302 may be, for example, one or more of the aforementioned attributes in the attribute section. That is, one or more attributes can be selected from the group including the following attributes: the distance between two feature points; relative to the direction of a straight line drawn from a specific feature point to another feature point at the specific feature point ; The angle of the ridge pattern at the coordinates of a specific feature point; the number of ridge lines intersected by a straight line drawn between two feature points; and the area associated with at least a subset of the feature points.

[0065] There are many different implementation solutions to perform steps 301-303, namely identifying feature points and/or generating associated attributes representing the fingerprint 10. All these attributes can be used by embodiments of the present invention. Different methods for identifying feature points and/or generating associated attributes are known in the art and can be implemented by those skilled in the art. Therefore, this will not be explained in the text.

[0066] It is advantageous to limit the number of attributes to be identified in step 301. In order to limit the number of attributes, these attributes can be filtered according to certain criteria. Such criteria may be, for example, but not limited to the maximum and/or minimum value of the attribute in question. Correspondingly, such a criterion may be, but is not limited to, the maximum and/or minimum (if there are three or more recognized feature points) of the area covered by the straight line connecting the identified feature points, and so on. Various rules for reducing or limiting the number of attributes by using certain standard filtering can be implemented by the embodiments of the present invention. Another rule to limit the number of attributes may be to include only those attributes whose image slope or ridge direction difference in the feature points meets certain filtering criteria.

[0067] In step 303, a number is assigned to each of the multiple attributes. The number includes multiple digits. The number may be, for example, a number including a number of binary digits (bits). The number may include, for example, 4 bits (that is, half a byte), 6 bits, 8 bits (that is, one byte), 16 bits, 24 bits, 32 bits, or more bits.

CN 101512552 Β

[0068] Referring now to FIG. 2, in one example, four attributes must be. 2. α ί and A_ocGenerated from the three identified feature points A_B_C of the fingerprint 10. In step 303, these four attributes can be assigned, for example, the following binary numbers composed of one byte, each of which is a? a₆ a₅ a₄ a₃a₂ a₁ a₀,b₇ b₆ b₅ b₄ b₃ b₂ b₀,c₇ c₆ c₅ c₄ c₃ c₂Ci c₀ And d7 d6 d5 d4 d3 d2 dldOo that is D] is assigned the number a? a₆ a₅ a₄ a₃ a₂ a]a₀, D? is assigned the number b? b₆ b₅ b₄ b₃b₂ bj b. , And so on.

[0069] In step 304, the digital representation of the fingerprint 10 is generated based on the assigned number. The digital representation is formed by at least partially interleaving multiple digits of multiple attributes. Therefore, the digital representation will represent or at least be associated with multiple attributes. Correspondingly, the digital representation can be configured as a feature of the fingerprint 10 at least in the neighborhood of two or more identified feature points. Thus, a single digital representation can be formed in step 304, wherein at least some digits in the digital representation are arranged in an interlaced or alternating manner.

[0070] It is particularly advantageous to create or generate a single digital representation based on the numbers assigned by multiple attributes. Generally speaking, the more attributes are included in the single digital representation, the more unique the single digital representation obtained becomes. In one embodiment, the assigned number is formed of multiple bits as described above. The interleaving of multiple bits may include interleaving multiple bits so that the digital representation forms a single value. The single value can be in the form of a bit stream, where the bits in the bit stream are arranged in an interleaved or alternating form. The digital representation may for example be created or generated so that all bits in the numbers assigned by the respective attributes or only those bits considered to be important bits are included in the single digital representation in an interleaved or alternating form.

[0071] It should be understood that the number of attributes involved in the combined single number representation can be any number greater than one. Moreover, it should be understood that the binary bits from each attribute can be grouped from 1 bit up to the entire length of the attribute (typically but not limited to one byte) before being interleaved into a single digital representation.

[0072] Referring again to FIG. 2 and the above examples, various examples of the numerical representation will now be described.

[0073] According to an embodiment of the invention, the digital representation is generated by arranging these binary digits in the following order: d? c₇ b₇ a₇ d₆ c₆ b₆ a₆ d₅ c₅ b₅ a₅ d₄ c₄ b₄ a₄ d₃ c₃ b₃ a₃ d₂ c₂ b₂ a₂^ c₁ b₁ a₁ d₀ c₀b. a₀o

[0074] According to another embodiment of the invention, the digital representation is created by arranging bits in the following order: a? b₇ c₇ d? a₆ b₆ c₆ d₆ a₅ b₅ c₅ d₅ a₄ b₄ c₄ d₄ a₃ b₃ c₃ d₃ a₂ b₂ c₂ d₂ a,₁ b_x c_x d] a_obo ^cod. .

[0075] According to some embodiments, the generation or creation of the digital representation includes interleaving only the most important bits of the plurality of bits.

[0076] In one embodiment, the digital representation is created by arranging in the following order: a? a₆ a₅ a₄ a₃a₂ a]a₀ a₇ b₇ c₇ d₇ b₆ c₆ d₆ b₅ c₅ d₅ b₄ c₄ d₄ b₃ c₃ d₃ b₂ c₂ d₂ b₁ 5 mountain b₀ c₀ d. .

[0077] In another embodiment, the generation of the digital representation includes interleaving only the two most important bits for each attribute according to the following bit sequence: d₇ c₇ b₇ a₇ d₆ c₆ b₆ a₆ d₅ d₄ d₃ d₂ Mountain d₀ c₅ c₄ c₃ c?® c₀ b₅ b₄ b₃ b₂ b]

[0078] In yet another embodiment, the generation of the digital representation includes interleaving only two or three of the most important bits for each attribute, and so on. Due to changes in the image quality, contact pressure, etc. of the fingerprint 10, it is generally reasonable to think that the two least important bits in each attribute are not important or at least hardly important. This means that the digital representation can be masked 8 bits in. In one embodiment, the digital representation can thus be generated, for example, by arranging the bits in the following order: d₇ c₇b₇ a₇ d₆ c₆ b₆ a₆ d₅ c₅ b₅ a₅ d₄ c₄ b₄ a₄ d₃ c₃ b₃ a₃ d₂ c₂ b₂ a₂o

[0079] When creating the digital representation, it should be understood that the goal is to make the digital representation as unique as possible. Therefore, since some LSDs in the participating attributes will change due to dust, humidity, etc., they can be masked out. The freed space can be changed

CN 101512552 Β

To be used to add important bits from one or more attribute types. Another potential reason for masking out some LSDs in the participating attributes is that the purpose of the embodiments of the present invention is to find similar or similar attributes. With this in mind, one should realize that some of the LSD in the participation attribute has nothing to do with achieving good results.

[0080] In step 305, the digital representation is used as a search argument when searching a database including data related to multiple fingerprints. Correspondingly, these numbers representing attributes in the unknown fingerprint 10 are used as binary search arguments for similar or similar attributes stored in the database. That is, searching for the same or similar fingerprints in step 305 includes searching for corresponding attributes in a database including data related to multiple fingerprints.

[0081] In an embodiment, the method further includes another step of grouping multiple attributes into multiple attribute subsets after the allocation in step 303. In this embodiment, the generating step, step 304, includes generating multiple digital representations of the fingerprint based on the attribute subset. Furthermore, step 305 includes using multiple digital representations as search arguments when searching the database.

[0082] As an example, a database that includes data related to multiple fingerprints may include a global table of digital representations from previously saved fingerprints. Each element in the global table may include not only the digital representation of the fingerprint, but also the digital representation of the identity of the person from which the fingerprint originated. The digital representation of the identity can be called the owner index.

[0083] In one embodiment, the search result is a number of similar numerical representations, which can be stored in the temporary table T1. Sort the table T1 based on the owner index and create a second table T2 by counting the number of persons found. The table T2 may thus include the index of the owner and the frequency count of the attributes of the owner. When sorting the frequency counts in increasing order, T2 will include the list of the most likely owners at the first place in the list.

[0084] The purpose is to identify the most probable all persons found in T2. In the first step, the index of the owner is used to retrieve the fingerprint or representation of the most probable owner from the database. In the second step, filter conditions are used to generate the first multiple digital representations of the unknown fingerprint. In the third step, the second plurality of digital representations of the known fingerprint retrieved from the database are generated using the same or similar filtering conditions as the first plurality of digital representations. In the fourth step, each digital representation in the first set is compared with each digital representation in the first plurality of digital representations. If there are two representations that are similar to each other, these two representations can create a matching pair. When all the representations in the first and second plurality of digital representations are compared, multiple matching pairs are created.

[0085] In the fifth step, for each of the matching pairs, the rotation angle is calculated. The rotation angle is represented by the following relationship: the angle between a straight line passing through two of the feature points represented by the first number in the matching pair and the corresponding straight line in the second number representation. Create multiple rotation angles by calculating the rotation angles of all matching pairs. In the sixth step, count the frequencies of all rotation angles +/- an allowable difference, and the maximum frequency rotation angle can be found and compared with the frequency values of the remaining rotation angles. If the minimum frequency difference is lower than a threshold, these fingerprints do not match. In the seventh step, for each feature point participating in each digital representation in the multiple matching digital representations, the existence of the feature points in the remaining digital representations in the multiple matching digital representations is detected. Create multiple matching feature points PMF, where the PMF includes all the feature points represented by all the numbers participating in the discovery of the feature points. The number of matching feature points is equal to the number of unique feature points in PMF.

[0086] FIG. 4A shows an example of a table listing similar values obtained from attributes assigned numbers 52, 49, 53. Once looking at the table shown in Figure 4A, it should be understood that only one binary search is required, and the number of linear searches is sufficient to find all similar attributes in the table. If the numbers A, B, and C in the table represent the sides of a triangle, those skilled in the art will recognize that triangles of similar shape will be found adjacent to each other. However, the interleaving result of this bit number is not always a list of adjacent values. Figure 4B shows another attribute list, where 2 binary searches are required to find values derived from similar triples. More attribute lists can be created, indicating that more than 2 binary searches are required. Has been sent

CN 101512552 Β

Now, if the number of binary digits used in the number assigned to each attribute changes by +/-1, the number of binary searches required to find all attributes of similar shape in the sorted global table is consistent with the prior art solution. Compared to significantly reduce. It should be recognized that once you look at Figures 4A and 4B, and compare this with SQL statements that can be used in prior art solutions. Such SQL statements can have the following syntax:

[0087] SELECT*From GLOBALTABLE where A> AC0NST-2AND A<

[0088] AC0NST+2AND B>BC0NST-2AND B<BC0NST+2AND C>

[0089] CC0NST-2 AND C &lt;CC0NST+2

[0090] Equipment

[0091] In the embodiment shown in FIG. 5, a device for searching a database including data related to a plurality of fingerprints

50, including:

[0092] The identification unit 501 is suitable for identifying at least two feature points in an unknown fingerprint image;

[0093] The first generating unit 502 is suitable for generating multiple attributes based on at least two feature points;

[0094] The allocating unit 503 is suitable for allocating a number including a plurality of digits to each of the plurality of attributes; [0095] The second generating unit 504 is suitable for generating the fingerprint based on the assigned number Numerical representation; and [0096] The search unit 505 is suitable for using the numerical representation as a search argument when searching the database.

[0097] The second generating unit 504 is suitable for generating the digital table by at least partially interleaving the plurality of digits.

[0098] Each unit in the device 50 may be, for example, in hardware, such as a processor with a memory. The processor may be any of a variety of processors, such as Intel or AMD processors, CPUs, microprocessors, programmable intelligent computers (PIC), microcontrollers, digital signal processors (DSP), etc. . However, the scope of the invention is not limited to these specific processors. The memory can be any memory that can store information, such as random access memory (RAM), such as double density RAM (DDR, DDR2), single density RAM (SDRAM), static RAM (SRAM), dynamic RAM (DRAM), video RAM (VRAM) and so on. The memory can also be flash memory, such as USB, portable flash memory (CF card), SM card, MMC memory, memory stick (MS card), SD card, mini SD (MiniSD card), micro SD (MicroSD card), xD card, TF Card and micro-drive memory and so on. However, the scope of the invention is not limited to these specific memories.

[0099] According to another embodiment, the device 50 includes a unit suitable for performing the method steps defined in any one of the embodiments.

[0100] In one embodiment, the device 50 is used in police control or crime scene investigation.

[0101] In another embodiment, the device 50 is used in a customs clearance system in an airport, an industrial park, or a building, etc.

[0102] In yet another embodiment, the device 50 is used to verify whether someone can use a certain type of facility. Examples of such facilities are automatic teller machines, access control systems, and systems composed of various electronic facilities such as mobile phones or computers.

[0103] Computer Program Product

[0104] In the embodiment shown in FIG. 6, a computer program product 60 for searching a database including data related to multiple fingerprints includes:

[0105] The identification code segment 601 is suitable for identifying at least two feature points in an unknown fingerprint image;

[0106] The first generated code segment 602 is suitable for generating multiple attributes based on at least two feature points;

[0107] The allocation code segment 603 is suitable for allocating a number including multiple digits to each of multiple attributes;

[0108] The second generation code segment 604 is suitable for generating a digital representation of the fingerprint based on the assigned number;

CN 101512552 Β

and

[0109] The search code segment 605 is suitable for using the digital representation as a search argument when searching a database.

[0110] The second generation code segment 604 is suitable for generating the digital representation by at least partially interleaving the plurality of digits. The computer program product can be embedded in a recording medium, stored in a computer memory, embedded in a read-only memory, or carried on an electrical carrier signal, for example.

[0111] According to another embodiment, the computer program product 60 processed by the computer system includes computer program code means for executing the method defined in any one of the embodiments.

[0112] The computer program product 60 can be loaded and run in a computer-capable system. Computer program, software program, program product, or software, in this context means any expression composed of a set of executions written in any programming language, code or symbol, intended to allow a computer-capable system to be directly or converted into another A specific function is performed after a language, code, or symbol.

[0113] Some embodiments of the invention improve the speed of the search process when searching a database including data related to multiple fingerprints. The advantage of some embodiments of the invention is that they provide improved performance for searching databases containing data related to multiple fingerprints.

[0114] The invention can be implemented in any suitable form, including hardware, software, firmware, or any combination thereof. However, it is advantageous to implement the invention as computer software running on one or more data processors and/or digital signal processors. The elements or elements in the embodiments of the invention may be physically, functionally and logically implemented in any suitable manner. Indeed, functionality can be implemented in a single unit, in multiple units, or as part of other functional units. As such, the various embodiments of the invention may be implemented in a single unit, or may be physically and functionally distributed between different units and processors. Referring to FIG. 5, the units 501, 502, 503, 504, and 505 may be implemented in one or more computers connected to a local or remote network, for example. Examples of such networks include but are not limited to LAN, WAN, UMA, GAN, Bluetooth, etc. As an example, when the embodiment of the present invention is used in a police management and control application, it is advantageous to have the unit 501 in the local device, and at least the unit 505 is implemented in the remote server.

[0115] The combination and modification of the above-mentioned embodiments should be able to be implemented by a person of ordinary skill in the art to which this invention belongs.

[0116] The applications and uses of the above-mentioned embodiments of the present invention are various and include all fields where fingerprint matching is used

[0117] Unless otherwise defined, all terms (including technical and scientific terms) used in the text have the same meaning as commonly understood by those of ordinary skill in the art to which the present invention belongs. It will also be understood that terms, such as those defined in commonly used dictionaries, should be interpreted as consistent with their meaning in the relevant field and will not be interpreted as ideal or excessively formal, unless the text is expressed in terms of So limited.

[0118] It should also be emphasized that the singular form "a" used in the text is intended to also include the plural form, unless otherwise described in terms of expression. It will also be understood that the terms "including" and/or "comprising" when used herein are used to indicate the described features, integers, steps, operations, elements, and/or elements, but do not exclude one or more The existence or addition of other features, integers, steps, operations, elements, elements, and/or groups formed by them.

[0119] The present invention has been described above with reference to specific embodiments. However, in addition to the above-mentioned embodiments, there are equally possible other embodiments within the scope of the invention. The method steps that are different from the above that execute the method through hardware or software or a combination of hardware and software can be provided within the scope of the invention. The different features and steps of the invention can be combined in ways other than the above-mentioned combination. The above-mentioned different embodiments do not limit the scope of the invention, but the scope of the invention is only limited by the appended patent claims.

<img file="CN101512552B_D0001.tif" />

<img file="CN101512552B_D0002.tif" />

c