TopWare 18: Liquid/Image.iso/liquid/top1086/wmorph.doc

Text File | 1993-08-22 | 10KB | 343 lines

                         WMORPH - 2-D Morphing Program

                           Version 1.0  May 21, 1993

                         Lam Ka Po ([e-mail])
                       Wong Wing Kin ([e-mail])









Objective

        This program WMORPH is a self-proposed project in our Computer
Graphics course.  The aim of the project is to build a 2-D Morphing system
running on PC.  User can input two 320x200 256-color GIF images files
and specify corresponding points on the two images.  The system will
produce a series of intermediate images showing the transition from the
original image to the desired image.  The intermediate images are
stored as 320x200 256-color GIF images file.














2-D Morphing

        Most of the techniques for 2-D morphing come from digital image
warping; a growing branch of image processing.  Digital image warping deals
with the geometric transformation of digital images, redefining the spatial
relationship between points in an image.  One of the most common applications
for image warping is texture mapping, a technique that is central to morphing.  To do a
morph, the animator needs to define a correspondence between the initial and
final images.  This can be done using points, triangles or meshes.  Once the
relationship has been defined, the textures in the images are blended from
the initial image to the final image to produce the morphing sequence.

    The method of subdividing the images varies between different morphing
programs.  The one used in this project defines common points in the two
images.  For a human face, these points could include the eyes, eyebrows,
nose and mouth.  Triangles are built from these points to create corresponding
areas on the images.  One of the most popular triangulation algorithms,
Delaunay triangulation is used in this program.  Delaunay's algorithm
maximizes the angles within each triangle and minimizes the lengths of the
sides.

    After subdividing the images, the transformation from the source to the
destination begins.























Project Description

A. Operating Environment

1.    DOS 5.0 or above
1.      80386 or above
2.      VGA 320x200 256 color
3.      Mouse & MS Mouse Driver ver 8.0 or above
4.      At least 5M hard disk space for output files
5.    At least 300K conventional memory













B. Program Description

1. Menu Display

a. Input image files

    Two buttons named "Source" and "Target" are used to
input images file.  When the button "Source" is clicked, a dialog box
would appear and prompt the user to input the source file.  When
this file is successfully loaded, the button name is replaced by the
source file name and the image would appear on the left window of the
menu.  Similarly, the destination file can be loaded using the "Target"
button.  The destination image would appear on the right window of
the menu.

b. image Movement

        As the window size is smaller than the image size,
clipping is employed to display only a portion of the image in the
screen.  In order to scroll to the other part of the images, four
buttons can be used.  These four buttons placed at the lower left
part of the menu.  The four direction buttons represent the
movement in the four directions.  Two speed can be used to move.
When the center part of button is clicked, the movement is slow.
However, when the tip of the direction sign is clicked, the
movement is about five times the slower one.

c. Mouse Pointer

    A mouse pointer can be seen in the menu.  It is used not
only to click the menu button, but also for point selection.  When
click the mouse on the images, a white spot appeared indicating
that that point is chosen.

d. Add Button

        The Add button is used to confirm the points selected on the
images.  After the selecting the two points on each image, the user
should then click the Add button to confirm that this point is to be
added.  After clicking this button, the point would be read and
triangles are formed on the images.

e. Morph Button

        The button Morph is used to start morphing.  When this button
is clicked, a dialog box would ask the user to input the file name.
It should be not more than five characters since another three digits
would added to the end of the file name to indicate the series of images.
Then, another dialog box would prompt the user to input the number of
intermediate steps required.

f. Exit Button
    This button is clicked when the user would like to
terminate the execution of the program.















C. Program Processing

1. Delaunay Triangulation

    The system use the "On-line Delaunay Triangulation"
algorithm to link up all inputted points on the source and destination
images.  On-line algorithm is used to give user a look
on the triangulation before input another points.

    The employ of the optimal triangulation algorithm is to
avoid generating triangles with sharp angles and long edges.  This
is important for image processing applications as it ensures that
only nearby data points will be used in the surface patch
computations that will follow.

    Initially, the four corners are pre-inputted as the first four
points.  Therefore, a diagonal line is seen on each images after
loading since two triangles are formed by four corner points.  In
addition, no points can be added on the four boundary edges of
each images.

2. Bresenham Scan Converting Line Algorithm

    Bresenham Scan Converting Line Algorithm is used to
draw lines on the images.  All the triangles are drawn by this line
drawing method.

3. Linear Transformation

        When the program starts to morph, the transformation of the
triangles is done by Linear Transformation.  This algorithm provides
an easy way to find the intermediate position of the triangles.

4. Find Points Within Particular Triangles

    After finding the intermediate triangles, corresponding
points of the source, intermediate and target triangles must be
known in order to find the corresponding color for those points.

    A similar approach to the scan converting left edge of a
polygon described in textbook is used to find out all the points
within a given triangle.

5. Affine Transformation

    After finding the points in each triangles, Affine
Transformation is used to find its corresponding points in the
source and target images

6. Finding Color

    For each pixels, its color is then calculated from the source
and target images' color and approximate color is displayed.

7. Program Output

    The intermediate steps are shown in the screen.  In addition, all the
intermediate images would be stored on disk with the user given file
names.  The file format is 320x200 GIF.










D. Other Consideration and Limitation

1. Color (8-bit color VS 24-bit color)

        Due to the limitation of the memory of DOS, it is difficult to
allocate sufficient memory to store the 24-bit image during program
processing.  Hence, 8-bit 256 color is chosen.


2. Performance in Time

    After integrating the whole program, system testing began.  We
found that most of the time is spent in calculating the color of each pixel.
Since at that time, each pixel is required to scan the whole color palette
and find the closest color.  That is, each pixel for each image must scan
an 256-sized array.  The performance on this is bad.

    Therefore, two methods are employed to solve this problem.
Firstly, we changed that part of code into assembly language in order to
make it behave better.  This makes the program run in a much faster.  But
it is still slow. Then, we change our finding color strategy.  A 32x32x32
hash table representing 64x64x64 RGB color is created to store the closest
color index in the palette table at the time of morphing.  In finding the
6x6x6-bits color from 5x5x5 bits color,  the least significant bit is ignored.
This approximate quite good and give a better performance in time.

4. Limitation in Transformation

    The transformation is mainly divided into two parts.  The reason
for this is due to the two different color palette for two different images
and also different triangles formed on the two images.

    For the first half of the morphing, the color palette of the source
images would be used while for the second half, the color palette of the
target images is used.  This makes the output has a visible change in the
color just before and after the switching of the color palette.

    Since the positions of the corresponding points for the source and
target images might different a lot, the triangles formed might be
completely different for two images.  Hence, we cannot just use the
displayed formed of triangles to morph images.  The method is that, for
the first half series, the triangles formed by Delaunay Triangulation of the
source images is used to morph with the corresponding triangles2 of the
target images.  Similarly, the triangles formed by Delaunay Triangulation
of the target image are used to morph with the corresponding triangles of
the source images.  Due to this reason, if the corresponding points of the
source and target images differ a lot, some intermediate steps might
appear to have some overlapping.





















Bibilography

1.      Wolberg, Georage.  Digital Image Warping.  IEEE Computer Society
Press, 1990.

2.      L. De Floriani and E. Puppo.  An On-line Algorithm for Constrained
Delaunat Triangulation.  CVGIP: Graphical Models And Image Processing,
Vol 54, No. 3, July, pp. 290-300, 1992

3.      Detlef Ruprecht and Heinrich Muller.  Image Warping with Scattered
Data Interpolation Methods.  Forschungbericht Nr. 443. 6 November 1992

4.      Valerie Hall.  Introduction to Morphing.  July, 1992.

5.      Foley, van Dam, Feiner and Hughes.  Computer Graphics: Principles
and Practice. 2nd Edition, Addision Wesley