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



ùݶȷؽά㷨о
괫馡
ժҪͨӾܵõһЩɢ㴦ϢЩɢ㴦άϢɶάؽҪùݶȷؽά㷨.
ؼʣݶȷά壬ؽά
ţTP391
RESEARCH ON AN ALGORITHM OF REBUILDING 3D
OBJECT SURFACE USING CONJUGATE GRADIENT METHOD
WANG Ru-ChuanWANG Shao-DiHU Lan
(Department of Computer science and Technology,Nanjing Institute of Posts and Telecommunications Nanjing 210003)
AbstractBy using stereopsis the 3D object surface informations of some dispersive points can be obtained.Based on these informations,the 3D object surface can be rebuilt. In the paper here,an algorithm of rebuilding the 3D object surface using the conjugate gradient method is discussed.
Key wordsconjugate gradient method ,3D object,rebuilding 3D object surface
ɻģߵȻеҵCAD/CAMо漰ؽ⣬ؽҪͨӾõһЩɢ㴦άϢΪ˵õһάͷϢҪݷɢıϢάؽ.Ͻ֪ͨɢıˣҪؽһͼϢһϱ.
1Ӳԭ
ӾǻǲԭͬһӲͬλõĳָݵһַ.׼ڲͬҳӦϵͨ׼õǶάӲϢҪתΪӾάֵҪڳģӲ࣬Ӳԭͼ1ʾ.


ͼ1Ӳԭͼ
ͼ1УCl,CrֱΪĹѧλ(͸)ClCr֮ľΪbΪf.ϵĵPͼϵͶӰֱΪPlPrPClCr߼ľΪdClCrֱͼߣֱΪAlArPͼߣΪB.|AlPl|=la,|ArPr|=lb,|PrB|=aοɵã
(1)
(2)
ʽ(1)ʽ(2)ɵã
(3)
Ӷ
(4)
ʽ(1)ɵã
(5)
ʽԿdbfla-lbй.la-lbΪPͼ.
2άؽ㷨
ͨӾܵõͼ㴦ϡӲֵΪ˵õһά棬Ҫݷɢ㴦Ϣάؽǽݼͼѧۼѧ滮ݶȷϸŻһֽάؽ㷨.
Ͻ֪ͨɢıͨһ֪ԲϵĵıƽԲ̣Ҳǰɷ״Һγɵľ.ˣάĻָҪؽһͼϢһµϱ.һϱǴڵģʹöαֺ
(6)
ﵽСֵSһ.
2.1㷨ϸ
ʽ(6)ĶαֺСֵɿһŻ⣬֪ǷɢݣӦѧ滮Ż.
(1) ѧ滮
ѧ滮ļ£ȣ滮ֳmmҪľÿһϵıϢ.ˣԽÿһ濴һm2άռеһ㣬ÿһάÿһֵ.m2άչ(m2+1)άʹһάǶαֺ(S)ֵ.(m2+1)άռнһ桱ΪĿ.(6)ʽСֵҲ͵ͬĿѰһ͵㣬һı漴ΪҪı.
ѧ滮ͨѰĿϵ͵㣺
١ѡĿϵһΪʼ.
ڡĿϼõһֲѡȡһе͵.
ۡ͵Ϊµʼ㣬ظֱҪΪֹ.
(2) Ŀ꺯ȷ
ʽ(6)ĶαֺģӦѧ滮ʱ轫תɢʽ.ڦ(S)ƽ㣬(S)СֵͬƽСֵ.
mmÿһΪ(i,j)ʾiСjе㣬ϵÿһS(i,j)ʾ.леĴS(i,j)ɵһm2άS={S(0,0),S(0,1)S(m-1,m-1)}.ɢʽ£ΪhƵУ

ٰ˫ػתΪȼ۵ɢʽɴˣõµĿ꺯

ؽȼʹһĿ꺯ﵽС.ΪؽһЩɢĵ㼯ԸĿ꺯ԼΪ
={(i,j)|(i,j)ϵ֪ĵ㼯}
ڦĵ(i,j)
S(i,j)-C(i,j)=0(11)
C(i,j)ǷӳݵһԼ.
2.2ݶȷ㷨Ż
ǰƵԿĿ꺯ǶεģС͹ʣĿϵõľֲС㼴ΪȫֵС.ߣΪĿ꺯ԼԵģĿ꺯СԲݶͶӰͬʱ԰ԼֱӺϲĿ꺯͵ȼһԼĿ꺯Ż⣬ͿԲùݶȷ.õľǹݶȷĿ꺯תΪ

һʾϳ̶ȵĲ.
2.2.1
ݶȷ(conjugate gradient methods)ԼŻһЧŻĻ˼Ŀ꺯֪㴦ݶȹһ鹲鷽Ŀ꺯ļСֵ.
AΪnnĶԳEnеd(1)d(2)
(d(1))TAd(2)=0(13)
AΪΪA.
κΪ
(14)
ʽУAΪnnĶԳx=x1,x2,,xnT,bT=b1,b2,,bn.
(15)
⣬ֱ۵ͼʾͼ2ʾ.


ͼ2
ĳһx(0)d(1)ʹf(x)ﵽСֵx(1)x(1)ΪôȸߵĽڵ㣬˵ݶȷΪȸߵķ߷.ˣ
Tf(x(1))d(1)=(b+Ax(1))Td(1)=0(16)
һx(0)d(1)ɵһСֵx(2)ͬ
Tf(x(2))d(1)=(b+Ax(2))Td(1)=0(17)
ʽ(17)ʽ(16)ĲΪ
(x(2)-x(1))T=Ad(1)=0(18)

d(2)=x(2)-x(1)(19)

(d(2))TAd(1)=0(20)
Ҳd(2)d(1)ΪA.ͼ2ɼd(2)x(1)x(2)еߵķ򣬴˷ϵļСֵ㼴Ϊf(x)ŵx*.
ɴ˿ɼڶԪκֻҪطd(2)d(1)һάεȻﵽСֵ㣻ŷϿռϷǸĶκònεﵽСֵ.
2.2.2ݶȷļ㲽
ݶȷ㲽£
(1)ʼx(0)ţòk=0
(2)㺯f(k)x(k)ݶg(k)=f(x(k))Ƿ㡬g(k)ܦţֹͣ㣬õx(k)ΪŽx*d(k)=-g(k)
(3)x(k)طd(k)һά㣬x(k+1)=x(k)+kd(k)
(4),У顬g(k+1)ܦţֹͣ㣬x(k+1)=x*ת(5)
(5)бǷk=nǣʾnΣnx(0)=x(k+1),k=0,ת(2)ת(6)
(6)

(7)òk=k+1ز(3).
2.2.3Ŀ꺯ݶȵȡ
ʽ(12)Ŀ꺯ʽڶݶʱijȡֵɷֳ6.ΪȿĿ꺯˫͵ǰ3Լ֣
(1)ĵ㣬(i,j){(i,j)|2im-3,2jm-3}(m-4)2㣬

/*ʽ(12)12͵3ƫ*/

ΪֳеĹԣʽΪʾÿһϵ£

ϵ40ӦΪS(i,j).
S(i,j)㴦ݶΪt(i,j)S(i,j)˵ĺͣؼt(i,j)ֵ¾ͲһһƵֱӸt(i,j)ֵ.
(2)4㣬(i,j){(0,0),(0,m-1),(m-1,0),(m-1,m-1)}Ӧ4ϵԵ(00)ΪƵɵã

4ϵã

ϿԿϵֵǻݶȵλöеģ֮ͨһġתõںļУ͸ϵһΪģ塱
3ıϲҾ붥һλȵ8㣬(i,j){(0,1),(0,m-2),(m-1,1)(m-1,m-2),(1,0),(m-2,0),(1,m-1),(m-2,m-1)}ԵS(m-1,m-2)Ϊݶȣ

ɴ˿ɵϵļ㡰ģ塱Ϊ

(4)ıϣȥ(2)(3)гĵ㣬(i,j){(i,j)|((j=0j=m-1),(2im-3))((i=0i=m-1),(2jm-3))}4(m-4).Ե(i,j){(i,j)|((i=m-1),(2jm-3))}Ϊݶȣ

ɴ˿ɵϵļ㡰ģ塱Ϊ

(5)ÿһλȵ4㣬:(i,j){(1,1),(m-2,1)(1,m-2),(m-2,m-2)}ԵS(m-2,1)Ϊݶȣ

ɴ˿ɵϵ㡰ģ塱Ϊ

(6)ھԵһλȵ4ϣȥ(3)(5)гĵ㣬(i,j){(i,j)|((i=1i=m-2),(2jm-3))((j=1j=m-2),(2jm-3))}4(m-4).Ե(i,j){(i,j)|((j=m-2),(2im-3))}Ϊݶȣ

ɴ˿ɵϵ㡰ģ塱Ϊ

Ŀ꺯ݶʱӦ6ּ㡰ģ塱ʽ(12)ǰݶȵĻϣټԼֵݶȼĿ꺯ݶ.ݶȺ󣬸ǰݶȷļ㲽裬ͿĿ꺯СֵҲı.
ͼ(ͼ3ͼ4)ǲ㷨ؽı.ͼؽڵĵǸMarr-Poggio㷨õģЩͼϢ.


ͼ3״¥ݵؽ֮һ(=1)


ͼ4״¥ݵؽ֮(=0.1)
ͼɵãϳ̶Ȳ±ʾؽġ⻬̶ȣ̫̫Сܺܺõؽ.ΪŵĦֵɲķȡͼ׼ʱƥĵЦֵĲԣȡֵؽʱʹЩƥĵӰ״ôֵͱ.
ͼпԿͼ׼õĻϣͨӦùݶȷαֺСֵάؽһеķ㷨˼·СüӾ۽߼⻷ӾһЧ.
3ᡡ
ӾǻǲԭͬһӲͬλõĳָݵһַΪջָռά״ӾһҪ3⣺ͼӲ㣬ӲָĳЩάԼϡάݻָ.
߼飺괫У19438ڣĿǰҪ¼ͼκ⡡.
馣194211ڣĿǰҪ¼ͨšͼ.
ᰣŮ19738˶ʿоĿǰҪ¼ͨš⼼.
ߵλ괫(ϾʵѧԺѧ뼼ϵϾ210003)
(ϾʵѧԺѧ뼼ϵϾ210003)
(ϾʵѧԺѧ뼼ϵϾ210003)
οף
1Celni G,Gossard D.Deformable curve and surface finite elements for free-form shape design. ACM SIGGRAP Computer Graphics,1991,25(4):257266
2Choi B K,Lee C S.Sweep surface modelling via coordinate transformations and blending.CAD,1990,22(2):8796
3.CAD/CAM.պѧ磬1994 
(Tang Rongxi. CAD/CAM Technology(in Chinese).Beijing:Beijing University of Aeronautics and Astronautics Press, 1994)
4괫.ͼμԭӦ.ʵ磬1997
(Wang Ruchuan. Principle and Application of Computer Graphics Technology(in Chinese). Beijing: People's Posts & Telecommunications Publishing House, 1997)
5¬ƽ̷٣ܹ.ؽһʵ÷оʵ.Chinagraph'96ļ.1996.9095
(Lu Zhangping, Tan Jianrong, Zhou Guangren. Study and implementation of a practical method for camber rebuilding.In Chinagraph'96 Collected Papers(in Chinese).1996.9095)
ոڣ1998-07-16
޸ڣ1999-03-19
