Yanushkevich S.N., Wang P.S.P., Gavrilova M.L., Srihari S.N. (eds.) Image Pattern Recognition. Synthesis and Analysis in Biometrics
Подождите немного. Документ загружается.
April 2, 2007 14:42 World Scientific Review Volume - 9in x 6in Main˙WorldSc˙IPR˙SAB
168 Synthesis and Analysis in Biometrics
The result of verifying 650 available signatures using multiple
component slope histograms appears in Table 6.1 below. The same
experimental protocol was used as previously (Section 6.1) on the same
data, so these results can be compared directly against those in Table 6.1.
The use of multiple exemplars appears to be one of the best methods tried
so far.
Table 6.1. Results using multiple components.
Method Verification False accept False reject Time per
rate signature (sec)
Multiple exemplars 96.8 0.0 3.2 0.010
(threshold)
Multiple exemplars 98.4 1.2 0.36 0.10
(K nearest neighbors)
6.4.2. Shadow Masks
The second comparison method is the high success rate shadow mask
technique
[
20
]
,
[
21
]
. A shadow mask is a configuration of sampling squares
which cover the entire signature image, each sampling a small area of the
signature. A typical shadow mask configuration consists of a constant
number of sampling squares, say N × M such boxes, to cover the entire
image area. A feature vector is created for each image, each feature being
a count of the number of pixels in the shadow that is cast onto each of the
bars, cast from the center outward, as seen in Fig. 6.6. When all boxes and
features are considered we have information about the shape of all parts of
the signature.
Fig. 6.6. Definition of shadow masks: (a) An individual sampling square showing the
six projection areas. (b) The signature is drawn over a grid of these squares, centered
at the centroid. (c) Each calculation projects the signature in each square onto the
projection areas, and a bitmap.
April 2, 2007 14:42 World Scientific Review Volume - 9in x 6in Main˙WorldSc˙IPR˙SAB
Composite Systems for Handwritten Signature Recognition 169
We use a shadow mask configuration consisting of a constant number of
sampling squares, (where a sampling square consists of top, bottom, right,
left, and two diagonal shadow mask bars at 45 and −45 degrees) arranged
in n rows and m columns, where each square of size P × Q pixels. This
configuration covers the entire image area. A feature vector is made for
each image in which each “feature” of the feature vector is a count of the
number of pixels representing the shadow that is cast onto each of the bars
(cast from the center outward) that make up the sampling box. Because
the sampling boxes are configured such that they touch one another at the
borders, the feature vector stores only 4 of the 6 shadow mask bars making
up a single sampling box. This means that most of the bars will be shared
with another sampling box, and storing all 6 bars would be redundant.
In total, the feature vector contains 4 × m × n + m + n features.
Once feature vectors have been computed for each image in the database,
the usual nearest neighbor Euclideandistance calculation is made when
classifying a feature vector.
While the algorithm was neither scale- nor rotation-invariant, it was
made somewhat translation-invariant by computing the “hyper-centre of
inertia”, essentially the centroid, of each signature. This was then used to
translate the signature to the center of the image prior to the casting of
shadows. In this way the signatures of the same person would overlap each
other more readily, assuming they were all placed one on top of another,
even though they may not line up the same way with the boundaries of the
sampling boxes.
The reported accuracy of the aforementioned signature verification
method is extremely high, in the 98–99% range, and thus bears further
investigation. Our implementation of the algorithm was tested on a
database of genuine signatures (black and white in pbm format) and, using
a leave-one-out method, keeps track of the percentage of signatures that
are correctly classified. We should mention that our work has identified a
minor flaw in the original shadow mask implementation in that it appears
to use scale, or the signature size, as a feature. We corrected this in our
own implementation, which may have affected the measured success rates
[
18
]
.
6.4.3. Intermediate Results
We tested our version on 11 sets of signatures, for a total of 539 images.
Each set, at one time, contained 50 signatures each. However, some had
to be removed due to problematic data (e.g. an image consisting of all
background). These signatures were relatively constant in terms of size
and orientation. That is, signatures belonging to the same set were similar
April 2, 2007 14:42 World Scientific Review Volume - 9in x 6in Main˙WorldSc˙IPR˙SAB
170 Synthesis and Analysis in Biometrics
in size, although signatures belonging to different sets sometimes varied
in size. Our measured success rate was 99.26%, which agrees with the
published result.
It may be of interest to note that, when tested using a set of 50 traced
forgeries, the program correctly classified them as belonging to a distinct
class. Forgeries, however, have not been thoroughly tested.
Using a leave-one-out protocol, the slope histogram technique achieved
a success rate of 89.1%, while the use of shadow masks gave 89.9%. This is,
by the way, lower than the published rate of over 99%, but this reflects the
method is neither scale nor rotation invariant. All the methods here are
using the same data, and are therefore being compared on an equal basis.
The graph in Fig. 6.7 shows how the success rate of these two methods
varies with the number of signatures used to train, and permits a direct
comparison with the temporal distance, global relative distance, and the
slope histogram methods discussed.
Success Rate
Number of Training Signatures
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
30
40
50
60
70
80
90
Temporal Distance
Slope Histogram
Global Distance
Fig. 6.7. Results for the signature recognition techniques discussed. Graphs of success
rate VS number of training items. All four methods are shown.
6.5. Composite Classifiers
In the process of designing vision systems and pattern analysis algorithms,
it is natural that a variety of techniques be tried, with the overall goal
of improving the rate at which patterns can be correctly classified. Many
diverse algorithms each have strengths and weaknesses, good ideas and bad.
One way to take advantage of this variety is to apply many methods to the
April 2, 2007 14:42 World Scientific Review Volume - 9in x 6in Main˙WorldSc˙IPR˙SAB
Composite Systems for Handwritten Signature Recognition 171
same recognition task, and have a scheme to merge the results
[
3
]
,
[
9
]
,
[
10
]
; this should be successful over a wider range of inputs than would any
individual method. Indeed, it is what will be demanded of such a multiple
classifier system: it must have a higher overall recognition rate than any of
the individual classifiers that make it up, or there is no point to the extra
effort involved.
Composite classifiers can be made up of similar classifier types
(e.g. nearest K neighbor, geometric features) or of quite diverse types
(non-homogeneous). In the latter case it is hoped to take advantage of the
diversity in the classifier set to achieve an increase in robustness. Classifiers
can differ in both the nature of the measurements used in the classification
process and in the type of classification produced:
Type I classification is a simple statement of the class,
Type II classification is a ranked list of probable classes, and
Type III classification assigns probabilities to classes.
A problem with the evaluation of composite classifiers is the availability
of the needed large number of classifications for a valid characterization,
along with the associated ground truth. A large data set is not enough; a
correct implementation of a collection of classifiers is needed. Even then the
nature of the classifications is pre-determined; there are many variables that
simply cannot be controlled. Thus it is that many published combination
algorithms have been tried only on relatively few data sets and in relatively
few variations.
It is desirable to promise a set of predictable behaviours under a wide
variety of circumstances. For instance, how does a composite classifier
behave when more than half of the component classifiers have high
correlations? When correlations are small? When one or more classifiers
fail on a few classes? These questions need answers
6.5.1. MergingType1Responses
Given that the output of each of the classifiers is a single, simple
classification value (a type I response), the obvious way to combine them
is by using a voting strategy. A majority voting scheme can be expressed
as follows: let C
i
(x) be the result produced by classifier i for the image x,
where there are k different classifiers in the system; then let H(x, d)bethe
number of classifiers giving a classification of d for the image x,whered is
one of 0,1,2,3,4,5,6,7,8,9. Then
E(x)=
j, if MAX(H(x, i)=H(x, j)andH(x, j) >
k
2
10, otherwise.
April 2, 2007 14:42 World Scientific Review Volume - 9in x 6in Main˙WorldSc˙IPR˙SAB
172 Synthesis and Analysis in Biometrics
This is called a simple majority vote (SMV). An easy generalization of
this scheme replaces the constant k/2 in the above expression with k ×a for
0 ≤ α ≤ 1 27. This permits a degree of flexibility in deciding what degree
of majority will be sufficient, and will be called a weighted majority vote
(WMV). This scheme can be expressed as:
E(x)=
j, if MAX(H(x, i)=H(x, j)andH(x, j) >αk)
10, otherwise.
Neither of these takes into account the possibility that all of the
dissenting classifiers agree with each other. Consider the following cases:
(a) In case A there are ten classifiers, with six of them supporting a
classification of “6”, one supporting “5”, one supporting “2” and two
classifiers rejecting the input digit.
(b) In case B, using the same ten classifiers, six of them support the
classification “6” and the other four all agree that it is a “5”.
Do cases A and B both support a classification of “6”, and do they do
so equally strongly?
One way to incorporate dissent into the decision is to let max1 be the
number of classifiers that support the majority classification j (MAX1=
H(x, j)), and to let MAX2 be the number supporting the second most
popular classification h (MAX2=H(x, h)). The the classification
becomes:
E(x)=
j, if MAX(H(x, i)=H(x, j)andMAX1 −MAX2 ≥ αk)
10, otherwise.
where α is between 0.0 and 1.0. This is called a Dissenting-Weighted
Majority Vote (DWMV).
For the five classifier system being discussed, the SMV strategy gave a
99.4 success rate. Evaluation of WMV is a little more difficult, requiring an
assessment of the effect of the value of a on the results. A small program
was written that varied a from 0.05 to 0.95, classifying all samples on each
iteration. This process was then repeated five more times, omitting one of
the classifiers each time to again test the relative effect of each classifier on
theoverallsuccess. Withthismuchdataanumericalvalueisneededthat
can be used to assess the quality of the results. The success rate could be
used alone, but this does not take into account that a rejection is much
better than a misclassification; both would count against the recognition
rate. A measure of reliability can be computed as:
Reliability = recognition/(100%-rejection)
The reliability value will be low when few misclassifications occur.
Unfortunately, it will be high if recognition is only 50%, with the other
April 2, 2007 14:42 World Scientific Review Volume - 9in x 6in Main˙WorldSc˙IPR˙SAB
Composite Systems for Handwritten Signature Recognition 173
50% being rejections. This would not normally be thought of as acceptable
performance. A good classifier will combine high reliability with a high
recognition rate; in that case, why not simply use the product
Reliability\index{subject}{Reliability}× Recognition
as a measure of performance? In the 50/50 example above this measure
would have the value 0.5: reliability is 100% (1.0) and recognition is
50% (0.5). In a case where the recognition rate was 50%, with 25%
rejections and 25% misclassifications, this measure will have the value 0.333,
indicating that the performance is not as good. The value Reliability×
Recognition will be called acceptability. The first thing that should be
done is to determine which value of a gives the best results, and this is more
accurately done when the data is presented in tabular form (Table 6.2).
Table 6.2. Acceptability
of the Multiple Classifier
Using a Weighted Majority
Vote.
Alpha Success
0.05 0.994
0.25 0.994
0.50 0.992
0.75 0.956
From this information it can be concluded that a should be between
0.45 and 0.5, for in this range the acceptability peaks without causing a
drop in recognition rate. DWMV also uses the a parameter, and can be
evaluated in a fashion identical to what has just been done for WMV. The
optimal value of a, obtained from Table 6.3, was found to be 0.25.
6.5.2. MergingType2Responses
The problem encountered when attempting to merge type 2 responses is
as follows: given M rankings, each having N choices, which choice has the
largest degree of support?
For example, consider the following 3 voter/4 choice problem
[
23
]
:
Voter 1: abcd Voter 2: cabdVoter 3: bdca
This case has no majority winner; a, b and c each get one first place vote.
Intuitively, it seems reasonable to use the second place votes in this case to
see if the situation resolves itself. In this case b receives two second place
April 2, 2007 14:42 World Scientific Review Volume - 9in x 6in Main˙WorldSc˙IPR˙SAB
174 Synthesis and Analysis in Biometrics
Table 6.3. Acceptability of
the Multiple Classifier Using a
Dissenting Weighted Majority
Vote.
Alpha Success
0.05 0.993
0.25 0.985
0.30 0.985
0.45 0.960
0.55 0.960
0.65 0.932
0.80 0.932
0.85 0.984
votes to a’s one, which would tend to support b as the overall choice. In
the general case there are a number of techniques for merging rank-ordered
votes, four of which will be discussed here.
The Borda count
[
5
]
is a well-known scheme for resolving this kind of
situation. Each alternative is given a number of points depending on where
in the ranking it has been placed. A selection is given no points for placing
last, one point for placing next to last, and so on up to N − 1 points for
placing first. In other words, the number of points given to a selection is
the number of classes below it in the ranking. For the 3 voter/4 choice
problem described above the situation is:
Voter 1: a(3) b(2) c(1) d(0),
Voter 2: c(3) a(2) b(1) d(0),
Voter 3: b(3) d(2) c(1) a(0),
where the points received by each selection appears in parentheses behind
the choice. The overall winner is the choice receiving the largest total
number of points:
a =3+2+0=5
b =2+1+3=6
c =1+3+1=5
d =0+0+2=2.
This gives choice b as the “Borda winner”. However, the Borda count does
have a problem that might be considered serious. Consider the following 5
April 2, 2007 14:42 World Scientific Review Volume - 9in x 6in Main˙WorldSc˙IPR˙SAB
Composite Systems for Handwritten Signature Recognition 175
voter/3 choice problem: Voter 1: abc,Voter 2: abc,Voter 3: abc,
Voter 4: bca,Voter 5: bca.
The Borda counts are a =6,b=7,c= 2, which selects b as the winner.
However, a simple majority of the first place votes would have selected a!
This violates the so-called majority criterion
[
23
]
:
If a majority of voters have an alternative X as their first choice, a
voting rule should choose X.
This is a weaker version of the Condorcet Winner Criterion
[
6
]
:
If there is an alternative X which could obtain a majority of votes in
pair-wise contests against every other alternative, a voting rule should
choose X as the winner.
This problem may have to be taken into account when assessing
performance of the methods.
Finally, we have the monotonicity criterion: If X is a winner under
a voting rule, and one or more voters change their preferences in a way
favorable to X without changing to order in which they prefer any other
alternative, then X should still be the winner. No rule that violates the
monotonicity criterion will be considered as an option for the multiple
classifier. This decision will not eliminate the Borda count. With
the monotonicity criterion in mind, two relatively simple rank merging
strategies become interesting. The first is by Black
[
4
]
, and chooses the
winner by the Condorcet criterion if such a winner exists; if not, the Borda
winner is chosen. This is appealing in its simplicity, and can be shown to be
monotonic. Another strategy is the so-called Copeland rule
[
23
]
:foreach
option compute the number of pair-wise wins of that option with all other
options, and subtract from that the number of pair-wise losses. The overall
winner is the class for which this difference is the greatest. In theory this
rule is superior to the others discussed so far, but it has a drawback in that
it tends to produce a relatively large number of tie votes in general.
The Borda, Black, and Copeland rules were implemented as described
and applied to the five classifier problem, and the results are summarized
in Table 6.4.
From Table 6.4, it would appear that the Borda scheme is tied with
Black, followed by Copeland. It is important to temper this view with
the fact that this result was obtained from basically one observation.
Confirmation would come from applying these schemes to a large number
of sets of characters.
April 2, 2007 14:42 World Scientific Review Volume - 9in x 6in Main˙WorldSc˙IPR˙SAB
176 Synthesis and Analysis in Biometrics
Table 6.4. Results of the
Voting Rules for Rank
Ordering.
Rule Success
Borda 99.9
Black 99.9
Copeland 99.6
6.5.3. MergingType3Responses
The problem of merging type 3 responses was not pursued with as much
vigor as were the type 1 and 2 problems, as very few systems yield
probabilities as their output. Indeed, the solution may be quite simple.
Xu decides that any set of type 3 classifiers can be combined using an
averaging technique. That is,
P
E
(x ∈ C
i
|x)=
1
k
k
j=1
P
j
(x ∈ C
i
|x),i=1, 2,...,M,
where P
E
is the probability associated with a given classification for
the multiple classifier, and P
k
is the probability associated with a given
classification for each individual classifier k. The overall classification is
the value j for which is a maximum. There is little actual type 3 data,
but it could be approximated by using the a posteriori method described
previously, where it is used to convert type 1 responses to type 3 responses.
Using this approximate data set, the result obtained by merging type 3
responses using averaging is given by:
Correct: 997 Incorrect: 3 Rejected: 0
Acceptability is 0.994.
6.5.4. Results from the Multiple Classifier
Using the acceptability measure to assess each of the merging methods
discussed, we need to look only at the best method in each of the three
groups; that is, the best multiple type 1 classifier, the best type 2, and the
best type three. The best three are given in Table 6.5.
From the Table 6.5 above it can be seen that the best classifier explored
uses the Black scheme for merging rank ordered responses.
April 2, 2007 14:42 World Scientific Review Volume - 9in x 6in Main˙WorldSc˙IPR˙SAB
Composite Systems for Handwritten Signature Recognition 177
Table 6.5. Multiple classifier results.
Name Type Acceptability
SMV 1 0.994
Black 2 0.998
Average 3 0.994
6.5.5. Further Classifier Combination Techniques
Kittler
[
10
]
suggests five possible combination strategies, and compares
these and a majority vote against each other on four actual classifiers and
2213 handprinted character samples. The best two of these combination
strategies, the median rule and the sum rule, are of interest here. Both are
based on the assumption, again, that the a priori probabilities associated
with each classifier are very near the a posteriori probabilities. The sum
rule, for R classifiers and m classes is:
Assign θ to class
(1 − R)P (w
j
)+
k
i=1
P w
j
|x
i
= max
m
k=1
[(1 − R)P (w
k
)+
R
i=1
P w
k
|x
i
].
The median rule can be expressed as:
Assign θ to class w
j
MEDIAN
R
i=1
P w
j
|x
i
=MAX
m
k=1
MEDIAN
R
i=1
P w
k
|x
i
,
where the x
i
represent measurements on the item: a feature vector. The
value of P can be found in the confusion matrix for each classifier i.
Other rank-based schemes could be used as well
[
24
]
,
[
25
]
.Behindthe
Borda count is the presumption that the second most likely classification is
relatively near, in terms of likelihood or preference, to the best classification;
its rank is only one away it. Consider a four-candidate vote and the result
ABCD. The sum of the ranks is 6 (in general N(N − 1)/2forN
candidates). Treating these as scores, A gets 3 and B gets 2; the difference
(1) is 1/6 of the total, the same as the difference between B and C,and
the difference between C and D. In other words, a Borda count assumes
that the distance between each candidate, once sorted, is the same; a
presumption of uniformity.
This uniformity assumption is often flawed in the case of classifiers,
although it may be the best that can be done for elections, the domain