Register

Registration involves the alignment of one object (the “moving” object) to a reference (or “fixed”) object.

Common instances of registration include point cloud registration and image registration. Registration can be used to align different scans/images of an object (e.g. a CT scan and an MRI scan), images of the same object taken at different times, different variations of the same kind of object (e.g. CT scans of bones belonging different individuals), or any other situation where you have two or more objects that can be aligned. Registration can be useful for detecting and measuring differences between objects, stitching together overlapping parts of a larger object, and more.

Registration is an optimization process, by which some measure of similarity is maximized (or some measure of distance is minimized). As such, it requires an objective function (a way to score the similarity/distance), a parameter space (a set of parameters that can be used to move the object), and an algorithm by which the parameter space can be explored in order to find the optimal set of parameters for the chosen objective function.

Registration strategies will often consider one “fixed” object which is held in place while the other “moving” object is transformed to line up with the fixed object.

Types of registration

There are a few ways to classify different approaches to registration.

Classification by modality

Registration strategies can be classified by what types of data are being aligned.

• Image registration: The alignment of two or more images (see also: Image2Image())

• Point cloud registration: The alignment of two or more sets of points (see also: Point2Point())

Classification by transformation

Registration strategies can also be classified by what type of transformation (i.e. parameter space) is used to align the objects.

• Rigid registration: The object is moved by translations and rotations, but not deformed.

• Similarity registration: The object is moved by translations and rotations, and can be uniformly scaled.

• Affine registration: The object is moved by translations and rotations, can be scaled in each direction, and can undergo shearing deformations.

• Elastic registration: The object can be deformed during the alignment process (note: currently not available in mymesh).

Iterative Closest Point (ICP)

Reference: Besl and McKay [BM92]

The iterative closest point algorithm is a classic and popular method for rigid registration of point sets.

The ICP algorithm involves the repetition of two key steps: 1. Identifying the “closest point” correspondences; and 2. Minimizing the distance between corresponding points.

Minimizing the distance between corresponding points

Reference: Arun et al. [AHB87]

Once pairs of corresponding points have been identified, the squared error between a set of \(N\) fixed points (\(p^f = \{p_i^f\}\)) and a corresponding set of \(N\) moving points (\(p^m = \{p_i^m\}\)) is written:

\[\Sigma^2 = \sum_{i=1}^{N} ||p_i^f - (\mathbf{R} p_i^m + \mathbf{T})||^2\]

where \(\mathbf{R}\) and \(\mathbf{T}\) are rotation and translation matrices, respectively. The objective is to find \(\mathbf{R}, \ \mathbf{T}\) that minimize the squared error: \(\underset{\mathbf{R}, \ \mathbf{T}}{\min}\Sigma^2\). Before attempting to minimize this squared error, we can simplify the problem by separating translation and rotation. At the least squares minimum of \(\Sigma^2\), the centroid of the moving points (\(c(p^m) = \frac{1}{N}\sum_{i=1}^{N}p_i^m\)) will be equal to that of the fixed points (\(c(p^f) = \frac{1}{N}\sum_{i=1}^{N}p_i^f\)) [AHB87], meaning the rotation can first be solved by centering both sets of points at the origin by subtracting the centroids from the points:

\[\begin{split}q_i^f = p_i^f - c(p^f), \\ q_i^m = p_i^m - c(p^m),\end{split}\]

simplifying the squared error to

\[\Sigma^2 = \sum_{i=1}^{N} ||q_i^f - (\mathbf{R} q_i^m)||^2.\]

The translation can subsequently be determined as

\[\mathbf{T} = c(p^f) - \mathbf{R}c(p^m).\]

The rotation can be found by performing singular value decomposition of the cross covariance matrix (see Arun et al. [AHB87] for derivation)

\[H = \sum_{i=1}^{N} q_i^m (q_i^f)^t = \mathbf{U \Sigma V}^t.\]

The rotation \(\mathbf{R}\) is then

\[\mathbf{R} = \mathbf{V} \mathbf{U}^t.\]