×

zbMATH — the first resource for mathematics

The structure-from-motion reconstruction pipeline – a survey with focus on short image sequences. (English) Zbl 1211.94006
Summary: The problem addressed in this paper is the reconstruction of an object in the form of a realistically textured 3D model from images taken with an uncalibrated camera. We especially focus on reconstructions from short image sequences. By means of a description of an easy to use system, which is able to accomplish this in a fast and reliable way, we give a survey of all steps of the reconstruction pipeline. For the purpose of developing a coherent reconstruction system it is necessary to integrate a number of different techniques such as feature detection, algorithms of the RANSAC-family, and methods for auto-calibration. We describe and review recent developments of distinct strands of these techniques. While developing our system, the necessity of improvements of several steps of the state-of-the-art reconstruction pipeline emerged. Two of these innovations are introduced in detail in this paper: an advanced SIFT-based feature detector and a two-stage RANSAC process facilitating a faster selection of relevant object points. In addition, we give a recommendation regarding auto-calibration for short image sequences.
MSC:
94A08 Image processing (compression, reconstruction, etc.) in information and communication theory
68U10 Computing methodologies for image processing
Software:
SIFT; SURF
PDF BibTeX XML Cite
Full Text: EuDML Link
References:
[1] Baumberg, A.: Reliable feature matching across widely separated views. IEEE Conf. on Computer Vision and Pattern Recognition 2000, Vol. 01, pp. 1774-1781.
[2] Bay, H., Tuytelaars, T., Gool, L. Van: Surf: Speeded up robust features. 9th European Conference on Computer Vision, Graz 2006.
[3] Beardsley, P. A., Torr, P. H. S., Zisserman, A.: 3d model acquisition from extended image sequences. ECCV ’96: Proc. 4th European Conference on Computer Vision-Volume II, Springer, London 1996, pp. 683-695.
[4] Beis, J. S., Lowe, D. G.: Shape indexing using approximate nearest-neighbour search in high-dimensional spaces. Proc. IEEE Conf. Comp. Vision Patt. Recog 1997, pp. 1000-1006.
[5] Birchfield, S., Tomasi, C.: Depth discontinuities by pixel-to-pixel stereo. Internat. J. Comput. Vision 3 (1999), 269-293.
[6] Canny, J.: A computational approach to edge detection. IEEE Trans. Pattern Anal. Mach. Intell. 8 (1986), 6, 679-698.
[7] Chum, O., Matas, J.: Matching with PROSAC - progressive sample consensus. Proc. Conference on Computer Vision and Pattern Recognition (C. Schmid, S. Soatto, and C. Tomasi, Vol. 1, Los Alamitos 2005, IEEE Computer Society, pp. 220-226.
[8] Chum, O., Matas, J., Kittler, J.: Locally optimized ransac. DAGM-Symposium 2003, pp. 236-243.
[9] Chum, O., Matas, J., Obdržálek, Š.: Enhancing RANSAC by generalized model optimization. Proc. Asian Conference on Computer Vision (ACCV) (K.-S. Hong and Z. Zhang, Vol. 2, Seoul 2004, Asian Federation of Computer Vision Societies, pp. 812-817.
[10] Cox, I. J., Hingorani, S. L., Rao, S. B., Maggs, B. M.: A maximum likelihood stereo algorithm. Comput. Vis. Image Underst. 63 (1996), 3, 542-567. · Zbl 05472735
[11] Dellaert, F., Seitz, S. M., Thorpe, Ch. E., Thrun, S.: Structure from motion without correspondence. IEEE Conf. on Computer Vision and Pattern Recognition 2000, pp. 557-564.
[12] Dempster, A. P., Laird, N. M., Rubin, D. B.: Maximum likelihood from incomplete data via the em algorithm. J. Roy. Statist. Soc. Ser. B 39 (1977), 1, 1-38. · Zbl 0364.62022
[13] Fischler, M. A., Bolles, R. C.: Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography. Commun. ACM 24 (1981), 6, 381-395.
[14] Fitzgibbon, A. W., Zisserman, A.: Automatic 3D model acquisition and generation of new images from video sequences. Proc.European Signal Processing Conference (EUSIPCO ’98), Rhodes 1998, pp. 1261-1269.
[15] Fitzgibbon, A. W., Zisserman, A.: Automatic camera recovery for closed or open image sequences. Proc. European Conference on Computer Vision 1998, pp. 311-326.
[16] Frahm, J.-M., Pollefeys, M.: Ransac for (quasi-)degenerate data (qdegsac). CVPR ’06: Proc. 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, Washington 2006, IEEE Computer Society, pp. 453-460.
[17] Friedman, J. H., Bentley, J. L., Finkel, R. A.: An algorithm for finding best matches in logarithmic expected time. ACM Trans. Math. Software 3 (1997), 3, 209-226. · Zbl 0364.68037
[18] Pollefeys, M., Gool, L J. Van, Meerbergen, G. Van, Vergauwen, M.: A hierarchical symmetric stereo algorithm using dynamic programming. Internat. J. Comput. Vision 47 (2002), 275-285. · Zbl 1012.68729
[19] Häming, K., Peters, G.: Extension of the generalized image rectification - Catching the infinity cases. Proc. 4th International Conference on Informatics in Control, Automation, and Robotics (ICINCO 2007) (J. Zaytoon, J.-L. Ferrier, J. A. Cetto, and J. Filipe, Vol. RA-2, Angers 2007, Institute for Systems and Technologies of Information, Control and Communication, pp. 275-279.
[20] Harris, Ch., Stephens, M.: A combined Corner and Edge detector. 4th ALVEY Vision Conference 1988, pp. 147-151.
[21] Hartley, R. I., Zisserman, A.: Multiple View Geometry in Computer Vision. Second edition. Cambridge University Press 2004. · Zbl 1072.68104
[22] Koch, R., Pollefeys, M., Gool, L. J. Van: Realistic surface reconstruction of 3d scenes from uncalibrated image sequences. J. Visualization and Computer Animation 11 (2000), 3, 115-127. <a href=”http://dx.doi.org/10.1002/1099-1778(200007)11:33.0.CO;2-2” target=”_blank”>DOI 10.1002/1099-1778(200007)11:33.0.CO;2-2
[23] Lhuillier, M., Quan, L.: A quasi-dense approach to surface reconstruction from uncalibrated images. IEEE Trans. Pattern Analysis and Machine Intelligence 27 (2005), 3, 418-433. · Zbl 05110878
[24] Lindeberg, T.: Feature detection with automatic scale selection. Internat. J. Comput. Vision 30 (1998), 2, 77-116.
[25] Lindeberg, T., Bretzner, L.: Real-time scale selection in hybrid multi-scale representations. Proc. Scale-Space, Lect. Notes in Comput. Sci. 2695, Springer 2003, pp. 148-163. · Zbl 1067.68753
[26] Lowe, D. G.: Distinctive image features from scale-invariant keypoints. Internat. J. Comput. Vision 60 (2004), 2, 91-110. · Zbl 02244065
[27] Lucas, B. D., Kanade, T.: An iterative image registration technique with an application to stereo vision. IJCAI81, pp. 674-679.
[28] Mikolajczyk, K., Schmid, C.: Scale and affine invariant interest point detectors. Internat. J. Comput. Vision 60 (2004), 1, 63-86. · Zbl 02244064
[29] Peters, G., Häming, K.: Fast freehand acquisition of 3d objects and their visualization. J. Commun. Comput. 7 (2010), 2-3.
[30] Pollefeys, M., Gool, L. Van, Vergauwen, M., Verbiest, F., Cornelis, K., Tops, J., Koch, R.: Visual modeling with a hand-held camera. Internat. J. Comput. Vision 59 (2004), 3, 207-232.
[31] Pollefeys, M., Koch, R., Gool, L. J. van: Self-calibration and metric reconstruction in spite of varying and unknown internal camera parameters. ICCV 1998, pp. 90-95.
[32] Pollefeys, M., Koch, R., Gool, L. J. van: A simple and efficient rectification method for general motion. Proc. Internat. Conference on Computer Vision (ICCV 1999), pp. 496-501.
[33] Pollefeys, M., Verbiest, F., Gool, L. Van: Surviving dominant planes in uncalibrated structure and motion recovery. Computer Vision - ECCV 2002, 7th European Conference on Computer Vision (Johansen. Lect. Notes Comput. Sci. 2351, Springer-Verlag 2002, pp. 837-851. · Zbl 1039.68700
[34] Pollefeys, M., Vergauwen, M., Cornelis, K., Tops, J., Verbiest, F., Structure, L. Van Gool., In, motion from image sequences.: Proc. Conference on Optical 3-D Measurement Techniques V (K. Gruen, Vienna 2001. pp. 251-258.
[35] Ponce, J., Papadopoulo, T., Teillaud, M., Triggs, B.: On the absolute quadratic complex and its application to autocalibration. IEEE Conference on Computer Vision & Pattern Recognition 2005, Vol. I., pp. 780-787.
[36] Prasad, M., Fitzgibbon, A. W.: Single view reconstruction of curved surfaces. IEEE Conf. on Computer Vision and Pattern Recognition 2006, Vol. 02, pp. ,1345-1354.
[37] Saxena, A., Sun, M., Ng, A. Y.: Make3d: Depth perception from a single still image. AAAI (D. Fox and C. P. Gomes, AAAI Press 2008, pp. 1571-1576.
[38] Schaffalitzky, F., Zisserman, A.: Multi-view matching for unordered image sets, or “How do I organize my holiday snaps?”. Proc. 7th European Conference on Computer Vision, Copenhagen 2002, Springer, Vol. 1, pp. 414-431. · Zbl 1034.68662
[39] Schaffalitzky, F., Zisserman, A., Hartley, R. I., Torr, P. H. S.: A six point solution for structure and motion. ECCV ’00: Proc. 6th European Conference on Computer Vision, Vol. I, London 2000, Springer, pp. 632-648.
[40] Shen, F., Wang, H.: A local edge detector used for finding corners. Proc. ICICS, 2001.
[41] Shi, J., Tomasi, C.: Good features to track. IEEE Conference on Computer Vision and Pattern Recognition (CVPR’94), Seattle 1994.
[42] Snavely, N., Seitz, S. M., Szeliski, R.: Photo tourism: Exploring photo collections in 3d. ACM Trans. on Graphics (SIGGRAPH Proc.), 25 (2006), 3, 835-846. · Zbl 05457597
[43] Torr, P. H. S., Zisserman, A.: Mlesac: a new robust estimator with application to estimating image geometry. Comput. Vis. Image Underst. 78 (2000), 1, 138-156. · Zbl 05690812
[44] Triggs, B.: Autocalibration and the absolute quadric. Proc. IEEE Conference on Computer Vision and Pattern Recognition, Puerto Rico 1977, IEEE Computer Society Press, pp. 609-614.
[45] Tsai, R. Y.: A versatile camera calibration technique for high-accuracy 3D machine vision metrology using off-the-shelf TV cameras and lenses. Radiometry (L. B. Wolff, S. A. Shafer, and G. Healey, Jones and Bartlett Publishers, Inc., pp. 221-244, 1992.
[46] Vergauwen, M., Gool, L. Van: Web-based 3d reconstruction service. Mach. Vision Appl. 17 (2006), 6, 411-426. · Zbl 05074848
[47] Viola, P., Jones, M.: Rapid object detection using a boosted cascade of simple features. IEEE Computer Society Conference on Computer Vision and Pattern Recognition 2001, Vol. 1, 511.
[48] Woodford, O. J., Torr, P. H. S., Reid, I. D., Fitzgibbon, A. W.: Global stereo reconstruction under second order smoothness priors. Proc. IEEE Conference on Computer Vision and Pattern Recognition, Anchorage 2008.
[49] Zhang, Z.: A flexible new technique for camera calibration. IEEE Trans. Pattern Analysis and Machine Intelligence 22 (1998), 1330-1334.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.