NCH es invariante a la rototraslación

Introducción

Hace poco empecé mi tesis sobre reconstrucción de superficies 3D. Una forma de abordarla es definir una superficie como el conjunto de nivel cero de una función $f : R^{3} \to R$ , y luego encontrar alguna manera de construir esa función a partir de un conjunto de puntos $P \subset R^{3}$ . NCH es un método que permite definir dicha función a partir de una nube de puntos junto con sus normales, que indican cuál es el lado interior de la superficie.

El algoritmo NCH es sorprendentemente simple: me llevó una tarde implementarlo y verlo funcionar sin experiencia previa en 3D (usando PCL , claro). Sin embargo, tiene dos grandes limitaciones: encontrar $f$ es $O (n^{2})$ , y evaluar $f$ en cualquier punto es $O (n)$ ; esto lo convierte en un algoritmo muy costoso, dado que la mayoría de las superficies tienen varios miles de puntos.

Si leés el artículo, quedará claro que es tan simple que no hay una forma obvia de reducir la cantidad de cómputo que requiere sin perder las buenas propiedades teóricas que posee. El objetivo de mi tesis es bastante indefinido por ahora, pero girará en torno a la simplificación: encontrar maneras de reducir la cantidad de puntos que hay que pasarle al algoritmo, para que sea viable ejecutarlo sobre nubes de puntos más grandes.

Sea lo que sea que termine haciendo, sin duda usaré este blog como archivo de demostraciones y de todo lo interesante que vaya aprendiendo en el camino, con la esperanza de que cuando llegue el día de sentarme a escribir la tesis, al menos tenga algo ya redactado, o al menos una imagen más clara del panorama.

Lo que sigue es la primera demostración que hice, y viene a cubrir un vacío que el artículo no aborda: demostrar que el algoritmo es insensible a la rotación y la traslación de los puntos que recibe.

Definiciones

Sea ${p_{1}, ..., p_{N}}$ un conjunto finito de puntos con vectores de orientación unitarios asociados ${n_{1}, ..., n_{N}}$ . Sea

f (x) = 1 \leq i \leq N max f_{i} (x)

la función de distancia con signo de NCH (aquella cuyo conjunto de nivel 0 es la superficie que queremos encontrar), con

f_{i} (x) = n_{i}^{t} (x - p_{i}) - ρ_{i} ∣∣ x - p_{i} ∣ ∣^{2}

las funciones base correspondientes a cada punto, con el parámetro $ρ_{i} \geq 0$ definido como:

ρ_{i} = j \in J_{i} max \frac{n _{i}^{t} ( p _{j} - p _{i} )}{∣∣ p _{j} - p _{i} ∣ ∣ ^{2}}

donde $J_{i} = {j : n_{i}^{t} (p_{j} - p_{i}) > 0}$

Invarianza a la rotación

Sea $p_{i}^{'} = Q p_{i}$ y $n_{i}^{'} = Q n_{i}$ con $Q$ una matriz ortogonal, y $f^{'}, f_{i}^{'}, ρ_{i}^{'}$ definida como antes. Entonces, si observamos la estimación $ρ_{i}^{'}$ :

ρ_{i}^{'} = j \in J_{i}^{'} max \frac{n _{i}^{' t} ( p _{j}^{'} - p _{i}^{'} )}{∣∣ p _{j}^{'} - p _{i}^{'} ∣ ∣ ^{2}} = j \in J_{i}^{'} max \frac{n _{i}^{t} Q ^{t} Q ( p _{j} - p _{i} )}{∣∣ Q ( p _{j} - p _{i} ) ∣ ∣ ^{2}} = j \in J_{i}^{'} max \frac{n _{i}^{t} ( p _{j} - p _{i} )}{∣∣ p _{j} - p _{i} ∣ ∣ ^{2}}

Además, si miramos el conjunto $J_{i}^{'}$ :

J_{i}^{'} = {j : n_{i}^{' t} (p_{j}^{'} - p_{i}^{'}) > 0} = {j : n_{i}^{t} Q^{t} Q (p_{j} - p_{i}) > 0} = {j : n_{i}^{t} (p_{j} - p_{i}) > 0} = J_{i}

Lo que implica que $ρ_{i}^{'} = ρ_{i}$ . Finalmente, $f_{i}^{'} (Q x)$ :

f_{i}^{'} (Q x) = n_{i}^{' t} (Q x - p_{i}^{'}) - ρ_{i}^{'} ∣∣ Q x - p_{i}^{'} ∣ ∣^{2} = n_{i}^{t} Q^{t} Q (x - p_{i}) - ρ_{i} ∣∣ Q (x - p_{i}) ∣ ∣^{2} = n_{i}^{t} (x - p_{i}) - ρ_{i} ∣∣ x - p_{i} ∣ ∣^{2} = f_{i} (x)

Así, cuando evaluamos en un punto rotado $Q x$ , obtenemos la garantía de que:

f^{'} (Q x) = f (x)

Invarianza a la traslación

La estrategia de demostración aquí es muy similar al caso anterior; la diferencia es que ahora los puntos cambian a $p_{i}^{'} = p_{i} + c$ y $n_{i}^{'} = n_{i}$ . En este caso, $p_{j}^{'} - p_{i}^{'} = p_{j} - p_{i}$ porque la constante se cancela; esto implica trivialmente que $J_{i}^{'} = J_{i}$ y $ρ_{i}^{'} = ρ_{i}$ . Finalmente, la nueva garantía que vamos a obtener es que:

f_{i}^{'} (x + c) = f_{i} (x)

Se deriva de que $c$ se cancela en la suma, y por último:

f^{'} (x + c) = f (x)

¿Por qué funciona esto?

Imaginemos $f (x) = 0$ , es decir, que $x$ está en el conjunto de nivel cero de $f$ o, en términos prácticos, que $x$ es un punto que pertenece al borde de la superficie reconstruida. En el caso de la rotación, esto implica que

f^{'} (Q x) = 0

Por lo tanto, el punto rotado $Q x$ formará parte de la superficie. En el caso de una traslación, tenemos que

f^{'} (x + c) = 0

Lo que implica que el punto desplazado $x + c$ pertenece a la superficie. Esto, por supuesto, funciona en ambos sentidos, gracias a las igualdades que establecimos anteriormente.