ѧ
JOURNAL OF SOFTWARE
1999ꡡ109ڡVol.10No.91999



̬ģֽıƽ㷨Ӧ*
ٽ𡡲ʿܡŸ
ժҪһֻȡ̬ģֽıƽ㷨ʵ˶ά̬ģ˫ֽ⣬ʹ㷨нϿĴٶ.̬ģֽ̬ͼЧһַǳõļ.»ͼеֱ߽㡢˵̬ģо.
ؼʡģֽ⣬㣬С˱ƽͼѧͼʶ.
ͼšTP391
An Approximate Algorithm and Its Application of the Morphological Templates Decomposition
ZOU Rong-jin,CAI Shi-jie,ZHANG Fu-yan
(State Key Laboratory for Novel Software Technology Nanjing UniversityNanjing210093)
(Department of Computer Science Jiangsu University of Science and TechnologyZhenjiang212000)
AbstractIn this paper, an approximate algorithm of obtaining morphological templates is described, and the bi-directional orthogonal decomposition of the two dimensional morphological templates is realized. The decomposition of morphological templates is a useful technique for enhancing the computational efficiency of morphological image processing operations. The recognition algorithm of the intersection points and the end points of the lines in engineering drawings based on the morphological templates is also proposed in this paper.
Key wordsTemplate decomposition, intervolve product operation, least squares approximation, computer graphics, image recognition.
ڹȥ10У̬ģΪһǿĹߣѹ㷺ͼͷ13.̬źʴԼǵϵͼҲ̬ģԪصķȡ˺ܴ.̬ģֽǻҪ.1רŵ֧̬ͼģʽṹģĴС״һЩԼ͵33ģ.̬ģ岢ޱҪСһ.̬ģֽΪСģķΪ̬ģĲṩЧֶ.ѧߣ16Ѿע⵽˹ڶֵͼҶͼ̬ģֽ.2ڽͼһضͼ̬仯ĸӶ.
һɷֽģָģһˮƽʹֱģ壬ģķ벿Сԭʼģƽ.ַʵҳɷģһӿռĻȻָģͶӰӿռĻģУģԭʼģСϵıƽ.ԭʼģɷַֽģľȷֽ⣬ҪļܴرȡN1N2ģС˷ֽ⣬Ҫ2N1N2(N1+N2-1)γ˷(2N1N2-1)(N1+N2-1)μӷ.
һּ㷨ʵ̬ģС˱ƽķֽ⣬ͼ㸴Ӷ.ͬʱͼֱ߽㡢˵̬ģо.
1ͼϢȡ̬ģ
Ϊ˶ͼռĸֽṹϢȡʹĳضĶά̬ģпռ㣬ԴﵽͻĳϢһϢĿ.ռǶĸԣȨ㣬ȨԱʾһͨΪ̬ģ.ѡģN1N2ĴСΪ335577.ռһʽΪ
(1)
ʽQΪͼУFΪͼУWΪ.
ƽһֳõͼ̬ģ壬4ֵ͵ģ.

״壬ҪķߣһЩӣԷֱ򡢺ԽߺҶԽ߷״壬ʾ

(a)   (b) ҶԽ߷򡡡 (c) 򡡡 (d) Խ߷
̬ģƶУÿصҪnnľֲ㣬ܴڴ湤ͼֽɨͼԼʵʱҪϸߵӦϵͳӰΪ.ͬʱĿǰɨֱʵߣͼľϸ̶ҲߣʹС̬ģ壬һͼνṹԷһ,Ҳӣ,ԽԽĸչ̬ģ壨n>3ʹõʵʵͼṹ֮.ǵڵԣҵһάȡֶάľֲǱĿǵĹؼ֮.ͨͼķֻһεһά㣬̬ģĶά㹦.
2̬ģķֽƽ㷨
һN1N2ľ̬ģ
(2)
Ĺؼȷģ壬һֱõģһˮƽõģ
(3)
ҪЩģԭģС˱ƽ.ģƽϱƽ
(4)
ˣƽΪ
(5)
ڸҪСС׼򣩣
(6)
(7)
ʽ(6)չ򻯣õ
(8)
ͬأʽ(7)չ򻯣õ
(9)
ʽ(8)ʽ(9)ļϱʾN1+N2Է飬N1+N2ǣֻN1+N2-1޹صģˣѡrN2-1=0෽þʾΪ
PQ=S(10)
У
(11)
,INNNλZNMһNMľԪʽ(2).CN1һN1Ԫص(c0,c1,...,cN1-1)TRN2-1N2-1Ԫص(r0,r1,...,rN2-2)T.ƵأXN1YN2-1ҲԪйʽ.
(12)
(13)
N1+N2-1Էʾľ󷽳̿ͨP.ǵPǶԳƾҲǶԳƾ.ΪP󣬱ʹ۵Ľ.
1. ADΪԳƾڱʽе.
(14)
,E=D-BTA-1B,F=A-1B.
2. GһUV
(15)
ʽ˴ӾGG+UVTݵһַ.
ý1ӦԪرʾΪ
A=N2IN1,B=ZN1(N2-1),D=N1IN2-1,(16)
ͿԵõ
A-1=N-12IN1,F=N-12ZN1(N2-1)E=N1IN2-1-N1N-12Z(N2-1)(N2-1).(17)
Ϊ˼Eʹý2
(18)
۹ʽԼ򻯣
E-1=N-11IN2-1+Z(N2-1)(N2-1).(19)
ˣԵõ
FE-1=N-11ZN1(N2-1),(20)
A-1+FE-1FT=N-12IN1+(N1N2)-1(N2-1)ZN1N1.(21)
ԣʽ(14)оPʽ
(22)
С˱ƽµģֽķʽɼ򵥵Q=P-1S.ģֽĴֱΪ
ci1=N-12xi1+ 0i1<N1,(23)

(24)
ƵأģˮƽΪ
ri2=N-11(yi2-yN2-1)0i2<(N2-1).(25)
̬ģֽ㷨
1 
(26)
2 
(27)
3 
(28)
4 ʽ(23)㡡{ci1;0i1<N1}
5 ʽ(25)㡡{ri2;0i2<(N2-1)}rN2-1=0
㷨ҪN1+N2-1γ˷2N1N2+2N1+N2μӷ.
3Ӧʵ̬ģĽ㷨
ͼֽʸеĽΪӦʵԾԺΪݵĶά̬ģ壬̬ͨģķֽʵֽĿټͼ⣬.
ڹͼֽɨͼУͼֱ߱ʾģ׼ȷʶֱߵĽλüֱ߶˵㣬֮Ĺդ㷨ͿжֱߵĴ.
ͼ1гɨͼֱ߽Ĵ̬.ڵǣνһģÿص̬ѧ㣬һµͼ.µͼУֱߵĽ㡢˵ϢӦֱֳ.ӾĽǶֱߵĽǱΪϺڵ򣬼ɫܶȽϸߵͼ1(b)(d)(g)(i)(j)еΪܶ.ֱߵĶ˵λһλھֲܶߵĽضϵλ.ֱͨߵм䲿λֽضϵλ.

ͼ1ͼֽɨͼеֱ߽̬
ʵһ˼ķǼÿһص㣨ڣֵֵܶܶӳԸصΪĵСڣڵĺڶ.ΪˣһȨw(t)ͼ2ʾǿĵأtֵСص㣩ܶȹһɱʾΪ
w(ti)=1/(tni+1) n=1,2,3,...nΪָ(29)
(30)
ʽЦ(i)ΪܶȺ.Ȩw(t)ѡʽָܶ࣬˥˥˥ȣtֵļһŷ¾ʾ.һ55m=5ľ뺯Ϊ7ݣģΪ

ʹģֽ㷨ɵõ

Ϊ(4)ʽõıƽķģ壬(5)ʽɼƽΪţ0.6228.

ͼ2Ȩ(t)
ںΪĻеļ޹صģҦ˺ͦҲ޹صģΪϵ.,ֱxyʹģۼܶȺֱʹöάģĽһµģȻС˱ƽ.
ʽ(29)(30)ɼͼÿصϵֵܶڹֱ߻ֱߵķֵཻ֣ܶӳֱߵλãһЧϸ㷨Чһµ.ֱཻĵطԲϸֲֵֵܶܶλǽģɴ˿ȷֱ߽λ.ֱߵĽͶ˵λܶͼϾֲɵ.
жһصpΪıҪǣ
1 p򴰿ڣ(p)>(i)i=1,2,...,Npi.
2 pԶֵܶjʣ(p)-(j)<ģ|j-|<.
жһصpΪ˵ıҪǣ
1 p򴰿ڣ(p)-(i)>ţſȡ-1.0<<0.0i=1,2,...,Npi.
2 pĵȸܶ{j}|(p)-(j)|<ģֻһλͬһ򣬼j1p,j2p<ֱ̣죩.
ֱ߽㼰˵ȷĻϣֱ֮ߵĴԽйդʸϼ⣬õݹеķFractal㷨беǷںɫصϣضںɫϣ㹹ֱ.ڲε㷨䲻ֱߵеһֻ12μֹˣʵʼС.
4ᡡ
һ̬ģķֽƽ㷨ֲάıΪһά㣬С˱ƽ׼򣬶̬ͼļЧһַǳõļ.ͬʱ½ͼʶеʸһӦ̬ģ崦ʶֱߵĽͶ˵㣬ϸ㷨ȾнϸߵĶλȺͽϿٶ.Ŀǰ㷨ֱֻߵһоչһͼصʶ.üѶ,Ҫҵһֻ̬ģ壬ڼ͵.
*оõŻ.
ͨѶϵˣٽϾ210093,Ͼѧ¼صʵ
߼飺ٽ1962ʿڣҪоΪͼѧͼʶ.
ʿܣ1945ڣʿʦҪоΪͼѧCAD.
Ÿף1939ڣʿʦҪоΪý弼ͼѧ.
ߵλٽ𣬲ʿܣŸףϾѧ¼صʵҡϾ210093
ٽ𣬲ʿܣŸףѧѧϵ򽭡212000E-mail: zjzrj@public.zj.js.cn
οף
1Shih F Y, Mitchell O R. Decomposition of gray scale morphological structuring elements. Pattern Recognition, 1991,24(3):195203
2Chang J Y, Chen C C. Decomposition of additively separable structuring elements with application. Pattern Recognition, 1993,26(8):867875
3Zhuang Z, Haralick R M. Morphological structuring elements decomposition. Computer Vision, Graphics Image Processing, 1986,35(4):370382
4Davidson J L. Nonlinear matrix decompositions and an application to parallel processing. Journal of Mathematics Image Vision, 1992,10(1):169192
5Gader P D. Separable decompositions and approximations of gray scale morphological templates. Computer Vision, Graphics Image Processing, 1991,53(5):288296
6Goutsias J. Morphological representation of discrete and binary image. IEEE Transactions on Image Processing, 1991,25(6):13691379
7.ͼ̬ѧ.Ϻ:Ϻѧ׳磬1990. 2357
(Wu Min-jin. Image Morphologic. Shanghai: Shanghai Scientific and Technological Literature Publishing House, 1990. 2357)
ոڣ1997-11-20޸ڣ1998-09-25
