# Why is this equality about the relative translation in the iterative closest point (ICP) algorithm obvious, and how can I derive it?

I'm a computer science bachelor student tasked with understanding On the ICP Algorithm by Esther Ezra, Micha Sharir, and Alon Efrat, and I'm having a lot of difficulty with even supposedly obvious claims. The setup is as follows, wherein we only look at translation, not rotation:

Let $$A = \{a_1, ..., a_m\}$$ and $$B = \{b_1, ..., b_n\}$$ be two point sets in $$d$$-space, for $$d\ge1$$, and suppose that the ICP algorithm aligns $$A$$ to $$B$$; that is, $$B$$ is fixed and $$A$$ is translated to best fit $$B$$.

At every iteration $$i$$ the ICP algorithm tries to find a relative translation vector $$\Delta t_i$$ that minimises its cost function, in this case the root mean square $$\mathrm{RMS}(\Delta t_i) := \frac{1}{m} \sum_{a\in A} || (a + t_{i-1} + \Delta t_i) - N_B(a + t_{i-1}) ||^2,$$ where $$||\cdot||$$ denotes the Euclidean norm, $$N_B(a)$$ denotes the nearest neighbour of $$a$$ in $$B$$, and $$m = |A|$$.

The paper states:

#### Lemma 2.3

At each iteration $$i \ge 2$$ of the algorithm, the relative translation vector $$\Delta t_i$$ satisifies $$\Delta t_i = \frac{1}{m} \sum_{a \in A} \left(N_B(a + t_{i-1}) - N_B(a + t_{i-2})\right),$$ where $$t_j = \sum_{k=1}^j \Delta t_k$$.

#### Proof

Follows using easy algebraic manipulations, based on the obvious equality that follows by construction $$\Delta t_i = \frac{1}{m}\sum_{a \in A} \left(N_B(a+t_{i-1}) - (a + t_{i-1})\right).$$

Unfortunately this obvious equality is not obvious to me, or at least not how I would derive/construct it.

Informally it seems plausible and intuitive to me that $$\Delta t_i$$ is equal to the average difference between the current and previous nearest neighbour of each $$a$$, but I'm not sure how I methodically arrive at this equality.

Indeed, that "obvious equality" is not that "obvious", except for people who have solved one or more similar problems.

Here is a transformation formula, where $$b=(a + t_{i-1}) - N_B(a + t_{i-1})$$ and $$c$$ is some term that does not involve $$\Delta t_i$$.

$$\mathrm{RMS}(\Delta t_i) =\frac{1}{m} \sum_{a\in A} ||\Delta t_i +b||^2 =||\Delta t_i + \frac{1}{m}\sum_{a\in A}b||^2 + c$$

So, $$\mathrm{RMS}(\Delta t_i)$$ achieves its minimum value when $$\Delta t_i = -\frac{1}{m}\sum_{a\in A}b=\frac{1}{m}\sum_{a \in A} \left(N_B(a+t_{i-1}) - (a + t_{i-1})\right).$$

Once that transformation formula is known, that equality should become obvious to you, since it is also your intuition that $$\Delta t_i$$ be "equal to the average difference between the current and previous nearest neighbour of each $$a$$".

Let see how we can prove that transformation formula. Recall that $$m$$ is the cardinality of $$A$$.

\begin{aligned} \frac{1}{m} \sum_{a\in A} ||\Delta t_i +b||^2 &=\frac{1}{m} \sum_{a\in A} (\Delta t_i+b)\cdot(\Delta t_i+b)\\ &=\frac{1}{m} \sum_{a\in A} (\Delta t_i\cdot\Delta t_i + 2b\cdot\Delta t_i + b\cdot b) \\ &=\Delta t_i\cdot\Delta t_i + \frac{2}{m}(\sum_{a\in A}b)\cdot\Delta t_i + \sum_{a\in A} b\cdot b \\ &=(\Delta t_i + (\frac{1}{m}\sum_{a\in A}b))\cdot (\Delta t_i + (\frac{1}{m}\sum_{a\in A}b)) + c \\ &=||\Delta t_i + (\frac{1}{m}\sum_{a\in A}b)||^2 + c, \\ \end{aligned}

where $$c=\sum_{a\in A} b\cdot b - (\frac{1}{m}\sum_{a\in A}b)^2.\quad\quad \checkmark$$