Detection of Matrices and Segmentation of Matrix Elements
in Scanned Images of Scientific Documents
KANAHORI Toshihiro
Research Center on Educational Media,Tsukuba College of Technology
4-12 Kasuga, Tsukuba-shi, Ibaraki, 305-0821 Japankanahori@k.tsukuba-tech.ac.jp

Abstract
We proposed a method for recognizing matrices whichcontain abbreviation symbols, and a format for representing the structure of matrices, and reported experimental results in our paper [1]. The method consisted of 4 processes;
detection of matrices, segmentation of elements, construction of networks and analysis of the matrix structure. In
the paper, our work was described with a focus on the construction of networks and the analysis of the matrix structure. However, we concluded that improvements in the othertwo processes were very important for obtaining a high accuracy rate for recognition. In this paper, we describe thetwo improved processes, the detection of matrices and thesegmentation of elements, and we report the experimentalresults.

1. Introduction
The technology of OCR is very efficient for digitizing
printed documents. However, current OCR systems can notrecognize mathematical formulae, which are very importantin scientific documents. Several algorithms for recognizing
mathematical formulae have been reported in the literature([2]–[4]), and some of them can be applied to very simple matrices, such as gridironed matrices. In our paper [1],we proposed a new practical method for recognizing matrices containing abbreviation symbols, and proposed a format
for representing a matrix structure to output the recognitionresults. We defined the domain to allow matrices to contain formula elements, area symbols and repeat symbols in
the matrix coordinates (Fig. 3). The method consists of 4processes; (1) detection of matrices in a scanned page image, and extraction of characters from each area of the matrices, (2) segmentation of the characters into elements foreach matrix, (3) construction of networks of the elements,

SUZUKI Masakazu
Faculty of Mathematics, Kyushu University
Kyushu Univ. 36, Fukuoka, 812-8581 Japansuzuki@math.kyushu-u.ac.jp

and (4) analysis of the structure of each matrix. In process(3), we regard a matrix structure as a network of elements
connected to each other by links representing their relationships, and we consider independently the horizontally andvertically projected networks (Fig. 1). In process (4), we obtain the areas of variable block pattern elements generating
the minimum rectangular area of the matrix by solving a simultaneous system of equations given by the two projected
networks (Fig. 2). When the segmentation of the elements
and the construction of the networks are performed without
error, the structure analysis is always completed correctly.
In our paper, we described these processes with a focus onalgorithms for constructing the networks and for solving thesimultaneous systems. In the experimental results of thepaper, we obtained some measure of accuracy of the recognition rate, but it was not satisfactory. Most of the errors
resulted from the process for segmentation of the elements.
In this paper, we present details of improved algorithms
for the 2 processes (1) and (2) above, and report the experimental results of these methods. The decorators, which represent detail numbers for elements, positions of elements,etc., are excluded at present (Fig. 3).

2. Assumptions and DefinitionsWe assume that a matrix has at least 2 rows and it isfenced by one of 4 couples of parentheses, ( ), { }, [ ] and | |(determinant), and that matrix elements can be gridironed(Fig. 2).
We classify the components of a matrix into 3 classes(Fig. 3). The definitions are;
Formula element has only one grid as its own area, and canconnect to other elements in the 8 directions (Fig. 1).
Area symbol has several grids as its own area and a freeboundary. Common area symbols are O, 0, 1, ∗, etc. , and aspace is also an area symbol.

Figure 3. Matrix components (left) and Decorators (right).

Figure 1. Example of the construction andprojection of a network.

acters are horizontally sorted by the x-coordinates of theirbounding rectangles, but in a mathematical formula having a 2-dimensional structure, their order is indefinite. For
example, in a fraction, characters of the numerator and denominator are mixed in a line, and their order is not defined.
The detection of matrices is processed as follows:
1. From the head to the tail of a line, big parentheses arelocated and added to a list of big parentheses, where abig parenthesis is determined by the following conditions:• Its height must be greater than Have × 1.5.
• It is one of the parentheses.

Figure 2. Example of a simultaneous systemof equations given by the two projected networks.

Repeat symbol means that formula elements are continuously aligned on the straight line in its direction; ↓, →, &or %. It can connect to formula elements and other repeat
symbols with different directions.
For our matrix recognition from a page image, we assume that its lines are distinguished, characters are recognized, a coordinate of a bounding rectangle of each character is obtained and an average of the heights of the characters is determined. We define the following symbols to givea clear description:
Have := the average of the heights of characters,
BR(c) := a bounding rectangle of a character c,
Intx (c) := a projected interval of BR(c) to the x-axis,
Inty (c) := a projected interval of BR(c) to the y-axis,

2.1. Detection of Matrices
The matrix recognition is applied to each of the lines.
Each line is a linear sequence of characters. In a line, char-• If it is not one of the parentheses, its width mustbe less than Have , considering an error of character recognition. In this case we regard it as ‘|’ (avert).
2. From the tail to the head of a line, for an openingparenthesis, a closing parenthesis is searched for which
can be a couple with the opening parenthesis, where
the conditions of a parenthesis couple are:
• The closed parenthesis is on the right side of theopening parenthesis.
• There is no big parenthesis between them.
• There are at least 2 characters between them.
• Considering the case when one of them is broken,
an intersection of their projections to the y-axis ismore than a half of each projection.
When a couple of parentheses are found, they are botherased from the list of parentheses. For a vert, a closing
vert is searched for amongst the verts in the list.
If some parentheses are remaining in the lists after the detection process, they are treated as conditional statements.
For each of the detected parenthesis couples, characters
between them are segmented into matrix components. We
assume that the results of the character recognition are always correct in the following.

2.2. Segmentation of Matrix Elements
Following the detection of matrices, each detected matrix has a set of characters in its own area. It is necessary tosegment them into formulae elements or area symbols.
We let C = {c1 , · · · , cn } be a set of the characters, except
for dots, in the matrix. For two characters c and d ∈ C, we
define an interval Btwx (c, d) = [s,t] by(s = min(tc ,td ),Intx (c) ∩ Intx (d) 6= 0/ ⇒t = max(sc , sd )Intx (c) ∩ Intx (d) = 0/ ⇒ Btwx (c, d) := 0,/where we let [sc ,tc ] = Intx (c) and [sd ,td ] = Intx (d). For acharacter c ∈ C, we define a set of characters, NBx (c), by
Btw(c, d) 6= 0,/ and NBx (c) := d ∈ C Intx (b) 6⊂ Btwx (c, d) .

for any b ∈ C

We also define Btwy (c, d) and NBy (c) in the same manner
as above. For c ∈ C, except for a ‘−’ (a minus), we obtaina scope of c, SC(c), by inflating BR(c) by αx Sx (c) on boththe left and right hand sides and by αy Sy (c) in both the upper and lower regions. If BR(d), for d ∈ C, and SC(c) havean intersection, the characters d and c are segmented into
the same element (Fig. 4). The value Sx (c) is obtained by anaverage of the two shortest lengths among a set of lengths ofintervals, { | Btwx (c, d)| d ∈ NBx (c) }. If | NBx (c, d)| < 2,a temporary value 12 Have is used instead of the lengths. Thevalue Sy (c) is obtained in a way similar to Sx (c). Thesevalues denote the distances between c and other characterswhich are immediately adjacent to c (there is no character
between them). If Sx (c) (or Sy (c)) is larger than Have , weassume that there is no character adjacent to c, so we set
Sx (c) = 0 (resp. Sy (c) = 0).
The coefficients, αx and αy , also depend on c. We set thecoefficient αx as4c is a big symbol (∑, ∏, etc.),c is a binary operator,
3αx (c) := 1.5 c is long and thin alphanumeric,
0.1 c is short and wide alphanumeric,1otherwise,
where we let c be long and thin when the height of BR(c)is greater than two times its width, and let c be short andwide when the width of BR(c) is greater than one and ahalf times its height, and αy as
1.2 c is a big symbol (∑, ∏, etc.),
0.3 c is a binary operator,
αy (c) :=
1.6 c is a fractional line,
0.3 otherwise,

where we let c be a fractional line when c is recognized asa fractional line by the character recognition, or when c isrecognized as a minus yet there are some characters within
a distance of a half of Have to the upper and lower regions ofc. These values are determined in practice. The values forαx are set larger than those for αy so that the horizontal connections are tighter than the vertical ones. Almost always abinary operator has characters on both of its sides and often
there is some space between them, so αx for binary operators is set larger than for other symbols. A big symbol often
includes an upper or a lower limit formula, and is separated
from it by only a very small distance, so αx for big symbols is set to be large to prevent a big symbol which does
not have an upper or lower limit formula from incorrectly
including other elements as part of a formula of this type. A
fractional line always has a numerator and a denominator,
so αx for fractional lines is set to be larger than for othersymbols.
The character ‘−’ (minus) is used as a binary operator ora sign. It is necessary to determine whether or not it is being
used as a sign. When it is a sign, the space on its left handside is larger than that on its right hand side. Therefore, forc = ‘−’, we use a different definition of SC(c). We obtain
SC(c) by inflating BR(c) by Sx (c) + β on both the left andright hand sides and by αy Sy (c) in both the upper and lower
regions (Fig. 5). The values Sy (c) and αy (c) are obtained ina similar way as for other characters. The value Sx (c) is thedistance on the x-axis between c and the nearest characterto c among R(c), where)(d is on the right side of c and.
R(c) := d ∈ CInty (c) ∩ Inty (d) 6= 0/
If R(c) = 0,
/ we set Sx (c) = 0. The constant β is included toallow for some fluctuation, and is set at 4 pixels per 600 dpi(scanned resolution).
In the above process, dots are not considered as components of a matrix element. However, they are very often contained in a matrix element, and it is necessary tosegment dots into elements if they are contained. We let
D = {d1 , · · · , dm } be the set of dots in the matrix and let
E = {e1 , · · · , el } be the set of segmented matrix elements.
For a dot d ∈ D and an element e ∈ E, if BR(d)∩BR(e) 6= 0,/where BR(e) is the smallest rectangle containing all bounding rectangles of the characters in e, then d is segmented
into e. If d is not segmented into any elements, we obtainthe scope of d, SC(d), by inflating BR(d) by two times thewidth of BR(d) on both the left and right hand sides (Fig. 6).
If there is an element whose bounding rectangle and SC(d)are intersecting, then d is segmented into the element.
There is some space on the left and the right hand side ofa function name, for example, sin, cos, max, and so on. Amatrix element is often divided at the spaces (Fig. 6). Therefore, if there is a function name on the head (or the tail) ofFigure 4. Example of a scope of a character.
On the right side, ‘C’ and ‘D’ are segmented
into the same element.

Figure 5. Example of a scope of a character‘−’ (a minus).

an element e, we obtain the scope of e, SC(e), by inflating
BR(e) by a half of Have on both the left and right hand sides,
and search for other elements whose bounding rectangles
intersect with SC(e), and combine e with these elements.

Data
Total matrices
Detection errorsof matrices
Success rates (%)
Segmentation errorsof elements (A)Number of all charactersof matrices
Success rates (%)
Segmentation errorsof elements (B)Success rates (%)
Construction errorsof networks
Success rates (%)
Total recognition errorsof matrices
Total success rates
of matrices (%)

Text
375

Journal
48

Total
423

162

18

95.7

95.8

95.7

126

18

5364

597

5961

99.8

99.0

99.7

5

4

9

98.6

91.3

97.8

6

4

10

98.3

91.3

97.5

7

4

1198.1

91.7

97.4

Table 1. Experimental results of the segmentation of elements, the construction of networks and the recognition of matrices.

3. Experimental Results
In order to evaluate our new methods, we implemented
them as part of our original OCR system ([4]). In ourmethod, when the segmentation of the matrix elements andthe construction of the networks are performed without error, the structure analysis is always exactly correct. Therefore, we evaluated the detection of the matrices, the segmentation of the elements and the construction of the networks using the system. We used two English and two
Japanese mathematics textbooks which included many matrices, mainly used to evaluate parameters, and two mathematical journals. We counted the numbers of errors withrespect to the 3 parts. We show the experimental results inFigure 6. Examples of a scope of a dot (left)
and a wrong segmentation of an element by
spaces on the both sides of function names(right).

Table 1.
In Table 1, the data “Detection errors” denotes the number of matrices which were not detected. The data “Segmentation errors (A)” denotes the number of characterswhich were segmented into the wrong elements. There
are several ways in which these errors can be counted.
For example, assume two elements ‘0’ and ‘−5’ are missegmented into the same element ‘0 − 5’. Considering thatthe ‘0’ is mis-segmented into the ‘-5’, the number of errors may be counted as 1, as that is the number of characters in the ‘0’, however if we consider that the ‘-5’ ismis-segmented into the ‘0’, then the number of errors may
be counted as 2, as that is the number of characters in the‘−5’. In this experiment, we recorded the minimum number among all the numbers which could be considered, because they are regarded as costs to correct the segmentation
errors. The success rate of (A) is the rate of properly segmented characters for all the characters of the detected matrices. The data “Segmentation errors (B)” denotes the number of detected matrices which have some mis-segmentedelements. Its success rate is the rate of properly segmented
matrices for all detected matrices. The data “Constructionerrors” denotes the number of matrices which have somemis-connected elements. The data “Total success rates” denotes the number of matrices which are detected and whoseFigure 7. Examples of success of the segmentation.

Figure 8. Examples of fails of the segmentation.

elements are properly segmented and connected in relation
to the total number of matrices.
Table 1 shows that the segmentation of elements has improved (the success rate in [1] was 75.3%). In Fig. 7, examples of success of the segmentation for complicated matrices are shown. However, several problems were found.
The misdetection is mainly caused by errors in the recognition of parentheses due to poor conditions of the prints, andcaused by a few very small matrices, which we did not consider. The parameters for our segmentation of elements aredetermined in practice. In particular, the segmentation rateof ‘−’ (a minus) depends heavily on the documents. At theleft side matrix in Fig. 8, the fractional lines are very shortand there are large spaces between their numerators and denominators, moreover the left space of the minus is much
longer than the right one, and at the right side one, the element ‘a1m ’ is too close to ‘a2m ’. These matrices can not beproperly segmented at present. There were often errors in
the connection of elements in simple matrices where repeat
symbols were not used, because the lengths and directionsof the repeat symbols are used to connect the elements. For
simple matrices, it is probably most effective for our method
to be combined with other methods.

4. Conclusion
We proposed a practical method for recognizing matrices
containing abbreviation symbols in the paper [1]. In the paper, we defined the domain to allow the matrices to contain

formula elements, area symbols, and repeat symbols in thematrix coordinates. The method consists of 4 parts; detection of matrices, segmentation of elements, construction ofnetworks and analysis of the matrix structure. We reportedthis work with a focus on the algorithms for constructing
the networks and for solving the simultaneous systems. We
obtained some measure of accuracy of the recognition ratein the experimental results of the paper, but it was not verysatisfactory. We found that most of the errors were causedin the segmentation of elements.
In this paper, we described in detail the detection of thematrices and an improved method for segmentation of theelements, and reported the experimental results. In the detection of matrices, we locate big parentheses using the average height of characters and search for parenthesis couples, and the experimental results indicate a very high accuracy. To segment characters in a matrix into elements, weuse the scope of a character, which is obtained by distances
between adjacent characters, and some parameters with respect to their features in the mathematical structure. The
experimental results showed an enormous improvement in
the segmentation of elements. However, the parameters aredetermined in practice, so the success of the segmentationof elements depends on the documents that are used.
For further improvement, we should determine the parameters statistically, using data from matrices recognizedby this method, and for simple matrices should try to combine our method with other independent recognition methods. Moreover, we also need to be able to recognize thedecorators of matrices which we excluded in this paper.

References[1] T. Kanahori and M. Suzuki, A Recognition Method ofMatrices by Using Variable Block Pattern Elements
Generating Rectangular Area, Graphic Recognition,
Lecture Notes in Computer Science 2390, Springer,
2002, pp. 320–329.
[2] D. Blostein and A. Grbavic, Recognition of Mathematical Notation, Handbook of Character Recognition
and Document Analysis, Eds. H. Buke, and P. Wang,
Word Scientific, 1997.
[3] M. Okamoto and H. Twaakyondo, Structure analysis and recognition of mathematical expressions, Proceedings of Third International Conference on Document Analysis and Recognition, Wontreal, 1995, pp.
430-437.
[4] Y. Eto, M. Sasai and M. Suzuki, Mathematical formula recognition using virtual link network, ICDAR
2001.