Punto establece registro

Punto de registro establecido es el proceso de alineación de dos conjuntos de punto. Aquí, el pescado azul se está registrando para el pez rojo.

En visión por computador y reconocimiento de patrones, punto de registro establecido, también conocido como punto de coincidencia, es el proceso de encontrar un espacial transformación alinea dos conjuntos de punto. El propósito de encontrar una transformación incluye combinar múltiples conjuntos de datos en un modelo consistente en todo el mundo y asignar una nueva medición a un conjunto de datos conocido para identificar las características o estimar su pose. Un sistema del punto puede ser datos crudos de Digitalización 3D o una matriz de Telémetros. Para su uso en procesamiento y basado en funciones de la imagen registro de la imagen, un sistema del punto puede ser un conjunto de características obtenidas por extracción de la característica de una imagen, por ejemplo detección de esquina. Registro conjunto de punto se utiliza en reconocimiento óptico de caracteres y la alineación de los datos de imágenes por resonancia magnética con tomografía asistida por computadora exploraciones.

Descripción del problema

Datos de dos escáneres 3D del mismo entorno necesitan ser alineados usando el punto de registro establecido.

Desde allí, colocó con éxito usando una variante del punto más cercano iterativo.

El problema puede ser resumido como sigue: Dejar $\lbrace\mathcal{M},\mathcal{S}\rbrace$ ser dos sistemas del punto tamaño finito in un verdadero espacio finito-dimensional del vector $\mathbb{R}^d$, que contienen $M$ y $N$ puntos respectivamente. El problema es encontrar una transformación que se aplicará a la configuración de puntos móviles de "modelo" $\mathcal{M}$ tal que la diferencia entre $\mathcal{M}$ y la estática "escena" $\mathcal{S}$ se minimiza. En otras palabras, una asignación de $\mathbb{R}^d$ Para $\mathbb{R}^d$ es deseado que rinde la mejor alineación entre la transformada "modelo" y la "escena". La asignación puede consistir en una transformación rígida o deformable. El modelo de transformación puede ser escrito como $T$ registrado el transformado, modelo punto conjunto es:

$T(\mathcal{M})$

   

(1)

Es útil definir un parámetro de la optimización $\theta$:

$T(\mathcal{M}, \theta)$

   

(2)

Así está claro que el algoritmo de optimización ajusta $\theta$. Dependiendo del problema y el número de dimensiones, puede haber más dichos parámetros. La salida de un algoritmo de registro conjunto punto por lo tanto es el parámetro de transformación $\theta$ del modelo $T$ Para $\mathcal{M}$ está perfectamente alineado con $\mathcal{S}$.

En la convergencia, que es deseable para la distancia entre los dos conjuntos de punto para llegar a un mínimo global. Es difícil sin agotar todas las transformaciones posibles, así que basta un mínimo local. Establece la función de la distancia entre un punto modelo transformado $T(\mathcal{M})$ y el sistema de punto de la escena $\mathcal{S}$ se da por cierta función $\operatorname{dist}$. Es un enfoque sencillo para tomar la Plaza de la Distancia euclidiana para cada par de puntos:

$\operatorname{dist}(T(\mathcal{M}), \mathcal{S}) = \sum_{m \in T(\mathcal{M})} \sum_{s \in \mathcal{S}} (m - s)^2$

   

(3)

Minimizar tal función en registro rígido es equivalente a resolver una mínimos cuadrados problema. Sin embargo, esta función es sensible a los datos aislados y en consecuencia algoritmos basados en esta función tienden a ser menos robusto contra datos ruidosos. Una formulación más robusta de la función de costo utiliza algunos función robusta $g$:

$\operatorname{dist}_{\operatorname{robust}}(T(\mathcal{M}), \mathcal{S}) = \sum_{m \in T(\mathcal{M})} \sum_{s \in \mathcal{S}} g((m - s)^2)$

   

(4)

Una formulación tan es conocida como un M-estimador. La función robusta $g$ se elige tal que la configuración local de la configuración de puntos es insensible a puntos distantes, por lo tanto, por lo que es robusto contra ruido y afloramientos.

Registro rígido

Dados dos conjuntos de punto, registro rígido produce un transformación rígida que asigna un punto a otro. Una transformación rígida se define como una transformación que no cambia la distancia entre dos puntos cualesquiera. Típicamente consiste en una transformación traducción y rotación. En casos raros, también puede reflejarse la configuración de puntos.

Registro no rígidos

Dados dos conjuntos de punto, registro deformable produce una transformación no rígidos que se asigna un sistema del punto a la otra. Incluyen transformaciones non-rígido transformaciones afines tales como escalamiento y cizalla mapeo. Sin embargo, en el contexto del punto determinado registro, registro deformable implica típicamente transformación no lineal. Si el eigenmodes de variación del punto de juego son conocidas, la transformación no lineal puede ser parametrizados por los valores propios. Una transformación no lineal también puede ser parametrizados como un tira fina de la placa.

Punto establece algoritmos de registro

Algunos enfoques al punto de registro conjunto utilizan algoritmos que resuelven la más general gráfico que empareja problema. Sin embargo, la complejidad computacional de tales métodos tienden a ser altos y están limitados a los registros rígidos. En las siguientes secciones se describen algoritmos específicos para el problema de registro conjunto de punto.

Punto más cercano iterativo

Artículo principal: Punto más cercano iterativo

El punto más cercano iterativo Algoritmo (ICP) fue introducida por Besl y McKay. El algoritmo realiza registro rígido en forma iterativa por suponiendo que cada punto en $\mathcal{M}$ se corresponde con el punto más cercano a él en $\mathcal{S}$y luego encontrar el mínimos cuadrados transformación rígida. Como tal, funciona mejor si plantean la inicial de $\mathcal{M}$ está lo suficientemente cerca $\mathcal{S}$. En pseudocódigo, se implementa el algoritmo básico como sigue:

   Algoritmo de ICP$(\mathcal{M}, \mathcal{S})$
       $\theta$ := $\theta_0$
mientras que no está registrado: $X$ := $\emptyset$
para $m_i \in T(\mathcal{M}, \theta)$:: $\hat{s}_j$ : = punto más cercano en $\mathcal{S}$ Para $m_i$
               $X$ := $X$ + $\langle m_i, \hat{s}_j \rangle$
           $\theta$ := mínimos cuadrados$(X)$
retorno $\theta$

Aquí, la función least_squares realiza mínimos cuadrados regresión para reducir al mínimo la distancia en cada uno de los $\langle m_i, \hat{s}_j \rangle$ pares, es decir, minimizando la función distancia en la ecuación ()3).

Porque el función de coste del registro depende de encontrar el punto más cercano en $\mathcal{S}$ a cada punto de $\mathcal{M}$, puede cambiar mientras se ejecuta el algoritmo. Por lo tanto, es difícil de probar que el ICP se reunirán en realidad exactamente a los óptimos locales. De hecho, empíricamente, ICP y EM-ICP no convergen al mínimo local de la función de costo. Sin embargo, porque el ICP es intuitivo de entender y fácil de implementar, sigue siendo el algoritmo de registro conjunto punto más comúnmente utilizado. Se han propuesto muchas variantes del ICP, que afecta a todas las fases del algoritmo de la selección y coincidencia de puntos de la estrategia de minimización. Por ejemplo, la maximización de la expectativa algoritmo se aplica el algoritmo ICP para formar el método EM-ICP y la Algoritmo de Levenberg-Marquardt se aplica el algoritmo ICP para formar el método de la LM-ICP.

Punto robusto que empareja

Sólido punto de coincidencia (RPM) fue introducido por oro et al. El método realiza registro usando recocido determinista y suave permite la asignación de las correspondencias entre conjuntos de punto. Mientras que en el ICP la correspondencia generada por la heurística más cercano vecino binaria, RPM utiliza un suave correspondencia donde la correspondencia entre dos puntos cualquiera puede ser en cualquier lugar de 0 a 1, aunque en última instancia, converge a 0 o 1. Las correspondencias encontramos RPM es siempre uno a uno, que no siempre es el caso de ICP. Dejar $m_i$ ser el $i$punto de TH en $\mathcal{M}$ y $s_j$ ser el $j$punto de TH en $\mathcal{S}$. El coincidir con matriz $\mathbf{\mu}$ se define como tal:

$\mu_{ij} = \left\lbrace\begin{matrix} 1 & \text{if point }m_i\text{ corresponds to point }s_j\\ 0 & \text{otherwise} \end{matrix}\right.$

   

(rpm.1)

El problema entonces se define como: dados dos conjuntos de punto $\mathcal{M}$ y $\mathcal{S}$ encontrar el Transformación afín $T$ y la matriz de fósforo $\mathbf{\mu}$ que mejor se les relaciona. Conociendo la transformación óptima hace que sea fácil determinar la matriz de fósforo y viceversa. Sin embargo, el algoritmo RPM determina ambos simultáneamente. La transformación se puede descomponer en un vector de traslación y una matriz de transformación:

$T(m) = \mathbf{A}m + \mathbf{t}$

La matriz $\mathbf{A}$ en 2D se compone de cuatro parámetros separados $\lbrace a, \theta, b, c\rbrace$, que son de escala, rotación y la vertical y horizontal del esquileo componentes respectivamente. La función de costo es entonces:

$\operatorname{cost} = \sum_{j=1}^N \sum_{i=1}^M \mu_{ij} \lVert s_j - \mathbf{t} - \mathbf{A} m_i \rVert^2 + g(\mathbf{A}) - \alpha \sum_{j=1}^N \sum_{i=1}^M \mu_{ij}$

   

(rpm.2)

sujeto a $\forall j~\sum_{i=1}^M \mu_{ij} \leq 1$, $\forall i~\sum_{j=1}^N \mu_{ij} \leq 1$, $\forall ij~\mu_{ij} \in \lbrace0, 1\rbrace$. El $\alpha$ término predispone el objetivo hacia más fuerte correlación disminuyendo el costo si la matriz partido tiene más en él. La función $g(\mathbf{A})$ sirve para regularizar la transformación afín penalizar el valuse grande de la escala y distorsionar los componentes:

$g(\mathbf{A}(a,\theta, b, c)) = \gamma(a^2 + b^2 + c^2)$

para un parámetro de regularización $\gamma$.

El método RPM optimiza la función de costo utilizando la Softassign algoritmo. Aquí se derivará el caso 1D. Dado un conjunto de variables $\lbrace Q_j\rbrace$ donde $Q_j\in \mathbb{R}^1$. Una variable $\mu_j$ se asocia a cada uno $Q_j$ tal que $\sum_{j=1}^J \mu_j = 1$. El objetivo es encontrar $\mathbf{\mu}$ maximiza $\sum_{j=1}^J \mu_j Q_j$. Esto puede ser formulado como un problema continuo mediante la introducción de un parámetro de control $\beta>0$. En recocido determinista método, el parámetro de control $\beta$ se incrementa lentamente mientras el algoritmo corre. Dejar $\mathbf{\mu}$ ser:

$\mu_{\hat{j}} = \frac{\exp{(\beta Q_{\hat{j}})}}{\sum_{j=1}^J \exp{(\beta Q_j)}}$

   

(rpm.3)

Esto se conoce como el función softmax. Como $\beta$ aumenta, se aproxima a un valor binario según lo deseado en la ecuación)rpm.1). El problema puede ser generalizado al caso 2D, donde en lugar de maximizar $\sum_{j=1}^J \mu_j Q_j$, se maximiza la siguiente:

$E(\mu) = \sum_{j=1}^N \sum_{i=0}^M \mu_{ij} Q_{ij}$

   

(rpm.4)

donde

$Q_{ij} = -(\lVert s_j - \mathbf{t} - \mathbf{A} m_i \rVert^2 - \alpha) = -\frac{\partial \operatorname{cost}}{\partial \mu_{ij}}$

Esto es sencillo, excepto que ahora las restricciones en $\mu$ son matriz doblemente estocástica restricciones: $\forall j~\sum_{i=1}^M \mu_{ij} = 1$ y $\forall i~\sum_{j=1}^N \mu_{ij} = 1$. Como tal el denominador de la ecuación)rpm.3) no puede ser expresado para el caso 2D simplemente. Para satisfacer las restricciones, es posible usar un resultado debido a Sinkhorn, lo que significa que una matriz doblemente estocástica es obtenida de cualquier matriz cuadrada con todas las entradas positivas por el proceso iterativo de alternancia normalizar de fila y columna. Así está escrito como tal el algoritmo:

   Algoritmo RPM2D$(\mathcal{M}, \mathcal{S})$
       $\mathbf{t}$ : = 0 $a, \theta, b, c$ : = 0 $\beta$ := $\beta_0$
       $\hat{\mu}_{ij}$ := $1 + \epsilon$
al mismo tiempo $\beta < \beta_f$:: mientras que $\mu$ No ha convergido: actualización de parámetros de correspondencia por softassign
               $Q_{ij}$ := $-\frac{\partial \operatorname{cost}}{\partial \mu_{ij}}$
               $\mu^0_{ij}$ := $\exp(\beta Q_{ij})$
               aplicar el método de Sinkhorn
al mismo tiempo $\hat{\mu}$ No ha convergido: actualización $\hat{\mu}$ por la normalización a través de todas las filas:
                   $\hat{\mu}^1_{ij}$ := $\frac{\hat{\mu}^0_{ij}}{\sum_{i=1}^{M+1} \hat{\mu}^0_{ij}}$
                   actualización $\hat{\mu}$ por la normalización a través de todas las columnas:
                   $\hat{\mu}^0_{ij}$ := $\frac{\hat{\mu}^1_{ij}}{\sum_{j=1}^{N+1} \hat{\mu}^1_{ij}}$
               actualización plantean parámetros por coordenadas pendiente
actualización $\theta$ usando solución analítica update $\mathbf{t}$ usando solución analítica update $a, b, c$ usando Método de Newton
           $\beta$ := $\beta_r \beta$
           $\gamma$ := $\frac{\gamma}{\beta_r}$
retorno $a, b, c, \theta$ y $\mathbf{t}$

donde el recocido determinista control de parámetro $\beta$ se establece inicialmente en $\beta_0$ y los aumentos por factor $\beta_r$ hasta que alcanza el valor máximo $\beta_f$. Las adiciones en la suma de medidas de normalización de $M+1$ y $N+1$ en lugar de sólo $M$ y $N$ porque las restricciones $\mu$ son las desigualdades. Como tal el $M+1$TH y $N+1$son elementos de TH variables de holgura.

El algoritmo también puede ampliarse para conjuntos de punto en 3D o mayores dimensiones. Las restricciones sobre la matriz de correspondencia $\mathbf{\mu}$ son las mismas en el caso como en el caso 2D 3D. Por lo tanto, la estructura del algoritmo permanece sin cambios, con la diferencia principal es cómo se resuelven las matrices de rotación y traslación.

Placa delgada tira punto robusto que empareja

Sistema de animación 2D registro deformable del punto verde $\mathcal{M}$ el magenta punto conjunto $\mathcal{S}$ corrompidas con afloramientos ruidosos. El tamaño de los círculos azules está inversamente relacionado con el parámetro de control $\beta$. Las líneas amarillas indican correspondencia.

El algoritmo que empareja (TPS-RPM) de placa delgada spline robusto punto por Chui y Rangarajan aumenta el método RPM para realizar registro deformable por oponeros la transformación como un tira fina de la placa. Sin embargo, porque la placa delgada tira parametrización sólo existe en tres dimensiones, el método no puede ampliarse a los problemas que implica cuatro o más dimensiones.

Correlación del núcleo

El enfoque de correlación (KC) del núcleo del punto de registro conjunto fue introducido por Tsin y Kanade. Comparado con el ICP, el algoritmo KC es más robusto contra datos ruidosos. A diferencia de ICP, donde, para cada punto de modelo, se considera solamente el punto más cercano de la escena, aquí cada escena punto afecta a todos los puntos del modelo. Como tal es un multiplicar-ligado algoritmo de registro. Para algunos función del núcleo $K$, la correlación del núcleo $KC$ de dos puntos $x_i, x_j$ se define así:

$KC(x_i, x_j) = \int K(x, x_i) \cdot K(x, x_j) dx$

   

(KC.1)

El función del núcleo $K$ elegido para punto de registro del sistema es típicamente simétrica y no negativo kernel, similar a las utilizadas en la Ventana de Parzen estimación de densidad. El Núcleo gaussiano típicamente utilizado por su sencillez, aunque otros como el Núcleo Epanechnikov y el núcleo tricube puede ser substituido. Establece la correlación del núcleo de un punto entero $\mathcal{\chi}$ se define como la suma de las correlaciones del núcleo de cada punto en el conjunto de todos los otros puntos en el conjunto:

$KC(\mathcal{X}) = \sum_{i\neq j}KC(x_i, x_j) = 2\sum_{i<j}KC(x_i, x_j)$

   

(KC.2)

El KC de un sistema del punto es proporcional, dentro de un factor constante, el logaritmo de entropía (teoría de la información). Observar que el KC es una medida de un "compactación" de la configuración de puntos — trivial, si todos los puntos en la configuración de puntos estaban en el mismo lugar, el KC evaluaría a cero. El función de coste del punto de establece registro algoritmo para algunos parámetros de transformación $\theta$ se define así:

$\operatorname{cost}(\mathcal{S}, \mathcal{M}, \theta) = -\sum_{m \in \mathcal{M}} \sum_{s \in \mathcal{S}} KC(s, T(m, \theta))$

   

(KC.3)

Algunas producciones de manipulación algebraica:

$KC(\mathcal{S} \cup T(\mathcal{M}, \theta)) = KC(\mathcal{S}) + KC(T(\mathcal{M}, \theta)) - 2 \operatorname{cost}(\mathcal{S}, \mathcal{M}, \theta)$

   

(KC.4)

La expresión se simplifica mediante la observación de $KC(\mathcal{S})$ es independiente de $\theta$. Además, suponiendo que registro rígido, KC (T (\mathcal {M}, \theta)) es invariante cuando $\theta$ ha cambiado porque la distancia euclidiana entre cada par de puntos sigue siendo el mismo bajo transformación rígida. Así que la ecuación anterior puede ser reescrita como:

$KC(\mathcal{S} \cup T(\mathcal{M}, \theta)) = C - 2 \operatorname{cost}(\mathcal{S}, \mathcal{M}, \theta)$

   

(KC.5)

El estimaciones de la densidad del núcleo se definen como:

$P_{\mathcal{M}}(x, \theta) = \frac{1}{N} \sum_{m \in \mathcal{M}} K(x, T(m, \theta))$

$P_{\mathcal{S}}(x) = \frac{1}{N} \sum_{s \in \mathcal{S}} K(x, s)$

La función de costo entonces puede ser demostrada que la correlación de las estimaciones de la densidad del dos núcleo:

$\operatorname{cost}(\mathcal{S}, \mathcal{M}, \theta) = -N^2 \int_x P_{\mathcal{M}}\cdot P_{\mathcal{S}} ~ dx$

   

(KC.6)

Habiendo establecido la función de coste, simplemente utiliza el algoritmo descenso de gradiente para encontrar la transformación óptima. Es computacionalmente caro calcular la función de costo desde cero en cada iteración, para una versión discreta del coste la función (ecuaciónKC.6) se utiliza. Las estimaciones de la densidad del núcleo $P_{\mathcal{M}}, P_{\mathcal{S}}$ puede ser evaluado en puntos de la cuadrícula y almacenados en un tabla de consulta. A diferencia de la ICP y métodos relacionados, no es necesario financiar al vecino más cercano, que permite que el algoritmo de KC para ser comparativamente simple en ejecución.

Comparado con ICP y EM-ICP para sistemas del ruidoso punto 2D y 3D, el algoritmo KC es menos sensible al ruido y resultados en la correcta inscripción más a menudo.

Modelo gaussiano mezcla

Las estimaciones de la densidad del núcleo son sumas de Gaussianas y por lo tanto pueden ser representadas como Modelos de mezcla gaussiano (GMM). Jian y Vemuri utilizan la versión GMM del algoritmo de registro KC realizar registro deformable parametrizadas por ranuras de la placa delgada.

Punto coherente deriva

Rígido (con la adición de escalamiento) registro de un conjunto de punto azul $\mathcal{M}$ punto rojo conjunto $\mathcal{S}$ usando el algoritmo deriva punto coherente. Ambos conjuntos de punto han sido corrompidas con puntos quitados y aislados espurio al azar.

Registro afín de un conjunto de punto azul $\mathcal{M}$ punto rojo conjunto $\mathcal{S}$ usando el algoritmo deriva punto coherente.

Registro no rígida de un conjunto de punto azul $\mathcal{M}$ punto rojo conjunto $\mathcal{S}$ usando el algoritmo deriva punto coherente. Ambos conjuntos de punto han sido corrompidas con puntos quitados y aislados espurio al azar.

Punto coherente deriva (CPD) fue introducida por Myronenko y la canción. El algoritmo toma un enfoque probabilístico a alinear sistemas del punto, similar al método GMM KC. A diferencia de enfoques anteriores al registro deformable que asumen un tira fina de la placa modelo de transformación, CPD es agnóstica en relación con el modelo de transformación utilizado. El sistema del punto $\mathcal{M}$ representa el Modelo gaussiano mezcla Centroides (GMM). Cuando los dos conjuntos de punto óptimo estén alineados, la correspondencia es el máximo del MGM probabilidad posterior para un punto de datos determinado. Para preservar la estructura topológica de los conjuntos de punto, los centroides GMM son forzados a moverse coherente como grupo. El maximización de la expectativa algoritmo se utiliza para optimizar la función de costo.

Hágase $M$ puntos en $\mathcal{M}$ y $N$ puntos en $\mathcal{S}$. El GMM función de densidad de probabilidad para un punto $s$ es:

$p(s) = \sum_{i=1}^{M+1} P(i) p(s|i)$

   

(CPD.1)

donde, en $D$ dimensiones, $p(s|i)$ es el Distribución Gausiana centrado en el punto $m_i \in \mathcal{M}$.

$p(s|i) = \frac{1}{(2\pi \sigma^2)^{D/2)}} \exp{\left(-\frac{\lVert s - m_i \rVert^2}{2\sigma^2}\right)}$

Las probabilidades de pertenencia $P(i)=\frac{1}{M}$ es igual para todos los componentes GMM. El peso de la distribución uniforme se denota como $w\in[0,1]$. El modelo de mezcla es entonces:

$p(s) = w \frac{1}{N} + (1-w) \sum_{i=1}^M \frac{1}{M} p(s|i)$

   

(CPD.2)

Los centroides GMM son re-parametrizadas por un conjunto de parámetros $\theta$ Estimado maximizando la probabilidad. Esto es equivalente a minimizar el negativo función log-verosimilitud:

$E(\theta, \sigma^2) = -\sum_{j=1}^N \log \sum_{i=1}^{M+1} P(i)p(s|i)$

   

(CPD.3)

donde se supone que los datos sean independientes e idénticamente distribuidas. La probabilidad de correspondencia entre dos puntos $m_i$ y $s_j$ se define como el probabilidad posterior del MGM centroide dado el punto de datos:

$P(i|s_j) = \frac{P(i)p(s_j|i)}{p(s_j)}$

El maximización de la expectativa Algoritmo (EM) se usa para encontrar $\theta$ y $\sigma^2$. El algoritmo EM consta de dos pasos. Primero, en el paso E o estimación paso, adivina los valores de los parámetros (valores de parámetro "viejo") y luego usa Teorema de Bayes para calcular las distribuciones de probabilidad posteriores $P^{\text{old}}(i,s_j)$ de los componentes de la mezcla. Segundo, en el paso M o maximización paso, luego se encuentran los valores del parámetro "nuevo" reduciendo la expectativa de la función log-verosimilitud negativa completa, es decir, la función de coste:

$\operatorname{cost}=-\sum_{j=1}^N \sum_{i=1}^{M+1} P^{\text{old}}(i|s_j) \log(P^{\text{new}}(i) p^{\text{new}}(s_j|i))$

   

(CPD.4)

Ignorando las constantes independientes de $\theta$ y $\sigma$() EcuaciónCPD.4) puede ser expresado así:

$\operatorname{cost}(\theta, \sigma^2)=\frac{1}{2\sigma^2} \sum_{j=1}^N \sum_{i=1}^{M+1} P^{\text{old}}(i|s_j) \lVert s_j - T(m_i,\theta) \rVert^2 + \frac{N_\mathbf{P}D}{2}\log{\sigma^2}$

   

(CPD.5)

donde

$N_\mathbf{P} = \sum_{j=0}^N \sum_{i=0}^M P^{\text{old}}(i|s_j) \leq N$

con $N=N_\mathbf{P}$ Sólo si $w=0$. Las probabilidades de GMM componentes calculados utilizando los valores de parámetro anterior posteriores $P^{\text{old}}$ es:

$P^{\text{old}}(i|s_j) = \frac {\exp \left( -\frac{1}{2\sigma^{\text{old}2}} \lVert s_j - T(m_i, \theta^{\text{old}})\rVert^2 \right) } {\sum_{k=1}^{M} \exp \left( -\frac{1}{2\sigma^{\text{old}2}} \lVert s_j - T(m_k, \theta^{\text{old}})\rVert^2 \right) + (2\pi \sigma^2)^\frac{D}{2} \frac{w}{1-w} \frac{M}{N}}$

   

(CPD.6)

Minimizando la función de costo en la ecuación)CPD.5) necesariamente disminuye la función log-verosimilitud negativa $E$ en la ecuación)CPD.3) a menos que ya está en un mínimo local. Por lo tanto, el algoritmo puede ser expresado mediante la siguiente pseudocódigo, donde se pone el punto $\mathcal{M}$ y $\mathcal{S}$ se representan como $M\times D$ y $N\times D$ matrices $\mathbf{M}$ y $\mathbf{S}$ respectivamente:

   Algoritmo de CPD$(\mathcal{M}, \mathcal{S})$
       $\theta$ := $\theta_0$
inicializar $0\leq w \leq 1$
       $\sigma^2$ := $\frac{1}{DNM}\sum_{j=1}^N \sum_{i=1}^M \lVert s_j - m_i \rVert^2$
mientras que no está registrado: E-paso, cálculo $\mathbf{P}$
para $i\in [1,M]$ y $j\in [1,N]$:: $p_{ij}$ := $\frac
                {\exp
                    \left(
                        -\frac{1}{2\sigma^2} \lVert s_j - T(m_i, \theta)\rVert^2
                    \right)}
                {\sum_{k=1}^{M} \exp
                    \left(
                        -\frac{1}{2\sigma^2} \lVert s_j - T(m_k, \theta)\rVert^2
                    \right) + (2\pi \sigma^2)^\frac{D}{2} \frac{w}{1-w} \frac{M}{N}}$
           M-paso, resolver la transformación óptima
           $\lbrace \theta,\sigma^2 \rbrace$ := resolver$(\mathbf{S}, \mathbf{M}, \mathbf{P})$
retorno $\theta$

donde el vector $\mathbf{1}$ es un vector columna de unos. El resolver función diferencia por el tipo de registro realizado. Por ejemplo, en el registro rígido, la salida es una escala $a$, una matriz de rotación $\mathbf{R}$y un vector de traslación $\mathbf{t}$. El parámetro $\theta$ puede escribirse como una tupla de éstos:

$\theta = \lbrace a, \mathbf{R}, \mathbf{t}\rbrace$

que se inicializa en uno, el matriz identidady un vector columna de ceros:

$\theta_0 = \lbrace 1, \mathbf{I}, \mathbf{0}\rbrace$

Es el conjunto de puntos alineados:

$T(\mathbf{M}) = a\mathbf{M}\mathbf{R}^T + \mathbf{1}\mathbf{t}^T$

El solve_rigid función de registro rígido puede escribirse entonces como sigue, con derivación de la álgebra explicada en papel de Myronenko 2010.

   solve_rigid$(\mathbf{S}, \mathbf{M}, \mathbf{P})$
       $N_\mathbf{P}$ := $\mathbf{1}^T\mathbf{P}\mathbf{1}$
       $\mu_s$ := $\frac{1}{N_\mathbf{P}}\mathbf{S}^T\mathbf{P}^T\mathbf{1}$
       $\mu_m$ := $\frac{1}{N_\mathbf{P}}\mathbf{M}^T\mathbf{P}\mathbf{1}$
       $\hat{\mathbf{S}}$ := $\mathbf{S} - \mathbf{1}\mu_s^T$
       $\hat{\mathbf{M}}$ := $\mathbf{M} - \mathbf{1}\mu_s^T$
       $\mathbf{A}$ := $\hat{\mathbf{S}^T}\mathbf{P}^T\hat{\mathbf{M}}$
       $\mathbf{U}, \mathbf{V}$ := SVD$(\mathbf{A})$ el descomposición de valor singular de $\mathbf{A}=\mathbf{U}\Sigma\mathbf{V}^T$
       $\mathbf{C}$ := $\operatorname{diag}(1, ..., 1, \det(\mathbf{UV}^T))$ // $\operatorname{diag}(\xi)$ es el matriz diagonal formado a partir de vectores $\xi$
       $\mathbf{R}$ := $\mathbf{UCV}^T$
       $a$ := $\frac{\operatorname{tr}(\mathbf{A}^T\mathbf{R})}{\operatorname{tr}(\mathbf{\hat{\mathbf{M}}^T \operatorname{diag}(\mathbf{P}\mathbf{1})\hat{\mathbf{M}}})}$ // $\operatorname{tr}$ es el rastro de una matriz
       $\mathbf{t}$ := $\mu_s - a\mathbf{R}\mu_m$
       $\sigma^2$ := $\frac{1}{N_\mathbf{P} D}(\operatorname{tr}(\mathbf{\hat{\mathbf{S}}^T \operatorname{diag}(\mathbf{P}^T\mathbf{1})\hat{\mathbf{S}}}))-a\operatorname{tr}(\mathbf{A}^T\mathbf{R})$
retorno $\lbrace a, \mathbf{R}, \mathbf{t}\rbrace, \sigma^2$

Para el registro afín, donde el objetivo es encontrar un Transformación afín en lugar de uno rígido, el resultado es una matriz de transformación afín $\mathbf{B}$ y una traducción $\mathbf{t}$ tal que el conjunto de puntos alineados:

$T(\mathbf{M}) = \mathbf{M}\mathbf{B}^T + \mathbf{1}\mathbf{t}^T$

El solve_affine función de registro rígido puede escribirse entonces como sigue, con derivación de la álgebra explicada en papel de Myronenko 2010.

   solve_affine$(\mathbf{S}, \mathbf{M}, \mathbf{P})$
       $N_\mathbf{P}$ := $\mathbf{1}^T\mathbf{P}\mathbf{1}$
       $\mu_s$ := $\frac{1}{N_\mathbf{P}}\mathbf{S}^T\mathbf{P}^T\mathbf{1}$
       $\mu_m$ := $\frac{1}{N_\mathbf{P}}\mathbf{M}^T\mathbf{P}\mathbf{1}$
       $\hat{\mathbf{S}}$ := $\mathbf{S} - \mathbf{1}\mu_s^T$
       $\hat{\mathbf{M}}$ := $\mathbf{M} - \mathbf{1}\mu_s^T$
       $\mathbf{B}$ := $(\hat{\mathbf{S}^T}\mathbf{P}^T\hat{\mathbf{M}})(\hat{\mathbf{M}^T}\operatorname{diag}(\mathbf{P}\mathbf{1})\hat{\mathbf{M}})^{-1}$
       $\mathbf{t}$ := $\mu_s - \mathbf{B}\mu_m$
       $\sigma^2$ := $\frac{1}{N_\mathbf{P} D}(\operatorname{tr}(\mathbf{\hat{\mathbf{S}} \operatorname{diag}(\mathbf{P}^T\mathbf{1})\hat{\mathbf{S}}}))-\operatorname{tr}(\hat{\mathbf{S}^T}\mathbf{P}^T\hat{\mathbf{M}}\mathbf{B}^T)$
retorno $\mathbf{B}, \mathbf{t}\rbrace, \sigma^2$

También es posible utilizar CPD con registro deformable usando una parametrización derivado usando cálculo de la variación.

Las sumas de las distribuciones gaussianas pueden ser computadas en tiempo lineal usando el transformación rápida de Gauss (FGT). En consecuencia, la complejidad de tiempo de CPD es $O(M+N)$, que es asintóticamente mucho más rápido que $O(MN)$ métodos.

Enlaces externos

• Implementación de referencia de placa delgada tira punto robusto que empareja
• Implementación de referencia de punto de correlación del núcleo conjunto registro
• Implementación de referencia de punto coherente deriva

Otras Páginas

• Alfred A. Tomatis
• Telemedicina
• John Dillinger
• Roca de Viking
• Expedicion perdida de Franklin