An approach to 3D pose determination

ABSTRACT

The orientation, or pose, of an object is a fundamental property that helps to define the geometrical relationship between the object and its environment. In addition, knowledge of object orientation can also facilitate interpretive and decision-making tasks in a variety of practical domains, including industrial, meteorological, and medical applications. Determining object pose, however, remains an open research question in the fields of graphics and visualization. This article describes a novel yet intuitively simple approach, which we call topological goniometry, to directly determine the pose of a three-dimensional object from 3D data. The topology of interest is that of two-sided surfaces in a three-manifold, and includes objects whose shaped are unaffected by elastic transformations. Algorithmically, topological goniometry is composed of the following major steps. The first analyzes the global topology in order to generate a distribution of 3D coordinate triplets in the proximity of the desired pose axis. Using this set of 3D points, that second step then invokes a “3D Walk” algorithm that considers the local topology to produce a generalized curve representing an estimate of the object's axis of pose. The resultant pose axis is thus not constrained to lie along a straight line but can be generalized 3D curve. The methods are illustrated with a variety of synthetically created models that exhibit duct-like shapes, and are further tested by introducting noise as well as deformations to these models. The approach is also applied to a number of real discrete data obtained from meteorological and medical domains. The results suggest that the appproach is applicable to both real and synthetic datasets and is shown to be robust, computationally efficient, and applicable to a variety of problems. The approach can incorporate context- or application-dependent information about the object of interest by using a set of constraints that guide the process of orientation determination. This article describes the approach, its implementation, and the results obtained with numerous applications.

REFERENCES

• 1: Colin Archibald , Cathy Merritt, Pose Determination of Known Objects from Sparse Range Images, Intelligent Autonomous Systems 2, An International Conference, p.185-195, December 11-14, 1989
• 2: ARNOLD, B.H. 1962. Intuitive Concepts in Elementary Topology. Prentice-Hall, Englewood Cliffs, NJ.
• 3: BARTON, C. A. AND ZOI}ACK, M. D. 1988. Determination of in situ stress orientation from borehole guided waves. J. Geophys. Res. 93, B7, 7834-7844.
• 4: BI.UM, H. 1967. A transformation for extracting new descriptors of shape. In Models for the Perception of Speech and Visual Form, MIT Press, Cambridge, MA, 74-87.
• 5: CLINE, H. E., DUMOULIN, C. L., HART, H. R., LORENSON, W. E., AND LUDKE, S. 1987. 3D reconstruction of the brain from magnetic resonance images using a connectivity algorithm. Magnetic Resonance Imaging 5, 345-352.
• 6: CI.1NE, H. E., LORENSEN, W. E., LUDKE, S., CRAWFORD, C. R., AND TEETER, B.C. 1988. Two algorithms for the three dimensional reconstruction of tomograms. Med. Physics 15, 3, 320 -327.
• 7: CLINE, H. E., LUDKE, S., LORENSEN, W. E., AND TEETER, B.C. 1990. A 3D medical imaging research workstation. In Volume Visualization Algorithms and Architectures, ACM SIG- GRAPH'90 Course Notes, ACM, NY.
• 8: COOKE, C. D., FOLKS, R. D., JONES, M. E., EZQUERRA, N. F., AND GARCIA, E.V. 1989. Automatic program for determining the long-axis of the left ventricular myocardium used for Thallium-201 tomographic reconstruction. J. Nuclear Med. 30, 6 IJune), 806.
• 9: CYC. ANSKI, D. AND ORR, J. A. 1985. Application of tensor theory to object recognition and orientation determination. IEEE Trans. Pattern Anal. Mach. Intell. 7, 6, 662-673.
• 10: EZQUERRA, N. AND MULLIf:K, R. 1996. 3D pose determination: Survey and robust approaches. CVGIP (submitted).
• 11: T. L. Faber , E. M. Stokely, Orientation of 3-D Structures in Medical Images, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.10 n.5, p.626-633, September 1988 [doi>10.1109/34.6771]
• 12: James D. Foley , Andries van Dam , Steven K. Feiner , John F. Hughes, Computer graphics: principles and practice (2nd ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 13: GI.ASSNER, A.S. 1989. An Introduction to Ray Tracing. Academic Press, London, U.K.
• 14: HE, Z.X. 1991. Automatic reorientation of left ventricle long-axis in TI-201 SPECT scans. In Proceedings of the European Association of Nuclear Medicine Conference IAmsterdam, March 20-23 ~.
• 15: HE, Z. X., MAUBLANT, J. C., CAUVIN, J. C., AND VEYRE, A. 1991. Reorientation of the left ventricular long-axis on myocardial transaxial tomograms by linear fitting method. J. Nuclear Med. 32, 1794-1800.
• 16: Anil K. Jain, Fundamentals of digital image processing, Prentice-Hall, Inc., Upper Saddle River, NJ, 1989
• 17: KAPOULEAS, I. 1990. Segmentation and feature extraction for magnetic resonance brain image analysis. In Proceedings of the Tenth International Conference on Pattern Recognition (Washington D.C., Dee. 4-8), Vol. 1, 583-590.
• 18: LE~:, A. J. AND CASASENT, D. 1990. Optical neural network for pose determination of spinning satellites. SP1E: Int. Soc. Optical Eng. 1297, 317-328.
• 19: LRL A., PIZER, S., EBERLY, D., MoRsE, B., ET AL. 1994. Volume registration using 3D core. In Proceedings of the Visualization in Biomedical Computing Conference tRochester, MN, Oct. 4-7), SPIE Proceedings, Vol. 2359, 217-226.
• 20: C.-H. Lo , H.-S. Don, 3-D Moment Forms: Their Construction and Application to Object Identification and Positioning, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.11 n.10, p.1053-1064, October 1989 [doi>10.1109/34.42836]
• 21: LORENSEN, W. E. AND CLINE, H. E. 1991. Marching cubes: A high resolution 3D surface construction algorithm. IEEE Trans. Nuclear Sci. 38, 748-754.
• 22: MERRIT, C., ARCHIBALD, C., AND NG, T. 1989. Pose determination of a satellite grapple fixture using a wrist-mounted laser range finder. In Proceedings of the SPIE (San Francisco, CA, Nov. 10-13), Vol. 1002, 583-590.
• 23: MULLICK, R. AND EZQUERRA, N. F. 1995. Automatic determination of LV orientation from SPECT data. IEEE Trans. Med. Imag. 14, 1 (March) 88-99.
• 24: MULLICK, R. AND EZQUERRA, N.F. 1993. Automatic segmentation of 3D cardiac SPECT data. In Proceedings of the Twelfth IEEE Southern Biomedical Engineering Conference (Atlanta, GA, July 23-27), 40-42.
• 25: NCSA 1990. Public domain dataset made available courtesy of the National Center for Supercomputing Applications, University of Illinois, Urbana Champaign.
• 26: PELLIZARI, C. A., CHEN, G. T. Y., SPELBRING, D. R., WEICHSELLBAUM, R. R., AND CHIN, C. T. 1989. Accurate three dimensional registration of CT, PET, and/or MR images of the brain. J. Comput. Assisted Tomography, 30, 20-26.
• 27: RAWCHANDRAN, G. AND CASASENT, D.P. 1991. Generalized in-plane rotation-invariant minimum average correlation energy filter. Optical Eng. 30, 10, 1601-1607.
• 28: RAY, L.P. 1990. Estimation of modeled object pose from monocular images. In Proceedings of the 1990 IEEE International Conference on Robotics and Automation (Los Angeles, CA, June 13-17), Vol. 1,408-413.
• 29: SADJADI, F. A. AND HALL, E.L. 1980. Three dimensional moment invariants. IEEE Trans. Pattern Anal. Mach. Intell. 2, 127-136.
• 30: William J. Schroeder , Jonathan A. Zarge , William E. Lorensen, Decimation of triangle meshes, ACM SIGGRAPH Computer Graphics, v.26 n.2, p.65-70, July 1992
• 31: Peter Shirley , Allan Tuchman, A polygonal approximation to direct scalar volume rendering, ACM SIGGRAPH Computer Graphics, v.24 n.5, p.63-70, Nov. 1990
• 32: Wesley Snyder , Griff Bilbro , Ambalavaner Logenthiran , Sarah Rajala, Optimal thresholding—a new approach, Pattern Recognition Letters, v.11 n.12, p.803-810, Dec. 1990 [doi>10.1016/0167-8655(90)90034-Y]
• 33: Tou, J. T. AND GONZALEZ, R. C. 1974. Pattern Recognition Principles. Addison-Wesley, Reading, MA.
• 34: TRIVEDI, M. M., ABIDI, M. A., EASON, R. O., AND GONZALEZ, R.C. 1989. Object recognition and pose determination in multisensor robotic systems. In Proceedings of the IEEE International Conference on Systems, Man, and Cybernetics (Paris, Oct. 8-11), Vol. 1, 186-193.
• 35: Greg Turk, Re-tiling polygonal surfaces, ACM SIGGRAPH Computer Graphics, v.26 n.2, p.55-64, July 1992
• 36: John Villasenor , Alain Vincent, An algorithm for space recognition and time tracking of vorticity tubes in turbulence, CVGIP: Image Understanding, v.55 n.1, p.27-35, Jan. 1992 [doi>10.1016/1049-9660(92)90004-M]
• 37: WEEKS, J.F. 1985. The Shape of Space. Marcel Dekker, New York.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Curve, surface, solid, and object representations

General Terms:
Algorithms, Design, Theory, Verification

Keywords:
axis of orientation, geometry, orientation determination, pose determination