| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
CAD-Based Computer Vision: From CAD Models to Relational Graphs
February 1991 (vol. 13 no. 2)
pp. 114-132
The topic of model-building for 3-D objects is examined. Most 3-D object recognition systems construct models either manually or by training. Neither approach has been very satisfactory, particularly in designing object recognition systems which can handle a large number of objects. Recent interest in integrating mechanical CAD systems and vision systems has led to a third type of model building for vision: adaptation of preexisting CAD models of objects for recognition. If a solid model of an object to be recognized is already available in a manufacturing database, then it should be possible to infer automatically a model appropriate for vision tasks from the manufacturing model. Such a system has been developed. It uses 3-D object descriptions created on a commercial CAD system and expressed in both the industry-standard IGES form and a polyhedral approximation and performs geometric inferencing to obtain a relational graph representation of the object which can be stored in a database of models for object recognition. Relational graph models contain both view-independent information extracted from the IGES description and view-dependent information (patch areas) extracted from synthetic views of the object. It is argued that such a system is needed to efficiently create a large database (more than 100 objects) of 3-D models to evaluate matching strategies.
[1] 114G. Agin and T. Binford, "Computer description of curved objects," inProc. 3rd Int. Joint Conf. Artificial Intelligence, 1973, pp. 1113-1115.[2] D. H. Ballard and C. M. Brown,Computer Vision. Englewood Cliffs, NJ: Prentice-Hall, 1982.[3] R. Bergevin and M. D. Levine, "Generic object recognition: Building coarse 3D descriptions from line drawings," inProc. IEEE Workshop Interpretation of 3D Scenes, Nov. 1989, pp. 68-74.[4] P. J. Besl, "Active optical range imaging sensors," inAdvances in Machine Vision: Architectures and Applications, J. L. C. Sanz, Ed. New York: Springer-Verlag, 1988.[5] P. J. Besl, "Geometric modeling and computer vision,"Proc. IEEE, vol. 76, no. 8, pp. 936-958, Aug. 1988.[6] P. J. Besl and R. C. Jain, "Three-dimensional object recognition,"ACM Comput. Surveys, vol. 17, no. 1, pp. 75-145, Mar. 1985.[7] B. Bhanu and C.-C. Ho, "CAD-based 3D object representation for robot vision,"Computer, vol. 20, pp. 19-35, Aug. 1987.[8] B. Bhanu, Ed., "Guest Editor's introduction,"(Special Issue on CAD-Based Robot Vision) Computer, Aug. 1987.[9] I. Biederman, "Recognition-by-components: A theory of human image understanding,"Psychol. Rev., vol. 94, no. 2, pp. 115-147, 1987.[10] R. C. Bolles and P. Horaud, "3DPO: A three dimensional part orientation svstem,"Int. J. Robotics Res., vol. 5, no. 3, Fall 1986, pp. 3-26.[11] J. Brady, N. Nandhakumar, and J. Aggarwal, "Recent progress in the recognition of obiects from range data," inProc. 9th Int. Conf. Pattern Recognition, Nov. 1988, pp. 85-92.[12] R.A. Brooks,Model-Based Computer Vision. Ann Arbor, MI: UMI Research Press, 1984.[13] C. M. Brown, "Some mathematical and representational aspects of solid modeling,"IEEE Trans. Pattern Anal. Machine Intell., vol. PAMI-3, no. 4, pp. 444-453, July 1981.[14] J. B. Burns and L. J. Kitchen, "Rapid object recognition from a large model base using prediction hierarchies," inProc. 1988 DARPA Image Understanding Workshop, 1988, pp. 711-719.[15] O.I. Camps, L.G. Shapiro, and R.M. Haralick, "PREMIO: The use of prediction in a CAD-model-based vision system," Dep. Elec. Eng., Univ. Washington, Tech. Rep. EE-ISL-89-01, 1989.[16] C. H. Chen and A. C. Kak, "A robot vision system for recognizing 3-D objects in low-order polynomial time,"IEEE Trans. Syst., Man Cybern., vol. 19, no. 6, pp. 1535-1563, Nov./Dec. 1989.[17] S.-W. Chen, "3D representation and recognition using object wings," Ph.D. dissertation, Dep. Comput. Sci., Michigan State Univ., 1989.[18] C.H. Chien and J. K. Aggarwal, "Volume/surface octrees for the representation of three-dimensional objects,"Comput. Vision, Graphics, Image Processing, vol. 36, pp. 100-113, 1986.[19] C.H. Chien, Y. B. Sim, and J. K. Aggarwal, "Construction of volume-surface octree from range data," inProc. 1988 IEEE Comput. Soc. Conf. Computer Vision and Pattern Recognition, June 1988, pp. 254-260.[20] R.T. Chin and C. R. Dyer, "Model-based recognition in robot vision,"ACM Comput. Surveys, vol. 18, no. 1, pp. 67-108, Mar. 1986.[21] J. H. Connell and M. Brady, "Generating and generalizing models of visual objects,"Artificial Intell., vol. 31, pp. 159-183, 1987.[22] C. Connolly, J. Mundy, J. Stenstrom, and D. Thompson, "Matching from 3-D range models into 2-D intensity scenes," inProc. First Int. Conf. Computer vision, June 1987, pp. 65-72.[23] R. deFigueriedo, "A framework for automation of 3D machine vision,"TI Tech. J., 1987, pp. 62-72.[24] D. Eggert and K. Bowyer, "Computing the orthographic projection aspect graph of solids of revolution," inProc. IEEE Workshop Interpretation of 3D Scenes, Nov. 1989, pp. 102-108.[25] J. R. Engelbrecht and F. M. Wahl, "Polyhedral object recognition using Hough-space features,"Pattern Recog., vol. 21, no. 6, pp. 155-168, 1988.[26] T. J. Fan, G. Medioni, and R. Nevatia, "Recognizing 3-D objects using surface descriptions," presented at the 2nd Int. Conf. Computer Vision, Dec. 5-8, 1988.[27] T. Fan, G. Medioni, and R. Nevatia, "Recognizing 3-D objects using surface descriptions,"IEEE Trans. Pattern Anal. Machine Intell., vol. 11, no. 11, pp. 1140-1157, 1989.[28] I. Faux and M. Pratt,Computational Geometry for Design and Manufacture. Ellis Horwood, 1979.[29] P. J. Flynn, "CAD-based computer vision: Modeling and recognition strategies," Ph.D. dissertation, Dep. Comput. Sci., Michigan State Univ., 1990.[30] P. J. Flynn and A. K. Jain, "Surface classification: Hypothesis testing and parameter estimation," inProc. 1988 IEEE Comput. Soc. Conf. Computer Vision and Pattern Recognition, June 1988, pp. 261-267.[31] P. J. Flynn and A. K. Jain, "CAD-based computer vision: From CAD models to relational graphs," inProc. 1989 IEEE Int. Conf. Systems, Man, Cybernetics, Nov. 1989, pp. 162-167.[32] Z. Gigus and J. Malik, "Computing the aspect graph for line drawings of polyhedral objects,"IEEE Trans. Pattern Anal. Machine Intell., vol. 12, no. 2, pp. 113-122, Feb. 1990.[33] C. Goad, "Fast 3D model-based vision," inFrom Pixels to Predicates, A. P. Pentland, Ed. Norwood, NJ: Ablex, 1986, pp. 371-391.[34] R. N. Goldman, "Two approaches to a quadric model for surfaces,"IEEE Comput. Graphics Applications, vol. 3, no. 1, pp. 21-24, Sept. 1983.[35] W.E.L. Grimson, "The combinatorics of object recognition in cluttered environments using constrained search," inProc. 1988 Int. Conf. Computer Vision (ICCV '88), 1988, pp. 218-227.[36] E. L. Hall, J. K. B. Tio, C. A. McPherson, and F. A. Sadjadi, "Measuring curved surfaces for robot vision,"Computer, vol. 15, no. 12, pp. 42-54, Dec. 1982.[37] C. Hansen and T. Henderson, "CAGD-based computer vision,"IEEE Trans. Pattern Anal. Machine Intell., vol. 11, no. 11, pp. 1181-1193, Nov. 1989.[38] C. D. Hansen, "CAGD-based computer vision: The automatic generation of recognition strategies," Ph.D. dissertation, Dep. Comput. Sci., Univ. Utah, 1988.[39] C. M. Hoffmann,Geometric and Solid Modeling: An Introduction. Los Altos, CA: Morgan Kaufmann, 1989.[40] K. Ikeuchi and T. Kanade, "Automatic generation of object recognition programs,"Proc. IEEE, vol. 76, no. 8, pp. 1016-1035, Aug. 1988.[41] A. K. Jain and R. L. Hoffman, "Evidence-based recognition of 3-D objects,"IEEE Trans. Pattern Anal. Machine Intell., vol. 10, no. 6, pp. 783-802, Nov. 1988.[42] A. Kak, A. Vayda, R. Cromwell, W. Kim, and C. Chen, "Knowledge-based robotics,"Int. J. Production Res., vol. 26, no. 5, pp. 707-734, 1988.[43] M. R. Korn and C. R. Dyer, "3-D multiview object representations for model-based object recognition,"Pattern Recog., vol. 20, no. 1, pp. 91-103, 1987.[44] J. Z. Levin, "Mathematical models for determining the intersections of quadric surfaces,"Comput. Graphics Image Processing, vol. 11, pp. 73-87, 1979.[45] W.-C. Lin and T.-W. Chen, "CSG-based object recognition using range images, " inProc. 9th Int. Conf. Pattern Recognition, Nov. 1988, pp. 99-103.[46] S. Lu and A.K.C. Wong, "Analysis of 3-D scene with partially occluded objects for robot vision," inProc. 9th Int. Conf. Pattern Recognition, Rome, Italy, Nov. 1988, pp. 303-308.[47] W.N. Martin and J.K. Aggarwal, "Volumetric descriptions of objects from multiple views,"IEEE Trans. Pattern Anal. Machine Intell., vol. PAMI-5, no. 2, pp. 150-158, Mar. 1983.[48] National Institute of Standards and Technology, "Initial graphics exchange specification, Version 4.0," Tech. Rep., 1988.[49] R. Nevatia and T. Binford, "Description and recognition of curved objects,"Artificial Intell., vol. 8, no. 1, pp. 77-98, 1977.[50] D. Nitzan, "Three-dimensional vision structure for robot applications,"IEEE Trans. Pattern Anal. Machine Intell., vol. 10, no. 3, pp. 291-309, May 1988.[51] M. Potmesil, "Generating models of solid objects by matching 3D surface segments," inProc. 1983 Int. Joint Conf. Artificial Intelligence, Aug. 1983, pp. 1089-1093.[52] A. Requicha and H. Voelcker, "Solid modeling: A historical summary and contemporary assessment,"IEEE Comput. Graphics Applications, vol. 2, no. 2, pp. 9-24, Mar. 1982.[53] A. Requicha and H. Voelcker, "Solid modeling: Current status and research directions,"IEEE. Comput. Graphics Applications, vol. 3, no. 7, pp. 25-37, Oct. 1983.[54] A. A. Requicha, "Representations for rigid solids: Theory, methods, and systems,"Comput. Surveys, vol. 12, no. 4, pp. 437-465, 1980.[55] D. F. Rogers,Procedural Elements for Computer Graphics. New York: McGraw-Hill, 1985.[56] H. Samet,The Design and Analysis of Spatial Data Structures. Reading, MA: Addison-Wesley, 1990.[57] M. O. Shneier, R. Lumia, and M. Herman, "Prediction-based vision for robot control,"Computer, vol. 20, no. 8, pp. 46-55, Aug. 1987.[58] F. Solina and R. Bajcsy, "Recovery of parametric models from range images: The case for superquadrics with global deformations,"IEEE Trans. Pattern Anal. Machine Intell., vol. 12, no. 2, pp. 131-147, Feb. 1990.[59] T. Sripradisvarakul and R. Jain, "Generating aspect graphs for curved objects," inProc. IEEE Workshop Interpretation of 3D Scenes, Nov. 1989, pp. 109-115.[60] Structural Dynamics Research Corp.,Geomod 4.0 User Guide, 1988.[61] Technical Arts Corp.,100X 3-Dimensional Scanner: User's Manual and Application Programming Guide, Redmond, WA.[62] W. Tiller, "Rational B-splines for curve and surface representation,"IEEE Comput. Graphics Applications, vol. 3, no. 6, pp. 61-69, Sept. 1983.[63] J. Veenstra and N. Ahuja, "Efficient octree generation from silhouettes," inProc. 1986 IEEE Conf. Computer Vision and Pattern Recognition, June 1986, pp. 537-542.[64] E. L. Walker and M. Herman, "Geometric reasoning for constructing 3D scene descriptions from images,"Artificial Intell., vol. 37, pp. 275-290, 1988.[65] P.R. Wilson, "A short history of CAD data transfer standards,"IEEE Comput. Graphics Applications, June 1987, pp. 64-67.
Index Terms:
CAD/CAM; solid modelling; CAD-based computer vision; relational graphs; 3-D object recognition systems; mechanical CAD systems; manufacturing database; industry-standard IGES form; polyhedral approximation; geometric inferencing; view-independent information; view-dependent information; patch areas; synthetic views; CAD/CAM; computer vision; solid modelling
Citation:
P.J. Flynn, A.K. Jain, "CAD-Based Computer Vision: From CAD Models to Relational Graphs," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 13, no. 2, pp. 114-132, Feb. 1991, doi:10.1109/34.67642
