430 IEEE TRANSACTIONS ON VISUALIZATION AND COMPUTER GRAPHICS,VOL.14,NO.2,MARCH/APRIL 2008 interior values of the function with known Dirichlet boundary condition and a guidance vector field.Due to its sparse linear property,the Poisson equation can be solved efficiently using conjugate gradient method or multigrid method [34]. Our Poisson-based algorithm adopts the normal-guided propagation rules for texture synthesis developed in Image space Texture space Textureshop [1].These rules describe the offsets of texture coordinates among adjacent pixels.We rewrite them as Fig.4.The orientation of the triangles(a)in image space should keep follows: consistent with that of their corresponding ones (b)in texture space. u(x+1,y)-u(x,y)=fur(N(x,y)), (9) TPI =T(PiPl Pi),and Tp2 =T(PiPi P2)(Fig.4).For each pair of corresponding triangles,the orientations of points v(x+1,)）-v(x,=fm(N(x) (10) should be equal.To achieve this,we define wij=sgn min(det(QiQ,QjQridet(P.Pei,P;Pe), u(x,y+1)-u(x,y)=f(N(x,) (11) det(oQa,QQa）·det(BP,BPa)） v(,y+1)-(x,)=fw(N(x,) (12) (7) where (u(r,y),u(,y))is the texture coordinate of the pixel (y)in the concerned region,N(r,y)=(N,Ny,N:)is the The energy function is then transformed into normal vector at pixel(x,y),and =∑(I.-Q,2-)/% (8) fa(N(c,)=(1+N:-N)/(1+N)N), (13) (i,j∈edges where the coefficient w;penalizes the triangle in M'whose fw(N(,y))=(NzNu)/((1+N2)Na), (14) orientation of points flips over with respect to its corre- sponding triangle in M.If so,wij is chosen as-1,otherwise, fw(N(x,)=(1+N:-N)/(1+N)N). (15) +1.With this energy function,a valid mesh in texture space is obtained. Since the texture coordinates of nodes in M are available, The minimal value of (8)is computed by the multi- (9)-(12)can be used directly to calculate texture coordinates dimensional Newton's method.For each iteration of New- of the interior pixels of triangles in M.In practice,this may ton's method,one multigrid solver is adopted for solving result in a wired mapping.For avoiding it,the texture the sparse linear equations.In practice,it converges to the coordinates are obtained by solving the energy minimiza- final solution within several seconds. tion problem below with respect to the u component.The v Once M'is obtained with the parameterization process, component can be computed in a similar way: a new texture can be mapped onto the ROI of the input image.Since the parameterization takes into account the minu(z.y) IVu(z,y)-Du(y)2 (16) underlying geometry of ROI,the new texture deforms naturally with respect to the underlying surface.Our where Vu(x,y)=(u(x+1,y)-u(x,y),u(x,y+1)-u(x,y)), experimental results demonstrate that the distortion effects and Du(,y)=(fur(N(,))fu(N(,y)). of the new textures are visually pleasing. Minimizing (16)yields a set of Poisson equations: 3.3 Poisson-Based Refinement △u(x,y)=divDu(z,y), (17) After the stretch-based parameterization,texture coordinates where A and div represent the Laplacian and divergence of the nodes in M have been obtained.Texture coordinates of operators,respectively.We adopt a multigrid solver to the interior pixels of triangles in M can be computed by obtain the solution with high efficiency. interpolating the obtained ones using barycenter coordinates Unlike the widely used Dirichlet Boundary conditions or the Radial Basis Functions (RBFs).However,such [32],[34]of the generic Poisson process,the external force in interpolation techniques cannot reflect the distortion effect our Poisson equations is imposed by the discrete texture of the new texture in the interior of each triangle.For coordinates of nodes of M. obtaining natural and smoother distortion,we design a Poisson-based refinement process instead of using interpola- 3.4 Lighting Effect Transfer tion techniques with barycenter coordinates or the RBFs. Using texture coordinates deduced by the stretch-based The origin of Poisson equation is from Isaac Newton's parameterization and Poisson-based refinement process,a laws of gravitation [31].It has been widely used in new texture is mapped onto ROI of the input image to computer graphics,including seamlessly image editing overwrite the old one.Due to the lack of simulating lighting [32],digital photomontage [33],gradient field mesh manip- effect exhibited in ROI,the mapping result looks flattening. ulation [34],and mesh metamorphosis [35].The main For realistic appearance,transferring the lighting effect principle of Poisson equation lies in how to compute the must be considered.TP1 ¼ TðPiPk1PjÞ, and TP2 ¼ TðPiPjPk2Þ (Fig. 4). For each pair of corresponding triangles, the orientations of points should be equal. To achieve this, we define wij ¼ sgn min det QiQk1 !; QjQk1  ! det PiPk1 !; PjPk1  ! ; det QiQk2 !; QjQk2  ! det PiPk2 !; PjPk2  ! : ð7Þ The energy function is then transformed into El ¼ X ði;jÞ2edges wij kQi Qjk2 l 2 ij 2. l 2 ij; ð8Þ where the coefficient wij penalizes the triangle in M0 whose orientation of points flips over with respect to its corre￾sponding triangle in M. If so, wij is chosen as 1, otherwise, þ1. With this energy function, a valid mesh in texture space is obtained. The minimal value of (8) is computed by the multi￾dimensional Newton’s method. For each iteration of New￾ton’s method, one multigrid solver is adopted for solving the sparse linear equations. In practice, it converges to the final solution within several seconds. Once M0 is obtained with the parameterization process, a new texture can be mapped onto the ROI of the input image. Since the parameterization takes into account the underlying geometry of ROI, the new texture deforms naturally with respect to the underlying surface. Our experimental results demonstrate that the distortion effects of the new textures are visually pleasing. 3.3 Poisson-Based Refinement After the stretch-based parameterization, texture coordinates of the nodes inMhave been obtained. Texture coordinates of the interior pixels of triangles in M can be computed by interpolating the obtained ones using barycenter coordinates or the Radial Basis Functions (RBFs). However, such interpolation techniques cannot reflect the distortion effect of the new texture in the interior of each triangle. For obtaining natural and smoother distortion, we design a Poisson-based refinement process instead of using interpola￾tion techniques with barycenter coordinates or the RBFs. The origin of Poisson equation is from Isaac Newton’s laws of gravitation [31]. It has been widely used in computer graphics, including seamlessly image editing [32], digital photomontage [33], gradient field mesh manip￾ulation [34], and mesh metamorphosis [35]. The main principle of Poisson equation lies in how to compute the interior values of the function with known Dirichlet boundary condition and a guidance vector field. Due to its sparse linear property, the Poisson equation can be solved efficiently using conjugate gradient method or multigrid method [34]. Our Poisson-based algorithm adopts the normal-guided propagation rules for texture synthesis developed in Textureshop [1]. These rules describe the offsets of texture coordinates among adjacent pixels. We rewrite them as follows: uðx þ 1; yÞ uðx; yÞ ¼ fuxð Þ Nðx; yÞ ; ð9Þ vðx þ 1; yÞ vðx; yÞ ¼ fuvð Þ Nðx; yÞ ; ð10Þ uðx; y þ 1Þ uðx; yÞ ¼ fuvð Þ Nðx; yÞ ; ð11Þ vðx; y þ 1Þ vðx; yÞ ¼ fvyð Þ Nðx; yÞ ; ð12Þ where ðuðx; yÞ; vðx; yÞÞ is the texture coordinate of the pixel ðx; yÞ in the concerned region, Nðx; yÞ¼ðNx; Ny; NzÞ is the normal vector at pixel ðx; yÞ, and fuxð Þ¼ð Nðx; yÞ 1 þ Nz N2 y Þ=ð Þ ð1 þ NzÞNz ; ð13Þ fuvð Þ¼ð Nðx; yÞ NxNyÞ=ð Þ ð1 þ NzÞNz ; ð14Þ fvyð Þ¼ð Nðx; yÞ 1 þ Nz N2 xÞ=ð Þ ð1 þ NzÞNz : ð15Þ Since the texture coordinates of nodes in M are available, (9)-(12) can be used directly to calculate texture coordinates of the interior pixels of triangles in M. In practice, this may result in a wired mapping. For avoiding it, the texture coordinates are obtained by solving the energy minimiza￾tion problem below with respect to the u component. The v component can be computed in a similar way: minuðx;yÞ Z M j j ruðx; yÞ Duðx; yÞ 2 ; ð16Þ where ruðx; yÞ¼ðuðx þ 1; yÞ uðx; yÞ, uðx; y þ 1Þ uðx; yÞÞ, and Duðx; yÞ¼ðfuxðNðx; yÞÞ; fuvðNðx; yÞÞ. Minimizing (16) yields a set of Poisson equations: uðx; yÞ ¼ divDuðx; yÞ; ð17Þ where and div represent the Laplacian and divergence operators, respectively. We adopt a multigrid solver to obtain the solution with high efficiency. Unlike the widely used Dirichlet Boundary conditions [32], [34] of the generic Poisson process, the external force in our Poisson equations is imposed by the discrete texture coordinates of nodes of M. 3.4 Lighting Effect Transfer Using texture coordinates deduced by the stretch-based parameterization and Poisson-based refinement process, a new texture is mapped onto ROI of the input image to overwrite the old one. Due to the lack of simulating lighting effect exhibited in ROI, the mapping result looks flattening. For realistic appearance, transferring the lighting effect must be considered. 430 IEEE TRANSACTIONS ON VISUALIZATION AND COMPUTER GRAPHICS, VOL. 14, NO. 2, MARCH/APRIL 2008 Fig. 4. The orientation of the triangles (a) in image space should keep consistent with that of their corresponding ones (b) in texture space.