En informática , el hash geométrico es un método para encontrar de manera eficiente objetos bidimensionales representados por puntos discretos que han sufrido una transformación afín , aunque existen extensiones para otras representaciones y transformaciones de objetos. En un paso fuera de línea, los objetos se codifican tratando cada par de puntos como una base geométrica . Los puntos restantes se pueden representar de forma invariante con respecto a esta base utilizando dos parámetros. Para cada punto, sus coordenadas transformadas cuantificadas se almacenan en la tabla hashcomo clave y los índices de los puntos básicos como valor. Luego, se selecciona un nuevo par de puntos básicos y se repite el proceso. En el paso en línea (reconocimiento), los pares de puntos de datos seleccionados al azar se consideran bases candidatas. Para cada base candidata, los puntos de datos restantes se codifican de acuerdo con la base y las posibles correspondencias del objeto se encuentran en la tabla construida previamente. La base candidata se acepta si un número suficientemente grande de puntos de datos indexa una base de objeto consistente.
El hash geométrico se sugirió originalmente en la visión por computadora para el reconocimiento de objetos en 2D y 3D, [1] pero más tarde se aplicó a diferentes problemas, como la alineación estructural de proteínas . [2] [3]
Hash geométrico en visión artificial
El hash geométrico es un método utilizado para el reconocimiento de objetos. Digamos que queremos comprobar si se puede ver una imagen de modelo en una imagen de entrada. Esto se puede lograr con hash geométrico. El método podría usarse para reconocer uno de los múltiples objetos en una base, en este caso la tabla hash debería almacenar no solo la información de pose sino también el índice del modelo de objeto en la base.
Ejemplo
En aras de la simplicidad, este ejemplo no utilizará demasiadas características puntuales y asumirá que sus descriptores vienen dados únicamente por sus coordenadas (en la práctica, los descriptores locales como SIFT podrían usarse para indexar).
Fase de entrenamiento
![](http://wikiimg.tojsiabtv.com/wikipedia/commons/1/12/GeometricHasingExample.png)
- Encuentre los puntos característicos del modelo. Suponga que se encuentran 5 puntos característicos en la imagen del modelo con las coordenadas, mira la foto.
- Introduzca una base para describir las ubicaciones de los puntos característicos. Para el espacio 2D y la transformación de similitud, la base está definida por un par de puntos. El punto de origen se coloca en el medio del segmento que conecta los dos puntos (P2, P4 en nuestro ejemplo), el El eje se dirige hacia uno de ellos, el es ortogonal y pasa por el origen. La escala se selecciona de modo que el valor absoluto de para ambos puntos básicos es 1.
- Describir las ubicaciones de las características con respecto a esa base, es decir, calcular las proyecciones a los nuevos ejes de coordenadas. Las coordenadas deben discretizarse para que el reconocimiento sea robusto al ruido, tomamos el tamaño del contenedor 0.25. Así obtenemos las coordenadas
- Almacene la base en una tabla hash indexada por las características (solo coordenadas transformadas en este caso). Si hubiera más objetos con los que hacer coincidir, también deberíamos almacenar el número de objeto junto con el par de bases.
- Repita el proceso para un par de bases diferente (Paso 2). Es necesario para manejar oclusiones . Idealmente, se deberían enumerar todos los pares no colineales . Proporcionamos la tabla hash después de dos iteraciones, se selecciona el par (P1, P3) para la segunda.
Tabla de picadillo:
Vector (, ) | base |
---|---|
(P2, P4) | |
(P2, P4) | |
(P2, P4) | |
(P2, P4) | |
(P2, P4) | |
(P1, P3) | |
(P1, P3) | |
(P1, P3) | |
(P1, P3) | |
(P1, P3) |
La mayoría de las tablas hash no pueden tener claves idénticas asignadas a valores diferentes. Entonces, en la vida real, uno no codificará las claves básicas (1.0, 0.0) y (-1.0, 0.0) en una tabla hash.
Fase de reconocimiento
- Encuentre puntos de características interesantes en la imagen de entrada.
- Elija una base arbitraria. Si no hay una base arbitraria adecuada, es probable que la imagen de entrada no contenga el objeto de destino.
- Describe las coordenadas de los puntos característicos en la nueva base. Cuantifique las coordenadas obtenidas como se hizo antes.
- Compare todas las entidades de puntos transformadas en la imagen de entrada con la tabla hash. Si las entidades puntuales son idénticas o similares, aumente el recuento de la base correspondiente (y el tipo de objeto, si lo hay).
- Para cada base tal que el conteo exceda un cierto umbral, verifique la hipótesis de que corresponde a una base de imagen elegida en el Paso 2. Transfiera el sistema de coordenadas de la imagen al modelo (para el supuesto objeto) e intente igualarlas. Si tiene éxito, se encuentra el objeto. De lo contrario, vuelva al paso 2.
Encontrar un patrón reflejado
Parece que este método solo es capaz de manejar escalado, traslación y rotación. Sin embargo, la imagen de entrada puede contener el objeto en transformación espejo. Por lo tanto, el hash geométrico también debería poder encontrar el objeto. Hay dos formas de detectar objetos reflejados.
- Para el gráfico vectorial, haz que el lado izquierdo sea positivo y el lado derecho negativo. Multiplicar la posición x por -1 dará el mismo resultado.
- Utilice 3 puntos para la base. Esto permite detectar imágenes en espejo (u objetos). En realidad, usar 3 puntos como base es otro enfoque para el hashing geométrico.
Hash geométrico en dimensiones superiores
Al igual que en el ejemplo anterior, el hash se aplica a datos de dimensiones superiores. Para los puntos de datos tridimensionales, también se necesitan tres puntos para la base. Los dos primeros puntos definen el eje x y el tercer punto define el eje y (con el primer punto). El eje z es perpendicular al eje creado usando la regla de la mano derecha. Observe que el orden de los puntos afecta la base resultante.
Ver también
Referencias
- ^ AS Mian, M. Bennamoun y R. Owens, Reconocimiento y segmentación de objetos basados en modelos tridimensionales en escenas abarrotadas ., Transacciones IEEE sobre análisis de patrones e inteligencia de máquinas, vol. 28, octubre de 2006, págs. 1584-601.
- ^ Moll, Mark; Bryant, Drew H .; Kavraki, Lydia E. (11 de noviembre de 2010). "El algoritmo LabelHash para la coincidencia de subestructura" . BMC Bioinformática . 11 : 555. doi : 10.1186 / 1471-2105-11-555 . ISSN 1471-2105 . PMC 2996407 . PMID 21070651 .
- ^ Nussinov, R .; Wolfson, HJ (1 de diciembre de 1991). "Detección eficiente de motivos estructurales tridimensionales en macromoléculas biológicas mediante técnicas de visión por ordenador" . Actas de la Academia Nacional de Ciencias de los Estados Unidos de América . 88 (23): 10495–10499. doi : 10.1073 / pnas.88.23.10495 . ISSN 0027-8424 . PMC 52955 . PMID 1961713 .
- Wolfson, HJ y Rigoutsos, I (1997). Hashing geométrico: una descripción general. IEEE Ciencias e Ingeniería Computacional, 4 (4), 10-21.