ѧ
JOURNAL OF SOFTWARE
1999ꡡ1011ڡVol.10No.111999



һ³ԵĽṹδ֪
ԭ
ժҪģδ֪ķǱʶı׶εһҪҾսԵ.Ŀǰһ㷽̱ߵ΢С.һֻڳȡߵķṹδ֪Ĳ.óȡıߵ֪ʶ;ֲԼѡһЩЧ.ɨˮƽʹֱʱ,Ʊ߶Ч,һο,ԸõȫϢʹȡԼϵ.־οĳȡ̱ߴĶ߻򲻺ʵķָ,ԴǶοĸӽṹ.ο鱻ȡ,ͨʣĲȡ.ʵ֤,÷ڱܲʱԿԺܺõع.
ؼʡͼ,ı,ͼָ,,ȡ,ݹ㷨.
ͼšTP391
A Robust Method for Unknown Structure Form Analysis
LI Xing-yuan1 GAO Wen1,2
1 (Department of Computer Science and Engineering Harbin Institute of Technology Harbin 150001)
2(Institute of Computing Technology The Chinese Academy of Sciences Beijing 100080)
Abstract The analysis of unknown forms is a challenging and important problem in document processing. Current methods can only tolerate small breaks in form lines. In this paper, a strategy is proposed for analyzing unknown structure and filled forms based on extracted lines. Individual edges are validated using knowledge of features of the extracted lines and their local proximity. In a process of scanning the horizontal and vertical lines, candidate edges are validated and rectangles are generated if their surrounding edges and their combination are all valid. To preserve the constraints and make full use of global information, the process is recursively applied. The rectangle extraction can tolerate large breaks in form lines, ignore irrelevant segments and deal with complex configurations such as embedded rectangles. After rectangle extraction, other form components are extracted by searching the remaining segments. Experiments on a collection of forms with handwritten fields and documents with tables show that the proposed approach works well even on poor quality images.
Key wordsImage analysis, document analysis, image segmentation, form analysis, rectangle extraction, recursive algorithm.
񱻹㷺ڸֳ.ԱԶĶԼǽϢķ,Ҫʵüֵ.оֽͨű1ݺIBM˾2.
Ըһͼ,ǹ֪ʶԽ,Խ.ܶϵͳñģʾһĽṹ,߱ȷ.ģ͵ĽֹġԶĺȫԶ.ֹģͷǳ.ʱһģͿֱܱҪʱ.,ֹģͶڱ´ӡʱڲλõ޷Ӧ,ʹխ.,ԶԶģͽĽṹģδ֪ı͸սԺҪ.
ͬһıһ,ĿǰͼٵҪųĸ.ȡıȫ,ûжߺͶ,ڽɱ߹ɵͼиڲľξͿԵõȫľο.,ʵܻȡһЩַͼļٱ߶,ͬʱ,ʵҲԤ.
ڴ֮ǰоѾ˺ܶδ֪ķ.ٵ˲ûͶӰķλ,ȻӦλѰҽǵİ취ȡο3.Fan˲ϸȡķ4,ϸ,ûк÷ַкͱϵֿ.WangSrihariӿȥһЩַ,Ȼͼ(line adjacent graph)߶,ٴͼؼ,ɹؼԪ5.GarrisrunķԪĹؼ6.BelaidHough任ȡ߶,Ȼһͼ,ͼϽ7.YuJainÿͼȡܵǵԪ8.WangSrihariķԴַͱճ,,4ַûпǱ߶ߵ.FujisawaNakanoȶˮƽʹֱrun˲,ȻñǿСĶ,ȡοڻ1,9.̺СĶߵַճ򽻲.HoriDoermann˴ԭͼСͼ10.һЩԭͼиٲľοڻСͼ,ַСĶЧϺ,ǵַ߳оһַһʱ,ӶߵСַַ߱,ӶСͼжʧο.ף10иĽ֤ʵ,ַԿ˷0.32mmĶ.ںܶǲ.Shinjo˸һӱ߽Ŀ˷ߵķ11,Ҫȥʵϵ߶ζʵϵ߶,Ǻ.
ڿĻ㲻ͬ,ģͶıûгȫϢ.:(1) ߳ȡûаѱΪһԴ;(2) ɾֲȡο鵥Ԫ,ֶߺͼٱ߶ʱ,ԭͼϾֲͺҵȷĽ.ĿǰΪֹ,ûһֿԴı߶γȡԪ㷨.ף10,12Ϊڱߵķʹڴߵı.
ף13һȫϢı߳ȡ.ڴ˻һṹδ֪ķ,οȡԪȡ.οȡԳȡıΪ,οԭͼϢ.ΪȫϢ,ȷο֮һЩԼ,Ȼһȡ㷨ĵȡο.
1 Լϵ
οȡΪһˮƽ߼ϡһֱ߼Ϻͱԭͼ,Ϊһο鼯.һοʾΪ(PTopLeft,PTopRight,PBottomLeft,PBottomRight,LLeft,LRight,LTop,LBottom),PTopLeft,PTopRight,PBottomLeft,PBottomRightֱǾοϡϡº½λ,(x,y)ʾ,οľλ.LLeft,LRight,LTop,LBottomǰΧþοҡϡ±ߵ,ολ.
ڳȡı߿ж,Ҳж߻߶,,ο鲢ȫرˮƽ߼Ϻʹֱ߼.һ,ο֮䲻໥,֮źǿϵ,Ҳ˵,ȡļοܻһοǷӦñȡ.,ͼ1(b),ȡ˾ο1,3,45,ο2ҲӦñȡ.ΪȻο1,3,45Ч,Щοı߾ͶЧ,ο2ıҲЧ.óȡ㷨õ˾ο1,3,45,ûгȡο2,һĽ.

ͼ1οǵı֮Լ
ھο֮ĻԼ,ܽ3Լϵ.
Լ1. һοȫڲο,Ч.ͼ1(a)еľο1.
Լ2. һοһȫЧľο,ñЧ.ͼ1(b),ADЧ,ΪЧ1,2,3(Ӧ߶AB,BCCD).
Լ3. һοһֵ߲رЧο,δǵһ㹻,ñЧ.ͼ1(c),ADЧ,Ϊο1(Ӧ߶AB);ο2(Ӧ߶BC)Ч,CD㹻.
2 οȡĻ㷨
2.1 㷨ĸ
PˮƽQֱ.ܹԲοѡ.ЩѡֻһСЧ.ԭ˵,ͨУЩѡȷı鼯.Ȼ,ںѡĿO(P2Q2),ҪѡϱȽϷʱ.ÿһѡοÿοĹϵ,ôУ̵ĸӶȾͱΪO(P4Q4).,ʵһڵɾοĿԶԶСھοѡĿ.PˮƽߺQֱ߶㹻,ǿ԰ͼָΪ(P-1)(Q-1),ÿοҪռһ,ֻ(P-1)(Q-1)ο.,ӦÿҵһO(PQ)㷨.
2.2 㷨
οȡ㷨ĹҪһϵ¶ˮƽߵɨʹҶԴֱߵɨ.1ˮƽߺ1ֱ߿γ1.ÿ㴦,Ǽ㲢Ϊο鶥ߺߵı.ͬʱ,ǰѾһߺһ,ж϶ӦĵױߺұǷ㹻.4߾Ч,Ͳһο.ʱ临ӶO(PQ).пԿ,Լϵ1.
㷨ˮƽ(ֱ)߼,ˮƽ(ֱ)ߴ()(),ʼŴڵ0.i,jֱɨеĵǰˮƽߺʹֱ.һTopEdgeQٿһοˮƽ.Ҳ˵,TopEdgejһˮƽߵ:ڵǰˮƽi֮ڴֱjj+1֮㹻ĳ(Ч).ı߿ж,ֻ¼ǰˮƽiһ.TopEdgej(0jQ)ʼΪ-1,ʾʼʱĶ߲.ͼ2гڶһɨ,ڵǰˮƽi=3͵ǰֱj=0ʱTopEdgeۣ.i=1,j=0ʱ,TopEdge0-2=-1,TopEdge3-7=0.

ͼ2һṹڵǰˮƽi=3͵ǰֱj=0ʱTopEdge[]
㷨һvlĿΪοߵĴֱ.ÿˮƽ߶дֱһɨ,һԶһһ.vlڿʼÿˮƽɨʱʼΪ-1.ͼ2еı,ǰˮƽi=1ʱ,vl=-1,j=0,1,2,3;vl=3,j=4(ɶԴֱ3ɨ֮);vl=4,j=5;vl=5,j=6;vl=6,j=7;vl=7,j=8.
,Ǹ㷨RectangleExtract.HEdgeValid(i,j1,j2)Ƿˮƽiڴֱj1j2֮Ч,˵,Ƿˮƽi봹ֱj1j2һˮƽ߹һο.Ƶ,VEdgeValid(j,i1,i2)Ƿֱjˮƽi1i2֮Ч.
Procedure RectangleExtract
1. ʼ TopEdgek=-1(k=0,1,...,Q).
2. For ÿˮƽi(i=0,1,...,P,ϵ) {
3. vl=-1;
4. For ÿֱj(j=0,1,...,Q,) {
5. If j!=0 and HEdgeValid(i,j-1,j),TopEdgej-1=i.
6. If vl!=-1 and TopEdgej-1 !=-1 and VEdgeValid(j,TopEdgej-1,i) and HEdgeValid(i,vl,j)/*Уұߺ͵ױ*/{
7. If vlkjTopEdgek,
һˮƽTopEdgevlݺi,ֱvljΧľο;
else{
8. HminHmaxֱΪTopEdgekvlkjСֵ.
9. For h1HminHmax-1,
if HEdgeValid(h1,vl,j) and VEdgeValid(vl,h,i)/*У鶥ߺ*/{
10. һˮƽh1i,ֱvljΧľο;break.
}
}
11. If Step7Step10вһο
For (k=vl;kj;k++)
TopEdgek=i;
/*øþοĵױߵΪЧ*/
}
12. If TopEdgej!=-1 and VEdgeValid(j,TopEdgej,i)==TRUE,
vl=j;/*У*/
}
}
Step7,ǼǷʱTopEdgekݶ.,ˮƽTopEdgekдvlvl+1,...,kk+1,...,j-1jС䶼Ч.ԼЧж:һһÿС䶼Ч,ñڸЧ.ʵ,ԼȫʵҪ.,TopEdgekڴvljЧ.ΪvlڴTopEdgevlݵiЧ,Step6ѾУұߺ͵ױ,vl,j,TopEdgevlݺiΧľοЧ.ǶvlkjTopEdgekݶ(ͼ3οʾ),ҪУvl.ΪvlڴTopEdgevlݵiЧ,TopEdgevlݿܲǾοĶ.Ƶ,ҪУ鶥.

ͼ3vlkj,TopEdge[k]ȵ
2.3 ߵУ
жһοǷЧ,ҪжǷЧ,Ҳμοȡ㷨еHEdgeValid(i,j1,j2)VEdgeValid(j,i1,i2).ֻVEdgeValid(j,i1,i2),ˮƽߵУ.
ǲһֻڹķ,ȴڵı߶κڼ丽ԭʼͼгȡһЩ,ȻһЩжϸǷЧ.
ȡ߸ȫ,ȻЧ.,ʵʵıлܶิӵ.ͼ4ʵʱеһЩο.ͼ4(a)(c),ַгȡٵĴֱ߶.ͼ4(d)(f),ÿο鶼бȽ϶̵ı.һЩ,ַļٱ߶ռıߵı߶ռıҪС.Щ,ƾ䱻ǵĳЧԾͲ.
     
(a) (b) (c) (d) (e) (f)
ͼ4 ӱռľο
жһЧ:(1) ĳlen;(2) 䱻ȡı߶ǵĳllen;(3) ԭͼհ(0)zlen;(4) ԭͼֱͶӰķֵpeak;(5) Ƿڱʻĺ;(6) ֱߵǷЧ,ulvalid.
ͨ,һֱ߶β඼бʻ֮,ַļٱ߶򳣳һбʻ.ǰΪ3.1:ޱʻ;2:һбʻ;3:бʻ.Բͬ,òͬı׼.Ҳ˵,Ե1,3.ѡЧΪһ˸ʽѧ./Ч,ҿ,ڰѸ俴Ч.,,ǲýɵҪ.
Ϊ˼zlen,peakȷǷбʻ,估ΧԭͼˮƽʹֱͶӰ.zlenYͶӰհ׳,peakXͶӰķֵ.XϵͶӰ,(Ҳ)нΪ0ͶӰ,˵(Ҳ)ûбʻ,,˵(Ҳ)бʻ.
ϵ,ǲһЩжЧ.
3 㷨չ
3.1 4ȷοЧ
ĿǰΪֹ,ǶʹÿߵЧο,ʱܻ.,ͼ5(a),ճ,ֱ1ˮƽ13֮䱻ȷΪЧ.ͬ,ֱ3ˮƽ13֮ҲȷΪЧ.,ˮƽ13ֱ13Χľο(ͼ5(a)Ӱʾ)ͱȷΪЧ.

ͼ5䰴ճȱȷΪЧ"ϸ"(EWS)
ΪĴ,ÿЧı,Ǽġϸ䡱(exact white interval,EWS)Ŀ.νϸָ,(Դֱ)(ˮƽ)߽,ڲû,Ҳ˵,ø˵ڲ.ֱ(ˮƽ)EWSͨˮƽ(ֱ)ͶӰõ.ͼ5(a),ֱ13һˮƽ1ˮƽ2EWS.ͼ5(b),ֱ33EWS.ˮƽ01,23,45.Ȼȥ4ߵEWS֮ʹڵ2ľο.,ͼ5(a)(b)ӰʾľοͲ,ΪǷֱ23EWS.
3.2 ο鱻ڲο鲿ָǵ
һο鱻ڲο鲿ָ,ڲľοָΪһκڲα.ڰεıʾȽϸ,ڲκСⲿʾ.
ֻҪڲοⲿο鲻ױ(ͼ6(a),(b)ʾ),ǰĻ㷨ͿԳȡⲿڲο.Ϊ㷨Եõȷұ.,û㷨ͳȡⲿο,Ϊڳȡھοʱʧ˶οȷvl.

ͼ6һο鱻ڲο鲿ָ
Ϊҵⲿľο,ڻοȡ㷨֮󸽼һ.Ѱҿܵڲο.һοڲο,ֻеڵ(ͼ6(b),(c)ʾ)ߵһ(ͼ6(d))ο.ȻԿܵڲο,ΧСο,ֱҵһοı߽Ϊֹ,ͼ6(c)ͼ6(d)ͷʾ.
4 㷨
ڱο֮ǿϵ,ͨһɨͰȫο鶼ȡ.һ㷨,ǰ㷨ĻϽе,ԱЧþο֮Ĺϵ.
ԴֱУʱ,ʹЧurValidΪһ.ڻ㷨һµɨ,УһֱʱѾõЧ.ЧԵļЧԼĽΪǰ.Ϊ˼ȫοЧ,ǵл㷨.ڵ1,ٶÿֱÿˮƽЧ,õο.ȻӳȡľοеˮƽʹֱÿСЧ.һεʱ,У鴹ֱ(ˮƽ)ʱ,ʹøյ()Ч.
һH=hijP(Q-1)¼ˮƽߵСЧ.

ͬ,þV=vijQ(P-1)¼ֱߵСЧ.vjiĶ.
Գȡÿο,i=LTop,LBottomjʣLLeft,LRight)hij=1,j=LLeft,LRightiʣLTop,LBottom)vji=1,͵õСЧ.
,hij(0iP,0jQ-1)vij(0iQ,0jP-1)ʼʱΪ0,ԺĵĳЩhijĳЩvijΪ1.еֱȡľο鼯ϴͬ.
̵һҪǿʹ㷨ֵ1Լ.
ΪԼ2,VEdgeValid(j,i1,i2).
Rule 0. i1ii2,vij=1,ϴγȡĽдֱji1i2֮Ч,VEdgeValid(j,i1,i2)=1.
ΪԼ3,VEdgeValid(j,i1,i2).
Rule 1. һ䲻,Ǫiʣi1,i2)ʹvij=1,Ѹvij=1Сȥ,ȻڵСϲ,õһ伯.ЩȫЧ,Ч.
,ͼ7(a),ٶһгȡ˾ο12.AFõ{AB,DF}.ABDFЧ,AFЧ.
ÿȡһο֮󶼸vij,УʱӦRule 0Rule 1,õҲʹںܶԼ.,ȻǱزٵ.ͼ7(b),ٶDAΪЧο4Ч,Ǿο1,2,3Ч(DA඼бʻ,DC,CB,BAû,ǿܵ),Ҫ2Rule 0ȷDAЧ.

ͼ7õʹ㷨Լ
̵һǿԴһЩڱṹ.ڹڱṹ֪ʶͨĳЩıʾ,ӦЩ֪ʶǰȷЩı.Խ.ڲӦñṹ֪ʶ³ȡο鼯,ȻȷЩı,ԺľοȡӦЩ֪ʶ.
5 ʵ
ĿǰΪֹ,ûпԱЧԵ㹻ͱͼݿ.ұ׼뼼оԺ(NIST)Special Database 6(structured forms database 2)5 595ҳͼ,ֻ20ֱṹ(12ֱ,8ҳ).
κľĿǰûһͳһĶ׼.Ķּ㾫ȵı׼:Ԫȷʺͱȷ.ڵԪȷ,κڳȡбѡϲ߽߰һԪһ.ڱȷ,κڵԪȡбӻ©һ߶һ.ԪȷʷӳȡĵԪĿó̶,ȷӳ˹ȡĴҪŬ.
Ѿһıͼ϶Աķ˲.Լ120260ͼ.󲿷ֱǴʵӦռ,ܶͼϲ.һЩǰһӡˢı,ɼڹڡʵıֽ־,аڼѧͼIEEE Transactions on PAMIϵдҳ.Щ־ûб,ȸӡɨ.ܶӡˢıǶ,һЩ˫.ֻܱռЩӡˢıһ,ڷǰû˹򶨱.ѡЩӡˢо󲿷ӡˢOCRϵͳԴӶıзָѣ14ݡ.֮,ҲԼһЩ,㷨ڸֽṹ͸̶ֶ߳ȵӦ,һЩ(ó).260ŲԱ120Ŵдַ.ʵʱģݵ,ûждκ.ͼɨ6ֲͬɨ,ɨֱʴ200dpi600dpi.
260ŲԱ,ڲṩκιڱ͵֪ʶ(ָʾǷñǡ)Ͳıϵͳκβ,Ԫȡȷ98.1%,߳ȡȷ98.5%.һ20003000Сͼ,һ̨Pentium200M HZ PC,ӱ߳ȡԪʱԼΪ2s.ٶȱҪ,ǿף6,9ݵĽȵ.
6  
һµģͶıԪ.һ־οȡ㷨.ԳȡıΪ,ͨɨˮƽߺʹֱߵĹУοı߳ȡο.ο֮Լϵ֮,ʹȡЩԼϵ.һһЩ֪ʶ.Уʱ˱ϢԭͼϢ.ͨһЩ,ϵͳԴܶิӵ.ʵ֤ǵķЧԺͶĸ̶.
ĿоõȻѧ𡢹863߿ƼĿ𡢹ҽ˲ŻйѧԺ˼ƻ.
߼飺ԭ,1964,ʿ,,ҪоΪıʶ,ѧϰ,.
,1956,ʿ,ڣʿʦ,ҪоΪܼӿ,ý弼.
ߵλԭҵѧѧ빤ϵ  1500
ԭġйѧԺ㼼о  100080
ͨѶϵ:ģ 100080,йѧԺ㼼о
ο
1 Nakano Y, Fujisawa H, Okada K et al. A document understanding system incorporating with character recognition. In: Proceedings of the 8th International Conference on Pattern Recognition. Washington D.C.: IEEE Computer Press, 1986. 801803
2 Casey R G, Ferguson D R. Intelligent forms processing. IBM Systems Journal, 1990,29(3):435450
3 Liu J, Ding X, Wu Y. Description and recognition of form and automated form data entry. In: Proceedings of the 3rd International Conference on Document Analysis and Recognition. Washington D.C.: IEEE Computer Press, 1995. 579582
4 Fan K C, Lu J M, Wang J Y. A feature point approach to the segmentation of form documents. In: Proceedings of the 3rd International Conference on Document Analysis and Recognition. Washington D.C.: IEEE Computer Press, 1995. 623626
5 Wang D, Srihari S N. Analysis of form images. In: Proceedings of the 1st International Conference on Document Analysis and Recognition. AFCET-IRISA/INRIA, Washington D.C.: IEEE Computer Press, 1991. 181191
6 Garris M D. Correlated run length algorithm (CURL) for detecting form structure within digitized documents. In: Proceedings of the 3rd Annual Symposium of Document Analysis and Information Retrieval. Washington D.C.: IEEE Computer Press, 1994. 413424
7 Belaid Y, Belaid A, Turolla E. Item searching in forms: application to french tax form. In: Proceedings of the 3rd International Conference on Document Analysis and Recognition. Washington D.C.: IEEE Computer Press, 1995. 744747
8 Yu B, Jain A K, Generic A. System for form dropout. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1996,18(11):11271134
9 Fujisawa H, Nakano Y, Kurino K. Segmentation methods for character recognition: from segmentation to document structure analysis. Proceedings of the IEEE, 1992,80(7):10791092
10 Hori O, Doermann D S. Robust table-form structure analysis based on box-driven reasoning. In: Proceedings of the 3rd International Conference on Document Analysis and Recognition. Washington D.C.: IEEE Computer Press, 1995. 218221
11 Shinjo H et al. A method for connecting disappeared junction patterns on frame lines in form documents. In: Proceedings of the 4th International Conference on Document Analysis and Recognition. Washington D.C.: IEEE Computer Press, 1997. 667670
12 Watanabe T, Luo Q, Sugie N. Layout recognition of multi-kinds of table-form documents. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1995,7(4):432445
13 ԭ.ԶĶо۲ʿѧλģ.ҵѧ,1997
(Li Xing-yuan. A study of automatic form reading Ph.D. Thesis. Harbin Institute of Technology, 1997)
14 Kanai J, Rice S V, Nartker T A et al. Automated evaluation of OCR zoning. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1995,17(1):8690
1998-05-12յԭ,1998-11-23յ޸ĸ
