| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
The Automatic Construction of a View-Independent Relational Model for 3-D Object Recognition
June 1993 (vol. 15 no. 6)
pp. 531-544
A view-independent relational model (VIRM) used in a vision system for recognizing known 3-D objects from single monochromatic images of unknown scenes is described. The system inspects a CAD model from a number of different viewpoints, and a statistical interference is applied to identify relatively view-independent relationships among component parts of the object. These relations are stored as a relational model of the object, which is represented in the form of a hypergraph. Three-dimensional components of the object, which can be associated with extended image features obtained by grouping of primitive 2-D features are represented as nodes of the hypergraph. Covisibility of model features is represented by means of hyperedges of the hypergraph, and the pairwise view-independent relations form procedural constraints associated with the hypergraph edges. During the recognition phase, the covisibility measures allow a best-first search of the graph for acceptable matches.
[1] 531N. Ayache and O. D. Faugeras, "HYPER: A new approach for the recognition and positioning of two-dimensional objects,"IEEE Trans. Patt. Anal. Machine Intell., vol. 8, no. 1, pp. 44-54, 1986.[2] K. D. Baker and G. D. Sullivan, "Performance assessment of model-based tracking," inProc. IEEE Workshop Applications Comput. Vision(Palm Springs), Nov. 1992.[3] H. S. Baird,Model-Based Image Matching Using Location, Cambridge, MA: MIT Press, 1986.[4] C. Berge,Graph and Hypergraph. New York: North-Holland, 1973.[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, Ed., "Guest Editor's introduction,"(Special Issue on CAD-Based Robot Vision) Computer, Aug. 1987.[8] B. Bhanu and C.-C. Ho, "CAD-based 3D object representation for robot vision,"Computer, vol. 20, pp. 19-35, Aug. 1987.[9] T. O. Binford, "Survey of model-based image analysis systems,"Int. J. Robotics Res., vol. 1, no. 1, 1982.[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] A. J. Bray, "Recognising and tracking polyhedral objects," Ph.D. dissertation, Univ. of Sussex, Oct. 1990.[12] K. S. Brisdon, G. D. Sullivan, and K. D. Baker, "Feature aggregation in iconic model evaluation," inProc. Fourth Alvey Vision Conf.(Manchester), 1988.[13] R. A. Brooks, "Model-based three-dimensional interpretations of two-dimensional images,"IEEE Trans. Patt. Anal. Machine Intell., vol. PAMI-5, pp. 140-150, 1983.[14] J. F. Canny, "A computational approach to edge detection,"IEEE Trans. Pattern Anal. Machine Intell., vol. PAMI-8, pp. 679-697, 1986.[15] 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.[16] C. H. Chien and J. K. Aggarwal, "Model construction and shape recognition from occluding contours,"IEEE Trans. Patt. Anal. Machine Intell., vol. 11, no. 4, pp. 372-389, 1989.[17] 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.[18] J. H. Connell and M. Brady, "Generating and generalizing models of visual objects,"Artificial Intell., vol. 31, pp. 159-183, 1987.[19] S. J. Dickinson, A. P. Pentland, and A. Rosenfeld, "Qualitative 3-D shape reconstruction using distributed aspect graph matching," inProc. ICCV 90(Osaka), 1990, pp. 257-262.[20] B. A. Draper and E. M. Riseman, "Learning 3D object recognition strategies," inProc. IEEE CVPR91(Hawaii), 1991, pp. 320-324.[21] T. Fan, G. Medioni, and R. Nevatia, "Recognizing 3-D objects using surface descriptions,"IEEE Trans. Patt. Anal. Machine Intell., vol. 11, no. 11, pp. 1140-1157, 1989.[22] L. D. Floriani, "Feature extraction from boundary models of three dimensional objects,"IEEE Trans. Patt. Anal. Machine Intell., vol. 11, no. 8, pp. 785-798, 1989.[23] P. J. Flynn and A. K. Jain, "CAD-based computer vision: From CAD models to relational graphs,"IEEE Trans. Patt. Anal. Machine Intell., vol. 13, no. 2, pp. 114-132, 1991.[24] Z. Gigus and J. Malik, "Computing the aspect graph for line drawings of polyhedral objects,"IEEE Trans. Patt. Anal. Machine Intell., vol. 12, no. 2, pp. 113-122, 1990.[25] C. Goad, "Special purpose automatic programming for 3D model-based vision," inProc. Image Understanding Workshop(Virginia), 1983, pp. 94-104.[26] W. E. L. Grimson and T. Lozano-Perez, "Model-based recognition and localization from sparse range or tactile data,"Int. J. Robotics Res., vol. 3, no. 3, pp. 3-35, 1984.[27] W. E. L. Grimson and T. Lozano-Perez, "Localizing overlapping parts by searching the interpretation tree,"IEEE Trans. Pattern Anal. Machine Intell., vol. PAMI-9, no. 4, July 1987.[28] C. Hansen and T. Henderson, "CAGD-based computer vision,"IEEE Trans. Patt. Anal. Machine Intell., vol. 11, no. 11, pp. 1181-1193, 1989.[29] K. Ikeuchi, "Generating an interpretation tree from a CAD model for 3-D object recognition in bin-picking tasks,"Int. J. Comput. Vision, vol. 1, no. 2, 1987.[30] A. K. Jain and R. Hoffman, "Evidence-based recognition of 3-D objects,"IEEE Trans. Patt. Anal. Machine Intell., vol. 10, no. 6, pp. 783-801, 1988.[31] J. J. Koenderink and A. J. van Doorn, "The internal representation of solid shape with respect to vision,"Biolog. Cybern., vol. 32, pp. 211-216, 1979.[32] D.J. Kriegman and I. Ponce, "Computing exact aspect graphs of curved objects: Solids of revolution," inProc. IEEE Workshop Interpretation of 3D Scenes, IEEE, New York, Nov. 1989, pp. 116-121.[33] Y. Kuno, Y. Okamoto, and S. Okada, "Object recognition using a feature search strategy generated from a 3D model,"Proc. ICCV 90(Osaka), 1990, pp. 626-635.[34] D. G. Lowe, "Three-dimensional object recognition from single two-dimensional images,"Artificial Intell., vol. 31, 1987.[35] D. Lowe, Perceptual Organization And Visual Recognition. Boston: Kluwer, 1985.[36] M. Marefat and R. L. Kashyap, "Geometric reasoning for recognition of three-dimensional object features,"IEEE Trans. Patt. Anal. Machine Intell., vol. 12, no. 10, pp. 949-965, 1990.[37] D. Marr and H. K. Nishihara, "Representation and recognition of the spatial organization of three-dimensional shape," inProc. Roy. Soc. Lond. B, 1978, pp. 269-294, vol. 200.[38] H. Niemann, G. F. Sagerer, S. Schroder, and F. Kummert, "Ernest: A semantic network system for pattern understanding,"IEEE Trans. Patt. Anal. Machine Intell., vol. 12, no. 10, pp. 883-905, 1990.[39] T. Sripradisvarakul and R. Jain, "Generating aspect graphs for curved objects," inProc. IEEE Workshop Interpretation of 3D Scenes, Nov. 1989, pp. 109-115.[40] G. D. Sullivan, "Visual interpretation of known objects in constrained scenes,"Phil. Trans. Roy. Soc. London B, vol. 337, pp. 361-370, 1992.[41] A. K. C. Wong, S. W. Lu, and M. Rioux, "Recognition and shape synthesis of 3D objects based on attributed hypergraphs,"IEEE Trans. Patt. Anal. Machine Intell., vol. 11, no. 3, pp. 279-290, 1990.[42] A. D. Worrall, K. D. Baker, and G. D. Sullivan, "Model based perspective inversion," inProc. Fourth Alvey Vision Conf.(Manchester), 1988.[43] S. Zhang, L. Du, G. D. Sullivan, and K. D. Baker, "Model-based 3D grouping by using 2D cues," inProc. British Machine Vision Conf.(Oxford), 1990.
Index Terms:
spatial reasoning; geometric reasoning; view-independent relational model; 3-D object recognition; vision system; single monochromatic images; CAD model; statistical interference; relational model; hypergraph; primitive 2-D features; hyperedges; procedural constraints; covisibility measures; best-first search; CAD; computer vision; graph theory; spatial reasoning; statistics
Citation:
S. Zhang, G.D. Sullivan, K.D. Baker, "The Automatic Construction of a View-Independent Relational Model for 3-D Object Recognition," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 15, no. 6, pp. 531-544, June 1993, doi:10.1109/34.216723
