Jou nal o Compu ing and In o ma ion Technology - CIT 9, 2001, 2, 101–112 101
Recognizing Typese Documen s
using Walsh T ans o ma ion
A ila Fazekas and And ´
as Hajdu
Uni e si y o Deb ecen, Hunga y
In his pape we p esen an e ec i e cha ac e ecogni ion
algo i hm, which can be applied mainly o ypese docu-
men s. Ou aim was o compose a cha ac e ecogni ion
algo i hm, which can be used o ecognize simple ypese
documen s in a as and eliable way. To ge a good
esul by his algo i hm he inpu ex documen should
con ain cha ac e s om he same cha ac e se wi h a
small numbe o symbols. This condi ion does no mean
a s ong es ic ion as he documen s in p ac ice usually
ha e his p ope y. The main cha ac e ecogni ion pa
o he algo i hm is based on he Walsh ans o ma ion,
which gi es a e bose desc ip ion abou he image, like
he symme ical ela ions, placemen o he o eg ound
and backg ound pixels, and so on. Tha is why we ied
o apply i o ecognize cha ac e s, and he algo i hm
p o ed o be ai ly e icien and eliable o simple
documen s, since he ea u e ec o s ex ac ed by Walsh
ans o ma ion can be well dis inguished. Mo eo e , ou
me hod had e y good esul s in ole a ing di e en ypes
o noise co up ion.
Keywo ds: op ical cha ac e ecogni ion, Walsh ans-
o ma ion
1. In oduc ion
The his o y o cha ac e ecogni ion analysed by
he ools o digi al image p ocessing da es back
o he 1950’s
(
O.D. TRIER e al
(
1996
))
.New
p oblems and challenges occu ed in p ac ical
applica ions and se e al cha ac e ecogni ion
me hods we e de eloped o sol e hem. Mos
o hese cha ac e ecogni ion algo i hms can
be applied o ypese documen s, and he e exis
p ocedu es o p ocess handw i en cha ac e s.
Cha ac e ecogni ion algo i hms a e based on
di e en me hods, acco ding o he ype o he
ex hey a e o be applied o. The i s s ep
one should ake du ing a cha ac e ecogni ion
p ocess is o selec he mos sui able me hod o
he speci ic applica ion.
A cha ac e ecogni ion p ocess usually includes
he scanning s ep, p ep ocessing
(
bina iza ion –
segmen a ion
)
, ea u e ex ac ion
(
skele oniza-
ion – con ou ex ac ion
)
, he ac ual ecogni-
ion and classi ica ion, some imes pos p ocess-
ing, and e i ica ion. Fo a comp ehensi e su -
ey on ea u e ex ac ion me hods, see O.D.
TRIER e al
(
1996
)
, whe e se e al algo i hms
a e p esen ed and compa ed. A commonly used
me hod p oduces hinning o he cha ac e s o
ob ain hei skele ons so he ecogni ion is based
on some kind o skele on analysis. An o e iew
on cha ac e ecogni ion algo i hms, which a e
based on hinning, can be ound in R.W. SMITH
(
1987
)
. Skele oniza ion is applied o eplace he
o iginal image wi h a smalle da a s uc u e and
has he ad an age o sa ing memo y.
Algo i hms o ecognizing bo h ypese and
handw i en cha ac e s can be based on p ojec-
ion his og ams, zoning o , as a mo e heo e ical
analysis, he ecogni ion can be execu ed ac-
co ding o he Fou ie desc ip o s O.D. TRIER
e al
(
1996
)
.
Recogni ion o handw i en cha ac e s is a mo e
sophis ica ed p oblem han he ecogni ion o
machine – p in ed ex . Nowadays, OCR pack-
ages a e able o ecognize only nea ly w i en
ex , bu esea ch is being done in o de o en-
able ecogni ion o common handw i en docu-
men s as well. One o hese algo i hms con ains
a hinning s ep and an addi ional s oke segmen-
a ion pa is inse ed o enable he algo i hm o
ecognize Chinese cha ac e s K.W. GAN e al
(
1991
)
, J.Y. LIN a al
(
1995
)
, H. OGAWA a al
(
1982
)
. Recogni ion o he A abic sc ip is also
a popula esea ch a ea wi h g owing li e a u e
S.A. MAHMOUD e al
(
1991
)
.
102 Recognizing Typese Documen s using Walsh T ans o ma ion
Ou algo i hm suppo s he ecogni ion o only
ypese and no handw i en documen s. We o-
cused on segmen a ion, and classi ica ion and
made some expe imen s o e i y he eliabili y
o ou cha ac e ecogni ion me hod. To clas-
si y a cha ac e , usually a ea u e ec o is com-
posed and he ac ual ecogni ion is achie ed by
sea ching o he closes p o o ype ea u e ec-
o . Dimension o he ea u e ec o can a y
om one applica ion o ano he and we also
ha e o choose a sui able me ics o measu e he
di e ence be ween wo ea u e ec o s. In ou
analyses we ied o ind a me hod, which gen-
e a es easily sepa able ea u e ec o s, ha is,
he p o o ype ec o s ha e la ge dis ance om
one o ano he . We ound ha he well-known
Walsh ans o ma ion has his p ope y, so ha
he ea u e ec o s gene a ed by Walsh ans o -
ma ion can be sepa a ed mo e e ec i ely han in
he case o o he popula cha ac e ecogni ion
me hods like zoning o p ojec ion his og ams.
Using Walsh ans o ma ion wi h unde de e -
mined ea u e ec o s we also ob ain a noise
il e ing e ec , which is e y use ul in cha ac-
e ecogni ion p ocesses.
We skipped he ea u e ex ac ion s ep, since he
classi ica ion s ep o ou algo i hm is based on
he Walsh ans o ms o he image, which can
be calcula ed wi hou any modi ica ions.
2. Desc ip ion o he Recogni ion Sys em
Ou algo i hm was de eloped o be applied o
ex documen s, which include cha ac e s om
a cha ac e se wi h a small numbe
(
84
)
o
symbols. Recognizable cha ac e s a e le e s,
numbe s, sepa a o s, punc ua ion ma ks, and so
on.
A he i s s ep o he algo i hm a segmen a-
ion p ocedu e di ides he o iginal bina y image
in o smalle ones, and hese smalle segmen s
a e s o ed in a chained lis . These segmen s a e
ac ually ec angles, and beside he image in o -
ma ion, he coo dina es o he uppe le pixel
and he size o he ec angle a e also s o ed o
e e y segmen . De ailed desc ip ion o his seg-
men a ion algo i hm can be ound in Sec ion 3.
Ou cha ac e ecogni ion me hod is based on
he Walsh ans o ma ion, which is desc ibed in
Sec ion 4. Fo e e y segmen a 64-dimensional
ea u e ec o is composed acco ding o he i s
64 Walsh ans o ms o he segmen .
A e calcula ing he ea u e ec o o a gi en
segmen , we judge whe he he segmen con-
ains ex in o ma ion
(
le e , numbe , e c.
)
,o
an un ecognizable symbol. Sec ion 5 summa-
izes he way how he decision is made and he
possibili ies how he algo i hm can be ained.
The scheme in Figu e 1 b ie ly desc ibes how
he algo i hm ope a es.
We used a commonly applied cha ac e se o
es ou algo i hm om se e al di e en poin s
o iew, like compu a ion speed, noise sensi i-
i y, ecogni ion ailu e. We made o he s a is-
ical in es iga ions as well, such as co ela ion
analysis. Ou expe imen al esul s a e summa-
ized in Sec ion 6.
Finally, Sec ion 7 con ains ou conclusions and
ecommenda ions abou he easibili y o he
me hod.
Fig. 1. Theo e ical scheme o he algo i hm.
Recognizing Typese Documen s using Walsh T ans o ma ion 103
3. Segmen a ion
The i s s ep o he algo i hm pe o ms a seg-
men a ion p ocedu e on he digi al image. We
y o de e mine minimal s o ing ec angles o
hose subse s o he image o eg ound, which
can be sepa a ed by ho izon al and e ical lines.
These ec angles can be de e mined by calcula -
ing hei size and he coo dina es o hei uppe
le pixel. These s o ing ec angles a e some-
imes e e ed o as segmen s. Using s o ing
ec angles, ou segmen a ion p ocedu e does no
ex ac he connec ed o eg ound componen s
in he case o a liga u e. This segmen a ion
me hod is able o handle liga u e appea ances
in he ex , which depend on he cha ac e se
applied. In he case o a liga u e ecogni ion is
ob iously unsuccess ul, since he pic u e o he
le e s changes d as ically, see Figu e 3, whe e a
liga u e “ i” appea s in he Hunga ian wo d “ i-
gyelo
00
”
(
obse e
)
. Ou algo i hm is p econdi-
ioned o his phenomenon, and can be ained
o ecognize liga u es. In ou expe imen s we
also used a CMR cha ac e se which allows
liga u es besides he liga u e- ee se s OCR-A
and OCR-B
(
which we e composed o op ical
cha ac e ecogni ion
)
.
Segmen a ion can be made pa allel easily, and
he whole p ocedu e can be pe o med as an al-
e na ing ecu si e sequence o ho izon al and
e ical segmen a ion s eps. Ho izon al seg-
men a ion s eps a e ollowed by e ical seg-
men a ion s eps, and ice e sa. Al e na ing
ho izon al and e ical segmen a ion s eps, each
o he exis ing segmen s is di ided in o smalle
segmen s. I he numbe o segmen s does no
change du ing a segmen a ion s ep, he algo-
i hm s ops. The ollowing desc ip ion explains
b ie ly – in me a language o ma – how he
segmen a ion p ocedu e wo ks:
Type SP=^Segmen 
Segmen =Reco d O
X,Y:Wo d {*Uppe le pixel coo dina es*}
LX,LY:Wo d {*Size o he segmen *}
Code:By e {*Code o he ecognized cha ac e *}
Pic u e:Poin e  {*The add ess o he segmen *}
Nex :SP {*Nex elemen o he chained lis *}
End
.
.
.
Func ion HSegmen a ion(Va Head:SP):Boolean {*T ue i a new segmen is de ined*}
Va NewHead:SP {*New segmen *}
Va SY,EY:Wo d {*Beginning and end o he segmen *}
Begin
SY:=Nex Emp yLine
EY:=Nex Emp yLine
I (SY=Head^.Y) And (EY=Head^.Y+Head^.LY-1) Then
HSegmen a ion:=False {*Image canno be segmen ed any mo e*}
Exi
End
While (EY-SY<>1) Do Begin {*Igno ing pai s o emp y lines*}
SY:=EY
EY:=Nex Emp yLine
End
New(NewHead) {*C ea ing a new elemen in he lis *}
Cu Pic u e(Head,NewHead,SY,EY) {*Cu en segmen is de ined by SY,EY*}
NewHead^.Nex :=Head^.Nex 
Head^.Nex :=NewHead
Head:=NewHead
HSegmen a ion:=HSegmen a ion(Head) O T ue
{*P ocessing he image pa emained*}
End
Fig. 2. Desc ip ion o he segmen a ion algo i hm in me a language o ma .
104 Recognizing Typese Documen s using Walsh T ans o ma ion
Ho izon al segmen a ion s ep:
We ha e a pixel
unning om le o igh , s a ing om he up-
pe le co ne o e e y segmen we ha e al eady
ex ac ed. I we ind an objec
(
o eg ound
)
poin in he gi en ow, hen we go down one
pixel and s a o un a pixel om he begin-
ning o his ow. The p ocedu e con inues ill
he unning pixel eaches he igh side o he
segmen
(
we ind a ow which does no con ain
objec poin s
)
. In his case we ob ain a new
segmen . The op ow o he new segmen will
be he uppe mos ow o he o iginal segmen ,
which con ains an objec poin . The bo om ow
o he new segmen will be he lowe mos ow
o he o iginal segmen , which has been al eady
p ocessed and con ains an objec poin . A e
de ining he new segmen , we go on wi h p o-
cessing he o iginal segmen , s a ing om ha
ow which did no con ain any objec poin s.
Ve ical segmen a ion s ep:
Ve ical segmen a-
ion p ocedu e is analogous o he ho izon al
one, bu he e he pixel uns om op o bo om,
s a ing om he uppe le co ne o a segmen .
We go igh one pixel ill a column is ound,
which does no con ain objec poin s. In his
case a new segmen is de ined.
In he i s s ep o he segmen a ion p ocedu e
he whole o iginal bina y image is conside ed
as he ini ial segmen , and a ho izon al segmen-
a ion s ep is pe o med. The segmen a ion al-
go i hm s ops i du ing a ho izon al o e ical
segmen a ion s ep we canno ind a ow o a col-
umn, which does no con ain an objec poin —
in o he wo ds, new segmen s canno be de ined.
The s eps o he segmen a ion algo i hm de-
sc ibed abo e can be seen in he ollowing ig-
u e, whe e he segmen s a e ep esen ed by ec -
angles. I he o iginal bina y image is a ex doc-
umen , he esul o he i s
(
ho izon al
)
s ep is
a line o ex .
Fig. 3. The esul o he segmen a ion a e he second
and ou h s eps.
No ice ha he op o he line is de e mined
by he highes cha ac e
(
“ ”
)
, and he bo om
is de e mined by he lowes cha ac e
(
“g”
)
.
The second
(
e ical
)
segmen a ion s ep di ides
he ex line in o cha ac e s, bu he ec angles
ha s o e he cha ac e s con ain ela i ely la ge
backg ound componen s, which can be elimi-
na ed wi h he ollowing
(
ho izon al
)
segmen-
a ion s ep. I he documen con ains some
g aphic pa s, hen he numbe o segmen a ion
s eps necessa y o segmen such a g aphic pa ,
depends on he complexi y o he g aphics.
Segmen a ion o he accen ed cha ac e s is an
in e es ing and di icul p oblem. In he case o
an English ex , a e h ee segmen a ion s eps
(
ho izon al – e ical – ho izon al
)
he s o ing
ec angles canno be educed any mo e, while
in he case o a Hunga ian ex which con ains
accen ed cha ac e s, we ha e he same si ua ion
only a e he ou h segmen a ion s ep. Figu e
3 illus a es his case as well, whe e segmen-
a ion o he Hunga ian accen ed cha ac e “o
00
”
is pe o med in ou s eps. Recogni ion o ac-
cen ed cha ac e s is a he di icul way, since
he accen is segmen ed sepa a ely. Analyzing
he posi ion o he segmen s o small size can
help o ecognize hese cha ac e s. Fo example,
i can be use ul o examine i a owel akes place
below a segmen o small size. Ou sys em was
no ained o ecognize accen ed cha ac e s in
ou analysis.
The inpu image
(
a ex documen
)
can be dis-
o ed in se e al ways: o a ed, co up ed by
noise, e c. The image may be o a ed i e.g. he
documen was inse ed in o he scanne in an
imp ope way. Ou me hod ole a es o a ion
o small deg ees. I he o a ion deg ee is oo
la ge, ho izon al segmen a ion is no able o sep-
a a e he documen lines in he i s s ep, since
he lowes pixel o a line is “unde ” he high-
es pixel o he nex line. The highes o a ion
deg ee ha may be ole a ed can be ob ained as
α
=
a c an line-space
pape wid h
;
ho izon al ma gins
:
(
3.1
)
Fo example, i we assume he line-space o be
4 mm and he page size o be A4 wi h small ma -
gins, he highes o a ion deg ee o be ole a ed
is 1
:
39

.
Recognizing Typese Documen s using Walsh T ans o ma ion 105
4. Cha ac e Recogni ion
Acco ding o he a e age size o he s o ed
bina y images in he chained lis , we can de-
cide whe he an elemen s o es ex in o ma ion
(
cha ac e
)
o some hing else, a g aphic o noise
co up ion, o example.
4.1. The Walsh T ans o ma ion
We use he Walsh ans o ma ion in ou cha ac-
e ecogni ion p ocess. Walsh ans o ma ion
was applied in se e al cases o se e al pu -
poses, bu ne e o cha ac e ecogni ion. We
ound ha his ans o ma ion gi es a e bose
desc ip ion o he image, like symme ical e-
la ions, placemen o he o eg ound and back-
g ound pixels, and so on. Tha is why we ied o
apply i o cha ac e ecogni ion, and inally ac-
complished good esul s o simple documen s.
The Walsh ans o ma ion W
(
u

)
is a sepa able
and symme ic ans o ma ion wi h he ollow-
ing o m in 2D:
W
(
u

)=
N
;
1
X
x
=
0
N
;
1
X
y
=
0
(
x

y
)
g
(
x

y

u

)

(
4.1
)
whe e
(
x

y
)
is in ensi y o he pixel wi h he
coo dina es
(
x

y
)
in he o iginal bina y im-
age. The size o he image is N

N

and
u

=
0
:::
N
;
1, hus we compu e N2
Walsh ans o ms al oge he , which can be o -
ganized in o an N2dimensional ea u e ec o :
(
W
(
0

0
)

W
(
0

1
)

W
(
0

2
)
:::
W
(
0

N
;
1
)

W
(
1

0
)

W
(
1

1
)
:::
W
(
N
;
1

N
;
1
))
:
Func ion gis he ke nel unc ion o he ans-
o ma ion and has he ollowing o m:
g
(
x

y

u

)=
=
1
N
n
;
1
Y
i
=
0
(
;
1
)
bi
(
x
)
bn
;
i
;
1
(
u
)+
bi
(
y
)
bn
;
i
;
1
(
)

(
4.2
)
whe e bi
(
x
)
is he i h bi in he bina y expansion
o x
(
so i is equal ei he 0 o 1
)
, and N
=
2n.
The Walsh ans o m is unique in he sense ha
i we conside wo di e en bina y images, he
co esponding ea u e ec o s a e also di e en .
I we compose a ea u e ec o which does no
con ain all he Walsh ans o m alues, hen his
ec o can be he same o wo di e en o igi-
nal bina y images, see Sec ion 4.2. The Walsh
ans o ma ion is sepa able, as i s ke nel unc-
ion can be sepa a ed:
g
(
x

y

u

)=
g1
(
x

u
)
g2
(
y

)
:
(
4.3
)
Mo eo e , he equali y
g
(
x

y

u

)=
g1
(
x

u
)
g1
(
y

)

(
4.4
)
also holds
(
he ac o s a e unc ionally equi -
alen
)
, hus he Walsh ans o ma ion is sym-
me ic as well. Wi h hese wo p ope ies he
compu a ion o he 2D ans o ms can be made
conside ably as e , since i can be simpli ied o
he compu a ion o wo 1D Walsh ans o ma-
ions, and he symme y makes he compu a ion
e en as e . All hese p ope ies o he Walsh
ans o ma ion a e well-known om li e a u e,
see R.C. GONZALEZ
(
1992
)
. Ou pu pose
was o collec hose ea u es, which ha e an im-
po an ole in ou algo i hm.
4.2. Applica ion o he Walsh T ans o ma-
ion
To pe o m he Walsh ans o ma ion, i s we
ha e o magni y he o iginal image o he size
o 2n

2n o some n. This does no mean
a conside able modi ica ion, since he Walsh
ans o ma ion is in a ian unde magni ica ion.
The image size was ixed a 32

32 and we used
linea ans o ma ion o magni y he segmen s.
Howe e , we compu ed only he ollowing 64
Walsh ans o ms ins ead o he 32

32
=
1024
ones:
(
W
(
0

0
)

W
(
0

1
)

W
(
0

2
)
:::
W
(
0

7
)

W
(
1

0
)

W
(
1

1
)
:::
W
(
7

7
))
:
The e a e h ee easons o educing he numbe
o he Walsh ans o ms:

We can sa e compu a ion ime;

These 64 alues desc ibe global ea u es
and symme ic ela ions o he bina y image
well;

We can il e ou some noise co up ion om
he image, since he compu a ion o less
Walsh ans o ms esul s in a blu ing e -
ec . Fo a de ailed desc ip ion o he noise
sensi i i y o he algo i hm, see Sec ion 6,
which summa izes ou expe imen al esul s.

106 Recognizing Typese Documen s using Walsh T ans o ma ion
Fig. 4. Di e en images wi h he same ea u e ec o .
An example o he la e p ope y can be seen in
Figu e 4, whe e he Walsh ans o ms W
(
0

0
)
,
W
(
0

1
)
,W
(
0

2
)
,W
(
0

3
)
,W
(
1

0
)
,W
(
1

1
)
,
:::
,
W
(
3

3
)
a e equal o he wo o iginal 8

8 bi-
na y images.
The di e ence
(
dis ance
)
o he 64D ea u e
ec o s o di e en cha ac e s is signi ican , so
he ecogni ion o a gi en cha ac e is qui e eli-
able. To p o e his s a emen check he ollow-
ing able, which illus a es Ca esian dis ance
alues be ween he ea u e ec o s o p o o ype
digi s. The alues show signi ican di e ences,
which suppo s ou concep ion o calcula e only
a 64 dimensional ea u e ec o o each cha -
ac e .
Magni ying he segmen s o he same size
(
32

32
)
can cause a p oblem in cha ac e ecogni-
ion. Though he lowe and uppe cases o he
cha ac e s usually look di e en , some cha ac-
e s ha e simila lowe and uppe cases
(
e.g.
“w” and “W”
)
, which become iden ical du ing
magni ica ion. We can a oid his p oblem by
s o ing he a io o he side leng hs o he s o ing
ec angle o e e y segmen . The p ope case
can be es o ed by compa ing he a io o he
side leng hs o he o iginal s o ing ec angle.
In he p e ious sec ion we desc ibed how he 2D
Walsh ans o ma ion can be pe o med as wo
1D ans o ma ions. In ou algo i hm we used
a as e me hod and compu ed he ans o ms
di ec ly om he ables. The alue
Ng
(
x

y

u

)=
n
;
1
Y
i
=
0
(
;
1
)
bi
(
x
)
bn
;
i
;
1
(
u
)+
bi
(
y
)
bn
;
i
;
1
(
)
(
4.5
)
in he ke nel unc ion can be

1. Fo example,
le us conside he case n
=
1, N
=
21
=
2. The
co esponding able adi ionally has he o m
(
0,0
) (
0,1
) (
1,0
) (
1,1
)
(
0

0
)++++
(
0

1
) +
;
+
;
(
1

0
)++
; ;
(
1

1
) +
; ;
+
Table 2. The ke nel unc ion alues o he Walsh
ans o ma ion o a 2

2 image.
whe e he cells o he able con ain
+
o
;
signs
acco ding o he alue o
(
4.5
)
.
012345678
1 1221
2 1494 1607
3 1113 1532 1727
4 1353 1338 1723 1566
5 1208 1253 1466 1271 1417
6 745 1464 1661 1224 1514 1273
7 1752 1143 1722 1917 1773 1600 1961
8 1224 1361 1554 1349 1511 1072 1229 1816
9 853 1456 1367 1220 1742 1279 1012 1815 1257
Table 1. Dis ance alues be ween he ea u e ec o s o p o o ype digi s.
Recognizing Typese Documen s using Walsh T ans o ma ion 107
4.3. Compa ing Fea u e Vec o s Agains
O he Algo i hms
Ou algo i hm was compa ed by wo classic
cha ac e ecogni ion me hod: one o hem is
based on p ojec ion his og ams, he o he one
is based on zoning. The eason why we in-
ol ed hese cha ac e ecogni ion algo i hms
in o ou analysis is ha bo h o hem use ea-
u e ec o s o classi y ecognizable cha ac e s
and assign a 64D ea u e ec o o e e y e-
cognizable segmen , simila ly o ou algo i hm.
We in ol ed di e en on ypes o ou analyses
(
OCR-A, OCR-B, CMR
)
. By ixing a p o o ype
alphabe
(
le e s, digi s, punc ua ion ma ks, and
o he symbols
)
, i s we compu ed he a e age
dis ance alues o e e y symbol om he es
o he alphabe . Table 3 con ains ou esul s
acco ding o he di e en cha ac e ecogni ion
algo i hms. Only he i s 10 lowe case le e s
o he alphabe a e p esen ed he e.
The en ies indica e mo e signi ican di e ence
alues in he case o Walsh ans o ma ion,
which esul s in be e ecogni ion pe o mance.
A de ailed desc ip ion and esul s o he es s we
pe o med o check he ecogni ion accu acy o
ou me hod a e p esen ed in Sec ion 6.
4.4. Cha ac e Recogni ion — Fea u e and
P o o ype Vec o s
As desc ibed in he p e ious sec ion, we ob ain
a 64 dimensional ea u e ec o by compu ing
some o he Walsh ans o ms o an elemen o
he chained lis . This ea u e ec o is compa ed
wi h p o o ype ec o s con aining he same 64
Walsh ans o ms o p o o ype cha ac e s. Fo
a gi en ea u e ec o we ind he closes p o o-
ype ec o by using a sui able dis ance unc ion
(
o example he Ca esian one
)
. I we assume
ha he size o he cha ac e segmen s lie in an
in e al, we can exclude he segmen s o oo
small
(
noise
)
o oo la ge size
(
g aphic pa s
)
om he ecogni ion p ocess be o e he deci-
sion s ep. Recogni ion is based on he dis ance
be ween he ea u e ec o o he analysed cha -
ac e and he p o o ype ec o .
5. Decision and T aining
As we men ioned be o e, he documen we a e
abou o p ocess should con ain only he ex
and some special symbols. Fo his kind o
documen s he algo i hm wo ks in a ai ly eli-
able way. To make he algo i hm mo e lexible,
we inse ed a decision s ep in o he ecogni ion
p ocess o handle un ecognizable segmen s. We
ha e he ollowing wo possibili ies o make a
decision abou he ecognizabili y o a segmen .
2-le el decision:
Wi h his s ep, he gi en seg-
men is always ecognized, which means ha
he algo i hm inds he p o o ype cha ac e
whose ea u e ec o has he minimal dis ance
om he ea u e ec o o he gi en segmen .
3-le el decision:
Wi h his s ep we classi y
he segmen s as ecognizable o unce ain ones.
In unce ain cases he algo i hm has “doub s”
abou he ecognizabili y o he gi en segmen s.
Walsh P ojec ion Zoning
Le e CMR OCR CMR OCR CMR OCR
a 2375 2795 478 615 316 406
b 2011 2323 335 432 238 310
c 2281 2613 356 470 280 373
d 1974 2396 333 439 244 316
e 2288 2742 390 642 294 417
1983 2478 334 477 236 321
g 1930 2377 330 416 233 306
h 1965 2326 338 462 241 314
i 1628 2272 344 487 205 311
j 1655 2328 338 508 194 314
Table 3. A e age dis ance alues o he i s 10 le e s om he es o he p o o ype alphabe .
108 Recognizing Typese Documen s using Walsh T ans o ma ion
This happens when he minimal dis ance is
la ge han he h eshold alue.
Du ing cha ac e ecogni ion we c ea e a 64D
ea u e ec o o e e y segmen , hen calcula e
he minimal dis ance be ween his ec o and
he p o o ype ec o s. The decision s eps abo e
a e based on his dis ance alue. In he 3-le el
decision s ep we use one c i ical alue. The de-
cision can be made acco ding o he ela ion o
he minimal dis ance alue agains he c i ical
alue. In he 3-le el case, i he minimal dis-
ance alue is la ge han he c i ical alue, he
segmen is conside ed un ecognizable.
C i ical alues can be gi en in di e en ways.
Fo example, in ou expe imen s we used 1
3

he
minimal dis ance be ween any wo o he p o o-
ype ec o s
as he c i ical alue o he 3-le el
decision. Ano he possibili y is o gi e he c i -
ical alue o each p o o ype ec o sepa a ely.
The e is a aining pa inse ed in o he algo-
i hm, which is independen o he ecogni ion
s ep. Adap i e ecogni ion would be ques ion-
able, since alse ecogni ion o a gi en cha ac e
would uin he co esponding p o o ype ec o .
I we wish o apply he algo i hm o a documen
using an unknown on ype, i s we ha e o
ain ou p ocess o ecognize he new symbols.
To do his, we ha e wo possibili ies. I we
ha e he on in elec onic o m, we can eas-
ily compose an a i icial documen con aining
he whole alphabe wi hou any noise. Scan-
ning h ough his documen we can ain he
algo i hm o e e y symbol o he alphabe . I
we canno compose such an a i icial documen
(
e.g. we do no ha e he on ype in elec onic
o m
)
, hen he algo i hm mus be ained by
using 3 o 10 samples o e e y symbol om
he scanned ma e ial.
6. Expe imen al Resul s
We calcula ed a e age compu a ion imes he
algo i hm ook o p ocess one page o p in ed
ex , which con ained 27 ows. I ook 4.9 sec-
onds o segmen he documen and addi ional 5
seconds o pe o m he ecogni ion s ep. The
es was execu ed on a Pe sonal Compu e a a
mode a e pe o mance le el
(
Pen ium 233 p o-
cesso
)
. The segmen a ion s ep o he algo i hm
akes app oxima ely he same ime o inish as
he ac ual ecogni ion s ep. Pe o mance o he
algo i hm can be imp o ed by making he p o-
cedu e pa allel. As we in es iga ed o he ea-
u es, we did no implemen pa allel segmen-
a ion and cha ac e ecogni ion, which would
d as ically educe he compu a ion ime. In he
case o pa allel p ocessing, segmen a ion o he
whole documen and he segmen a ion o one
cha ac e would ake app oxima ely he same
ime, and he same holds o cha ac e ecogni-
ion, oo. I means ha he compu a ion ime he
whole p ocess akes, would educe o 0.1 om
9.5 seconds.
We expe imen ally es ed he eliabili y o ou
cha ac e ecogni ion algo i hm. To pe o m
a compa a i e analysis, we did he same es
o ou ecogni ion algo i hm, and he me h-
ods based on p ojec ion his og ams, and zoning.
Syn he ic images we e gene a ed wi h he cha -
ac e se s CMR, OCR-A, OCR-B, which con-
ained he mos egula elemen s o hese se s
– app oxima ely 85 di e en symbols. These
p o o ype documen s we e used o ain he al-
go i hms, so he p o o ype ea u e ec o s we e
calcula ed. In he case o he CMR cha ac e
se we also in ol ed liga u es in o ou analysis.
We composed some
(
4
)
one page es docu-
men s con aining egula ex and calcula ed an
a e age accu acy alue o measu e he ecogni-
ion e iciency o he algo i hms. Using hese
samples, we made an analysis acco ding o he
ecogni ion accu acy o ou me hod o each
symbol o he alphabe . The esul o his es
can be ound in Appendix A.
We inse ed a noise gene a o s ep in o he cha -
ac e ecogni ion p ocess a e he segmen a-
ion. This way we co up ed he image wi h
di e en noise ypes
(
global, con ou
)
a di e -
en le els be o e execu ing he ecogni ion s ep.
We applied uni o mly dis ibu ed addi i e noise
co up ion and he le el o he co up ion was
de ined as he pe cen age o he pixels a ec ed
by he noise co up ion. Global noise co up-
ion means ha all he poin s o he bina y image
a e in ol ed in he noise co up ion, while in he
case o con ou noise co up ion only he con-
ou poin s a e a ec ed. Fo example, i we
apply con ou noise co up ion a he le el o
50%, hen a mos hal o he backg ound poin s
adjacen o he con ou poin s become objec
poin s. In ou expe imen s we applied global
and con ou noise co up ions bo h sepa a ely
and oge he . Mo eo e , es s we e pe o med
Recognizing Typese Documen s using Walsh T ans o ma ion 109
Global noise Con ou noise
Failu e 20% 25% 30% 35% 30% 40% 50% 60%
i
!
I 1% 5% 28% 37% 2% 16%
l
!
1 2% 3% 5% 5% 2% 2% 13% 4%
l
!
I 6% 17% 23% 18% 47% 82%
1
!
l 2% 6% 8% 1%
1
!
I 2% 4% 2% 4% 28% 38%
6
!
0 3% 6% 2%
!
l 1% 8% 1% 1%
Table 4. Recogni ion ailu es acco ding o di e en ypes o noise co up ion.
on ac ually scanned p in ed ma e ial, which is
equi alen o a small
(
1%
)
global and a mode -
a e
(
20%
)
con ou noise co up ion. Fo e e y
inpu documen we gene a ed 100 noisy images
wi h each o he noise ypes speci ied in he a-
ble. Appendix B summa izes he ypes o noise
co up ion we applied, and he ecogni ion ac-
cu acy o he in es iga ed algo i hms. The –
signs in he able indica es hose cases, when
he ecogni ion accu acy ell d as ically.
Fo e e y image we calcula ed i s ea u e ec o
in he way explained in Sec ion 4. Ou analysis
indica ed s ong co ela ion among he le els o
he noise co up ion, he ea u e ec o o he
image, and i s dis ance om he co esponding
p o o ype ec o . The co ela ion coe icien
=
0
:
7875 a he signi icance le el 0
:
001.
The ollowing able summa izes he ype and he
equency o some ypical ecogni ion ailu es
ha occu ed acco ding o he di e en ypes o
noise co up ion. We applied a 2-le el decision
du ing he ecogni ion.
I he ecogni ion is es ic ed only o digi s,
hen he dimension o he ea u e space can be
educed. Acco ding o a ac o analysis he di-
mension o he ea u e space can be educed
om 64 o 48 wi hou uining he accu acy o
he ecogni ion. We can ha e a mode a e ecog-
ni ion accu acy
(
a he le el o 90%
)
i we use
only a 16-dimensional ea u e space.
7. Conclusion — Applica ion in P ac ice
Ou cha ac e ecogni ion algo i hm should be
applied o ypese ex documen s which con-
ain cha ac e s om a cha ac e se wi h a small
numbe o symbols. The cha ac e s can be
magni ied as he algo i hm is in a ian unde
magni ica ion. Fo documen s o his ype, ou
algo i hm p oduces a eliable esul in an e -
ec i e and as way. Expe imen al analysis in-
dica ed ha he algo i hm ole a es noise co -
up ion qui e well. The noise sensi i i y o he
me hod can be educed u he by a lexical ana-
lysis. The ecogni ion speed can be imp o ed by
educing he applied cha ac e se . In ha case,
when he cha ac e se con ains a la ge numbe
o symbols, he algo i hm should be used o
classi ica ion ins ead o ecogni ion.
As a p ac ical applica ion we buil in ou cha -
ac e ecogni ion me hod in o an in o ma ion
loss comp essi e algo i hm. Du ing he com-
p ession ou main pu pose is o p ese e he
isual in o ma ion abou he documen , which
is mos impo an o a human e iewe , see A.
FAZEKAS e al
(
1999
)
.
This comp essi e algo i hm can be used suc-
cess ully in p ac ice, when he main goal is
o ansmi he comp essed documen h ough
some elecommunica ion channel. The o iginal
digi al images a e basically supposed o con ain
ex in o ma ion, which is eco ded in a ypo-
g aphically ixed o m wi hou using sophis i-
ca ed s uc u es. Fo example, ax documen s
usually ha e hese p ope ies. The algo i hm
was es ed in se e al cases and p o ed i sel o
be p e y e icien and eliable o simple docu-
men s.