Rigidity Checking of 3D Point Correspondences Under Perspective Projection
|
Abstract—An algorithm is described which rapidly verifies the potential rigidity of three-dimensional point correspondences from a pair of two-dimensional views under perspective projection. The output of the algorithm is a simple yes or no answer to the question "Could these corresponding points from two views be the projection of a rigid configuration?" Potential applications include 3D object recognition from a single previous view and correspondence matching for stereo or motion over widely separated views. The rigidity checking problem is different from the structure-from-motion problem because it is often the case that two views cannot provide an accurate structure-from-motion estimate due to ambiguity and ill conditioning, whereas it is still possible to give an accurate yes/no answer to the rigidity question. Rigidity checking verifies point correspondences using 3D recovery equations as a matching condition. The proposed algorithm improves upon other methods that fall under this approach because it works with as few as six corresponding points under full perspective projection, handles correspondences from widely separated views, makes full use of the disparity of the correspondences, and is integrated with a linear algorithm for 3D recovery due to Kontsevich. Results are given for experiments with synthetic and real image data. A complete implementation of this algorithm is being made publicly available.
[1] 1174 R. Basri, "On the Uniqueness of Correspondence Under Orthographic and Perspective Projections," A.I. Memo No. 1333, Massachusetts Institute of Technology, Artificial Intelligence Laboratory, Dec. 1991.
[2] B.M. Bennett, D.D. Hoffman, J.E. Nicola, and C. Prakash, "Structure from Two Orthographic Views of Rigid Motion," J. Opt. Soc. Am. A, vol. 6, no. 7, pp. 1,052-1,069, July 1989.
[3] B.M. Bennett, D.D. Hoffman, and C. Prakash, "Recognition Polynomials," J. Opt. Soc. Am. A, vol. 10, no. 4, pp. 759-764, Apr. 1993.
[4] M.L. Braunstein, D.D. Hoffman, and F.E. Pollick, " Discriminating Rigid from Nonrigid Motion: Minimum Points and Views," Perception and Psychophysics, vol. 47, no. 3, pp. 205-214, Mar. 1990.
[5] C. Harris, "Structure-from-Motion Under Orthographic Projection," Proc. First European Conf. Computer Vision,Antibes, France, pp. 118-123, 1990.
[6] C.G. Harris and J.M. Pike, "3D Positional Integration from Image Sequences," Image Vision Computing, vol. 6, no. 2, pp. 87-90, Feb. 1988.
[7] B.K.P. Horn, "Relative Orientation Revisited," J. Opt. Soc. Am. A, vol. 8, no. 10, pp. 1,630-1,638, Oct. 1991.
[8] X. Hu and N. Ahuja, "Motion Estimation Under Orthographic Projection," IEEE Trans. Robotics and Automation, vol. 7, no. 6, pp. 848-853, June 1991.
[9] D.P. Huttenlocher and J.M. Kleinberg, "Comparing Point Sets Under Projection," Proc. Fifth Ann. ACM-SIAM Symp. Discrete Algorithms,Philadelphia, Pa., pp. 1-7, 1994.
[10] J.J. Koenderink and A.J. van Doorn, "Affine Structure-from-Motion," J. Opt. Soc. Am. A, vol. 8, no. 2, pp. 377-385, Feb. 1991.
[11] L.L. Kontsevich, "Pairwise Comparison Technique: A Simple Solution for Depth Reconstruction," J. Opt. Soc. Am. A, vol. 10, no. 6, pp. 1,129-1,135, June 1993.
[12] R.V.R. Kumar, A. Tirumalai, and R.C. Jain, "A Non-Linear Optimization Algorithm for the Estimation of Structure and Motion Parameters," Proc. IEEE Computer Vision and Pattern Recognition,San Diego, Calif., pp. 136-143, June4-8, 1989.
[13] C-H. Lee and T.S. Huang, "Finding Point Correspondences and Determining Motion of a Rigid Object from Two Weak Perspective Views," Comp. Vis. Graph. and Image Processing, vol. 52, no. 3, pp. 309-327, Mar. 1990.
[14] K. Levenberg, "A Method for the Solution of Certain Nonlinear Problems in Least Squares," Quart. Appl. Math., vol. 2, pp. 164-168, 1944.
[15] H.C. Longuet-Higgins, "A Computer Program for Reconstructing a Scene from Two Projections," Nature, vol. 293, pp. 133-135, Sept. 1981.
[16] D.G. Lowe, "Fitting Parameterized Three-Dimensional Models to Images," IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 13, no. 5, pp. 441-450, May 1991.
[17] D.W. Marquardt, "An Algorithm for Least Squares Estimation of Nonlinear Parameters," SIAM J. Applied Math, vol. 11, no. 2, pp. 431-441, Feb. 1963.
[18] D.P. McReynolds, "Solving for Relative Orientation and Depth," MSc thesis, Dept. of Computer Science, Univ. of British Columbia, Oct. 1988.
[19] D.P. McReynolds, "Determining the Motion of a Remotely Piloted Vehicle from a Sequence of Images," IEEE Proc. Nat'l Aerospace and Electronics Conf.,Dayton, Ohio, vol. 3, pp. 1,097-1,104, 1989.
[20] D.P. McReynolds and D.G. Lowe, "Rigidity Checking of 3D Point Correspondences Under Perspective Projection," Technical Report 95-05, Dept. of Computer Science, Univ. of British Columbia, Mar. 1995, available as http://www.cs.ubc.ca/tr/1995/TR-95-05.
[21] E. Nishimura, G. Xu, and S. Tsuji, "Motion Segmentation and Correspondence Using Epipolar Constraint," Asian Conf. Computer Vision,Osaka, Japan, pp. 199-204, 1993.
[22] D. Sinclair, "Motion Segmentation and Local Structure," Proc. Fourth Int'l Conf. Computer Vision,Berlin, Germany, pp. 366-373, May 1993.
[23] R. Szeliski and S.B. Kang, "Recovering 3D Shape and Motion from Image Streams Using Non-Linear Least Squares," IEEE CS, Conf. Computer Vision and Pattern Recognition,New York, N.Y., pp. 752-753, June 1993.
[24] R.Y. Tsai and T.S. Huang, "Uniqueness and Estimation of 3D Motion Parameters of Rigid Bodies with Curved Surfaces," IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 6, no. 1, pp. 13-27, Jan. 1984.
[25] S. Ullman, The Interpretation of Visual Motion, MIT Press, Cambridge, Mass., 1979.
[26] G.Q. Wei, Z. He, and S.D. Ma, "Fusing the Matching and Motion Estimation of Rigid Point Patterns," Proc. IEEE Int'l Conf. Robotics and Automation,Cincinnati, Ohio, vol. 3, pp. 2,017-2,022, May 1990.
[27] J. Weng, N. Ahuja, and T. Huang, "Optimal Motion and Structure Estimation," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 15, no. 9, pp. 864-884, 1993.
Index Terms:
Rigidity checking, point correspondences, image matching, structure-from-motion, nonlinear parameter estimation, perspective projection.
Citation:
Daniel P. McReynolds, David G. Lowe, "Rigidity Checking of 3D Point Correspondences Under Perspective Projection," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 18, no. 12, pp. 1174-1185, Dec. 1996, doi:10.1109/34.546255
PURCHASE ARTICLE: $19
IEEE Xplore Subscribers
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb