I would like to reduce the "differentness" of two point clouds $X$ and $Y$ to a single comparable value $\lambda$, which would ideally be $0$ when $X$ and $Y$ are identical upto isometry (rotation, translation, reflection) and increasingly further from $0$ as $X$ and $Y$ become more difficult to match. The measure will in general be applied to large sets of points.
I'm aware that this is very vague, so I will present what I have some up with so far, and I would appreciate some kind of guidance. Feel free to stop reading my tirade at any point if you feel you understand the gist, as I tend to ramble:
We begin by computing the distance between each pair of points in $X$ and storing these distances in a matrix $D_X$. We similarly make a $D_Y$. These distances are invariant under rotation, translation, or reflection of their respective point cloud, which is desirable.
The next step is to compare these matrices. However, even if the two point clouds were "similar", one might have a few more points than the other, so the distance matrices might be of different size (though both square.) Therefore, the matrix comparison method must find matrices which share a large square submatrix to be "similar". Moreover, even if the two point clouds were "similar", their vertices were likely paired in different orders in the two matrices. Therefore, the matrix comparison method must be independent of permutation of the points (simultaneous row/column permutation.)
Suppose $\left|X\right| \leq \left|Y\right|$. One could "brute force" the problem by taking the cell-wise sums of squares between $D_X$ and every permutation of every $|X|$-point submatrix of $D_Y$ and using the smallest of these as the "differentness" of $X$ and $Y$. To illustrate just how many comparisons would have to take place, consider the following: each $|X|$-point submatrix of $D_Y$ is obtained by choosing and removing $\left|Y\right| – \left|X\right|$ points from $\left|Y\right|$. This represents $\left|Y\right| \choose \left|Y\right| – \left|X\right|$ matrix comparisons, which is already very big.
To tackle the permutation issue, one would, for each such submatrix, try each permutation of the points, which adds another $\left|X\right|!$ matrices to compare $D_X$ against. At this point we have a number of matrix comparisons proportional to ${\left|Y\right| \choose \left|Y\right| – \left|X\right|}\left|X\right|! = \frac{\left|Y\right|!}{\left(\left|Y\right| – \left|X\right|\right)!\left|X\right|!}\left|X\right|! = \frac{\left|Y\right|!}{\left(\left|Y\right| – \left|X\right|\right)!}$. This has in its worst case a factorial running time which is just awful.
Moreover, on top of being slow, the method is flawed because if one set of points can be entirely contained within another, even if one set has a single point and the other has thousands, the sets will then show up as a 100% match. However, perhaps this is convenient: precisely those situations which yield erroneous results are the most computationally difficult to deal with. Maybe there is some way to "factor them out"?
Best Answer
Triangulate the two point clouds to get two meshes $M_X$ and $M_Y$. Given $x \in X$, let $d(x,M_Y)$ denote it's minimum distance from $M_Y$. One possible measure of distance is then $$ \sum_{x \in X} d(x, M_Y) + \sum_{y \in Y} d(y, M_X) $$ If $X$ and $Y$ come from scanning physical objects, then this is a reasonable distance measurement to use, since it measures the dissimilarity of the two objects.
If $X$ and $Y$ come from scanning the same object in two different positions/orientations, then you may get a large distance result. If this is not desirable, you need to do "registration" first -- in other words, you need to apply a rigid motion to either $X$ or $Y$ to minimise differences that are purely due to differing locations, rather than differing shapes.
It might be useful to read this paper and some of references they cite. And you can search for "point cloud registration" or "ICP" to find out more.
Apparently you can find some registration/alignment functions in Meshlab.