COMPUTER VISION AND IMAGE

PROCESSING

Dr. Mithun Kumar Kar

School of Artificial Intelligence, Coimbatore
Amrita Vishwa Vidyapeetham
 Feature Detection and Matching
• Feature detection and matching are an essential component
of many computer vision applications.
• A feature is a distinctive, informative, and repeatable point
or region in an image that can be reliably detected under
changes such as scaling, rotation, Illumination changes,
different view points etc.
 Feature Detection and Matching
• Typical features include:
• Edges or interest points or key points
• Corners (junctions of edges)
• Blobs (regions with uniform intensity)
• Feature detection is the process of identifying key points
(interest points) in an image that are stable and distinctive.
• Feature matching finds correspondences between features
detected in two images.
• Image stitching is the process of combining multiple
overlapping images of the same scene into a single,
seamless panoramic image (much larger field of view).
 Points and Patches
• There are two main approaches to finding feature points
and their correspondences.
• The first is to find features in one image that can be
accurately tracked using a local search technique, such as
correlation or least squares.
• The second is to independently detect features in all the
images under consideration and then match features based
on their local appearance.
• Feature detection and matching pipeline can be classified in
to four stages:
• feature detection (extraction) stage,
• feature description stage,
• feature matching stage,
• and feature tracking stage.
 Points and Patches
• Point features can be used to find a sparse set of
corresponding locations in different images.
• For example, detection refers to finding the corners in a
region or image.
• Description, on the other hand, refers to assigning
quantitative (or sometimes qualitative) attributes to the
detected features, such as corner orientation, and location
with respect to other corners.
 Feature detectors
• How can we find image locations where we can reliably find
correspondences with other images?

• Look at the image pair shown in Figure and at the three

sample patches to see how well they might be matched or
tracked.
 Feature detectors
• Point features are distinct interest points (single pixel
locations) where the image intensity changes significantly in
two directions.
• Corners
• Junctions
• High-curvature points
 Feature detectors
• Corners are among the most informative and stable
features, making them ideal for matching, tracking, and
recognition.
• Corner detection is a technique used to identify interest
points in an image where the intensity changes significantly
in more than one direction.
• Corners are highly effective features because they are
distinctive and reasonably invariant to viewpoint.
• A corner is a point where two or more edges intersect.
 Feature detectors
• THE HARRIS-STEPHENS CORNER DETECTOR:
• The idea behind the Harris-Stephens (HS) corner detector is
illustrated in Figure.
 Feature detectors
• Corners are detected by running a small window over an
image, where the detector window is designed to compute
intensity changes.
• Mainly three scenarios are of interest:
• 1] Areas of zero (or small) intensity changes in all directions,
which happens when the window is located in a constant (or
nearly constant) region, as in location A.
• 2] Areas of changes in one direction but no (or small)
changes in the orthogonal direction, which this happens
when the window spans a boundary between two regions,
as in location B.
• 3] Areas of significant changes in all directions, a condition
that happens when the window contains a corner (or
isolated points), as in location C.
 Feature detectors
• The HS corner detector is a mathematical formulation that
attempts to differentiate between these three conditions.
• Let f denote an image, and let f (s, t) denote a patch of the
image defined by the values of (s, t).
• Let a patch of the same size, but shifted by (x, y), is given by
f (s + x, t + y).
• Then, the weighted sum of squared differences between the
two patches is given by

• where w(s, t) is a weighting function.

 Feature detectors
• The shifted patch can be approximated by the linear terms
of a Taylor expansion

• Where .
• We can then write

• In matrix form as

•
 Feature detectors
• Where
and

Matrix M sometimes is called the Harris matrix.

• The the weighted sum of squared differences between the
two patches is given by

 f 2
fx f y  x 
C ( x, y ) =  x y   w( s, t )  x
2  
s t  f x f y f y   y 
 Feature detectors
• If w(s, t) is isotropic, then M is symmetric because A is.
• The weighting function w(s, t) used in the HS detector
generally has one of two forms:
• 1] it is 1 inside the patch and 0 elsewhere
• 2] it is an exponential function of the form
 Feature detectors
• A corner is characterized by large values in region C, in both
spatial directions.
• However, when the patch spans a boundary there will also
be a response in one direction.
• How can we tell the difference?
• We know that, the eigenvectors of a real, symmetric matrix
(such as M) point in the direction of maximum data spread,
and the corresponding eigenvalues are proportional to the
amount of data spread in the direction of the eigenvectors.
• The eigenvectors are the major axes of an ellipse fitting the
data, and the magnitude of the eigenvalues are the
distances from the center of the ellipse to the points where
it intersects the major axes.
 Feature detectors
• It is found that the derivatives from the flat region form a
nearly circular cluster, whose eigenvalues are almost
identical, yielding a nearly circular fit to the points.
 Feature detectors
• The derivatives of the patch containing the edge, the spread
is greater along the x-axis, and about nearly the same as in
the y-axis.
• Thus, eigenvalue  x is “large” while  y is “small.
Consequently, the ellipse fitting the data is elongated in the
x-direction.
 Feature detectors
• The derivatives of the patch containing the corner, the data
is spread along both directions, resulting in two large
eigenvalues and a much larger and nearly circular fitting
ellipse.
 Feature detectors
• We conclude that:
• (1) two small eigenvalues indicate nearly constant intensity;
(2) one small and one large eigenvalue imply the presence
of a vertical or horizontal boundary, and
(3) two large eigenvalues imply the presence of a corner or
(unfortunately) isolated bright points.
• we see that the eigenvalues of the matrix formed from
derivatives in the image patch can be used to differentiate
between the three scenarios of interest.
• The HS detector utilizes a measure of corner response based
on the fact that the trace of a square matrix is equal to the
sum of its eigenvalues, and its determinant is equal to the
product of its eigenvalues.
 Feature detectors
• The measure is defined as

• R has large positive values when both eigenvalues are large,

indicating the presence of a corner.
• R has large negative values when one eigenvalue is large and
the other small, indicating an edge.
• Its absolute value is small when both eigenvalues are small,
indicating that the image patch under consideration is flat.
• k as a “sensitivity factor;” the smaller it is, the more likely
the detector is to find corners.
 Feature detectors
• Non-Maximum Suppression (Final Point Selection):
• Harris response produces many nearby high values.
• Apply non-maximum suppression to keep only local maxima
in a neighborhood
 Feature detectors
• Consider a bright square corner (top-left corner):

• We will test whether the center pixel (3,3) is a corner.

• Compute Image Gradients fx, fy using the central difference
formula
• fx =f(x+1,y)−f(x−1,y)
• fy =f(x,y+1)−f(x,y−1)
 Feature detectors
• Patch centered at (3,3):
• The gradient image is shown by

Pixel (fx) (fy)

(2,2) (100-100=0) (100-100=0)
(2,3) (20-100=-80) (100-100=0)
(2,4) (20-100=-80) (20-100=-80)
(3,2) (100-100=0) (20-100=-80)
• (3,3) (20-100=-80) (20-100=-80)
(3,4) (20-100=-80) (20-100=-80)
(4,2) (20-100=-80) (20-100=-80)
(4,3) (20-100=-80) (20-100=-80)
(4,4) (20-100=-80) (20-100=-80)
 Feature detectors
•.

• We get

• Taking the k value = 0.04

 Feature detectors
• Hence

• R is large and positive, significant intensity change in both x

and y, hence the center pixel (3,3) is a corner point.
 Feature detectors
• SCALE-INVARIANT FEATURE TRANSFORM (SIFT):
• SIFT is an algorithm developed by Lowe [2004] for extracting
invariant features from an image.
• It is called a transform because it transforms image data into
scale-invariant coordinates relative to local image features.
• SIFT features (called keypoints) are invariant to image scale
and rotation, and are robust across a range of affine
distortions, changes in 3-D viewpoint, noise, and changes of
illumination.
• The input to SIFT is an image. Its output is an n-dimensional
feature vector whose elements are the invariant feature
descriptors.
 Feature detectors
• SCALE SPACE:
• The first stage of the SIFT algorithm is to find image
locations that are invariant to scale change.
• This is achieved by searching for stable features across all
possible scales, using a function of scale known as scale
space, which can handle image structures at different scales.
• Scale space represents an image as a one-parameter family
of smoothed images, with the objective of simulating the
loss of detail that would occur as the scale of an image
decreases.
• Scale space is formed by progressively smoothing the image
using Gaussian filters with increasing standard deviation 𝜎.
 Feature detectors
• In SIFT, Gaussian kernels are used to implement smoothing,
so the scale parameter is the standard deviation ( ).
• The scale space, L (x, y,  ), of a grayscale image, f (x, y), is
produced by convolving f with a variable-scale Gaussian
kernel, G(x, y, ) :

• where the scale is controlled by parameter , and G is of

the form
 Feature detectors
• The input image f (x, y) is successively convolved with
Gaussian kernels having standard deviations , k ,k  ,
2

, … to generate a “stack” of Gaussian-filtered (smoothed)

images that are separated by a constant factor k.
• SIFT subdivides scale space into octaves, with each octave
corresponding to a doubling of .
• SIFT further subdivides each octave into an integer number,
s, of intervals
• The value used in the Gaussian kernel that generates the
image corresponding to an octave is
Feature detectors
 Feature detectors
• Detecting local extrema using Difference of Gaussian (DoG):
• SIFT initially finds the locations of keypoints using the
Gaussian filtered images.
• Keypoint locations in scale space are found by detecting
extrema in the difference of Gaussians of two adjacent
scale-space images in an octave and convolved it with the
input image that corresponds to that octave.
• To find keypoint locations related to the first two levels of
octave 1 in scale space, we look for extrema in the function
 Feature detectors
• Therefore, DoGs already have the necessary scaling “built
in”.
• Also we can write the relation

• Where  2G is called the Laplacian of Gaussian (LOG).

 Feature detectors
• Example: This has a bright blob at the center, which is ideal
for SIFT-style blob detection.
• We choose 3 scales (simplified):
• 𝜎1=1.0
• 𝜎2=1.6
• 𝜎3=2.0
 Feature detectors
• Difference of Gaussian (DoG):
• DoG1​=G2​−G1​
• DoG2​=G3​−G2​
• Scale-Space Extrema Detection:
• We test the center pixel (3,3):
• Compare with 26 neighbors:
• 8 neighbors in same DoG
• 9 neighbors in DoG above
• 9 neighbors in DoG below
• Center value −15 is smaller than all neighbors, hence this
point (3,3) is a local minimum in scale space and can be
taken as key point.
 Feature detectors
• Finding key points using LoG:
• A commonly used 5×5 LoG kernel with

• Apply LoG at the Center Pixel (3,3), we get a large value

1210.
• If we repeat LoG at different σ: like 1, 1.6 and 2 we get
 Feature detectors
σ LoG response at center
1.0 +1210
1.6 +1450 (maximum)
2.0 +900
• We get maximum response at σ ≈ 1.6. So the key point is
 Feature detectors
• Improving the Accuracy of Keypoint Locations:
• When a continuous function is sampled, its true maximum
or minimum may actually be located between sample
points.
• SIFT uses the linear and quadratic terms of a Taylor series
expansion of D( x, y,  ) , so that the origin is located at the
sample point being examined.

where D and its derivatives are evaluated at the sample point,

X = ( x, y,  )
T
 Feature detectors
• Here  is the familiar gradient operator and H is the
Hessian matrix.

• The location of the extremum, X , is found by taking the

derivative of D(x) with respect to x and setting it to zero,
which gives us
 Feature detectors
• Eliminating Edge Responses:
• Using a difference of Gaussians yields edges in an image.
But keypoints of interest in SIFT are “corner-like” features,
which are significantly more localized.
• Thus, intensity transitions caused by edges are to be
eliminated.
• An edge is characterized by high curvature in one direction,
and low curvature in the orthogonal direction.
• Curvature at a point in an image can be estimated from the
2 × 2 Hessian matrix evaluated at that point.
 Feature detectors
• Thus, to estimate local curvature of the DoG at any level in
scalar space, we compute the Hessian matrix of D at that
level

• Let  and  be the eigenvalues of H with the largest and

smallest magnitude, respectively. Then we have
 Feature detectors
• 1] If the determinant is negative, the curvatures have
different signs and the keypoint in question cannot be an
extremum, so it is discarded.
• 2] Let r denote the ratio of the largest to the smallest
eigenvalue. Then  = r 

• To check that the ratio of principal curvatures is below some

threshold, r, we only need to check
 Feature detectors
• We can eliminate the key points depending on the value of r.
• In the experimental results reported by Lowe [2004], a value
of r = 10 was used, that means, the keypoints with ratios of
curvature greater than 10 were eliminated.
• SIFT removes keypoints that lie on edges using the Hessian
matrix of the DoG function.
• At a candidate keypoint (𝑥,𝑦), the Hessian is:

• Edge Rejection Criterion:

 Feature detectors
• If we take r=10

• Suppose we take a Edge Point where

• So it should be rejected.
 Feature detectors
• Now if
 Feature detectors
• KEYPOINT ORIENTATION:
• To assign a consistent orientation to each keypoints so that
keypoints can be represent relative to its orientation and
thus achieve invariance to image rotation.
• The scale of the keypoint is used to select the Gaussian
smoothed image, L, that is closest to that scale.
 Feature detectors
• For each image sample, L(x, y), at this scale, we compute the
gradient magnitude, M(x, y), and orientation angle,  (x, y),
using pixel differences:

• A histogram of orientations is formed from the gradient

orientations of sample points in a neighborhood of each
keypoint.
 Feature detectors
• Each sample added to the histogram is weighed by its
gradient magnitude, and by a circular Gaussian function
with a standard deviation 1.5 times the scale of the
keypoint.
• Peaks in the histogram correspond to dominant local
directions of local gradients.
• The highest peak in the histogram is detected and any other
local peak that is within 80% of the highest peak is used also
to create another keypoint with that orientation.
 Feature detectors
• Assign a dominant orientation to a keypoint so that the
descriptor becomes rotation invariant.

• Example:
• Detected keypoint at location (x₀, y₀)
• Scale = σ
• Consider a small neighborhood around the keypoint.
• Assume the gradient magnitudes and directions at 9 pixels
are:
 Feature detectors
Pixel Gradient magnitude (m) Orientation (theta)

• | P1 | 10 | 10° |
• | P2 | 12 | 20° |
• | P3 |8 | 15° |
• | P4 | 20 | 95° |
• | P5 | 25 | 100° |
• | P6 | 22 | 110° |
• | P7 |5 | 200° |
• | P8 |6 | 210° |
• | P9 |4 | 205° |
 Feature detectors
• SIFT uses 36 bins, Each bin = 10° and Range: 0°–360°, we
now accumulate magnitudes into bins.
Orientation Range Bin Contributing pixels Sum of magnitudes

0°–10° Bin 1 — 0

10°–20° Bin 2 P1 (10°), P3 (15°) 10 + 8 = 18

20°–30° Bin 3 P2 (20°) 12

90°–100° Bin 10 P4 (95°) 20

100°–110° Bin 11 P5 (100°) 25

110°–120° Bin 12 P6 (110°) 22

200°–210° Bin 21 P7 (200°), P9 (205°) 5+4=9

210°–220° Bin 22 P8 (210°) 6

 Feature detectors
• Histogram Values (Non-Zero Bins):
• Bin 2 (10–20°)=18
• Bin 3 (20–30°)=12
• Bin 10 (90–100°)=20
• Bin 11 (100–110°)=25 ←MAX
• Bin 12 (110–120°)=22
• Bin 21 (200–210°)=9
• Bin 22 (210–220°)=6
• Dominant Orientation Selection
• Maximum histogram peak = 25, Corresponding bin = 100°–
110°​, hence
 Feature detectors
• Multiple Orientations:
• Multiple keypoints are created at the same location and
scale but with different orientations.
• SIFT also assigns secondary orientations if:

• Bins satisfying this are Bin 10 and 12 .

• If the image rotates → gradients rotate
• Histogram peak shifts → orientation compensates
 Feature detectors
• KEYPOINT DESCRIPTORS:
• After providing invariance like image location, scale, and
orientation to each keypoint, a descriptor for a local region
around each keypoint is computed to identify matches
(similarities) between local regions in two or more images.
• The approach used by SIFT to compute descriptors is based
on experimental results suggesting that local image
gradients appear to perform a function similar to what
human vision does for matching and recognizing 3-D objects
from different viewpoints.
Feature detectors
 Feature detectors
• A region of size 16 × 16 pixels is centered on a keypoint, and
the gradient magnitude and direction are computed at each
point in the region using pixel differences.
• A Gaussian weighting function with standard deviation
equal to one-half the size of the region is then used to
assign a weight that multiplies the magnitude of the
gradient at each point.
• The purpose of this function is to reduce sudden changes in
the descriptor with small changes in the position of the
function.
• Because there is one gradient computation for each point in
the region surrounding a keypoint, there are (16x16)
gradient directions to process for each keypoint.
 Feature detectors
• Next step is consists of quantizing all gradient orientations in
the 4 × 4 subregion into eight possible directions differing by
45°.
• SIFT performs interpolation that distributes a histogram
entry among all bins proportionally, depending on the
distance from that value to the center of each bin.
• Figure shows the eight directions of a histogram as a small
cluster of vectors, with the length of each vector being
equal to the value of its corresponding bin.
• Sixteen histograms are computed, one for each 4 × 4
subregion of the 16 × 16 region surrounding a keypoint.
• A descriptor, shown in on the lower left of the figure, then
consists of a 4 × 4 array, each containing eight directional
values.
 Feature detectors
• Descriptor Structure:
• Neighborhood: 16×16 pixels
• Divided into 4×4 subregions
• Each subregion → 8-bin orientation histogram
• Total dimensions: 4x4x8 = 128
 Feature detectors
• Each histogram has 8 bins, each covering 45°:

Bin Orientation range

1 0°–45°

2 45°–90°

3 90°–135°

4 135°–180°

5 180°–225°

6 225°–270°

7 270°–315°

8 315°–360°
 Feature detectors
• Assume subregion (1,1) has the following gradient
contributions:
Orientation Magnitude
20° 5
30° 3
70° 4
100° 6
190° 2
200° 3
300° 4
 Feature detectors
• Bin accumulation:
Bin Value

1 (0–45°) 5+3=8

2 (45–90°) 4

3 (90–135°) 6

4 0

5 (180–225°) 2+3=5

6 0

7 0

8 (315–360°) 4
 Feature detectors
• We now assume numerical histograms for all 16 subregions:
• Row 1
• H1,1​ = [8,4,6,0,5,0,0,4]
• H1,2​ = [5,3,4,2,1,0,0,1]
• H1,3​ = [2,1,3,5,4,1,0,0]
• H1,4​ = [1,0,2,6,5,2,1,0]
• Row 2
• H2,1​ = [4,5,6,2,1,0,0,1]
• H2,2​ = [6,7,8,3,2,1,0,1]
• H2,3​ = [3,4,6,4,3,1,0,0]
• H2,4​ = [2,3,5,6,4,2,1,0]
 Feature detectors
• Construct the 128-D Descriptor Vector:
• The descriptor is formed by concatenating all histograms:

• The 128 dimension vector

• L2 Normalization and threshold:

 SUMMARY OF THE SIFT ALGORITHM
• Construct the scale space: The parameters that need to be
specified are s, s, (k is computed from s), and the number of
octaves. Suggested values are s = 1 6 . , s = 2, and three
octaves.
• Obtain the initial keypoints. Compute the difference of
Gaussians, D(x, y,s), from the smoothed images in scale
space.
• Find the extrema in each D(x, y,s) image using the method
explained. These are the initial keypoints.
• Improve the accuracy of the location of the keypoints.
Interpolate the values of D(x, y,s) via a Taylor expansion.
• Delete unsuitable keypoints. Eliminate keypoints that have
low contrast and/or are poorly localized.
 SUMMARY OF THE SIFT ALGORITHM
• All keypoints whose values of D are lower than a threshold
are deleted. A suggested threshold value is 0.03. Keypoints
associated with edges are deleted. A value of 10 is
suggested for r.
• Compute keypoint orientations: Compute the magnitude
and orientation of each keypoint using the histogram-based
procedure discussed.
• Compute keypoint descriptors. Use the method
summarized in Figure to compute a feature (descriptor)
vector for each keypoint. If a region of size 16 × 16 around
each keypoint is used, the result will be a 128-dimensional
feature vector for each keypoint.
 LINKING EDGE POINTS(HOUGH
TRANSFORM)
• Edge detection typically is followed by linking algorithms
designed to assemble edge pixels into meaningful edges
and/or region boundaries.
• Let ( xi , y i ) denote a point in the xy-plane and consider the
general equation of a straight line in slope-intercept form:
y i = axi + b
• Infinitely many lines pass through ( xi , y i ) but they all satisfy
the equation y i = axi + b for varying values of a and b.

• Now if we write b = −axi + y and considering the ab-

plane (also called parameter space) yields the equation of a
single line for a fixed point .
 HOUGH TRANSFORM
• In fact, all points on this line have lines in parameter space
that intersect at (a, b) .
 HOUGH TRANSFORM
• Principal lines in xy-plane could be found by identifying
points in parameter space where large numbers of
parameter-space lines intersect.
• If we use the polar representation of a line:

• Where:
• 𝜌:perpendicular distance from origin
• 𝜃: angle of the normal
• Parameterization of a line in the xy-plane to the (  ,  )
space where each sinusoidal curve represents the family of
lines that pass through a particular point ( xk , y k )in the xy-
plane.
 HOUGH TRANSFORM
• Hough transform divides the parameter space  into so-
called accumulator cells.

•.
 HOUGH TRANSFORM
• Here ( min , max ) and (min ,max ) are the expected ranges of
the parameter values , that is −90° ≤ ≤ 90° and
−D ≤ ≤ D, where D is the maximum distance between
opposite corners in an image.
• The cell at coordinates (i, j) with accumulator value A(i, j)
corresponds to the square associated with parameter-space
coordinates ( i ,i ) .
• Initially, these cells are set to zero.
• Then, for every non-background point (x , y ) in the xy-
plane, we allowed subdivision values on the -axis and
solve for the corresponding .
 HOUGH TRANSFORM
• The resulting values are then rounded off to the nearest
allowed cell value along the axis.
• If the condition is satisfied, then we let A(p,q) = A(p,q) + 1.
• At the end of the procedure, a value of K in a cell A(i, j)
means that K points in the xy-plane lie on the line

• The number of subdivisions in the  plane determines

the accuracy of the collinearity of these points.
 HOUGH TRANSFORM
• Hough Transform Algorithm for (Line Detection):
• 1] Apply an edge detector (e.g., Canny) to get edge points.
• 2] Construct Parameter Space (Accumulator):
• Discretize:

Create an accumulator array A(ρ,θ)

• 3] Voting: For each edge pixel (𝑥,𝑦):

• Increment A(  , ) = A(  , ) + 1
 HOUGH TRANSFORM
• 4] Peak Detection:
Peaks in accumulator → detected lines
• 5] Line Reconstruction
Convert (𝜌,𝜃) back to image space.
• For vertical lines chose 𝜃=0.
• For horizontal lines chose 𝜃=90
• For diagonal lines chose 𝜃=45 or 135.
 HOUGH TRANSFORM
• Example:
• Suppose Edge points: (1,1),(2,2),(3,3)
• These lie on: y=x
• Using polar form: For 𝜃=45∘:

• For point (1,1):

• For point (2,2): ρ=2.828
 HOUGH TRANSFORM

• Edge coordinates are given by

Point (x,y)

P₁ (2,0)

P₂ (2,1)

P₃ (2,2)

P₄ (2,3)

P₅ (2,4)

• For a vertical line, choose:

 HOUGH TRANSFORM
• Compute the ρ Values with ρ=x
(x,y) ρ

(2,0) 2

(2,1) 2

(2,2) 2

(2,3) 2

(2,4) 2

• Accumulator Result: Detected Line 𝑥=2.

(ρ, θ) Votes
(2, 0°) 5 peaks
 Image Registration
• Image registration is the process of spatially aligning two or
more images of the same scene captured at different times,
from different viewpoints, or by different sensors.
• Images may differ due to:
Camera movement
Different sensors (RGB, IR, MRI, CT)
Time variation (before–after analysis)
Scale, rotation, or perspective change
• Registration makes meaningful comparison, fusion, or
analysis possible.
 Image Registration
• It can be shown as a transformation 𝑇(⋅) such that:

• Where I r ( x, y) is called reference image and I m ( x, y) is

called moving image.

(a spherical panorama constructed from 54 photographs)

 Image Registration
• Main steps of image registration are
• 1] Feature detection (find distinctive points or regions)
• 2] Feature matching (match features between images)
• 3] Transformation model (defines how images are aligned)
• 4] Optimization / similarity measure (maximize similarity
between images)
• 5] Resampling & interpolation (apply transformation and
interpolate)
 Image Registration
• Types of image registration:
• Based on data (Intensity-based , Feature-based (keypoints,
shapes)
• Based on transformation (Rigid, Affine, Non-rigid )
• Based on dimension (2D–2D, 3D–3D, 2D–3D)

• Applications:
• Medical imaging (tumor tracking)
• Remote sensing (change detection)
• Computer vision (panorama stitching)
• Biometrics (face, fingerprint)
• Robotics and navigation
 Image alignment and stitching
• Image alignment is the process of geometrically
transforming one image so that it matches another
reference image.
• Image alignment is the computation of 2D and 3D
transformations that map features in one image to another.
• Image alignment is needed mainly to tackle the error caused
by :
1] Images taken from different viewpoints
2]Images captured at different times
3] Images from different sensors (RGB, IR, MRI, CT)
4] Slight camera motion, rotation, or scale change
 Image alignment and stitching
• Image Stitching Pipeline:
• Image Acquisition (Same scene, different viewpoints)
• Feature Detection (Detect keypoints in each image)
• Feature Matching (Match descriptors across images)
• Image Alignment (bring corresponding keypoints, into the
same coordinate system.)
• Image Warping (Apply geometric transformation)
• Image Blending (Handles intensity differences.)
Image alignment and stitching
 Image alignment and stitching
• 2D feature based alignment:
• 2D feature-based alignment is a method of aligning two 2D
images by:
• Detecting distinctive features (keypoints),
• Matching those features between images, and
• Estimating a geometric transformation that maps one image
onto the other.
• It aligns images based on geometric correspondences, not
raw pixel intensities.
 Image alignment and stitching
• Complete 2D Feature-Based Alignment Pipeline:
• Input two images
• Detect keypoints
• Extract descriptors
• Match descriptors
• Reject outliers (RANSAC)
• Estimate transformation
• Warp image
 Image alignment and stitching
• Feature matching is the process of finding corresponding
feature points (keypoints) between two images by
comparing their descriptors.
• Distance Measures
• Euclidean Distance (SIFT)
 Jacobian
• The Jacobian is a matrix of partial derivatives that describes
how small changes in transformation parameters affect the
transformed image coordinates.
• If a transformation maps a point x=(x,y) as:
• Where P is the transformation parameter

• Example:
 2D Transformation Models
• Transformation estimation:
• 1] Translation: Shifts the image in x and y directions

• Shifting parameters: p=(tx​, ty​)

• Degrees of freedom: 2
• Effect: Moves points without rotation or scaling
• Jacobian: Identity matrix (constant shift)
• (x,y)=(2,3)
 2D Transformation Models
• Euclidean (Rigid) Transformation:
• Purpose: Rotation + translation cos  − sin  tx 
 sin  cos  
• Parameters: (𝑡𝑥, 𝑡𝑦, 𝜃)  ty 
• Preserves: Distances and angles
• Use: Object tracking, rigid motion
• Jacobian: 1 0 − x sin  − y cos  
0 1 x cos  − y sin  
 
 Image alignment and stitching
• Suppose Rotation angle: θ=90∘

Translation:
• Original point 𝑃=(1,2)

• Final transformed Point (0,2).

• We can use the homogenitus matrix:
 Image alignment and stitching
• Similarity Transformation
• Purpose: Rotation + translation + uniform scaling

• s → uniform scale factor, θ → rotation angle

• Jacobian:

• Degrees of freedom = 4
x = s( x cos  − y sin  ) + t x y = s( x sin  + y cos  ) + t x
 Image alignment and stitching
• We can present it in the following form

• Scale: s=2, Rotation angle: θ=90 and tx​=1, ty​=2

• We can use directly homogeneous matrix also
 Image alignment and stitching
• Affine Transformation
• Purpose: Adds shear and non-uniform scaling

• a11​, a12​, a21​, a22​ → linear transformation

• Degrees of freedom = 6
• Preserves: Parallel lines
• Use: Viewpoint changes with small perspective effects
• Jacobian:
 Image alignment and stitching
• Scaling in 𝑥 and Shear in 𝑥:
• Scaling in x:

• Shear in 𝑥:

• Combined in Affine transform

• a11 ​ = Scaling (and rotation contribution) in x-direction.

• a12 ​ = Shear (and rotation contribution) in x-direction.
• a21 ​ = Scaling (and rotation contribution) in y-direction.
• a22 ​ = Shear (and rotation contribution) in y-direction.
 Image alignment and stitching
• Projective Transformation (Homography)
• A projective transformation (also called homography) is the
most general 2D transformation, capable of modeling
perspective effects.
• Homogeneous Matrix Form:

• Normalized Form (Commonly Used)

 Image alignment and stitching
• Preserves: Straight lines only
• 8 degrees of freedom
• Use: Image stitching, document rectification
• Coordinate Mapping

• Models camera perspective

• A homography maps a point by matrix multiplication
followed by normalization, introducing perspective effects.
 Image alignment and stitching
• Homography Estimation:
• We estimate matrix H using all inliers such that the following
transformation results a single optimal transformation.

• Warp Image: Image warping applies the estimated

transformation to every pixel of the image to align it with
the reference image.
 Image alignment and stitching
• Reject outliers through Random Sample Consensus
(RANSAC)
• RANSAC rejects outliers by fitting a model to random
samples and keeping only matches that agree with the same
transformation.
• 1] Select minimum random samples
• 2] Estimate the model
• 3] Classify inliers and outliers
• 4] Count inliers
• 5] Repeat iterations
• 6] Re-estimate the final model using all inliers only.
 Image alignment and stitching
• Example:Suppose we matched 8 feature points between
two images.
Match Image-1 (x, y) Image-2 (x′, y′) Status
1 (0,0) (1,1) inlier
2 (1,0) (2,1) inlier
3 (0,1) (1,2) inlier
4 (1,1) (2,2) inlier
5 (2,2) (10,10) outlier
6 (3,3) (15,2) outlier
7 (4,1) (0,8) outlier
8 (2,0) (9,1) outlier

• True transformation: x′=x+1, y′=y+1

 Image alignment and stitching
• Random Sampling: {1,2,3,4}, {2,4,6,7},{1,4,5,6}, . . .
• Estimate Model: From these 4 points, estimate
transformation: x′=x+1, y′=y+1
• Compute Reprojection Error:

• Use threshold for Inlier / Outlier Decision: T=1

• Count Inliers
• Another Random Iteration
• After many iterations: Select model with maximum inliers
 Image alignment and stitching
• After outlier rejection pipeline proceeds with Estimate
Transformation and Warp Image.
• Estimate Transformation (Using Inliers):
• Using only inlier point pairs, we compute the best geometric
transformation that maps points from Image-1 to Image-2.
• Inlier correspondences:
• Choose Transformation Model:
Model Min Points
Translation 1
Euclidean 2
Similarity 2
Affine 3
Projective (Homography) 4
 Image alignment and stitching
• Example:
• Given a Point in Input Image:
• Let a pixel in the source image be:
• Given Affine Transformation Matrix

• Convert to Homogeneous Coordinates

 Image alignment and stitching
• Apply the Transformation (Forward Warping):

• Final Warped Pixel Location

• The pixel at (2,3) in the source image moves to (4, 5) in the

warped image.
 Image alignment and stitching
• How to Optimize a Geometric Transform (Image Alignment /
Registration).
• After choosing the transformation model, optimization
means finding the best parameters so that the transformed
image aligns with the reference image.
• Let the transformation be
• x=(x,y) → original point
• x′=(x′,y′) → transformed point
• p → transformation parameters
• Define an Error (Cost) Function: Feature-based error or
reprojection error
 Image alignment and stitching
• Intensity-based error

• Linear Least Squares optimization:

• Nonlinear Optimization:

• Use Jacobian
 Image alignment and stitching
• Warp the Image (Image Resampling):
• Use the optimized transformation matrix 𝑇 to map pixels
from the source image to the reference image.

• Each pixel in the source image is mapped to a new location.

• Interpolation is required because mapped coordinates are
not integers.
• Image Blending / Stitching (If multiple images)
• If alignment is part of panorama creation:
• Overlapping regions must be blended
• Reduce seams and exposure differences
 Pose Estimation
• Estimating an object’s 3D pose from a set of 2D point
projections.
• This pose estimation problem is also known as extrinsic
calibration, as opposed to the intrinsic calibration of internal
camera parameters.
• The problem of recovering pose from three
correspondences is known as the perspective-3-point-
problem (P3P).
• Object Pose Estimation is the process of determining the
position and orientation of a rigid object with respect to the
camera or world coordinate system from an image or video.
 Pose Estimation
• Pinhole projection of a 3D point X onto a camera image
plane
 Pose Estimation
• A pose describes the spatial configuration of an object.
• Object Pose Estimation:
• Object Pose Estimation is the process of determining the
position and orientation of a rigid object with respect to the
camera or world coordinate system from an image or video.
• In 3D, this is usually called 6-DoF pose estimation:
• Translation (Position) — 3 DoF, Rotation (Orientation) — 3
DoF

• Object Pose mean?

• Position → where the object located(𝑥,𝑦,𝑧)
• Orientation → how the object is rotated(𝛼,𝛽,𝛾)
 Pose Estimation
• Camera observes a 3D object
• The goal is to find R (rotation) and t (translation) that map
object to camera.

• The Perspective-n-Point (PnP) algorithm estimates the pose

of a 3D object (rotation and translation) from n known 3D
points and their 2D projections in an image.
 Pose Estimation
• Given known 3D object points ,
corresponding 2D image points and Camera
intrinsic matrix 𝐾, the pose estimation finds the Rotation
matrix 𝑅 and Translation vector 𝑡.
 
X 
 i
u  i
K −1  vi  = [ R | t ]  Yi 
 
 1  Z i 
1 

• r1​,r2​,r3​ are rows of R

 Pose Estimation
• PnP estimates the camera pose:

• Where R → rotation matrix (3×3)

• 𝑡 → translation vector
• Rotation matrix representation
• Constraints on R:

• From the pinhole camera model:

 Pose Estimation
• Rearranging we get

• Ignoring orthogonality constraints temporarily, we can have

the form

• Using ≥ 4 points, we solve this linear system using SVD.

 Pose Estimation
• We can write in matrix form:

• We can write in matrix form:

 Pose Estimation
• Example:
• Assume a square object lying on the Z=0 plane:
• Corresponding 2D Image Points (in pixels)
are given by

• Camera Intrinsic Matrix:

 Pose Estimation
• Normalize Image Coordinates:

• For point 𝑝1=(120,200)

• For point p2 =(0.075, -0.0375)

• P3=(0.06875, 0.0875)
• P4=(-0.05625, 0.075 )
 Pose Estimation
• PnP Projection Equation
• s is the scaling factor

• PnP solves for rotation R and translation t.

• Suppose after applying a PnP solver we get
Rotation Matrix R:
[[ 0.97464363 -0.05031705 0.21803207] Translation Vector t:
[[-0.39564917]
[ 0.0904755 0.97980324 -0.17832499]
[-0.3831756 ]
• [-0.20465574 0.19352988 0.95951145]]
[ 7.81958978]]
• R: object is slightly rotated and tilted
• Tz =7.8: object is 7.8 units in front of the camera
• Full 6-DoF pose is obtained
 Dense motion estimation
• Dense motion estimation is the process of estimating a
motion vector for every pixel between two (or more)
consecutive image frames.
• It produces a dense motion field, unlike sparse methods
that compute motion only at selected feature points.
• Given two frames: I ( x, y, t ) and I ( x, y, t + 1)

• Estimate a displacement field:

• So that
 Dense motion estimation
• Given two consecutive frames:
• Frame at time 𝑡: 𝐼(𝑥,𝑦,𝑡)
• Frame at time 𝑡+1: 𝐼(𝑥,𝑦,𝑡+1)
• We want to estimate a motion vector for each pixel:
• v = vertical displacement, u = horizontal displacement
 Dense motion estimation
• During motion estimation, the motion of objects is
measured and encoded into motion vectors.
• The search for the “best” motion vector requires that a
criterion of optimality be defined.
 Dense motion estimation
• Motion vectors may be selected on the basis of maximum
correlation or minimum error between macroblock pixels
and the predicted pixels (or interpolated pixels for sub-pixel
motion vectors) from the chosen reference frame.
• One of the most commonly used error measures is mean
absolute distortion (MAD)
 Dense motion estimation
• The simplest way to establish an alignment between two
images or image patches is to shift one image relative to the
other.
• Given a template image I 0 ( x) sampled at discrete pixel
locations , we wish to find where it is located
in image I1 ( x) .
• A least squares solution to this problem is to find the
minimum of the sum of squared differences (SSD) function.

• where u = (u, v) is the displacement and ei is called the

residual error ( the displaced frame difference).
 Optical flow
• Optical flow describes the apparent motion of pixels
between two consecutive image frames caused by object
motion, camera motion, or scene changes.
• In dense motion estimation, optical flow is computed for
every pixel in the image.
• The most general (and challenging) version of motion
estimation is to compute an independent estimate of
motion at each pixel, which is generally known as optical (or
optic) flow.
• When scenes contain moving objects, temporal variations in
intensity have to be taken into account.
• Only edges with a component normal to the direction of
motion carry information about the motion.
 Optical flow
• Considering the intensity function I ( x, y, t ) and expanding
it in a Taylor series:

• In this equation, Ix, Iy, and It denote respective partial

derivatives with respect to x, y, and t.
• Optical flow is based on the assumption that pixel intensity
remains constant while moving:

• we can deduce

• This is called the Optical Flow Constraint Equation.

 Optical flow
• Writing the local velocity v in the form:

• I t can be measured by subtracting pairs of images in the

input sequence.
• I can be estimated by Sobel or other gradient operators.
• Unfortunately, this equation is a scalar equation and will not
suffice for determining the two local components of the
velocity field.
• To compute the full velocity field v(x, y), we have to know
about v and its components lie on the following line in (vx,
vy) space
 Optical flow
• This line is normal to the direction (Ix, Iy), and has a distance
from the (velocity) origin that is equal to:

• We need to deduce the

component of v along the line.
Lucas–Kanade Formulation for Optical Flow
• The Lucas–Kanade (LK) method is a local optical flow
algorithm that estimates motion by assuming that
neighboring pixels move together.
• We are given two consecutive frames:

• Estimate the motion vector v=(u,v) at a pixel with the

brightness constancy assumption that is the optical flow
constraint equation:

• Here one equation, two unknowns (𝑢,𝑣), hence motion

cannot be uniquely determined from a single pixel.
(Aperture Problem)
Lucas–Kanade Formulation for Optical Flow
• Lucas–Kanade resolves this by assuming:
• All pixels inside a small window Ω have the same motion
(𝑢,𝑣).
• For every pixel 𝑖 ∈ Ω:

• solving using least squares:

Lucas–Kanade Formulation for Optical Flow
• Where:

• Lucas–Kanade estimates optical flow by fitting a constant

motion vector to a small neighborhood using least-squares
optimization.
Lucas–Kanade Formulation for Optical Flow
• Example: We use two consecutive frames and compute the
motion vector (u,v) at the center pixel.

• Object moves 1 pixel to the right.

• Horizontal gradient:
• Vertical gradient:
• Temporal gradient:
Lucas–Kanade Formulation for Optical Flow
• Compute gradients for all pixels in the window
Pixel (I_x) (I_y) (I_t)
(1,1) 0 0 0

(1,2) 10 0 0

(2,1) 0 10 0

(2,2) 10 10 −10

• For each pixel:

• Lucas–Kanade Matrix Form:
Lucas–Kanade Formulation for Optical Flow
• Compute the sums and solve the linear system

• Final Optical Flow Vector

• Motion is 1 pixel to the right and no vertical movement.

• The same computation is done for every pixel which
produces a dense motion field.
Optical flow
 Parametric motion
• Parametric motion is a way to describe motion by
expressing an object’s position as a function of an
independent parameter, usually time t.
• In 2D motion, the position of a particle is written as

• In optical flow, each pixel moves parametrically over time:

• We take the brightness constancy assumption:
I(x(t),y(t),t)=constant
 Parametric motion
• A moving camera has 6-DoF motion, parameterized as:

• Pose estimation (PnP connection)

 Layered motion
• Layered motion in computer vision is a way to model
complex scenes by assuming that different regions (layers)
of the image move differently, but each layer follows a
simple parametric motion model.
• Layered motion = “multiple motions, one scene”
• Each layer is spatially coherent, has its own motion
parameters and explains a subset of pixels.
• The layers can be background, foreground objects, camera
motion etc.
 Layered motion
• Let an image be decomposed into K layers.
• For pixel 𝑝=(𝑥,𝑦) , which belongs to layer 𝑘, the location of
the same physical point in the next frame is given by

• Where Wk​(⋅) represents parametric motion

function/models and θk​ represents motion parameters of
layer k.
 Layered motion
• Relation to optical flow:
• Dense optical flow: One motion vector per pixel
• Layered motion: Many pixels share same motion parameters
where motion is piecewise parametric.
• Layered motion pipeline:
• Extract optical flow or correspondences
• Cluster motions (e.g., RANSAC)
• Fit parametric model per cluster
• Assign pixels to layers
• Refine using EM or graph cuts
 Layered motion
• We assume layered motion:
• Layer 1 → Background
• Layer 2 → Foreground object
Pixel Coordinates (p = (x,y) ) True layer

(p_1) (10, 20) Background

(p_2) (30, 40) Background

(p_3) (60, 25) Foreground

(p_4) (65, 30) Foreground

• Layer 1: Background (camera translation)

• Foreground object (independent motion)

 Layered motion
• Compute 𝑝′ for each pixel using the motion models.
• Background pixels: p1 and p2→(12,20), (32,40)
• Foreground pixels: p3 and p4→(65,24), (70,29)
• Optical flow view (per pixel)
• Optical flow 𝑢=𝑝′−𝑝
Pixel Flow ( (u,v) )

(p_1) (2, 0)

(p_2) (2, 0)

(p_3) (5, −1)

(p_4) (5, −1)

• We can conclude that pixels within the same layer share identical
flow
 Layered motion
• We can use layered motion for motion segmentation.
• We can estimate hidden variables (e.g., layer assignments)
given current parameters that is estimate which pixels
belong to which motion layer.
• We can update model parameters to maximize the expected
likelihood (EM).
 Structure from Motion
• Structure from Motion (SfM) is a computer vision technique
used to recover the 3D structure of a scene and the camera
motion from a set of 2D images taken from different
viewpoints.
• The SfM pipeline consists of several key steps:
• Image Acquisition
• Feature Detection
• Feature Matching
• Camera Pose Estimation
• Triangulation
• Bundle Adjustment
• Dense Reconstruction or 3D Reconstruction
 Structure from Motion
• Image Acquisition
• Multiple overlapping images of the scene are captured from
different angles.
• The more overlap and variety
in viewpoints, the better the
reconstruction.
 Structure from Motion
• Feature Detection:
• Distinctive points (features) in each image are identified
using algorithms like SIFT, SURF or ORB.
• These features are robust to scale, rotation and illumination
changes.
 Structure from Motion
• Feature Matching
• Features are matched across different images to find
correspondences i.e., the same physical point seen in
multiple images.
• Reliable matching is crucial for accurate 3D reconstruction.
 Structure from Motion
• Camera Pose Estimation:
• The relative positions and orientations (extrinsic
parameters) of the cameras are estimated using the
matched features.
• This step often involves solving for the essential or
fundamental matrix between image pairs.
 Structure from Motion
• Triangulation:
• The 3D coordinates of matched features are computed by
triangulating their positions from multiple views, using the
known camera poses.
 Structure from Motion
• Triangulation is used for establishing correspondences
between the two images that is, deciding which points in
the second picture match the points in the first one.
 Structure from Motion
• The problem of determining a point’s 3D position from a set
of corresponding image locations and known camera
positions is known as triangulation.
• Objective: To find the 3D point p that lies closest to all of
the 3D rays corresponding to the 2D matching feature
locations {x j } observed by cameras .
• The nearest point to p on this ray, which we denote as
minimizes the distance .
Here C j is the jth camera center and is the direction of
originating rays from the camera centre.
 Structure from Motion
• Triangulation example:
• Camera Parameters: Focal length f = 800 pixels
• Principal point:
• Baseline between cameras: B=0.20 meters
• Assume that :
• Cameras are rectified
• Optical axes are parallel
• Right camera is shifted along X-axis
• Left camera center:

• Right camera center:

 Structure from Motion
• A scene point projects to:

Camera u (px) v (px)

Left 360 260
Right 340 260

• Compute Disparity:
• Stereo depth formula:
 Structure from Motion
• Compute X Coordinate:

• Compute Y Coordinate

• Final Triangulated 3D Point:

 Structure from Motion
• Showing how we get

• We will:
• Start with a pixel (𝑢,𝑣) in Camera-1
• Reconstruct the 3D point
• Reproject it into Camera-2 to get (𝑢′,𝑣′)
• Camera Intrinsics (Same for Both Cameras)
 Structure from Motion
• Camera-1 (World Reference)

• Camera-2 (Shifted Right by 0.2 m)

• Camera-2 center is at (0.2, 0, 0)

• Pixel Observation in Camera-1: (u,v)=(360,260)
 Structure from Motion
• Back-Project Pixel to a 3D Point:
• Find the Normalize Image Coordinates:

• To reconstruct a point, depth must be known.

• Assume: Depth is 𝑍=8 m.
 Structure from Motion
• Compute 3D Point in World Coordinates:

• Project 3D Point into Camera-2

• Transform to Camera-2 Coordinates
 Structure from Motion
• Perspective Projection

• Apply Intrinsics
 Structure from Motion
• Pixel in Camera-1 defines a ray
• Depth gives a unique 3D point
• Same 3D point reprojects to a shifted pixel in Camera-2
• Horizontal shift = disparity.
 Structure from Motion
• Bundle Adjustment:
• The term “bundle” refers to the bundles of rays connecting
camera centers to 3D points and the term “adjustment”
refers to the iterative minimization of re-projection error.
• Both the 3D point positions and camera parameters are
refined simultaneously to minimize the reprojection error
(the difference between observed and predicted feature
positions in the images).
• Reprojection error measures how well a 3D point, when
projected back into an image using the estimated camera
parameters, matches the observed 2D image point.
 Structure from Motion
• You observe a 2D feature point x in an image.
• You estimate: the 3D point X, the camera pose (R,t), the
camera intrinsics K.
• You project the 3D point back into the image.
• The distance between: observed point 𝑥 and projected point
𝑥^ is the reprojection error.
• π(⋅) be the perspective projection function, then projected
point in camera coordinate is given by

• Reprojection Error is given by

 Structure from Motion
• Bundle Adjustment is an optimization process that
simultaneously refines camera poses (rotation R, translation
t), 3D point positions(optionally), camera intrinsics by
minimizing the reprojection error over all images and all
points.
• Bundle Adjustment Objective:
 Structure from Motion
• Dense Reconstruction:
• After sparse point clouds are obtained, further algorithms
can interpolate and densify the reconstruction, producing a
detailed 3D model.
• Given known camera poses, multiple calibrated images,
dense reconstruction estimates depth for each pixel by
finding photometrically consistent matches across views.
• Dense Stereo (Two Views) is used for calculating the depth.
• For a pixel 𝑝 in image 1, search along the epipolar line in
image 2.
• Find best match.
• Depth is recovered via triangulation.
 Structure from Motion
• Multi-View Stereo (Stereo vision) is used for 3D
reconstruction.
• Dense reconstruction recovers full surface geometry by
estimating depth for nearly every pixel using multiple
calibrated images.
 Structure from Motion
• Texturing and Model Generation:
• The final step may involve generating a mesh and applying
textures from the original images for realistic visualization.
• After dense reconstruction, we usually have a dense point
cloud or a surface mesh.
• Texturing and model generation convert this raw geometry
into a realistic, usable 3D model.