
PROJECTS AT VISL FINISHED IN 2006 


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