Institute of Photogrammetry and GeoInformation Research Research Groups Geometry Completed projects
Time and Robustness efficient method for SFM of ordered and unordered images

Time and Robustness efficient method for SFM of ordered and unordered images

An example scene with repetitive structure and image pairs with very short baselines. (a) Two example images with repetitive structure. (b) Ground truth of overlap graph with the image IDs on the horizontal and the vertical axes; green pixels denote overlapping image pairs, red pixels represent non-overlapping pairs with incorrect ROs due to RS, and blue pixels indicate the corresponding VSB image pairs. (c) incorrect reconstruction without eliminating incorrect ROs. (d) accurate reconstruction
Team:  X. Wang, F. Rottensteiner, C. Heipke
Year:  2016
Funding:  CSC (Chinese Scholarship Council)
Duration:  Since 2016
Is Finished:  yes
Fig. 1 (a): Image overlap of UAV images
Fig. 1 (b): Image overlap of Internet images
Fig. 2: Workflow of our global SfM system


In close-range photogrammetry untrained users typically do not capture images in a pre-planned pattern, and even experts often need significantly more time for data acquisition when strict recording protocols must be followed. For some years, following the development of sensors, images can be accessed in a much easier way, e.g. crowd-sourced data from the Internet. Different from images taken sequentially (e.g. by unmanned aerial vehicles or UAV), crowd-sourced images are unordered images, i.e. the overlap relationships first need to be established. Fig. 1 is the image overlap graph of UAV images (left) and Internet images (right), respectively, where the horizontal and vertical axes are the image ID and a white spot means that the corresponding image pairs overlap. We first determine the overlap graph and in this way significantly improve the speed of subsequent image matching, since only overlapping image pairs need to be processed. Then, we solve the SFM (Structure from Motion) problem, referred to as image orientation in photogrammetry. A typical solution is based on incremental methods, in which new images are added into the block sequentially, and a global method. In the incremental method bundle adjustment needs to be repeatedly performed to take care of block deformations, which reduce the time efficiency. We want to improve on these deficiencies. 

Current method:

We mainly work on the two most time consuming problems: image matching and image orientation. Currently, we came up two methods to solve these two problems, see Fig. 2.

  • Image matching: We develop an efficient method to detect mutual overlap of a large set of unordered images. Features extracted from all images separately are split by several random k-d trees to efficiently obtain the nearest neighbours. Then, several strategies are applied to refine the results. Please refer to [1].
  • Robustfying Relative orientation: We develop a novel method to eliminate incorrect relative orientations with respect to repetitive structures and very short baselines for improving the robustness of our global sfm system. Please refer to [2] 
  • Image orientation: We use global pose estimation instead of an incremental approach. We present several methods to detect outliers first, and then separate rotation and translation determination into separate steps. Finally, only one bundle adjustment is used to optimize the result. Please refer to [3-5]

The experimental results are available:

Benchmark data are available for download at: 


[1] Wang, X.; Zhan, Z.Q.; Heipke, C. (2017): AN EFFICIENT METHOD TO DETECT MUTUAL OVERLAP OF A LARGE SET OF UNORDERED IMAGES FOR STRUCTURE-FROM-MOTION. In: ISPRS Annals of the Photogrammetry, Remote Sensing and Spatial Information Sciences IV-1/W1, pp. 191-198.

[2] Wang, X.; Xiao, T.; Gruber, M.; Heipke, C. (2019): Robustifying relative orientations with respect to Repetitive Structures and Very Short Baselines for Global SfM. In Proceeding of CVPR workshop.

[3] Wang, X.; Rottensteiner, F.; Heipke, C. (2018): Robust image orientation based on relative rotations and tie points. In: ISPRS Annals of the Photogrammetry, Remote Sensing and Spatial Information Sciences IV-2, pp. 295-302.

[4] Wang, X.; Rottensteiner, F.; Heipke, C. (2019): Structure from motion for ordered and unordered image sets based on random k-d forests and global pose estimation; ISPRS Journal of Photogrammetry and Remote Sensing 147:19-4.

[5] Wang, X.; Rottensteiner, F.; Heipke, C. (2019): Robust Structure From Motion Based on Relative Rotations and Tie Points. In: Photogrammetric Engineering and Remote Sensing 85(5): 347-359. 

Wang, X.; Xiao, Teng.; Kasten, Y. (2020): A HYBRID GLOBAL IMAGE ORIENTATION METHOD FOR SIMULTANEOUSLY ESTIMATING GLOBAL ROTATIONS AND GLOBAL TRANSLATIONS. In: ISPRS Annals of the Photogrammetry, Remote Sensing and Spatial Information Sciences V-2, pp. 95-104.