ѧ
JOURNAL OF SOFTWARE
1999 2 No.2 1999



һֻģʽԲʶ㷨*
ΰࡡȺ
ժҪڹͼֽʶϵͳ,ԲԲʶתһδ׽.½ʶ𷽷Ҫͼݽṹ,ڴ˻Բʶ㷨.㷨ȽͼԲģʽƥ,ӶȷԲͼ;Ȼ,ͨͼʵʩ,ջԲԲͼαʾ.ʵ,,ʶ㷨Ϻõؽͼֽʶеһؼ,ӦǿЧɿص.
ؼʡʶ,ʸ,ϸ.
ͼšTP391
A Pattern Based Circular Arc Recognition Algorithm 
LI Wei-qing PENG Qun-sheng 
Abstract Circular arc recognition is a difficult problem that is not entirely solved in engineering drawing recognition and understanding research field. In this paper, some concepts of global recognition method and patch structure are introduced, and a circular arc recognition algorithm is provided. The algorithm matches several patches with two patterns to decide the seeds, and then by tracing the other patches, it converts these patches into circular arcs. Examples are given, which show that the algorithm has effectively solved a key problem of recognizing drawings are given.
Key wordsGlobal recognition, vectorization, thinning.
ڹͼֽʸתڶ,ԲʶĿǰδĹؼ֮һ.ϸ1,2ģؽƥ,ҳĹǼ,ö.÷,ͼеȱݶսӰϴ.ƥ䷽3,4ͨغƥʸ,õͼߵмǼʸ.÷ЧرȱݵĲӰ,ƥ̸,ȷԱ֤.ֱַزϲ,һϵֱ߶ȥƽԲԲ,ԻԲͼαʽ.
ʶ𷽷5ϰͼֽиͼϵ.ͼ֯ͼݽṹ,ݴȡ͵Ĳи,ȡ.÷ͼľֲϸ,,ͼеȱݶսӰС;ͼ,֮˹ϵͼݽṹеõ,ʸת,˽ṹʼյõ֤,ڶͼֽͼؽ.
ף6ݶֱ߶εʶṩ˽Ϻõ㷨,ǶԲʶȴδо.ף7ʶ𷽷ʶԲԲʱ,Ƚͼתֱ߶,ֱ߶Ŀ3ʱ,ſȷԲļβ.ʹԭеͼϢԲתûֵܳõ.÷ͼֽа뾶СԲΪ.
Բʶ㷨,ͼԲģʽƥȷͼ,ͨͼʵʩ,ӶԲԲͼαʾ.,Ƚйظͼνṹ,Ȼͼεķָ,ԲģʽͻģʽԲʶ㷨,㷨,ʵ.
1 ʶ𷽷ĸݽṹ
1.1 ɨ
ͬһɨ,ɶĺɵصļϳΪɨ.sijxij0,xij1ʾiɨϵĵjɨ.
1.2 صϵ
ɨsijsi+1k,:xij0xi+1k0xij1xi+1k0xij0xi+1k1,Ǿصϵ.sijsi+1kصϵ,sij͵i+lɨϵɨζûصϵ,ͬʱ,si+1k͵iɨϵɨҲûصϵ,ô,sijsi+1kΪһһص.
1.3 ͼ 
һһصϵɨɵļϳΪһͼ.ͼ1ʾ3ͬͼ.
 
ͼ13ͬͼ 
1.4 ӹϵ
ͼpһɨͼqĵ1ɨصϵ,ô,ͼpͼqΪӹϵ.ͼ1,ͼpͼqͼpͼrڸӹϵ.
1.5 ֵܹϵ
ͼqĵ11ɨͼrĵ11ɨδͬһɨ,Ƕͼpɸӹϵ,ô,ͼqͼrΪֵܹϵͼ1ʾ.
ɨݽṹΪ:
typedef struct {
int x_start,x_end; // ɨ˵xֵ
} SCANSEG;
ͼݽṹΪ:
typedef struct {
int y_start,y_end; // ͼе1һɨεyֵ
int top,bottom;// ͼδڸӡֵܹϵͼ
SCANSEG *seg;// ָͼɨָ
} PATCH; 
2 Բʶ㷨
2.1 ͼηָ
ͼξò,ȫȷ,ô,ͼΪͼ;ͼμȲֱ߶,ҲԲ,ô,ͼΪͼ.
Ըͼαзָ,зͼ.ͼͨ3:ֱֱӡԲԲԼֱԲ.ͶӰָ㷨5ܽϺõشֱֱӵĸͼ,˴ؽ.
״̬,ֱͼÿһ㴦ĶײΪ,Բͼεÿһ㴦Ķײ־ͬ,ɴ˿Լͼи㴦Ķײ,Զײֽۼ.ֱߵĶײۼӺͿˮƽ,ԲĶײۼӺͿбʷֱ.ͼ2ʾԲԲΡԲֱ߶ĶײۼӺ,pΪ͵ӵ.
 
ͼ2ײֺ
2.2 Բģʽ
ͼݽṹɨʽԭʼͼ,ɨsijĳxij1-xij0+1һֵ,Զ϶ɨһˮƽ.,ʸת̵Ŀʼ,ȴˮƽ,ȻתԲ.
ͼ,ڻԲԲʱ,ͨӦǵĶԳһ,Գͨһˮƽߺһֱ߹.ˮƽܱȷʶ,ɴ,ѰԲͼ.һ,뾶ϴԲĶײͼҲΪڽϳɨζʶˮƽ,ҲɳΪѰͼε.
,Բģʽ,ֱͼ34ʾ,hΪˮƽ,ӰΪͼ.Ȼ,ǶܻһЩ仯ʽ.
2.3 ͼεȷ
ģʽ1,ʼβʱ3ȡΪ:1ȡͼ11/3,2ȡˮƽh,3ȡͼ22/3,3ֱͼ3еp,qrʾ.
 
ͼ3ģʽ1
ģʽ2,ʼβʱ3ȡΪ:1ȡͼ22/3,2ȡˮƽh,3ȡͼ42/3,3ֱͼ4еp,qrʾ.

ͼ4ģʽ2
ˮƽ߳,Ѱҷģʽͼ,ѡȡ3óʼ,ӦЩͼεĺϷһ,ģʽ1еͼ12ģʽ2еͼ24,ԾǷȷʵܹԲ.ͼһϷԲͼ,ɽΪͼ.
2.4 ͼθ
һͼγ,ͼ֮໥ϵ,һĹǰ,ҳһͬһԲͼ,ͼεĸٹ.տʼʱĳʼͼαֱʶΪʼͼκֹͼ,ÿٳһͼ,µͼΪʼͼ.ÿθʱ,¼һͼλãԲҰԲٷϻ¸٣ƣ˳ʱʱ룩.
ͼεĸٷϿܻжͼ֮,ʱ,Ҫ3:
(1)ĳһͼpÿһɨΣΧڣõԲ,pҪҵͼ.ͼpɨһֵ,ô,µԲļβ.
(2)͵ͼ,ô,ҪжһµǰٵͼpǷΪԲĶײͼ,,Ӹͼγ,ıһͼλãԲΪҰԲ,֮
ȻٷϸٸΪ¸,֮Ȼ,ͬʱ,ͼpΪʼͼ.
(3)ų,ôӦǷκһֹ,ԾǷҪ: ڸٷϲͼ; ڸٷϵͼβڸԲ; ڸٷϵͼΪֹͼ.
۶,ʼͼǰ,ҵֹͼΣģʽ1,ͼ1,˳ʱ뷽,յͼ2,һԲɹȡ.,١ڶֹʱ,뻥ʼͼκֹͼ,µʼͼΣԭȵֹͼΣµͼλáٷǰ.
3 ۺʵ
ͼνṹʶ𷽷Ѿ㽭ѧCAD&CGصʵƵġͼֽɨ롢ʶϵͳʵ.ͼ5ͼ7ֱʵ,Ѿͼַķ,ͼ6ͼ8ֱΪʸ.ɽԿ,ʶ𷽷Բʶ㷨кǿʶ,ܴ󲿷ֵԲ,,ʶĽԭͼֽǺϵñȽϺ.


ͼ5ͼֽͼ ͼ6ʸת


ͼ7ͼֽͼ ͼ8ʸת 
ͼܹ,ʶһЩСԲʱԻһЩ,ԭЩԲṩЧϢ,ԽСֱ߶ֿ.
ʶ𷽷ֵƵĵط,֮ǶС͵תȷԲ,⻹дڽһо.
߽ܣΰ,1965,ʿ,ʦ,ҪоΪͼֽɨʶ,ά.
Ⱥ,1947,ʿ,ڣʿʦ,ҪоΪͼѧ,ƷϢģ,ͼɨʶ.
ͨѶϵ:Ⱥ 310027,㽭ѧCAD&CGصʵ
ߵλΰࡡȺ㽭ѧCAD&CGصʵ ݡ310027
ο
1Smith R W. Computer processing of line images: a survey. Pattern Recognition, 1987,20(1):715
2Shaoxing Z, Nishihara S. Eliminating shape distortions in thinning of engineering drawings. In: Staudhammer J, Peng Qun-sheng eds. Proceedings of CAD/Graphics'91. Hangzhou, 1991. 472477
3Yang Li-rui, Zhou Ji. Contour shape analysis-directed vectorization of engineering drawings. In: Yang S, Zhou Ji, Li C eds. Proceedings of the CAD/Graphics'95. Wuhan, 1995. 150154
4Jiang Hua et al. Knowledge based mechanical drawing interpretation. In: Yang S, Zhou Ji, Li C eds. Proceedings of the CAD/Graphics'95. Wuhan, International Academic Publishers, 1995. 868872
5̷.ͼֽɨͼʶͼؽо۲ʿѧλģ.㽭ѧ, 1992(Tan Jian-rong. Research on global recognition and graph reconstruction of scanned image of engineering drawingsPh.D. Thesis. Zhejiang University, 1992)
6̷,Ⱥ.ͼԼĹͼɨͼֱʶ𷽷.ѧ,1994,17(8):561569(Tan Jian-rong, Peng Qun-sheng. A global line recognition approach to scanned image of engineering drawings based on graphics constraint. Chinese Journal of Computers, 1994,17(8):561569)
7ݳ,,.еͼֱֽԲʶ𷽷.ͼѧѧ,1996,8():225230(Chen Yong, Zhu Lin, Chang Ming. A global line and arc recognition approach to scanned image of mechanical drawings. Journal of Computer-Aided Design and Computer Graphics, 1996,8(supplement):225230)
1997-10-21յԭ,1998-03-02յ޸ĸ 
