H. Fuchs
Abstract
In many scientific and technical endeavors, a three-dimensional solid must be reconstructed from serial sections, either to aid in the comprehension of the object's structure or to facilitate its automatic manipulation and analysis. This paper presents a general solution to the problem of constructing a surface over a set of cross-sectional contours. This surface, to be composed of triangular tiles, is constructed by separately determining an optimal surface between each pair of consecutive contours. Determining such a surface is reduced to the problem of finding certain minimum cost cycles in a directed toroidal graph. A new fast algorithm for finding such cycles is utilized. Also developed is a closed-form expression, in terms of the number of contour points, for an upper bound on the number of operations required to execute the algorithm. An illustrated example which involves the construction of a minimum area surface describing a human head is included.
- 1 Aho, A.V., Hopcroft, J.E., and Ullman, J.O. The Analysis and Design of Computer Algorithms. Addison-Wesley, Reading, Mass., 1974. Google Scholar
Digital Library
- 2 Brooks, R.A., and DiChiro, G. Theory of image reconstruction in computed tomography. Radiology 117 (Dec. 1975), 561-572.Google ScholarCross Ref
- 3 Christofides, N. Graph Theory: An Algorithmic Approach. Academic Press, New York, 1975. Google ScholarDigital Library
- 4 Fuchs, H. The automatic sensing and analysis of threedimensional surface points from visual scenes. UTECH-CSC-76- 720, U. of Utah, Salt Lake City, Utah, Aug. 1975.Google Scholar
- 5 Harary, F. Graph Theory. Addison-Wesley, Reading, Mass., 1969.Google Scholar
- 6 Johnson, D.B. Efficient algorithms for shortest paths in sparse networks. J. ACM 24, 1 (Jan. 1977), 1-13. Google ScholarDigital Library
- 7 Kedem, Z.M., and Fuchs, H. A fast method for finding several shortest paths in certain graphs. Submitted for publication.Google Scholar
- 8 Keppel, E. Approximating complex surfaces by triangulation o{ contour lines. IBM J. Res. Develop. 19 (Jan. 1975), 2-11.Google ScholarDigital Library
- 9 Levinthal, C., and Ware, R. Three-dimensional reconstruction from serial sections. Nature 236 (March 1972), 207-210.Google ScholarCross Ref
- 10 Shantz, M.J., and McGann, G. D. Computational morphology: three-dimensional computer graphics for electron microscopy. To appear in IEEE Transactions on Biomedical Engineering.Google Scholar
- 11 Weinstein, M., and Castleman, K.R. Reconstructing 3-D specimens from 2-D section images. Proc. SPIE 26 (May 1971), 131-138.Google Scholar
Recommendations
Surfaces from contours
This paper is concerned with the problem of reconstructing the surfaces of three-dimensional objects, given a collection of planar contours representing cross-sections through the objects. This problem has important aplications in biomedical research ...
Optimal surface reconstruction from planar contours
SIGGRAPH '77: Proceedings of the 4th annual conference on Computer graphics and interactive techniques
Comments