[1] Crandall D, Owens A, Snavely N, et al. "Discrete-continuous optimization for large-scale structure from motion." (CVPR), 2011 [2] Crandall D, Owens A, Snavely N, et al. SfM with MRFs: Discrete-Continuous Optimization for Large-Scale Structure from Motion.(PAMI), 2012 2013-4-16
Discrete-Continuous Optimization for Large-scale Structure from Motion David Crandall School of Informatics and Computing Indiana University Andrew Owens CSAIL MIT Department of Computer Science Noah Snavely and Dan Huttenlocher Cornell University Runner-up best paper at CVPR 2011
MRFBP
MRFBP
Structure from Motion p 1 p 4 p 2 p 3 minimize f(r,t,x) p 5 p 6 p 7 Camera 1 R 1,t 1 R 2,t 2 Camera 2 Camera 3 R 3,t 3
Reconstruction pipeline ANN 3D (IBA) Start with seed model Run bundle adjustment Remove outliers Add another image Repeat R, T P, X
MRFBP
1SBA scalability 2 IBA[Incremental Bundler Adjustment] 3
SFMMRF SFM
SFMMRF : LBPloopy belief propagation MRF bundle adjustment
SFMMRF IBA 6
MRFBP
Compute relative pose between camera pairs using 2-frame SfM t ij R ij
R ij t ij (Ri, ti)(rj, tj) :
GPS tilt[sinha10]
1
pan twist
ncameras
Levenberg-Marquardt GPS MRF
MRFBP
binary constraints: pairwise camera transformations & camera-point unary constraints: pose estimates (e.g., GPS, heading info) 3D points can also be modeled
matching all pairs of images 1) Vocabulary tree 2) GPS matched pairssiftann pairransac + 5 E
high-twist Rij relative twistrelative twist20 aspect ratios Internet MRF
p Camera 1 Camera 2 Camera 3 track3d
NodesMRFTracks 1camera-camera 2
MRFLabelingNP-hard grid-structured graphssfm MRFLabels Riti6Labels
6-dimensional label Rt twist 0 2D BP distance transformsbp messages [1] [1]P. Felzenszwalb and D. Huttenlocher, Efficient belief propa-gation for early vision, IJCV, vol. 70, no. 1, pp. 41 54, 2006.
1 2 3MRFBP
Message L
T NODELABEL
1 2 3 4BP
tiltpantwistxyz
twist = 0 11*11*11 [] tilt&pan LABEL 1331482 LABEL482R
binary constraints: pairwise camera transformations unary constraints: pose estimates (e.g., GPS, heading info)
R ij IJ : t ij
twist = 0R (tilt & pan)
R ij t ij IJ tilttwist0
IJ tilttwist0
MRFmessage
MRFmessage TLabel
BP non-linear least squares twistrodrigues parameters
1 2 3BP
3D <x, y> BP LABELS2D LABELsz=0 GPS 300*300 GPS1~4
binary constraints: pairwise cameras Camera-3D point unary constraints: pose estimates (e.g., GPS, heading info) 3D points can also be modeled
R ij IJ : t ij
X Camera 1 Camera 3 Camera 2 Track3DX : Ray: XRay:
0
Cost as function of t j
R ij t ij IJ : GPS
Message 3DMessage
MRFCamerasmessage message
MRFCamerasmessage TLabel
BP non-linear least squares z
- 13D tracks3d 23Drobust Huber normb = 25
Reconstruction pipeline GPS 3D R, T P, X NLLS 2D2D 3D3D NLLS
MRFBP
3D 1IBA 22 3
Quad Total images: 6,514 Reconstructed images: 5,233 Edges in MRF: 995,734 Ground truth for 348 cameras Median error wrt ground truth: 1.16m (vs 1.01 for IBA)
Central Rome Reconstructed images: 14,754 Edges in MRF: 2,258,416 Median camera pose difference wrt IBA: 25.0m Our result Incremental Bundle Adjustment [Agarwal09]
GPS 100mBP
1 2 3LABEL 4BP
tilt0 Acropolistilt3.715.8 Quadtilt2.110.5
3D Quad: 1.21m1.9m SanFrancisco: 4.94m4.97m Quad: 1.21m3.93m SanFrancisco: 4.94m7.14m
BP
1 SFM---MRFSFM Cameras3D 2IBA IBA6
LABELS - SFM