Int. J. of Computers, Communications & Control, ISSN 18419836, EISSN 18419844
Vol. V (2010), No. 4, pp. 525531
Fingerprints Identiﬁcation using a Fuzzy Logic System
I. Iancu, N. Constantinescu, M. Colhon
Ion Iancu, Nicolae Constantinescu, Mihaela Colhon
Department of Informatics
University of Craiova,
Al.I. Cuza Street, No. 13, Craiova RO200585, Romania
Email: i_iancu@yahoo.com, nikyc@central.ucv.ro, mghindeanu@yahoo.com.
Abstract: This paper presents an optimized method to
Int. J. of Computers, Communications & Control, ISSN 18419836, EISSN 18419844Vol. V (2010), No. 4, pp. 525531
Fingerprints Identiﬁcation using a Fuzzy Logic System
I. Iancu, N. Constantinescu, M. Colhon
Ion Iancu, Nicolae Constantinescu, Mihaela Colhon
Department of InformaticsUniversity of Craiova,Al.I. Cuza Street, No. 13, Craiova RO200585, RomaniaEmail: i_iancu@yahoo.com, nikyc@central.ucv.ro, mghindeanu@yahoo.com.
Abstract:
This paper presents an optimized method to reduce the points numberto be used in order to identify a person using fuzzy ﬁngerprints. Two ﬁngerprintsare similar if
n
out of
N
points from the skin are identical. We discuss the criteriaused for choosing these points. We also describe the properties of fuzzy logic andthe classical methods applied on ﬁngerprints. Our method compares two matchingsets and selects the optimal set from these, using a fuzzy reasoning system. Theadvantage of our method with respect to the classical existing methods consists in asmaller number of calculations.
Keywords:
fuzzy models, ﬁngerprint authentication, cryptographic signature model.
1 Introduction
Fingerprint identiﬁcation is the most mature biometric method being implemented at an early levelsince 1960. The recognition of a ﬁngerprint can be done with two methods: ”onetoone” (veriﬁcation)and ”onetomany” (
:
N
identiﬁcation). The ﬁrst method is applied when we have two ﬁngerprintsand we want to verify if they belong to the same person. The second one is used when we have oneﬁngerprint and we search it in a data base. The veriﬁcation is much easier and faster because we have thetwo ﬁngerprints and we just need to compare them. On the other hand, the identiﬁcation implies moretime for extracting the ﬁngerprint because there are needed much more details.The ﬁngerprints are not compared with images, they use a method based on characteristic pointsnamed ”minutiae”. These points are characterized by
ridge ending
(the abrupt end of a ridge),
ridgebifurcation
(a single ridge that divides in two ridges),
delta
(a Yshaped ridge meeting),
core
(a Uturn inridge pattern), etc. All these features are grouped in three types of lines:
line ending
,
line bifurcation
and
short line
. After the minutiae points are localized, a map with all their locations on the ﬁnger is created.Every minutiae point has associated two coordinates
(
x
,
y
)
, an angle for orientation and a measure for theﬁngerprint quality. The matching of two ﬁngerprints depends on the position and on the rotation. For thisreason, every ﬁngerprint is represented, not only, as a group of points with two coordinates, but also, asa group of points with coordinates relative to other points. This allows obtaining an unique positioningof a point regarding to other three points. The three selected points must not be collinear. When twoﬁngerprints are compared, ﬁrst are compared the relative coordinates. If this stage ends successfully,these coordinates are transformed in 2D coordinates and veriﬁed.After verifying the ﬁngerprints, the result will tell us if they are from the same person with a highprobability. Still, the cases when the belonging probability of a ﬁngerprint is 0 (false) or 1(true) arerarely. In most of the cases, the probability will be a number
p
∈
[
,
]
. This fact leads to a fuzzy logic.The values in fuzzy logic can range between 0 and 1 (1 is for absolute truth, 0 for absolute falsity). Afuzzy value for an element
x
will express the degree of membership of
x
in a set
X
. It is essential torealize that fuzzy logic uses truth degrees as a mathematical model of the vagueness phenomenon whileprobability is a mathematical model of randomness.
Copyrightc
20062010 by CCC Publications
526 I. Iancu, N. Constantinescu, M. Colhon
2 State of the Art
Two ﬁngerprints are similar if
n
out of
N
points match. To verify this, Freedman et al. introducedthe fuzzy matching protocols [3]. Using these protocols, the information about the ﬁngerprint we wantto identify (or verify) will not be revealed if no match is found. To describe the fuzzy private matchingproblem we will take a set of words
X
=
x
...
x
N
where
{
x
i
}
are the letters. Two words
X
=
x
...
x
N
and
Y
=
y
...
y
N
match only if:
n
≤
{
k
:
x
k
=
y
k

≤
k
≤
N
}
and this relation is denoted with
X
≈
n
Y
. Inthe subsequent we will name the set
X
as the
total set for selection
. The input of the protocol will be twosets of words (
X
=
X
...
X
m
for the client and
Y
=
Y
...
Y
s
for the server) and the parameters
m
,
s
,
N
and
n
. While the output of the server is empty, the output of the client will be a set
{
Y
i
∈
Y

∃
X
i
∈
X
:
X
i
≈
n
Y
i
}
,where
A
≈
n
B
means that the points
A
and
B
are very close. This set is, in fact, the intersection of thetwo input sets [1]. It was demonstrated that this protocol leads information about the input even if nomatch is found [1]. Another protocol, based on Freedman’s protocol, was presented in [1]. It uses
σ
as acombination of
n
different indices
γ
,
γ
...
γ
n
and
σ
(
X
) =
x
γ

...

x
γ
t
for a word
X
. After the parametersand the public key are sent, the client constructs a polynomial representation of the points set:
P
σ
= (
x
−
σ
(
X
))
∗
(
x
−
σ
(
X
))
∗
...
∗
(
x
−
σ
(
X
m
))
Thisis afeedbackpolinomialvalueforasetofﬁngerprints. Thenhesends
{
P
σ
}
k
totheserver. Theserveranalyzes every received polynomial
{
P
σ
}
at the point
σ
(
Y
i
)
and computes
{
w
σ
i
}
k
=
{
r
∗
P
σ
(
σ
(
Y
i
))+
Y
i
}
k
,where
r
is a random value. After all the calculations, the server sends
{
w
σ
i
}
k
to the client. The clientwill decrypt all the messages and if
w
σ
i
matches with any word from
X
then it is added to the outputset.
{
w
σ
i
}
k
is a combination between ﬁngerprint points value and the parameter which characterizes thecommon information between a base set and the current set of collected values.A particular scheme of ﬁngerprint authentication describes a method which is not based on the minutiae points [12], but by the texture of the ﬁnger, called FingerCode. Such a FingerCode is a vectorcomposed from
values between
and
. The vector is ordered and stable in size. The method usesEuclidean distance to ﬁnd the matching. After estimating the block orientation, a curvature estimatoris designed for each pixel. Its maximal value is, in fact, the morphological searched center. Using aproperly tuned Gabor ﬁlter ( [11,13]) we can catch ridges and valleys from the ﬁngerprint. The FingerCode is computed as the average absolute deviation from the mean of every sector of each image.Errorcorrection for the FingerCode would never be efﬁcient enough to recognize a user. In [12], themethod proposed uses a secret
d
+
−
letter word
, which correspond to the
d
+
coefﬁcients of a polynomial
p
of degree
d
. The public key will be extract from
(
F
,
p
)
, where
F
is the FingerCode. Then, wechoose
n
random point of
p
. These points will be hidden like in a fuzzy commitment scheme. To ﬁnd thepolynomial
p
, each point is decoded. If at least
d
+
points are decoded then
p
can, also, be retrieved.A method based on the minutiae points and, also, on the pattern of the ﬁnger was presented in [4]. Allthe ridges that cross a line
(
x
,
y
)
where
x
and
y
are minutiae points are counted. Then, are presented all thepossible combinations of three minutiae points and the ridges crossing that line. Such a combinations’list needs
C
n
entries, where
n
is the number of minutiae points. This method is more complex becausebefore all the calculations are done we need to identify the minutiae points and then combine them.
3 Our Method
3.1 System Description
A commercial ﬁngerprintbased authentication system requires a very low False Reject Rate (FRR)for a given False Accept Rate (FAR) where FAR is
the probability that the system will incorrectly identify
and FRR is
the probability of failure in identiﬁcation
.
Fingerprints Identiﬁcation using a Fuzzy Logic System 527Our method is, also, based on the minutiae points of the ﬁngerprints. We can identify at least 40minutiae points on a ﬁngerprint, depending on its quality. In general, the number of the minutiae pointsvaries from 0 to 100. All the methods mentioned above can be applied to a ﬁngerprint veriﬁcation. But,for an identiﬁcation we need an algorithm with a low level of complexity because the data bases usedin practice have millions of ﬁngerprints. To reduce the search time and complexity, we ﬁrst propose toclassify the ﬁngerprints, and then, to identify the input ﬁngerprints only in one subset of the data base.To choose the right subset the ﬁngerprint is matched at a coarse level to one of the existing types. Afterthat, it is matched at a ﬁner level to all the ﬁngerprints of the subset. The FBI in the United Statesrecognize eight different types of patterns [5]. For example, we have an input ﬁngerprint and we wantto identify it in a data base with 15000 entries. We will take the minim number of minutiae points, 40.If no classiﬁcation is made we have to do at least
×
=
operations. But, if we use aclassiﬁcation with eight types (each subset has the same number of ﬁngerprints
/
=
) wewill have at least
(
+
)
×
=
calculations. This is because we will ﬁrst compare the inputﬁngerprint with each group and after that it will be compared with each element of the chosen group.As we can see, the calculations are reduced to only
,
%. The classiﬁcation of the ﬁngerprints ispreferred to have more than three types of subsets. This is because a higher accuracy is achieved. Sucha classiﬁcation, also, helps to reduce the number of calculations with a higher percentage.
3.2 Fuzzy Mathematical Background
A fuzzy set
A
in
X
is characterized by its membership function:
µ
A
:
X
→
[
,
]
where
µ
A
(
x
)
∈
[
,
]
represents the membership degree of the element
x
in the fuzzy set
A
. We will work with membership functions represented by trapezoidal fuzzy numbers. Such a number
N
= (
m
,
m
,
α
,
β
)
is deﬁned as
µ
N
(
x
) =
for x
<
m
−
α
x
−
m
+
α α
for x
∈
[
m
−
α
,
m
]
for x
∈
[
m
,
m
]
m
+
β
−
x
β
for x
∈
[
m
,
m
+
β
]
for x
>
m
+
β
The rules are represented by fuzzy implications. Let
X
and
Y
be two variables whose domains are
U
and
V
, respectively. The rule
if X is A thenY is B
is represented by its conditional possibility distribution ( [14], [15])
π
Y
/
X
:
π
Y
/
X
(
v
,
u
) =
µ
A
(
u
)
→
µ
B
(
v
)
,
∀
u
∈
U
,
∀
v
∈
V
where
→
is an implication operator ( [2]) and
µ
A
and
µ
B
are the membership functions of the fuzzy sets
A
and
B
, respectively. One of the most important implication is Lukasiewicz implication [2],
I
L
(
x
,
y
) =
min
(
−
x
+
y
,
)
.
3.3 Proposed Fuzzy Logic System
Fuzzy control provides a formal methodology for representing, manipulating and implementing human’s heuristic knowledge about how to control a system. In a fuzzy logic controller, the expert knowledge is of the form
528 I. Iancu, N. Constantinescu, M. Colhon
IF
(
a set of conditions are satisfied
)
THEN
(
a set of consequences are inferred
)
where the antecedents and the consequences of the rules are associated with fuzzy concepts (linguisticterms). The most known systems are: Mamdani, Tsukamoto, Sugeno and Larsen which work with crispdata as inputs. A Mamdani type model which works with interval inputs is presented in [10].In this paper we use a version of Fuzzy Logic Control (FLC) system from [9] in ﬁngerprints identiﬁcation. This version is characterized by:
ã
the
linguistic terms
(or values), that are represented by trapezoidal fuzzy numbers
ã
Lukasiewicz implication
, which is used to represent the rules
ã
the
crisp control action of a rule
, computed by MiddleofMaxima method
ã
the
overall crisp control actions
, computed by discrete CenterofGravity.We assume that the facts can be given by crisp data, intervals and/or linguistic terms and a rule ischaracterized by:
ã
a set of linguistic variable
A
, having as domain an interval
I
A
= [
a
A
,
b
A
]
ã
n
A
linguistic values
A
,
A
,...,
A
n
A
for each linguistic variable
A
ã
membership function
µ
A
i
(
x
)
for each value
A
i
, where
i
∈
{
,,...,
n
A
}
and
x
∈
I
A
.According to the structure of a FLC, the following steps are necessary in order to work with oursystem.
Firing levels
We consider an interval input
[
a
,
b
]
with
a
A
≤
a
<
b
≤
b
A
.
The membership function of
A
i
is modiﬁed( [10]) by membership function of
[
a
,
b
]
as follows
∀
x
∈
I
A
,
µ
A
i
(
x
) =
min
(
µ
A
i
(
x
)
,
µ
[
a
,
b
]
(
x
))
where
µ
[
a
,
b
]
(
x
) =
if x
∈
[
a
,
b
]
otherwise
It is obvious that, any tnorm
T
can be used instead of
min
(see, for instance, [6–8]).The ﬁring level, generated by the input interval
[
a
,
b
]
, corresponding to the linguistic value
A
i
is givenby:
µ
A
i
=
max
{
µ
A
i
(
x
)

x
∈
[
a
,
b
]
}
.
The ﬁring level
µ
A
i
, generated by a linguistic input value
A
′
i
is
µ
A
i
=
max
{
min
{
µ
A
i
(
x
)
,
µ
A
′
i
(
x
)
}
x
∈
I
A
}
.
The ﬁring level
µ
A
i
, generated by a crisp value
x
is
µ
A
i
(
x
)
.
Fuzzy inference
We consider a set of fuzzy control rules
R
i
:
if X
is A
i
and
...
and X
r
is A
r i
then Y is C
i
where the variables
X
j
,
j
∈
{
,,...,
r
}
,
and
Y
have the domains
U
j
and V, respectively. The ﬁring levelsof the rules, denoted by
{
α
i
}
, are computed by
α
i
=
T
(
α
i
,...,
α
r i
)
where
T
is a tnorm and
α
ji
is the ﬁring level for
A
ji
,
j
∈
{
,,...,
r
}
. The conclusion inferred from therule
R
i
, using the Lukasiewicz implication is
C
′
i
(
v
) =
I
(
α
i
,
C
i
(
v
))
,
∀
v
∈
V
.