Technical Tips

This page provides a collection of technical tips to help you with all steps of the assignment. In contrast to the more general Readings, these tips are more focused, and address precise technical problems. However, they do not provide the context of their application, so make sure to study all the relevant course material before digging further below. Also, check the Additional material, which provides also technical tips, but at a lower level (toolkits) than the tips below.

MS Word versions of the above documents here.

Apart from the above tech tips documents, below is a selection of technical tips which are asked for most frequently by students. You can skip reading these if you looked through ''all' tech mentioned above.

Computing PCA in Python

Principal Component Analysis (PCA) is used at various points in the MR pipeline, e.g., for pose normalization. Below is a Python code fragment that computes the eigenvalues and eigenvectors of a 3D shape's covariance matrix (the shape is modeled as a set of 3D vertices). Please note that necessary tabs may miss, so this code is not copy-and-paste ready for your Python editor.

import numpy as np
# generate a matrix (3, n_points) for 3D points
# row 0 == x-coordinate
# row 1 == y-coordinate
# row 2 == z-coordinate

n_points = 5000

x_coords = np.random.uniform(-10, 10, n_points)
y_coords = np.random.uniform(-3, 3, n_points)
z_coords = np.random.uniform(-1, 1, n_points)

A = np.zeros((3, n_points))
A[0] = x_coords
A[1] = y_coords
A[2] = z_coords

# compute the covariance matrix for A 
# see the documentation at 
# https://docs.scipy.org/doc/numpy/reference/generated/numpy.cov.html
# this function expects that each row of A represents a variable, 
# and each column a single observation of all those variables
A_cov = np.cov(A)  # 3x3 matrix

# computes the eigenvalues and eigenvectors for the 
# covariance matrix. See documentation at  
# https://docs.scipy.org/doc/numpy/reference/generated/numpy.linalg.eig.html 
eigenvalues, eigenvectors = np.linalg.eig(A_cov)

print("==> eigenvalues for (x, y, z)")
print(eigenvalues)
print("\n==> eigenvectors")
print(eigenvectors)

Computing volume of a 3D mesh

The formula for compactness involves computing the volume enclosed by a 3D mesh. Computing the volume of a triangle-only mesh is very simple. Code and explanations here.

Intuition: for each triangle, you compute the volume of a tetrahedron formed by the triangle plus the origin (or any other fixed world-point). The volume will be 'signed', in the sense that if the normal of that triangle points in the same direction (angle < 90 degrees) as the three tetrahedron edges linking the triangle's vertices with the fixed point, the volume will be positive; else, it will be negative. Intuitively, you 'add up' the volumes of the tetrahedra for the triangles whose normals face in one direction, and 'subtract' the volumes of the tetrahedra for the triangles whose normals point in the opposite direction. The result is the volume contained inside the mesh.

Notes:

for this to work, the mesh must be closed (watertight). If not, the volume you compute will be that of a closed shape formed by the mesh triangles and those formed by lines emerging from all vertices and going to the reference point. You may have a few such shapes in your databases. Since you will apply the computation of 3D compactness after normalization (when the shape's barycenter is translated to the origin), if you use the origin as reference point, you'll get a volume which is identical to the one of a watertight shape formed from your open shape by closing the openings by connecting their border points with the origin. For compactness estimation, this should be fine.
also, all mesh triangles must be oriented in the same way, i.e., with their normals pointing all outwards or all inwards. It is not entirely trivial to check/enforce this for any kind of 3D shape (convex or concave). However, to my knowledge, all shapes in the Princeton Benchmarks comply with this requirement.

Flipping test: Why needed?

As part of pose normalization, you have to implement a flipping test (see Module 4, slide 131). Here is a question that I often hear (and its answer):

Q: If I translate a shape so that its barycenter is in the origin, why do I still have to do a flipping test and possible flip? Won't there always be equal mass balanced to the e.g. left and right?

A: No. The flipping test (and possible flipping) is still needed. Don't confuse mass with momentum.

Translating a shape to its barycenter ensures that, indeed, the shape is balanced. If we hang a shape from its barycenter by a thread, it won't rotate. For a nice graphical illustration, see this post.

What does it mean if a shape is balanced? Does it mean that there's equal mass to the left and right of the thread the shape hangs from? No. It means that the momentum of the left part is equal to the momentum of the right part. The momentum of a particle equals its mass times its distance to the axis of symmetry (in our case, the thread the shape hangs from). Assuming uniform mass density, this means that for every particle in the left half at a distance d, there's a particle in the shape at distance d in the right half. Summing up, we find out that the barycenter is the average of all particles' coordinates (in our implementation, the 'particle' could be a triangle or a vertex).

So, if the shape is balanced, the momentum of the left half = momentum of the right half, and not that the mass of the left half = mass of the right half.

Simple example: Sketch a triangle and its barycenter (intersection of median lines). Imagine you cut the triangle at the barycenter with a line parallel to one of its edges, this line being the hanging thread. You get a trapezium and a smaller triangle. Basic geometry shows that the areas of the two are not equal.

Hence, the flipping test is indeed needed to ensure that we place the 'most mass' always in the same way (say, left) for different shapes in the database.

Checking normalizations

Steps 2 of the assignment involve several normalizations (of the shapes sampling densities, sizes, and poses). How to check if you implemented such normalizations correctly?

This can be done generically (and easily) for all above cases. Consider any quantity Q that is measured for a shape, such as

number of sampling points (vertices)
size of bounding box (computed via its diagonal)
position of bounding box (distance of its center to the origin)
pose (absolute value of cosine of angle between major eigenvector and, say, the X axis)

All these are scalar quantities.

What does a good normalization do? It reduces the variance of Q. Hence, to check if your normalization works OK, you can compute an indication of Q's variance before and then after the normalization, and compare them. If variance drops significantly, the normalization worked properly.

You can estimate this variance in several ways. From more aggregated (less informative) to less aggregated (more informative):

compute the average and standard deviation of Q: The standard deviation should drop after normalization. The average indicates the value around which normalization brings the shapes.
compute a histogram of Q over a fixed number of bins: Normalization should make the histogram more pointy, that is, having (ideally) a single large peak and being nearly zero away from that peak.

Shape diameter computation

This descriptor is part of those used for CBSR. How to compute it? For a shape of N vertices, of course, there is the brute-force solution which is O(N*N). However, much faster algorithms exist. One of them is described here.

Note: I have not tested the above code myself, so this is provided 'as is'. Feel free to experiment with this code. However, if getting it work correctly takes too long, ignore it and revert to simpler (albeit slower) solutions.

Comparing mixed feature vectors

A mixed feature vector is a vector that contains different types of features:

f = (e₁ e₂ ... e_n h₁ h₂ ... h_m)

We have two types of features in this vector:

e₁,...,e_n are global metrics, e.g. compactness, elongation, and similar. Each of them is a single scalar value.
h₁,...,h_m are histogram-based metrics, e.g., the A3, D1, and similar descriptors. Each of them is a N-valued vector, where N is the number of histogram bins.

Hence, f contains n + N*m elements in total.

How to compare two such feature vectors f and f'? Several options exist:

Use L₂ metric (simplest): The distance of f to f' is the square-root of the sum of squared differences between corresponding entries, sqrt((e₁-e₁')² + (e₂-e₂')² + ... (h₁₁-h₁₁')² + (h₁₂-h₁₂')² + ...), where h_ij indicates the j-th bin of the i-th histogram.

In this case, it is essential to normalize the histogram features: Each h_i should have the same weight as each e_i. Since a histogram h_i has N bins, the simplest way to achieve this is to divide each bin-value h_ij by N. The set of N bins of h_i will have, taken together, the same weight (one) as a scalar e_i.

Use a mix of metrics: Say you want to use EMD (Earth Mover's Distance) for histograms and L₂ for the global descriptors. This can be done as follows:

compare all the global features e_i with their counterparts e_i' using the L₂ metric, as above; say this gives you a distance d_e(f,f')
compare each histogram h_i with its counterpart h_i' using EMD or any other histogram metric; this gives you m distances d_h1(f,f'), ...d_hm(f,f')
assemble all above distances in a final distance. If d_e, d_h1, ..., d_hm are suitably normalized (i.e. in the same range), you can just return their average.

You cannot apply EMD or any other histogram-specific distance metrics on the entire vectors f, f' since these vectors do not contain only bin-values of a single histogram, but bins of m histograms, and also the global features e_i. Simply using EMD on f, f' would be as if you shift earth (recall the EMD metaphor) between, say, e₂ and h₁, or between h₂ and h₃, i.e., you would compare apples and pears, leading to wrong results.

Multimedia Retrieval

Lectures

Assignment

Others