Piecewise-linear interpolation between polygonal slices

ABSTRACT

In this paper we present a new technique for piecewise-linear surface reconstruction from a series of parallel polygonal cross-sections. This is an important problem in medical imaging, surface reconstruction from topographic data, and other applications. We reduce the problem, as in most previous works, to a series of problems of piecewise-linear interpolation between each pair of successive slices. Our algorithm uses a partial curve matching technique for matching parts of the contours, an optimal triangulation of 3-D polygons for resolving the unmatched parts, and a minimum spanning tree heuristic for interpolating between non simply connected regions. Unlike previous attempts at solving this problem, our algorithm seems to handle successfully any kind of data. It allows multiple contours in each slice, with any hierarchy of contour nesting, and avoids the introduction of counter-intuitive bridges between contours, proposed in some earlier papers to handle interpolation between multiply connected regions. Experimental results on various complex examples, involving actual medical imaging data, are presented, and show the good and robust performance of our algorithm.

REFERENCES

• 1: G. BAREQUET AND M. SHARIR, Filling gaps in the boundary of a polyhedron, Technical Report 277/93, Department of Computer Science, Tel Aviv University, 1993.
• 2: S. B^TmTZ}<Y, H.I. PmCE, P.N. COOK, L.T. COOK AND S.J. DWYER III, Three-dimensional computer reconstruction from surface contours for head CT examinations, J. of Computer Assisted Tomography, 5 (1981), 60-67.
• 3: Jean-Daniel Boissonnat, Shape reconstruction from planar cross sections, Computer Vision, Graphics, and Image Processing, v.44 n.1, p.1-29, Oct. 1988 [doi>10.1016/S0734-189X(88)80028-8]
• 4: J.D. BOISSONNAT AND B. GEIGER, Three dimensional reconstruction of complex shapes based on the Delaunay triangulation, Technical Report 1697, Inria-Sophia Antipolis, 1992.
• 5: H. N. Christiansen , T. W. Sederberg, Conversion of complex contour line definitions into polygonal element mosaics, ACM SIGGRAPH Computer Graphics, v.12 n.3, p.187-192, August 1978
• 6: H.E. CLINE, W.E. LOR~NSEN, S. LUDKE, C.R. CRAWFORD AND B.C. TEETER, Two algorithms for the three-dimensional reconstruction of tomograms, Medical Physics, 15 (1988), 320- 327.
• 7: L.T. COOK, P.N. COOK, K.R. L~.E, S. BATNITZKY, B.Y.S. WONG, S.L. FRITZ, J. OPHIR, S.J. DWYER IiI, L.R. BIGONGIARI AND A.W. T~MPELTON, An algorithm for volume estimation based on polyhedral approximation, IEEE Transactions on B~omedical Engineering, 27 (1980), 493-500.
• 8: A. B. Ekoule , F. C. Peyrin , C. L. Odet, A triangulation algorithm from arbitrary shaped multiple planar contours, ACM Transactions on Graphics (TOG), v.10 n.2, p.182-199, April 1991 [doi>10.1145/108360.108363]
• 9: H. Fuchs , Z. M. Kedem , S. P. Uselton, Optimal surface reconstruction from planar contours, Communications of the ACM, v.20 n.10, p.693-702, Oct. 1977 [doi>10.1145/359842.359846]
• 10: S. Ganapathy , T. G. Dennehy, A new general triangulation method for planar contours, ACM SIGGRAPH Computer Graphics, v.16 n.3, p.69-75, July 1982
• 11: B. GEIGER, Construction et utilisation des mod~les d'organes en rue de l'assistance au dia~_ostic et aux interventions chinrrgicals, Ph.D. Dissertation, E'Ecole des Mines de Paris, 1993.
• 12: C. GITLIN, Jo O'RouRI<E AND V. SUBRAlVfANIAN, On reconstructing polyhedra from parallel slices, Technical Report 025, Department of Computer Science, Smith College, Northampton, MA, 1993.
• 13: Leonidas Guibas , Jorge Stolfi, Primitives for the manipulation of general subdivisions and the computation of Voronoi, ACM Transactions on Graphics (TOG), v.4 n.2, p.74-123, April 1985 [doi>10.1145/282918.282923]
• 14: H. HAGEN, H. MULLER AND G.M. NIELSON, Focus on Scientific Visuahzatzon, Springer Verlag, 1993.
• 15: J. HONG AND H.J. WOLFSON, An improved model-based matchingmethod using footprints, Proc. 9th Int. Conf. on Pattern ~Flecogn~tion, 1988, 72-78.
• 16: Alan Kalvin , Edith Schonberg , Jacob T. Schwartz , Micha Sharir, Two-dimensional, model-based, boundary matching using footprints, International Journal of Robotics Research, v.5 n.4, p.38-55, Winter, 1987 [doi>10.1177/027836498600500403]
• 17: N. Kehtarnavaz , R. J. P. de Figueiredo, A framework for surface reconstruction from 3D contours, Computer Vision, Graphics, and Image Processing, v.42 n.1, p.32-47, April, 1988 [doi>10.1016/0734-189X(88)90141-7]
• 18: N. Ketarnavaz , L. R. Simar , R. J.P. Figueiredo, A syntactic/semantic technique for surface reconstruction from cross-sectional contours, Computer Vision, Graphics, and Image Processing, v.42 n.3, p.399-409, June, 1988 [doi>10.1016/S0734-189X(88)80048-3]
• 19: E. KEPPEL, Approximating complex surfaces by triangulation of contour lines, IBM Journal o/Research and Development, 19 (1975), 2-11.
• 20: E. KISHON, T. HASTm AND H. WOLFSON, 3-D curve matching using splines, J. o/Robotic systems, 8 (1991), 723-743
• 21: G.T. KLINCSI~K, Minimal triangulations of polygonal domains, Annals of Discrete Mathematics, 9 (1980), 121-123.
• 22: D. MEYERS, S. SKINNER AND K. SLOAN, Surfaces from contours: the correspondence and branching problems, Proc. Graphics Inter. face '91, 1991, 246-254.
• 23: L.L. SCHUMAKER, Reconstructing 3D objects from crosssections, in: W. Dahmen, M. Gasca and C.A. Micchelli (eds.), Computation of Cur~es and Surfaces, Kluwer Academic Pubfishers, 1989, 275-309.
• 24: Jacob T. Schwartz , Micha Sharir, Identification of partially obscured objects in two and three dimensions by matching noisy characteristic, International Journal of Robotics Research, v.6 n.2, p.29-44, Summer 1987 [doi>10.1177/027836498700600203]
• 25: Michael Shantz, Surface definition for branching, contour-defined objects, ACM SIGGRAPH Computer Graphics, v.15 n.2, July 1981 [doi>10.1145/988420.988426]
• 26: K.R. SLOAN AND L.M. HREOHANY~<, Surface reconstruction from sparse data, Proc. IEEE Conj. on Pattern Recognition and Image Processzng, 1981, 45-48.
• 27: Kenneth R. Sloan, Jr. , James Painter, From contours to surfaces: testbed and initial results, Proceedings of the SIGCHI/GI conference on Human factors in computing systems and graphics interface, p.115-120, April 05-09, 1987, Toronto, Ontario, Canada
• 28: Kenneth R. Sloan , James Painter, Pessimal Guesses may be Optimal: A Counterintuitive Search Result, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.10 n.6, p.949-955, November 1988 [doi>10.1109/34.9117]
• 29: Y F Wang , J K Aggarwal, Surface reconstruction and representation of 3-D scenes, Pattern Recognition, v.19 n.3, p.197-207, 1986 [doi>10.1016/0031-3203(86)90010-5]
• 30: Emo Welzl , Barbara Wolfers, Surface Reconstruction Between Simple Polygons via Angle Criteria, Proceedings of the First Annual European Symposium on Algorithms, p.397-408, September 30-October 02, 1993
• 31: H. J. Wolfson, On curve matching, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.12 n.5, p.483-489, May 1990 [doi>10.1109/34.55108]
• 32: M.J. ZYDA, A.R. JONES AND P.G. HOGAN, Surface construction from planar contours, Computers and Graphics, 11 (1987), 393-408.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.1 Interpolation
          Subjects: Spline and piecewise polynomial interpolation
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

General Terms:
Algorithms, Experimentation, Measurement, Performance

Keywords:
branching surfaces, curve matching, dynamic programming, geometric hashing, polyhedra, slice interpolation, surface fitting, surface reconstruction, tiling, triangulation