There are quite a few different notations you can use to write down...
**Chess Informant** was founded in 1966 in Belgrade, Yugoslavia (no...
### Belle
Belle was a chess computer developed by Ken Thompson and...
**Opening books** are databases of chess openings. In Computer Ches...
#### Chess Notations for computers
Fortunately nowadays computer l...
#### Skew angle
Skew angles usually result from placing an origina...
#### em unit
The *em* is a scalable unit that is equal to the curr...
Could somebody provide a visual to help me better understand the st...
+ **O-O** Castles Kingside
+ **O-O-O** Castles Queenside
*Cas...
552
IEEE
TRANSACTIONS ON
PATTERN
ANALYSIS AND MACHINE INTELLIGENCE.
VOL.
12.
NO. 6.
JUNE
1990
Reading
Chess
Absrracr-In an application of semantic analysis to images of ex-
tended passages of text, several volumes of a chess encyclopedia have
been read with high accuracy. Although carefully proofread, the hooks
were poorly printed and posed a severe challenge to conventional page
layout analysis and character-recognition methods. An experimental
page reader system carried out strictly top-down layout analysis for
identification of columns, lines, words, and characters. This proceeded
rapidly and reliably thanks to a recently-developed skew-estimation
technique. Resegmentation of broken, touching, and dirty characters
was handled in an efficient and integrated manner by a heuristic search
operating on isolated words. By analyzing the syntax of game descrip-
tions and applying the rules of chess, the error rate was reduced by a
factor of
30
from what was achievable through shape analysis alone.
Of the games with no typographical errors, 98% have been assigned a
legal interpretation, for an effective success rate of 99.995% on ap-
proximately one million characters (2850 games, 945 pages). We dis-
cuss several computer vision systems-integration issues suggested by
this experience.
Index
Terms-Character recognition, chess, document image anal-
ysis, layout analysis, semantics.
I.
INTRODUCTION
E present an engineering case study of a complete
computer vision system exhibiting unusually high
competency in a complex application, in part through the
use of computable semantics. The system is a page reader
and the application is the extraction of chess games from
the
Chess
Informant
[5], a series of volumes describing
games of theoretical interest.
The books are poorly printed, and pose a severe chal-
lenge to conventional layout analysis and character rec-
ognition methods. Novel features
of
our experimental
page reader include a strictly top-down layout analysis ap-
proach that works rapidly and reliably, largely owing to
a recently-developed technique for estimating the align-
ment angle of blocks of text. Preliminary classification is
performed before attempting to locate baselines or parti-
tion lines into words. Broken, touching, and dirty char-
acters are handled in an integrated manner by a shape-
guided heuristic operating on isolated words.
The games are extracted using a combination of layout
and syntactic rules. Each game is segmented into moves
(50
on average), and commentary is recognized and
stripped
off.
Each move consists of a move number and
two ply (half-moves), and each ply is described in three
Manuscript received May
23,
1988; revised October
12,
1989. Rec-
The authors are with
AT&T
Bell Laboratories,
600
Mountain Avenue,
IEEE
Log
Number 9034827.
ommended
for
acceptance by
C.
Y.
Suen.
Murray Hill, NJ 07974.
108.’
(R
76/a)
A
62
Luzem (01) 1982
1.
d4
Q€6 2. c4 e6 3. 433 c5
4.
d5
e&
5.
cd5 d6 6. Qc3 g6 7. g3 pg7 8. Ag2
0-0
9.
0-0 Qa6!?
10.
h3
[lo.
e4 &g4=]
Qc7
[RR
10.
..
Ee8!?
11.
4.f4 Qc7 12.
a4
Qe4
13.
Rcl
b5!
14. Bel Rb8
15.
ad2
g5!
16. Qde4 g€4 17. ab5
f5
18. Qd2 fg3
19.
fg3
@g5
20. Qfl
Qb5F
Csom
-
Sub%
Biile Herculane 1982; 11. Qd2!?]
11.
e4
Fig.
I.
A
sample
of
text
from
the
Clless
Infurinant
(shown
1.55
X
actual
size). This is a game’s header and opening moves, including two par-
enthetical comments in move number
IO.
KORTCHNOI
-
TRlXGOV
characters on average (see Fig. 1). By applying knowl-
edge of the rules of chess (the “semantics”), each move
is checked for legality directly in the context built up by
prior moves and indirectly through the consistency of later
moves. If the interpretations of moves suggested by shape
analysis are inadequate, alternatives are generated, again
by invoking the rules of chess. Even though this semantic
analysis is fully-backtracking, intolerable runtimes are
prevented by the high quality of the shape recognition
overall and a roughly uniform distribution of serious mis-
takes.
Of the first 142 games, two were flawed by typograph-
ical errors (editorial or typesetting mistakes), and the se-
mantic analysis failed, for assorted reasons, on three
more. The resulting
98%
of games correct
implies that
99.99% of the moves, and 99.995% of the characters,
were interpreted correctly. Without semantic analysis,
only
40%
of the games would have had a legal interpre-
tation, even though the character recognition rate due to
shape analysis alone is reasonably high (99.5
%).
Prior approaches to the detection and correction of er-
rors in text images have operated on
isolated words
from
natural languages, typically by means of dictionary look-
ups (e.g.,
[2]
[l
I]
1131) and character n-gram frequency
analysis (e.g., 1141
[I61
[7]). The lack of effective and
efficient algorithms for the analysis
of
natural language
has long frustrated the natural desire to extend this to sen-
tences. The comparative tractability of the semantics
of
chess offered an opportunity to experiment on
extended
sequences of text,
often consisting of hundreds of char-
acters, that make up complete games.
The exercise had two cooperating purposes: the first au-
thor’s principal motive was to experiment with contextual
reasoning in image analysis and the second author wished
0162-8828/90/0600-0552$01
.OO
0
1990
IEEE