Der iterative Algorithmus der nächsten Punkte

Gegeben sei eine Menge von 3D-Punkten $M = \{\mathbf{m}_i \ \lvert \ \mathbf{m}_i \in \mathbbm{R}^3, \ i=1,\ldots,N_m \}$. Für einen 3D-Scan mit der Datenmenge $D = \{\mathbf{d}_i \ \lvert \ \mathbf{d}_i \in \mathbbm{R}^3, \ i=1,\ldots,N_d \}$ sind eine Rotation $\MR$ sowie eine Translation $\mathbf{t}$ gesucht, die beide Mengen korrekt ineinander abbilden. Dabei muss die Fehlerfunktion

$$E(\MR, \mathbf{t}) = \sum_{i=1}^{N_m}\sum_{j=1}^{N_d}w_{i,j}\left... ...\lvert \mathbf{m}_{i}-(\MR \mathbf{d}_j+\mathbf{t}) \right\rvert\right\rvert ^2$$ (3.7)

minimiert werden. $w_{i,j}$ nimmt hierbei den Wert 1 an, falls die Messpunkte $\mathbf{m}_{i} \in M, \, \mathbf{d}_{j} \in D$ den gleichen Punkt darstellen. Die Minimierung von (3.7) muss mit der Maximierung von

$$\sum_{i=1}^{N_m}\sum_{j=1}^{N_d}w_{i,j}$$ (3.8)

einhergehen. Trifft dies nicht zu, ist die triviale Lösung $w_{i,j} = 0 \quad \forall i,j$ zulässig, was der Idee des Scanmatchings widerspricht.

Der iterative Algorithmus der nächsten Punkte (engl.: iterative closest points (ICP)) wurde etwa zeitgleich von Besl/McKay [10], Zhang [85] und Cheng/Medioni [13] 1991 entwickelt. Der Algorithmus - im Folgenden mit ICP bezeichnet - stellt einen allgemeinen Rahmen für die Registrierung von 3D-Tiefenbildern dar. Die fundamentalen Schritte des Algorithmus sind:

Es kann nachgewiesen werden, dass der obige Algorithmus konvergiert und ein lokales Minimum findet [10].

Satz 1 (Konvergenz-Theorem)   Der iterative Algorithmus der nächsten Punkte konvergiert monoton zu einem lokalen Minimum, wenn die Fehlerfunktion $E(\MR,\mathbf{t})$ (3.7) gegeben ist [10].

Beweis:Der Beweis wird mit vollständiger Induktion geführt. Für alle Iterationen $k$ des Algorithmus, insbesondere für den Induktionsanfang $k=1$, gelten folgende Aussagen: Gegeben seien zwei Mengen $M$ und $D_k$. Der erste Schritt des obigen Algorithmus liefert die Paare $w_{k,i,j}$, die den Fehler $F_k$ aufweisen:

$$F_k = \sum_{i=1}^{N_m}\sum_{j=1}^{N_d}w_{k,i,j}\left\lvert\left\lvert \mathbf{m}_{i}-\mathbf{d}_{k,j} \right\rvert\right\rvert ^2.$$ (3.9)

Schritt 2 des Algorithmus sucht die Transformation ( $\MR_k, \mathbf{t}_k$), die, angewendet auf die Datenpunkte $\mathbf{d}_{k,j}$, $F_k$ minimiert. Dadurch wird (3.9) zu

$$E_k = \sum_{i=1}^{N_m}\sum_{j=1}^{N_d}w_{k,i,j}\left\lvert\left\l... ...mathbf{m}_{i}-\MR_k\mathbf{d}_{k,j} + \mathbf{t}_k \right\rvert\right\rvert ^2.$$

Offensichtlich gilt immer $F_k \geq E_k$. Angenommen dies wäre nicht der Fall und es gälte $F_k < E_k$, dann würde die Identitätstransformation ( $\MR= \mathbbm{1}$ und $\mathbf{t}= \mathbf{0}$) in einem kleineren Fehler $E_k$ resultieren. Als nächstes wendet man die gefundene Transformation auf $D_k$ an, wodurch die Menge $D_{k+1}$ entsteht. Nun werden die Paare $w_{{k+1},i,j}$ berechnet und es ergibt sich folgender neuer Fehler:

$$F_{k+1} = \sum_{i=1}^{N_m}\sum_{j=1}^{N_d}w_{{k+1},i,j}\left\lvert\left\lvert \mathbf{m}_{i}-\mathbf{d}_{{k+1},j} \right\rvert\right\rvert ^2.$$

Es gilt $E_k \geq F_{k+1}$, weil entweder neue Paare mit kleineren Abständen $\left\lvert\left\lvert \mathbf{m}_{i}-\mathbf{d}_{{k+1},j} \right\rvert\right\rvert ^2$ entstehen oder die vorige Paarung wiederholt wird.

Also ist:

$$F_k \geq E_k \geq F_{k+1} \geq 0 \quad \forall k \geq 1.$$ (3.10)

Aus dem Satz der Konvergenz einer beschränkten monotonen Folge ergibt sich die Konvergenz zu einem Minimum [23].$\Box$