Shortest Geodesics on Polyhedral Surfaces

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.

Abstract
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.

1
Figure 1: Finding the next segment of the
Straightest curve by algorithm A.

 

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.

2
Figure 2: Finding the next segment of the straightest curve
by algorithm B.


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.

3
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.

4
Figure 4: The triangulated cylinder

 

Results of the Calculations of the Straightest Curves
Figure 5 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

5a

5a1

 

 

 

 

 

b

5b

5b1

 

 

 

 

 

c

5c

5c1

Figure 5: 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 5. 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 6 (since the two algorithms yielded exactly the same results, only the result of algorithm A is presented).

 

6
Figure 6: The shortest geodesic that lead from the
upper to the lower edge of the cylinder

 

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 M(Q). 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.