## Interactive Multigrid Image Warping## German CheungPlease contact German Cheung at german@ux2.sp.cs.cmu.edu for further details |

Return to Homepage | RealTime 3D Reconstruction | Temporal SFS | Human Kinematic Modeling and Motion Capture | Human Motion Transfer |

The major objective of the project is to utilize the fast nature of multigrid to image warping and build an interactive image warping program with both good local controls and smooth transition.

There are two major ways of performing image warping, namely mesh warping
approach [10] and field morphing method [1]. For the first method, a mesh with predefined
resolution is placed over the image and the user moves a subset of the mesh points
to some desired positions. A warp is then computed
based on *all* the mesh points. The advantage of this method
is its fast computation speed. However, as the warping is calculated on a predefined resolution
and each mesh point exert the same amount of influence on the warp, the expressiveness and
flexibility of the method are poor. For the field morphing method,
instead of imposing a mesh on the image, several
feature points or lines and their movements are identified by the user.
The warping is then determined by creating a "force field"
on the image pixels. Although this method allows the user to express and control the
exact warping of the feature points and lines, it is relatively slow as each image point
in the image is affected by all the warping force fields generated by the features.

The main aim of this project is to combine the advantages of the above two methods to build a real-time image warping system with good local control ability and smooth transition. The project idea is discussed in Section 3. The image warping system is described in Section 4 and some results are included in Section 5. Finally a brief conclusion is given in Section 6.

The basic theory of this project combines the idea of mesh and feature based warping. The user specified the transitions of a set of feature points in the image. Each feature point transition imposes a constraint on the warping mesh and the constraints propagate smoothly to the whole image. A smooth warping mesh (with resolution equal to the image resolution) is then calculated based on the constraints and the pixels are warped according to the warping mesh.

In this section, we will first explain how the problem of producing a smooth warping mesh based on several constraints is indeed equivalent to the problem of reconstructing a D surface based on scattered data points. Then a fast multigrid algorithm is introduced to solve the problem.

Figure 1 shows an image with some feature points and their desired transitions. The original positions of the feature points are represented by while the warped position are denoted by Mathematically, we can express the relation between as

**Figure 1:** Image with feature points and transitions.

Before formulating the problem into its mathematical form, we have to define the notion of smoothness. One way of quantifying the smoothness of a D surface is to use the thin plate model. The surface is modeled as a deformable thin plate and the degree of smoothness is measured by the amount of strain energy . The lower the strain energy, the smoother is the surface. can be expressed as

By applying the model to our problem and expressing the constraints (Eqs (1)) as energy of fitting, the solution of the surface mesh (similarly for ) can be obtained by solving the optimization problem as follows [8] :

Although standard relaxation methods such as Gauss-Seidel can be used to solve the above linear equation, the convergence rate is too slow and is thus inappropriate in our interative application. Instead, the fast multigrid method can be used. As discussed in [3], for a linear problem, the multigrid method speeds up convergence by relaxing the residual equation at a lower resolution (coarser grid) and correcting the solution at the fine level as follows :

- Relax on to obtain an approximation .
- Compute the residual .
- Transfer the residue to a coarse level by Restriction .
- Relax on the residual equation to obtain an approximation to the error .
- Transfer the residue back to the fine level by Interpolation .
- Correct the approximation at by the equation .

However, in our application, the above scheme will not work as the constraints are defined on the function but not on the error . This means that the the accuracy of the solution at a finer level cannot be consistently propagated to the coarser level by this correction scheme. As suggested in [7], this problem can be overcome by using a different multigrid scheme called full approximation scheme as first published in [2].

- Relax on to obtain an approximation .
- Compute the residual .
- Transfer the residual to a coarse level by Restriction .
- Rewrite the residue equation as .
- Approximate the residue equation on the coarse level as
- Define another function .
- Rewrite the residue equation at coarse level as
where

- Relax on the new equation above to obtain an approximation to the function
.
- Correct the approximation at by the equation
.

The algorithm for the surface fitting can be summarized as follow :

- Propagate the constraints at the finest level down to the coarser levels .
- Solve the equations at the coarsest level directly or by iterative relaxation.
- At a level with
*k > 1*, obtain an initial guess from the coarser level by interpolation. - Invoke the Full approximation Scheme at as discussed in 3.2.2.
- If
*k = L*, stop, otherwise, set and goto Step 3.

The whole process is illustrated in Figure 3.

**Figure 3:** Illustration of the Full Multigrid Full Approximation Scheme.

An image warping system is built with an user-interface as shown in Figure 4. The left image is the original image for warping and the right image is the warped image. The user can arbitrarily click feature points and specify their warped positions. The transitions will be shown by colored arrows with square dots indicating the final positions of the feature points. The warping system can be operated in two modes, namely the fixed mode and the interactive mode. The fixed mode performs warping after the user has specified all the feature points and their transitions. The interactive mode operates when the user wants to see the warping interactively by dragging a specific feature point. A hard copy feature is also added to the system so that the user can output not only the warped image but also the original image with the transition arrows in TIFF format. There is also a clear button so that the user can clear all the marked feature points. An accuracy slider is provided as an interface for the user to control how accurate the warping functions should be. An example is also included in Figure 4.

To prevent unpredictable warping, besides the constraints provided by the user, the four corners of the image are fixed. Moreover as in this application, it is desirable that the warping at the feature points are as close as possible to that specified by the user. Hence a large value of is chosen (note that is dependent on the grid size as discussed in [7]).

**Figure 4:** The image warping system.

This part of the results illustrate the effectiveness of the multigrid method as compared to Gauss-Seidel. Two experiments are performed to compare the effectiveness of both methods for a (finest) gird size of 32 x 32. A constraint is imposed on the surface at the point (19, 16) with an amplitude of 10. This is shown in Figure 5(a). Figure 5(b) and Figure 5(c) show the results of using Gauss-Seidel method and Full Multigrid method respectively. Both methods have the same absolute errors of 138.428 Gauss Seidel takes 2.32s for the computation while Full Multigrid uses 0.27s to reach the same absolute error. We can compare these two surfaces with that in Figure 5(d) which is the correct solution for the problem. It is obvious that although the surfaces by Gauss-Seidel and Full Multigrid have the same absolute errors, the latter one is in fact much closer to the correct solution as compared to the former one. An additional constraint is added to the system and the tests are performed again. The results are shown in Figure 6 which indicates that the Full Multigrid grid method is superior over Gauss-Seidel method both in accuracy and speed.

**Figure 5:** 3-D plots of (a). the constraints, (b). approximate solutions by Gauss-Seidel, (c).
Multigrid and (d). the correct solution.

**Figure 6:** 3-D plots of (a). the constraints, (b). approximate solutions by Gauss-Seidel, (c).
Multigrid and (d). the correct solution.

For example, in order to find the warping function for one dimension (say x) for a 512 x 512 image by using Full Multigrid Full Approximation Scheme (with the fastest parameter setting), it takes about 3s on a SGI O2 with a 175 MHz IP32 processor. The time is reduced to 0.7s for a 256 x 256 image. Hence the update rate is about 1 Hz for the interactive mode. Real time warping is possible for 256x256 image if a fast enough machine is used.

A set of original and warped images are shown in Figure 7 as an indication of the quality of the warping. It can be seen that the warping is quit smooth among all the constraints.

**Figure 7:** An example of warping a cat image using our warping system.

An interactive image warping system is built based on a surface fitting paradigm and fast multigrid method with smooth transitions and flexible local control. The system is able to perform close to real-time warping operations on images with sizes up to 256x256 with smooth transition. Moreover the technique can be extended to create animations [6] and perform three dimensional volume morphing [5].

- 1
- T. Beier, S. Neely, ``Feature-based Image Metamorphosis, ''
*SIGGRAPH'92 Proceedings*, 26(2), pg. 35-42, July, 1992. - 2
- A. Brandt, ``Multi-level adaptive techniques (MLAT) for partial differential
equations : ideas and software,''
*Mathematical Software III*, Rice. J.R. (ed.), Academic Press, New York, pg. 277-318, 1979. - 3
- W.L. Briggs, ''A Multigrid Tutorial,''
*SIAM*, 1987. - 4
- S. J. Gortler, M. F. Cohen, ``Hierarchical and Variational Geometric
Modeling with Wavelets, ''
*1995 Symposium on Interactive 3D Graphics*pg. 35-42, 1995. - 5
- A. Lerios, C. Garfinkle, M. Levoy, ``Feature-based Volume Metamorphosis, ''
*SIGGRAPH'95 Proceedings*, August, 1995. - 6
- P. Litwinowicz, L. Williams, ``Animating Images with Drawings, ''
*SIGGRAPH'94 Proceedings*, pg. 409-412, July, 1994. - 7
- D. Terzopoulos, ``Multi-level Reconstruction of Visual Surfaces: Variational Principles
and Finite Element Representations,''
*MIT A.I. Memo No. 671*, April, 1982. - 8
- D. Terzopoulos, ``Multilevel computational processes for visual surface reconstruction,''
*Computer Vision, Graphics, and Image Processing*, 24, pg.52-96 1983. - 9
- D. Terzopoulos, ``The Computation of Visible-Surface Representations,''
*IEEE Trans. PAMI*, Vol. 10, No. 4, pg. 417-438, 1988. - 10
- G. Wolberg, ``Digital Image Warping'',
*IEEE Computer Society Press*, 1990.