Fast and cheap object recognition by linear combination of views

ABSTRACT

In this paper, we present a real-time algorithm for 3D object detection in images. Our method relies on the Ullman and Basri [13] theory which claims that the same object under different transformations can often be expressed as the linear combinations of a small number of its views. Thus, in our framework the 3D object is modelized by two 2D images associated with spatial relationships described by local-invariant feature points. The recognition is based on feature points detection and alignment with the model. Important theoretical optimizations have been introduced in order to speed up the original full alignment scheme and to reduce the model size in memory. The recognition process is based on a very fast recognition loop which quickly eliminates outliers. The proposed approach does not require a segmentation stage, and it is applicable to cluttered scenes. The small size of the model and the rapidity of the detection make this algorithm particularly suitable for real-time applications on mobile devices.

REFERENCES

• 1: Yali Amit , Donald Geman , Xiaodong Fan, A Coarse-to-Fine Strategy for Multiclass Shape Detection, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.26 n.12, p.1606-1621, December 2004 [doi>10.1109/TPAMI.2004.111]
• 2: H. Bay, T. Tuytelaars, and L. J. Van Gool. SURF: Speeded up robust features. In European Conference on Computer Vision, pages 404--417, 2006.
• 3: Vittorio Ferrari , Tinne Tuytelaars , Luc Gool, Simultaneous Object Recognition and Segmentation from Single or Multiple Model Views, International Journal of Computer Vision, v.67 n.2, p.159-188, April 2006 [doi>10.1007/s11263-005-3964-7]
• 4: David Forsyth , Joseph L. Mundy , Andrew Zisserman , Chris Coelho , Aaron Heller , Charles Rothwell, Invariant Descriptors for 3D Object Recognition and Pose, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.13 n.10, p.971-991, October 1991 [doi>10.1109/34.99233]
• 5: C. Harris and M. Stephens. A combined corner and edge detection. In Proceedings of The Fourth Alvey Vision Conference, pages 147--151, 1988.
• 6: N. K. J. Fauqueur and R. Anderson. Multiscale keypoint detection using the dual-tree complex wavelet transform. In IEEE International Conference on Image Processing (ICIP'2006), 2006.
• 7: Vincent Lepetit , Pascal Lagger , Pascal Fua, Randomized Trees for Real-Time Keypoint Recognition, Proceedings of the 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05) - Volume 2, p.775-781, June 20-26, 2005 [doi>10.1109/CVPR.2005.288]
• 8: David G. Lowe, Object Recognition from Local Scale-Invariant Features, Proceedings of the International Conference on Computer Vision-Volume 2, p.1150, September 20-25, 1999
• 9: D. G. Lowe. Local feature view clustering for 3d object recognition. In IEEE Conference on Computer Vision and Pattern Recognition, volume I, pages 682--688, 2001.
• 10: K. Mikolajczyk , T. Tuytelaars , C. Schmid , A. Zisserman , J. Matas , F. Schaffalitzky , T. Kadir , L. Van Gool, A Comparison of Affine Region Detectors, International Journal of Computer Vision, v.65 n.1-2, p.43-72, November 2005 [doi>10.1007/s11263-005-3848-x]
• 11: Shree K. Nayar , Masahiro Watanabe , Minori Noguchi, Real-Time Focus Range Sensor, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.18 n.12, p.1186-1198, December 1996 [doi>10.1109/34.546256]
• 12: Fred Rothganger , Svetlana Lazebnik , Cordelia Schmid , Jean Ponce, 3D Object Modeling and Recognition Using Local Affine-Invariant Image Descriptors and Multi-View Spatial Constraints, International Journal of Computer Vision, v.66 n.3, p.231-259, March 2006 [doi>10.1007/s11263-005-3674-1]
• 13: 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]
• 14: P. Viola and M. Jones. Rapid object detection using a boosted cascade of simple features. In IEEE Conference on Computer Vision and Pattern Recognition, volume 1, pages 511--518, 2001.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.8 Scene Analysis

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Linear systems (direct and iterative methods)

  I. Computing Methodologies
  I.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.7 Feature Measurement
  I.5 PATTERN RECOGNITION
      I.5.1 Models
          Subjects: Structural

General Terms:
Algorithms, Performance

Keywords:
2D views, linear combination, object recognition