Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

Robust recognition systems require a careful understanding of the effects of error in sensed features. In model-based recognition, matches between model features and sensed image features typically are used to compute a model pose and then project the unmatched model features into the image. The error in the image features results in uncertainty in the projected model features. We first show how error propagates when poses are based on three pairs of 3D model and 2D image points. In particular, we show how to simply and efficiently compute the distributed region in the image where an unmatched model point might appear, for both Gaussian and bounded error in the detection of image points, and for both scaled-orthographic and perspective projection models. Next, we provide geometric and experimental analyses to indicate when this linear approximation will succeed and when it will fail. Then, based on the linear approximation, we show how we can utilize Linear Programming to compute bounded propagated error regions for any number of initial matches. Finally, we use these results to extend, from two-dimensional to three-dimensional objects, robust implementations of alignment, interpretation-tree search, and transformation clustering.

REFERENCES

• 1: Tao D Alter, Robust and Efficient 3D Recognition by Alignment, Massachusetts Institute of Technology, Cambridge, MA, 1992
• 2: T. D. Alter, 3-D Pose from 3 Points Using Weak-Perspective, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.16 n.8, p.802-808, August 1994 [doi>10.1109/34.308475]
• 3: Alter, T.D. and Grimson, W.E.L. 1993. Fast and robust 3D recognition by alignment. In Proc. Fourth Inter. Conf. on Computer Vision.
• 4: Alter, T.D. and Jacobs, D. 1994. Error propagation in full 3D-from- 2D object recognition. IEEE Conf. on Computer Vision and Pattern Recognition, pp. 892-898.
• 5: N Ayache , O D Faugeras, HYPER: a new approach for the recognition and positioning to two-dimensional objects, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.8 n.1, p.44-54, Jan. 1986 [doi>10.1109/TPAMI.1986.4767751]
• 6: Henry S. Baird, Model-based image matching using location, Massachusetts Institute of Technology, Cambridge, MA, 1985
• 7: R. Basri, Paraperspective ? Affine, Weizmann Science Press of Israel, Jerusalem, Israel, 1994
• 8: Beveridge, R., Weiss, R., and Riseman, E. 1990. Combinatorial optimization applied to variable scale 2D model matching. IEEE Conf. on Computer Vision and Pattern Recognition, pp. 18-23.
• 9: Bolles, R.C., Quam, L.H., Fischler, M.A., and Wolf, H.C. 1978. The SRI road expert: Image-to-database correspondence. In Proc. DARPA IU Workshop, pp. 163-174.
• 10: Bolles, R.C. and Cain, R.A. 1982. Recognizing and locating partially visible objects: The local-feature-focus method. Int. Journal of Robotics Research, 1(3):57-82.
• 11: Breuel, T. 1991. Model based recognition using pruned correspondence search. IEEE Conf. on Computer Vision and Pattern Recognition , pp. 257-268.
• 12: Brooks, R.A. 1981. Symbolic reasoning among 3-D models and 2-D images. Artificial Intell., 17:285-348.
• 13: Todd Anthony Cass, Polynomial-time geometric matching for object recognition, Massachusetts Institute of Technology, Cambridge, MA, 1993
• 14: Todd A. Cass, Polynomial-Time Object Recognition in the Presence of Clutter, Occlusion, and Uncertainty, Proceedings of the Second European Conference on Computer Vision, p.834-842, May 19-22, 1992
• 15: Todd A. Cass, Robust Affine Structure Matching for 3D Object Recognition, Proceedings of the 4th European Conference on Computer Vision-Volume I, p.492-503, April 15-18, 1996
• 16: Clark, C.S., Eckhardt, W.O., McNary, C.A., Nevatia, R., Olin, K.E., and VanOrden, E.M. 1979. High-accuracy model matching for scenes containing man-made structures. In Proc. Symp. Digital Processing of Aerial Images, SPIE, Vol. 186, pp. 54-62.
• 17: David T. Clemens , David W. Jacobs, Space and Time Bounds on Indexing 3D Models from 2D Images, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.13 n.10, p.1007-1017, October 1991 [doi>10.1109/34.99235]
• 18: Costa, M., Haralick, R.M., and Shapiro, L.G. 1990. Optimal affine-invariant point matching. In Proc. Sixth Israeli Conf. on Artif. Intell., pp. 35-61.
• 19: Ellis, R.E. 1989. Uncertainty estimates for polyhedral object recognition. In Proc. IEEE Conf. Rob. Aut., pp. 348-353.
• 20: Martin A. Fischler , Robert C. Bolles, Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography, Communications of the ACM, v.24 n.6, p.381-395, June 1981 [doi>10.1145/358669.358692]
• 21: Donald B. Gennery, Visual tracking of known three-dimensional objects, International Journal of Computer Vision, v.7 n.3, p.243-270, April 1992 [doi>10.1007/BF00126395]
• 22: Goad, C.A. 1983. Special purpose automatic programming for 3D model-based vision. In Proc. DARPA Image Understanding Workshop , pp. 94-104.
• 23: W. E. L. Grimson , T. Lozano-Pérez, Localizing overlapping parts by searching the interpretation tree, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.9 n.4, p.469-482, July 1987 [doi>10.1109/TPAMI.1987.4767935]
• 24: W. E. L. Grimson , D. P. Huttenlocher, On the Sensitivity of the Hough Transform for Object Recognition, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.12 n.3, p.255-274, March 1990 [doi>10.1109/34.49052]
• 25: Grimson, W.E.L. and Huttenlocher, D.P. 1990b. On the sensitivity of geometric hashing. In Proc. Third Inter. Conf. Computer Vision, pp. 334-338.
• 26: Grimson, W.E.L., Huttenlocher, D.P., and Alter, T.D. 1992a. Recognizing 3D objects from 2D images: An error analysis. In Proc. IEEE Conf. on Computer Vision and Pattern Recognition.
• 27: W. Eric L. Grimson , Daniel P. Huttenlocher , David W. Jacobs, A Study of Affine Matching With Bounded Sensor Error, Proceedings of the Second European Conference on Computer Vision, p.291-306, May 19-22, 1992
• 28: Hel-Or, Y. and Werman, M. 1992. Absolute orientation from uncertain point data: A unified approach. In Proc. IEEE Conf. on Computer Vision and Pattern Recognition, pp. 77-82.
• 29: R. Horaud, New methods for matching 3-D objects with single perspective views, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.9 n.3, p.401-412, May 1987 [doi>10.1109/TPAMI.1987.4767922]
• 30: Daniel P Huttenlocher, Three-Dimensional Recognition of Solid Objects from a Two- Dimensional Image, Massachusetts Institute of Technology, Cambridge, MA, 1988
• 31: Daniel P. Huttenlocher , Shimon Ullman, Recognizing solid objects by alignment with an image, International Journal of Computer Vision, v.5 n.2, p.195-212, Nov. 1990 [doi>10.1007/BF00054921]
• 32: Jacobs, D.W. 1991. Optimal matching of planar models in 3D scenes. IEEE Conf. on Computer Vision and Pattern Recognition, pp. 269- 274.
• 33: David W. Jacobs, Recognizing 3-D Objects Using 2-D Images, Massachusetts Institute of Technology, Cambridge, MA, 1993
• 34: Kumar, R. and Hanson, A. 1989. Robust estimation of camera location and orientation from noisy data having outliers. In Proc. IEEE Workshop on Interpretation of 3D Scenes, pp. 52- 60.
• 35: Lamdan, Y., Schwartz, J.T., and Wolfson, H.J. 1988. Object recognition by affine invariant matching. In Proc. IEEE Conf. on Computer Vision and Pattern Recognition, pp. 335-344.
• 36: Lamdan, Y., Schwartz, J.T., and Wolfson H.J. 1990. Affine invariant model-based object recognition. IEEE Transactions Robotics and Automation, 6:578-589.
• 37: Lamdan, Y. and Wolfson, H.J. 1991. On the error analysis of 'geometric hashing'. IEEE Conf. Computer Vision and Pattern Recognition , pp. 22-27.
• 38: David G. Lowe, Perceptual Organization and Visual Recognition, Kluwer Academic Publishers, Norwell, MA, 1985
• 39: David G. Lowe, Robust model-based motion tracking through the integration of search and estimation, International Journal of Computer Vision, v.8 n.2, p.113-122, Aug. 1992 [doi>10.1007/BF00127170]
• 40: Oshima, M. and Shirai, Y. 1983. Object recognition using three-dimensional information. IEEE Trans. Pattern Anal. Machine Intell. , Vol. 5, No. 4, pp. 353-361.
• 41: Conrad J. Poelman , Takeo Kanade, A Paraperspective Factorization Method for Shape and Motion Recovery, Proceedings of the Third European Conference-Volume II on Computer Vision, p.97-108, May 02-06, 1994
• 42: Isidore Rigoutsos, Massively parallel Bayesian object recognition, New York University, New York, NY, 1992
• 43: Rigoutsos, I. and Hummel, R. 1991. Robust similarity invariant matching in the presence of noise. Eighth Israeli Conf. on Artif. Intell. Computer Vision, Tel Aviv.
• 44: Roberts, L. 1966. Machine perception of three-dimensional solid objects. Optical and Electro-optical Information Processing, J. Tippett (Ed.), MIT Press: Cambridge.
• 45: Rothwell C., Zisserman, A., Mundy, J., and Forsyth, D. 1992. Efficient model library access by projectively invariant indexing functions. IEEE Conf. on Computer Vision and Pattern Recognition, pp. 109-114.
• 46: Sarachik, K.B. and Grimson, W.E.L. 1993. Gaussian error models for object recognition. In Proc. IEEE Conf. on Computer Vision and Pattern Recognition, pp. 400-406.
• 47: Raimund Seidel, Linear programming and convex hulls made easy, Proceedings of the sixth annual symposium on Computational geometry, p.211-215, June 07-09, 1990, Berkley, California, United States [doi>10.1145/98524.98570]
• 48: Strang, G. 1988. Linear Algebra and its Applications. Harcourt, Brace, Jovanavich, Publishers.
• 49: Sugimoto, A. and Murota, K. 1993. 3D object recognition by combination of perspective images. In Proc. SPIE, Vol. 1904, pp. 183- 195.
• 50: Charles W. Therrien, Decision estimation and classification: an introduction to pattern recognition and related topics, John Wiley & Sons, Inc., New York, NY, 1989
• 51: Thompson, D. and Mundy, J.L. 1987. Three-dimensional model matching from an unconstrained viewpoint. In Proc. IEEE Conf. Rob. Aut., pp. 208-220.
• 52: Shimon Ullman , Ronen Basri, Recognition by Linear Combinations of Models, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.13 n.10, p.992-1006, October 1991 [doi>10.1109/34.99234]
• 53: Wayner, P.C. 1991. Efficiently using invariant theory for model-based matching. IEEE Conf. on Computer Vision and Pattern Recognition , pp. 473-478.
• 54: Weinshall, D. and Basri, R. 1993. Distance metric between 3-D models and 2-D images for recognition and classification. IEEE Conf. on Computer Vision and Pattern Recognition, pp. 220- 225.
• 55: Wells, W. 1991. "MAP model matching. IEEE Conf. on Computer Vision and Pattern Recognition, pp. 486-492.
• 56: William M. Wells, III, Statistical Object Recognition, Massachusetts Institute of Technology, Cambridge, MA, 1993

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.3 Deduction and Theorem Proving
          Subjects: Uncertainty, "fuzzy," and probabilistic reasoning

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Linear programming

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Feature evaluation and selection
      I.5.4 Applications
          Subjects: Computer vision

General Terms:
Design, Experimentation, Measurement, Performance, Theory

Keywords:
Gaussian error, alignment, bounded error, error propagation, linear programming, model-based vision, noise, object recognition, perspective, scaled-orthographic, uncertainty