The purpose of this assignment is to get students hands on experience computing Procrustes Distance/Alignment and performing the Iterative Closest Points (ICP) algorithm (see Lecture 13 slides for more details). Because of the timing and the subject matter, this can be thought of as the programming part of the midterm, though it will still be grouped in and weighted in the Programming Assignments category
The code in this assignment is overall very short compared to other assignments you have done so far, but you need to be very careful about the finer points of matrix dimensions, transposes, and multiplication order to get this to work properly. This will also give everyone a first exposure to using numpy with geometry, which is needed in group assignment 2. Please have a look at the numpy demos we went over in class for some tricks that might help in this assignment and the next one.
This assigment is due at 11:55PM on Sunday 3/13. The first 5 points, which are setting up Python and taking a screenshot, are due on Wednesday 3/9, no exceptions and no partial credit (to make sure people are on track to setting up their Python environment).
Once you are finished, zip up your code and the sequence of images you generated in the examples section. Please also include a README with observations in the testing and examples sections, as well as any comments on the assignment and how many hours it took you.
To run the code, you will first need to make sure you have Python 2.7 installed, as well as some packages. The packages you need are
sudo apt-get install python-numpy python-scipy python-matplotlib python-opengl python-wxtools
Once you have these packages installed, you can run the file ICPView.py
, which is the entry point to running your code, which will be implemented in the file ICP.py
. ICPView.py
takes two command line arguments. The first argument is the path to the mesh that you want to aligned (referred to as "mesh X" from now on), and the second argument is the path to "target mesh" to which the first mesh will be aligned (called "mesh Y" or the "target mesh" from now on). For instance, if you run
then you should see something like this:
This GUI will help you to debug your code as you write it by showing you what correspondences you have found between two shapes, as well as what your Procrustes alignment step is doing. Left click + drag to rotate the camera, center click + drag to translate, and right click + drag to zoom. You can also compute an entire run of the ICP algorithm and play it back as an animation, and if you enter something into the text field "output prefix," then the program will output a sequence of PNG images that make up the movie. For example, here's what a working implementation would look like aligning the mesh candide.off
to the mesh NotreDameFrontHalf.off
candide2NotreDame.ogg |
An example of aligning candide.off to NotreDameFrontHalf.off |
ICPViewGLUT.py
. There are no textbox inputs enabled in this GUI, so you will have to pass a few more parameters along in the command line. The usage is as follows:
For example
Will start the program with the candide mesh and the Notre Dame mesh, capping ICP at a 200 iterations and saving the video frames with the prefix "candide." The GUI controls are as follows (most of the checkboxes and menu items in the ordinary GUI have been replaced with keyboard shortcuts)
pip uninstall PyOpenGL PyOpenGL-accelerate
)and try installing it instead from source. You'll have to download the three packages from here
conda install -c https://conda.anaconda.org/anaconda wxpython
ICPViewer.py
running by Wednesday 3/9. All or nothing on these points by that date
getCentroid(PC)
in ICP.py
to compute the centroid of a point cloud, where the points are along the columns of a 3 x N matrix. So you should return a 3 x 1 matrix representing the centroid. This should be one line of code (hint: use np.mean()
along some axis). You can test to make sure it's working properly in ICPViewer
by loading two shapes and clicking the "center meshes on centroids" button (Note that this is not exactly what happens in Procrustes alignment, since the centroids of the target mesh are computed on corresponding points only, but it can help you make sure your centroid step is correct). After the centroids are computed, be sure to re-center the camera by clicking the "Y Mesh" or the "X Mesh" views buttons.getCorrespondences(X, Y, Cx, Cy, Rx)
in ICP.py
. That is, given a centroid estimate for point clouds X and Y and a rotation matrix to align X with Y after centering both on their centroids, you need to compute the nearest neighbors on mesh Y to every point in mesh X. This example from class may be of some help. To complete that example, you need to fill in a matrix D where D[i, j] is the Euclidean or squared Euclidean distance between point i in X and point j in Y, and that code computes the index of the minimum distance along each row. You can use the "find correspondences" button in the GUI to help debug this:getProcrustesAlignment(X, Y, idx)
. To do this, you need to
np.linalg.svd
should come in handy here. Recall from lecture 13 that the SVD factorization of the matrix AB^{T}, ignoring the scaling matrix, gives you the optimal rotation matrix to rotate point cloud B to align with point cloud A.
doICP(X, Y, MaxIters)
. You should loop as long as the correspondences are all different from the correspondences you got last time. If they are the same, this means that the process has converged. Again, you can check for this without using a loop (you will lose 2 points if you check this with a loop: try, for instance, using some boolean condition and np.sum()
). You only have to loop up to the maximum number of iterations, regardless of convergence.
ICPView.py
with ICPViewGLUT.py
if you're using that):
Next, try doing this the other way around; that is, aligning
What do you notice? Why is this happening? What does this say about the symmetry (or lack thereof) of the ICP algorithm?
In addition to aligning the face model to the statue, you should try this out on other examples. A variety of meshes are included in the meshes/
directory in the code distribution. Please submit with your assignment a sequence of images that show your program in action aligning one of those meshes to another one, by filling in a string in the "Output Prefix" field before clicking "Animate ICP" (or in the GLUT GUI by providing a fourth command line argument of that prefix). Note that you can move the camera before or during the animation to get a better view.
If you are creative about what you align to what, you can probably create some interesting concepts. Therefore, if you would like, you can also choose to submit your alignment video to the art contest for this assignment. Please indicate that you would like to submit your example and whether or not I can include your name on the course web site (and if not what your pseudonym should be). The winner will get two raffle points. Feel free to use any of the meshes in the Princeton Shape Database as you did for the image source assignment.
Finally, there has been a script provided that facilitates changing the geometry of different meshes before you align them. Check out the file manipulateGeometry.py
. That example shows applying a random rotation to an .off file, but you can do anything you want. Remember that the initial guess has a huge effect on ICP, so if you choose a different position or orientation that will influence where the algorithm converges