Description
SIFT Feature Extraction
(a) Image (b) SIFT
Figure 1: Given an image (a), you will extract SIFT features using OpenCV.
One of the key skills to learn in computer vision (and software development in general)
is the ability to use other, open-source code, which allows you to not reinvent the wheel.
We will use OpenCV library for SIFT features extraction given your images.
You will use this library only for SIFT feature extraction and its visualization. All
following visualizations and algorithms must be done by your code. Using OpenCV,
you can extract keypoints and associated descriptors as shown in Figure 1. SIFT is
now included with the core OpenCV library, as the patent for the algorithm expired in
2020. But older version of OpenCV will not have it in the core library, so please make
sure you have a recent version of OpenCV.
Use OpenCV to visualize SIFT features with scale and orientation as shown in Figure 1
(OpenCV may use different colors to visualize). You may want to follow the following
tutorial:
https://docs.opencv.org/4.x/da/df5/tutorial_py_sift_intro.html
2
CSCI 5561: Project #2
Registration
3 SIFT Feature Matching
(a) Template (b) Target (c) SIFT matches with ratio test
Figure 2: You will match points between the template and target image using SIFT
features.
SIFT is composed of scale, orientation, and a 128-dimensional local feature descriptor,
f ∈ Z128. You will use the SIFT features to match between two images, I1 and I2. Use
two sets of descriptors from the template and target, find the matches using nearest
neighbor with the ratio test. You may use NearestNeighbors function imported from
sklearn.neighbors (You can install sklearn package easily by ”pip3 install -U scikitlearn”).
You can only use the SIFT module of OpenCV for the SIFT descriptor extraction. You
need to implement the matching with the ratio test yourself.
def find_match(img1, img2):
…
return x1, x2
Input: two input grayscale images with uint8 format.
Output: x1 and x2 are n × 2 matrices that specify the correspondence.
Description: Each row of x1 and x2 contains the (x, y) coordinate of the point correspondence in I1 and I2, respectively, i.e., x1(i,:) ↔ x2(i,:).
3
CSCI 5561: Project #2
Registration
4 Feature-based Image Alignment
Figure 3: You will compute an affine transform using SIFT matches filtered by
RANSAC. Red: outliers; Green: inliers; Yellow: the boundary of the transformed
template.
The noisy SIFT matches can be filtered by RANSAC with an affine transformation as
shown in Figure 3.
From this point, you cannot use any function provided by OpenCV, except for purely
visualization purposes.
def align_image_using_feature(x1, x2, ransac_thr, ransac_iter):
…
return A
Input: x1 and x2 are the correspondence sets (n × 2 matrices). ransac_thr and
ransac_iter are the error threshold and the number of iterations for RANSAC.
Output: 3 × 3 affine transformation.
Description: The affine transform will transform x1 to x2, i.e., x2 = Ax1. You may
visualize the inliers and the boundary of the transformed template to validate your
implementation.
4
CSCI 5561: Project #2
Registration
5 Image Warping
(a) Image (b) Warped image (c) Template (d) Error map
Figure 4: You will use the affine transform to warp the target image to the template
using the inverse mapping. Using the warped image, the error map |Itpl − Iwrp| can be
computed to validate the correctness of the transformation where Itpl and Iwrp are the
template and warped images.
Given an affine transform A, you will write code to warp an image I(x) → I(Ax).
Using the warped image, the error map |Itpl − Iwrp| can be computed to validate the
correctness of the transformation, where Itpl and Iwrp are the template and warped
images.
def warp_image(img, A, output_size):
…
return img_warped
Input: I is an image to warp, A is the affine transformation from the original coordinate
to the warped coordinate, output_size=[h,w] is the size of the warped image where
w and h are the width and height of the warped image.
Output: img_warped is the warped image with the size of output_size.
Description: The inverse mapping method needs to be applied to make sure the
warped image does not produce empty pixels. You are allowed to use interpn function
imported from scipy.interpolate for bilinear interpolation (scipy package can be
easily installed through ”pip3 install scipy” if you have not installed it yet).
5
CSCI 5561: Project #2
Registration
6 Inverse Compositional Image Alignment
(a) Template (b) Initialization (c) Aligned image
Figure 5: You will use the initial estimate of the affine transform to align (i.e., track)
next image. (a) Template image from the first frame. (b) The second frame image
with the initialization of the affine transform. (c) The second frame image with the
optimized affine transform using the inverse compositional image alignment.
Given the initial estimate of the affine transform A from the feature based image alignment (Section 4) as shown in Figure 5(b), you will track the next frame image using the
inverse compositional method (Figure 5(c)). You will parametrize the affine transform
with 6 parameters p = (p1, p2, p3, p4, p5, p6), i.e.,
W(x; p) =
p1 + 1 p2 p3
p4 p5 + 1 p6
0 0 1
u
v
1
= A(p)x (1)
where W(x; p) is the warping function from the template patch to the target image.
x =
u
v
1
is the coordinate of the point before warping, and A(p) is the affine transform
parametrized by p. You may use filter2D to compute the gradient of template image.
def align_image(template, target, A):
…
return A_refined, errors
Input: grayscale template template and target image target; the initialization of
3×3 affine transform A, i.e., xtgt =Axtpl where xtgt and xtpl are points in the target and
template images, respectively.
Output: A_refined is the refined affine transform based on inverse compositional image alignment; errors records the alignment error (L2 norm) at each iteration.
Description: You will refine the affine transform using inverse compositional image
alignment, i.e., A→A_refined. The pseudo-code can be found in Algorithm 1.
Tip: You can validate your algorithm by visualizing their error map as shown in Figure 6(a). Also you can visualize the error plot over iterations, i.e., the error must
decrease as shown in Figure 6(b).
6
CSCI 5561: Project #2
Registration
Algorithm 1 Inverse Compositional Image Alignment
1: Initialize p = p0 from input A.
2: Compute the gradient of template image, ∇Itpl
3: Compute the Jacobian ∂W
∂p at (x; 0).
4: Compute the steepest descent images ∇Itpl
∂W
∂p
5: Compute the 6 × 6 Hessian H =
P
x
h
∇Itpl
∂W
∂p iT h
∇Itpl
∂W
∂p i
6: while True do
7: Warp the target to the template domain Itgt(W(x; p)).
8: Compute the error image Ierr = Itgt(W(x; p)) − Itpl.
9: Compute F =
P
x
h
∇Itpl
∂W
∂p iT
Ierr.
10: Compute ∆p = H−1F.
11: Update W(x; p) ← W(x; p) ◦ W−1
(x; ∆p) = W(W−1
(x; ∆p); p).
12: if ∥∆p∥ < ϵ then
13: break
14: end if
15: end while
16: Return A_refined made of p.
(a) Image Alignment Steps and Error Map (b) Error map
Figure 6: Left to right, top to bottom: Template images of the first frame, warped image
based on the initialization of the affine parameters, template image is overlaid by the initialization, error map of the initialization, repeated template images of the first frame, optimized
warped image using the inverse compositional image alignment, template image is overlaid by
the optimized warped image, error map of the optimization. (b) An error plot over iterations.
7
CSCI 5561: Project #2
Registration
7 Putting Things Together: Multiframe Tracking
Figure 7: You will use the inverse compositional image alignment to track 4 frames of
images.
Given a template and a set of consecutive images, you will (1) initialize the affine
transform using the feature based alignment and then (2) track over frames using the
inverse compositional image alignment.
def track_multi_frames(template, img_list):
…
return A_list, errors_list
Input: template is grayscale template. image_list is a list of consecutive image
frames, i.e., img_list[i] is the i
th frame.
Output: A_list is the set of affine transforms from the template to each frame of
image, i.e., A_list[i] is the affine transform from the template to the i
th image;
errors_list stores the alignment errors per frame across iterations.
Description: You will apply the inverse compositional image alignment sequentially
to track over frames as shown in Figure 7. Note that the template image needs to be
updated at every frame, i.e., template←warp_image(img, A, template.shape).
