1 of 68

Just One Image is All It Takes

Rectification, Auto-Calibration and Scene Parsing from Affine-Correspondences of Repetitive Textures

Presenter: James Pritts

Czech Technical University in Prague

Applied Algebra and Geometry Group (AAG)

Czech Institute of Informatics, Robotics and Cybernetics (CIIRC)

Funded by Robotics for Industry (R4I) Robotics for Industry 4.0 (reg. no. CZ.02.1.01/0.0/0.0/15_003/0000470)

Tutorial: Affine Correspondences and their Applications

Daniel Barath, Dmytro Mishkin, James Pritts, Levente Hajder

final

2 of 68

Collaborators

Viktor Larsson
Zuzana Kukelova
Ondrej Chum
Jiri Matas
Yaroslava Lochman
Denys Rozumnyi
Oles Dobesovych
Rostyslav Hryniv
Pawan Kumar

2

3 of 68

Talk Outline

Applications

The Correspondence Problem

Camera Geometry

Minimal Solvers

Complementary Features

Limitations

Prior Work

Q&A

3

4 of 68

What good are Repetitive Textures?

4

Restore Invariants

Encode Invariants

Solve

Assumption: Coplanar repeats are related by isometries

5 of 68

Rectification

5

input

rectification

input

rectification

input

rectification

Pritts et al., Minimal Solvers for Radially-Distorted Conjugate Translations, TPAMI 2021
Pritts et al., Minimal Solvers for Rectifying from Radially-Distorted Scales and Change of Scales, IJCV 2020
Lochman et al, Minimal Solvers for Single-View Lens-Distorted Calibration, In WACV 2021

6 of 68

Gravity Direction

6

7 of 68

Symmetry Detection and Segmentation

7

[7] Pritts et al. Rectification and Segmentation of Coplanar Repeated Patterns. In CVPR, 2014

Wallpaper

Arbitrarily repeated

Sets of corresponding LAFs

7/23

wallpaper

isometries

rotational symmetry

Pritts et al, Detection, Rectification and Segmentation of Coplanar Repeated Patterns, In CVPR 2014

input

8 of 68

Ridiculously Wide-Baseline Stereo Matching

8

ortho-photos

first input

second input

undistorted image

9 of 68

Auto-Calibration and Scene Parsing

9

input

vanishing point labeling

vanishing line labeling

undistorted

1st rectified plane

2nd rectified plane

10 of 68

Detecting Coplanar Repeats

10

11 of 68

What is a Coplanar Repeat?

11

imaged translational symmetries

X and X′ are coplanar scene points so that

imaged rigid transform

rectified patches

distortion

homography

undistortion

where

Coplanar Repeats are image regions related by imaged rigid transforms

12 of 68

Detection and Representation

12

Extraction

Construction

Description

Matas et al, Robust Wide-Baseline Stereo from Maximally Stable Extremal Regions, In BMVC 2002
Obdrzalek and Matas, Object Recognition using Local Affine Frames on Distinguished Regions, In BMVC 2002

13 of 68

Affine-Covariant Scene

13

Matas et al, Robust Wide-Baseline Stereo from Maximally Stable Extremal Regions, In BMVC 2002
Obdrzalek and Matas, Object Recognition using Local Affine Frames on Distinguished Regions, In BMVC 2002

14 of 68

Point Parameterization of Affine-Covariant Feature

14

normalized patch

Pritts et al., Minimal Solvers for Radially-Distorted Conjugate Translations, TPAMI 2021

detections

15 of 68

Affine-Covariant Regions vs Points

Good Correspondences

Region Measurements

15

Perspective Image

Affine Rectification

≠

unequal area

equal area

Chum and Matas. Planar Affine Rectification from Change of Scale. In ACCV, 2010.
Ohta et al..: Obtaining surface orientation from texels under perspective projection. In: IJCAL, Vancouver, Canada (1981) 746–751
Criminisi et al. Shape from texture: homogeneity revisited. In BMVC, 2000.

Why not SIFTS? (similarity covariant)

16 of 68

Repetitive Texture Detection by Appearance Clustering

16

Single-link agglomerative clustering

17 of 68

Correspondence Pipeline

17

Tentative coplanar repeats

Descriptor clustering

Affine-Covariant Region Detection

Affine frame representation & description

18 of 68

Camera Geometry

18

19 of 68

Pinhole Camera

19

Hartley and Zisserman. Multiple-View Geometry. Book, 2003

20 of 68

Pinhole Camera Viewing Scene Plane

20

Hartley and Zisserman. Multiple-View Geometry. Book, 2003.

21 of 68

Radial Lens Distortion

Cameras with large lens distortions are commonly used

Simple and effective: radial and uniform

Rectification Solvers

Need: Satisfy constraints in real-projective plane
Biased model fitting, if ignored

RANSAC

Spatial Verification problems
Can we upgrade in a refinement stage?

21

GoPro Hero 4 Wide image

Fitzgibbon. Simultaneous linear estimation of multiple view geometry and lens distortion, In CVPR, 2001.

barrel distortion

radial component

22 of 68

Division-Model of Radial Lens Undistortion

one-parameter division model

22

distortion center subtracted

image point

pinhole point

image plane

Image sizes:

Fitzgibbon. Simultaneous linear estimation of multiple view geometry and lens distortion, In CVPR, 2001.

23 of 68

Distorted Chess Board

23

24 of 68

Imaged Vanishing Point Geometry

24

Matthew Antone. Robust camera pose recovery using stochastic geometry. thesis, 2001.

vanishing point

25 of 68

Avoid Image Space for Solver Design

Analytic functions for distortion and undistortion

Project rays to image space

25

Image Correspondences

26 of 68

Minimal Solvers for Undistortion, Rectification and Auto-Calibration

27 of 68

Rectification and Reversing the Imaging Process

Camera viewing a scene plane

27

perspective

image point

scene plane point

Perspective Image

Pre-imaging decomposition

Metric Rectification

Affine Rectification

similarity

affinity

projectivity

Hartley and Zisserman, Multiple-View Geometry, 2003

28 of 68

Rectification of Distorted Coplanar Repeats

Translations and Reflections

28

Rigid Transformations

Pritts et al, Minimal Solvers for Radially-Distorted Conjugate Translations, TPAMI 2021
Pritts et al, Minimal Solvers for Rectifying from Radially-Distorted Scales and Change of Scales, IJCV 2020
Pritts et al, Detection, Rectification and Segmentation of Coplanar Repeated Patterns, In CVPR 2014

29 of 68

Joint Undistortion and Rectification

29

Pritts et al, Minimal Solvers for Radially-Distorted Conjugate Translations, TPAMI 2021
Pritts et al, Minimal Solvers for Rectifying from Radially-Distorted Scales and Change of Scales, IJCV 2020
Pritts et al, Detection, Rectification and Segmentation of Coplanar Repeated Patterns, In CVPR 2014

Ignore distortion it in the first phase

Model in the final optimization step (LO)

Jointly Solve for Undistortion & Rectification

30 of 68

Warp Error

30

12 px

32 px

65 px

Image size: 3000x2250 px

estimated rectification

imaging by ground truth

affine ambiguity

Pritts et al, Coplanar Repeats by Energy Minimization, In BMVC 2016
Lochman et al, Minimal Solvers for Single-View Lens-Distorted Calibration, In WACV 2021

Increasing Undistortion Parameter Estimation Error

31 of 68

Conjugate Translations

31

Schaffalitzky et al. Planar Grouping for Automatic Detection of Vanishing Lines and Points. Image and Vision Computing, Volume 18, page 647--65

32 of 68

Radially-Distorted Conjugate Translations

32

Eliminate unknown homogeneous scalar
Generates two linear independent equations, 2 constraints per correspondence
Coincidence constraint

Pritts et al, Radially-Distorted Conjugate Translations, In CVPR, 2018
Pritts et al, Minimal Solvers for Radially-Distorted Conjugate Translations, TPAMI 2021

33 of 68

Eliminating Vanishing Point (EVP) Solvers

Radially-Distorted Conjugate Translations Solvers

Minimal configuration of coplanar repeats

33

Constraints

Input

Undistortion

Rectification

One-direction EVP solvers

Two-direction EVP solvers

(1–2) affine-covariant rgn cspond provides 3 pt csponds
(3–4) similarity-covariant rgn cspond provides 2 pt csponds

(1)

(2)

(3)

(4)

EVP variants

One-direction variant

Two-direction variant

Radially-Distorted Conjugate Translations

Pritts et al, Radially-Distorted Conjugate Translations, In CVPR, 2018
Pritts et al, Minimal Solvers for Radially-Distorted Conjugate Translations, TPAMI 2021

l	2 DOF vanishing line
u	2 DOF vanishing line
s_i^u	1 DOF magnitude trans.
	1 DOF div. model param.
s_i^u	constrained to be the same for at least two

The Eliminated Vanishing Point solvers use coplanar point correspondences translated in the same direction, which include translational symmetries. The minimally parameterized transformation that maps translated points to their correspondences is called a conjugate translation since it defines the sequence of pre-imaging, translation and imaging. The geometry for rectilinear cameras is shown on the left of the gray box, and for radially-distorted camera on the right of the gray box. The translation directions meet at the vanishing point u, and all vanishing translation directions of a scene plane are coincident with its vanishing line l.

The constraint equations for a radially-distorted conjugate translation are listed in the red box. The constraints are linear in the vanishing point, so it can be eliminated after rearrangment. The remaining unknowns are the vanishing line, division-model parameter and the relative scale of translation. The polynomial system that arises from the rank deficiency on the coefficient matrix M is solved using the Groebner-basis method.

The green box shows the minimal correspondence configurations on the scene plane that are used by the proposed solvers. In configurations (2) and (4), we relax the constraint that all points translate with the same magnitude, and in (3) and (4) we admit two translation directions.

Covariant region correspondences are used to reduce the minimal sample size: configuration (1) needs just one region correspondence; configurations (3) and (4) can be used with two similarity-covariant region correspondences..

An example result from these solvers is shown for a fisheye lens.

*//////////////////***

saturation of an ideal gives a way to factor out known solutions of an ideal. Given

that the set V (f) is a set of unwanted solutions to I then sat(I, f) is an ideal where these

solutions have been removed.

If we want to remove the set given by f = 0 we introduce a new synthetic variable s and

add the polynomial sf − 1 to the ideal.

34 of 68

Meets of Joined Points

34

image of vanishing line

imaged vp

Pritts et al, Radially-Distorted Conjugate Translations, In CVPR, 2018
Pritts et al, Minimal Solvers for Radially-Distorted Conjugate Translations, TPAMI 2021

35 of 68

Meets of Joined Affine-Covariant Correspondence

35

Pritts et al, Radially-Distorted Conjugate Translations, In CVPR, 2018
Pritts et al, Minimal Solvers for Radially-Distorted Conjugate Translations, TPAMI 2021

36 of 68

Eliminating Vanishing Line (EVL) Solver

Meets of Joins Solver

36

l	2 DOF vanishing line
	1 DOF div. model param.

3 directions are needed to construct

Best Minimal Solution Selection (BMSS)

From 10 meets available — only 3 are needed
Minimize the sum of symmetric transfer errors

Pre-emptive verification in RANSAC
Fast — EVL solver needs only 0.5 µs

Input

Undistortion

Rectification

Pritts et al, Radially-Distorted Conjugate Translations, In CVPR, 2018
Pritts et al, Minimal Solvers for Radially-Distorted Conjugate Translations, TPAMI 2021

Constraints

An affine-covariant region correspondence provides four translation directions in the scene plane, colored red, green, blue and cyan, which in shown in the top left. Any of the endpoints of the colored line segments can be joined to compute vanishing points that must meet the vanishing line of the scene plane. This geometry is shown by the undistorted image. The vanishing line can be eliminated from the polynomial constraints, which greatly simplifies the solver. The division model parameter is found as the roots of a quartic, and the vanishing line is found by back substitution.

Three vanishing points are required to constrain the three degrees of freedom of the vanishing line and division model parameter. The eliminated vanishing line solver has a mean time to solution of half a microsecond.

One affine covariant region correspondence provides 10 possible combinations of joins to generate the three vanishing points. Since the solver is fast, the joins can be partitioned into complementary subsets of minimal samples and unused joins, and cross validation can used to select the most accurate sample. This step is easily included in RANSAC to eliminate unneeded consensus set estimation, which is expensive.

37 of 68

Clever Constraint Design Matters

37

Solvers	AC Configuration	Solutions	Complexity
Radially-Distorted Conjugate Translations	1	4	Groebner Basis, Elimination template 14x18
Meets of Joined Csponds.	1	4	quartic

VS

38 of 68

The Equal-Rectified Scales Constraint

Geometric invariant of affine-rectified space is used to put algebraic constraints on the unknowns of .

38

rectifying function

Imaged Scene Plane

Rectified Scene Plane

Pritts et al. Rectification from Radially-Distorted Scales. In ACCV, 2018.
Pritts et al. Minimal Solvers for Rectifying from Radially-Distorted Scales and Change of Scales. IJCV, 2020.

39 of 68

Corresponded Sets (instead of Correspondences)

39

222

32

4

Pritts et al. Rectification from Radially-Distorted Scales. In ACCV, 2018.
Pritts et al. Minimal Solvers for Rectifying from Radially-Distorted Scales and Change of Scales. IJCV, 2020.

40 of 68

Directly-Encoded Scale

40

Rectified scale is the determinant of its rectified points

rectifying

Pritts et al. Rectification from Radially-Distorted Scales. In ACCV, 2018.
Pritts et al. Minimal Solvers for Rectifying from Radially-Distorted Scales and Change of Scales. IJCV, 2020.

l	2 DOF vanishing line
	1 DOF div. model param.

41 of 68

Directly-Encoded Scale (DES) Solvers

41

Pritts et al. Rectification from Radially-Distorted Scales. In ACCV, 2018.
Pritts et al. Minimal Solvers for Rectifying from Radially-Distorted Scales and Change of Scales. IJCV, 2020.

Input

Undistortion

Rectification

Geometric invariant: coplanar repeats have the same scale in the affine-rectified space

DES solvers

Undistortion

Rectified cut-out

Input

Constraints

l: 2 DOF vanishing line
: 1 DOF div. model parameter

Rectified scale is the determinant of its rectified points

The Directly Encoded Scale Solvers use the scale constraint that two instances of rigidly-transformed coplanar repeats occupy identical areas in the scene plane and in the affine-rectified image of the scene plane.

These solvers use affine-covariant regions to represent imaged coplanar repeats.

The rectified scale, denoted si, is the area of the triangle defined by the affine-rectified image of the three distorted points that parameterize a region detection. The area is computed as the determinant of the triangle’s vertices. The rectified points are functions of the measured distorted points, the unknown division model parameter, and the vanishing line. The rectified scales of coplanar repeats are eliminated pairwise by setting them equal. The equations generate a polynomial system of degree four with three unknowns, two for the vanishing line and one for the division model parameter.

There are three minimal configurations of regions for this problem shown in the green box: three region correspondences, denoted 222; a corresponded set of three regions and a region correspondence, denoted 32; and a corresponded set of four region correspondences, denoted 4. A solver is generated for each configuration using Groebner basis.

////****////

These constraints are complicated and required sampling different bases by creating different solvers. Solver stability was measured on simulated scenes and the most stable solver was kept.

42 of 68

Change of Scale Due to Imaging

Relative scale change is only a function of the vanishing line and undistortion function.

Idea: Linearize affine rectification and compute Jacobian determinant

42

Pritts et al. Rectification from Radially-Distorted Scales. In ACCV, 2018.
Pritts et al. Minimal Solvers for Rectifying from Radially-Distorted Scales and Change of Scales. IJCV, 2020

smaller rel. scale

larger rel. scale

43 of 68

Change of Scale

43

rectifying

Pritts et al. Rectification from Radially-Distorted Scales. In ACCV, 2018.
Pritts et al. Minimal Solvers for Rectifying from Radially-Distorted Scales and Change of Scales. IJCV, 2020

Inhomogenous

Formulation!

44 of 68

Change of Scale (CS) Solvers

44

Rectification

Change of Scale

Change of Scale Due to Imaging

Constraints

l : 2 DOF vanishing line
: 1 DOF div. model parameter

The Jacobian determinant approximates

change of scale of the rectifying and undistorting function near the image point

CS

solvers

Undistortion

Rectified cut-out

Input

Minimal configuration of coplanar repeats

Geometric invariant: coplanar repeats have the same scale in the affine-rectified space

Pritts et al, Minimal Solvers for Rectifying from Radially-Distorted Scales and Change of Scales, IJCV 2020

The Change of Scale solvers also restore the equal-scale invariant of affine-rectified space.

The Jacobian determinant of the rectifying transformation is used to induce local constraints on the imaged vanishing line and the unknown parameter for the division model. The Jacobian determinant gives the change of scale at a point. The unknown rectified scales are expressed as a product of the distorted scale of the region and the change of scale due to rectification. As before, unknown rectified scales are eliminated pair-wise, and the same minimal configuration arise. Solvers are generated for all configurations.

The inverse Jacobian determinant gives the change of scale due to imaging. This is rendered on the images as an alpha-blended colormap, where pixels with vanishing relative scales are more purple and pixels with larger relative scales are more orange. The image of the centroid of the detected rectified coplanar repeats is used to set the reference scale. Importantly, the dense change of scale enables automated image rectification. Bounds are set on the relative scale change so that regions close to the vanishing line don’t blow up the rectification.

45 of 68

Clever Constraint Doesn’t Matter

45

Solvers	AC Configuration	Solutions	Complexity
Directly Encoded Scale (DES)	222	54	Groebner Basis, Elimination template 133x187
Change of Scale (CS)	222	54	Groebner Basis, Elimination template 133x187

VS

DES

CS

46 of 68

Vanilla RANSAC performance

46

47 of 68

Metric Upgrade from Affine-Rectified Rigid Transforms

47

Pritts et al, Detection, Rectification and Segmentation of Coplanar Repeated Patterns, In CVPR 2014

48 of 68

Metric Upgrade from Affine-Rectified Rigid Transforms

48

Pritts et al, Detection, Rectification and Segmentation of Coplanar Repeated Patterns, In CVPR 2014

where

3 unknowns for (global)
1 unknown for every corresponded set

49 of 68

Semi-Metric Upgrade from Affine-Rect. Glide Reflections

49

Pritts et al., Detection, Rectification and Segmentation of Coplanar Repeated Patterns. In CVPR, 2014

50 of 68

Semi-Metric Upgrade from Affine-Rect. Glide Reflections

50

Pritts et al., Detection, Rectification and Segmentation of Coplanar Repeated Patterns. In CVPR, 2014

Point incidence constraint
4 unknowns for
Generates linear constraints
Anisotropic ambiguity exists

51 of 68

Maximum-Likelihood Estimation

51

LO-RANSAC framework

(1) sample from tentatively grouped repeats → (2) joint hypothesis on undistortion and affine rectification

→ (3) metric upgrade → (4) locally optimize on maximal consensus sets → (1) until converged

Pritts et al. Rectification and Segmentation of Coplanar Repeated Patterns. In CVPR, 2014

52 of 68

The Best of Both Worlds?

52

Pritts et al.: 4 point correspondences

Covariant regions are noisy thus provide less accuracy

Wildenauer et al.:

Antunes et al.:

5 circular arcs

7 circular arcs

Circular arcs are hard to group as imaged parallel scene lines

Wildenauer, 3 circular arcs

53 of 68

Complementary Features Along Manhattan Directions

53

Imaged Translational Symmetries

Imaged Parallel Scene Lines

Lochman et al, Minimal Solvers for Single-View Lens-Distorted Calibration, In WACV 2021

54 of 68

Configurations of Vanishing Points

54

3 distinct VPs

Coplanar

Orthogonal

vanishing line

image of an absolute conic

2 VPs are coincident

2 distinct VPs

Lochman et al, Minimal Solvers for Single-View Lens-Distorted Calibration, In WACV 2021

55 of 68

Sampling Feature Configurations

55

Hybrid RANSAC

Tentative Groups of Regions

Tentative Groups of Arcs

Undistortion

Rectifications

vanishing point

vanishing line

undistorted images of parallel lines

image of the absolute conic

Family of Minimal Solvers

Common Constraints

point csponds

circular arcs

Samayang 12 mm fisheye lens

Camposeco et al, Hybrid Camera Pose Estimation, In CVPR 2018
Lochman et al, Minimal Solvers for Single-View Lens-Distorted Calibration, In WACV 2021

56 of 68

Scene Parsing

56

input

vanishing point labeling

vanishing line labeling

undistorted

first-plane rectified

second-plane rectified

Lochman et al, Minimal Solvers for Single-View Lens-Distorted Calibration, In WACV 2021

57 of 68

Manhattan Frame Rectification

57

Input

Undistorted

Manhattan Planes Rectified

58 of 68

Percentage of Top-1 Solutions of Focal Length (AIT)

58

Solver	% of Top-1
	1.5%
	10.2%
	15.5%
	21.7%
	25.4%
	25.7%

SOTA

Proposed

59 of 68

AIT Dataset Performance

59

60 of 68

Disentangling Focal Length and Lens Undistortion

60

61 of 68

Reality Check

62 of 68

AIT Dataset Performance

62

63 of 68

Shape Parameters of Affine-Covariant Region

63

64 of 68

Frobenius Norm is Geometric Error of Shapes

64

E. Riba, D. Mishkin, et al., Kornia: an Open Source Differentiable Computer Vision Library for PyTorch, In WACV 2020

Thanks for the image Dima!

65 of 68

Prior Work

Fitzgibbon. Simultaneous linear estimation of multiple view geometry and lens distortion, In CVPR, 2001.

Schaffalitzky et al. Planar Grouping for Automatic Detection of Vanishing Lines and Points. Image and Vision Computing, Volume 18, page 647--65

Chum and Matas. Planar Affine Rectification from Change of Scale. In ACCV, 2010.

Ohta et al..: Obtaining surface orientation from texels under perspective projection. In: IJCAL, Vancouver, Canada (1981) 746–751

Criminisi et al. Shape from texture: homogeneity revisited. In BMVC, 2000.

Kukelova et al. Radial Distortion Homography. In CVPR 2015

65

The papers that are most directly related to the work presented here.

66 of 68

Tutorial Bibliography

66

Y. Lochman, O. Dobosevych, R. Hryniv, and J. Pritts. Minimal Solvers for Single-View Auto-Calibration. In WACV, 2021
J. Pritts, Z. Kukelova, V. Larsson, Y. Lochman, and O. Chum. Minimal Solvers for Rectifying from Radially-Distorted Conjugate Translations. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2021
J. Pritts, Z. Kukelova, V. Larsson, Y. Lochman, and O. Chum. Minimal Solvers for Rectifying from Radially-Distorted Scales and Change of Scales. International Journal of Computer Vision, 128(4), 950–968, 2020
J. Pritts, Z. Kukelova, V. Larsson, and O. Chum. Rectification from Radially-Distorted Scales. In ACCV, 2018
J. Pritts, Z. Kukelova, V. Larsson, and O. Chum. Radially-Distorted Conjugate Translations. In CVPR, 2018
J. Pritts, D. Rozumnyi, M. P. Kumar, and O. Chum. Coplanar Repeats by Energy Minimization. In BMVC, 2016
J. Pritts, O. Chum, and J. Matas. Detection, Rectification and Segmentation of Coplanar Repeated Patterns. In CVPR, 2014

67 of 68

Q&A Session

67

Thank You!

68 of 68

[1] H. Stewenius. Gröbner Basis Methods for Minimal Problems in Computer Vision. Centre for Mathematical Sciences, Lund University, 2005

68

Pose problem,

port problem

to ℤp

Port to ℝ

Build matrix based Gröbner basis code

Compute number

of solutions

Pose problem

over ℝ

Backsubstitute

Compute action matrix, solve eigen problem

Compute

Gröbner basis

Offline:

Online: