Verificación espacial
# Verificación espacial

La verificación espacial tiene la labor de verificar una concordancia espacial entre determinados puntos de una pareja de imágenes.

En las imágenes de la derecha se observa que ambos pares de imágenes tienen palabras visuales en común, pero tan solo una pareja tiene las coincidencias coherentes entre sí.

El problema principal es que los valores atípicos (que no encaja o no corresponde con el modelo seleccionado) afectan al ajuste por mínimos cuadrados (técnica de análisis numérico enmarcada dentro de la optimización matemática, en la que, dados un conjunto de pares ordenados: variable independiente, variable dependiente, y una familia de funciones, se intenta encontrar la función continua).

## Ventajas

* Efectivo cuando se es capaz de encontrar características seguras sin desorden.
* Buenos resultados para la correspondencia en instancias específicas.

## Inconvenientes

* El escalado de modelos.
* La verificación espacial no se puede utilizar como post-procesado.

## Métodos

Los métodos más utilizados para realizar la verificación espacial y evitar errores causados por estos valores atípicos, son los siguientes:

### RANSAC (RANdom Sample Consensus)

Pretende evitar el impacto de los valores atípicos, o que no encajan con el modelo, así que solo tiene en cuenta los "típicos", los que coinciden con el model en cuestión. Si se elige un valor atípico para calcular el ajuste en curso, entonces la línea resultante tendrá poco apoyo del resto de los puntos. El algoritmo que se lleva a cabo consiste en un loop que realiza los siguientes pasos:

* De todo el conjunto de datos de entrada, se toma un subconjunto de ellos al azar con el fin de estimar el modelo.
* Computar el modelo del subconjunto. El modelo se estima con algoritmos lineales estándares.
* Buscar los valores coincidentes de la transformación.
* Si el error del modelo es mínimo, este es aceptado, y si el número de correspondencias es suficientemente largo, el subconjunto de los puntos implicados se denomina conjunto de consenso. Y se vuelve a computar el modelo estimado en todas las correspondencias.

El objetivo es mantener el modelo con mayor número de coincidencias y el problema principal es el número de veces que se tendrá que repetir el proceso para obtener la mejor estimación del modelo. RANSAC establece de antemano el número de iteraciones en el algoritmo.

Para especificar escenas u objetos, se suele utilizar la transformación afín para llevar a cabo la verificación espacial.

### TGH (Transformada Generalizada de Hough)

Se trata de una técnica para la detección de figuras en imágenes digitales que resuelve la veracidad del espacio mediante agrupaciones de los puntos que pertenecen al modelo a través de un procedimiento de votación sobre un conjunto de figuras parametrizadas.

No es factible comprovar todas las combinaciones de características ajustando un modelo para cada subconjunto posible, de modo que se usa la técnica de votación, en la que se guarda un voto por cada possible línea en la que cada punto se encuentra. Luego se observa cuáles han sido las líneas con más votos y aquellas son las seleccionadas.

Si utilizamos las características locales de escala, rotación y traslación invariantes, cada coincidencia característica da una hipótesis de alineación para la escala, traslación y orientación del modelo en la imagen.

Una hipótesis generada por una sola coincidencia puede ser poco fiable, así que para cada coincidencia (match), se hace una votación para conseguir una hipótesis en el espacio Hough más sólida. De modo que tenemos dos fases importantes:

* Entrenamiento: Para cada modelo característico, se guarda en 2D la localización, escala y orientación del modelo.
* Prueba: Se deja que cada coincidencia sea realizada mediante el algoritmo SIFT y el modelo de características vote en el espacio Hough.

Las principales desventajas son las siguientes:

* El ruido o el desorden puede mostrar más votaciones de los que se pretendían obtener como objetivo.
* El tamaño de la matriz acumuladora debe escogerse con cuidado.

## RANSAC VS Transformada generalizada de Hough

Diferencias entre RANSAC y GHT :

| | GHT | RANSAC |
| - | - | - |
| Correspondencia | Única correspondencia, votación para todos los parámetros consistentes | Mínimo subconjunto de correspondencias para estimar el modelo (count liners) |
| Representación | Representa incerteza en el espacio modelo | Representa incerteza en el espacio imagen |
| Complejidad | Complejidad lineal en el número de correspondencias y el número de células de voto | Debe buscar todos los puntos de datos para comprobar inliers en cada iteración |
| Ventajas | Puede manejar outliers mayores | Escala mejor a espacios de mayores dimensiones |

## Ejemplos

* Sistema de recuperación de Google. El objetivo es recuperar objetos o escenas con la facilidad, rapidez y afinación en que el buscador Google encuentra una página web que contiene unas palabras determinadas.
