M.Sc Thesis

M.Sc StudentSidlesky Avishay
SubjectPolygon Reconstruction from Line Cross-Sections
DepartmentDepartment of Computer Science
Supervisors PROF. Gill Barequet
PROF. Chaim Craig Gotsman
Full Thesis textFull thesis text - English Version


In the field of medical imaging, numerous applications can benefit from a three-dimensional model of human organs. Common imaging techniques, such as MRI and CT, output a dense set of parallel slices of the region of interest and as a consequence, practically all prior art addresses the problem of reconstructing a three-dimensional triangular mesh from parallel slices. Some algorithms for three-dimensional mesh reconstruction are geometric in nature and assume a preprocessing edge-detection phase that identifies contours in each slice. These contours represent the boundary between "material" and "nonmaterial" regions. Each slice may contain several contours and contour hierarchies.

In recent years, sensors capable of accurately measuring position and orientation (referred to as P&O) have been developed. These sensors, when mounted on hand-held devices, such as ultrasound transducers, provide valuable P&O information of the cross-section planes, thus expanding the scope of previous work to the reconstruction of a three-dimensional triangular mesh from arbitrary, nonparallel, slices.

An interesting, yet unexplored, problem in itself is the two-dimensional version of the problem, namely, two-dimensional polygon reconstruction from line cross-sections, which is defined as follows: Given a set of cutting lines and the intersection-segments of the interior of an unknown polygon (or possibly several distinct or nested polygons) with these lines, find the best possible polygon(s) fitting the cross-sections. A sampling condition, that guarantees sufficient sampling of the polygon edges must be formulated, otherwise an infinite number of solutions may exist. In addition, a merit function may be defined to allow comparison between solutions, if several exist, to choose the "best" one.

In this thesis we investigate the problem of two-dimensional polygon reconstruction from line cross-sections. We focus on, but do not limit ourselves to, cases where the number of cutting lines is small and seek all reconstructions that are consistent with the input and comply with a natural sampling condition. We describe an algorithm for providing these reconstructions in detail.

Our complexity analysis shows that the number of reconstructions, and hence, the run time of the algorithm, is exponential in nature, since it involves products of Catalan numbers. If we restrict the algorithm to provide a single reconstruction, the run time is quadratic in the size of the input. The related question of conditions for uniqueness of the solution remains open.