Recognizing typeset documents using Walsh transformation

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.