社団法人 電子情報通信学会
THE INSTITUTE OF ELECTRONICS,
INFORMATION AND COMMUNICATION ENGINEERS

信学技報
TECHNICAL REPORT OF IEICE.

サポートベクターマシンによる数学記号認識
クリストファー

マロン†

鈴木 昌和††

内田誠一†††† マサチューセッツ工科大学数学部†† 九州大学大学院数理学研究院 〒 812–8581 福岡市東区箱崎 6–10–1††† 九州大学大学院システム情報科学研究院 〒 812–8581 福岡市東区箱崎 6–10–1
E-mail: †malon@mit.edu, ††suzuki@math.kyushu-u.ac.jp, †††uchida@is.kyushu-u.ac.jp

キーワード

数式認識、記号認識、文字認識、サポートベクターマシン

Support Vector Machines for Mathematical Symbol Recognition
Christopher MALON† , Masakazu SUZUKI†† , and Seiichi UCHIDA†††† MIT Department of Mathematics
77 Massachusetts Ave., Cambridge, MA 02139 USA†† Engineering Division, Faculty of Mathematics, Kyushu University
6–10–1 Hakozaki, Higashi-ku, Fukuoka-shi, Fukuoka, 812–8581 Japan††† Faculty of Information Science and Electrical Engineering, Kyushu University
6–10–1 Hakozaki, Higashi-ku, Fukuoka-shi, Fukuoka, 812–8581 Japan
E-mail: †malon@mit.edu, ††suzuki@math.kyushu-u.ac.jp, †††uchida@is.kyushu-u.ac.jp
Abstract Mathematical formulas challenge an OCR system with a range of similar-looking characters whose bold,calligraphic, and italic varieties must be recognized distinctly, though the fonts to be used in an article are not known
in advance. We describe the use of support vector machines (SVM) to learn and predict about 300 classes of styled
characters and symbols.
Key words mathematical formula recognition, symbol recognition, character recognition, support vector machines

1. Introduction

The Infty Project [7] in the Suzuki Laboratory at Kyushu
University is developing Infty Reader software [5] to perform

Optical character recognition problems were considered

OCR of scanned mathematical journal articles, and produce

very early in the development of support vector machines,

output in languages that allow symbol relationships to bewith promising results [1]. However, the problem of OCR formathematical documents is substantially more difficult thanproperly encoded, including TEXand MathML. Although Infty Reader nominally achieved 99 percent accuracy of single–

standard OCR problems for three principal reasons:letter recognition before this investigation (October 2005),（ 1 ） Although a variety of fonts is used in mathematicalits failure to distinguish certain common symbols would be

literature, when reading any single paper, it is important tobothersome to any serious user.

keep appearances of italic, bold, roman, calligraphic, type-

The Infty Project defined entities for about 600 charac-

writer, and blackboard bold letters distinguished.

ters and symbols used in mathematical research, and cre-（ 2 ） A rich set of symbols is used, and distinctions be-ated a ground truth database identifying their appearances

tween letters may be more subtle than within the characterin page–by–page scans of hundreds of journal articles. Manyset of a typical human language.

character pairs could be distinguished in different styles by（ 3 ） The symbols are not arranged in a simple one–

simple clustering techniques applied to directional features

dimensional pattern. Subscripts, superscripts, fractional re-measured in a mesh grid. Runtime accuracy exceeded 99% ,lationships, and accents occur, and may be nested [2].

but hundreds of letter pairs remained consistently problem—1—

atic. We aim to improve the accuracy of single–character
recognition through the use of support vector machines.

2. Test Data
The Infty character set comprises 1,571 Roman and Greek

Big Symbol
Calligraphic
Greek UprightArrow

letters, numbers, and mathematical symbols, divided into 46
categories according to purpose and style. Further details ofthese characters appear in [8].

Greek Italic

The Infty Project has selected journal articles representing diverse fields of higher mathematics, taken from a thirty

Binary Operators

year period. These articles were scanned page by page at 600
dpi to produce bitmap image files. The Infty OCR engine

Other Symbols

extracted the symbols from each page and recognized each

German Uprightsymbol as a character from the Infty character set. College

Blackboard Boldand graduate mathematics students manually inspected andcorrected the results.
The results of this process appear in a “ground truth”
database. Namely, for each character on a scanned page,

Latin Uprighta bitmap framed by the bounding box of that character istaken from the page. This bitmap is tagged with the correct identification of the symbol. （注 1） “Link information”

Latin Italic

describing the character’s relationship to others on the page(subscripts, superscripts, limits, portions of a fraction, etc.)
is also available in the database, but it is not utilized in thepresent study.
In fact, the Infty project has produced two databases ofRelational Operators
Accents
Punctuation

this kind. One, called InftyCDB-1, is freely available for re-

Symbol Fragments

search purposes upon request, and is summarized in [8]. The

Ligature Italicother is used internally by the Infty Reader OCR engine.

Brackets

We use the latter database in this experiment, because it

Ligature Upgrighthas more data, and because it makes it easier to compare

Figure 1 Symbols with 10 training, selection, and testing samples

our results with those of the actual Infty Reader. Our data
sample consists of 284,739 character symbols extracted from363 journal articles. There are 608 different characters represented.
At random, we divide the 363 articles into three parts consisting of 121 articles each. The data from the corresponding
articles is marked as “training”, “selection”, or “testing” ac-

3. Directional Features
Given an instance of a symbol, let w be its width and hbe its height. Our feature vectors consist of the aspect rah
tio ( w), followed by 160 floating–point coordinates of meshdirectional feature data.

cordingly. To make sure we had enough data to train andThis mesh data is divided into “tall”, “square”, andevaluate our classifiers, we examined only the characters with“short” blocks of 48, 64, and 48 coordinates respectively.

at least ten samples in training, selection, and testing por-When the aspect ratio of a character exceeds 1.3, the talltions of the database. This left 297 characters, pictured inblock contains directional feature data computed from a 3×4

Figure 1.

mesh; otherwise it contains zero–valued entries. When the1
aspect ratio of a character is between 1.7
and 1.7, the square

block contains directional feature data from a 4 × 4 mesh;（注 1）：Some bitmaps would not be identifiable solely on the basis ofotherwise it contains zero–valued entries. When the aspect

this bitmap. For example, a hyphen could not be distinguished from1
ratio of a character is less than 1.3, the short block contains

an underscore, without knowing its relationship to the baseline on
the page when it was scanned. The original position on the page isdirectional features computed from a 4 × 3 mesh; otherwisepart of the database, but this information was discarded prior to ourit contains zero–valued entries. Thus, for any symbol, one

experiment.

—2—

or two (but never three) of the blocks are assigned nonzero

popular methods (1–vs–1, 1–vs–all, and the Directed Acyclic

entries.

Graph) may be found in [4]. Except for the 1–vs–all method,

We describe roughly the algorithm for associating direc-

these methods require the construction of O(n2 ) classifiers

tional feature data to an m × n mesh block. Divide theto solve an n–class classification problem. Because the Infty

original bitmap horizontally into m equally sized lengths,

character set includes more than 1,500 entities, this seemedand vertically into n equally sized lengths. Assign a “chunk”

unnecessarily burdensome. Therefore, we try to extract anof four coordinates of the block to each of the m × n grideasier part of the classification problem that can be solved

positions; initially, their values are zero. These four coor-

without SVM.

dinates represent the horizontal and vertical directions, andTaking the data assigned to the “training” portion of thedatabase, we compute the mean feature vectors for the in-two diagonals.
The contribution of part of the outline’s direction to thestances of each symbol. We create a naive classifier thatmesh features is determined from its position in the bitmap,

assigns an input to the class whose mean feature vector isusing a partition of unity. Given a positive integer r, con-nearest, by Euclidean distance.

sider the r–fold partition of unity given by the functions
pri : [0, 1] → [0, 1] defined bypri (x) =the database, to produce a confusion matrix. The (i, j) entry of this matrix counts the number of samples in which


0





1
x < ri − 2r
i
1 <
i
1
−
=x< +

r(x − (i/r − 1/2r))−r(x − (i/r + 3/2r))



0



 1



−r(x − 3/2r)
0

j by this rule. The 297 by 297 confusion matrix we pro-(1)

We consider some of the misrecognitions to be too difficult

duced had 947 nonzero off-diagonal entries, an average of 3.2
misrecognitions per character.
for any classifier to resolve on the basis of our mesh of directional features. Particularly, we do not expect bold andnon–bold variants of the same character to be distinguish-

1
x < 2r1 <3
x < 2r2r =3
x > 2r(2)

able. Also, we do not expect upper and lower case variants of
the letters C, O, P, S, V, W, X, and Z to be distinguishable inthe same style, or in styles that are identical except for bold-and

prr−1 (x) =a character truly belonging to class i was assigned to class

r
2r
r
2r
1 <
3
i
i
+
+
x
<
r
2r =
r
2r
3
x > ri + 2r

for 1 <
= i < r − 1,

pr0 (x) =We run this naive classifier on the “selection” portion of



 0



3
r(x − (1 − 2r))

1

ness. Disregarding misrecognitions of these two kinds, 896
3
x < 1 − 2r
1
1− 3 <
=x<1−

2r
1 <
1 − 2r=x2rother nonzero off–diagonal entries remain in the confusion.

matrix.
For 62 of the 297 characters with ten training, selection,(3)
Discard every isolated black pixel from the original bitmap.

and testing samples, the naive classifier recognized less thanhalf of the selection samples correctly. These characters are
displayed in Figure 2. In comparison, ninety percent ac-

In the remaining bitmap, trace every outline between whiteand black pixels, following its chain code description. Whenvisiting the pixel in location (x, y) during this trace, identify
the direction (horizontal, vertical, diagonal one, or diagonaltwo) where the next pixel in the outline will be. For every i,
m x
n y
0<
= i < m, and every j, 0 <= j < n, add pi ( ) · pj ( ) to thewhcoordinate of the (i, j) chunk representing that direction.
After completing the trace of each outline component, divide all the values by the perimeter of the bounding box.
This result gives the values to be entered in the corresponding block of the feature vector.

4. Naive classifier
Typically, a support vector machine learns a binary classification. There are various techniques for putting SVM’stogether to distinguish multiple classes; a comparison of some

Figure 2 Characters the naive classifier usually fails to recognize

curacy is achieved for 197 of the 297 symbols, 95 percent
accuracy for 163 symbols, and 99 percent accuracy for 123
symbols.
Although the confusion matrix is relatively sparse, certain
troublesome characters have many misrecognition results, as
can be seen in Figure 3. For 95 of the 297 characters, atleast four distinct characters occur as misrecognition results.

—3—Characters160of soft margin will yield the classifier with the best general-

140

ization ability. We optimize this choice for best performance120

on the selection portion of our data, as follows.

100

Our basic parameter search method, here and in the fol-8060

lowing sections, is a grid search method that generalizes to40

any number of dimensions. For each candidate parameter200assignment, we train an SVM with those parameters on the
0

2

4

6
8
10
12
14
Number of misrecognition alternatives

16

18

training portion of our data. Then we measure its perfor-

20

Figure 3 Histogram of distinct misrecognitions of an input char-mance on the instances of two classes that appear in theselection data. The score of the parameter is the minimum

acter by the naive classifierof the accuracy on the first class’s input and the accuracy
Eleven letters (plain ’1’, ’4’, ’E’, ’I’, ’l’, ’r’, ’s’, ’t’, ’ “ ’, anditalic ’γ’ and ’ψ’) had ten or more distinct characters appear

on the second class’s input. Hereafter, “accuracy” by itself,
in the context of a binary classification problem, will refer tothis score.

as misrecognition results.
At runtime, the naive classifier will be used to assign eachletter to a cluster of possible candidates, consisting of therecognition result and the other candidates most likely tohave produced that recognition result (as determined by our
confusion matrix). The harder problem of distinguishing between the letters in each of these clusters will be assigned tosupport vector machines.

Often, grid searches require a search interval to be specified for each dimension. Our approach requires only an initial parameter choice, and then grows the search region outward, until performance stops improving. More formally, let
x1 , . . . , xn be the variable parameters, and xinit, . . . , xinitben1
their initial values. Let L be the discrete set of points of thenform (2j1 xinit, . . . , 2jn xinitn ) for some (j1 , . . . , jn ) ∈ Z .
1.
to xinit
and xmax（ 1 ） For each i, set xminiii

5. Linear SVM（ 2 ） Set the iteration count t to zero.

Within each cluster, we will use the 1–to–1 approach tomulticlass classification. This requires first creating a binary







（ 3 ） Let B be the box xmin
, xmax× · · · × xmin
, xmax,nn11and ∂C be its boundary. Record the best value on each surface of the box.

SVM for each pair of classes in the cluster.
Because they are simple and can be computed quickly, we
begin our experiment with SVM’s that use the linear kernel:（ 4 ） For each untested parameter value in the finite set

L ∩ ∂C, train a new SVM on those parameters, and assign
it a score based on selection data performance, as explainedK(~x, ~y ) = ~x · ~y.

(4)The naive classifier, when restricted to two classes, can bethought of as the linear classifier determined by the hyperplane equidistant from the two cluster centers. The support
vector method enables us to search for hyperplanes in theoriginal feature space that perform better on the training
data.
There are no kernel parameter choices needed to create alinear SVM, but it is necessary to choose a value for the softmargin (C) in advance. Then, given training data with feature vectors x~i assigned to class yi ∈ {−1, 1} for i = 1, . . . , l,
the support vector machines solve
min

~
w,b,
~ ξ

1
K(w,
~ w)
~ +C
2

Pl

ξ
i=1 i

above.
（ 5 ） If the performance is superior to 99.5% accuracy,skip to the last step.
（ 6 ） From these results, for every i, set bt,+
and bt,−toiithe highest scores achieved on the hyperplanes xi = xmaxi
and xi = xmin
, respectively.
i>（ 7 ） If t > 0, double xmax
for every i such that bt,+
i
=
i
t−1,−
>
bt−1,+, and halve xmin
for every i such that bt,−
.
i
= bi
i
i

If t = 0, double xmax
and halve xmin
for all i, regardless.
ii（ 8 ） Increment the iteration count t.
（ 9 ） If t < 3 or the best performance has increased in thelast iterations, return to step 3.
（ 10 ） Report the best performance, and the most recently(5)

subject to yi (K(w,~ x~i ) + b) >= 1 − ξiξi >=0tested parameter selection that reached that performance.
Initial choices may matter under this grid search algorithm, if the algorithm terminates before reaching a selection

where ξ~ is an l–dimensional vector, and w~ is a vector in theof parameters that produces globally optimal results. Thissame feature space as the x~i (see, e.g., [3]). The values w~ andpossibility seems unlikely as long as the resulting SVM per-b determine a hyperplane in the original feature space, giving

forms better than random guessing in each case. The linear

a linear classifier. A priori, one does not know which value

SVM problem has only the soft margin C = x1 as a param—4—

eter, and we set it initially to be xinit= 1024.
1
Table 1 displays the accuracy achieved by the linear SVM
selected, on the testing data for pairs of symbols that thenaive classifier sometimes confused.
Accuracy > Number of pairs
Total

795

0

783

.5

774

.6

770

.7

767

.8

759

.9

750

.95

742

.97

720

.99

684

.995

650

.999

609

Figure 5 Pairs with two–fold improvement over naive classifier
using linear SVM

Table 1 Linear SVM performance

We compared the chosen linear SVM classifier’s performance on the letters where the naive classifier did not reach
100% accuracy, to the performance of the naive classifier.
The 896 misrecognitions of the naive classifier comprise 795
unordered pairs of symbols. For nine of these pairs, boththe naive classifier and the linear SVM always misassigned
one of the two characters. Figure 4 compares the performance of the two methods on the remaining 786 pairs. Of
the 786 pairs, 34 did not perform as well under the linear
SVM as with the naive classifier. The exact same performance was achieved on 95 pairs, and improvement occurredon 657 pairs. The histogram does not report the 24 symbols
with more than a three–fold improvement in accuracy. Thirteen of these symbols received zero accuracy from the naiveclassifier, for an infinite improvement in performance.

symbol recognition rates dramatically improved, but the useof a linear kernel severely limits the potential benefit of a
support vector machine. The use of a Gaussian (radial) kernel
2

K(~x, ~y ) = e−γk~x−~yk(6)in the SVM problem (5) effectively transforms the input feature space into an infinite–dimensional one, where the search
for an optimal separating hyperplane is carried out. Classifiers of this form may perform better on classes whose feature
data is not linearly separable in the original feature space.
However, the addition of the parameter γ in the kernel definition makes the parameter search two–dimensional, adding
According to a result of Keerthi and Lin [6], given a soft

250

Number of pairs

Just by using linear kernel support vector machines, ourcomputational expense to the selection of a classifier.

300

margin C, the sequence of Gaussian SVM classifiers with

200

C
kernel parameter γ and soft margin 2γ
converges pointwise,150

as γ → 0, to the linear SVM classifier with soft margin C.

100

Thus, if our parameter search is wide enough, we should

50
0

6. Gaussian SVM

achieve higher accuracy with the Gaussian kernel than with
0

0.5

1
1.5
2
Number of times improvement in accuracy

2.5

3

Figure 4 Histogram of improvement of linear SVM compared tonaive classifier

Figure 5 illustrates the cases where the linear SVM
achieved double the accuracy of the naive classifier.

the linear one.
We constructed Gaussian–kernel SVM classifiers for the
75 pairs of letters that the linear kernel failed to distinguishwith 97% accuracy. A comparison of the performance of thechosen classifiers for each kernel type is given in Figure 6.
In Figure 7, we display the eight pairs on which the Gaussian SVM performed with at least 10% higher accuracy thanthe linear SVM. The 31 pairs where Gaussian SVM accuracy
falls below 80% are shown in Figure 8.
—5—

1

Acknowledgments
Gaussian SVM accuracy

0.8

The first author thanks the MIT Japan Program for its

0.6

support of the visit that made this collaboration possible,
0.4

and Kyushu University for its generous hospitality during
his stay.

0.2

0

0

0.1

0.2

0.3

0.4
0.5
0.6
Linear SVM accuracy

0.7

0.8

0.9

1

Figure 6 Comparison of linear and Gaussian SVM performance

Figure 7 Pairs with 10% improvement from linear to Gaussian
kernelFigure 8 Pairs with under 80% accuracy by Gaussian SVM

7. Conclusion
Even with the simplest kernel, the support vector method

References[1] Corinna Cortes and Vladimir Vapnik. Support-vector networks. Mach. Learn., 20(3):273–297, 1995.
[2] Yuko Eto and Masakazu Suzuki. Mathematical formula
recognition using virtual link network. In Sixth International Conference on Document Analysis and Recognition(ICDAR), pages 430–437. IEEE Computer Society Press,
2001.
[3] C.-W. Hsu, C.-C. Chang, and C.-J. Lin. A practical guide tosupport vector classification. http://www.csie.ntu.edu.tw/%7Ecjlin/papers/guide/guide.pdf, July 2003.
[4] C.-W. Hsu and C.-J. Lin. A comparison of methods for
multi-class support vector machines. IEEE Transactions
on Neural Networks, 13:415–425, 2002.
[5] The infty project. http://infty.math.kyushu-u.ac.jp.
[6] S. Sathiya Keerthi and Chih-Jen Lin. Asymptotic behaviors of support vector machines with gaussian kernel. NeuralComput., 15(7):1667–1689, 2003.
[7] Masakazu Suzuki, Fumikazu Tamari, Ryoji Fukuda, Seiichi
Uchida, and Toshihiro Kanahori. Infty: an integrated ocr
system for mathematical documents. In DocEng ’03: Proceedings of the 2003 ACM symposium on Document engineering, pages 95–104, New York, NY, USA, 2003. ACM
Press.
[8] Masakazu Suzuki, Seiichi Uchida, and Akihiro Nomura. A
ground-truthed mathematical character and symbol image
database. In ICDAR ’05: Proceedings of the Eighth International Conference on Document Analysis and Recognition (ICDAR’05), pages 675–679, Washington, DC, USA,2005. IEEE Computer Society.

is strong enough to achieve good generalization accuracy onan optical character recognition problem that causes difficulty for simpler classification methods. We believe that our
SVM results may be the best classification possible on thebasis of the mesh of directional features we are using.
To distinguish the characters that confuse our SVM classifier, we plan to add new features. For example, by counting
the number of connected components in a symbol, we could
distinguish many variants of the greater–than sign (>). We
also plan to record the convexity or concavity of a symbol as
traced along its outline, to distinguish various nearly vertical characters. These features will be the topic for a future
paper.
To our surprise, the SVM’s we constructed with the Gaussian kernel did not show significantly stronger performanceon the testing data. We attribute this phenomenon to thesimple nature of our mesh of directional features. We plan
to repeat this comparison after attaching a greater variety offeatures to our data.

—6—