Skip to content

ML4360 - Computer vision

Direct Linear Transform

Let X={x~i,x~i} denote a set of 2D2D correspondences.

Concatenate Ai into single 2n×9 matrix A leads to the following constrained least squares problem

h~=argminh~ ||Ah~||22+λ(||h~||221)=argminh~ h~TATAh~+λ(h~Th~1)

where we have fixed ||h~||22=1 as H~ is is homogeneous (i.e., defined only up to scale).

The solution to the above optimization problem is the singular vector corresponding to the smallest singular value of A. The resulting algorithm is called Direct Linear Transformation.

Singular Value Decomposition

The SVD of m×n matrix A is given by A=UΣVT=i=1ruiσiviT

where:

  • U: m×m orthogonal matrix of the orthonormal eigenvectors of AAT

  • VT: transpose of a n×n orthogonal matrix containing the orthonormal eigenvectors of ATA

  • Σ: a m×n matrix, actually a diagonal matrix with r elements equal to the root of the positive eigenvalues of AAT or ATA (both matrics have the same positive eigenvalues anyway) and mr extra zero rows and nr new zero columns.

Pseudoinverse Matrix

Definition

For AKm×n, a pseudoinverse of A is defined as a matrix A+Kn×m satisfying all of the following four criteria, known as the Moore–Penrose conditions:

  • AA+ need not be the general identity matrix, but it maps all column vectors of A to themselves:
AA+A=A.
  • A+ acts like a weak inverse:
A+AA+=A+.
  • AA+ is Hermitian. Hermitian matrix is a complex square matrix that is equal to its own conjugate transpose.
A HermitianA=AT=AH
  • A+A is also Hermitian.

Linear least-squares

The pseudoinverse provides a least squares solution to a system of linear equations.For AKm×n, given a system of linear equations Ax=b, in general, a vector x that solves the system may not exist, or if one does exist, it may not be unique. More specifically, a solution exists if and only if b is in the image of A, and is unique if and only if A is injective. The pseudoinverse solves the "least-squares" problem as follows:

  • xKn, we want to find a z satisfying Azb2Axb2, where z=A+b and 2 denotes the Euclidean norm.

  • This weak inequality holds with equality if and only if x=A+b+(IA+A)w for any vector w; this provides an infinitude of minimizing solutions unless A has full column rank, in which case (IA+A) is a zero matrix.

Assume we want to solve n in Sn=I where S is a real matrix. A solution may not unique. We can use pseudoinverse to solve it.

STI=STSnn=(STS)1STI

(STS)1ST here is pesudoinverse. * Reference: wikipedia

Chamfer Distance

Chamfer Distance is widely used in 3D reconstruction to judge how close one point cloud is on average to the other.

Given two point clouds X and Y, Chamfer Distance is defined as follows:

d=0.5(1|X|xiXminyjYxiyj2+1|Y|yjYminxiXxiyj2)

In the following code, we use the KDTree to get the nearest neighbors of one point cloud to the other.

Chamfer Distance
def chamfer_distance(pcl_0, pcl_1):     # pcl_0 and pcl_1 are two point clouds in 3D space
    assert pcl_1.shape[-1] == 3
    assert pcl_0.shape[-1] == 3
    kd_pcl_0 = KDTree(pcl_0)
    kd_pcl_1 = KDTree(pcl_1)
    mindis_x2y, nearest_x2y= kd_pcl_1.query(pcl_0)
    mindis_y2x, nearest_y2x= kd_pcl_0.query(pcl_1)
    chamfer_dist = 0.5 * float(mindis_x2y.mean() + mindis_y2x.mean())
    assert type(chamfer_dist) == float
    return chamfer_dist