Final Project Report

Voronoi Based Polygon Contour Deformation

August to November 1999
ME751 : Computer Aided Engineering Design

Submitted by : Ankur Lahoti (96046)
Instructor : Dr. Amitabha Mukerjee

Motivation
Literature Review
Methodology
Results
Conclusion
Implementation Details
References

1. Objective :

The main objective of this project is to generate Shape Class for a sample input image of an object using its Voronoi Diagram. The main objective can be subdivided into two separate problems: generation of voronoi diagram of an image; reconstruction of the object from the voronoi description. The members of the Shape Class that are generated vary slightly with respect to the polygonal approximation of the input image.
A sample input and output is as follws :
Input : The input to the system is a J-shaped polygonal image.

Fig. 1 The input binary object image Fig. 2 The Intermediate form

Intermediate Form : The intermediate form is the voronoi skeleton of the input image. This intermediate form is only an approximation of the exact voronoi diagram of the object that I get from the first module of the system.

By comparing with the original voronoi diagram of the object we see that there is marked difference in it. The voronoi diagram from which the object is generated is different from the actual voronoi diagram of the object. This is because of the approximation in the estimation of the voronoi diagram of the original object.

Output : The ouput is a set of 6 images that are similar in shape but slightly diffrerent from the input image. The structure in red is the perturbed voronoi skeleton of the original input image.

_____________________________________________________________________________________

2. Motivation :

Shape Classes serve a large database of a kind of objects similar in shape but otherwise different. This database of slightly different shapes can be used in many fields, like pattern recognition, shape classification etc. This could even be used in illustrating shape deformation within certain constrained limits. All these varied applications of shape classes motivated me to take up this project.
Besides this extensive use of voronoi diagrams and their applicability to a variety of applications motivated me to adopt the strategy for implementing the shape class generation from a single input image.
Applications of Voronoi Diagrams
____________________________________________________________________________________

3. Literature Review :

Dr. R.L.Ogniewicz has done immense amount of work in generating voronoi diagram for any kind of object. The shape is polygonally approximated and its pruned hierarchic voronoi diagram results. Following are the references describing the approach taken by him.

Skeleton-Space: a Multiscale Shape Description Combining Region and Boundary Information, R.L.Ogniewicz, CVPR 94

This paper gives a multiscale extension to the medial axis transform by combining boundary properties derived at distinct scales and region information. The object is described by using heirarchic Voronoi skeletons, where the prominence of each skeleton component is expressed by its height. The regularization scheme is not directly dependent on either the distance of the skeleton points from the boundary nor the branch lengths. the scale-space heirarchy is carried out indirectly by adapting the boundary potential function. This paper uses a birth-set that represents a concise method to encode the topology at a vertex of the Discrete Voronoi Medial Axis (DVMA). In the final step the scale and the pruning parameters are automatically chosen. The method proposed for multi-scale medial axis generation does not involve any correspondence between distinct levels of resolution and the pruning parameters are selected automatically by tracking the prominent skeleton nodes across scales.
Results from this paper

Voronoi Skeletons : Theory and Applications, R.Ogniewicz and M.Ilg, CVPR 92

This paper presents a novel method of robust skeletonization based on the Voronoi diagram (VD) of boundary points, which is characterized by correct Euclidean metrics and inherent preservation of connectivity. The points that lie deep inside an object are less sensitive to changes among the boundary
points than are the outer parts. A set of close variants of boundary potential function are defined based on the distance of the skeleton point from the boundary. The rendering of Circularity Residual results into ridges running all around the heirarchic medial axes of the object whose height is proportional to
the level of heirarchy of that medial axis.

The Application of Voronoi Skeletons to Perceptual Groupings in Line Images ,M.Ilg and R.Ogniewicz, ICPR92

This paper discusses the amenability of the medial axis transform to processes at the intermediate level which organize low-level primitives to entities on a semantically higher level. The typical large number of boundary points in a highly irregular object lead to a large amount of skeletal information which is not always mandatory. The regularization functions drive to heirarchic clustering of the skeletal componentsto skeletal pyramid. The heirarchic characterisation basically boils down to simple thresholding. Due to the properties of preserving the proximity and adjacency infoirmation by the Voronoi
diagrams, they are a useful tool for finding relationship between different entities and manipulating with proximity problems.

Qualitative sketch optimization , Amitabha Mukerjee, Ram Bhushan Agrawal, NivedanTiwari and Nusrat Hasan, Artificial Intelligance for Engineering Design, Analysis and Manufacturing, 1997,Vol 11, Pg 311-323

A portion of the paper talks about the reconstruction of the object from the voronoi diagram and introducing perturbations into it. The paper describes the generation of shape classes from the MAT of the original shape. The 3 parameters suggested to define perturbations are : the link angle, the link length, and the node radius of the MAT of the input shape. The suggested Qualitative MAT model is robust and has already been tested in a variety of design optimization contexts.
_____________________________________________________________________________________

4. Methodology :

There are basically three subproblems in the project : Generating Voronoi Diagram, Perturbation of the Voronoi Skeleton and Object Reconstruction

Generating Voronoi Diagram from an Image : Many implementations of this problem have been done so far but the most robust and efficient of all the implementations is by Dr.R.L. Ogniewicz. The implementations offers construction of multiscale hierarchic voronoi diagram construction with different pruning strategies - chord residual, pyramidal residual, automatic residual and user-defined thresholds. This module results into the voronoi skeleton desription of the input image.
Perturbations in the Voronoi Skeleton : The paper on "Qualitative sketch Optimization" by Mukerjee et. al describes the perturbations in the voronoi diagram by changing : (a) Link Length (b) Relative Link angle (c) Radius at the Nodes. For the first two sources of perturbations can be represented as changing the absolute co-ordinates of the Nodes. Small perturbations in the co-ordinates of the nodes produce similar effect as that of relative rotation by small angles or incrementing or decrementing the link lengths by small amounts. The third kind of perturbation can directly be done by altering the radius at the voronoi skeleton nodes. The altered data is fed into the Object Reconstruction Module.
Object Reconstruction from the Voronoi Skeleton : The paper by Mukerjee et. al describes a comprehensive methodology to construct the object from the voronoi skeleton. In the MAT description the chord residual at all the end nodes of the skeleton are known as the result from the first module. By chord residual we mean that the radius of the circle touching atleast two sides of the original object boundary. With the help of this knowledge I know that the Common tangent between the two circles, constructed at the voronoi nodes as center and of radius equal to the chord residual( radius of the circle)at the respective nodes, form the part of boundary of the object. So, common tangents are constructed for pair of circles at the nodes connected by a voronoi skeleton edge. The obtained common tangents form the boundaries of the object. To obtain the vertices of the object these tangents are intersected and the vertices are obtained by pruning the common tangents. The main problem in this part is that of selection of the tangents whose intersection results into the vertex of the object. This is done by considering two adjacent voronoi edges having a common voronoi node. The 3 voronoi nodes involved in the 2 edges form a triangle. We calculate the centroid of this triangle and check in which region does it lie with respect to the voronoi edges and origin i.e the same side of the edge as that of origin or the opposite side. Now I have to consider only that point of intersection of the 4 tangents, 2 each of the voronoi edges, that intersect on the same sides of the edges as that of the centroid of the triangle formed of the edges. After finding all the intersection points, basically the vertices of the object the common tangents are pruned at these end points thereby representing the complete object. The procedure adopted is an approximate one as the assumptions state that the voronoi diagram of teh object is supposed to contain only edges and all parabolic sections are approximated as straight line segments. A major enhancement in this module can be done by strict analysis of the data obtained from the Generate Voronoi Diagram Module to construct the voronoi skeleton of the original object and then perrturbing this skeleton to produce results. The following figures give a comprehensive graphical step-by-step summary of the methodology.

    Assumptions :
            The obtained voronoi diagram does not contain any parabolic curve.
            There are no inconsistencies arising during the object reconstruction from the voronoi skeleton.

A step-by-step procedure of object reconstruction from the voronoi diagram.

In clockwise order : (a) Original Voronoi diagram of the object, (b) Perturbed Voronoi Diagram, (c) Common Tangents drawn between two adjacent voronoi edges, (c) Pruned Common tangents forming the boundary of the object and their intersections form the vertices of the object.

Module Descriptions :

1. Generate Voronoi Diagram Module :

Input : A binary image in any of the following formats : jpg, gif, tiff, Sun raster file.
Output : The output is a data file describing the voronoi skeleton of the object.
Processing : Get polygonal approximation of the object. Describe the edges by multiple equidistant points from the edge. Get voronoi description of these points.

2. Perturb the Voronoi skeleton :

Input : Description of the voronoi skeleton ouput by the first module.
Output : Perturbed Voronoi Skeleton description.
Processing : Change the absolute co-ordinates of the nodes that effect the length and angle perturbations in the voronoi diagram. Change the node radii to get altered voronoi description.

3. Object Reconstruction :

Input : Description of the voronoi diagram as resulted by the second module.
Output : The Object description.
Processing : Obtain the common tangents of the neighbouring nodes connected by a link. Intersect the common tangents to get the vertices of the object. Prune the tangents to get the object description.

_______________________________________________________________________________________

5. Results :

Some Results obtained from the First Module - Objects/Shapes and their corresponding Voronoi diagrams

Some results of the Third Module - Perturbed Objects

Above is a Tshaped Object and following is an Lshaped Object, their Voronoi Diagrams and the Perturbed Shapes.

____________________________________________________________________________________

6. Conclusion :

This project takes reasonable assumptions about the voronoi skelton that is obtained from the first module. But if implemented strictly taking into account the exact description of the voronoi skeleton and the consistency checks into the reconstructionm of the object the results would be remarkably better. It would then make a complete robust and efficient integrated module to obtain the shape classes.
_____________________________________________________________________________________

7. Implementation Details :

Implementation Details of all the three modules is as follows:

1. Generate Voronoi Diagram Module : The source code is available here. The binaries and their functionalities is as follows :

            ctran : extracts the boundaries from the binary image.
            voro   : computes voronoi diagram from the output from ctran.
            prune : prunes the medial axis description obtained from voro.

2. Perturb Voronoi Description Module: The source code for this module is embedded into the display routine for the final reconstructed object. The functions involved are :

alter_coods : alters the co-ordinates of the nodes to perturb by relative link angle and link length.
alter_radius : alters the radius of a node ( either + or - ).

3. Object Reconstruction Module: The source code is contained in the following files :

            input.c : reads the data from the data file resulting from the first module and constructs all the data structures that are required.
            tangent.c : finds the common tangents of the connected nodes.
            prune.c : intersects the tangents and identifies the vertices of the object and appropriately prunes the tangents

4. Scripts that link Module1 with the rest of the Modules : These are shell scripts that parse the output obtained from the Module1 and make it available to the rest of teh program.

runtest : Executes the Module1 on a binary image file and writes the data into input.dat data file.
getdata : This script parses the data in input.dat and filters the voronoi skeleton information from it.

README file.
______________________________________________________________________________________

8. References and Links :

Voronoi Skeletons : Theory and Applications R.L.Ogniewicz and M.Ilg , Appeared in Proc. CVPR'92, pp. 63-69, June 1992
Skeleton Space : a Multiscale Shape Description Combining Region and Boundary Information R.L.Ogniewicz, Appeared in Proc. CVPR'94, pp. 746-751, June 1994
The Application of Voronoi Skeletonsto Perceptual Grouping in Line Images M.Ilg and R.Ogniewicz, Appeared in Proc. Int. Conf. on Pattern Recognition, pp. 382-385, 1992
Hierarchic Voronoi Skeletons R.L.Ogniewicz and O.Kubler, Appeared in Proc. Int. Conf. on Pattern Recognition, 1995
Face on a Voronoi Diagram
http://www.voronoi.com
Animation showing Voronoi Diagrams through xanim