Training Content
Resume:
IMPROVEMENT OF ZONE CONTENT
CLASSIFICATION BY USING BACKGROUND
ANALYSIS
Yalin Wang, Robert Haralick, and Ihsin T. Phillips
Department of Electrical Engineering
University of Washington Seattle, WA 98195 U.S.A.
Department of Computer Science/Software Engineering
Seattle University, Seattle, WA 98122 U.S.A.
ylwang, haralick, ***@******.**.**********.***
Abstract. This paper presents an improved zone content classi cation method.
Motivated by our novel background-analysis-based table identi cation research,
we added two new features to the feature vector from one previously published
method [7]. The new features are the total area of large horizontal and large ver-
tical blank blocks and the number of text glyphs in the zone. A binary decision
tree is used to assign a zone class on the basis of its feature vector. The train-
ing and testing data sets for the algorithm include images drawn from the
UWCDROM-III document image database. The classi er is able to classify each
given scienti c and technical document zone into one of the nine classes, text
classes (of font size pt and font size pt), math, table, halftone,
#!
"
map/drawing, ruling, logo, and others. The improved zone classi cation method
raised the accuracy rate to from and reduced the median false
' & &
($ %
alarm rate to from .
210
( % &
($ %
1 Problem Statement
Let be a set of zone entities. Let be a set of content labels, such as text, table,
3 4
math, etc. The function associates each element of with a label. The
A@875
9 36
4 B
function speci es measurements made on each element of, where is
HFEDC
G 9 36 3 G
the measurement space.
The zone content classi cation problem can be formulated as follows: Given a zone
set and a content label set, nd a classi cation function, that has the
3 4 RQPI5
4 9 36
maximum probability:
US
T T T
(1)
5 C YW3
XV W3
VV
In our current approach, we assume conditional independence between the zone
classi cations, so the probability in Equation 1 may be decomposed as
US
T T T US
T hT
g hT
g
(2)
5 C YW3
XV ca W3
b ` VV 5 C YV
X V
V
f0e0d
US
T hT
g hT
g
The problem can be solved by maximizing each individual probability 5 C YV
X V
V
pg
i
in Equation 2, where . 3
In our zone content classi cation experiment, the elements in set are zone groundtruth
3
entities from UWCDROM III document image database [6]. The elements of set are 4
text with font size pt, text with font size pt, math, table, halftone, map/drawing,
sq
tr vu
wr
hT
g g xg
i
ruling, logo, and others. is a feature vector generated for, where . We used
C V 3
a decision tree classi er to compute the probability in Equation 2 and make the assign-
ment.
2 Related Work and Paper Organization
A complete document image understanding system can transform paper documents into
a hierarchical representation of their structure and content. The transformed document
representation enables document interchange, editing, browsing, indexing, ling and
retrieval. The zone classi cation technique plays the key role in the success of such a
document understanding system. Not only is it useful for successive applications such
as OCR, table understanding, etc, but it can be used to assist and validate document
segmentation.
In the literature, Sivaramakrishnan et. al [7] extracted features for each zone such as
run length mean and variance, spatial mean and variance, fraction of the total number
of black pixels in the zone, and the zone width ratio for each zone. They used the
decision tree classi er to assign a zone class on the basis of its feature vector. They did
their experiments on document images from UWCDROM I image database. Liang
& w
wy
et. al [5] developed a feature based zone classi er using only the knowledge of the
widths and the heights of the connected components within a given zone. Le et. al [4]
proposed an automated labeling of zones from scanned images with labels such as titles,
authors, af liations and abstracts. The labeling is based on features calculated from
optical character recognition(OCR) output, neural network models, machine learning
methods, and a set of rules that is derived from an analysis of the page layout for each
journal and from generic typesetting knowledge for English text.
We developed a novel background-analysis-based table identi cation technique. We
repeated Sivaramakrishnan et. al s work [7] on a larger database with a goal to improve
its performance on table zone classi cation. Although some background analysis tech-
niques can be found in the literature([1],[2]), none of them, to our knowledge, has been
used in the table identi cation problem. We added two new features: the total area of
large horizontal and vertical blank blocks and the number of text glyphs in the given
zone, to the original feature vector. We improved the accuracy rate and reduced the false
alarm rates for most of the nine classes.
The rest of this paper is divided into sections. section 3 gives the de nitions of
large horizontal and large vertical blank blocks. The two new features are described in
section 4. A brief introduction to the decision tree classi er is given in section 5. The
experimental results are reported in section 6. Our conclusion and statement of future
work are discussed in section 7.
3 Some De nitions
E T
p
i
A polygonal area on a document page is given by a pair where speci es V
the label that designates the physical type of content, e.g. text block, text line, word, etc.,
and is the area enclosed by boundary of the polygon. The boundary of a polygon is
given as a sequence of line segments connecting the successive vertices of the polygon.
The vertices are given as a clockwise ordered list of points.
We use white-pixels to represent background pixels and black-pixels for foreground
pixels. In our background analysis, both foreground and background are represented
by polygonal areas. Noting that, for the purpose of zone classi cation, the foreground
polygonal areas are connected components and their bounding boxes and the back-
ground polygonal areas are blank blocks and their bounding boxes.
hT
De nition : Let represent a zone with rows and columns. Let be the
r V
coordinate of its lefttop vertex.
hT
e d gsgi
fhf m kjd
l i
p one
l i
` V X q q j
q
De nition : A horizontal white run is a sequence of horizontally contiguous white-
r s
pixels whose starting and ending pixels must have a black-pixel or the zone border
as its neighbor.
2 y vwv &)h T
x e x dT uuu e dT
ts
` V V
V
2 hT
ze zd i d
z d
{z Ye
z Ye
l {z vwv
uuu T
ed
where,,, for, and pixel,
V ` ` r ~}
r` V
x x T
d
e
must have a black pixel or the zone border on its left and right side, respec-
V
tively. Similar to the run-length encoding, for each run, the location of the starting
T
pixel of the run and its horizontal length must be recorded. We call them as Row, s
V
T T
Column, and Length . s
V s
V
De nition : A horizontal blank block is a sequence of horizontal white runs
on contiguous rows, whose starting point column coordinates and lengths are the
same.
x vwwY T
uuu
` s
s V
zT hz T
{ zT z T
{ zT
l
where Row Row, Column Column, Length
s V
` s V r V s
` s V !V s
`
z T
{ wvwY
uuu
Length, for .
s
V p}
r`
Clearly, the same idea can be applied to de ne vertical white run and vertical white
blank block. The difference will be that we use vertically contiguous pixels to de ne
vertical white run and vertical runs on contiguous columns for vertical white blank
block. h
De nition : A horizontal blank block, with lefttop vertex coordinate
2
` 2
& T, is a large horizontal blank block if and only if it satis es the following
V
conditions:
its row numbers and column numbers are large enough compared with the cur-
&
0
u
rent zone. Speci cally,, where is . This number was statistically
r
determined by our experiment on another table data set;
It does not touch left or right side of the zone bounding box, i.e. and
`
l
l y
;
` 2
where is the column number in the zone.
h
De nition : A vertical blank block, with lefttop vertex coordinate
8
` Y
& T, is a large vertical blank block if and only if it satis es the following
V
conditions:
Its row number and column number are large enough compared with the cur-
rent zone. Speci cally, and, where and are the
x
x
p
~
median height and median width of text glyphs in the zone. is empirically
u
determined as ; r
It does not touch left or right side of the zone bounding box, i.e. and `
l
l y
;
` 2
where is the column number in the zone.
4 Two New Features for Zone Content Classi er
Our goal is to improve table zone classi cation using our background-analysis-based
table identi cation technique. The most distinguished feature of a table zone is the
large gaps between its columns. Even for the tables with rulings, we will have gaps if
we remove the rulings. On the background analysis, we can expect to nd both large
horizontal and large vertical blank blocks inside the table zones.
On the other hand, we can also nd many large horizontal and large vertical blank
blocks in drawing/map zones. To discriminate table zones and drawing/map zones, we
added one more feature, the number of text glyphs in a zone. The so-called text glyphs
are not from any OCR output. They are outputs of a statistical glyph lter. The inputs
of this lter are the glyphs after nding connected component operation. The lter
classi es each glyph into one of two classes: text glyph and non-text glyph. The lter
uses a statistical method to classify glyphs and was extensively trained on UWCDROM
III document image database.
The newly added features are:
1. The total area of large horizontal and large vertical blank blocks, A.
) d
T
`
V
0e
where or and .
) o
` X ` m
kD
U m
q
2. The number of text glyphs in this zone, N, normalized by the zone area.
d
T
j
V
Figure 1 illustrates two zone examples showing the overlayed bounding boxes of large
horizontal blank blocks, large vertical blank blocks and text glyphs.
Together with the features used in Sivaramakrishnan et. al s work [7], we have a
y
total of features. We feed the generated feature vector to a binary decision tree to get
0
w
the zone classi cation.
(a)
(b)
Fig. 1. Illustrates the example bounding boxes of large horizontal blank blocks, large
vertical blank blocks, and text glyphs. The so-called text glyphs are labeled by a statis-
tical glyph lter. (a) a table zone example; (b) a map/drawing zone example.
5 Decision Tree Classi er
A decision tree classi er makes the assignment through a hierarchical decision proce-
dure. The classi cation process can be described by means of a tree, in which at least
one terminal node is associated with each class and nonterminal nodes represent various
collections of mixed classes.
For the construction of a decision tree, we need a training set of feature vectors
yYY
with true class labels. Let be a unit-training set to be
sn y H
r ` 6 ` q
used to design a binary tree classi er. Each unit has an associated measurement
x x
with known true class. At any non-terminal node, let be the set of classes still x
x x x
yY Y
possible for a unit at node . Let be the subset of `
D 6
r` q
e
training units associated with node . If the number of units for class in node is
x x x
denoted by, we must have . s`
x
Now we describe how the decision rule works at node . Consider unit which
x x
T
has measurement vector . If the discriminant function is less than or equal to a
x x 5 V x
2 z
threshold, then is assigned to class, otherwise it is assigned to class . An w
x
assignment to means that a unit descends to the left child node and an assignment
v
x
2 z x
to can be understood in a similar way. Given a discriminant function, the units x x 5 jx
x
hT
T
yYY
in are sorted in such a way that for . Let
5 V
5q V
r x` r
2
be the true classes associated with the measurement vectors . Then a set of candidate
x
thresholds for the decision rules is de ned by
x x
hT
T
x x
x
5 V 5 V
`
` X
r
x
For each threshold value, unit is classi ed by using the decision rule speci ed above. x
e
We count the number of samples assigned to whose true class is and we v x
e
2vz
count the number of samples assigned to whose true class is, that is,
x
x x
hT
e
and
X x v`
5
kaV x
q ` x q
hT
e
and
X v`
V
5 ` q
x
Let be the total number of samples assigned to and be the total number of
v
x
vz
samples assigned to, that is,
and
` `
x
S
We de ne the impurity of the assignment made by node to be
x
j
S
0wE
n
0w
`
x
S
The discriminant threshold is chosen such that it minimizes the impurity value .
The impurity is such that it gives a minimum value when the training samples are com-
pletely separable.
The learned discriminant function splits the training subset into two subsets and
generates two child nodes. The process is repeated at each newly generated child node
until a stopping condition is satis ed, and the node is declared as a terminal node based
on a majority vote. The maximum impurity reduction, the maximum depth of the tree,
and minimum number of samples are used as stopping conditions.
At the testing stage, a feature vector is the input to a decision tree, a decision is made
at every non-terminal node as to what path the feature vector will take. This process is
continued until the feature vector reaches a terminal node of the tree, where a class is
assigned to it.
6 Experiments and Results
A hold-out method is used for the error estimation in our experiment. We divide the
data set into parts, train on the rst parts and then test on the th part. Then
r
hT
train on the other parts, omitting the th part. Continue the training and
r )r
V
testing, each time omitting one part from the decision tree construction and then testing
on the omitted part. Then the combined part results are put together to estimate the
total error rate [3].
The output of the decision tree is compared with the zone labels from the ground
truth in order to evaluate the performance of the algorithm. A contingency table is
computed to indicate the number of zones of a particular class label that are identi ed
as members of one of nine classes. The rows of the contingency table represent the true
classes and the columns represent the assigned classes. The cell at row r and column c is
the number of zones whose true class is r while its assigned class is c. We also compute
four rates here: Correct Recognition Rate(CR), Mis-recognition Rate(MR), False Alarm
Rate(FR), Accuracy Rate(AR). Suppose we only have two classes: a and b. The possible
true- and detected-state combination is shown in Table 1.
Assigned Class
True Class
Contact this candidate