Chapter 16 Image Matching

16.1 Introduction

16.1.1 Image Matching and Object Reconstruction

object reconstruction: determination of object's pose or shape

image matching and object reconstruction needed for

- time-varying sequences for recognizing parts in motion
- visual inspection of geometry of 3D parts
- medical diagnosis of beating hearts
- monitoring land use
- deriving topographic maps from satellite or aerial imagery
- analysis of slices of computer tomography images

: object mapped into images

: object to image mapping transformations

: describe illumination, reflectance, sensing, ...

assumption: transformations are one to one

assumption implicitly excludes transparent surfaces or occlusions

: unknown parameters specifying geometry of object

: unknown parameters specifying reflectance property of object

: unknown parameters specifying pose of camera

: unknown parameters specifying atmospheric response

mapping can be summarized as:

general setup of object reconstruction and image matching

(a) object mapped to via transformations

(b) setup for two perspective images

=====Fig. 16.1=====

image can be predicted from by:

16.1.2 The Principle of Image Matching

: two digital or digitized images or image patches

: size (point tracking) to
(satellite image registration)

: points of images

: coordinates of points

: intensities of points

: specified geometric spatial-mapping function

: set or vector of unknown parameters

if corresponds to , their coordinates related by:

: intensity-mapping function containing intensity relation

: unknown vector

intensities on one image related to other image:

complete model of image matching:

: may be deterministic, stochastic, and/or piecewise continuous

correspondence of : relate to same point on object

problem of image matching or correspondence consists of:

- finding all corresponding points
- determining parameters of mapping functions

: point attributes derived from intensity functions in neighborhood

: points in a neighborhood around

image matching solution achieved in three-step procedure

- select appropriate image features in one or in both images

e.g. interest operator to derive list of interesting points or edges - find corresponding point pairs with similarity and consistency

with from first list and from second list

similarity: based on attributes and properties of intensity function

consistency: based on degree to which spatial-mapping function fulfilled - interpolate parallaxes between selected feature pairs

16.1.3 Image Matching Procedures

properties of some correspondence algorithms for image matching

=====Table 16.1=====

similarity measures reflect the assumed intensity-mapping function

- same intensity:
:

e.g. Horn and Schunck optic flow, minimum sum of absolute difference - linear intensity mapping: :

e.g. maximum cross-correlation

consistency measure or interpolation method on stereo images:

- (a) same size: surfaces parallel to image plane
- (b) contraction: locally tilted planar surface patch
- (c) expansion: smooth or piecewise smooth surface
- (d) difference: piecewise smooth with occlusions

precision of image matching and edge detection (all figures in pixels)

=====Table 16.2=====

=====Garfield 17:28=====

16.2 Intensity-Based Matching of One-Dimensional Signals

: replacing : intensity of first image

: replacing : intensity of second image

: replacing : location of first image

: replacing : location of second image

: observational noise component

1D intensity-based matching model:

16.2.1 The Principle of differential Matching

assumption: no intensity changes due to viewing direction

: location in first image

: unknown deformation at to produce corresponding point

point in first image corresponds to point in second image

nonlinear model valid for all observed values :

: additive noise; independent and identically distributed

: mean zero, variance

assumed observation process: to the right of

=====Fig. 16.4=====

: approximate values of unknown deformation

: unknown correction for unknown value

abbreviations:

nonlinear model can be written as:

linearize around point to obtain:

for some and where

assumption: does not vanish and second-order term negligible

linearized model with known: , unknown:

or explicitly

easily determine random variable assuming :

or explicitly

thus

principle of the applied differential approach to estimate local deformation

=====Fig. 16.5=====

16.2.2 Estimating an Unknown Shift

assumption: only uniform shift i.e.
,

: initial approximation for , thus

linearizing around for each :

linearized model can be expressed as:

or in short

minimizing by choosing appropriate

from which follows the estimate

16.2.3 Estimating Unknown Shift and Scale

: fixed reference point

augment model by assuming transformation contains unknown scale:

in reduced coordinates

linear model reads as:

linearized model:

use Taylor's expansion for linearized model and minimize , thus

16.2.4 Compensation for Brightness and Contrast

: change in contrast

: change in brightness

nonlinear model with brightness and contrast but without scale parameter:

linearized model:

normal equation system for least-squares solution to minimize :

16.2.5 Estimating Smooth Deformations

used for larger windows but transformation still smooth

16.2.6 Iterations and Resampling

iterative estimation scheme: if initial approximations are crude

16.2.7 Matching of Two Observed Profiles

both profiles corrupted by noise: reduce to methods developed so far

16.2.8 Relations to Cross-Correlation Techniques

cross-correlation model: assumes a shift between two corresponding image

=====Oldie 33:79=====

16.3 Intensity-Based Matching of Two-Dimensional Signals

differential techniques for intensity-based matching expanded to 2D

16.3.1 The Principle and the Relation to Optical Flow

nonlinear model:

with

assumption: approximate values of unknown known

related to optical flow equation: i.e. noise term omitted:

linearize by Taylor's expansion:

let , we get optical flow equation:

16.3.2 Estimating Constant-Shift Parameters

simplest model for matching:

linearized model:

normal equations to minimize :

16.3.3 Estimating Linear Transformations

: eight unknown parameters

model to match two small windows:

linearized model:

to minimize , normal equation matrix :

eight unknown parameters:

right-hand side :

solution: normal equation system

: six corrections for geometric transformation

: corrections for radiometric parameter

16.3.4 Invariant Points

(a),(b): corner points; scale difference cannot be determined

(c),(d): circularly symmetric; rotation cannot be determined

=====Fig. 16.8=====

16.4 An Interest Operator

16.4.1 Introduction

interesting has several meanings, depending on context:

- distinctness: distinguishable from immediate neighbors

distinct points: corners, blobs, highly textured places, etc. - invariance: position and selection invariant w.r.t. geometric distortion

invariance and distinctness: influence all subsequent steps in analysis - stability: position and selection invariant w.r.t. viewing

stability: ensures interesting points in image correspond to object points

corner points of polyhedra: stable

T-junction: unstable since it results from occlusions

stability: decisive for image-matching, 3D reconstruction

=====Nalwa,*A Guided Tour of Computer Vision*, p. 137===== - uniqueness: global separability, i.e. imagewide separability

distinctness: aims at local separability

uniqueness: to avoid locally distinct but repetitive features or points

uniqueness: closest notion to interestingness - interpretability: requires extracted points to have meaning

e.g. corners, junctions of lines, centers of circles, rings, etc.

an interest operator with a three-step procedure:

- selection of optimal windows: search for local maxima of average gradient magnitude
- classification of the image function within the selected windows

classification distinguishes between types of singular points

e.g. corners, rings, spirals, isotropic texture - estimation of the optimal point within the window as the classification

precise for corners and for centers of circular symmetric features

16.4.2 Estimating Corner Points

16.4.3 Evaluation and Classification of Selected Windows

16.4.4 Selection of Optimal Windows

16.4.5 Uniqueness of Selected Points

uniqueness of selected points: based on similarity derived from attributes

highest uniqueness measure: points with no features in common with other

repetitive features show low uniqueness

uniqueness measure represented by the area of the circles

=====Fig. 16.11=====

=====joke=====

16.5 Robust Estimation for Feature-Based Matching

16.5.1 The Principle of Feature-Based Matching

three steps of feature-based matching:

- selecting features by using some interest operator
- finding correspondences by using similarity and consistency measure
- interpolating between parallaxes by spatial-mapping function

individual steps for similarity measure:

- similarity between extracted features:

form preliminary list of correspondences, including weights - mapping function hypothesis: found by robust estimation procedure,
similar to relaxation techniques

by enforcing one-to-one correspondence between image features - final parameters of mapping function: by maximum likelihood estimate allowing rigorous evaluation of the match

: parameters to be estimated

: observed measurement

maximum likelihood (ML) estimate:

: prior information about parameters

Bayesian estimate: maximum a posteriori (MAP) estimate:

=====J. V. Beck and K. J. Arnold,

=====

16.5.2 The Similarity Measure

16.5.3 Heuristics for Selecting Candidate Pairs

finding candidate pairs of features: first step after selecting image features

finding candidate pairs: to reduce algorithmic complexity in final match

finding candidate pairs: all types of a priori knowledge may be included

heuristics and strategies for selecting candidate pairs:

- expected parallax may be used to exclude unlikely feature pairs
- similarity of features required to be above certain threshold
- uniqueness of selected points used to reduce number of candidate pairs

16.5.4 Robust Estimation for Determining the Spatial-Mapping Function

preliminary correspondences must be compared to see if consistent with model

most general model applied: local smoothness constraint almost everywhere

finite-element description of spatial-mapping function would be appropriate

robust estimation: used only for finding good hypothesis for match

images with mostly translation , no rotation (identity matrix)

=====Fig. 16.12=====

16.5.5 Evaluating the Final Result

result of finding most likely parameters of mapping function must be evaluated:

- to be sure the solution is correct
- to have quantitative measure for parameter quality

apply classical hypothesis tests to evaluate the result:

- global check if data and model are consistent using sum of squared residuals
- precision of estimated parameters can be determined
- result termed reliable only if enough points used to determine mapping
- projection of one image into other: decisive check on matching correctness

16.6 Structure from Stereo by Using Correspondence

=====Experiment: close one eye and put pen cap back=====

implication of ambiguous correspondences between image points

=====Nalwa, *A Guided Tour of Computer Vision*, Fig. 7.3=====

monotonic-ordering assumption: conjugate image points have same order

violation of the monotonic-ordering assumption

=====Nalwa, *A Guided Tour of Computer Vision*, Fig. 7.7=====

occlusion as an impediment to stereo

=====Nalwa, *A Guided Tour of Computer Vision*, Fig. 7.4=====

scene recovered from a pair of stereo images

=====Nalwa, *A Guided Tour of Computer Vision*, Fig. 7.9=====

large windows: to establish global correspondence

small windows: using global correspondence for local correspondence

stochastic relaxation as a tool for correspondence establishment

=====Nalwa, *A Guided Tour of Computer Vision*, Fig. 7.10=====

assumption: interior orientation of cameras determined by calibration

for reasons of stability: at least five groups of points used for calibration

16.6.1 Epipolar Geometry

image matching tremendously simplified: if relative orientation known

relative orientation known: 2D search reduced to 1D by epipolar geometry

: projection centers

: baseline length

: focal lengths

: principal points assumed to be two image coordinate origins

: two image coordinate systems

: 3D object point

: 2D image coordinates for the point

collinearity condition: five points
lie in one plane

epipolar plane : the plane
lie in

epipolar lines : intersection lines of epipolar plane and image
planes

different points: have different pairs of epipolar lines

all epipolar planes: form pencil of planes passing through baseline

epipoles : epipolar line intersection point

epipoles : intersection of baseline and image planes

in general: epipolar lines are not parallel

epipolar geometry of a general image pair

=====Fig. 16.13=====

epipolar plane : defined by

given one image point: epipolar line fixed and sits on this
line

since epipolar line known: search is necessary in only one dimension

epipolar line constraint: strongest constraint in image matching

epipolar line constraint: used as soon as available

: principal points

: image coordinate system

parallel to

epipolar lines identical and parallel to baseline

image planes : identical and parallel to baseline

search space for given : line

epipolar geometry of a normal image pair

=====Fig. 16.14=====

16.6.2 Generation of Normal Images

to rectify image pairs to normal: for correspondence and 3D determination

: new image plane

relation between general image pair and normal image pair

=====Fig. 16.15=====

procedure for rectification to normal image pair:

- Choose a plane parallel to baseline .

now focal length of normal images fixed

Choose new image coordinate systems with origins

parallel to

: principal points of new images

parallel to

Choose a common pixel spacing in the normal images. - For each of the images:

(a) Choose four points well distributed over the new image.

: coordinates of 4 points in normal images

(b) Project the four points into the original image.

Use known pose of the cameras here.

: four coordinates in image planes

(c) Solve the equation system:

(d) Rectify the original image.

each pixel in normal image: determines in original image

16.6.3 Specializing the Image-Matching Procedures

interest operator reduced to 1D: searching edges across epipolar lines

16.6.4 Precision of Three-Dimensional Points from Image Points

wide-angle stereo: distance between two centers of projection large

wide-angle stereo: more precise estimates for 3D positions

wide-angle stereo: more difficult to establish correspondence

adaptive matching window: size inversely proportional to intensity variance

adaptive matching window: size inversely proportional to estimated disparity

(a) original (b) (c) (d) adaptive matching window size

=====Nalwa, *A Guided Tour of Computer Vision*, Fig. 7.8=====

stereo image pair taken with a photogrammetric stereo camera

=====Fig. 16.17=====

=====Garfield 17:52=====

2002-02-26