2
$\begingroup$

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.

$\endgroup$
0

1 Answer 1

1
$\begingroup$

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$$

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.