Question 1: Filtering (9pts)
a) Briefly explain what the kernel below would give us when it is used to filter an image.
How can we compute the gradient directions in the image using this kernel? (3pts)
0 1 2
-1 0 1
-2 -1 0
b) Given a low-pass filter, we can get the high-pass filtered image by first filtering it using
the low-pass filter and subtracting it from the original image. Alternatively, following
the same idea, we can generate a high-pass filter kernel from a low-pass filter kernel.
Compute a high-pass filter kernel using the low-pass filter kernel given below. (3pts)
0.03 0.11 0.03
0.11 0.44 0.11
0.03 0.11 0.03
c) Briefly explain why the low-pass filter kernel below can not directly be used to generate
a high-pass filter kernel as we did in Part (a). Explain how we can modify the method
above to generate a high-pass filter kernel using the kernel below. (3pts)
1 2 1
2 5 2
1 2 1
Question 2: Optical flow (7pts)
a) Briefly explain the aperture problem. (1pt)
We make 3 certain assumptions when developing the Kanade-Lukas optical flow algorithm.
Let’s analyze them:
b) Briefly explain the brightness constancy assumption. When do we make use of this
assumption when developing our formulation? (2pts)
c) Briefly explain the spatial coherence assumption. At what stage does the Lukas-Kanade
formulation make use of this assumption? (2pts)
d) Briefly explain the small motion assumption. How do we work around this assumption
when the motion is large? (2pts)
1
Question 3: Transformations, Least Squares, RANSAC (26pts)
Note: This question may appear intimidating because of its length. Don’t be intimidated!
This question is long because each small step guides you towards the final solution. While
some steps depend on previous ones, some are independent questions. Don’t rush and go
over the question step by step. Good luck!
We define a transformation between two images as follows:
x′y′
w
=
a b cd e f
0 0 1
xy
w
(1)
where (x, y, x′, y′) are the coordinates of a pixel before and after the transformation.
a) What type of transformation is this? What type of operations between two images can
this transformation represent? (1pt)
b) Mathematically demonstrate that this transformation is closed under composition.
(2pts)
If this transformation is unknown, we will need to estimate it from known ((x, y)− (x′, y′))
pairs. In this case, the unknown vector will be t⃗ =
[
a b c d e f
]T
.
c) Open the matrix formulation and write down Equation 1 as a set of equations. (1pt)
d) Rewrite this set of equations in At⃗ = b⃗ form, where t⃗ =
[
a b c d e f
]T
. (2pts)
e) What are the dimensions of A? How many point matches at minimum do we need to
solve for t⃗? Why? (2pts)
f) Let’s assume that we have 4 matching points, (x1, y1) − (x′1, y′1) to (x4, y4) − (x′4, y′4).
Rewrite your equation in Part 3d again, this time including all the point matches in
the formulation. (2pts)
There are now more equations than unknowns, which means that this is an overconstrained
linear system. To arrive at a solution, we will need to find the most agreeable solution to
all these points, so we will apply a least squares formulation.
To apply least squares, we define our energy (or error) function as e = ∥At⃗− b∥2, take its
derivative with respect to the unknown vector and equate it to zero. Let’s do it step by
step:
g) Distribute the multiplication to openly write down e = ∥At⃗− b∥2 = (At⃗− b)T (At⃗− b)
in matrix form. (2pt)
h) Take the derivative of the matrix equation from last part with respect to t⃗. (3pts)
Some very useful formulas:
∂
∂x⃗
(
x⃗ TATAx⃗
)
= 2Ax⃗ AT x⃗ = x⃗ TA
i) Equate the derivative you found to zero and write down t⃗ in terms on A and b⃗. (2pts)
2
Now, we have a way to estimate the transformation from 4 matching points. In our ap-
plication scenario of finding point matches and computing the transformation from them
as we did in class, we will have many more point pairs than 4. However, some of these
matches will be incorrect.
So, we will apply outlier detection, RANSAC, before computing our final estimation.
j) Why do we want to avoid including outliers in our least squares formulation? (1pt)
k) Briefly explain how RANSAC works. (2pts)
In our version of RANSAC in this question, we will create many random selections of 4
point matches to generate many hypotheses.
l) Which equation from previous parts do we need to compute a hypothesis? Explain.
(2pts)
m) Which equation from previous parts can we use to compute how good a given hypothesis
is? Explain. (2pts)
n) After we find the best hypothesis, how do we identify outliers? (2pts)
3