о뷢չ
JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
1999ꡡ3611ڡVol.36No.111999



һֻεͼ㷨
־Ҷ
ժҪ߹ƶ,õBeizerߣΪ߶ͼڵƵӳ䣬һЧĲֵ㷨Ŀ-Դӳ䣬صʵֱЧ.ʵ֤㷨Ч棬һʵüֵ.
ؼʣΣBezier ߣӳ䣬ֵ
ͼţTP391
AN IMAGE DEFORMATION ALGORITHM BASED ON
POLYGON OF OUTLINE
WANG Jin, PAN Zhi-Geng, and YE Cheng-Qing
State Key Laboratory of CAD & CGZhejiang UniversityHangzhou 310027
Department of Computer ScienceZhejiang UniversityHangzhou 310027
AbstractTwo Beizer curves from two random control ploygons are obtained firstly in the present paperwhich are constituted of two discount lines then these curves are taken as control lines to map those web control points within a ploygon of outlineFinally, an intuitive and expeditious interpolation algorithm realizing object-source mapping is used to paint every pixel. Experimental results of image deformation using the algorithm prove that this algorithm is intuitive, expeditious, and practical.
Key wordsimage deformtion, Bezier curves, region mapping, interpolation
1
ͼμӰӡ桢֡ṤCAD˹㷺Ӧ.ӹ֡ͼƬָ״任ͼεЧӦ.ͼηΪάΡά֣жάǶԶάƽͼΡͼбδ.ĿǰӦý϶Ķά.
2ƶζͼν仯
2.1ƶBezier
㷨L1L2Ϊ.L1n+1p0,p1,p2,p3,,pn ɣL2m+1q0,q1,q2,q3,,qm ɣɵõ
nεBezierL1䣺
mεBezierL2䣺
ͼ1ʾ.


ͼ1
2.2Bezier߶νб仯
Polygons+1u0,u1,u2,u3usɣһui(x,y)±仯ͼ2.


ͼ2
2.2.1εĸӳ
֪ͼһuixyͼ᷽Ϊֱ򣨼ӾκߵķXнǦΪ0ͼ2ʾ.
uixyֱXᡢYƽߣ4ߵĽΪtxtytbxbyblxlylrxryr.

ԵĸʾBezier߶εĳȣͼ2У

 

ͬɵ

͵õui(x,y)Ӧֱ߶Σ
ͬͼ2

ɵõ

ˣui(x,y)Ӧĵui(x,y)ѾӦø㷨θӦĵ.
2.2.2εĸӳ
㷨ٴε2.1ڵ˼ӳνƽ.
ͼɶɣζԸν任ͿɵõͼƽɵŤ.ͼ3еһӦ.


ͼ3
2.3Bezier߶Ƶ任
Ӧ2.2е㷨ԴڲƵ任Ϊõ3㷨иصֵ׼ͼ4ʾ.


ͼ4
2.4ͼΪⷽ
ִǰΪͼ᷽Ϊֱ򣨼ӾκߵķXнǦΪ0ڽ㷨ƹ㵽ΪǶȵ.
ð滻᷽ΪȶȵӾελã4ΪLeftTopxltylt LeftBottomxlbylbRightTopxrtyrt RightBottomxrbyrbͼ5ʾ.


ͼ5
ڵlp(x1,y1)֪йϵʽ

x1y1ֵ֪

ͬt2ŵļȫͬ2.2ڡ2.3.
3һֿٵĲֵ㷨
˫Բֵ˼룬Ƶһֱڱ̡ٶȿĲֵ.
ǿɼԴͼ,Դͼ϶һ,ͼ64ԴĿ.4ֱĿ-Դӳ,ͼ.
ͼ6ʾûԭͼеdown϶up,Ŀ-Դοֻ֪ҪĿıεĸԭıεӦλ,ĿıεĻҶֵΪԭıεӦλõΧĵҶֵƽֵ,ͼ.ͬʱӳͲֵĿıαԭıδ(ͼŤöô),ԭıεӦ.ӳ㷨ͼ7ʾ.


ͼ6任4


ͼ7ĿӳΪԴӳͼ
ͼ,(a,b,c,d)Ŀı,Ǳ(a,b,c,d)еĵP(x,y)(aa,bb,cc,dd)еĶӦP(xx,yy),˵ĵ㼴ص.
֪,ֱabϵһAɱʾΪa(1-)+b, 0ܦ1;:
Ax=ax(1-)+bx , Ay=ay(1-)+by.
AxʾAĺ,AyʾA.axʾaĺ, ayʾa꣬ͬ.
ͬ,ֱbcϵһBԱʾΪ
Bx=bx(1-)+cx; By=by(1-)+cy 0ܦ¡1;
ɴ˵õ:ı(a,b,c,d)еһP(x,y)ԱʾΪ
x=(1-)(1-)ax+(1-)dx+(1-)¡bx+¡cx(1)
y=(1-)(1-)ay+(1-)dy+(1-)¡by+¡cy(2)
 0ܦ1, 0ܦ¡1.
ҪP(aa,bb,cc,dd)еӦP(xx,yy),ʽ(1)ʽ(2)ͦ,ʽ
x0=(1-)(1-)aax+(1-)ddx+(1-)¡bbx+¡ccx(3)
y0=(1-)(1-)aay+(1-)ddy+(1-)¡bby+¡ccy(4)
x0,y0ֵȡΪxxyy. ,͵õP.
Pľ:
(1-)(1-)Ϊu;(1-)Ϊv;¡(1-)Ϊw;Ϊt.
u+v+w+t=1.(5)
ɴ˼,õ
(u+w)(u+v)=u(6)
(v+t)(v+u)=v(7)
(w+t)(w+u)=w(8)
(v+t)(w+t)=t(9)
ʽ(6)/(7)ɵãu/v=(u+w)/(v+t)=(1-)/
ʽ(8)/(9)ɵãw/t=(w+u)/(v+t)=(1-)/.
ɴ,ǵõu/v=w/t.u/v=1/kv=uk,t=wk
Ӷʽ1ʽ(2)дɣ
uax+kudx+wbx+kwcx=x(10)
uay+kudy+wby+kwcy=y.(11)
ʽ(10)ʽ(11)ɵã
u(ax+kdx)+w(bx+kcx)=x
u(ay+kdy)+w(by+kcy)=y.
,ǵõ
(12)
(13)
ʽ(5)v=uk,t=wkɵõ:
(u+w)(1+k)=1(14)
ʽ(12)ʽ(13)ʽ(14)õһkһԪη:
(15)
ʽ(15)kʽ(12)ʽ(13)uw,vtv=uk,t=wkõ.
,u,v,w,tȫ,Ӷɦ=v+tͦ=w+t˦ͦ.ѽĦͦ´ʽ(3)ʽ(4)ȡ󼴽PԴζӦP.Ȼ,ǲǼ򵥵ذPĻҶֵΪPĻҶֵ.ǰPĻҶֵΪPΧ4ĻҶƽֵ.
,ͼ㷨:
1. ĿһصP(x,y)2.
2. ÷(1)(2)PĦͦ,õĦͦ´ʽ(3)ʽ4x0y0x0y0ȡΪxxyy, P(xx,yy)ΪPԴеĶӦ.
3. ĿеصPĻҶֵΪ2õPΧ4ĻҶƽֵ. Ŀеص㶼ִ˲2,㷨,ûִйӳһת2.
4ͼε㷨
ڣ2.3ڵĽΪǰᣬȻСζԸƵеӳ䣬Ӧõ3ڵĲֵ㷨иصĻƣʵֶͼı.
ñ㷨£
1 ֹջϵͳͼԵõͼĸΣ
2 ڿƱεߣӦBezierߣ
3 ӵһοʼδֱȫϣ
4 ӵǰڵĵһпʼδֱȫϣ
5 ӵǰеĵһеƵ㿪ʼδֱȫϣ
6 Ӧ2.3ڵ㷨任ǰƵֵӦõ3ڵĲֵ㷨Сн4ڸصĲֵƣ
7 5Ľ¼滻Դͼԭأ
8 ת3.
ͼ8 Ӧý.

(a)һһ΢Ц

ͼ8ֱЧ
5
ı㷨Bezier߼ӿƣʹñι̸׿ơҲܱ棻иĲֵ㷨Чʸߡ.ȤĶ߿ԺܿCC++ʵִ㷨.пߵĸĿЧҪؽƻ粻⣬ɱȽ׵ؽһԿ߾ֲ.
߼飺ʿоҪоΪṤCADͼѧ
־ʿʦҪоΪʵͼѧ
Ҷ壬ʿʦҪоΪܼϵͳ.
ߵλ־㽭ѧCAD & CGصʵҡݡ310027
Ҷ塡㽭ѧѧϵݡ310027
οף
1Hu Xiaoxue. The algorithms for region mapping and their applications. Chinese Journal of Advanced Software Research, 1992, 5(2): 8795
2־ǿ,ƺ. һͼ㷨. ͼѧѧ, 1998, 10(1): 16
(Lao Zhiqiang, Pan Yunhe. A feature-based image deformation algorithm. Journal of Computer-Aided Design & Computer Graphics(in Chinese), 1998, 10(1): 16)
3, ׯ, Ⱥ. һӦòĶ̬ɱη. ѧ, 1997, 20(7): 600606
(Feng Jieqing, Ma Lizhuang, Peng Qunsheng. Animated free-form deformation following the shape of parametric surface. Chinese Journal of Computers(in Chinese), 1997, 20(7): 600606) 
ԭյڣ1998-10-27޸ĸյڣ1999-07-06.
