On Three-Dimensional Surface Reconstruction Methods
|
A survey is presented of some of the surface reconstruction methods that can be found in the literature; the focus is on a small, recent, and important subset of the published reconstruction techniques. The techniques are classified based on the surface representation used, implicit versus explicit functions. A study is made of the important aspects of the surface reconstruction techniques. One aspect is the viewpoint invariance of the methods. This is an important property if object recognition is the ultimate objective. The robustness of the various methods is examined. It is determined whether the parameter estimates are biased, and the sensitivity to obscuration is addressed. The latter two aspects are particularly important for fitting functions in the implicit form. A detailed description is given of a parametric reconstruction method for three-dimensional object surfaces that involves numeric grid generation techniques and variational principle formulations. This technique is invariant to rigid motion in dimensional space.
[1] 1G. J. Agin and T. O. Binford, "Computer description of curved objects," inProc. 3rd Int. Joint Conf. Artificial Intell., Aug. 1976, pp. 629-640.
[2] R. Bajcsy and C. Broit, "Matching of deformed images," inProc. 6th Int. Joint Conf. Pattern Recognition, 1982, pp. 351-353.
[3] R. Bajcsy and F. Solina, "Three dimensional object representation revisited," inProc. IEEE 1st Int. Conf. Comp. vision, June 1987, pp. 231-240.
[4] A. H. Barr, "Superquadrics and angle-preserving transformations,"IEEE Comput. Graphics and Applications, pp. 11-23, Jan. 1981.
[5] H. G. Barrow and J. M. Tenenbaum, "Computational vision,"Proc. IEEE, vol. 69, no. 5, pp. 572-595, May 1981.
[6] B.A. Barsky, "The beta-spline: A local representation based on shape parameters and fundamental geometric measures," Ph.D. dissertation, Univ. of Utah, Salt Lake City, Dec. 1981.
[7] P. J. Besl and R. C. Jain, "Three-dimensional object recognition,"ACM Comput. Surveys, vol. 17, no. 1, pp. 75-145, Mar. 1985.
[8] P. J. Besl, J. B. Birch, and L. T. Watson, "Robust window operations," inProc. IEEE 2nd Int. Conf. Comp. vision, Dec. 1988, pp. 591-600.
[9] T.O. Binford, "Visual perception by computer," presented at the IEEE Conf. on Systems and Control Dec. 1971.
[10] A. Blake, "Reconstructing a visible surface," inProc. Nat. Conf. Artificial Intell., Aug. 1984, pp. 23-26.
[11] A. Blake and A. Zisserman, "Invariant surface reconstruction using weak continuity constraints," inProc. IEEE Conf. Comp. Vision and Pattern Recognition, July 1985, pp. 62-67.
[12] A. Blake and A. Zisserman,Visual Reconstruction. Cambridge, MA: MIT Press, 1987.
[13] R. M. Bolle and D.B. Cooper, "Bayesian recognition of local 3-D shape by approximating image intensity functions with quadric polynomials,"IEEE Trans. Pattern Anal. Machine Intell., vol. PAMI-6, pp. 418-429, July 1984.
[14] R. M. Bolle and D.B. Cooper, "On optimally combining pieces of information, with application to estimating 3-D complex-object position from range data,"IEEE Trans. Pattern Anal. Machine Intell., vol. PAMI-8, pp. 619-638, Sept. 1986.
[15] R. M. Bolle, R. Kjeldsen, and D. Sabbah, "Primitive shape extraction from depth maps," inProc. IEEE Workshop Comp. vision, Nov.-Dec. 1987, pp. 324-326.
[16] R. M. Bolle, A. Califano, R. Kjeldsen, and R. W. Taylor, "Visual recognition using concurrent and layered parameter networks," IBM Tech. Rep., Nov. 1988; IEEE Conf. Computer Vision and Pattern Recognition, 1989.
[17] F. L. Bookstein, "Fitting conic sections to scattered data,"Comp. vision, Graphics, and Image Processing, vol. 9, pp. 56-71, 1979.
[18] T. E. Boult and J. R. Kender, "Visual surface reconstruction using sparse depth data," inProc. IEEE Conf. Comp. vision and Pattern Recognition, June 1986, pp. 68-76.
[19] T. E. Boult and A. D. Gross, "Recovery of superquadrics from 3-D information," inProc. SPIE Intell. Robots and Comp. Vision, Nov. 1987, pp. 358-365.
[20] M. Brady and A. Yuille, "An extremum principle for shape from contour,"IEEE Trans. Pattern Anal. Machine Intell., vol. PAMI-6, no. 3, pp. 288-301, 1984.
[21] A. Brandt, "Multi-level adaptive solutions to boundary-value problems,"Math. Computing, vol. 31, pp. 333-390, 1977.
[22] B. Cernuschi-Frías, "Orientation and location parameter estimation of quadric surfaces in 3-D from a sequence of images," Ph.D. dissertation, Brown Univ., Div. of Engineering, Providence, RI, May 1984.
[23] D. J. Choi and J. R. Kender, "Solving the depth interpolation problem on a parallel architecture with a multigrid approach," inProc. IEEE Conf. Comput. Vision and Pattern Recognition, June 1988, pp. 189-194.
[24] A. K. Cline, "Curve fitting using splines under tension," Nat. Center for Atmospheric Res., Tech. Rep. no. 3, 1973.
[25] A. K. Cline, "Reproducing positivity, monotonicity, and convexity in curves with splines under tension," Univ. of Texas at Austin, Center for Numerical Analysis, CNA-169, 1980.
[26] A. K. Cline, "Surface smoothing by splines under tension," Univ. of Texas at Austin, Center for Numerical Analysis, CNA-170, 1981.
[27] D. B. Cooper and N. Yalabik, "On the computational cost of approximating and recognizing noise-perturbed straight lines and quadratic arcs in the plane,"IEEE Trans. Comp., vol. C-25, no. 10, pp. 1020-1032, Oct. 1976.
[28] R. Courant and D. Hilbert,Methods of Mathematical Physics, vol. 2. New York: Interscience, 1962.
[29] C. De Boor,A Practical Guide to Splines. New York: Springer-Verlag, 1978.
[30] M.P. DoCarmo,Differential Geometry of Curves and Surfaces. Englewood Cliffs, NJ: Prentice-Hall, 1976.
[31] A. Dresden,Solid Analytical Geometry and Determinants. New York: Dover, 1964.
[32] J. Duchon, "Interpolation de functions de deux variables suivant le principe de la flexion des plaques minces,"Rev. Francaise d'Automatique Informatique et Recherche Operationelle, pp. 5-12, Dec. 1976.
[33] G. Farin, Ed.,Geometric Modeling: Algorithms and New Trends. Philadelphia: Soc. for Industrial and Applied Math., 1987.
[34] O.D. Faugeras, M. Herbert, and E. Pauchon, "Segmentation of planar and quadratic patches from range data," inProc. IEEE Conf. Pattern Recognition and Image Processing, 1983.
[35] M. Gardiner, "The superellipse: A curve that lies between the ellipse and the rectangle,"Sci. Amer., Sept. 1965.
[36] S. Geman and D. Geman, "Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images,"IEEE Trans. Pattern Anal. Machine Intell., vol. PAMI-6, no. 2, pp. 721-741, Nov. 1984.
[37] R.N. Goldman, "The role of surfaces in solid modeling," inGeometric Modeling: Algorithms and New Trends, G. E. Farin, Ed. Philadelphia: Society for Industrial and Applied Math., 1987, pp. 69-90.
[38] W.E.L. Grimson, "A computer implementation of a theory of human stereo vision,"Phil. Trans. Roy. Soc. London B, vol. 298, pp. 395-427, 1981.
[39] W.E.L. Grimson, "An implementation of computational theory for visual surface interpolation,"Comput. Vision, Graphics, Image Processing, vol. 6, no. 22, pp. 39-69, 1983.
[40] A. D. Gross and T. E. Boult, "Error of fit measures for recovering parametric solids," inProc. 2nd Int. Conf. Comput. vision, Dec. 1988, pp. 690-694.
[41] D. G. Hakala, R. C. Hillyard, P. J. Malraison, and B.E. Nourse, "Natural quadrics in mechanical design," inAutofact West Proc., Vol. I, CAD/CAM VIII, Nov. 1980, pp. 363-378.
[42] W. Hackbusch and U. Trottenberg,Multigrid Methods. New York: Springer-Verlag, 1981.
[43] E.L. Hall, J.B.K. Tio, C.A. McPherson, and F.A. Sadjadi, "Measuring curved surfaces for robot vision,"IEEE Computer, pp. 42-54, Dec. 1982.
[44] J.G. Harris, "The coupled depth/slope approach to surface reconstruction," M.S. thesis, Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, Cambridge, 1986.
[45] E. Hildreth, "Computation underlying the measurement of visual motion,"Artificial Intell., vol. 23, pp. 309-354, 1984.
[46] B. K. P. Horn, "Obtaining shape from shading information," inThe Psychology of Computer Vision, P.H. Winston, Ed. New York: McGraw-Hill, 1975.
[47] B. K. P. Horn and M. J. Brooks, "The variational approach to shape from shading,"Comp. vision, Graphics, and Image Processing, vol. 33, no. 2, pp. 174-208, Feb. 1986.
[48] P. Huber,Robust Statistics. New York: Wiley, 1981.
[49] K. Ikeuchi, "Recognition of 3-D objects using the extended Gaussian image," inProc. Int. Joint Conf. on Artificial Intell., Aug. 1981, pp. 595-600.
[50] K. Ikeuchi and B. K. P. Horn, "Numerical shape from shading and occluding boundaries,"Artificial Intell., vol. 17, pp. 141-184, 1981.
[51] J. Y. Jou and A. C. Bovik, "Improving visible-surface reconstruction," inProc. IEEE Conf. Computer vision and Pattern Recognition, June 1988, pp. 138-143.
[52] J. R. Kender, D. Lee, and T. Boult, "Information based complexity applied to optimal recovery of the 2 1/2-D sketch," inProc. IEEE Workshop Comp. vision: Representation and Control, Oct. 1985, pp. 157-167.
[53] S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, "Optimization by simulated annealing,"Science, vol. 220, pp. 671-680, 1983.
[54] J. Koenderink and A. van Doorn, "The internal representation of solid shape with respect to vision,"Biological Cybernetics, vol. 32, pp. 211-216, 1979.
[55] J. L. Lagrange,Mécanique analitique, chez la veuve Desaint. Paris: Libraire, Rue de Foire St Jacques, 1788.
[56] C. L. Lawson, "Software for C1surface interpolation," inMathematical Software III, J. R. Rice, Ed. New York: Academic, 1977, pp. 161-194.
[57] D. Marr and T. Poggio, "A theory of human stereo vision,"Proc. Roy. Soc. London B, vol. 204, pp. 301-328, 1979.
[58] D. Marr and H. K. Nishihara, "Representation and recognition of the spatial organization of three dimensional structure,"Proc. Roy. Soc. London B, vol. 200, pp. 269-294, 1978.
[59] D. Marr,Vision. New York: W. H. Freeman, 1982, pp. 295-328.
[60] J. L. Marroquin, "Probabilistic solutions to inverse problems," Ph.D. dissertation, Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, Cambridge, Sept. 1985.
[61] D. Meagher, "Oct-tree encoding: A new technique for representation, manipulation and display of arbitrary 3-D obiects," Tech. Rep. IPL-TR-80-111, Rensselaer Polytech. Institute, Troy, NY, Oct. 1980.
[62] J. Meinguet, "Multivariate interpolation at arbitrary points made simple,"J. Applied Math. and Physics, vol. 30, pp. 292-304, 1979.
[63] M. Minsky, "A framework for representing knowledge," in The Psychology of Computer Vision, P.H. Winston, Ed. New York McGraw-Hill, 1975, pp. 211-277.
[64] H. H. Nagel, "Constraints for the estimation of displacement vector fields from image sequences," inProc. Int. Joint Conf. on Artificial Intell., Aug. 1983, pp. 945-951.
[65] K. A. Narayanan, D. P. O'Leary, and A. Rosenfeld, "Image smoothing and segmentation by cost minimization,"IEEE Tyans. Syst. Man, Cybernetics, vol. SMC-12, pp. 91-96, 1982.
[66] R. Nevatia,Machine Perception. Englewood Cliffs: Prentice-Hall, Inc., 1982.
[67] A. P. Pentland, "Recognition by parts," inProc. IEEE 1st Int. Conf. on Comp. Vision, June 1987, pp. 612-620.
[68] A. P. Pentland, "Automatic extraction of deformable part models," MIT Media Lab, Vision Sciences Group, Tech. Rep. 104, Cambridge, MA, July 1988.
[69] D.T. Pilcher, "Smooth approximation of parametric curves and surfaces," Ph.D. dissertation, Univ. of Utah, Salt Lake City, Aug. 1973.
[70] J. Ponce and D. Chelberg, "Finding the limbs and cusps of generalized cylinders,"Int. J. Comp. Vision, vol. 1, no. 3, 1987.
[71] A. Ralston and P. Rabinowitz,A First Course in Numerical Analysis. New York: McGraw-Hill, 1987.
[72] K. Rao and R. Nevatia, "Generalized cone descriptions from sparse 3-D data," inProc. IEEE Conf. Comp. Vision and Pattern Recognition, June 1986, pp. 256-263.
[73] C.H. Reinsch, "Smoothing by splines under tension,"Numer. Math., vol. 10, pp. 177-183, 1967.
[74] A. A. Requicha, "Representations for rigid solids: Theory, methods, and systems,"Comput. Surveys, vol. 12, no. 4, pp. 437-465, 1980.
[75] L. E. Scales,Introduction to Non-linear Optimization. New York: Springer-Verlag, 1985.
[76] S. A. Shafer,Shadows and Silhouettes in Computer Vision. Boston: Kluwer, 1985.
[77] L. L. Schumaker, "Fitting surfaces to scattered data," inApproximation Theory II, G. G. Lorentz, C. K. Chui, and L. L. Schumaker, Eds. New York: Academic, 1976, pp. 203-267.
[78] F. Solina, "Shape recovery and segmentation with deformable part models," Ph.D. dissertation, Univ. Pennsylvania, 1987.
[79] R. S. Szeliski, "Bayesian modeling of uncertainty in low-level vision," Ph.D. dissertation, Carnegie-Mellon Univ., Computer Science Dept., Pittsburgh, PA, Aug. 1988.
[80] G. Taubin, "Algebraic nonplanar curve and surface estimation in 3-space with application to position estimation," Brown University, Div. of Engin., LEMS-43, Providence, RI; also IBM T. J. Watson Res. Center, RC 13873, Yorktown Heights, NY, Feb. 1988.
[81] D. Terzopoulos, "Multilevel computational processes for visible surface reconstruction,"Comput. Vision, Graphics and Image Processing, vol. 24, pp. 52-96, 1983.
[82] D. Terzopoulos, "Multiresolution computation of visible-surface representations," Ph.D. dissertation, Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, Cambridge, 1984.
[83] D. Terzopoulos, "Regularization of inverse visual problems involving discontinuities,"IEEE Trans. Pattern Anal. Machine Intell., vol. PAMI-8, no. 4, pp. 413-424, July 1986.
[84] D. Terzopoulos, "The computation of visible-surface representations,"IEEE Trans. Pattern Anal. Machine Intell., vol. 10, no. 4, pp. 417-438, July 1988.
[85] D. Terzopoulos, A. Witkin, and M. Kass, "Constraints on deformable models: Recovering 3D shape and nonrigid motion,"Artificial Intell., vol. 36, pp. 91-123, 1988.
[86] J. F. Thompson, Z. U. A. Warsi, and C. W. Mastin,Numerical Grid Generation: Foundations and Applications. New York: Elsevier, 1985.
[87] J. W. Tukey, "A survey of sampling from contaminated distribution," inContributions to Probability and Statistics, I. Olkin, Ed. Stanford, CA: Stanford Univ. Press, 1960.
[88] J. W. Tukey, The future of data analysis,"Ann. Math. Statist., vol. 33, pp. 1-67, 1962.
[89] B.C. Vemuri, A. Mitiche, and J.K. Aggarwal, "Curvature-based representation of objects from range data,"Image and Vision Comput., vol. 4, no. 2, pp. 107-114, May 1986.
[90] B.C. Vemuri, "Representation and recognition of objects from dense range maps," Ph.D. dissertation, Univ. of Texas at Austin, Dept. of Electrical and Computer Engineering, Austin, 1987.
[91] D. M. Young,Iterative Solutions of Large Linear Systems. New York: Academic, 1971.
Index Terms:
rigid motion invariant; three-dimensional surface reconstruction methods; surface representation; explicit functions; viewpoint invariance; object recognition; robustness; parameter estimates; sensitivity; obscuration; parametric reconstruction method; three-dimensional object surfaces; numeric grid generation techniques; variational principle formulations; computer vision; computerised picture processing; invariance; parameter estimation; variational techniques
Citation:
R.M. Bolle, B.C. Vemuri, "On Three-Dimensional Surface Reconstruction Methods," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 13, no. 1, pp. 1-13, Jan. 1991, doi:10.1109/34.67626
PURCHASE ARTICLE: $19
IEEE Xplore Subscribers
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb