Image-Based 3D Browsing with Morphing
3-D browsing is a computer technique that enables people to visualize objects and scenes in the computer screen. Traditionally, 3-D browsing is realized with geometry-texture model, in which a mesh of the object or scene is constructed and textures are mapped to the mesh. This method, however, offers limited plausibility, and gets inefficient when the model is complicated. An alternative is the image-based way, which computes unknown views directly from photographs taken from other perspectives. This is a particularly useful way in 3-D demonstration, in that it provides convincing 3-D effects with nearly constant complexity. Nowadays, image based rendering (IBR) is one of the most thriving research areas in computer graphics.
In this final project, I build a system for triangulating series of 2D images of a 3D object. Multiple images are to be loaded from files and displayed. The system will also provide an interface for displaying and browsing the reconstructed 3D object models using OpenGL.
Morphing is an image processing technique used for the metamorphosis from one image to another. The idea is to get a sequence of intermediate images which when put together with the original images would represent the change from one image to the other. As shown in the figure below.
(please click on the middle figure)
Given two images I1 and I2, there exists a warping function f such that
Then we have
Assume to be our warping parameter, the morphing function F can be written as
In the morphing process, I1 is gradually warped and faded out, while I2 is gradually rectified in shape as well as intensity.
From the above discussion, we know that in order to get the morphing result, we have to propose a descent way to interpolate the geometry and intensity of two images with respect to the single parameter -
Steven M. Seitz et. al. found out that if the two images I1 and I2 are from different camera perspectives, we cannot simply apply linear interpolation to them; otherwise the following image is the result.
(Figure from Steven M. Seitz Charles R. Dyer, View Morphing, SigGraph 1996)
This is because there is a projective transformation between two arbitrary images in the form as below:
The transformations do not form a close set under bilinear interpolation, which is to say that generally linear combinations of two projective transformations are not a 2D projective any more.
However, when the two images are actually parallel - which means they do not have 3D rotation - it can be proved that the linear combination of two projective transformations is actually another projective transformation. Assume
are a pair of parallel projective matrices related with I1 and I2, which have the form as follows:
so that if we just do linear interpolation between the two images, we get
It is now easy to see that the three matrices all have the same form. And
is indeed a projective matrix.
Another thing we can take advantage of is that if two images are so close to each other, any non-linear interpolation can be approximated by linear interpolations.
Here is an example:
(please click on the middle figure)
2.3 Modified Delaunay Triangulation
(please click on the above figure)
Delaunay Triangulation Algorithm
NEW listPoints //an empty point list
NEW listTriangles //an empty triangle list
NEW listTemp //an empty point list as a temporary cache
WHILE there is still point P not added in listPoints
add P into listTriangles
FOR every triangle T in listTriangles, if P is inside the circumcircle of T
Delete T from listTriangles
FOR every vertex Q of T, if Q is not in listTemp
Add Q into listTemp according to the increasing order of the slope of segment PQ
2.4 2-freedom View
We can directly expand our 1D translational browsing to cylindrical browsing, and even to spherical browsing with 2 degrees of freedom. If we have one displacement parameter for translational browsing, one rotational angle for cylindrical browsing, we shall have two parameters - one for latitude and the other for longitude. And we therefore do 2D interpolations between three neighboring images instead of two. The idea is depicted in the following figures. 
3.1 Project Organization
3.2 Data Storage
For more information, please refer to User's Manual.
4. Difficulties & Further Discussion
Real View Morphing. Note that what we do here is not the same idea as that is stated in Seitz's paper. A parallel image plane example.
Ghost Effect. Notice the Fan example, there are locations inconsistant in even two neighboring views which causes so called "Ghost Effect". We can use denser sampling to reduce that problem.
Assembly. Whether or not it is better to combine the three programs into one needs further analysis.
In this project, we study morphing techniques in IBR systems. We developed a cylindrical system and a spherical browsing system with the mesh-based morphing algorithm, and tested their efficiency. Our conclusion is that image based rendering by view morphing is a viable means in 3-D rendering applications.
We also find some limitations in browsing with IBR, such as difficulties in preprocessing and in generating novel poses. We presented some discussions and suggestions in Part V.
On the whole, our browser offers convincing 3-D effects with little system expense. Further refinement may make it more practically useful.
 Steven M. Seitz, Charles R. Dyer. View Morphing. Proceedings of SIGGRAPH 96, pp. 21-30, August 1996.
 Thaddeus Beier, Shawn Neely. Feature-based Image Metamorphosis. Proceedings of SIGGRAPH 92, 26(2) pp. 35-42, July 1992.
 Seungyong Lee, George Wolberg, Sung Yong Shin. Polymorph: Morphing Among Multiple Images. IEEE Computer Graphics and Applications, Vol.18, pp. 58-71. November, 1998.