Efficient Fourier-based approach for detecting orientations and occlusions in epipolar plane images for 3D scene modeling

ABSTRACT

This paper presents a Fourier-based approach for automatically constructing a 3D panoramic model of a natural scene from a video sequence. The video sequences could be captured by an unstabilized camera mounted on a moving platform on a common road surface. As the input of the algorithms, "seamless" panoramic view images (PVIs) and epipolar plane images (EPIs) are generated after image stabilization if the camera is unstabilized. A novel panoramic EPI analysis method is proposed that combines the advantages of both PVIs and EPIs efficiently in three important steps: locus orientation detection in the Fourier frequency domain, motion boundary localization in the spatio-temporal domain, and occlusion/resolution recovery only at motion boundaries. The Fourier energy-based approaches in literature were usually for low-level local motion analysis and are therefore not accurate for 3D reconstruction and are also computationally expensive. Our panoramic EPI analysis approach is both accurate and efficient for 3D reconstruction. Examples of layered panoramic representations for large-scale 3D scenes from real world video sequences are given.

REFERENCES

• 1: Adelson, E.H. and Bergen, J.R. 1985. Spatiotemporal energy model for the perception of motion. J. Opt. Soc. Am., A2:284-299.
• 2: Allmen, M. and Dyer, C.R. 1991. Long range spatiotemporal motion understanding using spatiotemporal flow curves. In IEEE Conf. Computer Vision and Pattern Recognition, pp. 303-309.
• 3: Baillard, C. and Zisserman, A. 1999. Automatic reconstruction of piecewise planar models from multiple views. In IEEE Conf. Computer Vision and Pattern Recognition, pp. 559-565.
• 4: Baker, H.H. and Bolles, R.C. 1989. Generalizing epipolar-plane image analysis on the spatiotemporal surface. Int. J. Computer Vision, 3:33-49.
• 5: S. Baker , R. Szeliski , P. Anandan, A Layered Approach to Stereo Reconstruction, Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, p.434, June 23-25, 1998
• 6: Michael J. Black , Allan D. Jepson, Estimating Optical Flow in Segmented Images Using Variable-Order Parametric Models With Local Deformations, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.18 n.10, p.972-986, October 1996 [doi>10.1109/34.541407]
• 7: Bolles, R.C., Baker, H.H., and Marimont, D.H. 1987. Epipolar-plane image analysis: An approach to determining structure from motion. Int. J. Computer Vision, 1(1):7-55.
• 8: Chang, N.L. and Zakhor, A. 1997. View generation for three-dimensional scene from video sequence. IEEE Trans on Image Processing, 6(4):584-598.
• 9: Nelson L. Chang , Avideh Zakhor, Constructing a Multivalued Representation for View Synthesis, International Journal of Computer Vision, v.45 n.2, p.157-190, November 2001 [doi>10.1023/A:1012476031602]
• 10: Shenchang Eric Chen, QuickTime VR: an image-based approach to virtual environment navigation, Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, p.29-38, September 1995 [doi>10.1145/218380.218395]
• 11: Robert T. Collins, A Space-Sweep Approach to True Multi-Image Matching, Proceedings of the 1996 Conference on Computer Vision and Pattern Recognition (CVPR '96), p.358, June 18-20, 1996
• 12: Robert T. Collins , Christopher O. Jaynes , Yong-Qing Cheng , Xiaoguang Wang , Frank Stolle , Edward M. Riseman , Allen R. Hanson, The ascender system: automated site modeling from multiple aerial images, Computer Vision and Image Understanding, v.72 n.2, p.143-162, Nov. 1998 [doi>10.1006/cviu.1998.0729]
• 13: S. Coorg , S. Teller, Automatic Extraction of Textured Vertical Facades from Pose Imagery, Massachusetts Institute of Technology, Cambridge, MA, 1998
• 14: Arun K. Dalmia , Mohan Trivedi, High-speed extraction of 3D structure of selectable quality using a translating camera, Computer Vision and Image Understanding, v.64 n.1, p.97-110, July 1996 [doi>10.1006/cviu.1996.0047]
• 15: Paul E. Debevec , Camillo J. Taylor , Jitendra Malik, Modeling and rendering architecture from photographs: a hybrid geometry- and image-based approach, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.11-20, August 1996 [doi>10.1145/237170.237191]
• 16: Olivier Faugeras , Luc Robert , Stéphane Laveau , Gabriella Csurka , Cyril Zeller , Cyrille Gauclin , Imad Zoghlami, 3-D reconstruction of urban scenes from image sequences, Computer Vision and Image Understanding, v.69 n.3, p.292-309, March 1998 [doi>10.1006/cviu.1998.0665]
• 17: D. J. Fleet , M. J. Black , A. D. Jepson, Motion Feature Detection Using Steerable Flow Fields, Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, p.274, June 23-25, 1998
• 18: William T. Freeman , Edward H. Adelson, The Design and Use of Steerable Filters, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.13 n.9, p.891-906, September 1991 [doi>10.1109/34.93808]
• 19: Hansen, M., Anandan, P., Dana, K., van de Wal, G., and Burt, P. 1994. Real-time scene stabilization and mosaic construction. In IEEE Conf. Computer Vision and Pattern Recognition, pp. 54-62.
• 20: Heeger, D.J. 1987. Optical flow from spatio-temporal filters. In Proc. IEEE Int. Conf. Computer Vision, pp. 181-190.
• 21: Ishiguro, H., Yamamoto, M., and Tsuji, S. 1990. Omni-directional stereo for making global map. In Proc. IEEE Int. Conf. Computer Vision, pp. 540-547.
• 22: Bernd Jähne, Digital image processing: concepts, algorithms and scientific applications, Springer-Verlag, London, 1991
• 23: Yin Li , Heung-Yeung Shum , Chi-Keung Tang , Richard Szeliski, Stereo Reconstruction from Multiperspective Panoramas, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.26 n.1, p.45-62, January 2004 [doi>10.1109/TPAMI.2004.1261078]
• 24: Leonard McMillan , Gary Bishop, Plenoptic modeling: an image-based rendering system, Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, p.39-46, September 1995 [doi>10.1145/218380.218398]
• 25: Carlos Morimoto , Rama Chellappa, Fast 3D Stabilization and Mosaic Construction, Proceedings of the 1997 Conference on Computer Vision and Pattern Recognition (CVPR '97), p.660, June 17-19, 1997
• 26: David W. Murray, Recovering range using virtual multicamera stereo, Computer Vision and Image Understanding, v.61 n.2, p.285-291, March 1995 [doi>10.1006/cviu.1995.1021]
• 27: Nayar, S. and Karmarkar, 2000. 360 × 360 mosaics. In IEEE Conf. Computer Vision and Pattern Recognition, II:388-395.
• 28: S. A. Niyogi, Detecting kinetic occlusion, Proceedings of the Fifth International Conference on Computer Vision, p.1044, June 20-23, 1995
• 29: Peleg, S. and Ben-Ezra, M. 1999. Stereo panorama with a single camera. In IEEE Conf. Computer Vision and Pattern Recognition, pp. 395-401.
• 30: Shmuel Peleg , Moshe Ben-Ezra , Yael Pritch, Omnistereo: Panoramic Stereo Imaging, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.23 n.3, p.279-290, March 2001 [doi>10.1109/34.910880]
• 31: S. Peleg , J. Herman, Panoramic mosaics by manifold projection, Proceedings of the 1997 Conference on Computer Vision and Pattern Recognition (CVPR '97), p.338, June 17-19, 1997
• 32: Shmuel Peleg , Benny Rousso , Alex Rav-Acha , Assaf Zomet, Mosaicing on Adaptive Manifolds, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.22 n.10, p.1144-1154, October 2000 [doi>10.1109/34.879794]
• 33: Paul Rademacher , Gary Bishop, Multiple-center-of-projection images, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p.199-206, July 1998 [doi>10.1145/280814.280871]
• 34: Harpreet S. Sawhney , Serge Ayer, Compact Representations of Videos Through Dominant and Multiple Motion Estimation, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.18 n.8, p.814-830, August 1996 [doi>10.1109/34.531801]
• 35: H. S. Sawhney , R. Kumar , G. Gendel , J. Bergen , D. Dixon , V. Paragano, VideoBrushTM: Experiences with Consumer Video Mosaicing, Proceedings of the 4th IEEE Workshop on Applications of Computer Vision (WACV'98), p.56, October 19-21, 1998
• 36: Jonathan Shade , Steven Gortler , Li-wei He , Richard Szeliski, Layered depth images, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p.231-242, July 1998 [doi>10.1145/280814.280882]
• 37: Heung-Yeung Shum , Richard Szeliski, Systems and Experiment Paper: Construction of Panoramic Image Mosaics with Global and Local Alignment, International Journal of Computer Vision, v.36 n.2, p.101-130, Feb. 2000 [doi>10.1023/A:1008195814169]
• 38: H. -Y. Shum , M. Han , R. Szeliski, Interactive Construction of 3D Models from Panoramic Mosaics, Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, p.427, June 23-25, 1998
• 39: Shum, H.-Y. and Szeliski, R., 1999. Stereo reconstruction from multiperspective panoramas. In Proc. IEEE Int. Conf. Computer Vision, pp. 14-21.
• 40: Shum, H.-Y., Kalai, A., and Seitz, S.M. 1999. Omnivergent stereo. In Proc. IEEE Int. Conf. Computer Vision, pp. 22-29.
• 41: Szeliski, R. 1999. A multi-view approach to motion and stereo. In IEEE Conf. Computer Vision and Pattern Recognition, pp. 157-163.
• 42: Wang, J. and Adelson, E.H. 1994. Representation moving images with layers. IEEE Trans. on Image Processing, 3(5):625-638.
• 43: Yalin Xiong , Ken Turkowski, Creating Image-Based VR Using a Self-Calibrating Fisheye Lens, Proceedings of the 1997 Conference on Computer Vision and Pattern Recognition (CVPR '97), p.237, June 17-19, 1997
• 44: Jiang Yu Zheng , Saburo Tsuji, Panoramic representation for route recognition by a mobile robot, International Journal of Computer Vision, v.9 n.1, p.55-76, Oct. 1992
• 45: Jiang Yu Zheng , Saburo Tsuji, Generating dynamic projection images for scene representation and understanding, Computer Vision and Image Understanding, v.72 n.3, p.237-256, Dec. 1998 [doi>10.1006/cviu.1998.0678]
• 46: Z. Zhu , G. Xu , X. Lin, Constructing 3D Natural Scene from Video Sequences with Vibrated Motions, Proceedings of the Virtual Reality Annual International Symposium, p.105, March 14-18, 1998
• 47: Zhu, Z., Xu, G., and Lin, X., 1999. Panoramic EPI generation and analysis of video from a moving platform with vibration. In IEEE Conf. Computer Vision and Pattern Recognition, pp. 531-537.
• 48: Zhu, Z. 2001. Full View Spatio-Temporal Visual Navigation-Imaging, Modeling and Representation of Real Scenes, China Higher Education Press, December 2001 (based on his Ph.D. Thesis, Department of Computer Science and Technology, Tsinghua University, 1997. English Version may be found at http://www-cs.engr.ccny.cuny.edu/~zhu/PhD-Thesis/).
• 49: Zhu, Z. and Hanson, A.R. 2001.3D LAMP: A new layered panoramic representation. In Proc. IEEE Int. Conf. Computer Vision, vol. II, pp. 723-730.
• 50: Zhu, Z., Riseman, E.M., and Hanson, A.R. 2001. Parallel-perspective stereo mosaics. In Proc. IEEE Int. Conf. Computer Vision, vol. I, pp. 345-352.
• 51: Zhigang Zhu , Allen R. Hanson , Edward M. Riseman, Generalized Parallel-Perspective Stereo Mosaics from Airborne Video, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.26 n.2, p.226-237, January 2004 [doi>10.1109/TPAMI.2004.1262190]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

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

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation
          Subjects: Fast Fourier transforms (FFT)

  I. Computing Methodologies
  I.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.8 Scene Analysis
          Subjects: Motion

Keywords:
3D reconstruction, energy model, epipolar plane image, layered representation, motion analysis, occlusion recovery, panoramic representation