PROJECTS AT VISL FINISHED IN 2006



Shortest Geodesics on Polyhedral Surfaces

 


by Efrat Barak
http://visl.technion.ac.il/~efrat_b/


Supervised by Emil Saucan and Eli Appleboim

 

 

URL: http://visl.technion.ac.il/projects/2006w28

 

Introduction

 

In the field of medical imaging, it is often necessary to extend a three dimensional surface to a two dimensional one, in order to enable doctors to print and examine planar medical images. For obvious medical reasons, such a transformation should not distort the data in the image, or at least maintain a very low level of distortion. This project focused on the problem of finding the best place to cut a three dimensional cylindrical surface in order to extend it into a two dimensional one, with minimal distortion. We have suggested two new algorithms for finding this place, as well as several methods of finding information about the two dimensional surface without performing the mapping. The objectives of the project were to implement the algorithms in MATLAB environment and prove their accuracy and efficiency by testing them on a cylindrical surface that was generated in a CT scan

 

Mathematical Methods

 

This study relates to triangulated surfaces, i.e. a surfaces that consist of continuous planar triangles whose vertices are points that were generated by sampling a real three dimensional surface. We suggest two new mathematical algorithms for calculating the shortest and straightest curve along which the cylinder should be cut. The curve is calculated segment after segment, where each segment stretches between two vertices of the triangulated surface. The choice of each segment is performed by mathematical theorems that ensure that this segment would yield the minimal possible deviation from the desired direction of the curve. The two algorithms differ in the ways of finding the next segment.

 

Algorithm A: Finding the Straightest Curve by Projecting Triangles

 

This algorithm is based on the following idea: For a given vertex, the possible next segments are lines from this vertex to all the vertices it’s neighborhood. In order to choose the segment that is closest to the given direction of motion, each of the neighbor vertices is projected on the plane of each of the current triangles (There are two current triangles, since the last segment of the curve is a side of two triangles). The angle between the line that is received from the projection and the direction of motion is calculated, and the segment whose angle is the smallest is chosen to be the next segment.

 

An example for the presented algorithm is shown in figure 1.

 

Figure 1: Finding the next segment of the

Straightest curve by algorithm A.

 

 

The initial vertex in figure 1 is vertex A, the current vertex is vertex B, and vertex C is one of the possible next vertices (the rest of them are marked with black dots). The two triangles that the first segments of the straightest line (i.e., segment AB) is a side of are and . BC’ is the projection of the line BC on the triangle , and  is the angle between BC’ and (the direction of motion).

 

 

Algorithm B: Finding the Geodesic by Calculating the Angles between Neighboring Vertices

 

The principle of this algorithm is: For a given vertex, the possible next segments are lines from this vertex to all the vertices it’s neighborhood. The angles between all the possible next segments to the direction of motion are calculated. The segment whose angle is the smallest of all is chosen to be the next segment of the curve. An example for this algorithm is presented in figure number 2.

 

Figure 2: Finding the next segment of the straightest curve

by algorithm B.

 

Methods for Characterization of Features of the Rectangle without Conformal Mapping

 

In spite the fact that mapping a three dimensional cylinder to a two dimensional rectangle require a non-linear transformation, several features of the rectangle could be calculated even without finding it explicitly. We propose four different methods for evaluating the module  of the rectangle, which is given by:

 

Where is the length of the longer side of the rectangle, is the length of it's shorter side, and Q is the polyhedral surface before the expansion

 

At first, several definitions should be made: Let  be the length of the straightest curve along which we cut the cylinder, and  is the average of the lengths of the upper and the lower edges of the cylinder. In addition, we define:

 

 

 

The proposed methods for evaluating  are:

 

 

 

 

 

 

 

 

 

Methods for Modeling the Process in MATLAB

 

The three dimensional surface that was examined in this project is a cylinder that consists of discrete points, which were generated in a CT scan of the large intestine of a human being (The data from the CT scan was provided by Rambam Hospital in Haifa). The discrete data was imported to MATLAB, where triangulation was performed on it in order to create a polyhedral cylinder. Figure 3 presents the sample points of the large intestine, before the triangulation.

 

Figure 3: A MATLAB presentation of the sample points

of the large intestine

 

 

The Triangulation Algorithm

 

Since there is no current MATLAB tool that can perform triangulation on a surface that is two dimensional but consists of points in a three dimensional space, the triangulation was performed in the following way: The data set was split into two parts, and each of them was projected on a plane. MATLAB functions were used to perform a two dimensional triangulation on each of the groups of samples, and then the planes were stretched back to their former shape on the cylinder. The result of this process is presented in figure 4.

 

Figure 4: The triangulated cylinder

 

 

 

 

A Method for Calculating the Lengths of the Outlines of the Cylinder The

 

In order to evaluate M(Q), the lengths of the outlines of the cylinder’s edges should be calculated. For this aim, it was necessary to find all the triangles. They were found in the following method: All the triangles of the triangulated surface were examined. Every triangle that had only two neighbors was marked as an edge triangle. Every edge triangle that had two vertices above the line  was classified as an upper edge triangle, and every edge triangle that had two vertices below the line  was marked as a lower edge triangles.

The vertices on the upper and lower outlines of the cylinder were found by examining all the vertices of the edge triangles, and taking each vertex that fulfilled one of the conditions that were just presented. The results are presented in figure 5.

 

a

b

 

Figure 5: (a) The edge triangles (b) The edge vertices

 

In order to find the lengths of the upper and lower outlines of the cylinder, the curve of each edge was found in the following way: an initial vertex was chosen. The distances from this vertex to all the vertices were calculated, and the vertex was connected to it’s closest neighbor. This was repeated for every vertex, when the connection could be done only to vertices that were not connected yet. The result is presented in figure 6.

 

a

b

Figure 6: a and b show the results of the algorithm for finding the outlines of the upper and lower edges of the cylinder, correspondingly.

 

The lengths of eac of the outlines of the cylinder was calculated by summing the distances from each vertex of the circle to it’s closest neighbor. 

 

 

Results

 

Results of the Calculations of the Straightest Curves

 

Figure 7 presents the results of simulations that were performed in MATLAB for calculating the straightest curve on the triangulated surface, according to the two algorithms.

 

 

Algorithm A (triangles projection)

Algorithm B (direct angles calculation)

 

 

 

 

 

a

 

 

 

 

 

b

 

 

 

 

 

c

Figure 7: Comparison of the results of the two algorithms for calculating the straightest curve. The figures in each row are the results of simulations in which the same starting point was used.

 

The results that were just presented show that the two algorithms succeed in calculating the straightest curves that lead from a starting point on the upper edge of the cylinder to the lower edge. In some cases the curve does not seem straight enough, but it is in fact the straightest curve that could have been calculated in that area, due to the sparse sampling. The true distance which is specified in the titles of the figures is the direct distance between the starting point and the last point of the curve.

 

The perfect match between the results of the different algorithms can also be clearly observed from figure 7. In fact, after a comparison of the results for every possible starting point, it can be stated that the algorithms yield the same results, and are therefore indeed equivalent.

 

The shortest of all of the straightest curves was chosen to be the curve along which the cylinder would be cut. This curve is presented in figure 8 (since the two algorithms yielded exactly the same results, only the result of algorithm A is presented).

 

Figure 8: The shortest geodesic that lead from the

 upper to the lower edge of the cylinder

 

 

Results of the Calculations of M(Q)

 

The parameters  and  were calculated in the following ways:  was calculated from the straightest and shortest curve that we found, and the result was . Since the polyhedral cylinder is far from a perfect geometrical cylinder,  was determined to be the average of the lengths of the outlines of the cylinder in different heights. The results was , therefore:

 

 

The results of calculating M(Q) in the different methods are:

 

 

 

 

 

 

Conclusion

 

The results of the simulations showed evidently that both of the suggested algorithms produce curves which are indeed the straightest possible curves for a given direction. Furthermore, the two algorithms yielded exactly the same results, and they were therefore proven to be equivalent. As for the methods of calculating M(Q), some of these methods gave corresponding results, while others failed to give a reasonable range of values for . Further research in this subject should attend to optimize these methods, and find the most accurate one of them.

 

Acknowledgments

 

I would like to thank my supervisors Emil Saucan and Eli Appleboim for their guidance throughout the project. I would also like to thank the Ollendorff Minerva Center which supported this project.

FULL DOCUMENTATION