%!PS-Adobe-3.0
%%Title: (File for World Scientific)
%%Creator: (Microsoft Word: LaserWriter 8 8.2)
%%CreationDate: (14:54 Wednesday, April 1, 1998)
%%For: ()
%%Pages: 26
%%DocumentFonts: Times-Roman Symbol Times-Bold Times-Italic Times-BoldItalic
%%DocumentNeededFonts: Times-Roman Symbol Times-Bold Times-Italic Times-BoldItalic
%%DocumentSuppliedFonts:
%%DocumentData: Clean7Bit
%%PageOrder: Ascend
%%Orientation: Portrait
%%DocumentMedia: Default 612 792 0 () ()
%ADO_ImageableArea: 30 31 582 761
%%EndComments
userdict begin/dscInfo 5 dict dup begin
/Title(File for World Scientific)def
/Creator(Microsoft Word: LaserWriter 8 8.2)def
/CreationDate(14:54 Wednesday, April 1, 1998)def
/For()def
/Pages 1 def
end def end
/md 223 dict def md begin/currentpacking where {pop /sc_oldpacking currentpacking def true setpacking}if
%%BeginFile: adobe_psp_basic
%%Copyright: Copyright 1990-1993 Adobe Systems Incorporated. All Rights Reserved.
/bd{bind def}bind def
/xdf{exch def}bd
/xs{exch store}bd
/ld{load def}bd
/Z{0 def}bd
/T/true
/F/false
/:L/lineto
/lw/setlinewidth
/:M/moveto
/rl/rlineto
/rm/rmoveto
/:C/curveto
/:T/translate
/:K/closepath
/:mf/makefont
/gS/gsave
/gR/grestore
/np/newpath
14{ld}repeat
/$m matrix def
/av 81 def
/por true def
/normland false def
/psb-nosave{}bd
/pse-nosave{}bd
/us Z
/psb{/us save store}bd
/pse{us restore}bd
/level2
/languagelevel where
{
pop languagelevel 2 ge
}{
false
}ifelse
def
/featurecleanup
{
stopped
cleartomark
countdictstack exch sub dup 0 gt
{
{end}repeat
}{
pop
}ifelse
}bd
/noload Z
/startnoload
{
{/noload save store}if
}bd
/endnoload
{
{noload restore}if
}bd
level2 startnoload
/setjob
{
statusdict/jobname 3 -1 roll put
}bd
/setcopies
{
userdict/#copies 3 -1 roll put
}bd
level2 endnoload level2 not startnoload
/setjob
{
1 dict begin/JobName xdf currentdict end setuserparams
}bd
/setcopies
{
1 dict begin/NumCopies xdf currentdict end setpagedevice
}bd
level2 not endnoload
/pm Z
/mT Z
/sD Z
/realshowpage Z
/initializepage
{
/pm save store mT concat
}bd
/endp
{
pm restore showpage
}def
/$c/DeviceRGB def
/rectclip where
{
pop/rC/rectclip ld
}{
/rC
{
np 4 2 roll
:M
1 index 0 rl
0 exch rl
neg 0 rl
:K
clip np
}bd
}ifelse
/rectfill where
{
pop/rF/rectfill ld
}{
/rF
{
gS
np
4 2 roll
:M
1 index 0 rl
0 exch rl
neg 0 rl
fill
gR
}bd
}ifelse
/rectstroke where
{
pop/rS/rectstroke ld
}{
/rS
{
gS
np
4 2 roll
:M
1 index 0 rl
0 exch rl
neg 0 rl
:K
stroke
gR
}bd
}ifelse
%%EndFile
%%BeginFile: adobe_psp_colorspace_level1
%%Copyright: Copyright 1991-1993 Adobe Systems Incorporated. All Rights Reserved.
/G/setgray ld
/:F/setrgbcolor ld
%%EndFile
level2 startnoload
%%BeginFile: adobe_psp_patterns_level1
%%Copyright: Copyright 1991-1993 Adobe Systems Incorporated. All Rights Reserved.
/patfreq Z
/patangle Z
/bk Z
/fg Z
/docolorscreen Z
/graystring Z
/pattransf{}def
/initQDpatterns
{
/patfreq 9.375 store
/patangle
1 0 $m defaultmatrix dtransform
exch atan
por not
{90 add}if
normland{180 add}if
store
:a
}def
/docolorscreen
/setcolorscreen where
{
pop/currentcolorscreen where
{
pop/setcmykcolor where
{
pop true
}{
false
}ifelse
}{
false
}ifelse
}{
false
}ifelse
def
/setgraypattern
{
/graystring xs
patfreq
patangle
{
1 add
4 mul
cvi
graystring
exch get
exch
1 add 4 mul
cvi
7 sub
bitshift
1 and
}setscreen
64 div setgray
}bd
/:b
{
/pattransf load settransfer
pop pop pop
setgraypattern
}bd
docolorscreen startnoload
/screensave 5 array def
/:a{currentgray currentscreen currenttransfer screensave astore pop}bd
/:e{screensave aload pop settransfer setscreen setgray}bd
/:d
{
pop pop pop
/pattransf load settransfer
setgraypattern 8{pop}repeat
}bd
/:c
/:d ld
docolorscreen endnoload docolorscreen not startnoload
/screensave 20 array def
/:a{currentcmykcolor currentcolorscreen currentcolortransfer screensave astore pop}bd
/:e{screensave aload pop setcolortransfer setcolorscreen setcmykcolor}bd
/rstring Z
/grstring Z
/blstring Z
/convroll{64 div 4 -1 roll}bd
/setcolorpattern
{
/graystring xs
/blstring xs
/grstring xs
/rstring xs
patfreq
patangle
{
1 add 4 mul cvi rstring
exch get exch 1 add 4 mul
cvi 7 sub bitshift 1 and
}
patfreq
patangle
{
1 add 4 mul cvi grstring
exch get exch 1 add 4 mul
cvi 7 sub bitshift 1 and
}
patfreq
patangle
{
1 add 4 mul cvi blstring
exch get exch 1 add 4 mul
cvi 7 sub bitshift 1 and
}
patfreq
patangle
{
1 add 4 mul cvi graystring
exch get exch 1 add 4 mul
cvi 7 sub bitshift 1 and
}
setcolorscreen
convroll convroll convroll convroll
setcmykcolor
}bd
/:d
{
pop pop pop
/pattransf load settransfer
pop pop setcolorpattern
}bd
/:c
/:d ld
docolorscreen not endnoload
%%EndFile
level2 endnoload level2 not startnoload
%%BeginFile: adobe_psp_patterns_level2
%%Copyright: Copyright 1990-1993 Adobe Systems Incorporated. All Rights Reserved.
/pmtx Z
/BGnd Z
/FGnd Z
/PaintData Z
/PatternMtx Z
/PatHeight Z
/PatWidth Z
/$d Z
/savecolor 4 array def
/savecolorspace Z
/:a{
mark 0 0 0 currentcolor savecolor astore pop cleartomark
/savecolorspace currentcolorspace store
}bd
/:e{
savecolorspace setcolorspace
mark savecolor aload pop setcolor cleartomark
}bd
/initQDpatterns
{
gS
initmatrix
mT dup 4 get exch 5 get :T
1 0 dtransform round exch round exch idtransform
dup mul exch dup mul exch add sqrt
0 1 dtransform round exch round exch idtransform
dup mul exch dup mul exch add sqrt
neg
scale
0
por not{90 add}if
normland{180 add}if
rotate
matrix currentmatrix
gR
/pmtx xs
:a
}bd
/:t
{
14 dict begin
/BGnd xdf
/FGnd xdf
/PaintData xdf
/PatternType 1 def
/PaintType 1 def
/BBox[0 0 1 1]def
/TilingType 1 def
/XStep 1 def
/YStep 1 def
/PatternMtx[24 0 0 24 0 0]def
/PaintProc
BGnd null ne
{
{
begin
BGnd aload pop :F
0 0 1 1 rF
FGnd aload pop :F
24 24 true PatternMtx PaintData imagemask
end
}
}{
{
begin
FGnd aload pop :F
24 24 true PatternMtx PaintData imagemask
end
}
}ifelse
def
currentdict
PatternMtx
end
gS $c setcolorspace pmtx setmatrix makepattern gR
}bd
/:u
{
14 dict begin
/$d 8 dict def
/PatternType 1 def
/PaintType 1 def
/BBox[0 0 1 1]def
/TilingType 1 def
/XStep 1 def
/YStep 1 def
/PaintData xdf
/PatHeight xdf
/PatWidth xdf
/PatternMtx[PatWidth 0 0 PatHeight 0 0]def
$d begin
/ImageType 1 def
/MultipleDataSource false def
/Height PatHeight def
/Width PatWidth def
/Decode[0 1 0 1 0 1]def
/ImageMatrix PatternMtx def
/DataSource PaintData def
/BitsPerComponent 8 def
end
/PaintProc
{
begin
$d image
end
}def
currentdict
PatternMtx
end
gS $c setcolorspace pmtx setmatrix makepattern gR
}bd
/bk[1 1 1]def
/fg[0 0 0]def
/:b{
:t
setpattern
pop pop
}bd
/:d{
:t
setpattern
10{pop}repeat
}bd
/:c{
:u
setpattern
10{pop}repeat
}bd
%%EndFile
level2 not endnoload
%%BeginFile: adobe_psp_uniform_graphics
%%Copyright: Copyright 1990-1993 Adobe Systems Incorporated. All Rights Reserved.
/@a
{
np :M 0 rl :L 0 exch rl 0 rl :L fill
}bd
/@b
{
np :M 0 rl 0 exch rl :L 0 rl 0 exch rl fill
}bd
/arct where
{
pop
}{
/arct
{
arcto pop pop pop pop
}bd
}ifelse
/x1 Z
/x2 Z
/y1 Z
/y2 Z
/rad Z
/@q
{
/rad xs
/y2 xs
/x2 xs
/y1 xs
/x1 xs
np
x2 x1 add 2 div y1 :M
x2 y1 x2 y2 rad arct
x2 y2 x1 y2 rad arct
x1 y2 x1 y1 rad arct
x1 y1 x2 y1 rad arct
fill
}bd
/@s
{
/rad xs
/y2 xs
/x2 xs
/y1 xs
/x1 xs
np
x2 x1 add 2 div y1 :M
x2 y1 x2 y2 rad arct
x2 y2 x1 y2 rad arct
x1 y2 x1 y1 rad arct
x1 y1 x2 y1 rad arct
:K
stroke
}bd
/@i
{
np 0 360 arc fill
}bd
/@j
{
gS
np
:T
scale
0 0 .5 0 360 arc
fill
gR
}bd
/@e
{
np
0 360 arc
:K
stroke
}bd
/@f
{
np
$m currentmatrix
pop
:T
scale
0 0 .5 0 360 arc
:K
$m setmatrix
stroke
}bd
/@k
{
gS
np
:T
0 0 :M
0 0 5 2 roll
arc fill
gR
}bd
/@l
{
gS
np
:T
0 0 :M
scale
0 0 .5 5 -2 roll arc
fill
gR
}bd
/@m
{
np
arc
stroke
}bd
/@n
{
np
$m currentmatrix
pop
:T
scale
0 0 .5 5 -2 roll arc
$m setmatrix
stroke
}bd
%%EndFile
%%BeginFile: adobe_psp_basic_text
%%Copyright: Copyright 1990-1993 Adobe Systems Incorporated. All Rights Reserved.
/S/show ld
/A{
0.0 exch ashow
}bd
/R{
0.0 exch 32 exch widthshow
}bd
/W{
0.0 3 1 roll widthshow
}bd
/J{
0.0 32 4 2 roll 0.0 exch awidthshow
}bd
/V{
0.0 4 1 roll 0.0 exch awidthshow
}bd
/fcflg true def
/fc{
fcflg{
vmstatus exch sub 50000 lt{
(%%[ Warning: Running out of memory ]%%\r)print flush/fcflg false store
}if pop
}if
}bd
/$f[1 0 0 -1 0 0]def
/:ff{$f :mf}bd
/MacEncoding StandardEncoding 256 array copy def
MacEncoding 39/quotesingle put
MacEncoding 96/grave put
/Adieresis/Aring/Ccedilla/Eacute/Ntilde/Odieresis/Udieresis/aacute
/agrave/acircumflex/adieresis/atilde/aring/ccedilla/eacute/egrave
/ecircumflex/edieresis/iacute/igrave/icircumflex/idieresis/ntilde/oacute
/ograve/ocircumflex/odieresis/otilde/uacute/ugrave/ucircumflex/udieresis
/dagger/degree/cent/sterling/section/bullet/paragraph/germandbls
/registered/copyright/trademark/acute/dieresis/notequal/AE/Oslash
/infinity/plusminus/lessequal/greaterequal/yen/mu/partialdiff/summation
/product/pi/integral/ordfeminine/ordmasculine/Omega/ae/oslash
/questiondown/exclamdown/logicalnot/radical/florin/approxequal/Delta/guillemotleft
/guillemotright/ellipsis/space/Agrave/Atilde/Otilde/OE/oe
/endash/emdash/quotedblleft/quotedblright/quoteleft/quoteright/divide/lozenge
/ydieresis/Ydieresis/fraction/currency/guilsinglleft/guilsinglright/fi/fl
/daggerdbl/periodcentered/quotesinglbase/quotedblbase/perthousand
/Acircumflex/Ecircumflex/Aacute/Edieresis/Egrave/Iacute/Icircumflex/Idieresis/Igrave
/Oacute/Ocircumflex/apple/Ograve/Uacute/Ucircumflex/Ugrave/dotlessi/circumflex/tilde
/macron/breve/dotaccent/ring/cedilla/hungarumlaut/ogonek/caron
MacEncoding 128 128 getinterval astore pop
level2 startnoload
/copyfontdict
{
findfont dup length dict
begin
{
1 index/FID ne{def}{pop pop}ifelse
}forall
}bd
level2 endnoload level2 not startnoload
/copyfontdict
{
findfont dup length dict
copy
begin
}bd
level2 not endnoload
md/fontname known not{
/fontname/customfont def
}if
/Encoding Z
/:mre
{
copyfontdict
/Encoding MacEncoding def
fontname currentdict
end
definefont :ff def
}bd
/:bsr
{
copyfontdict
/Encoding Encoding 256 array copy def
Encoding dup
}bd
/pd{put dup}bd
/:esr
{
pop pop
fontname currentdict
end
definefont :ff def
}bd
/scf
{
scalefont def
}bd
/scf-non
{
$m scale :mf setfont
}bd
/ps Z
/fz{/ps xs}bd
/sf/setfont ld
/cF/currentfont ld
/mbf
{
/makeblendedfont where
{
pop
makeblendedfont
/ABlend exch definefont
}{
pop
}ifelse
def
}def
%%EndFile
%%BeginFile: adobe_psp_derived_styles
%%Copyright: Copyright 1990-1993 Adobe Systems Incorporated. All Rights Reserved.
/wi
version(23.0)eq
{
{
gS 0 0 0 0 rC stringwidth gR
}bind
}{
/stringwidth load
}ifelse
def
/$o 1. def
/gl{$o G}bd
/ms{:M S}bd
/condensedmtx[.82 0 0 1 0 0]def
/:mc
{
condensedmtx :mf def
}bd
/extendedmtx[1.18 0 0 1 0 0]def
/:me
{
extendedmtx :mf def
}bd
/basefont Z
/basefonto Z
/dxa Z
/dxb Z
/dxc Z
/dxd Z
/dsdx2 Z
/bfproc Z
/:fbase
{
dup/FontType get 0 eq{
dup length dict begin
dup{1 index/FID ne 2 index/UniqueID ne and{def}{pop pop}ifelse}forall
/FDepVector exch/FDepVector get[exch/:fbase load forall]def
}/bfproc load ifelse
/customfont currentdict end definefont
}bd
/:mo
{
/bfproc{
dup dup length 2 add dict
begin
{
1 index/FID ne 2 index/UniqueID ne and{def}{pop pop}ifelse
}forall
/PaintType 2 def
/StrokeWidth .012 0 FontMatrix idtransform pop def
/customfont currentdict
end
definefont
8 dict begin
/basefonto xdf
/basefont xdf
/FontType 3 def
/FontMatrix[1 0 0 1 0 0]def
/FontBBox[0 0 1 1]def
/Encoding StandardEncoding def
/BuildChar
{
exch begin
basefont setfont
( )dup 0 4 -1 roll put
dup wi
setcharwidth
0 0 :M
gS
gl
dup show
gR
basefonto setfont
show
end
}def
}store :fbase
}bd
/:mso
{
/bfproc{
7 dict begin
/basefont xdf
/FontType 3 def
/FontMatrix[1 0 0 1 0 0]def
/FontBBox[0 0 1 1]def
/Encoding StandardEncoding def
/BuildChar
{
exch begin
sD begin
/dxa 1 ps div def
basefont setfont
( )dup 0 4 -1 roll put
dup wi
1 index 0 ne
{
exch dxa add exch
}if
setcharwidth
dup 0 0 ms
dup dxa 0 ms
dup dxa dxa ms
dup 0 dxa ms
gl
dxa 2. div dup ms
end
end
}def
}store :fbase
}bd
/:ms
{
/bfproc{
dup dup length 2 add dict
begin
{
1 index/FID ne 2 index/UniqueID ne and{def}{pop pop}ifelse
}forall
/PaintType 2 def
/StrokeWidth .012 0 FontMatrix idtransform pop def
/customfont currentdict
end
definefont
8 dict begin
/basefonto xdf
/basefont xdf
/FontType 3 def
/FontMatrix[1 0 0 1 0 0]def
/FontBBox[0 0 1 1]def
/Encoding StandardEncoding def
/BuildChar
{
exch begin
sD begin
/dxb .05 def
basefont setfont
( )dup 0 4 -1 roll put
dup wi
exch dup 0 ne
{
dxb add
}if
exch setcharwidth
dup dxb .01 add 0 ms
0 dxb :T
gS
gl
dup 0 0 ms
gR
basefonto setfont
0 0 ms
end
end
}def
}store :fbase
}bd
/:mss
{
/bfproc{
7 dict begin
/basefont xdf
/FontType 3 def
/FontMatrix[1 0 0 1 0 0]def
/FontBBox[0 0 1 1]def
/Encoding StandardEncoding def
/BuildChar
{
exch begin
sD begin
/dxc 1 ps div def
/dsdx2 .05 dxc 2 div add def
basefont setfont
( )dup 0 4 -1 roll put
dup wi
exch dup 0 ne
{
dsdx2 add
}if
exch setcharwidth
dup dsdx2 .01 add 0 ms
0 .05 dxc 2 div sub :T
dup 0 0 ms
dup dxc 0 ms
dup dxc dxc ms
dup 0 dxc ms
gl
dxc 2 div dup ms
end
end
}def
}store :fbase
}bd
/:msb
{
/bfproc{
7 dict begin
/basefont xdf
/FontType 3 def
/FontMatrix[1 0 0 1 0 0]def
/FontBBox[0 0 1 1]def
/Encoding StandardEncoding def
/BuildChar
{
exch begin
sD begin
/dxd .03 def
basefont setfont
( )dup 0 4 -1 roll put
dup wi
1 index 0 ne
{
exch dxd add exch
}if
setcharwidth
dup 0 0 ms
dup dxd 0 ms
dup dxd dxd ms
0 dxd ms
end
end
}def
}store :fbase
}bd
/italicmtx[1 0 -.212557 1 0 0]def
/:mi
{
italicmtx :mf def
}bd
/:v
{
[exch dup/FontMatrix get exch
dup/FontInfo known
{
/FontInfo get
dup/UnderlinePosition known
{
dup/UnderlinePosition get
2 index 0
3 1 roll
transform
exch pop
}{
.1
}ifelse
3 1 roll
dup/UnderlineThickness known
{
/UnderlineThickness get
exch 0 3 1 roll
transform
exch pop
abs
}{
pop pop .067
}ifelse
}{
pop pop .1 .067
}ifelse
]
}bd
/$t Z
/$p Z
/$s Z
/:p
{
aload pop
2 index mul/$t xs
1 index mul/$p xs
.012 mul/$s xs
}bd
/:m
{gS
0 $p rm
$t lw
0 rl stroke
gR
}bd
/:n
{
gS
0 $p rm
$t lw
0 rl
gS
gl
stroke
gR
strokepath
$s lw
/setstrokeadjust where{pop
currentstrokeadjust true setstrokeadjust stroke setstrokeadjust
}{
stroke
}ifelse
gR
}bd
/:o
{gS
0 $p rm
$t 2 div dup rm
$t lw
dup 0 rl
stroke
gR
:n
}bd
%%EndFile
%%BeginFile: adobe_psp_dashes
%%Copyright: Copyright 1990-1993 Adobe Systems Incorporated. All Rights Reserved.
/:q/setdash ld
/:r{
np
:M
:L
stroke
}bd
/nodash[]def
/qdenddash
{
nodash 0 setdash
}bd
%%EndFile
/currentpacking where {pop sc_oldpacking setpacking}if end
%%EndProlog
%%BeginSetup
md begin
countdictstack[{
%%BeginFeature: *ManualFeed False
level2 {1 dict dup /ManualFeed false put setpagedevice}{statusdict begin /manualfeed false store end} ifelse
%%EndFeature
}featurecleanup
countdictstack[{
%%BeginFeature: *InputSlot Upper
%%EndFeature
}featurecleanup
countdictstack[{
%%BeginFeature: *PageRegion LetterSmall
level2 {
2 dict dup /PageSize [612 792] put dup /ImagingBBox [30 31 582 761] put setpagedevice
}{
/lettersmall where {pop lettersmall} {letterR} ifelse
} ifelse
%%EndFeature
}featurecleanup
()setjob
/mT[1 0 0 -1 30 761]def
initQDpatterns
/sD 16 dict def
300 level2{1 dict dup/WaitTimeout 4 -1 roll put setuserparams}{statusdict/waittimeout 3 -1 roll put}ifelse
%%IncludeFont: Times-Roman
%%IncludeFont: Symbol
%%IncludeFont: Times-Bold
%%IncludeFont: Times-Italic
%%IncludeFont: Times-BoldItalic
/f0_1/Times-Roman
:mre
/f0_13 f0_1 13 scf
/f0_12 f0_1 12 scf
/f0_10 f0_1 10 scf
/f0_9 f0_1 9 scf
/f0_8 f0_1 8 scf
/f0_7 f0_1 7 scf
/f0_6 f0_1 6 scf
/f0_5 f0_1 5 scf
/f0_4 f0_1 4 scf
/f1_1/Symbol
:bsr
240/apple pd
:esr
/f1_12 f1_1 12 scf
/f1_10 f1_1 10 scf
/f1_9 f1_1 9 scf
/f1_8 f1_1 8 scf
/f1_6 f1_1 6 scf
/f2_1/Times-Bold
:mre
/f2_10 f2_1 10 scf
/f2_9 f2_1 9 scf
/f3_1 f1_1
def
/f3_10 f3_1 10 scf
/f3_9 f3_1 9 scf
/f4_1/Times-Italic
:mre
/f4_10 f4_1 10 scf
/f4_9 f4_1 9 scf
/f4_8 f4_1 8 scf
/f4_7 f4_1 7 scf
/f4_6 f4_1 6 scf
/f5_1 f1_1
:mi
/f5_10 f5_1 10 scf
/f5_9 f5_1 9 scf
/f5_8 f5_1 8 scf
/f6_1/Times-BoldItalic
:mre
/f6_10 f6_1 10 scf
/Courier findfont[10 0 0 -10 0 0]:mf setfont
%%EndSetup
%%Page: 1 1
%%BeginPageSetup
initializepage
(; page: 1 of 26)setjob
%%EndPageSetup
gS 0 0 552 730 rC
111 62 :M
f0_8 sf
.3 .03(Handbook on Optical Character Recognition and Document Image Analysis, pp. 000-000)J
111 72 :M
.044 .004(Eds. P.S.P. Wang and H. Bunke)J
111 82 :M
-.012(\251 World Scientific Publishing Company, 1996)A
246 161 :M
f0_10 sf
.498 .05(CHAPTER 22)J
-1 -1 242 150 1 1 241 149 @b
-1 -1 242 150 1 1 241 149 @b
242 150 -1 1 309 149 1 242 149 @a
-1 -1 310 150 1 1 309 149 @b
-1 -1 310 150 1 1 309 149 @b
-1 -1 242 164 1 1 241 163 @b
-1 -1 242 164 1 1 241 163 @b
242 164 -1 1 309 163 1 242 163 @a
-1 -1 310 164 1 1 309 163 @b
-1 -1 310 164 1 1 309 163 @b
-1 -1 242 163 1 1 241 150 @b
-1 -1 310 163 1 1 309 150 @b
146 188 :M
f2_10 sf
3.021 .302(RECOGNITION OF MATHEMATICAL NOTATION)J
f0_7 sf
0 -3 rm
(*)S
0 3 rm
174 229 :M
f0_10 sf
-.051(DOROTHEA BLOSTEIN)A
f0_7 sf
0 -3 rm
S
0 3 rm
f0_10 sf
-.046( and ANN GRBAVEC)A
193 242 :M
f4_8 sf
.143 .014(Department of Computing and Information Science)J
182 255 :M
-.012(Queen\325s University, Kingston, Ontario, Canada K7L 3N6)A
132 285 :M
f0_9 sf
1.583 .158(Recognition of mathematical notation involves two main components: symbol)J
114 295 :M
2.593 .259(recognition and symbol-arrangement analysis. Symbol-arrangement analysis is)J
114 305 :M
1.03 .103(particularly difficult for mathematics, due to the subtle use of space in this notation.)J
114 315 :M
.909 .091(We begin with a general discussion of the mathematics-recognition problem. This is)J
114 325 :M
1.436 .144(followed by a review of existing approaches to mathematics recognition, including)J
114 335 :M
2.375 .237(syntactic methods, projection-profile cutting, graph rewriting, and procedurally-)J
114 345 :M
1.706 .171(coded math syntax. A central problem in all recognition approaches is to find a)J
114 355 :M
3.266 .327(convenient, expressive, and effective method for representing the notational)J
114 365 :M
1.692 .169(conventions of mathematics.)J
114 385 :M
f4_9 sf
1.169(Keywords)A
f0_9 sf
4.455 .445(: Computer recognition of mathematical notation; Notational)J
114 395 :M
4.527 .453(conventions; Symbol recognition; Symbol-arrangement analysis; Syntactic)J
114 405 :M
1.284 .128(methods; Projection-profile cutting; Graph rewriting.)J
96 434 :M
f2_10 sf
.826(1.\312Introduction)A
111 452 :M
f0_10 sf
.114 .011(Over the centuries, people have developed a specialized two-dimensional notation for)J
96 465 :M
.177 .018(communicating with each other about mathematics. The notation is designed to represent)J
96 478 :M
1.537 .154(ideas in a way that aids mathematical thinking and visualization. It is natural and)J
96 491 :M
.844 .084(convenient for people to communicate with computers using this same notation. This)J
96 504 :M
4.433 .443(involves conversion between mathematical notation and internal computer)J
96 517 :M
-.033(representations. Under current technology, two-dimensional mathematical notation can be)A
96 530 :M
.799 .08(generated by computers, but recognition facilities are not widely available: the task of)J
96 543 :M
.534 .053(translating mathematics into a computer-processable form usually falls to a human user)J
96 556 :M
.752 .075(\(Fig. 1\). By relieving the user of the burden of translation, a mathematics recognition)J
96 569 :M
.694 .069(system enhances the usefulness of computers as a tool for mathematics and document-)J
96 582 :M
-.062(handling.)A
-4126 -4126 -1 1 -4124 -4126 1 -4126 -4127 @a
96 601.24 -.24 .24 239.24 601 .24 96 601 @a
96 611 :M
f0_7 sf
.101(*)A
f0_8 sf
0 3 rm
.413 .041( This research is supported by Canada\325s Natural Sciences and Engineering Research Council.)J
0 -3 rm
96 621 :M
f0_7 sf
.061A
f0_8 sf
0 3 rm
.441 .044( blostein@qucis.queensu.ca)J
0 -3 rm
endp
%%Page: 2 2
%%BeginPageSetup
initializepage
(; page: 2 of 26)setjob
%%EndPageSetup
-30 -31 :T
gS 30 31 552 730 rC
126 96 :M
f0_8 sf
.037 .004(2 )J
f4_8 sf
.206 .021(Handbook on Optical Character Recognition and Document Image Analysis)J
123 123 365 430 rC
np 331 393 :M
337 380 :L
340 382 :L
343 384 :L
331 393 :L
eofill
-1 -1 341 383 1 1 374 340 @b
1 G
325 287 159 57 rF
0 G
325.5 287.5 158 56 rS
1 G
125 276 156 85 rF
0 G
125.5 276.5 155 84 rS
129 277 153 36 rC
132 287 :M
f2_10 sf
(Man)S
152 287 :M
(u)S
158 287 :M
(al )S
168 287 :M
(con)S
183 287 :M
(ver)S
197 287 :M
(s)S
201 287 :M
(ion)S
214 287 :M
f0_10 sf
( of)S
225 287 :M
( not)S
240 287 :M
(at)S
247 287 :M
(i)S
250 287 :M
(on:)S
132 298 :M
(P)S
138 298 :M
(ers)S
149 298 :M
(on )S
162 298 :M
(dir)S
173 298 :M
(ec)S
182 298 :M
(tl)S
187 298 :M
(y )S
195 298 :M
(ent)S
207 298 :M
(er)S
215 298 :M
(s)S
219 298 :M
( t)S
224 298 :M
(he )S
236 298 :M
(s)S
240 298 :M
(tr)S
246 298 :M
(uct)S
258 298 :M
(ure)S
271 298 :M
( )S
132 309 :M
(of )S
143 309 :M
(a )S
150 309 :M
(ma)S
162 309 :M
(t)S
165 309 :M
(hem)S
182 309 :M
(at)S
189 309 :M
(i)S
192 309 :M
(ca)S
201 309 :M
(l)S
204 309 :M
( e)S
211 309 :M
(xpres)S
232 309 :M
(s)S
236 309 :M
(i)S
239 309 :M
(on, )S
254 309 :M
(by)S
gR
gS 248 395 105 25 rC
256 405 :M
f0_10 sf
(C)S
263 405 :M
(omput)S
288 405 :M
(e)S
293 405 :M
(r-proc)S
317 405 :M
(es)S
325 405 :M
(s)S
329 405 :M
(abl)S
341 405 :M
(e)S
251 416 :M
(m)S
259 416 :M
(at)S
266 416 :M
(he)S
276 416 :M
(ma)S
288 416 :M
(t)S
291 416 :M
(ic)S
298 416 :M
(al)S
305 416 :M
( )S
308 416 :M
(expre)S
330 416 :M
(s)S
334 416 :M
(s)S
338 416 :M
(ion)S
gR
gS 123 123 365 430 rC
np 301 469 :M
297 455 :L
301 455 :L
305 455 :L
301 469 :L
eofill
:a
0fg bk
:b
[4
4
] 0 :q
301 455 301 422 :r
[] 0 :q
301 422 :M
psb
pse
:e
328 291 154 47 rC
331 301 :M
0 G
f2_10 sf
(Au)S
344 301 :M
(tom)S
361 301 :M
(ati)S
372 301 :M
(c )S
379 301 :M
(con)S
394 301 :M
(ver)S
408 301 :M
(s)S
412 301 :M
(ion)S
425 301 :M
f0_10 sf
( of)S
436 301 :M
( not)S
451 301 :M
(at)S
458 301 :M
(i)S
461 301 :M
(on:)S
331 312 :M
(C)S
338 312 :M
(om)S
351 312 :M
(pute)S
368 312 :M
(r )S
374 312 :M
(re)S
382 312 :M
(cogni)S
404 312 :M
(ze)S
413 312 :M
(s )S
419 312 :M
(t)S
422 312 :M
(he )S
434 312 :M
(s)S
438 312 :M
(tr)S
444 312 :M
(uct)S
456 312 :M
(ure)S
469 312 :M
( )S
331 323 :M
(of)S
340 323 :M
( a)S
347 323 :M
(n expr)S
372 323 :M
(es)S
380 323 :M
(s)S
384 323 :M
(i)S
387 323 :M
(on i)S
402 323 :M
(n )S
410 323 :M
(tw)S
420 323 :M
(o-di)S
436 323 :M
(me)S
448 323 :M
(ns)S
457 323 :M
(i)S
460 323 :M
(onal)S
477 323 :M
( )S
331 334 :M
(m)S
339 334 :M
(at)S
346 334 :M
(he)S
356 334 :M
(ma)S
368 334 :M
(t)S
371 334 :M
(ic)S
378 334 :M
(al)S
385 334 :M
( )S
388 334 :M
(nota)S
405 334 :M
(t)S
408 334 :M
(ion.)S
gR
gS 123 123 365 430 rC
np 386 285 :M
376 275 :L
379 273 :L
382 271 :L
386 285 :L
eofill
325 191 -1 1 380 273 1 325 190 @a
159 129 120 36 rC
162 139 :M
f0_10 sf
(A pe)S
181 139 :M
(rs)S
188 139 :M
(on w)S
208 139 :M
(ant)S
220 139 :M
(i)S
223 139 :M
(ng t)S
238 139 :M
(o )S
162 150 :M
(com)S
179 150 :M
(m)S
187 150 :M
(uni)S
200 150 :M
(ca)S
209 150 :M
(te)S
216 150 :M
( m)S
226 150 :M
(a)S
231 150 :M
(the)S
243 150 :M
(m)S
251 150 :M
(at)S
258 150 :M
(i)S
261 150 :M
(cal)S
272 150 :M
( )S
162 161 :M
(not)S
175 161 :M
(at)S
182 161 :M
(i)S
185 161 :M
(on t)S
200 161 :M
(o )S
208 161 :M
(the)S
220 161 :M
( c)S
227 161 :M
(omput)S
252 161 :M
(e)S
257 161 :M
(r)S
gR
gS 424 205 64 25 rC
427 215 :M
f0_10 sf
(Sc)S
437 215 :M
(anner)S
427 226 :M
(\(off-)S
445 226 :M
(li)S
450 226 :M
(ne)S
460 226 :M
( da)S
472 226 :M
(ta)S
479 226 :M
<29>S
gR
gS 349 205 60 25 rC
352 215 :M
f0_10 sf
(Da)S
364 215 :M
(ta)S
371 215 :M
( Tabl)S
391 215 :M
(et)S
352 226 :M
(\(on-)S
369 226 :M
(li)S
374 226 :M
(ne)S
384 226 :M
( da)S
396 226 :M
(ta)S
403 226 :M
<29>S
gR
gS 303 432 93 13 rC
306 441 :M
f0_9 sf
(\(w)S
315 441 :M
(he)S
323 441 :M
(n)S
328 441 :M
( o)S
335 441 :M
(ut)S
342 441 :M
(pu)S
351 441 :M
(t i)S
358 441 :M
(s )S
364 441 :M
(de)S
372 441 :M
(s)S
376 441 :M
(ir)S
381 441 :M
(e)S
385 441 :M
(d)S
390 441 :M
<29>S
gR
gS 251 539 33 14 rC
254 549 :M
f0_10 sf
(S)S
260 549 :M
(cr)S
268 549 :M
(een)S
gR
gS 321 539 33 14 rC
324 549 :M
f0_10 sf
(Pr)S
333 549 :M
(int)S
343 549 :M
(e)S
348 549 :M
(r)S
gR
gS 265 479 87 14 rC
268 489 :M
f0_10 sf
(Not)S
283 489 :M
(at)S
290 489 :M
(i)S
293 489 :M
(on ge)S
315 489 :M
(nera)S
332 489 :M
(t)S
335 489 :M
(or)S
gR
gS 123 123 365 430 rC
255.5 469.5 103 36 rS
np 335 537 :M
327 525 :L
330 524 :L
333 523 :L
335 537 :L
eofill
322 506 -1 1 331 524 1 322 505 @a
144 312 135 43 rC
147 321 :M
f0_9 sf
(Typ)S
161 321 :M
(in)S
168 321 :M
(g )S
175 321 :M
(a)S
179 321 :M
(n ASCI)S
205 321 :M
(I)S
208 321 :M
( )S
211 321 :M
(f)S
214 321 :M
(or)S
221 321 :M
(m o)S
235 321 :M
(f)S
238 321 :M
( t)S
243 321 :M
(he)S
251 321 :M
( )S
147 331 :M
(ma)S
158 331 :M
(th)S
165 331 :M
(e)S
169 331 :M
(ma)S
180 331 :M
(ti)S
185 331 :M
(c)S
189 331 :M
(a)S
193 331 :M
(l )S
198 331 :M
(e)S
202 331 :M
(xp)S
211 331 :M
(r)S
214 331 :M
(e)S
218 331 :M
(ss)S
225 331 :M
(io)S
232 331 :M
(n, )S
241 331 :M
(or)S
147 341 :M
(I)S
150 341 :M
(ss)S
157 341 :M
(ui)S
164 341 :M
(ng)S
173 341 :M
( a)S
179 341 :M
( s)S
185 341 :M
(e)S
189 341 :M
(qu)S
198 341 :M
(e)S
202 341 :M
(nc)S
210 341 :M
(e)S
214 341 :M
( )S
217 341 :M
(of)S
224 341 :M
( c)S
230 341 :M
(o)S
235 341 :M
(mma)S
253 341 :M
(nd)S
262 341 :M
(s )S
147 351 :M
(to)S
154 351 :M
( a)S
160 351 :M
( s)S
166 351 :M
(tr)S
171 351 :M
(u)S
176 351 :M
(c)S
180 351 :M
(tu)S
187 351 :M
(r)S
190 351 :M
(e)S
194 351 :M
(-)S
197 351 :M
(ba)S
205 351 :M
(s)S
209 351 :M
(e)S
213 351 :M
(d )S
220 351 :M
(ma)S
231 351 :M
(th)S
238 351 :M
( e)S
244 351 :M
(di)S
251 351 :M
(to)S
258 351 :M
(r.)S
gR
gS 138 312 17 33 rC
141 321 :M
f0_9 sf
(-)S
144 321 :M
( )S
141 341 :M
(-)S
gR
1 G
gS 123 123 365 430 rC
15 16 304.5 143 @j
0 G
.648 lw
14 15 304.5 143 @f
-.648 -.648 304.648 175.648 .648 .648 304 150 @b
-.648 -.648 294.648 187.648 .648 .648 304 174 @b
304 174.648 -.648 .648 312.648 186 .648 304 174 @a
-.648 -.648 304.648 163.648 .648 .648 314 159 @b
320 146 12 11 rC
323 153 :M
f0_6 sf
(-)S
325 153 :M
f1_6 sf
S
gR
0 G
gS 30 31 552 730 rC
.648 lw
310 139 :M
312.662 137.665 314.828 136.331 316.5 135 :C
318.162 133.665 320.662 132.165 324 130.5 :C
327.328 128.831 330.662 127.665 334 127 :C
337.328 126.331 339.995 125.831 342 125.5 :C
343.995 125.165 345 125 345 125 :C
345 125 346.328 124.831 349 124.5 :C
351.661 124.165 353.995 124.498 356 125.5 :C
357.995 126.498 359 127 359 127 :C
359 127 359.994 127.331 362 128 :C
363.994 128.665 365.161 129.998 365.5 132 :C
365.828 133.998 366 135 366 135 :C
366 135 366.328 136.165 367 138.5 :C
367.661 140.831 366.994 143.498 365 146.5 :C
362.994 149.498 360.661 151.164 358 151.5 :C
355.328 151.831 352.495 152.331 349.5 153 :C
346.495 153.664 343.162 154 339.5 154 :C
335.828 154 332.662 154 330 154 :C
327.328 154 325.328 153.664 324 153 :C
322.662 152.331 322 152 322 152 :C
322 152 321.495 151.498 320.5 150.5 :C
319.495 149.498 318.329 147.998 317 146 :C
315.662 143.998 315 143 315 143 :C
315 143 314.829 142.831 314.5 142.5 :C
314.162 142.164 313.662 141.498 313 140.5 :C
312.329 139.498 312 139 312 139 :C
stroke
123 123 365 430 rC
325 134 41 13 rC
328 143 :M
f0_7 sf
( )S
330 143 :M
f0_6 sf
<28>S
332 143 :M
(x-)S
337 143 :M
f1_6 sf
(m)S
340 143 :M
f0_6 sf
<29>S
343 141 :M
( )S
344 143 :M
( )S
346 143 :M
(f)S
348 143 :M
<28>S
350 143 :M
(x\))S
355 143 :M
( )S
357 143 :M
(dx)S
339 134 9 9 rC
342 141 :M
f0_5 sf
(2)S
gR
gS 323 127 11 10 rC
326 133 :M
f1_6 sf
S
gR
gS 322 135 14 17 rC
326 146 :M
f1_12 sf
S
330 146 :M
f0_12 sf
( )S
gR
gS 123 123 365 430 rC
295 159.648 -.648 .648 304.648 163 .648 295 159 @a
408 210 14 14 rC
411 220 :M
f0_10 sf
(or)S
gR
gS 123 123 365 430 rC
np 228 276 :M
233 262 :L
236 264 :L
239 266 :L
228 276 :L
eofill
-1 -1 237 265 1 1 284 189 @b
np 267 393 :M
256 385 :L
258 382 :L
261 380 :L
267 393 :L
eofill
241 361 -1 1 259 382 1 241 360 @a
np 271 537 :M
280 525 :L
277 524 :L
273 523 :L
271 537 :L
eofill
-1 -1 278 525 1 1 284 505 @b
gR
gS 30 31 552 730 rC
126 582 :M
f2_9 sf
.461(Fig.\3121.)A
f0_9 sf
1.936 .194( Conversion between 2D mathematical notation \(which people work with\) and a)J
126 593 :M
1.764 .176(computer-processable representation. Input of expressions is shown in the top part of the)J
126 604 :M
.878 .088(figure: the automatic-conversion pathway is desirable, but not yet widely available. Currently,)J
126 615 :M
1.51 .151(most people who need to enter mathematical expressions use manual conversion \(typing an)J
126 626 :M
2.194 .219(ASCII form of the expression, or issuing editor commands to enter the structure of the)J
126 637 :M
.946 .095(expression [1]\). In contrast, the technology for output of mathematical notation is mature and)J
126 648 :M
.752 .075(widely available \(bottom part of the figure\).)J
endp
%%Page: 3 3
%%BeginPageSetup
initializepage
(; page: 3 of 26)setjob
%%EndPageSetup
-30 -31 :T
gS 30 31 552 730 rC
351 96 :M
f0_8 sf
.127 .013(Recognition of Mathematical Notation 3)J
141 123 :M
f0_10 sf
.553 .055(The requirements that must be met by a mathematics-recognition system depend on)J
126 136 :M
.182 .018(the application. Two main uses of recognition systems are as follows.)J
148 153 :M
S
157 153 :M
1.215 .121(On-line entry of mathematical notation, for a person creating a document for)J
157 166 :M
.389 .039(printing. A handwritten entry on a data tablet is one appropriate input means. A)J
157 179 :M
-.004(successful recognizer must be able to cope with the variability of handwriting; on-)A
157 192 :M
.153 .015(line timing information can be a great help.)J
148 205 :M
S
157 205 :M
2.11 .211(Off-line recognition of mathematical notation. Here, a previously typeset)J
157 218 :M
.77 .077(document is scanned; the mathematical expressions it contains must be located)J
157 231 :M
.596 .06(and then analyzed. This can be done for a variety of purposes. An example of)J
157 244 :M
.614 .061(small-scale use is a reading machine for the visually impaired. Large-scale use)J
157 257 :M
2.07 .207(arises in the scanning and interpretation of a large collection of technical)J
157 270 :M
-.063(documents, for the creation of a database.)A
126 295 :M
f6_10 sf
1.192(1.1.\312Six\312Processes\312for\312Mathematics\312Recognition)A
141 313 :M
f0_10 sf
1.068 .107(Mathematical notation uses two-dimensional arrangements of symbols to transmit)J
126 326 :M
2.891 .289(information. Understanding a mathematical expression involves two \(possibly)J
126 339 :M
.166 .017(concurrent\) activities: symbol recognition and symbol-arrangement analysis. The former)J
126 352 :M
2.275 .228(converts the input image into a set of symbols. The latter analyzes the spatial)J
126 365 :M
.126 .013(arrangement of this set of symbols \(relative to the given notational conventions of the 2D)J
126 378 :M
.972 .097(language for expressing mathematics\) to recover the information content of the given)J
126 391 :M
.118 .012(mathematical notation.)J
141 404 :M
.886 .089(The two major recognition activities \(symbol recognition and symbol-arrangement)J
126 417 :M
.066 .007(analysis\) are performed by all mathematics-recognition systems. Subdividing further, the)J
126 430 :M
-.027(mathematics-recognition problem can be discussed in terms of six processes [2]:)A
375 468 :M
f1_12 sf
( )S
375 468 :M
S
375 459 :M
S
375 450 :M
S
126 445 :M
f0_10 sf
.298(\(1\)\312early\312processing\312\321\312noise\312reduction,\312de-skewing,\312etc)A
f0_9 sf
.165A
f0_4 sf
.073A
f0_9 sf
S
126 457 :M
f0_10 sf
.273(\(2\)\312segmentation,\312to\312isolate\312symbols)A
f0_13 sf
S
126 469 :M
f0_10 sf
.266(\(3\)\312recognition\312of\312symbols)A
381 457 :M
.309 .031( symbol recognition)J
375 504 :M
f1_12 sf
( )S
375 504 :M
S
375 495 :M
S
375 486 :M
S
126 481 :M
f0_10 sf
.31(\(4\)\312identification\312of\312spatial\312relationships\312among\312symbols\312\312)A
126 493 :M
.218(\(5\)\312identification\312of\312logical\312relationships\312among\312symbols)A
f0_13 sf
S
126 505 :M
f0_10 sf
.217(\(6\)\312construction\312of\312meaning)A
381 493 :M
( )S
0 -6 rm
-.041(symbol-arrangement)A
0 6 rm
387 498 :M
-.03(analysis)A
126 523 :M
.673 .067(These processes can be executed in series, or in parallel with later processes providing)J
126 536 :M
.638 .064(contextual feedback for the earlier processes. Any implementation must perform these)J
126 549 :M
.219 .022(recognition steps, although an implementation can mix steps together, so that the various)J
126 562 :M
.192 .019(processes are not clearly delineated in the code. The order of these recognition steps can)J
126 575 :M
.076 .008(vary somewhat. For example, partial identification of spatial and logical relationships can)J
126 588 :M
.338 .034(be performed prior to symbol recognition; this is done in projection-profile cutting \(Sec.)J
126 601 :M
-.007(3.2\), and in Faure and Wang\325s structure recognition \(Sec. 3.5\).)A
141 614 :M
.185 .018(For research purposes, it is possible to bypass the symbol-recognition step in order to)J
126 627 :M
-.014(concentrate on symbol-arrangement analysis. Test-data for the recognition system can be)A
126 640 :M
.692 .069(obtained by scanning a mathematical expression, and manually simulating the symbol-)J
126 653 :M
-.042(recognition step. This approach has been taken in [3] [4] [5] [6]. Here, perfect \(error-free\))A
endp
%%Page: 4 4
%%BeginPageSetup
initializepage
(; page: 4 of 26)setjob
%%EndPageSetup
-30 -31 :T
gS 30 31 552 730 rC
126 96 :M
f0_8 sf
.037 .004(4 )J
f4_8 sf
.206 .021(Handbook on Optical Character Recognition and Document Image Analysis)J
126 123 :M
f0_10 sf
.261 .026(symbol-recognition results are used to test the symbol-arrangement analysis method. To)J
126 136 :M
.507 .051(create a complete recognizer, one must: \(1\) supply an automatic symbol-recognizer, \(2\))J
126 149 :M
.088 .009(modify the symbol-arrangement analysis so that it can handle errors and uncertainty from)J
126 162 :M
1.356 .136(the symbol recognizer, and \(3\) possibly provide feedback from symbol-arrangement)J
126 175 :M
.702 .07(analysis to symbol recognition. For example, the work by Dimitriadis )J
f4_10 sf
.557 .056(et al.)J
f0_10 sf
.611 .061( [7] builds)J
126 188 :M
.034 .003(on Anderson\325s work [3] in this way.)J
126 213 :M
f6_10 sf
1.171(1.2.\312Notational\312Conventions)A
141 231 :M
f0_10 sf
2.481 .248(Notational conventions play a central role in mathematics recognition. The)J
126 244 :M
.782 .078(notational conventions define the two-dimensional language, the mapping between the)J
126 257 :M
.377 .038(marks on the paper and the information that these marks represent. All six of the above)J
126 270 :M
.457 .046(recognition processes require knowledge of notational conventions. For example, noise)J
126 283 :M
.164 .016(reduction \(1\) needs knowledge of the notation in order to preserve small or thin symbols,)J
126 296 :M
.5 .05(such as the decimal point. Segmentation \(2\) needs information about how symbols can)J
126 309 :M
.35 .035(overlap. Symbol recognition \(3\) needs information about symbol appearance; perhaps a)J
126 322 :M
-.023(font defining fixed symbols, and structural descriptions for parameterized symbols such as)A
126 335 :M
.415 .042(the integrals and matrix brackets. The identification of spatial relationships \(4\) requires)J
126 348 :M
.796 .08(information about which spatial relationships are significant for encoding information.)J
126 361 :M
.847 .085(The identification of logical relations among symbols \(5\) can require extensive use of)J
126 374 :M
1.891 .189(notational conventions; for example, large parts of an expression may need to be)J
126 387 :M
1.711 .171(examined to determine whether a spatial relationship that looks like a subscript is)J
126 400 :M
1.516 .152(coincidental, or whether it actually has the logical meaning )J
f4_10 sf
.391(subscript)A
f0_10 sf
1.156 .116(. Finally, the)J
126 413 :M
.618 .062(construction of meaning \(6\) relies heavily on the knowledge of notational conventions:)J
126 426 :M
.304 .03(this is the step in which the diagram is fully converted into the information it represents.)J
126 439 :M
-.008(Existing mathematics-recognition systems use a variety of methods to represent and apply)A
126 452 :M
.127 .013(notational conventions; these are summarized in Secs. 3 to 6.)J
126 477 :M
f6_10 sf
1.157(1.3.\312Definition\312of\312Mathematical\312Notation)A
141 495 :M
f0_10 sf
2.074 .207(The first step in designing a mathematics recognition system is to define the)J
126 508 :M
1.119 .112(recognition problem. We should begin with a definition of mathematical notation: a)J
126 521 :M
.302 .03(definition of the syntax and semantics of this two-dimensional language. Unfortunately,)J
126 534 :M
.636 .064(mathematical notation, like most diagrammatic notations, is not formally defined. It is)J
126 547 :M
.905 .091(only semi-standardized, allowing many variations and drawing styles. Here is a brief)J
126 560 :M
.034 .003(review of some sources of information about mathematical notation.)J
148 577 :M
S
157 577 :M
f2_10 sf
2.564 .256(Written descriptions:)J
f0_10 sf
1.52 .152( Various descriptions of mathematical notation have)J
157 590 :M
.013 .001(been published. Some presentations are oriented toward human readers who want)J
157 603 :M
1.22 .122(to solve typesetting problems \(e.g. [8] [9] [10]\). Others are geared toward a)J
157 616 :M
.573 .057(computational treatment of typesetting problems \(e.g. [11]\). These descriptions)J
157 629 :M
-.035(are oriented toward generation of mathematical notation; they do not make explicit)A
157 642 :M
1.544 .154(the knowledge of notational conventions that is needed to solve recognition)J
157 655 :M
.036(problems.)A
endp
%%Page: 5 5
%%BeginPageSetup
initializepage
(; page: 5 of 26)setjob
%%EndPageSetup
-30 -31 :T
gS 30 31 552 730 rC
351 96 :M
f0_8 sf
.127 .013(Recognition of Mathematical Notation 5)J
148 123 :M
f0_10 sf
S
157 123 :M
f2_10 sf
4.365 .436(Descriptions built into mathematics-recognition systems:)J
f0_10 sf
2.287 .229( Existing)J
157 136 :M
1.916 .192(mathematics-recognition systems use a variety of methods for representing)J
157 149 :M
-.03(notational conventions. These are reviewed below.)A
148 162 :M
S
157 162 :M
f2_10 sf
3.566 .357(Descriptions built into mathematics-generation systems:)J
f0_10 sf
2.23 .223( Generators)J
157 175 :M
2.02 .202(of mathematical notation \(which are usually bundled with editors\) contain)J
157 188 :M
-.003(comprehensive, though often proprietary, descriptions of notational conventions.)A
148 201 :M
S
157 201 :M
f2_10 sf
1.807 .181(Human experts:)J
f0_10 sf
1.093 .109( Interviews with a highly-experienced user of mathematical)J
157 214 :M
2.132 .213(notation can help in defining the notational conventions appropriate for a)J
157 227 :M
-.078(mathematics recognizer.)A
126 244 :M
.86 .086(Several decades ago, Martin suggested that the first step in automating the processing)J
126 257 :M
.476 .048(mathematical notation is to make a study of the notation. He presents a brief list of the)J
126 270 :M
.154 .015(notational conventions found in use in technical publications \([12], p. 79\).)J
141 283 :M
.574 .057(To simplify the recognition problem, attention can be restricted to a certain style of)J
126 296 :M
.994 .099(mathematical notation. For example, during the development of Chou\325s system [13],)J
126 309 :M
.972 .097(testing was conducted with a large set of mathematical expressions, all drawn from a)J
126 322 :M
.24 .024(textbook which was known to be typeset in TROFF. This restriction to a certain style of)J
126 335 :M
1.605 .161(mathematics typesetting increases the uniformity of notational conventions that the)J
126 348 :M
.121 .012(recognizer encounters. Clearly, recognition is easier if one knows the technology used to)J
126 361 :M
-.113(create the document being recognized.)A
141 374 :M
.495 .049(Here we do not undertake a summary of the notational conventions of mathematics.)J
126 387 :M
1.788 .179(Instead, we limit ourselves to a brief discussion of the factors that influence how)J
126 400 :M
.32 .032(mathematical symbols should be grouped during the recognition process. This grouping)J
126 413 :M
.289 .029(results from interpreting the appearance of a particular mathematical expression, relative)J
126 426 :M
.979 .098(to the notational conventions for mathematics. Relevant grouping factors include the)J
126 439 :M
.069(following.)A
137 456 :M
-.328(\(1\))A
153 456 :M
-.054(Grouping factors defined for mathematical notation in general:)A
153 469 :M
S
162 469 :M
f2_10 sf
.638(Operator\312range:)A
f0_10 sf
.872 .087( The )J
f4_10 sf
.636(range)A
f0_10 sf
2.032 .203( of an operator defines the possible spatial)J
162 482 :M
.574 .057(locations for operands. The range for operators is established by conventional)J
162 495 :M
1.013 .101(usage, and can vary from one typesetting style to another. For example, the)J
162 508 :M
.524 .052(bounds of an integral can appear above and below the integral symbol, or they)J
162 521 :M
3.322 .332(can appear to the top-right and bottom-right of the integral symbol.)J
162 534 :M
1.539 .154(Computationally, operator range can be defined in various ways, including)J
162 547 :M
-.01(grammar rules [3] [13], division rules in a structure specification scheme [4], and)A
162 560 :M
1.765 .176(rules for applying projection-profile cuts [14]. Details of the definition of)J
162 573 :M
f4_10 sf
-.096(operator range)A
f0_10 sf
-.091( vary from one author to another.)A
153 586 :M
S
162 586 :M
f2_10 sf
.612(Operator\312precedence:)A
f0_10 sf
1.843 .184( Operator precedence is defined by a ranking of)J
162 599 :M
1.437 .144(mathematical operators, to indicate the priority of evaluation of operations.)J
162 612 :M
-.069(Authors vary in their precise definition of operator precedence.)A
137 629 :M
-.328(\(2\))A
153 629 :M
-.014(Grouping factors arising within a particular mathematical expression:)A
153 642 :M
S
162 642 :M
f2_10 sf
.36(Symbol\312identity:)A
f0_10 sf
1.051 .105( The identity of a symbol restricts how it can be grouped)J
162 655 :M
1.24 .124(with other symbols. In most cases, symbol identity determines whether the)J
endp
%%Page: 6 6
%%BeginPageSetup
initializepage
(; page: 6 of 26)setjob
%%EndPageSetup
-30 -31 :T
gS 30 31 552 730 rC
126 96 :M
f0_8 sf
.037 .004(6 )J
f4_8 sf
.206 .021(Handbook on Optical Character Recognition and Document Image Analysis)J
162 123 :M
f0_10 sf
.615 .061(symbol is an operator or an operand. Once the identity of an operator symbol)J
162 136 :M
.931 .093(has been recognized, knowledge about the general grouping factors \(operator)J
162 149 :M
-.082(range and operator precedence\) is applied in the process of locating the operands.)A
153 162 :M
S
162 162 :M
f2_10 sf
.438(Relative\312symbol\312placement:)A
f0_10 sf
1.385 .139( Relative symbol placement is crucial to the)J
162 175 :M
.048 .005(identification of implicit mathematical operators. Whereas explicit operators are)J
162 188 :M
.34 .034(represented by a symbol \(+ - )J
f1_10 sf
.153(S)A
f0_10 sf
.414 .041(\), implicit operators are indicated by the relative)J
162 201 :M
.589 .059(location of operands \(implied multiplication, subscript, exponentiation\). Eight)J
162 214 :M
2.005 .2(basic spatial relationships are commonly used in mathematics-recognition)J
162 227 :M
.868 .087(systems: left, right, above, below, above right, above left, below right, below)J
162 240 :M
.934 .093(left \(e.g. [15]\). Identification of these relationships can be difficult; Sec. 5.1)J
162 253 :M
.009 .001(discusses methods for distinguishing subscript, in-line, and superscript relations.)J
153 266 :M
S
162 266 :M
f2_10 sf
.679(Relative\312symbol\312size\312and\312case:)A
f0_10 sf
2.244 .224( Relative symbol size provides a clue)J
162 279 :M
.303 .03(for resolving ambiguous spatial relationships. This is particularly important for)J
162 292 :M
.013 .001(implicit operators. For example, a decreased font size provides evidence that the)J
162 305 :M
2.208 .221(relation between symbols is subscript or superscript, rather than implied)J
162 318 :M
1.47 .147(multiplication. Symbol size provides a cue for recognition, but not a hard)J
162 331 :M
1.052 .105(constraint; this is particularly true for handwritten mathematical expressions,)J
162 344 :M
-.039(where symbol size can be erratic.)A
126 361 :M
1.294 .129(These factors \(operator range, operator precedence, symbol identity, relative symbol)J
126 374 :M
2.179 .218(placement, relative symbol size and case\) interact in complex ways. Additional)J
126 387 :M
1.1 .11(terminology can be useful in describing this interaction. For example, Chang\325s term)J
126 400 :M
f4_10 sf
1.697 .17(operator dominance)J
f0_10 sf
.854 .085( is defined for operators in the context of a particular expression.)J
126 413 :M
.381 .038(Operator A dominates over operator B if operator B\325s range nests completely within the)J
126 426 :M
.068 .007(range of operator A. Operator dominance provides a partial ordering on the evaluation of)J
126 439 :M
-.057(operations; operator precedence information is used to complete the ordering [4].)A
141 452 :M
.965 .097(The grouping of symbols into subexpressions is a central problem in mathematics)J
126 465 :M
2.187 .219(recognition. Below we review various computational approaches to solving this)J
126 478 :M
1.644 .164(problem. Syntactic methods rely upon parsing to eventually determine the correct)J
126 491 :M
1.253 .125(groupings \(Secs. 3.1, 4.1\). Projection-profile cutting exploits the existence of white)J
126 504 :M
.946 .095(space to efficiently extract \(part of\) the structure of an expression \(Sec. 3.2\). Graph-)J
126 517 :M
.252 .025(rewriting rules can be used to encode knowledge of operator precedence, operator range,)J
126 530 :M
-.042(and other symbol-grouping factors \(Sec. 3.3\). Procedurally-coded recognition rules can be)A
126 543 :M
.776 .078(used as well \(Sec. 3.4\). An interesting modularization of the mathematics-recognition)J
126 556 :M
.179 .018(problem is discussed in Sec. 3.5.)J
126 581 :M
f6_10 sf
1.16(1.4.\312Problems\312in\312Recognizing\312Mathematical\312Notation)A
141 599 :M
f0_10 sf
.141 .014(We now discuss problems that arise in the recognition of mathematical notation. It is)J
126 612 :M
.042 .004(interesting to compare the mathematics-recognition domain with other document-analysis)J
126 625 :M
-.008(domains. A few comparisons are mentioned below, but further work is needed to obtain a)A
126 638 :M
.01 .001(deeper understanding of the similarities and differences between mathematics-recognition)J
126 651 :M
-.064(and other document-recognition problems.)A
endp
%%Page: 7 7
%%BeginPageSetup
initializepage
(; page: 7 of 26)setjob
%%EndPageSetup
-30 -31 :T
gS 30 31 552 730 rC
351 96 :M
f0_8 sf
.127 .013(Recognition of Mathematical Notation 7)J
126 121 :M
f4_10 sf
.416(1.4.1.\312Noise\312versus\312small\312symbols)A
141 139 :M
f0_10 sf
1.166 .117(Various forms of preprocessing are common in document-image analysis. These)J
126 152 :M
.302 .03(serve to reduce noise, remove skew, and so on. In preprocessing mathematical notation,)J
126 165 :M
.54 .054(it is important to choose algorithms that will preserve small symbols, which are critical)J
126 178 :M
.128 .013(to the meaning. These include dots, commas, and symbol annotations such as A)J
f1_9 sf
0 -1 rm
S
0 1 rm
f0_10 sf
(.)S
126 201 :M
f4_10 sf
.26(1.4.2.\312Symbol\312segmentation\312and\312recognition)A
141 219 :M
f0_10 sf
1.124 .112(Symbol segmentation is relatively easy in printed mathematical notation, because)J
126 232 :M
.617 .062(there is little symbol overlap compared to other notations such as music \([16]; see also)J
126 245 :M
.48 .048(the chapter by Bainbridge and Carter in this book\). Handwritten mathematical notation)J
126 258 :M
.466 .047(may contain many heavily-overlapping symbols; this can be very difficult to segment if)J
126 271 :M
-.022(only off-line data is available.)A
141 284 :M
1.307 .131(Symbol recognition in mathematical notation is difficult because there is a large)J
126 297 :M
.541 .054(character set \(roman letters, greek letters, operator symbols\) with a variety of typefaces)J
126 310 :M
2.74 .274(\(normal, bold, italic\), and a range of font sizes \(subscripts, superscripts, limit)J
126 323 :M
.302 .03(expressions\). Certain symbols have an enormous range of possible scales \(e.g. brackets,)J
126 336 :M
.702 .07(parentheses, )J
f1_10 sf
.185(S)A
f0_10 sf
.13 .013(, )J
f1_10 sf
.24(P)A
f0_10 sf
.13 .013(, )J
f1_10 sf
.086A
f0_10 sf
.217 .022( \).)J
126 359 :M
f4_10 sf
.534(1.4.3.\312Ambiguity\312in\312the\312role\312of\312symbols)A
141 377 :M
f0_10 sf
.719 .072(A characteristic of mathematical notation is that most symbols have a well-defined)J
126 390 :M
.763 .076(meaning. That is, \3222\323 always means )J
f4_10 sf
.238(two)A
f0_10 sf
.673 .067(, \322+\323 always means )J
f4_10 sf
.206(plus)A
f0_10 sf
.712 .071(, and so on. Compare)J
126 403 :M
.957 .096(this to the meaning that a line has in a road map; it could represent a road, a river, a)J
126 416 :M
.081 .008(fence, or a large number of other possibilities. However there are a few common symbols)J
126 429 :M
.188 .019(in mathematical notation that do feature such ambiguity in their role. A dot can represent)J
126 442 :M
.838 .084(a decimal point, a multiplication operator, a symbol annotation such as x)J
428 436 :M
(.)S
432 442 :M
1.75 .175(, or noise; a)J
126 455 :M
.083 .008(horizontal line can indicate a fraction line or a minus sign. The only way to determine the)J
126 468 :M
.276 .028(meaning of such symbols is through the contextual information provided by surrounding)J
126 481 :M
.522 .052(symbols. Thus, resolving ambiguity in role is a problem that must be addressed during)J
126 494 :M
-.035(symbol-arrangement analysis.)A
126 517 :M
f4_10 sf
.212(1.4.4.\312Identifying\312significant\312spatial\312relationships\312)A
141 535 :M
f0_10 sf
.416 .042(Much of the meaning in mathematical notation is carried by the spatial relationships)J
126 548 :M
1.962 .196(between the symbols. Although mathematics is a relatively standardized notation,)J
126 561 :M
2.158 .216(considerable variation is permitted in relative symbol placement. In light of this)J
126 574 :M
1.146 .115(variability, it is not clear how to define and identify meaningful spatial relationships)J
126 587 :M
1.381 .138(among symbols in an expression. Spatial relationships are especially critical for the)J
126 600 :M
2.125 .213(recognition of implicit mathematical operators; these are indicated by the spatial)J
126 613 :M
1.483 .148(arrangement of operands, rather than by an explicit operator symbol. Superscripts,)J
126 626 :M
.956 .096(subscripts, implied multiplication, and matrix structure are indicated implicitly by the)J
126 639 :M
1.35 .135(layout of operands, whereas addition, subtraction, and division use explicit operator)J
126 652 :M
.166(symbols.)A
endp
%%Page: 8 8
%%BeginPageSetup
initializepage
(; page: 8 of 26)setjob
%%EndPageSetup
-30 -31 :T
gS 30 31 552 730 rC
126 96 :M
f0_8 sf
.037 .004(8 )J
f4_8 sf
.206 .021(Handbook on Optical Character Recognition and Document Image Analysis)J
141 121 :M
f0_10 sf
.306 .031(A difficult problem is to distinguish between configurations that represent horizontal)J
126 134 :M
.446 .045(adjacency and those that represent superscripts or subscripts. One source of difficulty is)J
126 147 :M
-.027(the continuum of positions between the horizontal adjacency and superscript \(or subscript\))A
126 161 :M
.536 .054(configurations: 2x 2)J
0 -1 rm
.165(x)A
0 1 rm
.143 .014( 2)J
0 -2 rm
.165(x)A
0 2 rm
.143 .014( 2)J
0 -3 rm
.165(x)A
0 3 rm
.143 .014( 2)J
0 -4 rm
.165(x)A
0 4 rm
(.)S
141 174 :M
.338 .034(Mathematics interpretation is complicated by the fact that symbols in many different)J
126 187 :M
.354 .035(positions can potentially affect the meaning of a given symbol. There is a dense web of)J
126 200 :M
.791 .079(interdependencies among symbols. A large local neighborhood must be considered to)J
126 213 :M
1.66 .166(interpret mathematical notation. From a given symbol, \322adjacent\323 symbols may be)J
126 226 :M
.295 .03(relatively far away \(say 5 to 10 times the symbol size, in every direction\). This contrasts)J
126 239 :M
.032 .003(with music notation, where there are much stronger constraints on the location of relevant)J
126 252 :M
.166(symbols.)A
126 275 :M
f4_10 sf
2.623 .262(1.4.5.\312Ambiguity of\312relative\312symbol\312placement)J
141 293 :M
f0_10 sf
3.397 .34(Mathematical notation uses subtle spatial relationships to indicate logical)J
126 306 :M
.77 .077(relationships: given a certain spatial relationship between two symbols, it can be quite)J
126 319 :M
.498 .05(difficult to determine the logical relationship between these symbols. We illustrate this)J
126 332 :M
.215 .021(with the subscript relation. \(Keep in mind that we cannot locally deduce the baseline for)J
126 345 :M
.341 .034(a line of mathematical notation.\) The configuration )J
0 -2 rm
.108(x)A
0 2 rm
0 1 rm
.06(i)A
0 -1 rm
.311 .031( could indicate that the symbol \324i\325)J
126 358 :M
.142 .014(is a subscript of \324x\325 \(as in the expression x)J
0 3 rm
(i)S
0 -3 rm
.057(y)A
0 3 rm
(j)S
0 -3 rm
.159 .016(\), or it could be a coincidental alignment \(as)J
126 371 :M
.694 .069(in the expression a)J
0 -3 rm
.228(x)A
0 3 rm
.726 .073(i\). Martin provides an interesting series of examples of ambiguity)J
126 384 :M
.677 .068(arising from subtleties of symbol placement \([12], p. 83\). Additional examples can be)J
126 397 :M
.412 .041(found in [6]. The ambiguity of spatial relationships is greatly increased for handwritten)J
126 410 :M
.061 .006(mathematical expressions; people take a lot of freedom with the placement and alignment)J
126 423 :M
.288 .029(of symbols. Proper resolution of symbol-relationship ambiguities can require contextual)J
126 436 :M
.015 .002(information from the entire expression.)J
126 459 :M
f4_10 sf
.265(1.4.6.\312Little\312redundancy\312in\312the\312notation)A
141 477 :M
f0_10 sf
1.994 .199(Mathematical notation has fairly little redundancy, when compared with other)J
126 490 :M
1.946 .195(notations such as music [2]. Redundant representation of information provides a)J
126 503 :M
2.393 .239(recognition system with constraints and cross-checks, particularly useful for the)J
126 516 :M
.181 .018(interpretation of noisy images. The relative lack of redundancy in mathematical notation)J
126 529 :M
.152 .015(means that less information is available for resolving symbol-recognition ambiguities.)J
126 554 :M
f6_10 sf
1.2(1.5.\312Scope\312of\312Mathematics-Recognition\312Systems)A
141 572 :M
f0_10 sf
1.005 .1(Comparisons among mathematics-recognition systems are complicated by the fact)J
126 585 :M
1.568 .157(that each system defines the recognition problem in its own way, placing different)J
126 598 :M
2.2 .22(limitations on the types of input that should be recognizable. Definition of the)J
126 611 :M
-.018(recognition problem includes the following considerations.)A
148 628 :M
S
157 628 :M
.082 .008(The mathematical notation may be handwritten or typeset. In case of handwritten)J
157 641 :M
.116 .012(notation, the input data may be on-line or off-line.)J
endp
%%Page: 9 9
%%BeginPageSetup
initializepage
(; page: 9 of 26)setjob
%%EndPageSetup
-30 -31 :T
gS 30 31 552 730 rC
351 96 :M
f0_8 sf
.127 .013(Recognition of Mathematical Notation 9)J
148 123 :M
f0_10 sf
S
157 123 :M
.11 .011(Isolated mathematical expressions may be given as input, or the system may have)J
157 136 :M
.099 .01(to first locate mathematical expressions within a text page.)J
148 149 :M
S
157 149 :M
.956 .096(Recognizers accept different sets of notational constructs. For example, some)J
157 162 :M
.934 .093(authors use )J
f4_10 sf
1.822 .182(mathematical notation)J
f0_10 sf
1.18 .118( to mean arithmetic mathematical notation,)J
157 175 :M
-.012(whereas others include matrix notation as well.)A
148 188 :M
S
157 188 :M
1.138 .114(Recognizers make various assumptions about the layout style of the notation.)J
157 201 :M
1.946 .195(Some systems expect a very regular layout, assuming, for example, that a)J
157 214 :M
.419 .042(summation-limit-expression must lie within the x-extent of the )J
f1_10 sf
.14(S)A
f0_10 sf
.334 .033( symbol. Other)J
157 227 :M
.26 .026(systems allow great flexibility in symbol placement.)J
148 240 :M
S
157 240 :M
.508 .051(Some recognizers begin with the raw image as input, whereas others begin with)J
157 253 :M
1.055 .106(symbols as input. The latter systems can be tested by human simulation of a)J
157 266 :M
1.114 .111(perfect symbol recognizer. This human simulation sometimes includes lexical)J
157 279 :M
1.198 .12(identification as well \(e.g. using integers and floating-point numbers as input)J
157 292 :M
-.008(tokens [3]\).)A
141 313 :M
.74 .074(This concludes our introduction of the mathematics-recognition problem. We now)J
126 326 :M
.545 .055(turn to a survey of existing work in the area, organized according to major sub-parts of)J
126 339 :M
1.387 .139(the problem: finding mathematical expressions in a document, methods for symbol-)J
126 352 :M
.323 .032(arrangement analysis \(syntactic methods, projection-profile cutting, graph rewriting, and)J
126 365 :M
.988 .099(procedurally-coded rules\), handling noise, identifying subtle spatial relationships, and)J
126 378 :M
.334 .033(recognition of handwritten expressions. Various factors are traded off in the design of a)J
126 391 :M
.945 .094(recognition system; these include efficiency, simplicity, readability, compactness, and)J
126 404 :M
-.048(generality.)A
126 429 :M
f2_10 sf
1.05(2.\312Finding\312the\312Mathematical\312Expressions\312in\312a\312Document)A
141 447 :M
f0_10 sf
.42 .042(Mathematical expressions are typically embedded in text documents, either as offset)J
126 460 :M
.306 .031(expressions, or embedded directly into a line of text. Thus, the first step in mathematics)J
126 473 :M
.052 .005(recognition is to identify where expressions are located on the page. \(This does not apply)J
126 486 :M
.152 .015(to on-line recognition systems, where input comes from a person writing on a data tablet.)J
126 499 :M
-.031(In this case, text and equations generally are not mixed.\))A
141 512 :M
.874 .087(Most work we survey assumes that the recognition system begins with an isolated)J
126 525 :M
1.083 .108(mathematical expression. An exception is Lee and Wang, who present a method for)J
126 538 :M
.522 .052(extracting both embedded and offset mathematical expressions in a text document [17].)J
126 551 :M
1.214 .121(Text lines are labeled as offset expressions based both on internal properties and on)J
126 564 :M
.19 .019(having increased white space above and below them. The remaining text lines consist of)J
126 577 :M
-.008(a mixture of pure text and text with embedded expressions. These lines are converted to a)A
126 590 :M
2.471 .247(stream of tokens. Certain tokens are recognized as belonging to an embedded)J
126 603 :M
1.382 .138(mathematical expression; no details of this process are given, except that it is done)J
126 616 :M
-.04(\322according to some basic expressions forms\323.)A
endp
%%Page: 10 10
%%BeginPageSetup
initializepage
(; page: 10 of 26)setjob
%%EndPageSetup
-30 -31 :T
gS 30 31 552 730 rC
126 96 :M
f0_8 sf
.049 .005(10 )J
f4_8 sf
.203 .02(Handbook on Optical Character Recognition and Document Image Analysis)J
126 121 :M
f2_10 sf
.954(3.\312Methods\312for\312Symbol-Arrangement\312Analysis)A
141 139 :M
f0_10 sf
2.122 .212(Existing recognition systems use a variety of approaches for representing the)J
126 152 :M
1.481 .148(notational conventions of mathematics, and for using these to drive the recognition)J
126 165 :M
.38 .038(process. Here we review four approaches: syntactic methods, projection-profile cutting,)J
126 178 :M
-.152(graph-rewriting, and procedurally-coded rules.)A
126 203 :M
f6_10 sf
1.223(3.1.\312Syntactic\312Methods)A
141 221 :M
f0_10 sf
1.017 .102(A common strategy for recognizing mathematical notation involves some form of)J
126 234 :M
1.301 .13(two-dimensional grammar. Syntactic analysis is appealing for mathematical notation)J
126 247 :M
.716 .072(because the notation has an obvious division into primitives \(i.e. symbols\), a recursive)J
126 260 :M
2.129 .213(structure, and a well-defined syntax \(compared to other diagrammatic notations\).)J
126 273 :M
.474 .047(Grammar rules are used to define the correct grouping of mathematical symbols, and to)J
126 286 :M
-.005(define the meaning of the resultant grouping.)A
126 309 :M
f4_10 sf
.074(3.1.1.\312Coordinate\312grammars)A
141 327 :M
f0_10 sf
1.897 .19(Anderson presents coordinate grammars for the recognition of commonly-used)J
126 340 :M
1.703 .17(arithmetic and matrix mathematical notation [3]. This work provides an excellent)J
126 353 :M
.861 .086(example for illustrating the methods of syntactic pattern recognition. Since Anderson)J
126 366 :M
.44 .044(presents his complete grammars, a precise understanding of his system can be obtained,)J
126 379 :M
.019 .002(both at the abstract and detailed levels. Correctly recognized symbols and symbol-groups)J
126 392 :M
-.056(\(integers and real numbers\) are assumed as input.)A
141 405 :M
1.433 .143(A coordinate grammar operates on )J
f4_10 sf
.316(sets)A
f0_10 sf
1.126 .113( of symbols, rather than on the strings of)J
126 418 :M
.588 .059(symbols used in traditional formal language theory. Nonterminals and terminals of the)J
126 431 :M
.032 .003(grammar are attributed with bounding-box and center coordinates, as well as with a string)J
126 444 :M
f4_10 sf
.233(m)A
f0_10 sf
.489 .049(, an ASCII encoding of the meaning of the symbol-set. The final interpretation result)J
126 457 :M
.207 .021(is given by the )J
f4_10 sf
.137(m)A
f0_10 sf
.306 .031( attribute of the grammar\325s start symbol.)J
141 470 :M
.296 .03(Using a top-down parsing scheme, each grammar-rule application starts with a set of)J
126 483 :M
1.062 .106(symbols and a syntactic goal \(e.g. EXPRESSION, FACTOR, LIMIT\). The grammar)J
126 496 :M
.213 .021(rule specifies how to subdivide the set of symbols into several subsets, each with its own)J
126 509 :M
.696 .07(syntactic subgoal. Partitioning conditions are used to describe spatial constraints. For)J
126 522 :M
.289 .029(example, a division rule \(syntactic goal DIVTERM\) subdivides the set of symbols into a)J
126 535 :M
.25 .025(horizontal bar, a set of symbols above the horizontal bar \(syntactic goal EXPRESSION\),)J
126 548 :M
.893 .089(and a set of symbols below the horizontal bar \(syntactic goal EXPRESSION\). If this)J
126 561 :M
.413 .041(partitioning fails \(e.g. there is no horizontal bar, or some symbols are to the right or left)J
126 574 :M
.747 .075(of the horizontal bar\) then the production rule reports failure, causing the parser to try)J
126 587 :M
1.368 .137(another alternative. On the other hand, successful partitioning gives the parser two)J
126 600 :M
.813 .081(syntactic subgoals; if these succeed, then the division-rule\325s )J
f4_10 sf
.347(m)A
f0_10 sf
.721 .072( value is constructed by)J
126 613 :M
1.828 .183(appropriate combination of the subgoals\325 )J
f4_10 sf
.72(m)A
f0_10 sf
1.389 .139( values. Particular care is taken to find)J
126 626 :M
.777 .078(efficient partitioning strategies for the grammar rules describing implicit mathematical)J
126 639 :M
1.417 .142(operations \(implied multiplication, subscript, superscript\): these rules do not have a)J
endp
%%Page: 11 11
%%BeginPageSetup
initializepage
(; page: 11 of 26)setjob
%%EndPageSetup
-30 -31 :T
gS 30 31 552 730 rC
347 96 :M
f0_8 sf
.126 .013(Recognition of Mathematical Notation 11)J
126 123 :M
f0_10 sf
.15 .015(terminal symbol \(such as a horizontal bar or a plus sign\) on the right-hand side, and must)J
126 136 :M
-.037(therefore try several partitioning alternatives.)A
141 149 :M
.46 .046(In summary, a coordinate grammar provides a clear, well-structured approach to the)J
126 162 :M
2.351 .235(recognition of mathematical notation. Slow parsing speeds can be a drawback.)J
126 175 :M
.793 .079(\(Anderson points out that, in general, more efficient recognizers could be achieved by)J
126 188 :M
1.031 .103(exploiting the special topological features of the notation and sacrificing some of the)J
126 201 :M
.973 .097(flexibility of a purely syntax-directed approach.\) A major difficulty is to extend the)J
126 214 :M
1.173 .117(syntactic approach to handle errors or uncertainty from symbol recognition; Sec. 4.1)J
126 227 :M
.436 .044(describes Chou\325s work in this direction. Also, tests based on bounding-box coordinates)J
126 240 :M
2.014 .201(provide a fairly crude recognition of spatial relationships. \(For example, a limit)J
126 253 :M
.956 .096(expression under a )J
f1_10 sf
.358(S)A
f0_10 sf
.655 .066( is required to have an )J
f4_10 sf
.268(x)A
f0_10 sf
.846 .085(-extent that lies strictly within the )J
f1_10 sf
.358(S)A
f0_10 sf
.452 .045J
f4_10 sf
.268(x)A
f0_10 sf
(-)S
126 266 :M
1.281 .128(extent.\) Modifications or extensions of the coordinate-grammar formalism could be)J
126 279 :M
2.55 .255(devised, to reduce restrictions on the symbol layouts permitted in recognizable)J
126 292 :M
-.014(expressions.)A
141 305 :M
.935 .094(More recently, Belaid and Haton report on a recognition system using both a top-)J
126 318 :M
.923 .092(down and a bottom-up parser [18]. The coordinate grammar they use is simpler than)J
126 331 :M
1.048 .105(Anderson\325s; a smaller subset of mathematical notation is analyzed, with emphasis on)J
126 344 :M
.302 .03(symbol recognition as well as symbol-arrangement analysis. In cases of uncertainty, the)J
126 357 :M
.78 .078(symbol recognizer provides lists of alternatives; contextual information applied during)J
126 370 :M
.021 .002(parsing can sometimes choose the correct alternative. For example, the parser can choose)J
126 383 :M
-.001(between \322\(\323 and \322C\323. When the symbol alternatives can play similar syntactic roles \(such)A
126 396 :M
.028 .003(as \322S\323 and \3225\323\), user interaction is necessary to solve the ambiguity.)J
126 419 :M
f4_10 sf
.172(3.1.2.\312Structure\312specification\312schemes)A
141 437 :M
f0_10 sf
(Chang uses )S
f4_10 sf
.01 .001(structure specification schemes)J
f0_10 sf
.007 .001( to recognize the structure of mathematical)J
126 450 :M
.132 .013(expressions [4]. This is a restriction of the syntactic approach, designed to be efficient in)J
126 463 :M
1.052 .105(searching for the structure of an expression. Recognition time is )J
f4_10 sf
.515(O)A
f0_10 sf
.237<28>A
f4_10 sf
.357(n)A
f0_9 sf
0 -3 rm
.321(2)A
0 3 rm
f0_10 sf
.891 .089(\), for an input)J
126 476 :M
1.545 .155(expression consisting of )J
f4_10 sf
.429(n)A
f0_10 sf
1.444 .144( symbols. This time is for symbol-arrangement analysis:)J
126 489 :M
-.073(correctly-recognized symbols are assumed as input.)A
141 502 :M
.209 .021(Structure specification schemes are based on the existence of operators, which divide)J
126 515 :M
.372 .037(the pattern into one or several sub-patterns. The scheme is specified as a set of division)J
126 528 :M
2.372 .237(rules, one per operator, which indicate this spatial partitioning into subpatterns.)J
126 541 :M
1.073 .107(Precedence numbers, given as part of a division rule, are used to resolve ordering of)J
126 554 :M
.763 .076(operators when neither operator dominates the other. Chang presents precise, detailed)J
126 567 :M
.378 .038(descriptions of his algorithms for applying division rules to find a well-formed structure)J
126 580 :M
1.954 .195(in the given input. \(A well-formed structure is equivalent to the parse tree of a)J
126 593 :M
-.082(syntactically-correct expression.\))A
141 606 :M
-.014(A structure specification scheme has less expressive power than the picture processing)A
126 619 :M
.106 .011(grammars that Chang used previously. In other words, any structure specification scheme)J
126 632 :M
-.029(can be translated into a picture processing grammar that describes the same set of patterns;)A
126 645 :M
.905 .091(the inverse translation, from grammar to structure specification scheme, is not always)J
endp
%%Page: 12 12
%%BeginPageSetup
initializepage
(; page: 12 of 26)setjob
%%EndPageSetup
-30 -31 :T
gS 30 31 552 730 rC
126 96 :M
f0_8 sf
.049 .005(12 )J
f4_8 sf
.203 .02(Handbook on Optical Character Recognition and Document Image Analysis)J
126 123 :M
f0_10 sf
.175 .017(possible. To offset this loss of descriptive power, there is the aforementioned increase in)J
126 136 :M
.247 .025(efficiency, as well as an increase in usability. \(Chang states that a table of division rules)J
126 149 :M
.738 .074(is more concise, and easier to design and comprehend than a table of picture-grammar)J
126 162 :M
-.044(rules.\))A
141 175 :M
1.151 .115( Chang presents small-scale tests that illustrate the use of structure specification)J
126 188 :M
2.094 .209(schemes for the recognition of mathematical notation, and for the recognition of)J
126 201 :M
-.018(document-layout structure \(e.g. the reading order of paragraphs\). Two thresholds, )A
f4_10 sf
(t)S
f0_10 sf
-.018( and )A
f1_9 sf
(a)S
f0_10 sf
(,)S
126 214 :M
.1 .01(are used. Operators are classified as being on the same line if their centroids are within )J
f4_10 sf
(t)S
f0_10 sf
(.)S
126 227 :M
.483 .048(Also, an operator is regarded as being contained in a region if a certain fraction )J
f1_9 sf
.2(a)A
f0_10 sf
.309 .031( of its)J
126 240 :M
.062 .006(total area \(e.g. 70%\) is contained in that region.)J
126 265 :M
f6_10 sf
1.21(3.2.\312Projection\312Profile\312Cutting)A
141 283 :M
f0_10 sf
.146 .015(Projection-profile cutting \(also called )J
f4_10 sf
.197 .02(structural analysis)J
f0_10 sf
.099 .01(\) is a technique that has been)J
126 296 :M
1.34 .134(used in a variety of document-image analysis applications. In recognition of music)J
126 309 :M
1.336 .134(notation, full-page projections are sometimes used to separate staves, with localized)J
126 322 :M
.58 .058(projections used to isolate particular music symbols [16]. Projection profiles have also)J
126 335 :M
-.005(been used for page-layout analysis, to divide a page into columns and paragraphs \(see the)A
126 348 :M
.573 .057(chapter by Ha and Bunke in this book\). Here we consider the use of projection-profile)J
126 361 :M
.027 .003(cutting to express the structure of a mathematical expression.)J
141 374 :M
.035 .003(To analyze the structure of a mathematical expression, Okamoto )J
f4_10 sf
(et al.)S
f0_10 sf
.038 .004( apply recursive)J
126 387 :M
.429 .043(projection-profile cutting [14] [19]. This method provides an analysis of symbol-layout)J
126 400 :M
.15 .015(structure, prior to the recognition of symbol identity, and without the use of an expensive)J
126 413 :M
.91 .091(parsing step. Cutting by the vertical projection profile is attempted first, followed by)J
126 426 :M
.082 .008(horizontal cuts for each resulting region. This process repeats recursively until no further)J
126 439 :M
.218 .022(cutting is possible. The resulting spatial relationships are represented by a tree structure.)J
126 452 :M
1.328 .133(Special processing is used for square-roots, subscripts, superscripts; these cannot be)J
126 465 :M
1.014 .101(handled by a projection profile cut. More extensive special processing is reported in)J
126 478 :M
.083 .008(subsequent work [6]. For example, they state that)J
148 495 :M
f4_10 sf
2.008 .201(There are many cases in which the symbols of a printed mathematical)J
148 508 :M
.493 .049(expression are printed very close to each other or there is no blank space in)J
148 521 :M
1.157 .116(terms of vertical projection profile in the expression. For this reason the)J
148 534 :M
.169 .017(width of a blank space is calculated by deleting 10% of both sides of symbols,)J
148 547 :M
.145 .014(except in the case of horizontal bars of fractions or summation symbols which)J
148 560 :M
.184 .018(have an important role in the width of symbols \([6], pp. 435\320436\).)J
126 577 :M
f0_10 sf
.707 .071(Sec. 3.4 discusses this work further, in the context of procedurally-coded math syntax.)J
126 590 :M
.293 .029(For completeness, we give references to three mathematics-recognition papers written in)J
126 603 :M
-.006(Japanese, two of which originate from Okamoto\325s project [20] [21] [22].)A
141 616 :M
2.152 .215(Faure and Wang use )J
f4_10 sf
.919(X)A
f0_10 sf
1.17 .117( and )J
f4_10 sf
.836(Y)A
f0_10 sf
2.616 .262( projections in their processing of handwritten)J
126 629 :M
.082 .008(mathematical expressions [23]. They describe situations under which projection methods)J
126 642 :M
.069 .007(fail. These include square root symbols, closely-written symbols, and skew. They define)J
126 655 :M
-.013(mask-removal operations to address these situations \(see Sec. 3.5\).)A
endp
%%Page: 13 13
%%BeginPageSetup
initializepage
(; page: 13 of 26)setjob
%%EndPageSetup
-30 -31 :T
gS 30 31 552 730 rC
347 96 :M
f0_8 sf
.126 .013(Recognition of Mathematical Notation 13)J
141 123 :M
f0_10 sf
(J. Ha )S
f4_10 sf
(et al.)S
f0_10 sf
.021 .002( propose another mathematics recognition system that uses a recursive X-Y)J
126 136 :M
2.532 .253(decomposition [15]. Based on bounding-box attributes of primitives, an initial)J
126 149 :M
.222 .022(expression tree is constructed in a top-down fashion. In a bottom-up traversal, the initial)J
126 162 :M
.176 .018(tree is checked for syntax errors. Tree nodes are split or merged to fix syntax errors: this)J
126 175 :M
.97 .097(corrects for missing primitives and other errors. This work is in the design stage; an)J
126 188 :M
.092 .009(implementation is planned.)J
141 201 :M
.503 .05(It appears that projection profile cutting is a simple and efficient technique, suitable)J
126 214 :M
.939 .094(for analyzing some aspects of mathematical-expression structure. A complete system)J
126 227 :M
.59 .059(must provide extensive additional processing to cover cases not amenable to projection)J
126 240 :M
.036(analysis.)A
126 265 :M
f6_10 sf
1.198(3.3.\312Graph\312Rewriting)A
141 283 :M
f0_10 sf
1.885 .188(Graph rewriting is a general computational technique, in which information is)J
126 296 :M
-.068(represented as an attributed graph and computation proceeds by updating the graph through)A
126 309 :M
.293 .029(the application of graph-rewriting rules. \(A graph-rewriting rule )J
f4_10 sf
.088(g)A
f4_7 sf
0 2 rm
(l)S
0 -2 rm
f0_10 sf
.114 .011( ::= )J
f4_10 sf
.088(g)A
f4_7 sf
0 2 rm
(r)S
0 -2 rm
f0_10 sf
.238 .024( specifies that a)J
126 322 :M
.34 .034(subgraph isomorphic to )J
f4_10 sf
.093(g)A
f4_7 sf
0 2 rm
(l)S
0 -2 rm
f0_10 sf
.227 .023( can be replaced by graph )J
f4_10 sf
.093(g)A
f4_7 sf
0 2 rm
.051(r)A
0 -2 rm
f0_10 sf
.344 .034(. Further information is associated)J
126 335 :M
.231 .023(with the graph-rewriting rule, to specify how attribute-values for )J
f4_10 sf
.069(g)A
f4_7 sf
0 2 rm
(r)S
0 -2 rm
f0_10 sf
.2 .02( are computed, and to)J
126 348 :M
.354 .035(specify the creation of edges between )J
f4_10 sf
.114(g)A
f4_7 sf
0 2 rm
.062(r)A
0 -2 rm
f0_10 sf
.32 .032( and the main graph.\) Graph rewriting has been)J
126 361 :M
.182 .018(applied to mathematics recognition as follows [5]. The existence of a symbol-recognizer)J
126 374 :M
1.38 .138(is assumed: the input graph contains one node to represent each symbol, with node)J
126 387 :M
.143 .014(attributes recording the spatial coordinates of the symbol. Given this initial graph, which)J
126 400 :M
-.004(contains no edges, graph-rewriting rules are applied to add edges representing potentially-)A
126 413 :M
.509 .051(meaningful spatial relationships. Further application of graph-rewriting rules is used to)J
126 426 :M
.378 .038(prune and modify these edges, identifying the logically-important relationships from the)J
126 439 :M
.703 .07(spatial relationships. Information about operator precedence, stored as edge attributes,)J
126 452 :M
1.892 .189(helps to determine how symbols are to be grouped into subexpressions. When a)J
126 465 :M
.046 .005(subexpression is recognized, the corresponding subgraph is replaced by a single node that)J
126 478 :M
-.004(represents the subexpression. The final output for a successfully-recognized expression is)A
126 491 :M
.991 .099(a single node whose meaning attribute represents the high-level meaning of the input)J
126 504 :M
.032 .003(expression as a character string. Fig. 2 illustrates a sample graph-rewrite rule.)J
141 517 :M
-.008(The recognition process in [5] is organized into four phases.)A
126 530 :M
.277 .028( )J
f2_10 sf
.713(Build)A
186 530 :M
f0_10 sf
1.179 .118(Add edges between symbols that are related by potentially-meaningful)J
186 543 :M
2.689 .269(associations. Edges are labeled Above, Below, Left, Superscript,)J
186 556 :M
.081(Subscript.)A
126 569 :M
f2_10 sf
.654(Constrain)A
186 569 :M
f0_10 sf
.379 .038(Apply knowledge of notational conventions to remove contradictions and)J
186 582 :M
.146 .015(resolve ambiguities. This includes:)J
186 595 :M
S
194 595 :M
1.496 .15(Remove contradictory associations; remove the more distant of two)J
194 608 :M
.143 .014(similar associations)J
186 621 :M
S
194 621 :M
.151 .015(Disambiguate horizontal lines as fractions or minus signs)J
186 634 :M
S
194 634 :M
.179 .018(Disambiguate dots as decimals, multiplication signs, or noise)J
186 647 :M
S
194 647 :M
-.021(Disambiguate diagonal associations \321 exponents and subscripts)A
endp
%%Page: 14 14
%%BeginPageSetup
initializepage
(; page: 14 of 26)setjob
%%EndPageSetup
-30 -31 :T
gS 30 31 552 730 rC
126 96 :M
f0_8 sf
.049 .005(14 )J
f4_8 sf
.203 .02(Handbook on Optical Character Recognition and Document Image Analysis)J
.875 G
150 132 311 85 rC
152 134 102 83 rF
1 G
152.5 134.5 101 82 rS
0 G
np 253 162 :M
239 165 :L
239 162 :L
239 158 :L
253 162 :L
eofill
217 163 -1 1 240 162 1 217 162 @a
np 325 161 :M
311 165 :L
311 161 :L
311 157 :L
325 161 :L
eofill
297 162 -1 1 312 161 1 297 161 @a
1 G
253 153 299 172 9 @q
0 G
253.5 153.5 298.5 171.5 8.5 @s
1 G
325 153 371 172 9 @q
0 G
325.5 153.5 370.5 171.5 8.5 @s
187 155 12 14 rC
190 165 :M
f4_10 sf
(u)S
gR
gS 340 155 12 14 rC
343 165 :M
f4_10 sf
(v)S
gR
gS 263 155 24 14 rC
266 165 :M
f0_10 sf
(Sign)S
gR
1 G
gS 150 132 311 85 rC
415 153 461 172 9 @q
0 G
415.5 153.5 460.5 171.5 8.5 @s
427 155 22 14 rC
430 165 :M
f0_10 sf
(Exp)S
gR
gS 384 156 17 14 rC
387 166 :M
0 G
f0_10 sf
(::=)S
gR
0 G
gS 150 132 311 85 rC
172.5 153.5 217.5 171.5 8.5 @s
218 162 22 14 rC
221 172 :M
f0_10 sf
(Left)S
gR
gS 297 165 23 14 rC
300 175 :M
f0_10 sf
(Left)S
gR
gS 256 171 11 14 rC
259 181 :M
f0_10 sf
(1)S
gR
gS 329 170 11 14 rC
332 180 :M
f0_10 sf
(2)S
gR
gS 418 171 13 15 rC
421 181 :M
f0_10 sf
(6)S
426 181 :M
f1_10 sf
S
gR
gS 171 171 11 14 rC
174 181 :M
f0_10 sf
(4)S
gR
gS 227 147 11 14 rC
230 157 :M
f0_10 sf
(5)S
gR
gS 301 146 11 14 rC
304 156 :M
f0_10 sf
(3)S
gR
gS 151 187 108 24 rC
154 196 :M
f4_9 sf
(u)S
159 196 :M
f0_9 sf
( )S
161 196 :M
f1_9 sf
S
167 196 :M
f0_9 sf
( { letter, digit, integer, )S
154 207 :M
(number, exp, fractionLine})S
gR
gS 30 31 552 730 rC
135 238 :M
f0_9 sf
2.086 .209(Application Condition)J
229 238 :M
f1_9 sf
S
243 238 :M
f0_9 sf
.076<28>A
f4_9 sf
.102(v)A
f0_9 sf
.052 .005( )J
f1_9 sf
.163A
f0_9 sf
.292 .029( { Letter, Digit, Integer, Number, Exp }\) & \( prec_in\(3\)=1 \))J
135 257 :M
.063(Embedding)A
229 257 :M
f1_9 sf
S
243 257 :M
f0_9 sf
.037(In)A
f0_7 sf
0 2 rm
.029(Left)A
0 -2 rm
f0_9 sf
.1 .01( = {\(1, 6'\)}, Out)J
f0_7 sf
0 2 rm
.029(Left)A
0 -2 rm
f0_9 sf
.099 .01( = {\(2, 6'\)},)J
243 268 :M
.19(Out)A
f0_7 sf
0 2 rm
.157(Above)A
0 -2 rm
f0_9 sf
.406 .041( = {\(1, 6'\), \(2, 6'\)}, Out)J
f0_7 sf
0 2 rm
.154(Below)A
0 -2 rm
f0_9 sf
.399 .04( = {\(1, 6'\), \(2, 6'\)},)J
243 279 :M
.107(In)A
f0_7 sf
0 2 rm
.093(Super)A
0 -2 rm
f0_9 sf
.286 .029( = {\(1, 6'\)}, Out)J
f0_7 sf
0 2 rm
.093(Super)A
0 -2 rm
f0_9 sf
.281 .028( = {\(2, 6'\)},)J
243 290 :M
.141(In)A
f0_7 sf
0 2 rm
.137(Sub)A
0 -2 rm
f0_9 sf
.378 .038( = {\(1, 6'\)}, Out)J
f0_7 sf
0 2 rm
.137(Sub)A
0 -2 rm
f0_9 sf
.373 .037( = {\(2, 6'\)},)J
135 309 :M
.663 .066(Attribute Transfer)J
229 309 :M
f1_9 sf
S
243 309 :M
f0_9 sf
.319 .032({m\(6'\) = m\(1\) \(m\(2\)\); reset_prec\(6'\) })J
126 332 :M
f2_9 sf
.378(Fig.\3122.)A
f0_9 sf
1.372 .137( A graph-rewrite rule to interpret a signed item as a subexpression. The following)J
126 343 :M
.641 .064(steps are used to apply this graph-rewrite rule to a host graph.)J
126 354 :M
1.25(1.)A
139 354 :M
.76 .076(Locate )J
f4_9 sf
.218(g)A
f4_7 sf
0 3 rm
.094(l)A
0 -3 rm
f0_7 sf
0 -3 rm
.141(host)A
0 3 rm
f0_9 sf
.481 .048(, a subgraph of )J
f4_9 sf
.218(g)A
f0_9 sf
.594 .059( that is isomorphic to the unshaded part of the left-hand side of)J
139 365 :M
2.104 .21(the production rule. \(If no isomorphic subgraph can be found, report failure of rule)J
139 376 :M
.885 .088(application.\) This particular rule looks for a node with a Sign label that has a Left-labeled)J
139 387 :M
.627 .063(edge connecting it to some node with a variable label denoted )J
f4_9 sf
.192(v)A
f0_9 sf
(.)S
126 398 :M
1.25(2.)A
139 398 :M
.715 .072(Test the application conditions. If they fail, report failure of rule application. This rule has)J
139 409 :M
1.355 .135(both textual and graphical application conditions. The textual application conditions test)J
139 420 :M
.95 .095(that the label )J
f4_9 sf
.35(v)A
f0_9 sf
1.092 .109( is a member of the set {Letter, Digit, Integer, Number, Exp}, and that the)J
139 431 :M
1.356 .136(precedence attribute prec_in of the Left edge has the value 1. The graphical application)J
139 442 :M
.914 .091(condition uses shaded region\(s\) to specify host-graph structure that must be )J
f4_9 sf
.244(absent)A
f0_9 sf
.646 .065( for rule)J
139 453 :M
1.317 .132(application to occur. In this case, rule-application is prohibited if there is an operand in)J
139 464 :M
1.158 .116(front of the Sign node, since in that case the Sign should be interpreted as an addition or)J
139 475 :M
.988 .099(subtraction, rather than as a negation or explicit plus sign.)J
126 486 :M
1.25(3.)A
139 486 :M
1.877 .188(Remove )J
f4_9 sf
.445(g)A
f4_7 sf
0 3 rm
.192(l)A
0 -3 rm
f0_7 sf
0 -3 rm
.289(host)A
0 3 rm
f0_9 sf
1.294 .129( from the host graph; the remainder of the host graph is called RestGraph.)J
139 497 :M
.569 .057(Keep track of the pre-embedding edges \(i.e. edges that connected )J
f4_9 sf
.178(g)A
f4_7 sf
0 3 rm
.077(l)A
0 -3 rm
f0_7 sf
0 -3 rm
.115(host)A
0 3 rm
f0_9 sf
.642 .064( to RestGraph\).)J
126 508 :M
1.25(4.)A
139 508 :M
1.366 .137(Create )J
f4_9 sf
.406(g)A
f4_7 sf
0 3 rm
.246(r)A
0 -3 rm
f0_7 sf
0 -3 rm
.263(host)A
0 3 rm
f0_9 sf
1.042 .104( by making a copy of the right-hand side of the production rule. In this case)J
139 519 :M
f4_9 sf
.282(g)A
f4_7 sf
0 3 rm
.122(l)A
0 -3 rm
f0_7 sf
0 -3 rm
.183(host)A
0 3 rm
f0_9 sf
.823 .082( consists of a single node with label Exp \(short for Expression\).)J
126 530 :M
1.25(5.)A
139 530 :M
1.505 .15(Embed )J
f4_9 sf
.391(g)A
f4_7 sf
0 3 rm
.236(r)A
0 -3 rm
f0_7 sf
0 -3 rm
.253(host)A
0 3 rm
f0_9 sf
1.46 .146( into RestGraph: use the embedding information to translate pre-embedding)J
139 541 :M
1.21 .121(edges into post-embedding edges. Here, the embedding phrase In)J
f0_7 sf
0 2 rm
.227(Left)A
0 -2 rm
f0_9 sf
.935 .093( = {\(1, 6'\)} specifies)J
139 552 :M
.95 .095(that an incoming Left edge to node 1 causes creation of an incoming Left edge to node 6'.)J
139 563 :M
1.725 .173(Other edge labels are treated analogously, e.g. transferring outgoing Above edges from)J
139 574 :M
.434 .043(nodes 1 and 2 to node 6'.)J
126 585 :M
1.25(6.)A
139 585 :M
.847 .085(Compute attribute values for )J
f4_9 sf
.25(g)A
f4_7 sf
0 3 rm
.151(r)A
0 -3 rm
f0_7 sf
0 -3 rm
.162(host)A
0 3 rm
f0_9 sf
.766 .077(, using the attribute transfer function. Here, the meaning)J
139 596 :M
.817 .082(of the Exp node \(represented by the attribute )J
f4_9 sf
.411(m)A
f0_9 sf
.878 .088(, a string\) is computed by concatenating the)J
139 607 :M
.898 .09(meanings of nodes 1 and 2, with appropriate insertion of parentheses.)J
endp
%%Page: 15 15
%%BeginPageSetup
initializepage
(; page: 15 of 26)setjob
%%EndPageSetup
-30 -31 :T
gS 30 31 552 730 rC
347 96 :M
f0_8 sf
.126 .013(Recognition of Mathematical Notation 15)J
126 123 :M
f2_10 sf
.554(Rank)A
186 123 :M
f0_10 sf
2.589 .259(Use information about operator precedence to group symbols into)J
186 136 :M
(subexpressions.)S
126 149 :M
f2_10 sf
.391(Incorporate)A
186 149 :M
f0_10 sf
-.063(Interpret subexpressions)A
126 170 :M
2.632 .263(The use of Build and Constrain phases allows recognition of expressions with)J
126 183 :M
.671 .067(considerable flexibility in the relative placement of symbols. Build is allowed to form)J
126 196 :M
.327 .033(edges generously, assuring that all relevant associations are included. Any excess edges)J
126 209 :M
-.031(are removed by the Constrain phase.)A
141 222 :M
.266 .027(This graph-rewriting system interprets an expression in a bottom-up manner, with no)J
126 235 :M
1.102 .11(backtracking. The recursive nature of subexpressions is handled as follows. Graph-)J
126 248 :M
1.157 .116(rewriting rules in the Rank phase encode information about operator precedence and)J
126 261 :M
.202 .02(operator range as edge attributes. An ordering is assigned to the edges around each node,)J
126 274 :M
.352 .035(indicating which operator has highest priority locally. Next, Incorporate rules group the)J
126 287 :M
1.073 .107(highest-priority symbols into subexpressions, replacing them by a single node. When)J
126 300 :M
.689 .069(Incorporate cannot find further subexpressions, the Rank rules are re-applied to update)J
126 313 :M
1.137 .114(edge attribute values. Incorporate and Rank phases alternate until only a single node)J
126 326 :M
.038 .004(remains. The meaning attribute indicates the meaning of the entire input expression.)J
141 339 :M
.039 .004(The recognition system consists of approximately 60 graph-rewriting rules. Execution)J
126 352 :M
.436 .044(is slow due to the crude graph-rewriting environment. Good results are obtained on the)J
126 365 :M
.732 .073(small set of test expressions that have been tried; these test expressions include highly)J
126 378 :M
1.023 .102(irregular symbol positioning, as could occur in handwritten expressions. The current)J
126 391 :M
-.002(work does not handle errors from symbol recognition; however, spurious dots and poorly-)A
126 404 :M
-.081(aligned symbols are interpreted correctly.)A
141 417 :M
.78 .078(In summary, graph-rewriting is a promising approach for mathematics recognition.)J
126 430 :M
1.404 .14(Graph rewriting offers a flexible formalism with a strong theoretical foundation for)J
126 443 :M
.727 .073(manipulating two-dimensional patterns. It has been shown to be a useful technique for)J
126 456 :M
.858 .086(high-level recognition of circuit diagrams and musical scores \(references in [5]\). The)J
126 469 :M
2.603 .26(organization into Build, Constrain, Rank, and Incorporate phases facilitates the)J
126 482 :M
.888 .089(construction and integration of new rewriting rules. Future research must address the)J
126 495 :M
.56 .056(error-prone nature of symbol recognition, either allowing the graph-rewriting system to)J
126 508 :M
1.305 .131(process input consisting of a number of possible interpretations for each symbol, or)J
126 521 :M
-.041(providing for feedback from the graph-rewriting system to a symbol recognizer.)A
126 546 :M
f6_10 sf
1.035(3.4.\312Procedurally-Coded\312Math\312Syntax)A
141 564 :M
f0_10 sf
.4 .04(H. J. Lee )J
f4_10 sf
.518 .052(et al.)J
f0_10 sf
.785 .079( have developed a mathematics recognition system using procedural)J
126 577 :M
1.547 .155(code to embody the syntax of mathematical notation [17] [24] [25]. After symbol)J
126 590 :M
.67 .067(recognition, the mathematical expression is represented by a list of symbols in random)J
126 603 :M
.332 .033(order. To recognize appropriate symbol groups \(i.e. subexpressions\), procedural code is)J
126 616 :M
.545 .055(used. After a group of symbols is recognized as a subexpression, it is represented by a)J
126 629 :M
.473 .047(bounding box, and further grouping takes place. To indicate the flavor of these rules, a)J
126 642 :M
.37 .037(few sample rules are repeated here. A length threshold of 20 pixels is used to classify a)J
126 655 :M
.769 .077(horizontal line as a long bar or a short bar. If a long bar has symbols both above and)J
endp
%%Page: 16 16
%%BeginPageSetup
initializepage
(; page: 16 of 26)setjob
%%EndPageSetup
-30 -31 :T
gS 30 31 552 730 rC
126 96 :M
f0_8 sf
.049 .005(16 )J
f4_8 sf
.203 .02(Handbook on Optical Character Recognition and Document Image Analysis)J
126 123 :M
f0_10 sf
1.119 .112(below it, it is treated as a division. If there are no symbols above it, it is treated as)J
126 136 :M
1.095 .109(boolean negation. If a short bar has no symbols above or below it, it is treated as a)J
126 149 :M
.383 .038(minus sign. If it has symbols above or below it, then combination characters \(such as =)J
126 162 :M
cF
f1_10 sf
.02A
sf
.203 .02( )J
cF
f1_10 sf
.02A
sf
.203 .02( )J
f1_10 sf
0 -1 rm
.218A
0 1 rm
f0_10 sf
.47 .047(\) are formed. Various sources of errors are discussed in [25], including: scanning)J
126 175 :M
1.704 .17(\(noise and broken characters\); thinning \(e.g. confusion between \322x\323 and \322)J
f1_9 sf
.494(l)A
f0_10 sf
1.717 .172(\323\); and)J
126 188 :M
1.215 .121(expression formation \(mainly due to incorrect recognition of subscript versus in-line)J
126 201 :M
.71 .071(relations\). Other aspects of this system are discussed in Sec. 2 \(locating mathematical)J
126 214 :M
.175 .017(expressions in text\) and Sec. 4.4 \(splitting of connected symbols\). In summary, a benefit)J
126 227 :M
.443 .044(of this procedural approach is fast execution; the authors also find it convenient to code)J
126 240 :M
.783 .078(recursively in this way. A disadvantage is that this approach provides a rather ad hoc)J
126 253 :M
.022 .002(representation of notational conventions, making the procedural code difficult to maintain)J
126 266 :M
.061 .006(or scale up.)J
141 279 :M
.4 .04(The recognition system by Okamoto )J
f4_10 sf
.282 .028(et al.)J
f0_10 sf
.374 .037( [6] [14] [19] combines projection-profile)J
126 292 :M
.101 .01(analysis with an extensive array of procedurally-coded recognition rules. The system has)J
126 305 :M
1.073 .107(been tested on more than 100 expressions, taken from journals or generated by TeX.)J
126 318 :M
.116 .012(Their system is able to correctly recognize most of the expression structures. The variety)J
126 331 :M
.44 .044(and complexity of their successfully-recognized expressions is impressive. This system)J
126 344 :M
.453 .045(began with the use of projection-profile cutting and has evolved through the addition of)J
126 357 :M
-.049(specialized code segments to correct particular recognition errors arising in earlier versions)A
126 370 :M
.672 .067(of the system. Thus it is difficult to summarize the design of the system; the reader is)J
126 383 :M
.71 .071(referred to [6] for a description of the extensive list of processing steps and thresholds)J
126 396 :M
2.853 .285(used. This paper provides a compelling illustration of the complexity of the)J
126 409 :M
2.767 .277(mathematics-recognition task, of the many symbol configurations that must be)J
126 422 :M
1.062 .106(considered. The authors state that syntactic approaches, using parsing, are untenable)J
126 435 :M
1.005 .101(because the great variety of possible expressions makes it impossible to provide an a)J
126 448 :M
2.767 .277(priori syntax definition for all possible expressions. This, combined with the)J
126 461 :M
.341 .034(computational complexity of parsing, motivates them to instead use a large collection of)J
126 474 :M
.925 .092(procedurally-coded recognition rules. Their comment about a priori)J
f4_10 sf
.113 .011( )J
f0_10 sf
1.293 .129(syntax definition)J
126 487 :M
.341 .034(requires some clarification: any recognition method, including procedurally-coded rules,)J
126 500 :M
1.6 .16(implicitly or explicitly defines the syntax of recognizable expressions. Apparently)J
126 513 :M
.602 .06(Okamoto )J
f4_10 sf
.341 .034(et al.)J
f0_10 sf
.407 .041( find it easier and more practical to provide an implicit syntax definition,)J
126 526 :M
.848 .085(coded as procedural rules, rather than an explicit syntax definition, coded as grammar)J
126 539 :M
.013(rules.)A
126 564 :M
f6_10 sf
.988(3.5.\312Data-driven\312and\312Knowledge-driven\312Modules)A
141 582 :M
f0_10 sf
.826 .083(Faure and Wang present an interesting, systematic description of the mathematics-)J
126 595 :M
.946 .095(recognition problem [23]. The emphasis is on extracting the structure of handwritten)J
126 608 :M
.578 .058(expressions, with symbol recognition performed only in restricted circumstances. \(The)J
126 621 :M
.832 .083(authors plan to add modules for symbol recognition and full syntax recognition later.\))J
126 634 :M
-.008(Evidence is cited that humans recognize the structure of an expression prior to performing)A
126 647 :M
1.2 .12(complete symbol recognition. For example, when a person is reading a handwritten)J
endp
%%Page: 17 17
%%BeginPageSetup
initializepage
(; page: 17 of 26)setjob
%%EndPageSetup
-30 -31 :T
gS 30 31 552 730 rC
347 96 :M
f0_8 sf
.126 .013(Recognition of Mathematical Notation 17)J
126 123 :M
f0_10 sf
-.01(expression aloud, syntactic structures such as a division bar are recognized correctly, even)A
126 136 :M
.013 .001(before noticing that certain symbols in the numerator or denominator are illegible.)J
141 149 :M
.871 .087(Input data is provided by people writing on a digitizing tablet. The system works)J
126 162 :M
2.346 .235(with freely-written material \320 the users are not restricted to particular styles of)J
126 175 :M
.345 .035(mathematical notation, and the expressions users write deviate from a horizontal writing)J
126 188 :M
.683 .068(line. The sample expressions shown in the paper [23] exhibit significant, non-uniform)J
126 201 :M
.853 .085(skew, and many instances of hasty writing \(such as a division bar that is significantly)J
126 214 :M
.552 .055(shorter than the numerator, and a )J
f1_10 sf
.228(S)A
f0_10 sf
.533 .053( symbol with a gap between the two strokes used to)J
126 227 :M
.299 .03(form the symbol\).)J
141 240 :M
.649 .065(The recognition system is organized as a collection of independent modules, which)J
126 253 :M
.36 .036(communicate through a shared memory. The shared memory contains the input data, as)J
126 266 :M
1.767 .177(well as the representation tree, which is updated as recognition progresses. \(This)J
126 279 :M
.066 .007(architecture is reminiscent of a blackboard architecture, although here the shared memory)J
126 292 :M
1.108 .111(does not trigger module application, but a fixed order of module application is used.)J
126 305 :M
-.001(Document-image-analysis systems that use a blackboard architecture are reviewed in [2].\))A
126 318 :M
-.07(Currently four modules are used:)A
148 335 :M
S
157 335 :M
-.066(Acquisition)A
148 348 :M
S
157 348 :M
.536 .054(Data-driven segmentation. This module builds an initial relational tree. It does)J
157 361 :M
.361 .036(not take writing-order into account, and thus applies to off-line data as well. No)J
157 374 :M
2.37 .237(contextual information is available to the procedures of this module: the)J
157 387 :M
.789 .079(information available to an operator is restricted to the expression-subimage to)J
157 400 :M
.483 .048(which it is applied. Projections onto the X and Y axis are used; when these fail)J
157 413 :M
.359 .036(\(e.g. due to a square root symbol, closely-written symbols, or excessive skew\), a)J
157 426 :M
.955 .095(mask-removal operation is attempted. The first step is to detect a mask: first,)J
157 439 :M
.185 .018(special routines look for square roots and fraction bars; if these fail then any long)J
157 452 :M
.7 .07(or tall stroke is sought. Next the mask is removed, and the remaining symbols)J
157 465 :M
-.03(are analyzed using X or Y projections.)A
148 478 :M
S
157 478 :M
-.073(Knowledge-driven segmentation. This module corrects the relational tree produced)A
157 491 :M
.343 .034(by the previous module. It uses domain-specific knowledge, looking for a set of)J
157 504 :M
-.027(specific patterns, and updating the relational tree by pattern-dependent corrections.)A
157 517 :M
1.165 .116(This module has knowledge about a subset of the lexicon, the syntactic rules)J
157 530 :M
.483 .048(related to these symbols, the writing order \(e.g. the long stroke is written before)J
157 543 :M
.081 .008(the dot in \322i\323 or \322j\323\), and symbol shape \(e.g. the strokes of \322E\323, \322F\323, and \322)J
f1_10 sf
(S)S
f0_10 sf
.111 .011(\323 may)J
157 556 :M
.941 .094(not be connected\). The patterns that this module looks for are structured as a)J
157 569 :M
-.066(hierarchy of frames. Once relational-tree nodes have been identified for correction,)A
157 582 :M
.348 .035(a complex procedure is needed to update the remainder of the tree in accordance)J
157 595 :M
-.104(with the corrected nodes.)A
148 608 :M
S
157 608 :M
3.169 .317(Line labeling. This module labels the spatial relationships \(subscript,)J
157 621 :M
.2 .02(superscript, same line\) between components of a writing line. Statistical labeling)J
157 634 :M
.173 .017(is used, as discussed in Sec. 5.1.2.)J
endp
%%Page: 18 18
%%BeginPageSetup
initializepage
(; page: 18 of 26)setjob
%%EndPageSetup
-30 -31 :T
gS 30 31 552 730 rC
126 96 :M
f0_8 sf
.049 .005(18 )J
f4_8 sf
.203 .02(Handbook on Optical Character Recognition and Document Image Analysis)J
126 127 :M
f0_10 sf
1.856 .186(Modules for symbol recognition and full syntax analysis will be added as system)J
126 140 :M
2.499 .25(development continues. This system provides an interesting subdivision of the)J
126 153 :M
.511 .051(mathematics-interpretation problem into subproblems, and it demonstrates the ability to)J
126 166 :M
1.009 .101(cope with challenging handwritten input. The organization of this system as a set of)J
126 179 :M
-.047(independent modules imposes a welcome structure on the software. A structured approach)A
126 192 :M
.198 .02(eases the task of designing, coding, and debugging the complex and diverse rules needed)J
126 205 :M
-.023(during mathematics recognition.)A
126 230 :M
f2_10 sf
1.109(4.\312Noise,\312Distortions,\312and\312Connected\312Symbols)A
141 248 :M
f0_10 sf
.278 .028(Recognition of mathematical notation is greatly complicated by noise and distortions)J
126 261 :M
.61 .061(in the input. Various computational approaches can be used to deal with this problem;)J
126 274 :M
.845 .084(these include stochastic grammars, deterministic grammars with confidence-values for)J
126 287 :M
-.055(tokens, and postprocessing error-correction rules.)A
126 312 :M
f6_10 sf
1.102(4.1.\312Stochastic\312Grammars)A
141 330 :M
f0_10 sf
.215 .021(Chou uses a stochastic grammar to recognize noisy typeset equations [13]. The most)J
126 343 :M
.437 .044(likely parse is taken as the correct interpretation of the input. Each production rule in a)J
126 356 :M
.611 .061(stochastic grammar has an associated probability. The probability of a particular parse)J
126 369 :M
.298 .03(tree is computed by multiplying together the probabilities of each production used in the)J
126 382 :M
.508 .051(parse. Two-dimensional patterns are described by allowing each production rule to use)J
126 395 :M
-.034(either vertical or horizontal concatenation \(Sec. 5.1.1\). Square-roots are not recognized by)A
126 408 :M
-.048(the grammar described in [13]. To add them, the square-root sign would have to be treated)A
126 421 :M
.183 .018(as two symbols, so that the necessary spatial relationships can be described by horizontal)J
126 434 :M
-.094(and vertical concatenation.)A
141 447 :M
.995 .1(A dynamic programming algorithm is presented for finding the most likely parse;)J
126 460 :M
.451 .045(complexity of this algorithm is )J
f4_10 sf
.212(O)A
f0_10 sf
.098<28>A
f4_10 sf
.147(n)A
f0_8 sf
0 -3 rm
.118(3)A
0 3 rm
f0_10 sf
.426 .043(\). An iterative algorithm is used to learn grammar-)J
126 473 :M
1.3 .13(parameters \(such as production-rule probabilities\) from training data: parsing all the)J
126 486 :M
.494 .049(training expressions gives an estimate of the expected number of times each production)J
126 499 :M
(rule is used.)S
141 512 :M
.303 .03(Conceptually, the stochastic grammar goes all the way down to the pixel level. As a)J
126 525 :M
1.779 .178(practical matter, this is implemented in two parts. First, symbol candidates \(with)J
126 538 :M
1.021 .102(associated probabilities\) are generated by exhaustive template matching \(match every)J
126 551 :M
.3 .03(symbol-template to every image location; see Sec. 4.4\). Next, the stochastic grammar is)J
126 564 :M
.697 .07(used to find the most likely parse of the symbol candidates; the calculation of a parse-)J
126 577 :M
.691 .069(probability includes contributions from the symbol-probabilities of all symbols used in)J
126 590 :M
-.054(the derivation.)A
141 603 :M
1.329 .133(Testing reported in [13] is created by copying bitmaps from a previewer for the)J
126 616 :M
.595 .06(eqn/troff typesetting system; noise is added by flipping each image bit with probability)J
126 629 :M
.832 .083(0.01. The resulting images are quite challenging, due both to added noise and to the)J
126 642 :M
.779 .078(previewer\325s low resolution \(100 dots per inch\). Subsequent testing \(mentioned during)J
endp
%%Page: 19 19
%%BeginPageSetup
initializepage
(; page: 19 of 26)setjob
%%EndPageSetup
-30 -31 :T
gS 30 31 552 730 rC
347 96 :M
f0_8 sf
.126 .013(Recognition of Mathematical Notation 19)J
126 123 :M
f0_10 sf
1.7 .17(Chou\325s demonstration at SSPR90, Murray Hill, New Jersey\) involved scanning all)J
126 136 :M
.057 .006(equations in a mathematics textbook.)J
141 149 :M
1.064 .106(In summary, Chou mentions the following advantages of stochastic grammars for)J
126 162 :M
.074 .007(document recognition. The approach treats the interpretation process by parsing from the)J
126 175 :M
.127 .013(grammar-start-symbol to the pixel level, with no hard decisions made at any intermediate)J
126 188 :M
1.069 .107(stage. The result is statistically optimal, given the noise model and grammar model.)J
126 201 :M
.206 .021(Noise, ambiguity, and touching characters are handled well. Grammar-parameters can be)J
126 214 :M
.064 .006(trained to achieve optimal performance on particular printers, fonts, layouts and scanners.)J
126 227 :M
.397 .04(To offset this, the following disadvantages are mentioned: computational expense, skew)J
126 240 :M
2.505 .25(sensitivity \(preprocessing must include good skew correction\), and difficulty in)J
126 253 :M
-.026(accounting for kerning.)A
141 266 :M
1.575 .158(More recently, Kopec and Chou are performing document-image analysis using)J
126 279 :M
-.043(methods adapted from communication theory [26]. Here a finite-state model of the image-)A
126 292 :M
.564 .056(creation-process is included as part of the recognition system. This interesting, highly-)J
126 305 :M
.381 .038(promising approach is illustrated on the interpretation of the phone book\325s yellow pages)J
126 318 :M
.258 .026(columns. Experiments with the interpretation of other notations, such as music notation,)J
126 331 :M
-.079(have been undertaken as well.)A
126 356 :M
f6_10 sf
1.082(4.2.\312Error\312Correction\312with\312a\312Coordinate\312Grammar)A
141 374 :M
f0_10 sf
2.279 .228(Dimitriadis )J
f4_10 sf
1.304 .13(et al.)J
f0_10 sf
1.848 .185( report on on-going work that extends Anderson\325s coordinate)J
126 387 :M
.609 .061(grammar to add error detection and correction [7]. Unfortunately, this is a preliminary)J
126 400 :M
1.6 .16(report with few details. Dimitriadis\325 Ph.D. thesis \(in Spanish; Dept. of Automatic)J
126 413 :M
.682 .068(Control and Systems, University of Valladolid, cited as \322expected 1991\323\) may provide)J
126 426 :M
.436 .044(more information. On-line data from a data tablet is processed by grouping strokes and)J
126 439 :M
.43 .043(applying elastic matching to recognize symbols; each symbol is represented by a series)J
126 452 :M
-.048(of candidates, with confidence measures. Parsing starts by considering the candidates with)A
126 465 :M
2.033 .203(highest confidences; if the resulting global confidence figure is rather low, other)J
126 478 :M
-.002(candidates are tried, and a globally optimum decision is made. At the time of their report,)A
126 491 :M
1.459 .146(this parsing scheme was in the planning stage; they do not discuss the danger of a)J
126 504 :M
-.046(combinatorial explosion of candidate-combinations.)A
126 529 :M
f6_10 sf
1.015(4.3.\312Postprocessing\312Error-correction\312Rules)A
141 547 :M
f0_10 sf
.188 .019(Heuristic rules for error-correction are discussed in [17]. Examples of these rules are)J
126 560 :M
.076 .008(as follows. Knowledge of special function names can correct character confusions \(\3225in\323)J
126 573 :M
.599 .06(is corrected to \322sin\323; \322c0s)J
f4_10 sf
.173(x)A
f0_10 sf
.528 .053(\323 is corrected to \322cos)J
f4_10 sf
.173(x)A
f0_10 sf
.551 .055(\323\). The operands of a binary operator)J
126 586 :M
-.007(normally appear in the same font type and font size; this can be used to correct a character)A
126 599 :M
1.268 .127(confusion such as \322/<)J
f4_10 sf
.208(i)A
f0_10 sf
.422(<)A
f4_10 sf
.374(n)A
f0_10 sf
.623 .062J
f4_10 sf
.374(1)A
f0_10 sf
.422(<)A
f4_10 sf
.208(i)A
f0_10 sf
.422(<)A
f4_10 sf
.374(n)A
f0_10 sf
1.221 .122(\323. Knowledge of legal subscripts can eliminate)J
126 612 :M
.184 .018(further confusions, such as correcting 1)J
f0_8 sf
0 3 rm
(2)S
0 -3 rm
f0_10 sf
.065 .007( to l)J
f0_8 sf
0 3 rm
(2)S
0 -3 rm
f0_10 sf
.099 .01( and 5)J
f0_8 sf
0 3 rm
(2)S
0 -3 rm
f0_10 sf
.077 .008( to S)J
f0_8 sf
0 3 rm
(2)S
0 -3 rm
f0_10 sf
(.)S
endp
%%Page: 20 20
%%BeginPageSetup
initializepage
(; page: 20 of 26)setjob
%%EndPageSetup
-30 -31 :T
gS 30 31 552 730 rC
126 96 :M
f0_8 sf
.049 .005(20 )J
f4_8 sf
.203 .02(Handbook on Optical Character Recognition and Document Image Analysis)J
126 121 :M
f6_10 sf
1.27(4.4.\312Connected\312Symbols)A
141 139 :M
f0_10 sf
1.806 .181(Connected symbols are common both in typeset and handwritten mathematical)J
126 152 :M
2.137 .214(expressions. Separation of such symbols is a difficult problem, which has been)J
126 165 :M
.006 .001(extensively studied in OCR and other domains as well. Here we review a few approaches)J
126 178 :M
-.001(to symbol-separation that have been used in mathematics-recognition systems.)A
141 191 :M
1.716 .172(Anderson assumes correctly-recognized symbols as input [3]. A grammar rule)J
126 204 :M
.19 .019(\(number A56\) shrinks each symbol\325s bounding box down to a center point. This enables)J
126 218 :M
.218 .022(subsequent coordinate-tests to yield the desired results. For example, in the expression )J
f4_10 sf
0 -3 rm
(y)S
0 3 rm
481 214 :M
(_)S
481 222 :M
(x)S
126 234 :M
f0_10 sf
.041 .004(the modified bounding box of the \322)J
f4_10 sf
(y)S
f0_10 sf
.042 .004(\323 lies wholly above the division bar.)J
141 247 :M
.353 .035(To recognize symbols, Lee and Lee begin with thinning followed by curve detection)J
126 260 :M
.373 .037([25]. Connected symbols are separated using a dynamic programming algorithm. First,)J
126 273 :M
.911 .091(the curve list is matched to each of the reference symbols. If the maximum similarity)J
126 286 :M
1.064 .106(value is lower than a threshold, the curve list is passed to the dynamic programming)J
126 299 :M
.869 .087(algorithm. Here the curve list undergoes curve splitting and loop merging, and is put)J
126 312 :M
.008 .001(into a canonical order. Then the reference symbols are matched to the sequence of curves)J
126 325 :M
.209 .021(at the start of the curve list.)J
141 338 :M
.16 .016(Chou\325s stochastic grammar does not require explicit separation of connected symbols)J
126 351 :M
-.007([13]. Instead, the lexical access stage matches all templates in the font dictionary to every)A
126 364 :M
.44 .044(position in the image. \(The font dictionary has separate entries for different font sizes.\))J
126 377 :M
.854 .085(A match is retained if the hamming distance \(number of differing pixels\) between the)J
126 390 :M
1.068 .107(template and the image is below the three-sigma threshold. \(Using a noise model in)J
126 403 :M
.076 .008(which image bits are independently flipped with probability )J
f4_10 sf
(P)S
f4_8 sf
0 2 rm
(e)S
0 -2 rm
f0_10 sf
.083 .008(, the three-sigma threshold)J
126 416 :M
1.582 .158(includes all matches where the number of disagreeing bits is within three standard)J
126 429 :M
.412 .041(deviations of the mean number of disagreeing bits. The probability of a greater number)J
126 442 :M
.938 .094(of disagreeing bits is less than 0.13%.\) The result is a list of all characters that have)J
126 455 :M
.395 .039(significant probability of being present in the image. These hypothesized characters are)J
126 468 :M
-.009(then processed by the stochastic grammar \(Sec. 4.1\).)A
141 481 :M
-.027(Systems that accept on-line input face a rather different segmentation problem. Where)A
126 494 :M
.56 .056(off-line systems must separate symbols that overlap in the image, on-line systems must)J
126 507 :M
1.059 .106(gather together the set of strokes that form a single symbol. As described in Sec. 6,)J
126 520 :M
.015 .001(Chen and Yin [27] do this by analyzing the bounding boxes of successive strokes.)J
126 545 :M
f2_10 sf
1(5.\312Identifying\312Spatial\312Relationships)A
141 563 :M
f0_10 sf
.797 .08(It is difficult to recognize the spatial and logical relationships among symbols in a)J
126 576 :M
.197 .02(mathematical expression \(Secs. 1.3 and 1.4\). Here we review techniques for recognizing)J
126 589 :M
.899 .09(subscript, in-line, and superscript relations, and also briefly discuss the recognition of)J
126 602 :M
.45 .045(matrix notation.)J
endp
%%Page: 21 21
%%BeginPageSetup
initializepage
(; page: 21 of 26)setjob
%%EndPageSetup
-30 -31 :T
gS 30 31 552 730 rC
347 96 :M
f0_8 sf
.126 .013(Recognition of Mathematical Notation 21)J
126 121 :M
f6_10 sf
1.129(5.1.\312Distinguishing\312Subscript,\312In-line,\312Superscript)A
141 139 :M
f0_10 sf
.851 .085(The identification of subscripts, in-line, and superscript relations is a complex and)J
126 152 :M
.882 .088(important problem. For example, the system reported in [6] makes recognition errors)J
126 165 :M
.473 .047(that are typically errors in subscript and superscript recognition; this is a mature system)J
126 178 :M
-.02(that is capable of correctly recognizing many complex expression structures.)A
126 201 :M
f4_10 sf
.177(5.1.1.\312Global\312thresholds)A
141 219 :M
f0_10 sf
1.72 .172(Some authors address this problem by choosing global threshold parameters to)J
126 232 :M
1.477 .148(distinguish the relations \(e.g. [3] [4] [27]\). As another example, Chou\325s stochastic)J
126 245 :M
.217 .022(grammar [13] encodes horizontal and vertical concatenation criteria into each production)J
126 258 :M
2.025 .203(rule. Two examples are as follows. An <)J
f4_10 sf
.704(Expression)A
f0_10 sf
1.529 .153(> and a <)J
f4_10 sf
.718(Factor)A
f0_10 sf
1.992 .199(> can be)J
126 271 :M
.286 .029(horizontally concatenated only if both have the same pointsize, and their baselines differ)J
126 284 :M
.364 .036(by at most one pixel. A <)J
f4_10 sf
.165(Symbol)A
f0_10 sf
.325 .032(> and a <)J
f4_10 sf
.141(Subscript)A
f0_10 sf
.643 .064(> can be horizontally concatenated)J
126 297 :M
.062 .006(only if the subscript has a smaller pointsize and a lower baseline.)J
126 320 :M
f4_10 sf
.22(5.1.2.\312Statistical\312labeling)A
141 338 :M
f0_10 sf
.37 .037(Extensive discussion of subscript and superscript identification is provided by Wang)J
126 351 :M
2.06 .206(and Faure [28]. This paper highlights the complexity of the task, and offers an)J
126 364 :M
.045 .005(interesting approach to its solution. Given a sequence of symbol-bounding-boxes that are)J
126 377 :M
1.4 .14(part of the same writing line, the task is to label the relationships between pairs of)J
126 390 :M
1.907 .191(symbols as exponent \()J
f4_10 sf
.666(E)A
f0_10 sf
1.372 .137(\), in-line \()J
f4_10 sf
.606(L)A
f0_10 sf
1.418 .142(\), or subscript \()J
f4_10 sf
.545(S)A
f0_10 sf
1.408 .141(\). \(Note that these are spatial)J
126 403 :M
1.22 .122(relationships, not logical relationships. The symbol pairs in the expression )J
f4_10 sf
.38(a)A
f0_8 sf
0 -3 rm
.304(2)A
0 3 rm
f4_10 sf
.38(b)A
f0_8 sf
0 -3 rm
.304(3)A
0 3 rm
f0_10 sf
.86 .086( are)J
126 416 :M
.793 .079(labeled )J
f4_10 sf
.404 .04(E S E)J
f0_10 sf
.674 .067(; later processing must determine that the )J
f4_10 sf
.228(b)A
f0_10 sf
.592 .059( is not logically a subscript of)J
126 429 :M
.382 .038(the 2.\) Both adjacent and non-adjacent pairs of symbols must be labeled. For example,)J
126 442 :M
f4_10 sf
.394(x)A
f4_8 sf
0 -3 rm
.355(a)A
0 3 rm
f4_6 sf
0 -2 rm
.148(i)A
0 2 rm
f0_10 sf
.69 .069( and )J
f4_10 sf
.394(x)A
f4_8 sf
0 -3 rm
.355(a)A
0 3 rm
f4_10 sf
.246(i)A
f0_10 sf
1.306 .131( have the same pairwise labelings \()J
f4_10 sf
.542(E)A
f0_10 sf
1.094 .109( followed by )J
f4_10 sf
.443(S)A
f0_10 sf
1.464 .146(\); to distinguish these)J
126 455 :M
1.031 .103(expressions, the )J
f4_10 sf
.255(x)A
f0_10 sf
.207(-to-)A
f4_10 sf
.16(i)A
f0_10 sf
.802 .08( relationship must be labeled as either )J
f4_10 sf
.351(E)A
f0_10 sf
.319 .032( or )J
f4_10 sf
.32(L)A
f0_10 sf
.884 .088(. Processing takes)J
126 468 :M
1.056 .106(place on bounding-box information alone; symbol identity is recognized later. Thus,)J
126 481 :M
1.116 .112(constraints based on symbol identity \(Sec. 5.1.3\), cannot be applied here. Similarly,)J
126 494 :M
1.209 .121(character-baseline information is unavailable. \(Ambiguity arises in cases such as )J
f4_10 sf
0 -2 rm
.316(y)A
0 2 rm
f4_9 sf
(c)S
126 507 :M
f0_10 sf
.2 .02(versus )J
f4_10 sf
.057(bc)A
f0_10 sf
.226 .023(; these have similarly-configured bounding boxes, but different spatial relations)J
126 520 :M
.37 .037(among the symbols.\))J
141 533 :M
-.005(Training data \(35 expressions produced by 7 writers\) is used to construct a recognizer.)A
126 546 :M
-.02(Two features are measured from each pair of bounding boxes: the height-ratio and vertical)A
126 559 :M
.68 .068(offset. A modified Ho\320Kashyap algorithm is used to place decision boundaries in this)J
126 572 :M
.114 .011(feature space. The space is divided into six regions \(exponent, either exponent or in-line,)J
126 585 :M
1.584 .158(in-line but on the exponent side, in-line but on the subscript side, either in-line or)J
126 598 :M
.198 .02(subscript, subscript\). This is done separately for each of the three following zones: taller)J
126 611 :M
.961 .096(box followed by a shorter box; two boxes of approximately equal height; shorter box)J
126 624 :M
(followed by a taller box.)S
141 637 :M
.545 .054(During classification, the feature space is used to calculate an initial estimate of the)J
126 650 :M
1.079 .108(probabilities of the )J
f4_10 sf
.431(E)A
f0_10 sf
.294 .029(, )J
f4_10 sf
.392(L)A
f0_10 sf
.548 .055( and )J
f4_10 sf
.353(S)A
f0_10 sf
.922 .092( labels for the given symbol pair. The final labeling is)J
endp
%%Page: 22 22
%%BeginPageSetup
initializepage
(; page: 22 of 26)setjob
%%EndPageSetup
-30 -31 :T
gS 30 31 552 730 rC
126 96 :M
f0_8 sf
.049 .005(22 )J
f4_8 sf
.203 .02(Handbook on Optical Character Recognition and Document Image Analysis)J
126 121 :M
f0_10 sf
1.489 .149(found by searching for the most-probable labeling that also satisfied the contextual)J
126 134 :M
.622 .062(constraints. These constraints eliminate impossible situations such as the following: in)J
126 147 :M
.602 .06(the symbol-triple )J
f4_10 sf
.161(ab)A
0 -2 rm
.143(c)A
0 2 rm
f0_10 sf
.175 .018(, if )J
f4_10 sf
.161(ab)A
f0_10 sf
.33 .033( is labeled )J
f4_10 sf
.179(L)A
f0_10 sf
.25 .025( and )J
f4_10 sf
.161(b)A
0 -2 rm
.143(c)A
0 2 rm
f0_10 sf
.33 .033( is labeled )J
f4_10 sf
.196(E)A
f0_10 sf
.294 .029(, then )J
f4_10 sf
.121<61CA>A
0 -2 rm
.143(c)A
0 2 rm
f0_10 sf
.382 .038( must be labeled )J
f4_10 sf
.196(E)A
f0_10 sf
(.)S
126 160 :M
1.095 .109(Testing results \(using expressions produced by writers who did not participate in the)J
126 173 :M
.315 .031(production of training data\) are promising. In a comparison with human labeling \(based)J
126 186 :M
.383 .038(on a presentation of bounding boxes\), the system had slightly higher error rates than the)J
126 199 :M
1.451 .145(humans. The authors propose addressing this by introducing directionality into the)J
126 212 :M
-.027(recognition process.)A
141 225 :M
.279 .028(This labeling process constitutes one recognition module in the complete recognition)J
126 238 :M
.125 .012(system [23] discussed in Sec. 3.5.)J
126 261 :M
f4_10 sf
.302(5.1.3.\312Constraints\312based\312on\312symbol\312identity)A
141 279 :M
f0_10 sf
2.655 .266(Another approach to sub- and superscript recognition is mentioned in [17].)J
126 292 :M
.46 .046(Recognition is based on spatial coordinates as well as local context. The system makes)J
126 305 :M
.243 .024(use of a priori information regarding legal configurations for superscripts and subscripts:)J
126 318 :M
.058 .006(for example, )J
f4_10 sf
(a)S
f4_9 sf
0 -3 rm
(x)S
0 3 rm
f0_10 sf
.028 .003( and )J
f4_10 sf
(x)S
f4_9 sf
0 2 rm
(n)S
0 -2 rm
f0_10 sf
.046 .005( are legal, whereas )J
f4_10 sf
(B)S
f0_9 sf
0 4 rm
(*)S
0 -4 rm
f0_10 sf
.028 .003( and )J
f4_10 sf
(X)S
f0_9 sf
0 -4 rm
(&)S
0 4 rm
f0_10 sf
.049 .005( are not. Similar constraints are used)J
126 331 :M
.354 .035(in [6].)J
126 356 :M
f6_10 sf
1.158(5.2.\312Recognizing\312Matrices)A
141 374 :M
f0_10 sf
1.28 .128(Matrix-recognition can be restricted to explicit matrices, or it can include linked)J
126 387 :M
.047 .005(vectors, in which a line connecting two matrix elements denotes an indeterminate number)J
126 400 :M
.022 .002(of intervening elements.)J
141 413 :M
.269 .027( Anderson presents a coordinate grammar for matrix notation, which recognizes both)J
126 426 :M
1.096 .11(explicit and linked matrices [3]. The matrix recognition is heavily dependent on the)J
126 439 :M
-.045(availability of three parameters:)A
139 452 :M
(mhmax)S
184 452 :M
-.026(maximum separation between two horizontally adjacent matrix elements)A
139 465 :M
(mvmax)S
184 465 :M
-.033(maximum separation between two vertically adjacent matrix elements)A
139 478 :M
-.072(vmax)A
184 478 :M
.215 .022(maximum vertical separation between adjacent characters belonging to the)J
184 491 :M
-.016(same matrix element)A
126 504 :M
.008 .001(The coordinate grammar recognizes rows, columns, or diagonals one at a time. Therefore)J
126 517 :M
.296 .03(it never obtains an overall view of matrix structure. For example, suppose that the input)J
126 530 :M
.006 .001(is a \322matrix\323 with a variable number of entries in each row. The grammar does not notice)J
126 543 :M
1.467 .147(this; it parses the input as an EXPLICITARRAY and reports the number of matrix)J
126 556 :M
1.004 .1(columns as equal to the number of entries in the last row of the matrix. It would be)J
126 569 :M
.859 .086(interesting to explore whether the coordinate-grammar formalism can produce a fuller)J
126 582 :M
.066 .007(analysis of matrix structure.)J
141 595 :M
.263 .026(In [6], analysis of explicit matrices begins by finding a pair of delimiters of the same)J
126 608 :M
-.011(size and type. Next a horizontal projection profile is computed for the delimited region; if)A
126 621 :M
.202 .02(this profile exhibits periodicity \(indicating several rows of similar height\), then a vertical)J
126 634 :M
.247 .025(projection profile is used to separate the columns. Finally, each matrix entry is analyzed)J
126 647 :M
.284 .028(as an expression in its own right.)J
endp
%%Page: 23 23
%%BeginPageSetup
initializepage
(; page: 23 of 26)setjob
%%EndPageSetup
-30 -31 :T
gS 30 31 552 730 rC
347 96 :M
f0_8 sf
.126 .013(Recognition of Mathematical Notation 23)J
141 123 :M
f0_10 sf
2.001 .2(Another approach to matrix recognition is mentioned in [17]. First a pair of)J
126 136 :M
.289 .029(enclosure symbols are found. Symbols within this area are grouped based on proximity;)J
126 149 :M
.084 .008(no details of the proximity metric are given.)J
126 174 :M
f2_10 sf
.985(6.\312On-line\312Recognition\312of\312Handwritten\312Expressions)A
141 192 :M
f0_10 sf
1.248 .125(A data tablet offers the possibility of using timing information to assist with the)J
126 205 :M
-.011(recognition of a mathematical expression.)A
141 218 :M
.597 .06(Chen and Yin describe a system for recognizing handwritten mathematical notation)J
126 231 :M
.656 .066([27]. The emphasis of this work is on symbol segmentation \(i.e. collecting the strokes)J
126 244 :M
.513 .051(that make up a single symbol\) and symbol recognition. Symbol segmentation proceeds)J
126 257 :M
-.011(by surrounding each stroke with a frame \(a bounding box\), and testing consecutive frames)A
126 270 :M
.103 .01(for overlap in )J
f4_10 sf
(X)S
f0_10 sf
.063 .006( and )J
f4_10 sf
(Y)S
f0_10 sf
.131 .013( projections. Special tests are performed to unify two-part symbols)J
126 283 :M
.311 .031(such as )J
f4_10 sf
.076(i)A
f0_10 sf
.114 .011(, )J
f4_10 sf
.076(j)A
f0_10 sf
.388 .039(, =, )J
cF
f1_10 sf
.039A
sf
.388 .039(, )J
cF
f1_10 sf
.039A
sf
.388 .039(. Also, special tests are performed for the square-root symbol, which)J
126 296 :M
.877 .088(obscures gaps in the )J
f4_10 sf
.392(X)A
f0_10 sf
.5 .05( and )J
f4_10 sf
.357(Y)A
f0_10 sf
.985 .099( projections of symbols inside it. Symbol recognition is)J
126 309 :M
-.032(performed using a nearest-neighbor algorithm, with features coded from stroke types \(line,)A
126 322 :M
.262 .026(clockwise curve, counterclockwise curve, circle\). Multi-character classes are created for)J
126 335 :M
1.121 .112(confusion-prone symbols, such as \3221\323 versus \322/\323, \3220\323 versus \322O\323, or \322C\323 versus \322\(\323.)J
126 348 :M
2.277 .228(After nearest-neighbor classification, specific contextual constraints are tested to)J
126 361 :M
.195 .019(disambiguate symbols in these multi-character classes. For example, if two operands are)J
126 374 :M
1.116 .112(found on either side of a \3221 or /\323 character, then this character is classified as a \322/\323,)J
126 387 :M
.367 .037(otherwise as a \3221\323. If the system rejects a character, or fails to disambiguate it, the user)J
126 400 :M
.133 .013(is asked for correction. Recognition results are presented for seven writers entering eight)J
126 413 :M
.109 .011(test expressions; the overall symbol-recognition rate is 94%.)J
141 426 :M
.357 .036(On-line data is analyzed in [7]; few details are given, but they do mention the use of)J
126 439 :M
-.023(elastic matching \(dynamic time warping\).)A
141 452 :M
-.018(The system by Faure and Wang [23] [28] is geared toward recognizing the structure of)A
126 465 :M
.927 .093(handwritten mathematical notation. On-line information is used as needed during the)J
126 478 :M
.165 .017(knowledge-driven segmentation module. Considerable variability in the handwriting can)J
126 491 :M
.032 .003(be tolerated. Sec. 3.5 provides further discussion of this work.)J
141 504 :M
.425 .043(Recognition of handwritten expressions is treated in [18], as discussed in Sec. 3.1.1.)J
126 517 :M
1.486 .149(Timing information \(from the data tablet\) is used in extracting strokes for symbol)J
126 530 :M
.125 .013(recognition, but is not used during syntactic analysis.)J
126 555 :M
f2_10 sf
1.04(7.\312Summary\312and\312Conclusions)A
141 573 :M
f0_10 sf
.358 .036(Mathematics recognition is a practically-important problem. Recognition is difficult)J
126 586 :M
-.031(because mathematical notation is only semi-standardized, conveys meaning through subtle)A
126 599 :M
.075 .007(use of spatial relationships, involves a large alphabet of symbols and a large range of font)J
126 612 :M
.87 .087(sizes, and contains little redundancy in its representation of information. Comparison)J
126 625 :M
.585 .059(among existing mathematics-recognition systems is complicated by the myriad ways in)J
126 638 :M
1.015 .102(which the mathematics-recognition problem can be defined. Input may be typeset or)J
126 651 :M
.828 .083(handwritten, on-line or off-line, input expressions may be isolated or mixed with text,)J
endp
%%Page: 24 24
%%BeginPageSetup
initializepage
(; page: 24 of 26)setjob
%%EndPageSetup
-30 -31 :T
gS 30 31 552 730 rC
126 96 :M
f0_8 sf
.049 .005(24 )J
f4_8 sf
.203 .02(Handbook on Optical Character Recognition and Document Image Analysis)J
126 123 :M
f0_10 sf
-.058(recognizable expression layouts may be restricted to a greater or lesser degree. In addition,)A
126 136 :M
.172 .017(some recognizers assume pixels as input, whereas others assume that symbol-recognition)J
126 149 :M
.539 .054(has already taken place. This great variation in problem-definition makes it difficult to)J
126 162 :M
1.38 .138(compare the strengths and weaknesses of existing mathematics recognition systems.)J
126 175 :M
1.045 .104(Research is needed to clarify the definition of mathematical notation and its dialects.)J
126 188 :M
2.183 .218(Such a definition could provide a basis for more meaningful comparison among)J
126 201 :M
-.002(mathematics-recognition systems.)A
141 214 :M
.91 .091(A variety of system architectures are used for mathematics recognition. Syntactic)J
126 227 :M
1.14 .114(analysis involves parsing an expression using a two-dimensional grammar, such as a)J
126 240 :M
.039 .004(coordinate grammar or stochastic grammar, after symbol recognition has been performed.)J
126 253 :M
1.149 .115(A grammar provides a clear, explicit representation of mathematical-notation syntax,)J
126 266 :M
-.005(although parsing can be computationally expensive. Projection-profile cutting determines)A
126 279 :M
.68 .068(the structure of an expression by recursively dividing the image into subregions \(using)J
126 292 :M
.12 .012(minima in the horizontal and vertical projection profiles\); this can be done before symbol)J
126 305 :M
.774 .077(recognition is performed. This simple and efficient technique is suitable for solving a)J
126 318 :M
1.56 .156(restricted part of the mathematics-recognition problem. Graph rewriting represents)J
126 331 :M
.341 .034(symbols and symbol-relationships as a graph, rewriting parts of the graph as recognition)J
126 344 :M
.837 .084(proceeds. This offers a flexible means of applying extensive knowledge of notational)J
126 357 :M
1.967 .197(conventions; however, current graph-rewriting environments execute quite slowly.)J
126 370 :M
.158 .016(Procedurally-coded rules provide step-by-step instructions for recognizing an expression.)J
126 383 :M
1.128 .113(Unless a systematic organization of rules is provided, such a system can become ill-)J
126 396 :M
-.002(understood and unmanageable due to the unexpected interactions among the unstructured,)A
126 409 :M
.238 .024(often ad hoc recognition rules. The data-driven and knowledge-driven modules of Faure)J
126 422 :M
1.642 .164(and Wang illustrate one approach for systematically organizing procedurally-coded)J
126 435 :M
(recognition rules.)S
141 448 :M
-.015(Whatever recognition approach is used, the structure of recognizable expressions must)A
126 461 :M
-.02(be characterized. Such a syntax for mathematics may be defined implicitly or explicitly. A)A
126 474 :M
1.232 .123(major objective is to define the syntax cleanly, to provide a unifying framework for)J
126 487 :M
-.04(handling the myriad details and exceptions that arise during mathematics recognition.)A
126 525 :M
f2_10 sf
.597(References)A
125 540 :M
f0_9 sf
.255([1])A
148 540 :M
.533 .053(Y. Nakayama, Mathematical formula editor for CAI, )J
f4_9 sf
.559 .056(Proc. ACM SIGCHI Conf. on Human)J
148 550 :M
1.332 .133(Factors in Computing Systems)J
f0_9 sf
1.112 .111(, Austin, Texas, April 1989, 387\320392.)J
125 561 :M
.255([2])A
148 561 :M
2.983 .298(D. Blostein, General diagram-recognition methodologies, )J
f4_9 sf
2.494 .249(Proc. Int. Workshop on)J
148 571 :M
1.959 .196(Graphics Recognition)J
f0_9 sf
1.299 .13(, University Park, Pennsylvania, Aug. 1995, 200\320212.)J
125 582 :M
.255([3])A
148 582 :M
4.431 .443(R. Anderson, Two-dimensional mathematical notation, in )J
f4_9 sf
5.816 .582(Syntactic Pattern)J
148 592 :M
1.888 .189(Recognition, Applications)J
f0_9 sf
1.052 .105(, ed. K. S. Fu \(Springer -Verlag,1977\) 147\320177.)J
125 603 :M
.255([4])A
148 603 :M
2.717 .272(S. Chang, A method for the structural analysis of two-dimensional mathematical)J
148 613 :M
1.742 .174(expressions, )J
f4_9 sf
2.19 .219(Information Sciences)J
f0_9 sf
.176 .018( )J
f2_9 sf
.388(2)A
f0_9 sf
1.279 .128(, 3 \(1970\) 253\320272.)J
125 624 :M
.255([5])A
148 624 :M
2.111 .211(A. Grbavec and D. Blostein, Mathematics recognition using graph rewriting, )J
f4_9 sf
.663(Third)A
148 634 :M
3.015 .301(Int.Conf. on Document Analysis and Recognition)J
f0_9 sf
2.699 .27(, Montreal, Canada, Aug. 1995,)J
148 644 :M
.607(417\320421.)A
endp
%%Page: 25 25
%%BeginPageSetup
initializepage
(; page: 25 of 26)setjob
%%EndPageSetup
-30 -31 :T
gS 30 31 552 730 rC
347 96 :M
f0_8 sf
.126 .013(Recognition of Mathematical Notation 25)J
125 120 :M
f0_9 sf
.255([6])A
148 120 :M
1.612 .161(H. Twaakyondo and M. Okamoto, Structure analysis and recognition of mathematical)J
148 130 :M
1.866 .187(expressions, )J
f4_9 sf
1.483 .148(Proc. Third Int. Conf. on Document Analysis and Recognition)J
f0_9 sf
1.834 .183(, Montreal,)J
148 140 :M
1.297 .13(Canada, Aug. 1995, 430\320437.)J
125 151 :M
.255([7])A
148 151 :M
1.098 .11(Y. Dimitriadis, J. Coronado, and C. de la Maza, A new interactive mathematical editor,)J
148 161 :M
1.885 .189(using on-line handwritten symbol recognition, and error detection-correction with an)J
148 171 :M
1.422 .142(attribute grammar, )J
f4_9 sf
1.272 .127(Proc. First Int. Conf. on Document Analysis and Recognition)J
f0_9 sf
1.152 .115(, Saint)J
148 181 :M
1.476 .148(Malo, France, Sept. 1991, 242\320250.)J
125 192 :M
.255([8])A
148 192 :M
1.04 .104(T. Chaundy, P. Barrett, and C. Batey, )J
f4_9 sf
1.49 .149(The Printing of Mathematics)J
f0_9 sf
1.54 .154( \(Oxford University)J
148 202 :M
1.937 .194(Press, 1957\).)J
125 213 :M
.255([9])A
148 213 :M
1.019 .102(K. Wick, )J
f4_9 sf
1.679 .168(Rules for Typesetting Mathematics)J
f0_9 sf
1.163 .116(, translated by V. Boublik and M. Hejlova)J
148 223 :M
.824 .082(\(The Hague, Mouton, 1965\).)J
125 234 :M
.337([10])A
148 234 :M
1.2 .12(N. Higham, )J
f4_9 sf
1.442 .144(Handbook of Writing for the Mathematical Sciences)J
f0_9 sf
1.661 .166( \(SIAM, Philadelphia,)J
148 244 :M
.551(1993\).)A
125 255 :M
.337([11])A
148 255 :M
1.698 .17(D. Knuth, Mathematical typography, )J
f4_9 sf
1.617 .162(Bulletin of the American Mathematical Soc.)J
f0_9 sf
.193 .019( )J
f2_9 sf
.424(1)A
f0_9 sf
.706 .071(, 2)J
148 265 :M
.46(\(1979\).)A
125 276 :M
.337([12])A
148 276 :M
1.967 .197(W. Martin, Computer input/output of mathematical expressions, )J
f4_9 sf
1.674 .167(Proc. 2nd Symp. on)J
148 286 :M
1.255 .126(Symbolic and Algebraic Manipulations)J
f0_9 sf
.875 .087(, New York, 1971, 78\32087.)J
125 297 :M
.337([13])A
148 297 :M
2.343 .234(P. Chou, Recognition of equations using a two-dimensional stochastic context-free)J
148 307 :M
.784 .078(grammar, )J
f4_9 sf
.711 .071(Proc. SPIE Visual Communications and Image Processing IV)J
f0_9 sf
.713 .071(, Philadelphia PA,)J
148 317 :M
3.84 .384(Nov. 1989,\312852\320863.)J
125 328 :M
.337([14])A
148 328 :M
1.031 .103(M. Okamoto and B. Miao, Recognition of mathematical expressions by using the layout)J
148 338 :M
1.203 .12(structure of symbols, in )J
f4_9 sf
1.424 .142(Proc. First Int. Conf. on Document Analysis and Recognition)J
f0_9 sf
(,)S
148 348 :M
1.351 .135(Saint Malo, France, Sept. 1991, 242\320250.)J
125 359 :M
.337([15])A
148 359 :M
2.603 .26(J. Ha, R. Haralick, and I. Phillips, Understanding mathematical expressions from)J
148 369 :M
2.798 .28(document images, )J
f4_9 sf
2.454 .245(Proc. Third Int. Conf. on Document Analysis and Recognition)J
f0_9 sf
(,)S
148 379 :M
1.287 .129(Montreal, Canada, Aug. 1995, 956\320959.)J
125 390 :M
.337([16])A
148 390 :M
1.869 .187(D. Blostein and H. Baird, A critical survey of music image analysis, in )J
f4_9 sf
.621(Structured)A
148 400 :M
.922 .092(Document Image Analysis)J
f0_9 sf
.643 .064(, eds. H. Baird, H. Bunke, and K. Yamamoto, \(Springer-Verlag,)J
148 410 :M
2.611 .261(1992\) 405\320434.)J
125 421 :M
.337([17])A
148 421 :M
1.639 .164(H. Lee and J. Wang, Design of a mathematical expression recognition system, )J
f4_9 sf
.559(Proc.)A
148 431 :M
1.198 .12(Third Int. Conf. on Document Analysis and Recognition)J
f0_9 sf
1.207 .121(, Montreal, Canada, Aug. 1995,)J
148 441 :M
.583(1084\3201087.)A
125 452 :M
.337([18])A
148 452 :M
1.901 .19(A. Belaid and J. Haton, A syntactic approach for handwritten mathematical formula)J
148 462 :M
1.185 .119(recognition, )J
f4_9 sf
.999 .1(IEEE Trans. Pattern Analysis and Machine Intell.)J
f0_9 sf
.225 .022(, )J
f2_9 sf
.27(6)A
f0_9 sf
.889 .089(, 1 \(1984\) 105\320111.)J
125 473 :M
.337([19])A
148 473 :M
3.465 .346(M. Okamoto and A. Miyazawa, An experimental implementation of document)J
148 483 :M
2.574 .257(recognition system for papers containing mathematical expressions, in )J
f4_9 sf
.638(Structured)A
148 493 :M
1.244 .124(Document Image Analysis)J
f0_9 sf
.862 .086(, eds. H. Baird, H. Bunke, and K. Yamamoto \(Springer-Verlag)J
148 503 :M
1.411 .141(1992\) 36\32053. \(Earlier version in )J
f4_9 sf
1.881 .188(Proc. IAPR Workshop on Statistical and Structural)J
148 513 :M
1.391 .139(Pattern Recognition)J
f0_9 sf
.844 .084(, Murray Hill, New Jersey, June 1990, 335\320350.\))J
125 524 :M
.337([20])A
148 524 :M
.568 .057(A. Murase, T. Satou, and M. Nakagawa, Prototyping of METAH, a recognition system for)J
148 534 :M
1.301 .13(on-line handwritten mathematical expressions, )J
f4_9 sf
1.239 .124(Information Processing Society of Japan)J
148 544 :M
1.525 .152(SIG Notes)J
f0_9 sf
.296 .03(, )J
f2_9 sf
.355(93)A
f0_9 sf
1.015 .102(, 35 \(1993\) 25\32032 \(in Japanese\).)J
125 555 :M
.337([21])A
148 555 :M
2.053 .205(M. Okamoto and H. Higashi, Mathematical expression recognition by the layout of)J
148 565 :M
1.491 .149(symbols, )J
f4_9 sf
1.81 .181(Trans. IEIEC)J
f0_9 sf
.168 .017( )J
f2_9 sf
.339(J78-D-II)A
f0_9 sf
1.217 .122(, 3, \(1995\) 474\320482 \(in Japanese\).)J
125 576 :M
.337([22])A
148 576 :M
1.702 .17(M. Okamoto and H. Twaakyondo, Mathematical expression recognition by projection)J
148 586 :M
1.361 .136(profile characteristics, )J
f4_9 sf
1.643 .164(Trans. IEIEC)J
f0_9 sf
.152 .015( )J
f2_9 sf
.307(J78-D-II)A
f0_9 sf
1.097 .11(, 2 \(1995\) 366\320370 \(in Japanese\).)J
125 597 :M
.337([23])A
148 597 :M
.626 .063(C. Faure and Z. Wang, Automatic perception of the structure of handwritten mathematical)J
148 607 :M
.88 .088(expressions, in )J
f4_9 sf
1.205 .121(Computer Processing of Handwriting)J
f0_9 sf
.984 .098( \(World Scientific, 1990\) 337\320361.)J
125 618 :M
.337([24])A
148 618 :M
.578 .058(H. Lee and M. Lee, Understanding mathematical expressions in a printed document, )J
f4_9 sf
.188(Proc.)A
148 628 :M
.57(Second)A
f0_9 sf
.269 .027( )J
f4_9 sf
2.349 .235(Int. Conf. Document Analysis and Recognition)J
f0_9 sf
2.018 .202(, Tsukuba, Japan, Oct. 1993,)J
148 638 :M
.607(502\320505.)A
endp
%%Page: 26 26
%%BeginPageSetup
initializepage
(; page: 26 of 26)setjob
%%EndPageSetup
-30 -31 :T
gS 30 31 552 730 rC
126 96 :M
f0_8 sf
.049 .005(26 )J
f4_8 sf
.203 .02(Handbook on Optical Character Recognition and Document Image Analysis)J
125 120 :M
f0_9 sf
.337([25])A
148 120 :M
1.47 .147(H. Lee and M. Lee, Understanding mathematical expressions using procedure-oriented)J
148 130 :M
1.902 .19(transformation, )J
f4_9 sf
2.158 .216(Pattern Recognition)J
f0_9 sf
.176 .018( )J
f2_9 sf
.387(27)A
f0_9 sf
1.277 .128(, 3 \(1994\) 447\320457.)J
125 141 :M
1.434 .143([26] G. Kopec and P. Chou, Document image decoding using markov source models, )J
f4_9 sf
.629(IEEE)A
148 151 :M
1.192 .119(Trans. Pattern Analysis and Machine Intelligence)J
f0_9 sf
.133 .013( )J
f2_9 sf
.293(16)A
f0_9 sf
.966 .097(, 6 \(1994\) 602\320617.)J
125 162 :M
.337([27])A
148 162 :M
2.052 .205(L. Chen and P. Yin, A system for on-line recognition of handwritten mathematical)J
148 172 :M
2.756 .276(expressions, )J
f4_9 sf
2.522 .252(Computer Processing of Chinese and Oriental Languages)J
f0_9 sf
.279 .028( )J
f2_9 sf
.614(6)A
f0_9 sf
1.657 .166(, 1 \(1992\))J
148 182 :M
.65(19\32039.)A
125 193 :M
.337([28])A
148 193 :M
.614 .061(Z. Wang and C. Faure, Structural analysis of handwritten mathematical expressions, )J
f4_9 sf
.191(Proc.)A
148 203 :M
1.259 .126(Ninth Int. Conf. on Pattern Recognition)J
f0_9 sf
1.151 .115(, Rome, Italy, Nov. 1988, 32\32034.)J
endp
%%Trailer
end
%%EOF