о뷢չ
JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
1999Vol.36No.6P.725-731



ڽڵ״ͼǼȡ㷨о

ժҪһӱڵλϢ״ͼǼȡ㷨.˽еĸդƴֱ߹һ棬һ򹹳һУɲڽеɼڵλü˽ṹϵͨͬһڵ㲢⻬Ľй鲢ΪͬԴأȡߵõ״ͼǼܡʵ㷨ܺõؿ˷˴ͳϸ㷨ڵ㴦ĹǼܻ估ߵȱݣȷرصļϢ׼ȷطӳؼ˹ϵ.
ؼʣǼȡ У ڵ㣬 ״ͼ ͬԴ
ţTP39
AN JOINT-POINT-BASED SKELETONIZATION
ALGORITHM OF LINE IMAGES
WANG JianZHANG Shu-ShengWANG Guang
(CAD/CAM Research Center of Northwestern Polytechnical University, Xi'an 710072)
AbstractDescribed in the paper here is a high-quality skeletonization algorithm of the line images, which emphasizes acquiring accurate data of joint-points. Firstly, the conception of cross section sequence (CSS) is proposed. If a line joining two points which lie on the two sides of a raster curve is approximately perpendicular with the local direction of this curve, this pair of points define a cross section. A group of sequent cross sections compose of a CSS which describes the contour of the straight or curved line segment. According to those contour points which do not belong to CSSes, the positions and the topological structures of joint-points can be retrieved by calculation and analysis. Each two CSSes which cross the same joint-points can be retrieved by calculation and analysis. Each two CSSes which cross the same joint-point and fulfill with the smoothing condition are merged as a part of a raster curve which is called the coorigin line segment (CLS). Finally, the completed skeleton of the line image can be extracted by calculating the middle lines of CLSes. The experimental results show that the joint-point-based algorithm can well overcome the defects caused by conventional thinning algorithms, such as the distortion of the skeleton at the joint points, a lot of surplus short lines, etc. This algorithm can preserve not only the completed and precise geometrical information of raster curves, but also the topological relation among the curves.
Key wordsskeletonization, cross section sequence, joint-point, line image, co-origin line segment
1
״ͼʶһֱоȵ.ʶǰΪ˼ٺ̵ͱģʽȡͨҪĹǼ(ֽ)һ̳ΪǼȡ(ϸ).ǼȡĺûֱӰ쵽ʶȷ.ΪǼȡı׼Ǽܵλþȣ˽ṹϵ׼ȷԣǼȡ㷨һȱݡǼڽڵ㴦ػ(ǽĶ˵ǵ֧ͳΪڵ)ǼкߡһصĹǼֳܷɹ߶εȣ1.ͼ1Ϊóϸ㷨ϸͼʾ˻.ʵĹǼܣٻȷʶ.һ״ͼǿԿȡͼнڵ򣬾ȷڵľȷλãڵ̶ˣôͼǼܵ˽ṹϵҲͻ̶(Ĺؽ)2.ڵȡǼܲ£ôǼҲѻ.Ϊڵ㴦ϢǳҪ.ΪӱڵϢĸǼȡ㷨˼·ͨӵķȡÿڵ㣬ȷλڵ˽ṹϵȷЩؽڴ˽ڵشЩڵ㣬˽Ǽ.


ͼ1ͳϸ㷨
2㷨еĻ
㷨ںڰ׶ֵͼ.ԼͼϽصΪԭ㣬XˮƽָYֱָ.ͼX᷽WidthؿY᷽HeightظߣͼһصɼΪp(x,y),x{0,1,,Width-1},y{0,1,,Height-1}.ʧһԣǼٶΪɫصȡֵΪ0ͼصΪɫȡֵΪ1p(x,y)=0ʱpΪص㣻p(x,y)=1ʱpΪͼص.
1. IΪͼصļ.KIӼK={p1,p2,,pi,,pn},pi=1(i=1,2,,n).KKΪIһͨ.
(1) Kеصͨ.
(2) KһֵΪ1صKеһص㲻ͨ.
״ͼһͨһػཻĲ.
2. صp(x,y)=1p4ڴֵΪĵ㣬pΪص.
4صбe4(x,y),߼ʽ£
(1)
p(-1,y)=0,p(x,-1)=0,p(Width,y)=0,p(x,Height)=0.e4(x,y)=1ʱp(x,y)Ϊص.
һͨص㼯Ϲͨߣ߿ɷΪ.һͨһ.߶8յĻ.
Լ״ͼУNߣÿֵΪ1صʼҲķʽи٣˳ʱ٣ʱ٣õNص㼯ϣÿص.
3. jnjص㣬jɼΪPj={pj(1),pj(2),,pj(nj)},(1jN),ǳpj(i+1)pj(i)ḷ́pj(i-1)pj(i)ǰֱpj(i+1)=succ(pj(i))pj(i-1)=pred(pj(i)).
4. һ㴦ָڲķʸΪڸõ㴦ڷʸ.
5. aΪͨKϵһص㣬Ϊa㴦ߵڷʸ.aΪ㣬ط򾭹4ֱ·һصֹǶص֮ǰһֵΪ1ĵΪaĶصbb=opp(a).
ע⣺aĶصΨһģbǶصĶص㣬ҲԲκصĶص.
6. PΪͨKȫصļϣp,qP,pq,(p,q)һ.(p,q)߼ʽǾͳΪKpq㴦Ľ棬C(p,q):
(2)
УD(a,b)Ϊصab֮ľ(a,b)λΪpixel;
Th1Ϊͨȡ2.
ע⣺һصڶ棬󳣷صĸ.󣬶״ͼC(p,q)p,qp㴦.
7. C(=C(p,q))C(=C(p,q))ǽ棬p{p,succ(p)}q{q,pred(q)}CC䣬CCḷ́ΪC=next(C)CCǰΪC=last(C).
8. LΪһϵн򼯺ϣL=(C0,C1,,Ck-1)(k>0)һԽCiCi+1(i=0,1,,k-2)Ci+1=next(Ci)(Ci=last(Ci+1))next(Ck-1){,C0}ĹϵǳLΪУC0ΪLͷCk-1ΪLβֱΪC0=head(L),Ck-1=tail(L).
ĳһͨĳΪУ߿Կǽƽе(Ⱦ)ô״ͼУЩмϳΪ״򣬶ɲ״ĵɵǳΪ򣬻ƽڵ.ڵͨλصĶ˵㴦۵㴦㴦֧㴦.
3㷨
㷨ļ·ǣȶԶֵ״ͼȡ٣Ȼҳȫвȡ״ͨ״״򲢷˽ṹݷ״˽ṹ⻬Ľнй鲢ȡǼ.
3.1ߵȡ
߼ʽʽ(1)£

УV(x,y)ֱH(x,y)Ϊˮƽ.
ʽ(3)ǿɽȡֽΪˮƽʹֱζĲ.ͼ£P=[h1,h2,,hn]T
Уhiʾiص㣬ֱĲɼΪ
Կֱϣжֻ뵱ǰСһСһе.ƵģˮƽϿͨеƺƵõh-ih+iˮƽϵĲɼΪ

ˣiصȡΪe4i=ViHiͼΪ
(4)
õк󣬿ڵ㶨߽и٣õУٹӦʼѭֵΪ1ĵҲࡱԭ߽Freemanʽ.ף3ݶԸ㷨ﲻ׸.
3.2״ȡ
ȡ٣ǿɵõɵķ.״ȡ£
1ݶ5ʹDDA㷨4ݣÿһĶص.
2ݶ6пܵĽ棬״ͼȫļF.
3ڽ漯FУΪ㣬ҳ㶨7ǰͺ̣ҳǰǰͺ̵ḷ́ƣֱǰͺ̣ҳĽ湹һУ˽еĽӼFɾ.˷ҳFепܵĽУɽмG.
ע⣬ѰҺ(ǰ)ĹУһC(p,q)ж㶨7ĺ(ǰ)ͼ2ʾ5.5УȡC(p,q)ΪC(p,q)ĺ(ǰ)ͼӼFɾ.


ͼ2C(p,q)Ķ(ǰ)
4ڽмGУܻͼ3ʾཻ.ǷǷ.ǼÿһĿȣΪеĿ.ཻĽУΪ̵ĽкϷзǷдӼGɾ.

ͼ3״ཻ
5ڱ㷨Уϣÿжܵĳʹڵ򾡿Сڽڵľȷλͷڵ˽ṹʵͼУ״ͼͨƽ̹ࡰ(С͹򰼿)ͼ4ʾЩʹɹͬһ״ĽзֳС.Ǹϲео.

ͼ4Ͻе
輯GеLm,Lnͷ(β)ֱΪCm(pm,qm),Cn(pn,qn)ͼ4.
 D(pm,qm)D(pn,qn)
 pmpn߽ƽqmqnߣ
 pm,pn֮qm,qn֮֮СD(pm,pn)/2
ǾͽLmLnϲΪһ.
GеĿԺϲĽмԺϲõļGΪ״򼯺.
3.3ڵȡۺ
㼯У״򼯺Gĵ㼴Ϊɷ״ĵ㣬Щģ֯ģǳЩΪ״.ڵȡҪЩ״ԽڵΪλ֯Щĸڵ.
(1)ڵȡ
״㼯ΪWȡһa,aΪ˳ʱ(ʱ)٣ֱһL1еһp1,p1q1L1Ķ˽C1ôp1q1q1ʼ˳ʱ(ʱ)һL2еһp2ƣͼ5ʾܸĳһLnLnеqnʱصa˽ڵAȡϣɸķ״ͽж˽ΧΪڵA.ӼWɾɽڵAķ״󣬿ɿʼһڵȡֱWанڵȡΪֹ.


ͼ5ڵȡ
9. ǰڵSӵ״ĸΪڵSĶ.
(2)ڵ㾫ȷλ
ͼ6ʾ״Lk1, Lk2, Lk3ཻڽڵS.ϣڵSľȷλӦǾLk1, Lk2, Lk3Vk1, Vk2, Vk3ĵ.ΪˣǸֵFΪ


ͼ6ڵ㾫ȷλü
(5)
УnΪڵSĶȣ
VkLkڿSʸ
WkǽڵSһsLk˽еʸ
(Vk,Wk)Vk,Wkڻ
Vk,WkʸVk,Wkģ.
֪SеĵsԽVk(k=k1,,kn)ֵFԽʹֵFĵs(x,y)ΪڵSľȷλ.
(3)ڵľۺ
ͼ7(a)ʾĳЩ״ǶģܳΪһڵֳ.Ӧÿ״жϣǷڶ࣬ڵǷԾۺ.ǹ涨ڵDС״WʱڵӦϲͼ7(a)ڵ㲻Ӧϲͼ7(b).


ͼ7ڵľۺ
3.4ڵ˽ṹͬԴصĹ鲢
״ͼУһԲֱཻ㽫ԲΪ״a,b.ǳa,bӦͬһĸصһ״ΪͬԴ.ΪʹȡĹǼܼࡢҪԻΪͬԴصһ״Թ鲢ڶͬԴȡһǼ.
ͨڵȡǻһЩڵϢڵĶȼЩ״˽ڵӵ.һڵ˽ṹĹʵϾͬԴصĹ鲢.ڵ˽ṹĿľȷЩཻڴ˺һͨЩ.
״ͼa,bΪͬԴأӦʣ
(1) a,b߿.
(2) a,bڵй⻬ʣ⻬Կa,bڽڵӴнͨнСĳһֵȼΪ⻬.ڳȡֵ=10
(3) һ״һڵ㴦ֻһ״֮ͬԴ.
3.5Ǽȡ
ÿ״ͼعɣͨϵ״ͽڵȡͬԴصĹ鲢̣صĹǼȡú.ÿɽڵͻΪͬԴص״Ӷɣ˾Ϊڵ㣬ʾͼͼ8.״߼ΪöεĹǼܣÿ֮ͨڵ㾫ȷλõӣɹصǼܣǼܵ˵ɶ˽ڵľȷλþ.


ͼ8Ǽȡʾͼ
4ʵ
Cʵ˱㷨ǼȡЧɲμͼ9.ԭʼͼ񡢹Ǽȡͳϸ㷨ϸıȽϣǿԿڽڵĹǼȡ㷨ϸ㷨и߾ȡ࣬ʧص.


ͼ9
㷨ıȽϣ
(1) 㷨ǼȡϢḻ.ÿһǼܶһֱߡԲֱԲ⻬ɵĸ.ͳϸ㷨õǶ߶Σںʶ֮ǰж߹鲢Щ߷صĻ䣬鲢.ñ㷨õǼܺٽֱߡԲȻصʶ𽫱׼ȷⱾ㷨ȡУȰصľȷλϢ߿ϢҲؼϢͽڵϢǽкӹϵʶĻ.
(2) ڵ˽ṹ(硰T͡Xͻӵཻϵ)ȷرڵλþȷ.ͼ9(a)ƫһԲֱཻ߽Ľڵ㣬ʵϲһ㣬ཻ㷨ȡǼ(ͼ9(e))ȷطӳԭͼ⣬ϸԵĻ.ͬʱϸ㷨ʹøʴԭ޷ƽڵλã㷨ͨ״ߣϸطȷڵλãԾи߾.
(3) 㷨.ϸ㷨ڡT͡Xͻӵཻ£ּߣʶ鷳ͼ9(f).ڱ㷨򲻻.
(4) 㷨нϺõ.ָԭͼϾеĻɨʱİߵë.ʹϸ㷨ʱǿΪʲôͼ9(f)һЩڵ㴦ĪĶ.㷨Ǵ״ģԶ.
ŵģ㷨ҲһЩȱдĽ£
(1) 㷨ԭͼһҪ.ԭͼճȡһϴʱڽڵ㸽ֽϴʱӰȡԴȽͼԵ⻬Ա㷨.
(2) ԣ㷨Ȼȡ˱ϸ㷨Ϣʹʱ̣ʱԭϸ㷨2.54.0㷨Чд.
5ᡡ
㷨˼·ȡͼ(ڡ)УȻһЩڡƥ䣬ƽеڡֱʾⲿΪ״Ȼߺ߿߼ΪǼܣδʾΪڵ򣬸״ڵӹϵȷڵ˽ṹͣڵλã󽫽ڵ򲿷ֵĹǼγĹǼܽ.
һ㷨֤˽ڵ㴦ϢƻǼȫԭͼ߿ڣɾȷصλϢ˽ṹϵһָ߾ȹǼȡ㷨.㷨ɨ״ͼĹǼϢ߿ϢϢ.ǼϢǺͼʶĻ߿ϢǺʶĻϢҪʱΪṩԭʼϢ.㷨˶ߺϲ⣬ùǼϢ߶εļβݼβڽӹϵ߿ϢͬԴ߶ι鲢Ϊһ߶.
㷨ΪͼֽʸʶȶֵͼеĹǼȡṩһӱЧֶ.
ĿõѧعԱл.
߼飺У197211ʿоҪ¹ͼ⡢Ƚģʽ뼼ȷо.
У19569ڣʿʦҪȽģʽ뼼򹤳̡ͼ⡢칤еӦõȷо.
㣬У196312ʿоҪ¹ͼ⡢򹤳̵ȷġо.
ߵλҵѧCAD/CAMרҵʵҡ710072
ҵѧCAD/CAMרҵʵҡ710072
㣨ҵѧCAD/CAMרҵʵҡ710072
οף
1. ڽͼɨ蹤ͼǼȡо[˶ʿ]. ҵѧ1997
(Wang Jian. Research on CSSG-based skeletonization method for engineering drawings (in Chinese). Northwestern Polytechnical University, Xi'an,1997)
2Toshirp Suzuki, Shunji Mori. Structural description of line image by the cross section sequence graph. International Journal of Pattern Recognition and Artificial Intelligence, 1993, 7(5): 10551076
3У. ͼεԶ߸ϸ.΢ͻӦã1994(9)2628
(Zuo Jianzhong, Zhang Xinrong. Automatic tracing and thinning of engineering drawings. Micro-Computer and Application (in Chinese), 1994, (9):2628)
4ҵȺ. ͼѧ̳. ѧ磬1994
(Tang Rongxi, Wang Jiaye, Peng Qunsheng et al. Course of Computer Graphics (in Chinese). Beijing:Science Press, 1994)
ոڣ1998-09-02
޸ڣ1999-03-08
