Computer Vision II, HW2 Solution

Description

1.2 Problem 1 (Math): Line-plane intersection (5 points)

The line in 3D defined by the join of the points X₁ = (X₁, Y₁, Z₁, T₁)^⊤ and X₂ = (X₂, Y₂, Z₂, T₂)^⊤ can be represented as a Plucker matrix L = X₁X^⊤₂ − X₂X^⊤₁ or pencil of points X(λ) = λX₁ + (1 − λ)X₂ (i.e., X is a function of λ). The line intersects the plane π = (a, b, c, d)^⊤ at the point

• _L = Lπ or X(λ_π), where λ_π is determined such that X(λ_π)^⊤π = 0 (i.e., X(λ_π) is the point on π). Show that X_L is equal to X(λ_π) up to scale.

Your solution here

1.3 Problem 2 (Math): Line-quadric intersection (5 points)

In general, a line in 3D intersects a quadric Q at zero, one (if the line is tangent to the quadric), or two points. If the pencil of points X(λ) = λX₁ + (1 −λ)X₂ represents a line in 3D, the (up to two) real roots of the quadratic polynomial c₂λ²_Q + c₁λ_Q + c₀ = 0 are used to solve for the intersection

point(s) X(λ_Q). Show that c₂ = X^⊤₁QX₁ − 2X^⊤₁QX₂ + X^⊤₂QX₂, c₁ = 2(X^⊤₁QX₂ − X^⊤₂QX₂), and c₀ = X^⊤₂QX₂.

Your solution here

1.4 Problem 3 (Programming): Linear Estimation of the Camera Projection Matrix (15 points)

Download input data from the course website. The file hw2_points3D.txt contains the coordinates

˜ ˜ ˜

of 50 scene points in 3D (each line of the file gives the X_i, Y_i, and Z_i inhomogeneous coordinates of

a point). The file hw2_points2D.txt contains the coordinates of the 50 corresponding image points in 2D (each line of the file gives the x˜_i and y˜_i inhomogeneous coordinates of a point). The scene points have been randomly generated and projected to image points under a camera projection matrix (i.e., x_i = P X_i), then noise has been added to the image point coordinates.

Estimate the camera projection matrix P _DLT using the direct linear transformation (DLT) al-gorithm (with data normalization). You must express x_i = P X_i as [x_i]^⊥P X_i = 0 (not x_i × P X_i = 0), where [x_i]^⊥x_i = 0, when forming the solution. Return P _DLT, scaled such that

||P _DLT||_Fro = 1

The following helper functions may be useful in your DLT function implementation. You are welcome to add any additional helper functions.

[1]: import numpy as np

import time

def Homogenize(x):

• converts points from inhomogeneous to homogeneous coordinates return np.vstack((x,np.ones((1,x.shape[1]))))

def Dehomogenize(x):

• converts points from homogeneous to inhomogeneous coordinates return x[:-1]/x[-1]

def Normalize(pts):

• data normalization of n dimensional pts

• Input:

• pts – is in inhomogeneous coordinates

• Outputs:

• pts – data normalized points

• T – corresponding transformation matrix

“””your code here”””

T = np.eye(pts.shape[0]+1)

return pts, T

def ComputeCost(P, x, X):

• Inputs:

• P – the camera projection matrix

• x – 2D inhomogeneous image points

• X – 3D inhomogeneous scene points

• Output:

• cost – Total reprojection error

“””your code here”””

cost = np.inf

return cost

[3]: def DLT(x, X, normalize=True):

• Inputs:

• x – 2D inhomogeneous image points

• X – 3D inhomogeneous scene points

• normalize – if True, apply data normalization to x and X

• Output:

• P – the (3×4) DLT estimate of the camera projection matrix P = np.eye(3,4)+np.random.randn(3,4)/10

• data normalization

if normalize:

x, T = Normalize(x)

X, U = Normalize(X)

else:

x = Homogenize(x)

X = Homogenize(X)

“””your code here”””

• data denormalize if normalize:

P = np.linalg.inv(T) @ P @ U

return P

def displayResults(P, x, X, title):

print(title+‘ =’)

print (P/np.linalg.norm(P)*np.sign(P[-1,-1]))

# load the data

x=np.loadtxt(‘hw2_points2D.txt’).T

X=np.loadtxt(‘hw2_points3D.txt’).T

assert x.shape[1] == X.shape[1]

n = x.shape[1]

• compute the linear estimate without data normalization print (‘Running DLT without data normalization’) time_start=time.time()

P_DLT = DLT(x, X, normalize=False) cost = ComputeCost(P_DLT, x, X) time_total=time.time()–time_start

• display the results

print(‘took %f secs’%time_total)

print(‘Cost=%.9f‘%cost)

• compute the linear estimate with data normalization print (‘Running DLT with data normalization’) time_start=time.time()

P_DLT = DLT(x, X, normalize=True) cost = ComputeCost(P_DLT, x, X) time_total=time.time()–time_start

• display the results

print(‘took %f secs’%time_total)

print(‘Cost=%.9f‘%cost)

print(“\n==Correct outputs==”)

print(“Cost=%.9f without data normalization”%97.053718991)

print(“Cost=%.9f with data normalization”%84.104680130)

Running DLT without data normalization

took 0.000463 secs

Cost=inf

Running DLT with data normalization

took 0.000401 secs

Cost=inf

==Correct outputs==

Cost=97.053718991 without data normalization Cost=84.104680130 with data normalization

[4]: # Report your P_DLT value here!

displayResults(P_DLT, x, X, ‘P_DLT’)

P_DLT =

[[ 0.60369009 -0.02436935 -0.13541828 0.00823547] [ 0.00946005 0.58272017 0.05249946 -0.13460888] [ 0.01359714 0.00299854 0.49864781 0.08477583]]

1.5 Problem 4 (Programming): Nonlinear Estimation of the Camera Projection Matrix (30 points)

Use P _DLT as an initial estimate to an iterative estimation method, specifically the Levenberg-Marquardt algorithm, to determine the Maximum Likelihood estimate of the camera projection matrix that minimizes the projection error. You must parameterize the camera projection matrix as a parameterization of the homogeneous vector p = vec(P ^⊤). It is highly recommended to implement a parameterization of homogeneous vector method where the homogeneous vector is of arbitrary length, as this will be used in following assignments.

Report the initial cost (i.e. cost at iteration 0) and the cost at the end of each successive iteration. Show the numerical values for the final estimate of the camera projection matrix P _LM, scaled such that ||P _LM||_Fro = 1.

The following helper functions may be useful in your LM function implementation. You are welcome and encouraged to add any additional helper functions.

Hint: LM has its biggest cost reduction after the 1st iteration. You’ll know if you are implementing LM correctly if you experience this.

[5]: # Note that np.sinc is different than defined in class def Sinc(x):

• Returns a scalar valued sinc value

“””your code here”””

y = x

return y

def Jacobian(P,p,X):

• compute the jacobian matrix

• Input:

• P – 3×4 projection matrix

• p – 11×1 homogeneous parameterization of P

• X – 3n 3D scene points

• Output:

• J – 2nx11 jacobian matrix

J = np.zeros((2*X.shape[1],11))

“””your code here”””

return J

def Parameterize(P):

• wrapper function to interface with LM

• takes all optimization variables and parameterizes all of them

• in this case it is just P, but in future assignments it will

• be more useful

return ParameterizeHomog(P.reshape(-1,1))

def Deparameterize(p):

• Deparameterize all optimization variables return DeParameterizeHomog(p).reshape(3,4)

def ParameterizeHomog(V):

• Given a homogeneous vector V return its minimal parameterization

“””your code here”””

return v_hat

def DeParameterizeHomog(v):

• Given a parameterized homogeneous vector return its deparameterization

“””your code here”””

return v_bar

def Normalize_withCov(pts, covarx):

• data normalization of n dimensional pts

• Input:

• pts – is in inhomogeneous coordinates

• covarx – covariance matrix associated with x. Has size 2n x 2n, where␣ ,→n is number of points.

• Outputs:

• pts – data normalized points

• T – corresponding transformation matrix

• covarx – normalized covariance matrix

“””your code here”””

T = np.eye(pts.shape[0]+1)

return pts, T, covarx

def ComputeCost_withCov(P, x, X, covarx):

• Inputs:

• P – the camera projection matrix

• x – 2D inhomogeneous image points

• X – 3D inhomogeneous scene points

• covarx – covariance matrix associated with x. Has size 2n x 2n, where␣ ,→n is number of points.

• Output:

• cost – Total reprojection error

“””your code here”””

cost = np.inf

return cost

[6]: def LM(P, x, X, max_iters, lam):

• Input:

• P – initial estimate of P

• x – 2D inhomogeneous image points

• X – 3D inhomogeneous scene points

• max_iters – maximum number of iterations

• lam – lambda parameter

• Output:

• P – Final P (3×4) obtained after convergence

• data normalization

covarx = np.eye(2*X.shape[1])

x, T, covarx = Normalize_withCov(x, covarx)

X, U = Normalize(X)

“””your code here”””

• you may modify this so long as the cost is computed

• at each iteration

for i in range(max_iters):

cost = ComputeCost_withCov(P, x, X, covarx)

print (‘iter %03d Cost %.9f‘%(i+1, cost))

# data denormalization

P = np.linalg.inv(T) @ P @ U

return P

• LM hyperparameters lam = .001 max_iters = 100

• Run LM initialized by DLT estimate with data normalization print (‘Running LM with data normalization’)

print (‘iter %03d Cost %.9f‘%(0, cost)) time_start=time.time()

P_LM = LM(P_DLT, x, X, max_iters, lam) time_total=time.time()–time_start print(‘took %f secs’%time_total)

print(“\n==Correct outputs==”)

print(“Begins at %.9f; ends at %.9f“%(84.104680130, 82.790238005))

Running LM with data normalization

iter 000 Cost inf

iter 001 Cost inf

iter 002 Cost inf

iter 003 Cost inf

iter 004 Cost inf

iter 005 Cost inf

iter 006 Cost inf

iter 007 Cost inf

iter 008 Cost inf

iter 009 Cost inf

iter 010 Cost inf

iter 011 Cost inf

iter 012 Cost inf

iter 013 Cost inf

iter 014 Cost inf

iter 015 Cost inf

iter 016 Cost inf

iter 017 Cost inf

iter 018 Cost inf

iter 019 Cost inf

iter 020 Cost inf

iter 021 Cost inf

iter 022 Cost inf

iter 023 Cost inf

iter 024 Cost inf

iter 025 Cost inf

iter 026 Cost inf

iter 027 Cost inf

iter 028 Cost inf

iter 029 Cost inf

iter 030 Cost inf

iter 031 Cost inf

iter 032 Cost inf

iter 033 Cost inf

iter 034 Cost inf

iter 035 Cost inf

iter 036 Cost inf

iter 037 Cost inf

iter 038 Cost inf

iter 039 Cost inf

iter 040 Cost inf

iter 041 Cost inf

iter 042 Cost inf

iter 043 Cost inf

iter 044 Cost inf

iter 045 Cost inf

iter 046 Cost inf

iter 047 Cost inf

iter 048 Cost inf

iter 049 Cost inf

iter 050 Cost inf

iter 051 Cost inf

iter 052 Cost inf

iter 053 Cost inf

iter 054 Cost inf

iter 055 Cost inf

iter 056 Cost inf

iter 057 Cost inf

iter 058 Cost inf

iter 059 Cost inf

iter 060 Cost inf

iter 061 Cost inf

iter 062 Cost inf

iter 063 Cost inf

iter 064 Cost inf

iter 065 Cost inf

iter 066 Cost inf

iter 067 Cost inf

iter 068 Cost inf

iter 069 Cost inf

iter 070 Cost inf

iter 071 Cost inf

iter 072 Cost inf

iter 073 Cost inf

iter 074 Cost inf

iter 075 Cost inf

iter 076 Cost inf

iter 077 Cost inf

iter 078 Cost inf

iter 079 Cost inf

iter 080 Cost inf

iter 081 Cost inf

iter 082 Cost inf

iter 083 Cost inf

iter 084 Cost inf

iter 085 Cost inf

iter 086 Cost inf

iter 087 Cost inf

iter 088 Cost inf

iter 089 Cost inf

iter 090 Cost inf

iter 091 Cost inf

iter 092 Cost inf

iter 093 Cost inf

iter 094 Cost inf

iter 095 Cost inf

iter 096 Cost inf

iter 097 Cost inf

iter 098 Cost inf

iter 099 Cost inf

iter 100 Cost inf

took 0.004240 secs

==Correct outputs==

Begins at 84.104680130; ends at 82.790238005

[7]: # Report your P_LM final value here!

displayResults(P_LM, x, X, ‘P_LM’)

P_LM =
[[ 0.60369009		-0.02436935	-0.13541828	0.00823547]
[	0.00946005	0.58272017	0.05249946	-0.13460888]
[	0.01359714	0.00299854	0.49864781	0.08477583]]

10