## Randomized Hough Transform 2: Rototranslations

Here I briefly explained how the RHT works, with reference to a very simple case (finding the directions of rows and columns of a grid). Now I’ll spend some words on a more complex application.

When scanning the surface of an object with an optical scanner, be it based on laser or binocular photogrammetry, some portions of the surface may not be acquired, due to occlusions (they are hidden by other portions of the surface and therefore not reached by the laser ray or not seen by both cameras) or simply because the object is larger than the field of the scanning device.

The solution is to move the object and/or the scanner, so that the hidden parts become visible, and to repeat the acquisition as many times as needed. Then the rototranslations between the different poses must be determined in order to merge the acquisitions in a single point cloud.

To determine the rototranslations, one possibility is to have the scanner carried by something which keeps track of its position and orientation, eg a robotic arm having position encoders at its joints.

Another possibility is to match at least three (the more the better) non-aligned points across each couple of poses. Three couples of non-aligned points determine a rototranslation. The points can be intrinsic features of the object being scanned, or easily recognizable markers purposedly sticked onto the object.

In this second case we have a number of acquisitions, each with a list of 3D reference points. We know that the reference points of, say, acquisition A, as a whole, are in correspondence with those of, say, acquisition B, because they refer to the same 3D entities, but we don’t know in which order the correspondences are. Also, the elements in the A list need not be precisely as many as those in the B list – maybe one or more markers were acquired in A and missed in B, or the reverse. Even worse, maybe some markers were missed both in A and in B, but not the same markers – so that the two lists contain some points which do correspond, even if in unknown order, but also some which do not correspond at all.

Not very simple, isn’t it? Well, RHT can help.

In my previous post, RHT was used to extract shapes (straight lines, circumferences, …) from minimal subsets of samples (couples or triples of points in an image). Here, the concepts of shape and sample must be extended: the shape is the rototranslation, and the minimal subsets are triples of couples of 3D points.

While two non coincident points always define a straight line and three non collinear points always define a circumference, it is not true that any three couples of points always define a rototranslation. The rototranslation is a rigid transformation. Therefore, if the three of couples of points $(A, A'), (B, B'), (C, C')$ are connected by the rototranslation $\begin{bmatrix} R & \mathbf{t} \end{bmatrix}$, so that $A' = R A + \mathbf{t}$, $B' = R B + \mathbf{t}$, $C' = R C + \mathbf{t}$, it must be true that $\left| A-B \right| = \left| A' - B' \right|$, $\left| A - C \right| = \left| A' - C' \right|$, $\left| B - C \right| = \left| B' - C' \right|$.

This fact can be useful to discard a priori minimal subsets not respecting this constraint, avoiding further computation on them. Of course, one must remember that the equality sign is a mathematical abstraction never showing up in the real world. Due to unavoidable acquisition and reconstruction errors, the lengths of corresponding segments will never be precisely equal, so the check must be done with a small tolerance.

As said in my previous post on this subject, the RHT algorithm needs to compare two shapes to determine how much they differ. How can we measure the dissimilarity between two rototranslations?

I found satisfactory to define the dissimilarity as the root mean square difference of the lengths of the edges of a simplex. Let

$P_0 = (0, 0, 0)$

$P_1 = (s, 0, 0)$

$P_2 = (0, s, 0)$

$P_3 = (0, 0, s )$

where $s$ is a characteristic length of the problem, eg the linear size of the field of measure. Then I define the dissimilarity between two rototranslations $\begin{bmatrix} R & \mathbf{t} \end{bmatrix}$ and $\begin{bmatrix} R' & \mathbf{t'} \end{bmatrix}$ as

$d (\begin{bmatrix} R & \mathbf{t} \end{bmatrix}, \begin{bmatrix} R' & \mathbf{t'} \end{bmatrix}) = \sqrt{ \dfrac{\sum_{i=0}^{3} ((R P_i + \mathbf{t}) - (R' P_i + \mathbf{t'}))^2}{4} }$

$d$ is non-negative, it is null for identical rototranslations and, thanks to the characteristic length $s$, it keeps into account both the effects of the translation and of the rotation putting them on a common ground.

That said, the RHT algorithm for rototranslations follows the same steps as described in my previous post. Here is the pseudocode:

1. Initialize an empty list of rototranslations.
2. Repeat 3..10 for a maximum number of times:
3. Randomly choose three distinct points from the first acquisition.
4. Randomly choose three distinct points from the second acquisition.
5. If the rigidity constraint is violated, restart from 3.
6. Compute the rototranslation defined by the three couples of points.
7. If the list of rototranslations is empty, add the new rototranslation to the list, keeping track of the three couples of points used to compute it.
8. Otherwise if the list of rototranslations is not empty, compute the dissimilarity of the new rototranslation with respect to all those in the list.
9. If the lowest dissimilarity found is under a specified threshold, merge the two rototranslations by merging their associated samples (couples of points) and recomputing the rototranslation. If the merged rototranslation has enough samples, exit the iterations.
10. Otherwise if the lowest dissimilarity found is over a specified threshold, add the new rototranslation to the list.

Several algorithms are available to compute the rototranslation given three or more couples of points; see eg Lorusso, Eggert and Fisher, A Comparison of Four Algorithms for Estimating 3-D Rigid Transformations.

The choice of the random number generator used to extract the minimal subsets is critical. It must be a good one, with an as long as possible cycle. I used the Mersenne generator by Agner Fog. Also, be aware that two independent generators (with different seeds) must be used to extract the samples from the first and from the second acquisition.

The algorithm, as described, needs three parameters:

• maximum number of iterations;
• dissimilarity threshold to decide if the new rototranslation has to be merged with an existing one or must be added to the list;
• minimum number of samples to accept a rototranslation as a valid result and exit the algorithm.

It could also be a good idea to give up the search after a certain number of iteration without finding a new minimal subset different from those already seen.

I haven’t made thorough testing, but I dare say that RHT is competitive with RANSAC for finding rototranslations.

Here you find a short movie (5 min) showing the acquisition and registration of point clouds based on marker matching with the RHT for rototranslations algorithm.