Shape Reconstruction on a Varying Mesh
|
A central class of image understanding problems is concerned with reconstructing a shape from an incomplete data set, such as fitting a surface to (partially) given contours. A new theory for solving such problems is presented. Unlike the current heuristic methods, the method used starts from fundamental principles that should be followed by any reconstruction method, regardless of its mathematical or physical implementation. A mathematical procedure which conforms to these principles is presented. One major advantage of the method is the ability to handle shapes containing both smooth and sharp parts without using thresholds. A sharp variation, such as a corner, requires a high-resolution mesh for adequate representation, while slowly varying sections can be represented with sparser mesh points. Unlike current methods, this procedure fits the surface on a varying mesh. The mesh is constructed automatically to be more dense at parts of the image that have more rapid variation. Analytical examples are given in simple cases, followed by numerical experiments.
[1] 345R. E. Barnhill and R. F. Riesenfeld, Eds.,Computer Aided Geometric Design. New York: Academic, 1974.
[2] H. G. Barrow and J. M. Tenenbaum, "Interpreting line drawings as three-dimensional surfaces,"Artificial Intell., vol. 17, pp. 75-117, 1981.
[3] A. Blake and A. Zisserman,Visual Reconstruction. Cambridge, MA: MIT Press, 1987.
[4] M. Brady and A. Yuille, "An extremum principle for shape from contour,"IEEE Trans. Pattern Anal. Machine Intell., vol. PAMI-6, 1984.
[5] M. Brady and H. Asada, "Smoothed local symmetries and their implementation," MIT A.I. Memo 757, Feb. 1984.
[6] M. Brady, J. Ponce, A. Yuille, and H. Asada, "Describing surfaces," inProc. 2nd. Symp. Robotics Res., Kyoto, Japan, 1984.
[7] R. Courant and D. Hilbert,Methods of Mathematical Physics, vol. I, London: Interscience, 1953.
[8] L. Davis, L. Janos, and S. Dunn, "Efficient recovery of shape from texture," Comput. Vision Lab., Univ. Maryland, Tech. Rep. TR- 1133, 1982.
[9] C. DeBoor,A Practical Guide to Splines. New York: Springer-Verlag, 1978.
[10] M. Do Carmo,Differential Geometry of Curves and Surfaces. Englewood Cliffs, NJ: Prentice-Hall, 1976.
[11] W. E. L. Grimson, "The implicit constraint of the primal sketch," MIT AI Memo 663, 1981.
[12] B. K. P. Horn, "The curve of least energy,"ACM Trans. Math. Software, vol. 9, pp. 441-460, 1983.
[13] M. Kass, A. Witkin, and D. Terzopoulos, "Snakes: Active contour models,"Int. J. Comput. Vision, 1987.
[14] D. Marr,Vision. San Francisco, CA: Freeman, 1982.
[15] T. Pavlidis,Structural Pattern Recognition. New York: Springer-Verlag, 1977.
[16] T. Poggio, inProc. Image Understanding Workshop, Los Angeles, CA, 1987.
[17] A. Rosenfeld and A. Kak,Digital Picture Processing, New York: Academic, 1976.
[18] K. A. Stevens, "The visual interpretation of surface contours,"Artificial Intell., vol. 17, pp. 47-73, 1981.
[19] G. Strang and G. J. Fix,An Analysis of the Finite Element Method. Englewood Cliffs, NJ: Prentice-Hall, 1973.
[20] D. Terzopoulos, "Multi-level reconstruction of visual surfaces: Variational principles and finite element representations," AI Memo 671, MIT, Apr. 1982.
[21] D. Terzopoulos, "Computing visible surface reconstruction," Memo 800, Artificial Intell. Lab., Mass. Inst. Technol., Cambridge, MA, 1985.
[22] I. Weiss, "3-D shape representation by contours,"Computer Vision, Graphics and Image Processing, no. 41, pp. 80-100, 1988.
[23] I. Weiss, "Curve fitting with optimal mesh point placement," Comput. Vision Lab., Univ. Maryland, Tech. Rep. CAR-TR-22, 1986.
[24] A. Witkin, "Recovering surface shape and orientation from texture,"Artificial Intell., vol. 17, pp. 17-45, 1981.
[25] D. Young and R. Gregory,A Survey of Numerical Mathematics, vols. 1 and 2. Reading, MA: Addison-Wesley, 1973.
Index Terms:
picture processing; pattern recognition; shape reconstruction; image understanding; high-resolution mesh; varying mesh; pattern recognition; picture processing
Citation:
I. Weiss, "Shape Reconstruction on a Varying Mesh," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 12, no. 4, pp. 345-362, Apr. 1990, doi:10.1109/34.50621
PURCHASE ARTICLE: $19
IEEE Xplore Subscribers
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb