Pattern Recognition 64 (2017) 268–276

Contents lists available at ScienceDirect

Pattern Recognition
journal homepage: www.elsevier.com/locate/pr

Eﬃcient temporal pattern recognition by means of dissimilarity spaceembedding with discriminative prototypes

MARK

⁎

Brian Kenji Iwanaa,b, , Volkmar Frinkena,c,d, Kaspar Riesene, Seiichi UchidaaaDepartment of Advanced Information Technology, Kyushu University, Fukuoka, Japan
Institute of Decision Science for a Sustainable Society, Kyushu University, Fukuoka, Japan
Electrical and Computer Engineering, UC Davis, Davis, CA, USAdOnai Technology, San Jose, CA, USAe
University of Applied Sciences and Arts Northwestern Switzerland, Olten, Switzerlandbc

A R T I C L E I N F O

A BS T RAC T

Keywords:
Temporal patterns
Online digit classiﬁcation
Dissimilarity representation
Ensemble classiﬁcation
Dissimilarity space embedding

Dissimilarity space embedding (DSE) presents a method of representing data as vectors of dissimilarities. This
representation is interesting for its ability to use a dissimilarity measure to embed various patterns (e.g. graphpatterns with diﬀerent topology and temporal patterns with diﬀerent lengths) into a vector space. The method
proposed in this paper uses a dynamic time warping (DTW) based DSE for the purpose of the classiﬁcation ofmassive sets of temporal patterns. However, using large data sets introduces the problem of requiring a highcomputational cost. To address this, we consider a prototype selection approach. A vector space created by DSE
oﬀers us the ability to treat its independent dimensions as features allowing for the use of feature selection. The
proposed method exploits this and reduces the number of prototypes required for accurate classiﬁcation. To
validate the proposed method we use two-class classiﬁcation on a data set of handwritten on-line numerical
digits. We show that by using DSE with ensemble classiﬁcation, high accuracy classiﬁcation is possible with very
few prototypes.

1. Introduction
An important issue in pattern recognition is the method in which
the data is represented. Using a representation that best describes thedata or that captures the discriminating features is one of the mostimportant factors in a successful machine learning model [1]. For thatreason, much research is dedicated to the preprocessing, featuredesign, and transformation of data [2,3]. In general, there are two
major approaches to this problem, statistical and structural. A statistical approach uses feature vectors as basic representation formalism,
while the latter employs symbolic data structures (e.g. strings, trees, orgraphs). Whether we use feature vectors or symbolic data structures forpattern representation, the goal is to ﬁnd a good representation of thedata with the foundation to support machine learning.
Dissimilarity representation is a novel approach in pattern recognition [4] in which the data is represented as the diﬀerence, ordissimilarity, to other objects or patterns. Instead of using a pattern's
features, data representation is done based on the patterns relations toother patterns. In this manner, we represent the data as vectors ofdissimilarities rather than feature vectors and are able to embed thedissimilarity representation into vector space, or dissimilarity space⁎embedding (DSE). The intuition of this approach is the notion that
distance between patterns of similar categories is smaller than patternsof diﬀerent categories. This fundamental view of patterns as distances
also grants the to use complex patterns, like symbolic data structures,with the mathematical and machine learning foundation of vector
space [5]. By embedding the patterns into dissimilarity space, we canbridge the gap between complex pattern recognition and feature vector
recognition.
This paper speciﬁcally tackles temporal pattern recognition.
Temporal patterns present an aforementioned complex pattern due
to the interconnectivity and dependency on sequence order. Also, whenlearning temporal patterns, temporal distortions and length variations
must be considered. These obstacles are not addressed by classicalﬁxed-dimensional Euclidean pattern recognition. Rather than using acomplex model to represent temporal patterns, we can accuracy
represent them using DSE and still use the tools granted by vector
space. To accomplish this, we embed the temporal patterns into adissimilarity space by using dynamic time warping (DTW) as adissimilarity measure. DSE is an N-dimensional feature vector who
elements are the DTW distance between prototype patterns and sample
patterns. The N-dimensional space is now dimensionally ﬁxed to theCorresponding author at: Department of Advanced Information Technology, Kyushu University, Fukuoka, Japan.
E-mail addresses: brian@human.ait.kyushu-u.ac.jp (B.K. Iwana), kaspar.riesen@fhnw.ch (K. Riesen), uchida@ait.kyushu-u.ac.jp (S. Uchida).

http://dx.doi.org/10.1016/j.patcog.2016.11.013
Received 9 January 2016; Received in revised form 17 September 2016; Accepted 16 November 2016
Available online 21 November 20160031-3203/ © 2016 Elsevier Ltd. All rights reserved.

Pattern Recognition 64 (2017) 268–276

B.K. Iwana et al.

There are many aspects and types of prototype selection methods, but
in general, the mechanism for selecting prototypes can be broken down
into three main categories [16]. The condensation methods ﬁnd thepoints close to the decision boundaries and remove the internal points.
The purpose of this method is to save the classiﬁer's accuracy, butremove the redundancy. Edition methods attempt to reduce the noise
by removing prototypes near decision boundaries which conﬂict with
its surroundings. Finally, hybrid methods combine the two previous
methods.

number of prototypes N and can be used for the analysis of temporal
patterns.
Recently, it has been a trend in pattern recognition that byincreasing the data set size, a higher accuracy could be achieved.
Banko and Brill [6] demonstrated that for natural language processing,
the number of words was more important than the complexity of theclassiﬁer. The work of 80 million tiny images [7] has shown that evenwith a simple nearest neighbor classiﬁcation performs suﬃciently witha massive number of image patterns. Similar trials with massive
patterns has been made for image segmentation [8], video image
recognition [9,10], and handwritten character images [11], proving thevalue of using massive pattern numbers. Therefore, intuitively, toexploit DSE to its potential, we need to use large data.
However, by increasing the size of the data set, you also increase thecomputational requirement. When using massive pattern numbers, you can
encounter the problem of having a huge computational requirement.
Typically, there are three primary ways to address this issue: reducing
the size of the patterns or features, using eﬃcient search schemes, andselecting meaningful patterns. Tiny images [7] and tiny videos [9] overcome
the computational requirement by reducing the image resolution. Other
solutions include creating low-dimensional representations via feature
selection [12,13]. Another solution to the computational problem is touse optimized search schemes such as estimation, approximate nearest
neighbor [14], and vocabulary tree search [15]. A third solution is to select
only the meaningful patterns or prototypes useful for the classiﬁer. Classicalmethods include prototype selection, edition, and condensation [16].
Besides the problem of computational time when using a massive
data set and a large set of prototypes, we are also creating a highdimensional vector space that is subject to the curse of dimensionality[17]. Therefore, we need to reduce the dimensionality of the DSE.
AdaBoost oﬀers two advantages for this purpose: (1) building a strong
ensemble classiﬁer from weak learners and (2) being used for selecting
discriminative features when each weak learner depends on single
features [18]. To solve the computational challenge, we apply AdaBoost
to select the meaningful features and in this the case of DSE, prototypes
as references to dissimilarities to samples. The end result is a novel,
optimized prototype selector scheme for DSE.
The contribution of this paper is to address the massive patternrecognition of temporal patterns. Firstly, we embed temporal patterns
into a vector space using a DTW-based dissimilarity measure. This
allows us to represent temporal patterns as vectors of dissimilarities toprototypes. Secondly, we develop a new method of prototype selection
by using AdaBoost as a feature selector for the resulting DSE. We canincrease the computational eﬃciency by only using the prototypes
within the ensemble classiﬁer created by AdaBoost. Finally, we showthat the accuracy of the classiﬁer constructed by AdaBoost can be
improved by preparing the prototype pool with patterns of classes
external to a two-class classiﬁcation.
The remaining of this paper is organized as follows. Section 2
reviews the related work in prototype selection and DSE. Section 3
elaborates on dissimilarity representation and the relation to vector
space embedding. Section 4 provides a more detailed description of themethod proposed. In Section 5, we conﬁrm that the proposed methodand discuss the usability of patterns of classes external to the two-classclassiﬁer. Finally, Section 6 draws a conclusion and describes futurework.

2.2. Dissimilarity representation
Dissimilarity representation is a fast growing ﬁeld [19]. There havebeen many recent publications which concern diﬀerent aspects ofdissimilarity based pattern recognition [20–23] as well as extrapolating
dissimilarity representation to graphs [24], string based object representation [25], and signature veriﬁcation [26,27].
There have also been attempts to increase the eﬃciency ofclassiﬁcation and the applications to diﬀerent patterns. Pekalska
et al. [28] proposed using normal density-based classiﬁers in DSE to
overcome the limitations of k-NN methods. Pekalska et al. [29] also
analyzed prototype selection techniques, such as mode seeking, kCenters, an editing and condensing algorithm, linear programming,and feature selection, within DSE. Riesen and Bunke [30] also used
prototype clustering in addition to prototype selection techniques on
dissimilarity based graph classiﬁcation. Other trials for prototype
selection in DSE include using genetic algorithms [31] and using it
for the application of signature veriﬁcation [32].
3. Dissimilarity space embedding
Instead of characterizing patterns by its features, it is possible torepresent patterns as dissimilarities to other patterns [4]. This dissimilarity representation measures the distance between patterns with theconsideration that patterns of the same class are more likely to be
similar than patters of a diﬀerent class. Due to variations of patterns,
there exist instances where a category of patterns does not share acommon feature, but it is still possible to classify the patterns based on
the distance to a prototype [33]. By using the distance measure
between patterns as features, we can emphasize the fundamental
relationship between patterns and de-emphasize the features of thepatterns. Dissimilarity representation allows for the embedding of
information on how the patterns exist on the system as a whole.
Using this dissimilarity representation, we can take a vector spaceembedding approach by representing the data as vectors of dissimilarities. An N-dimensional vector space is created from the dissimilarities between each prototype p in P and each sample s in S based ona distance measure d (p, s). As illustrated in Fig. 1, the key idea is toselect N number prototypes P and represent any sample as a vector vs
whose entries are the distances

vs = (d (p1, s), d (p2 , s),..., d (pN , s))T .

(1)

2. Related works
In this section, we will brieﬂy discuss prototype selection andprovide the previous works related to DSE.
2.1. Prototype selection
Fig. 1. A visualization of embedding a sample s into an N-dimensional vector space
using the dissimilarities to prototypes p1, …, pN . vs is the vector whose entries are the

The goal of prototype selection is to reduce an initial set of
prototypes to a subset while retaining as much information as possible.

distances to the respective prototypes.

269

Pattern Recognition 64 (2017) 268–276

B.K. Iwana et al.

Fig. 3. An example of a DTW calculation. (left) Two superimposed sample patterns. The
yellow connections are the optimized matches between the elements in a , the blue square
markers, and the elements in b , the green circle markers. The length of the connections
are the distances between matched elements. (right) An rendering of the cost matrix
between the patterns over time. The values are determined by the local distance between
every element where dark areas as low cost and light areas as high cost. The central
yellow line represents the warping path determined by DTW. (For interpretation of thereferences to color in this ﬁgure legend, the reader is referred to the web version of thisarticle).

Fig. 2. Diagram outlining the proposed method. The training consists of creating a DSE
with a DTW-based distance measure and learning with AdaBoost. The resulting ensemble
classiﬁer and prototype subset are carried to the testing phase.

The resulting DSE preserves some of the characteristics of the underlying patterns.
DSE was originally proposed for dissimilarities directly computed
between objects [4], but the distance measure is not limited Euclideanfeature vectors and can be used on patterns not endowed withmathematically well deﬁned operations such as graphs [30] andsequences [34]. The embedding into this vector space, allows us to
use the full potential of existing algorithms that work on vectors but on
additional data types.

dDTW(a , b) = D(I , J ) = ∑ c(ai , bq ).
bq ∈ Q

The asymmetric slope constraint of Eq. (2) aligns matching features
so that the path of the distance measure is monotonic and that the
number of matches is always equal to I, the length of each sequence a .
The ﬁxed length of a and varying length of b allows for the DTW to be
calculated without consideration of the normalization of pattern sizes
and variable rates, while the monotonicity maintains elastic matchingcontinuity. These characteristics allow for a desirable dissimilarity
measure for non-uniform temporal patterns.
We embed temporal patterns into a vector space, in the manner
described by Eq. (1), by using the DTW-distance dDTW as the dissimilarity measure. The resulting dissimilarity space for each sample sm is
now represented as a feature vector,

4. Prototype selection with AdaBoost in DSE
The proposed method for prototype selection of temporal patterns,
as illustrated in Fig. 2, consists of two primary steps. First, we create an|P|-dimensional DSE with a DTW-based distance measure. Next, weapply AdaBoost to discriminatingly select the relevant prototypes. In
doing so, we select a subspace of the original DSE to those prototypes
used in the ﬁnal ensemble classiﬁer created by AdaBoost by preserving
the dimensions associated with the selected prototypes.

vsm = (dDTW(p1, sm), dDTW(p2 , sm), …, dDTW(pN , sm))T ,Embedding into vector space requires a distance measure that
returns a value that represents the dissimilarity between patterns. To
accurately portray the dissimilarities, the chosen distance measure
should be an eﬀective measurement for the patterns.
DTW is a popular dynamic programming algorithm of ﬁnding the
optimal alignment and measuring the distance between temporal
patterns. Given two sequences a = a1, …, ai , …, aI of length I, andb = b1, …, bj , …, bJ of length J, where ai and bj are elements with awell-deﬁned distance measure, such as coordinates or vectors, DTW
computes the optimal matching of sequence elements given constraints. The goal is to determine the optimal match between pairwise
elements so that the global distance is minimized. This can be seen in
Fig. 3, which illustrates a sample DTW-distance calculation and the
optimal matches as determined by the warping path from DTW.
There are several diﬀerent constraints to which sequence elements
must conform in the literature. Our method uses the asymmetric slope
constraint given bymin

D(i − 1, j′)j ′∈{j, j −1, j −2}(4)where each feature is the DTW-distance to each prototype
p1, p2 , …, pN . The DTW-distance measure allows the embedding of
patterns of varying sizes into a ﬁxed N-dimensional vector space.

4.1. DTW-based distance measure

D(i , j ) = c(ai , bj ) +(3)

4.2. Prototype selection with AdaBoost
The AdaBoost algorithm, described in Algorithm 1, is a machinelearning algorithm that combines a set of weak learners to create anonlinear ensemble classiﬁer [35]. The algorithm performs by iterating
through many rounds of weighted weak learners and combines theminto a single strong classiﬁer after a desired low training error has beenreached [35,36]. During each round of AdaBoost, the weak learners isapplied with cumulative weights emphasizing the incorrect patterns
and deemphasizing the correct classiﬁcations from the previous
rounds. The weak learners typically consist of fast, inaccurate, or linear
classiﬁers with the only requirement of being a better than chanceclassiﬁer. The ﬁnal ensemble classiﬁer combines the weak learners
using a weighted vote allowing for the adaptation to diﬃcult andnonlinear data sets.

(2)
Algorithm 1. AdaBoost algorithm.
If we deﬁne the weak component learner to be linear classiﬁers
based on a single feature, the decision boundaries are dependent on
single dimensional axes. By representing the dissimilarities between
prototypes and samples in vector space as features, each axis isdetermined by a prototype. Each prototype-axis has a potential weaklearner to be selected by AdaBoost. This consideration allows AdaBoost

over the cost matrix c(ai , bj ) where c is the Euclidean distance between
the points at i and j of sequences a and b respectively. The DTW
algorithm estimates the optimal distance on the cost matrix between
the D(0, 0) and D(I , J ), therefore, the DTW-distance is determined by
the value at D(I , J ). In other words, where Q is the set of all matchedelements of b with respective elements in a , the DTW-distance isdeﬁned as
270

Pattern Recognition 64 (2017) 268–276

B.K. Iwana et al.

1: function AdaBoost
2: Training set {(s1, l1), …, (sm , l m), …, (sM , lM )}selected subset of prototype-axis classiﬁers and conﬁdence values used
to calculate the ﬁnal classiﬁer.
AdaBoost provides the ability to discriminately select prototypes aswell as oﬀering us a powerful nonlinear classiﬁer. With ability to reducethe dimensionality of independent dimensions, we can overcome thechallenges of computationally costly classiﬁers, such as k-NN and
Support Vector Machines (SVM), of related DSE works. Combined withbeing able to learn very complex decision boundaries, AdaBoost is an
ideal classiﬁer for DSE.

1

3: Initialize weights: W1(m ) ← M for m = 1, …, M
4: for k = 1, …, kmax do
5: Train weak learner using Wk(m ).
6: Select classiﬁer with the lowest error:hk (s) ← argminϵn = |{(s, 1) ∈ T |wk (m ){s ≠ 1}}|hn

7:Calculate conﬁdence:1 ⎛1 − ϵ ⎞αk ← 2 ln⎜ ϵ k ⎟⎝ k ⎠8:Update weights:⎧ e−αk , if hk (sm) = lm
Wk +1(m ) ← Wk(m ) × ⎨ α⎩ e k , otherwise
9: Normalize
Wk+1(m ) such that ∑m Wk+1(m′) = 1′
10: end for
11: return composite classiﬁer:

4.3. Preparation of the initial prototype set
The assumption of using dissimilarities in two-class classiﬁcation isthat patterns can be grouped into classes based on their similarity tothe prototypes. Thus, for a two-class classiﬁcation problem, it is naturalto prepare the sets by using patterns from those two classes. Usually,
this indicates that patterns more similar to the prototype are membersof the prototype's class and patterns that are less similar belong to thecompared class. We start by preparing the initial prototype set withpatterns of class A and class B. However, note that the selected
prototypes might not be balanced; prototypes of one class may be
selected over the other class. In the most extreme case, all of theselected prototypes would be of a single class.
Although, DSE only requires the dissimilarity representation toshow a separation of the two classes for accurate classiﬁcation. It does
not necessarily need to know the class membership of the prototypes.
Based on this idea, it is possible that in two-class classiﬁcation, there
exist prototypes of a third, external class that is more discriminative
than the pairwise classes. Fig. 5 demonstrates an example where theprototype-axis of external class C has a higher distinction in thedissimilarities of the samples than the pairwise classes that are being
compared.

k

H (s) ← sign(∑kmax
α h (s))=1 k k12: end functiond(pN, S )d(p2, S )5. Experimental results
5.1. Data set

d(p1, S )The UNIPEN on-line handwritten digit data set was used for theexperiment. The data set is provided by the International Unipen
Foundation (iUF). The iUF provides benchmark data sets for writer
identiﬁcation and handwriting recognition [37]. The data set used forthe experiment consists of about 15,000 time ordered sets of coordinates split into ten digit classes. Real on-line handwritten numerical
digits is an ideal source of data for temporal pattern classiﬁcation
because of the numerous variations of patterns while maintaining
distinct categories.
For the experiment, we used a two-class classiﬁer comparing toindividual classes and repeated the experiment for all possible combinations of classes. While the two-class classiﬁer employed by AdaBoost
can be extended by using a 1-vs-other classiﬁcation or a multi-class
AdaBoost, we adhere to the use of the two-class classiﬁcation to better
analyze the experimental results. This also allows the experiment todetermine the eﬀects proposed by Section 4.3, namely, the inclusion of
prototypes of classes not found in the two compared classes.
The data set was divided into three subsets, an initial prototype set,a training set, and a test set. Each prototype set was made of 130
patterns of each class. The size of each test set was deﬁned at 260
patterns. Finally, the training sets for the dissimilarity space embedding and AdaBoost contained 2080 patterns. This process was repeatedfor both experiments using the same partitions of the data set for 9-foldcross-validation.1

Fig. 4. A visualization of AdaBoost applied to a dissimilarity space. The points represent
samples in the N-dimensional space of two classes, white and black. The mid-lines depict
weak learners based on each of the prototype dissimilarity-based axis with the shaded
areas representing a classiﬁcation of black. Only classiﬁers for the dissimilarity-based
axes of p1 and p2 are shown. The eventual end ensemble classiﬁer would be a weighted
vote based on all dimensions of the DSE that are chosen by AdaBoost.

to be used as a discriminative prototype selector due to its ability tochoose a subset of classiﬁers to build its ensemble classiﬁer. This is only
possible if the weak learner is dependent on a single feature. If the
weak learner uses all features, AdaBoost cannot be used in this manner.
Unlike exhaustive classiﬁcation methods, only prototypes useful to
AdaBoost need to be calculated and irrelevant prototypes can bediscarded. This ability to select features, or dissimilarities to prototypes, allows AdaBoost to reduce the dimensionality of DSE and thecomputational requirement of classifying massive data sets that would
typically require large amounts of prototypes.
To compare each of the two classes in the ensemble classiﬁer
training, we use a nearest prototype classiﬁer as the weak learner inLine 5 of Algorithm 1 within the DTW-based DSE created from vs m(pn).
The weights of the classiﬁers, as determined by AdaBoost, are applied
to the samples of each prototype-axis within the DSE. Within eachround of AdaBoost, the classiﬁer with the lowest error in Line 5 ofAlgorithm 1 is selected as the basis of the weight updates for thesubsequent round. Fig. 4 illustrates the application of AdaBoost on adissimilarity space. The resulting training produces a discriminatively

19-fold cross-validation was used because the data set was split into 10 sets: 8 sets fortraining patterns, and two left out, 1 for test patterns and 1 for prototype patterns.

271

Pattern Recognition 64 (2017) 268–276

B.K. Iwana et al.

Class BClass CClass A

Fig. 5. This ﬁgure shows an idealized example of an external class, Class C, performing better than any pattern in within the pairwise classiﬁcation of Class A and Class B. The rings
represent decision boundaries for a classiﬁer based on the distance to the respective centers.

5.2. Evaluation of the proposed method

Table 1
A table comparing the evaluated methods and methods from literature in recognition
rate, data set size required at execution, and average per digit classification time.

In this section, we evaluate the viability of two-class classiﬁcation in
DSE with AdaBoost in accuracy and eﬃciency. We consider thefollowing ﬁve evaluations:• Proposed Method: The test sample set is classiﬁed using the strong
•

•
•
•

ensemble classiﬁer that is constructed by AdaBoost in DSE. This
serves as the evaluation of the proposed method when using
prototypes of classes within the pairwise classes.
Proposed Method+External Classes: Similar to the Proposed
Method, this evaluation uses the strong ensemble classiﬁer constructed by AdaBoost in DSE. Unlike the Proposed Method, theinitial prototype set of this method was prepared with prototypes ofany of the ten possible classes. The extra patterns for the externalclasses were taken from the unused prototypes that would normallybe left out for two-class classiﬁcation. There is an equal representation of every class in the initial prototype set.
DSE Random: DSE using randomly selected prototypes equal to thenumber of prototypes selected by Proposed Method and the samenearest prototype classiﬁer used in the proposed methods.
DSE k-Centers: k-Centers selects prototypes in a manner that the
prototypes are evenly distributed, as described in [30]. The prototypes are selected through a k-medians clustering method. Like DSE
Random, classiﬁcation is done in a DSE created from the selected
prototypes and with the same classiﬁer as Proposed Method.
Simple 1-NN: To serve as the baseline evaluation of classic non-DSE
space, random prototypes were used with a 1-NN method based on
the DTW-distance between prototypes and test samples. The
number of prototypes selected was exactly equal to the number ofprototypes selected by Proposed Method.

Evaluation

Recognition rate

Data set size

Per digit
time

Proposed Method
Proposed Method+External
Classes
Simple 1-NN
DSE Random
DSE k-Centers
Full Training Set 1NN
DAG-SVM-GDTW[38]Interpolation Kernel[39]

95.15 ± 5.74%
96.67 ± 4.38%

13.25 ± 6.02 prototypes
14.66 ± 6.97 prototypes

0.088 s0.094 s86.94 ± 17.2%
83.19 ± 7.89%
80.75 ± 7.54%
99.03 ± 0.92%

Same as Proposed Method
Same as Proposed Method
Same as Proposed Method
90% training set

0.120 s0.092 s0.090 s14.33 s96.2%

40% training set

–

97.1

50% training set–

increase in accuracy compared to 1-NN with comparatively reduced
prototypes. As shown in Table 1, averaging all two-class classiﬁcations
across all folds of cross-validation, AdaBoost in DSE achieves a95.15 ± 5.74% accuracy after 200 rounds while Simple 1-NN withrandomly selected prototypes of the same amount has a lower accuracyof 86.94 ± 17.2%. Where 1-NN in feature space is highly dependent on
the prototype set has a low tolerance to noise [40], the weak learners
selected by AdaBoost in DSE tend to have high accuracies due to theweighted error minimization of the selection process. This high

These evaluations are done considering the eﬀectiveness of the
proposed method to reduce the number of prototypes. With exception
to Proposed Method+External Classes, the evaluations use a number ofprototypes equal to the Proposed Method. The accuracies are calculated by averaging all folds and the computational time cost isdetermined on a system with a Intel Xeon E5 2.6 GHz processor.
In addition, we compare our method to other two-class classiﬁcation methods without considering prototype reduction. This includes
using 1-NN with the entire training set as prototypes (Full Training Set
1-NN), using a Support Vector Machine with a DTW based kernel(DAG-SVM-GDTW) [38], and representing each time-series as a sumof piecewise polynomial basis functions through a kernel interpolation(Interpolation Kernel) [39]. The computational time cost of Full
Training Set 1-NN is done on the same system as the previous
methods. The other comparisons were reported using the same handwritten digits from the UNIPEN data set using a reduced training set
size for speed purposes.

Fig. 6. The average recognition accuracy for 45 class pairs over 9 folds between the DSEwith AdaBoost method (Proposed Method and Proposed Method+External Classes), theDSE baseline methods using prototypes selected randomly (DSE Random) and prototypes selected through k-medians clustering (DSE k-Centers), and 1-NN with randomly
selected prototypes (Simple 1-NN).

5.2.1. Analysis of proposed method
The proposed method of using AdaBoost in DSE has a large272

Pattern Recognition 64 (2017) 268–276

B.K. Iwana et al.

Fig. 7. The unique prototype patterns selected by AdaBoost between class “0” and class “6” when limited to the compared classes (Proposed Method), in order of selection (top-left tobottom-right).

accuracy of the weak learners provides a high overall accuracy of theensemble classiﬁer, even in the initial rounds.
When compared to DSE Random and DSE k-Centers, Proposed
Method had a much higher accuracy using the same number ofprototypes. DSE Random and DSE k-Centers both had the lower
accuracy of 83.19 ± 7.89% and 80.75 ± 7.54% respectively. The accuracy
improvement is due to the nonlinear ability of the ensemble classiﬁer in
addition to the weak learner error minimization. Fig. 6 also shows thatthe simple clustering of prototypes does not necessarily improveclassiﬁcation of dissimilarity space. The overﬁtting in Fig. 6 from the
DSE k-Centers evaluation is due to prototypes from outlier clusters
being selected and having a negative impact on the accuracy.
An example of an improvement of DSE with AdaBoost is the case of
the comparison between class “0” and class “6.” This example reveals
which patterns the AdaBoost algorithm judged as the best prototypes
for the classiﬁer as well as the progression to the prototypes it thought
were more diﬃcult but still beneﬁcial to the ensemble classiﬁer, as
shown in Fig. 7. The selected patterns are visually and intuitively
closely representative to their ground truth classes and distant fromtheir opposing classes. The improvement in the abilities to distinguishclasses provided by AdaBoost in DSE can be seen in Figs. 8 (a) and (b).
Compared to the randomly selected prototypes of Fig. 8 (a), the DSE
created by the prototypes selected by AdaBoost have much less noise
and a better distinction between classes.
In addition, Fig. 6 shows a quick convergence in accuracy from the
Proposed Method when compared to the baselines. Freund andSchapire [41] proved that the error of the ﬁnal classiﬁer drops

Fig. 9. A comparison of the reduction in prototypes between limiting the selection of
prototypes to the pairwise classes (Proposed Method) and including external classes(Proposed Method+External Classes). The graph indicates the average number of uniqueprototypes selected by Adaboost over the number of rounds of weak learner decisions.

after the initial rounds, AdaBoost tends to repeat the use of previously
selected weak learners. The initial weak learners are selected for theirability for separating the general patterns, but as the weights of thediﬃcult patterns get emphasized, the latter iterations are selected fortheir ability with the outliers and noise. This caused the prototype
selection process to become cyclic in that the algorithm will compensate the weights for the diﬃcult patterns only to change it back foreither other diﬃcult patterns or the general patterns. The repeated useof past prototypes reduced the original prototype set of 260 patterns

2

exponentially and is bounded by e−2t (1/2−ϵk) , where k is the roundnumber and ϵk is the error of the kth learner. AdaBoost has been also
shown to be resilient to overﬁtting [42–44] which is consistent with theobservations from the experiment.
A convergence was not only observed in the accuracy but the
prototypes selected by AdaBoost, as shown in Fig. 9. We found that

Fig. 8. An example of two prototypes in DSE comparing Class “0” (red) and Class “6” (blue). (a) shows the ﬁrst two prototypes selected by DSE Random, (b) shows the ﬁrst two
prototypes selected by Proposed Method, and (c) shows the ﬁrst two prototypes selected by Proposed Method+External Classes. (For interpretation of the references to color in thisﬁgure legend, the reader is referred to the web version of this article).

273

Pattern Recognition 64 (2017) 268–276

B.K. Iwana et al.

Fig. 10. A box plot of the pairwise classiﬁcations across all folds with the top and bottom of the boxes as the third and ﬁrst quantile respectively. The Proposed Method and Proposed
Method+External Classes boxes represent the error rates. The External class usage boxes are calculated by NE /NT where NE is the number of unique prototypes that belong an externalclass and NT is the total number of unique prototypes used to build the strong classiﬁer. Note, the External Class Usage boxes are scaled for the visualization. This shows relationshipbetween the frequency at which external prototypes were selected and the accuracies of the proposed methods.

Case 1: An increase in choices of similar shapes. In general,a good classiﬁer would expect the distance between samples in thesame class to be smaller than the samples from a diﬀerent class [36].
Intuitively, by increasing the pool of prototypes, AdaBoost will be able
to ﬁnd those prototypes which are more similar to one class than thecomparison class. Because only the shape and not the class membership of the prototypes is taken into consideration, its possible for there
to be prototypes of an external class to resemble one of the two classes
in question. An example of this would be in the comparison of class “0”and class “6′ in Fig. 11, the digits which have the ground truth of ”4″
are visually similar to be number “6”s.' These prototypes were selected
because their similarity to class “6” greatly exceeds their dissimilarity
to class “0.”Case 2: A better separation in dissimilarity between thetest classes despite being diﬀerent to both. In contrast to
Example 1, there are instances where there are few successfulclassiﬁers within the two classes being compared. This means that
there exist patterns that are dissimilar to both classes, but are selected
because they are more dissimilar to one class than the other. The DSEof these external class prototypes can provide a higher distinction
between the compared classes better than the compared classes canthemselves. The comparison of class “5” and class “8” is a good exampleof this phenomenon. The unique selected prototypes are shown in
Fig. 13 and a comparison of the dissimilarity representation of the ﬁrst
two prototypes selected by AdaBoost with and without external classes
can be seen in Fig. 12. From Fig. 12 (a) and (b), it is observed that class“5” makes poor linear classiﬁers due to the large diﬀerence in writing
styles . Likewise, class “8” has a high variation in styles causing forinconsistent classiﬁer performance. However, from the viewpoint ofclass “0,” both classes in question are dissimilar, but class “5” is evenmore dissimilar than class “8.”per classiﬁcation to an average of 13.25 ± 6.02 prototypes after 200
rounds.
The 94.90% reduction in prototypes results in a much faster testclassiﬁcation time due to the dramatic reduction in required DTW
calculations. Using an Intel Xeon E5 2.6 GHz processor, the Proposed
Method had an average time cost of 0.088 s for every classiﬁcation,
which includes repeating the DTW calculations for each prototype inthe ensemble classiﬁer. In comparison, Full Training Set 1-NN had an
average time cost of 14.33 s for every classiﬁcation due to requiring a
DTW calculation with each training prototype. While the accuracy of
Full Training Set 1-NN is the highest of all compared methods, a timeof 14.33 s is unsuitable for real-time applications and larger data sets.
However, the results of the proposed method conﬁrm that a high levelof accuracy can be maintained even after reducing the number ofprototypes signiﬁcantly. It is important to note that while the accuracy
stabilizes quickly, 200 rounds were calculated to give the prototype
selection process to stabilize.

5.2.2. Analysis of proposed method+external classes
To evaluate the eﬀectiveness of including prototypes of classes
external to the two-class classiﬁcation, the proposed method is
expanded to allow the selection of prototypes of any class. The additionof prototypes of external classes to the pairwise classiﬁcation increased
the accuracy of the ensemble classiﬁer constructed by AdaBoost. The
results in Table 1 show an improvement with the previous results of an
average of 95.15 ± 5.74% after 200 rounds in Section 5.2 increased to
96.67 ± 4.38%. As portrayed in Fig. 9, the total number of uniqueprototypes used for the ensemble classiﬁer slightly increased from
13.25 ± 6.02 to 14.66 ± 6.97 and takes an average of 0.094 s for everyclassiﬁcation with an Intel Xeon E5 2.6 GHz processor. Overall, there
was a signiﬁcant increase in accuracy and only a nominal increase in
number of prototypes and computational time.
The distribution of percentages of external class prototypes selected
by AdaBoost for each pairwise classiﬁcation, shown in Fig. 10, reveals
that using the additional external class prototypes is common, especially when the ensemble classiﬁer failed to achieve a high accuracy
before they were included. Generally, for the more diﬃcult classiﬁcations of Proposed Method, AdaBoost selected more prototypes of theexternal classes during Proposed Method+External Classes. A large
performance gain is seen on the initially diﬃcult classiﬁcations when alarge percentage of external class prototypes were introduced. Only
rarely were the external class prototypes a detriment to the classiﬁcation. It can be inferred that the class is not an important factor in
selecting prototypes, but the shape of the pattern.
Two example cases of this include:

6. Conclusion
In this paper, we presented a method of temporal pattern recognition by transforming the data into a vector space by means ofdissimilarity embedding. Using AdaBoost for the purpose of prototype
selection in the DTW-distance vector space proved to be a viable
method of pattern classiﬁcation. The experiment performed on a
portion of the UNIPEN on-line handwriting data set. It was able tomaintain an average accuracy of 95.15 ± 5.74% for two-class classiﬁers
over 9-fold validation. We were able to increase the accuracy to an
average of 96.67 ± 4.38% by introducing prototypes of classes external
to the two-class classiﬁers into the initial prototype set. The number ofprototypes were reduced to an average of 13.25 ± 6.02 for Proposed274

Pattern Recognition 64 (2017) 268–276

B.K. Iwana et al.

Fig. 11. The unique prototype patterns selected by AdaBoost between class “0” and class “6” when allowed to choose any class (Proposed Method+External Classes), in order of
selection (top-left to bottom-right). The boxed patterns are instances of AdaBoost supplementing the selection with prototypes of external classes.

Fig. 12. An example of two prototypes in DSE comparing Class “5” (red) and Class “8” (blue). (a) shows the ﬁrst two prototypes selected by DSE Random, (b) shows the ﬁrst two
prototypes selected by Proposed Method, and (c) shows the ﬁrst two prototypes selected by Proposed Method+External Classes. (For interpretation of the references to color in thisﬁgure legend, the reader is referred to the web version of this article).

Fig. 13. The unique prototype patterns selected by AdaBoost between class “5” and class “8” when allowed to choose any class (Proposed Method+External Classes), in order of
selection (top-left to bottom-right). The boxed patterns are instances of AdaBoost supplementing the selection with prototypes of external classes.

Conﬂict of interest

Method and 14.66 ± 6.97 for Proposed Method+External Classes. The
experiment demonstrates:

None declared.

• AdaBoost can be used as an eﬀective prototype selection method in••

References

DSE. Temporal patterns with a DTW-based distance measure can beclassiﬁed with a high accuracy and low prototype count by using thestrong classiﬁer constructed by AdaBoost. Compared to exhaustive
methods such as 1-NN, it is possible to reduce the computational
requirement by using an ensemble classiﬁer comprised of fast weaklearners with a very small number of prototypes.
The overall performance of AdaBoost in DSE can be improved byintroducing classes external to the two-class classiﬁer while maintaining a substantial decrease in prototypes.
There exist patterns that are more similar to one class than anotherclass but do not necessarily belong to either. Some of these patterns
from third classes can distinguish between the two classes better
than patterns from the two classes themselves.

[1] P. Domingos, A few useful things to know about machine learning, Commun. ACM
55 (10) (2012) 78–87. http://dx.doi.org/10.1145/2347736.2347755.
[2] H. Liu, H. Motoda, Feature Extraction, Construction and Selection: A Data Mining
Perspective, Kluwer Academic Publishers, Norwell, MA, USA, 1998. http://dx.doi.org/10.1016/s0898-1221(99)90021-4.
[3] J. Han, M. Kamber, J. Pei, Data Mining: Concepts and Techniques. 〈http://dx.doi.
org/10.1145/565117.565130〉.
[4] E. Pekalska, R.P. Duin, The Dissimilarity Representation for Pattern Recognition:
Foundations and Applications, World Scientiﬁc, Singapore, 2005. http://dx.doi.org/10.1142/9789812703170.
[5] R.P. Duin, E. Pkalska, The dissimilarity representation for structural patternrecognition, in: Progress in Pattern Recognition, Image Analysis, Computer Vision,and Applications, Springer, 2011, pp. 1–24. 〈http://dx.doi.org/10.1007/978-3642-25085-9_1〉.
[6] M. Banko, E. Brill, Scaling to very very large corpora for natural language
disambiguation, in: Proceedings of the 39th Annual Meeting on Association for
Computational Linguistics, Association for Computational Linguistics, 2001, pp.
26–33. 〈http://dx.doi.org/10.3115/1073012.1073017〉.
[7] A. Torralba, R. Fergus, W.T. Freeman, 80 million tiny images: a large data set for
nonparametric object and scene recognition, IEEE Trans. Pattern Anal. Mach.
Intell. 30 (11) (2008) 1958–1970. http://dx.doi.org/10.1109/tpami.2008.128.
[8] C. Liu, J. Yuen, A. Torralba, Nonparametric scene parsing via label transfer, IEEE
Trans. Pattern Anal. Mach. Intell. 33 (12) (2011) 2368–2382. http://dx.doi.org/
10.1109/tpami.2011.131.
[9] A. Karpenko, P. Aarabi, Tiny videos: a large data set for nonparamet495-ric video
retrieval and frame classiﬁcation, IEEE Trans. Pattern Anal. Mach. Intell. 33 (3)(2011) 618–630. http://dx.doi.org/10.1109/tpami.2010.118.

In the future, we hope to expand the ability of pattern recognition in
DSE to other data sets and applications as well as explore thecharacteristics of temporal patterns in DSE. The large reduction incomputational requirement opens DSE to be used with massive data
sets and real time applications. Also, because the proposed method
demonstrates the usefulness of shape over class membership, future
work can be done by using DSE with generated, classless, andunlabeled prototypes. Optimized prototypes can lead to more eﬃcientand accurate dissimilarity representation.
275

Pattern Recognition 64 (2017) 268–276

B.K. Iwana et al.

in: Structural, Syntactic, and Statistical Pattern Recognition, Springer, 2014, pp.
343–352. 〈http://dx.doi.org/10.1007/978-3-662-44415-3_35〉.
[32] G.S. Eskander, R. Sabourin, E. Granger, On the dissimilarity representation andprototype selection for signature-based bio-cryptographic systems, in: SimilarityBased Pattern Recognition, Springer, 2013, pp. 265–280. 〈http://dx.doi.org/10.
1007/978-3-642-39140-8_18〉.
[33] S.K. Reed, Pattern recognition and categorization, Cogn. Psychol. 3 (3) (1972)
382–407. http://dx.doi.org/10.1016/0010-0285(72)90014-x.
[34] B. Iwana, S. Uchida, K. Riesen, V. Frinken, Tackling temporal pattern recognitionby vector space embedding, in: Proceedings of the 2015 13th International
Conference on Document Analysis and Recognition (ICDAR), 2015, pp. 816–820.
〈http://dx.doi.org/10.1109/icdar.2015.7333875〉.
[35] Y. Freund, R.E. Schapire, A decision-theoretic generalization of on-line learningand an application to boosting, J. Comput. Syst. Sci. 55 (1) (1997) 119–139. http://dx.doi.org/10.1006/jcss.1997.1504.
[36] R.O. Duda, P.E. Hart, D.G. Stork, Pattern Classif. (2012). http://dx.doi.org/
10.1007/s00357-007-0015-9.
[37] International Unipen Foundation, International Unipen Foundation –iUF. 〈http://
www.unipen.org/home.html〉 (accessed 19.10.15).
[38] C. Bahlmann, B. Haasdonk, H. Burkhardt, Online handwriting recognition withsupport vector machines-a kernel approach, in: Proceedings of the EighthInternational Workshop on Frontiers in Handwriting Recognition, IEEE, 2002, pp.
49–54. 〈http://dx.doi.org/10.1109/iwfhr.2002.1030883〉[39] K. Sivaramakrishnan, K. Karthik, C. Bhattacharyya, Kernels for large margin timeseries classiﬁcation, in: Proceedings of the International Joint Conference on
Neural Networks, IJCNN 2007 IEEE, 2007, pp. 2746–2751. 〈http://dx.doi.org/10.
1109/ijcnn.2007.4371393〉.
[40] I. Kononenko, M. Kukar, Machine Learning and Data Mining: Introduction to
Principles and Algorithms, Horwood Publishing, Chichester, UK, 2007. http://dx.doi.org/10.5860/choice.45-3834.
[41] Y. Freund, R.E. Schapire, A desicion-theoretic generalization of on-line learningand an application to boosting, in: Lecture Notes in Computer Science, Springer
Science+Business Media, 1995, pp. 23–37. 〈http://dx.doi.org/10.1007/3-54059119-2_166〉.
[42] A.J. Grove, D. Schuurmans, Boosting in the limit: Maximizing the margin oflearned ensembles, in: Proceedings of the Fifteenth National Conference on
Artiﬁcial Intelligence, 1998, pp. 692–699.
[43] H. Drucker, C. Cortes, Boosting decision trees, in: Advances in Neural Information
Processing Systems, 1996, pp. 479–485.
[44] J.R. Quinlan, Bagging, boosting, and c4.5, in: Proceedings of the Thirteenth
National Conference on Artiﬁcial Intelligence, AAAI Press, 1996, pp. 725–730.

[10] J. Yuen, B. Russell, C. Liu, A. Torralba, Labelme video: Building a video databasewith human annotations, in: Proceedings of the 2009 IEEE 12th International
Conference on Computer Vision, IEEE, 2009, pp. 1451–1458. 〈http://dx.doi.org/
10.1109/iccv.2009.5459289〉.
[11] M. Goto, R. Ishida, Y. Feng, S. Uchida, Analyzing the distribution of a large-scalecharacter pattern set using relative neighborhood graph, in: Proceedings of the2013 12th International Conference on Document Analysis and Recognition(ICDAR), IEEE, 2013, pp. 3–7. 〈http://dx.doi.org/10.1109/icdar.2013.10〉.
[12] D.L. Martin, Feature extraction: a survey, in: Proceedings of the IEEE, vol. 57(8),1969, p. 1391. 〈http://dx.doi.org/10.1109/proc.1969.7277〉.
[13] G. Chandrashekar, F. Sahin, A survey on feature selection methods, Comput. Electr.
Eng. 40 (1) (2014) 16–28. http://dx.doi.org/10.1016/j.compeleceng.2013.11.024.
[14] S. Arya, D.M. Mount, N.S. Netanyahu, R. Silverman, A.Y. Wu, An optimal algorithm
for approximate nearest neighbor searching ﬁxed dimensions, J. ACM (JACM) 45(6) (1998) 891–923. http://dx.doi.org/10.1145/293347.293348.
[15] D. Nister, H. Stewenius, Scalable recognition with a vocabulary tree,
in: Proceedings of the 2006 IEEE Computer Society Conference on Computer
Vision and Pattern Recognition, IEEE, vol. 2, 2006, pp. 2161–2168. 〈http://dx.doi.
org/10.1109/cvpr.2006.264〉.
[16] S. Garcia, J. Derrac, J.R. Cano, F. Herrera, Prototype selection for nearest neighborclassiﬁcation taxonomy and empirical study, IEEE Trans. Pattern Anal. Mach.
Intell. 34 (3) (2012) 417–435. http://dx.doi.org/10.1109/tpami.2011.142.
[17] R. Bellman, Adaptive Control Processes: a Guided Tour, vol. 4. 〈http://dx.doi.org/
10.2307/1909901〉.
[18] P. Viola, M.J. Jones, Robust real-time face detection, Int. J. Comput. Vis. 57 (2)(2004) 137–154. http://dx.doi.org/10.1023/b:visi.0000013087.49260.fb.
[19] M. Pelillo, Similarity-Based Pattern Analysis and Recognition, Springer, London,
UK, 2013. http://dx.doi.org/10.1007/978-1-4471-5628-4.
[20] A.L. Fred, A. Lourenço, H. Aidos, S.R. Bulò, N. Rebagliati, M.A. Figueiredo, M.
Pelillo, Learning similarities from examples under the evidence accumulation
clustering paradigm, in: Similarity-Based Pattern Analysis and Recognition,
Springer, 2013, pp. 85–117. 〈http://dx.doi.org/10.1007/978-1-4471-5628-4_5〉.
[21] R.C. Wilson, E.R. Hancock, E. Pekalska, R.P. Duin, Spherical and hyperbolic
embeddings of data, IEEE Trans. Pattern Anal. Mach. Intell. 36 (11) (2014)
2255–2269. http://dx.doi.org/10.1109/tpami.2014.2316836.
[22] M. San Biagio, S. Martelli, M. Crocco, M. Cristani, V. Murino, Encoding structuralsimilarity by cross-covariance tensors for image classiﬁcation, in: International
Journal of Pattern Recognition and Artiﬁcial Intelligence, vol. 28(07). 〈http://dx.
doi.org/10.1142/s0218001414600088〉.
[23] R.P. Duin, M. Bicego, M. Orozco-Alzate, S.-W. Kim, M. Loog, Metric learning indissimilarity space for improved nearest neighbor performance, in: Structural,
Syntactic, and Statistical Pattern Recognition, Springer, 2014, pp. 183–192.
〈http://dx.doi.org/10.1007/978-3-662-44415-3_19〉.
[24] K. Riesen, M. Neuhaus, H. Bunke, Graph embedding in vector spaces by means ofprototype selection, in: Graph-Based Representations in Pattern Recognition,
Springer, 2007, pp. 383–393. 〈http://dx.doi.org/10.1007/978-3-540-72903-7_35〉.
[25] B. Spillmann, M. Neuhaus, H. Bunke, E. Pekalska, R.P. Duin, Transforming strings
to vector spaces using prototype selection, in: Structural, Syntactic, and Statistical
Pattern Recognition, Springer, 2006, pp. 287–296. 〈http://dx.doi.org/10.1007/
11815921_31〉.
[26] L. Batista, E. Granger, R. Sabourin, Applying dissimilarity representation to oﬀ-line
signature veriﬁcation, in: Proceedings of the 2010 20th International Conference
on Pattern Recognition (ICPR), IEEE, 2010, pp. 1293–1297. 〈http://dx.doi.org/10.
1109/icpr.2010.322〉.
[27] G.S. Eskander, R. Sabourin, E. Granger, Dissimilarity representation for handwritten signature veriﬁcation., in: AFHA, Citeseer, 2013, pp. 26–30.
[28] E. Pekalska, R.P. Duin, Dissimilarity representations allow for building goodclassiﬁers, Pattern Recognit. Lett. 23 (8) (2002) 943–956. http://dx.doi.org/
10.1016/s0167-8655(02)00024-7.
[29] E. Pekalska, R.P. Duin, P. Paclík, Prototype selection for dissimilarity-basedclassiﬁers, Pattern Recognit. 39 (2) (2006) 189–208. http://dx.doi.org/10.1016/
j.patcog.2005.06.012.
[30] K. Riesen, H. Bunke, Graph Classiﬁcation Based on Vector Space Embedding 23,
World Scientiﬁc, Singapore, 2009, pp. 1053–1081. http://dx.doi.org/10.1142/
s021800140900748x.
[31] Y. Plasencia-Calana, M. Orozco-Alzate, H. Méndez-Vázquez, E. García-Reyes, R.P.
Duin, Towards scalable prototype selection by genetic algorithms with fast criteria,

Brian Kenji Iwana received a B.S. from the University of California, Irvine, UnitedStates of America in 2005. He is currently pursuing a Ph.D. degree from the Department
Advanced Information Technology at Kyushu University, Japan. His research interests
include pattern recognition, temporal patterns, and dissimilarity space embedding.
Volkmar Frinken is a researcher at Onai Technology and was formerly a Research
Assistant Professor at Kyushu University, Japan. He obtained his M.S. in Computer
Science in 2007 from the University of Dortmund, Germany and in 2011 his Ph.D. fromthe University of Bern, Switzerland. His research interests include handwriting recognition and keyword spotting, semisupervised learning, language models and document
analysis.
Kaspar Riesen received his M.S. and Ph.D. degrees in Computer Science from the
University of Bern in 2006 and 2009, respectively. He is interested in graph based
representations in pattern recognition and related ﬁelds. Kaspar Riesen has more than 40
publications which are currently cited by 158 authors in more than 200 publications.
Since 2009 he works at the University of Applied Sciences Northwestern Switzerland.
Seiichi Uchida received B.E. and M.E. and Dr. Eng. degrees from Kyushu University in
1990, 1992 and 1999, respectively. From 1992–1996, he joined SECOM Co., Ltd., Japan.
Currently, he is a professor at Kyushu University. His research interests include patternrecognition and image processing. He received 2007 IAPR/ICDAR Best Paper Award,
2010, ICFHR Best Paper Award, and many domestic awards. Dr. Uchida is a member ofIEEE, IEICE and IPSJ.

276