1 of 88

Get to know:

Multiple View Geometry & OpenMVG

2 of 88

Agenda

Tutorial on 3D reconstruction from images

Camera geometry
Multiple View geometry (optimization vs closed form solutions)
Image matching
Large scale image matching
Structure from Motion
Best resources

OpenMVG (retrospective on creating an open source project)

Q&A

3 of 88

3D reconstruction from images

Multiple-View Stereovision

Multi-View Geometry

4 of 88

What are we gonna learn about?

Bearing vector

Camera Intrinsics

Camera Pose|Extrinsics

Residual Error

Triangulation

Tracks

5 of 88

Camera geometry | Projective geometry

6 of 88

Camera geometry | Projective geometry

7 of 88

Camera geometry | Projective geometry

8 of 88

Camera geometry | Projective geometry

9 of 88

Camera geometry | Projective geometry

10 of 88

Camera geometry | Projective geometry

(x’,y’) = (ui,vi) / wi

Bearing = R^T * K^-1(x,y,1)

Cartesian coordinates

Homogeneous coordinates (W)

x = (xi,yi) ->x,y,w

X = (X,Y,Z) -> X,Y,Z,W

11 of 88

Camera geometry | Projective geometry

12 of 88

Two view geometry

What happen if we have two camera, as human do?

https://github.com/openMVG/openMVG/tree/develop/src/openMVG_Samples

13 of 88

Two view geometry

What happen if we have two camera, as human do?

Triangulation|Residual Error|Cheirality
Epipolar Geometry
Relative Pose
Absolute Pose
Homography
Robust estimation
Lens distortion
Bundle adjustment

https://github.com/openMVG/openMVG/tree/develop/src/openMVG_Samples

14 of 88

Two view geometry

What happen if we have two camera, as human do?

We can triangulate observations!

15 of 88

Two view geometry

What happen if we have two camera, as human do?

We can triangulate observations!

{X} given C,C’ and x,x’

Is it easy?

Yes and No

16 of 88

Two view geometry

What happen if we have two camera, as human do?

We can triangulate observations!

{X} given C,C’ and x,x’

Is it easy?

Yes and No

NOISE

imperfect parameters

17 of 88

Two view geometry

What happen if we have two camera, as human do?

We can triangulate observations!

{X} given C,C’ and x,x’

Is it easy?

Yes and No

NOISE

imperfect parameters => Residual Errors

18 of 88

Residual Error

19 of 88

Residual Error

Image Plane (Pixels)

Angular (Radian/Degree)

20 of 88

Cheirality | Positive Depth

Depth of a point | Projected along the Z camera axis (direction of looking)

Why do we need to know?

A visible point cannot be

behind a camera (outlier)

depth > 0

depth < 0

Depth = (R*X)[2] + t[2]

21 of 88

Two view geometry

What happen if we have two camera, as human do?

Triangulation|Residual Error|Cheirality
Epipolar Geometry
Relative Pose
Absolute Pose
Homography
Robust estimation
Lens distortion
Bundle adjustment

22 of 88

Epipolar Geometry

Projection of points along the bearing vector are projected to a line

23 of 88

Epipolar Geometry

Projection of points along the bearing vector are projected to a line

Triangular relation (O_l X O_R)
/!\ Relation is independent of scale (the camera baseline: t) /!\

e (Epipole)

can be Inside or Outside image

24 of 88

Fundamental matrix | Essential Matrix

Relation point - ligne F [3x3] | E [3x3]

Pixel coords ->

Bearing vectors ->

Epipoles ->

25 of 88

Fundamental matrix | Essential Matrix

Relation point - ligne F [3x3] | E [3x3]

Pixel coords ->

F -> rank2 -> 7 Dof

8 points -> DLT
7 points -> DLT+rank

Bearing vectors ->

E -> 5Dof (R:3Dof + t:2dof (scale independent))

8 points -> DLT
5 points -> Minimal solver

26 of 88

Two view geometry

What happen if we have two camera, as human do?

Triangulation|Residual Error|Cheirality
Epipolar Geometry
Relative Pose
Absolute Pose
Homography
Robust estimation
Lens distortion
Bundle adjustment

27 of 88

Essential Matrix -> Relative pose

Bearing vectors ->

E -> 5Dof (R:3Dof + t:2dof (scale independent))

8 points -> DLT
5 points -> Minimal solver

Essential matrix -> [R|t] -> relative pose

28 of 88

Spherical camera | Epipolar geometry

Epipolar geometry is still valid for Spherical cameras:

A line is projecting to a circle

Cool fact: Epipole always visible

-> Show in which direction the other camera is

29 of 88

Two view geometry

What happen if we have two camera, as human do?

Triangulation|Residual Error|Cheirality
Epipolar Geometry
Relative Pose
Absolute Pose
Homography
Robust estimation
Lens distortion
Bundle adjustment

30 of 88

Absolute pose

Find the camera parameters given 2D - 3D correspondences

Calibrated camera -> DLT (4pt) | Minimal Solver (3pt)
Uncalibrated proj. camera -> DLT (6pt)
Uncalibrated + distortion -> Non Linear

31 of 88

Two view geometry

What happen if we have two camera, as human do?

Triangulation|Residual Error
Epipolar Geometry
Relative Pose
Absolute Pose
Homography
Robust estimation
Lens distortion
Bundle adjustment

32 of 88

Homography | Planar constraint

What happen if 3D points belong to the same plane?

2d-2d correspondences

H is a 2D projective linear relation

4points (DLT)

Cool fact: Reversible L->R | R->L

33 of 88

Two view geometry

What happen if we have two camera, as human do?

Triangulation|Residual Error
Epipolar Geometry
Relative Pose
Absolute Pose
Homography
Robust estimation
Lens distortion
Bundle adjustment

34 of 88

Robust estimation

Find agreement in chaos?

Hypothesis -> A model exists and points belong or do not belong

Common framework: RANSAC: RANdom Sampling Consensus

35 of 88

Robust estimation

Find agreement in chaos? => RANSAC

Hypothesis -> A model exists and points belong or do not belong

How many point support a random sample hypothesis?

#Points under tolerance Alpha for a given metric (i.e Distance point to line)

36 of 88

Robust estimation

Find agreement in chaos? => RANSAC

Hypothesis -> A model exists and points belong or do not belong

How many point support a random sample hypothesis?

#Points under tolerance Alpha for a given metric

Which Value?

Which Metric?

37 of 88

Robust estimation

Find agreement in chaos? => RANSAC

Hypothesis -> A model exists and points belong or do not belong

How many point support a random sample hypothesis:

#Points under tolerance Alpha for a given metric

Which Value?

Empiric

i.e 2 pixel

Which Metric?

Algebraic vs pixel

With or without dimension

38 of 88

Robust estimation (Homography)

39 of 88

Two view geometry

What happen if we have two camera, as human do?

Triangulation|Residual Error
Epipolar Geometry
Relative Pose
Absolute Pose
Homography
Robust estimation
Lens distortion
Bundle adjustment

40 of 88

Lens/Camera distortion

Mathematical modelization of the Lens distortion

Distortion <-> Undistortion

Lens | Math model (i.e polynomial)

Direct (apply polynomial)
Undirect (iterative minimization)

So camera parameters become: lens coef. ; K (principal point + focal length)

Polynomial of degree 1, degree 3; Degree 3 + Tangential (Brown-Conrady)

41 of 88

A note on camera distortion & epipolar geometry

Epipolar Line -> Curve!

If using distortion | un-distortion methods -> no more problem

42 of 88

Two view geometry

What happen if we have two camera, as human do?

Triangulation|Residual Error
Epipolar Geometry
Relative Pose
Absolute Pose
Homography
Robust estimation
Lens distortion
Bundle adjustment

43 of 88

Bundle adjustment

Let’s say we start from some initial parameters?

Could we optimize them all at the same time?

Residual cost-function (pixel)
Parameter optimization

Gradient descent

Non Linear Least Square optimization:

Levenberg-Marquardt

-> Working from 2 to N views

44 of 88

Multiple-view geometry

What happen if we have more camera, as human do when we move?

45 of 88

Multiple-view geometry

What happen if we have more camera, as human do when we move?

Corresponding points

Feature matching
Feature tracking
Large Scale Feature matching

Structure from Motion (SfM)

Incremental
Global

46 of 88

Feature matching

Describe image with Local Feature & descriptors

Nearest neighbors!

Closest distance� in descriptor space

47 of 88

Feature tracking

How can we retrieve corresponding 2d observations to a 3D potential points?

ordered images -> Correlation | KLT (Lucas Kanade -> gradient tracking)

un-ordered images -> Connected Component

48 of 88

Large Scale Matching

Compute

Features

Compute

Matches

Geometric

Filter

Which image pairs to match?

Tracks

Exhaustive [Default]

Video (n-next)

GPS neighborhood

Pre-emptive

matching

VLAD

Local(sampling)

Global

Feature independent

Pairs

Brute-Force [Too Slow]

Approximate Nearest Neighbors

49 of 88

Multiple-view geometry

What happen if we have more camera, as human do when we move?

Corresponding points

Feature matching
Feature tracking
Large Scale Feature matching

Structure from Motion (SfM)

Incremental
Global

50 of 88

Structure from Motion | SfM

51 of 88

Structure from Motion | Approach

Incremental

Start from a seed (Relative pose)
Add one image at a time (Absolute pose)

Bundle Adjust often to minimize error accumulation

Global

Start from Relative pose graph
Global Rotations
Global Translations
Triangulation + Bundle Adjust once

[ACCV12] Moulon P. et al. Adaptive Structure from Motion with a contrario model estimation.

[ICCV13] Moulon P. et al. Global Fusion of Relative Motions for Robust, Accurate and Scalable Structure from Motion.

52 of 88

What do you need to remember

Bearing vector

Camera Intrinsics

Camera Pose|Extrinsics

Residual Error

Triangulation

Tracks

53 of 88

What do you need to remember

Geometric solver (H, F, E,...) -> (X Degree of Freedom | Y correspondences):

Linear solution -> Subject to noise
Closed form solution -> Perfect geometric (multiple) solutions
Adjustment -> Nonlinear Least Square -> Levenberg Marquardt

Projective geometry -> convenient (Linear Least Squares: SVD is your best friend)

Distortion -> un-convenient

Bundle Adjustment

Global Minimization -> Not convex -> stuck in local minima
Distortion and R|T can compensate each other...

54 of 88

Resources (Which book to read?)

Multiple View Geometry in Computer Vision. Richard Hartley and Andrew Zisserman, March 2004. https://www.robots.ox.ac.uk/~vgg/hzbook/

Multi-View Stereo: A Tutorial. Yasutaka Furukawa and Carlos Hernandez. Foundations and Trends in Computer Graphics and Vision, 2015.

https://github.com/openMVG/awesome_3DReconstruction_list

55 of 88

OpenMVG:

Open Multiple-View Geometry

55

56 of 88

Agenda

OpenMVG?

The Framework

Creating pipelines

Showcases

Challenges and opportunities

Take Home Message

56

57 of 88

[OpenMVG] The long term goal

2013: Create an accessible; patent free & permissive library for 3D reconstruction from images

OpenMVG

Focus on Multiple View Geometry & Structure From Motion

57

58 of 88

[OpenMVG] The Vision

What is OpenMVG?

A flexible C++ framework focused on reproducible research | MPL2 Permissive license
TDD Test Driven Development since day 1

Mission

Extend awareness about 3D reconstruction from images algorithms and techniques

Vision

Ease reproducible research with easy-to-read and accurate implementation of state of the art algorithms (implementation + evaluation framework)

Credo

"Keep it simple, keep it maintainable"

58

In order to start OpenMVG I set some basic rules to keep as a motivation for the project to move forward.

What the project should be:

The main goal is about creating a c++ library to help reproducible research and keep it with a permissive license.

In order to check that every implementation is “working” (as we expect whatever the platform we use) we are following the Test Driven Development rule.

The mission/Main goal is to share knowledge with the community, extend awareness about 3D reconstruction from images algorithms and techniques.

The project vision is to ease reproducible research and allow our community to use, modify, play with accurate implementation of the most relevant algorithms to this field

And finally, I set a credo to Make things simple and easier to maintain by all of us (let’s be in favor of an easy learning curve rather than some code that is fast but that you cannot understand)

59 of 88

[OpenMVG] How hard could it be?

The magic: Linear formulation is all you need to build a SFM pipeline

Triangulation, rotation averaging, E/F/H/Relative/Absolute Pose Matrix

The dark side: Needed for robustness and speed

Robust estimation - API (Flexibility/Extensibility)
Optimization (Bundle Adjustment)
Minimal solvers (speed/accuracy)

59

Pictures

Image

description

Image matching

SfM

60 of 88

OSS: It takes time, commitment, time...

60

VLAD

Stellar SfM

61 of 88

Implementation of many papers along the road

Minimal solvers (Relative/Absolute pose)

.. [Nister] An Efficient Solution to the Five-Point Relative Pose. PAMI 2004

.. [Kneip] A Novel Parametrization of the P3P-Problem for a Direct Computation of Absolute Camera Position and Orientation. CVPR 2011

.. [Ke] An Efficient Algebraic Solution to the Perspective-Three-Point Problem. CVPR 2017

.. [Nordberg] Lambda Twist: An Accurate Fast Robust Perspective Three Point (P3P) Solver. ECCV 2018

Triangulation

.. [Lee] Closed-Form Optimal Triangulation Based on Angular Errors. ICCV 2019; Triangulation: Why Optimize? BMVC 2019

.. [LinfNorm] L infinity Minimization in Geometric Reconstruction Problems. CVPR 2004

Robust estimation

.. [ACRANSAC] Automatic homographic registration of a pair of images, with a contrario elimination of outliers. IPOL 2012

Global Structure from motion

Global

.. [Govindu] "Combining two-view constraints for motion estimation". CVPR 2001

.. [Martinec] Robust Multiview Reconstruction. 2008

.. [Chatterjee] Efficient and Robust Large-Scale Rotation Averaging. ICCV 2013

.. [Kyle2014] Robust Global Translations with 1DSfM. ECCV 2014

.. [GlobalACSfM] Global Fusion of Relative Motions for Robust, Accurate and Scalable Structure from Motion. ICCV, 2013

Sequential

.. [ACSfM] Adaptive structure from motion with a contrario model estimation. ACCV, 2012.

Tracking

.. [TracksCVMP12] Unordered feature tracking made fast and easy. CVMP 2012.

61

exhaustive list here

62 of 88

OpenMVG

The framework

62

63 of 88

OpenMVG framework

63

Pictures

Image

description

Image matching

SfM

Task

Data

Provider

Data

Storage

Binaries

Pipelines

SfMInit_ImageListing

ComputeFeatures

ComputeMatches

Libraries

SfM

Localization

Export

Import

EvalQuality

64 of 88

OpenMVG framework

64

Pictures

Image

description

Image matching

SfM

Task

Data

Provider

Data

Storage

Binaries

Pipelines

SfMInit_ImageListing

ComputeFeatures

ComputeMatches

Abstraction Layer

Data Layer

Libraries

Implementation Layer

SfM

Localization

Export

Import

EvalQuality

65 of 88

OpenMVG framework

65

Pictures

Image

description

Image matching

SfM

Task

Data

Provider

Data

Storage

Binaries

Pipelines

SfMInit_ImageListing

ComputeFeatures

ComputeMatches

Data Layer

Libraries

Implementation Layer

SfM

Localization

Export

Import

EvalQuality

Features/Regions

Provider

Matches_provider

66 of 88

OpenMVG framework

66

Pictures

Image

description

Image matching

SfM

Task

Data

Provider

Data

Storage

Binaries

Pipelines

SfMInit_ImageListing

ComputeFeatures

ComputeMatches

Libraries

Implementation Layer

SfM

Localization

Export

Import

EvalQuality

SfM_data

Regions

PairWiseMatches

Features/Regions

Provider

Matches_provider

Viewgraph

67 of 88

OpenMVG framework

67

Pictures

Image

description

Image matching

SfM

Task

Data

Provider

Data

Storage

SfM_data

Regions

PairWiseMatches

Features/Regions

Provider

Matches_provider

Libraries

Image

Features

Matching

Robust estimation

SfM

BundleAdjustment

Multiview

Camera

Graph

MatchingImageCollection

Tracking

Geometry

Viewgraph

Binaries

Pipelines

SfMInit_ImageListing

ComputeFeatures

ComputeMatches

SfM

Localization

Export

Import

EvalQuality

68 of 88

OpenMVG Import/Export

68

export

import

Blender

PLY

MetaShape

PMVS

NVM

COLMAP

MVE

OpenMVS

SphericalToCubic

HTML - WebGL

...

Kitti

Middlebury

ETH3D

DTUMVS

BlendedMVS

...

SfM

EvalQuality

Benchmark

GT poses

Images

VFX

Image

Based

Modeling

Dense

Point

Cloud

Textured

Mesh

Point Cloud

Refined Mesh

Textured Mesh

69 of 88

OpenMVG pipelines

69

SfM_data

SFM_DATA

70 of 88

SfM_Data Kesako?

SfM_Data → an interoperable data container

Image relation to camera Intrinsics/Extrinsics → Views
Intrinsics and Extrinsics data → Intrinsics, Poses,
Structure (3d/2d visibility graph) → Structure

70

71 of 88

SfM_Data Kesako?

SfM_Data → an interoperable data container

Image relation to camera Intrinsics/Extrinsics → Views
Intrinsics and Extrinsics data → Intrinsics, Poses,
Structure (3d/2d visibility graph) → Structure

71

struct SfM_Data

{

Views views; // MAP: Used images

Poses poses; // Map: Poses data

Intrinsics intrinsics; // Map: Intrinsics camera data

Landmarks structure; // Structure (3D pts with 2D observations)

};

struct View

{

std::string s_Img_path; // image path on disk

IndexT id_view; // UID of the view

IndexT id_intrinsic; // ID (unique or shared)

IndexT id_pose; // ID (unique or shared)

};

72 of 88

SfM_Data Kesako?

SfM_Data → an interoperable data container

Image relation to camera Intrinsics/Extrinsics → Views
Intrinsics and Extrinsics data → Intrinsics, Poses,
Structure (3d/2d visibility graph) → Structure

72

Shared

Views:

Id 0

Id 1

Id 2

Intrinsics

Poses

Id0: PinholeRadial3

Id 0

Id 1

Id 2

Id1: Pinhole

struct SfM_Data

{

Views views; // MAP: Used images

Poses poses; // Map: Poses data

Intrinsics intrinsics; // Map: Intrinsics camera data

Landmarks structure; // Structure (3D pts with 2D observations)

};

struct View

{

std::string s_Img_path; // image path on disk

IndexT id_view; // UID of the view

IndexT id_intrinsic; // ID (unique or shared)

IndexT id_pose; // ID (unique or shared)

};

73 of 88

Usage Toolkits

73

74 of 88

OpenMVG usage

74

OnDevice SfM (Android/ARM)

HUNGARY

Map the present & the past

SWITZERLAND

OpenCV - OpenMVG - MVE

(Feat / SfM / MVS)

75 of 88

OpenMVG usage

75

Forensics 3D Printed Prosthetic

https://www.nydailynews.com/news/world/tuc-tuc-toucan-new-3d-printed-beak-article-1.2613909

76 of 88

OpenMVG usage

3D Survey for Science dissemination

500 anniversary of Château de Chambord

76

Credits:

Drone Survey: DroneContrast,

Path planning and processing: R. Janvier (custom pipeline made from openMVG),

Sponsor and Organizer: Intelligence des Patrimoines (University of Tours and University of Orléans, Fr.)

77 of 88

OpenMVG usage

3D Survey for Science dissemination

500 anniversary of Château de Chambord)

77

Credits:

Drone Survey: DroneContrast,

Path planning and processing: R. Janvier (custom pipeline made from openMVG building blocks!),

Sponsor and Organizer: Intelligence des Patrimoines (University of Tours and University of Orléans, Fr.)

78 of 88

OpenMVG usage

Civil engineering (stone degradation monitoring), Volubilis ,Morocco.

78

Credits: University of Orléans, Fr.

79 of 88

^{"Collaborative Augmented Reality on Smartphones via Life-long City-scale Maps" ISMAR 2020}

79

80 of 88

Challenges &

Opportunities

80

81 of 88

Challenges and opportunities

Understand the community typical usage and needs → OpenMVG 2019 Survey

Requests

SLAM, Laser + SfM,
Speed (Image Matching/SfM), Accuracy,
MVS
Feature Detection & Matching,
Geodesy

81

Longevity	Dataset size	Pipelines	Derivative work
40% uses OpenMVG for 3+ years	1000+ images	Incremental SfM prefered pipeline	30% users build custom pipelines from OpenMVG

In order to understand better our community we are running from time to time a survey. It allows us to obtain feedback from the community and have a better picture about their usage, they desired features.

Our last survey was launched in 2019 and we were able to gather a representative set of 50 answers.

We were glad to see that the community is using OpenMVG since a long time (most of our users are using it for more than 3 years).

It also gave us meaningful information about the size of the dataset or the SfM pipeline that the community is using (they are processing larger and larger datasets)

Finally an interesting point was to note that ⅓ of our community is able to leverage OpenMVG and create its own custom pipelines (Things that we wanted in the initial vision of the project - empower the community)

We also found that without surprise our community is interested by others related SLAM, Laser data and the additional points you see listed here (but our community cannot address them all)

82 of 88

Opportunities/Challenges

Awareness

Being known, used

Accessibility

Making code available

share code with your papers

Community

Getting contribution

Foster reproducible research

82

Speed

Code readability vs speed vs accuracy

Relevance

Keep contribution aligned with people needs
Aligns interests of Machine Learning and SFM communities

Here is the best summary I could do as today for the OpenMVG project Opportunities and challenges:

They are oriented around awareness, accessibility, community building, speed and relevance of the work.

Those opportunites/challenge seems pretty generic and feel free to remember them and see how they relate to your own projects..

You have to face it, it is hard to being know, being used…and getting contribution.
Making code available, following the specific development rules of a 3rd party project is not the main thing we want to do as researcher…
But it is very nice to see that some of us; researcher, engineers are pushing towards creating a open culture where we share knowledge and make code available, usable.

What people want is SPEED, SPEED, they expect a open source software to be FREE and as fast as commercial software that are fine tuned by army of engineers. As a project and community you have to carefully explain multiple time that the community is doing this on free time and that they are welcome to contribute to the project.

Lastly on the relevance, it is hard to keep an alignment of the work that interest you personally and the feature that interest your community.

One challenge that the computer vision community is facing today is the bridge between the Machine Learning and SfM communities (make the researcher collaborate and use the best of their worlds together)

….

83 of 88

Where are we ‘OpenMVG perspectives?

83

Have

WIP

84 of 88

[Context] OpenSource SfM toolkits

84

Data as show on Github on april 8th 2021

Project	Created in	License	#Contributors	#Releases	#GithubStars	#GithubForks	Continuous Integration
Bundler-SfM	2008	GPL	11	4	1303	459	NO
OpenMVG	2013	MPL2	74	17	3460	1.3k	YES
MVE	2014 (SFM)	BSD 3-Clause license	28	X	750	358	YES
Telesculptor	2014	BSD 3-Clause license	19	26	396	129	YES
TheiaSfM	2015	New BSD license	30	7	650	239	NO
OpenSFM	2015	Simplified BSD license	69	11	2031	601	YES
Colmap	2018	BSD 3-clause license	57	16	2832	757	YES

85 of 88

Take Home Message

85

86 of 88

What’s next

Scalability

Large scale image matching - loop closure detection - generic VLAD
Polynomial SIFT (3 times less memory, same or better results than SIFT)
New SFM Pipelines

Speed + robustness: N-view initialization - Stellar SfM

Align the interests of ML and CV communities (Kapture?)

Please join us for better features/matches, ...

86

87 of 88

Take home message

Flexible framework for Reproducible Research

Easy interoperability

SfM_Data container (JSON/Bin/XML)

Convenient Import/Export

Community & knowledge focused

“Together we achieve more”
Please join the OpenMVG project!

87

https://github.com/openMVG/openMVG; openMVG/awesome_3DReconstruction_list

88 of 88

Thank you

OpenMVG

88