J.-H. Chang, K.-C. Fan / Pattern Recognition 34 (2001) 1907}1925
1917
the (R
, < ) pair will give us an explicit solution in
G>ꢀꢁꢀꢂ\ꢀ
G
allocating the genuine ridge points.
In order to interpret the condition of elements con-
tained in the train set, we divide the train set into three
portions and discuss them individually.These three por-
tions of elements are the initial elements, the intermediate
elements, and the terminal elements.
4
.2.1. The initial elements
For Types 1 and 2 section sets, the starting element in
the train set is a valley point without reference ridge point
at its left.Therefore, we discard the initial valley element
if this train set comes from Types 1 and 2 section sets.For
Types 3 and 4 section sets, the initial element pair that
belongs to the train set is (R , < ) and R is the starting
ꢀ
ꢀ
ꢀ
element (see Fig.12).
4
.2.2. The intermediate elements
After eliminating the starting valley point for Types
1
and 2 section sets, the rest of elements in the train set
are all intermediate elements excepts the terminal ridge
points of Types 2 and 4 section sets.There exist three
di!erent conditions while observing the gray-level shift
Fig.13. Intermediate conditions.
for the intermediate element pairs (R
, < ).Fig.13
right.If there exists an element pair ( R
, < )
G>ꢀꢁꢀꢂ\ꢀ
G
I>ꢀꢁꢀꢂ\ꢀ
I
illustrate these three conditions.The element pairs with
larger drop height are obtained from distinct ridges, and
the element pairs with smaller drop height are coming
from an identical ridge line.The image background also
produces many element pairs.
with i(k(n that satis"es rule (2), we mark the
temporal ridge point R as a genuine ridge element
R
and discard all ridge points from R
On the other hand, if there does not exist any ele-
to R
.
H>ꢀ
I>ꢀꢁꢀꢂ\ꢀ
ment pair, which satis"es rule (2) while searching to
We can extract the genuine ridge points in the train set
by the following rules.Let the function gray( ) ) denote
the gray value of elements in the train set.For any
candidate element pair (R , < ), j"1, , m and
the end of train set, we keep R and make decision
according to the terminal elements.
R
(4) The element pair (R , < ) that does not satisfy any of
H
G
the rules (1), (2) or (3) will be discarded.Since there
will exist some blur area in a "ngerprint image
which is produced by slightly movement while ac-
quiring this "ngerprint image, we will discard these
uncertain ridge elements to avoid locating erron-
eous ridge points, i.e., the ridge points that are ac-
tually derived from background or ravines.
2
H
G
i"1, , n, there exist four possibilities for the belonging
2
of element R .
H
(
1) R is derived from the ripple of image background if
H
the gray value of R is smaller than ¹ .That is,
R 3C if gray(R )(¹ .We will discard this ridge
H
H
H
element R :
H
(
2) R is accepted as genuine ridge point if the element
4.2.3. The terminal elements
H
pair (R , < ) satis"es the following conditions: The
The terminal elements are de"ned as the rightmost
ridge element that has not been referenced by any ele-
ment.Thus, only Types 2 and 4 section sets possess
terminal ridge elements.Figs.14(a) and (b) illustrate the
terminal conditions for the section sets that are termin-
ated inside a ridge.There will exist a temporal ridge
R with P(R )(P(R ).For this condition, we accept the
H
G
gray value of R is larger than ¹ and the gray value
H
0
di!erence of R and < exceeds ¹ .By de "ning the
H
G
"
set of genuine ridge points as R, R 3R if and only if
H
gray(R )'¹ and (gray(R )!gray(< ))'¹ .
H
0
H
G
"
(
3) Both R and < are derived from the same ridge line
H
G
of a "ngerprint image if the gray value of < is larger
G
R
R
K
than ¹ and the gray value di!erence of R and
terminal ridge element R as a genuine ridge point with-
out any limitation.The section sets as illustrated in
0
H
R
<
is smaller than ¹ .That is, R , < 3C if
G
"
H
G
0
gray(< )'¹ and (gray(R )!gray(< ))(¹ .We
Fig.14(c), which possess the terminate ridge R , are
acquired from Types 2 and 4 section sets.We accept the
terminal ridge element R if the element pair (R , < )
satis"es the acceptance rule (2).
G
0
H
G
"
K
will store this ridge element R as a temporal ridge
H
point R .Several element pairs, which belong to the
R
K
K
L
identical ridge line, appear following the "rst identi-
cal ridge element pair R .We will search the other
element pairs still left in the train set from left to
The gray-scale ridge allocation algorithm is a combi-
R
nation of "nding the genuine ridge points by the rules
Hofmann
