Iterative Closest Point (ICP)

In this exercise you will implement the ICP algorithm.
Your implementation will include the following:

1. A kd-tree, either the standard median kd-tree or the eigen kd-tree.
2. Acceleration using the linear and parabolic extrapolation methods as described in class.

Class Interface Definitions

1. kd-tree:
Your kd-tree must implement the NearestNeighbor interface. I supply you with a naive implementation of the nearest neighbor query and a test program.
I also supply you with two input files:
1. cloud.pnt
2. cloudSubSet.pnt (a sub set of the points found in cloud.pnt).
Each file contains a serialized Vector of Point3D objects. Do not try to create a kd-tree with a bin size of one, there are multiple appearances of the same point in the data
If you want to see what these points represent goto here.

public KDTree(Vector points, int binSize, boolean copy);

copy is a boolean which says if you have to make an internal copy of the data or not.
 

2. ICP:
Implementation of the ICP algorithm. Point pairing in each iteration is done using your kd-tree implementation. The rigid transformation in each iteration is computed with Horn's closed form solution (previous exercise). You will also implement the acceleration by extrapolation (linear and parabolic).

public Icp(int maxIterations, double epsilon);
public Frame apply(Frame initialGuess, Vector left, Vector right);

epsilon is the minimal change of the RMS between consecutive iterations which is still considered a change.

Analysis

What is the breakdown point of the algorithm, for what rotations/translations does it converge to a minimum which is not the global one, assuming that the initial transformation is the identity.
Your analysis should include the following table (ax - rotation around x axis etc. dx - translation in the x direction etc.)

Experiment Number | Actual Transformation     |  Computed Transformation | Number of Iterations
-----------------------------------------------------------------------------------------------------------------------
             1                |  ax,ay,az,dx,dy,dz           |  ax,ay,az,dx,dy,dz               |           xxx
                                                                       :
                                                                       :
             n                |  ax,ay,az,dx,dy,dz           |  ax,ay,az,dx,dy,dz               |           xxx
 

How much faster does the algorithm converge when using the extrapolation acceleration compared to the basic implementation.
Your analysis should include the following table (experiment number na - without extrapolation, nb - with extrapolation. ax - rotation around x axis etc. dx - translation in the x direction etc.)

Experiment Number | Actual Transformation     |  Computed Transformation | Number of Iterations | Time to Convergence
------------------------------------------------------------------------------------------------------------------------------------------------
             1a              |  ax,ay,az,dx,dy,dz           |  ax,ay,az,dx,dy,dz               |           xxx                  |          ttt
             1b              |  ax,ay,az,dx,dy,dz           |  ax,ay,az,dx,dy,dz               |           xxx                  |          ttt
                                                                       :
                                                                       :
             na                |  ax,ay,az,dx,dy,dz          |  ax,ay,az,dx,dy,dz               |           xxx                 |          ttt
             nb                |  ax,ay,az,dx,dy,dz          |  ax,ay,az,dx,dy,dz               |           xxx                 |          ttt
 
 

Technical Issues

1. Use the Point3D class whose API is found here. Don't forget to set your classpath to ~cas\imports (javac -classpath ~cas\imports:.).
2. Create a jar file containing the following files: Icp.java, KDTree.java, README.
3. Your README file should contain your analysis as specified above and your identification info (login, name, student i.d.).
4. Send the jar file to me zivy@cs.huji.ac.il.

VRML (Virtual Reality Modeling Language)

1. cloud.wrl
2. cloudSubSet.wrl