Hispanopedia Wiki
Articulo de referencia

Hash geométrico

En informática , el hash geométrico es un método para encontrar eficientemente objetos bidimensionales representados por puntos discretos que han sufrido una transformación afín...

Hispanopedia WikiContenido en espanolLectura gratuita

En informática , el hash geométrico es un método para encontrar eficientemente objetos bidimensionales representados por puntos discretos que han sufrido una transformación afín , aunque existen extensiones a 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 hash como clave, y los índices de los puntos de la base como valor. Luego se selecciona un nuevo par de puntos de la base y se repite el proceso. En el paso en línea (reconocimiento), se consideran pares de puntos de datos seleccionados aleatoriamente como bases candidatas. Para cada base candidata, los puntos de datos restantes se codifican según la base y se encuentran posibles correspondencias del objeto en la tabla previamente construida. 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 propuso originalmente en visión por computadora para el reconocimiento de objetos en 2D y 3D, [ 1 ] pero luego se aplicó a diferentes problemas como la alineación estructural de proteínas . [ 2 ] [ 3 ]

Hashing geométrico en visión artificial

El hash geométrico es un método utilizado para el reconocimiento de objetos. Supongamos que queremos comprobar si una imagen modelo se puede ver en una imagen de entrada. Esto se puede lograr con el hash geométrico. El método se puede utilizar para reconocer uno de los múltiples objetos en una base; en este caso, la tabla hash debe almacenar no solo la información de la pose, sino también el índice del modelo del objeto en la base.

Ejemplo

Para simplificar, este ejemplo no utilizará demasiados elementos puntuales y asumirá que sus descriptores vienen dados únicamente por sus coordenadas (en la práctica, se podrían utilizar descriptores locales como SIFT para la indexación).

Fase de formación

Puntos del objeto en el sistema de coordenadas de la imagen y ejes del sistema de coordenadas de la base (P2, P4).
  1. Encuentra los puntos característicos del modelo. Supón que se encuentran 5 puntos característicos en la imagen del modelo con las coordenadas(12,17);{\displaystyle (12,17);}(45,13);{\displaystyle (45,13);}(40,46);{\displaystyle (40,46);}(20,35);{\displaystyle (20,35);}(35,25){\displaystyle (35,25)}, mira la imagen.
  2. Introduzca una base para describir las ubicaciones de los puntos característicos. Para el espacio 2D y la transformación de similitud, la base se define mediante 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), elincógnita′{\displaystyle x'}El eje está dirigido hacia uno de ellos, ely′{\displaystyle y'}es ortogonal y pasa por el origen. La escala se selecciona de tal manera que el valor absoluto deincógnita′{\displaystyle x'}para ambos puntos base es 1.
  3. Describa las ubicaciones de las características con respecto a esa base, es decir, calcule las proyecciones a los nuevos ejes de coordenadas. Las coordenadas deben discretizarse para que el reconocimiento sea robusto al ruido; tomamos un tamaño de intervalo de 0,25. Así obtenemos las coordenadas.(−0,75,−1,25);{\displaystyle (-0,75,-1,25);}(1.00,0.00);{\displaystyle (1.00,0.00);}(−0,50,1,25);{\displaystyle (-0.50,1.25);}(−1.00,0.00);{\displaystyle (-1.00,0.00);}(0.00,0,25){\displaystyle (0.00,0.25)}
  4. Almacene la base en una tabla hash indexada por las características (en este caso, solo coordenadas transformadas). Si hubiera más objetos con los que comparar, también deberíamos almacenar el número de objeto junto con el par base.
  5. Repita el proceso para un par de bases diferente (Paso 2). Esto es necesario para manejar las oclusiones . Idealmente, se deberían enumerar todos los pares no colineales . Proporcionamos la tabla hash después de dos iteraciones; el par (P1, P3) se selecciona para la segunda.

Tabla hash:

La mayoría de las tablas hash no pueden tener claves idénticas asignadas a valores diferentes. Por lo tanto, en la práctica no se codificarán las claves base (1.0, 0.0) y (-1.0, 0.0) en una tabla hash.

Fase de reconocimiento

  1. Encuentra puntos de interés en la imagen de entrada.
  2. Elija una base arbitraria. Si no existe una base arbitraria adecuada, es probable que la imagen de entrada no contenga el objeto buscado.
  3. Describe las coordenadas de los puntos característicos en la nueva base. Cuantifica las coordenadas obtenidas como se hizo anteriormente.
  4. Compara todas las características puntuales transformadas de la imagen de entrada con la tabla hash. Si las características puntuales son idénticas o similares, incrementa el contador para la base correspondiente (y el tipo de objeto, si lo hay).
  5. Para cada base cuyo recuento supere un umbral determinado, verifique la hipótesis de que corresponde a una base de imagen seleccionada en el paso 2. Transfiera el sistema de coordenadas de la imagen al del modelo (para el supuesto objeto) e intente que coincidan. Si lo consigue, se ha encontrado el objeto. De lo contrario, vuelva al paso 2.

Encontrar patrones simétricos

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 especular. Por lo tanto, el hash geométrico también debería poder encontrar el objeto. Hay dos maneras de detectar objetos reflejados.

  1. Para el gráfico vectorial, asigna un valor positivo al lado izquierdo y un valor negativo al lado derecho. Multiplicar la posición x por -1 dará el mismo resultado.
  2. Utilice 3 puntos como base. Esto permite detectar imágenes especulares (u objetos). De hecho, usar 3 puntos como base es otro método para el hash geométrico.

Hashing geométrico en dimensiones superiores

De forma similar al ejemplo anterior, el hashing se aplica a datos de dimensiones superiores. Para 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 (junto con el primero). El eje z es perpendicular al eje creado utilizando la regla de la mano derecha . Nótese que el orden de los puntos afecta a la base resultante.

Véase también

Referencias

  1. ↑ AS Mian, M. Bennamoun y R. Owens, Reconocimiento y segmentación de objetos basados ​​en modelos tridimensionales en escenas desordenadas , IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 28, octubre de 2006, págs. 1584-601.
  2. ↑ Moll, Mark; Bryant, Drew H.; Kavraki, Lydia E. (2010-11-11). "El algoritmo LabelHash para la coincidencia de subestructuras" . BMC Bioinformatics . 11 555. doi : 10.1186/1471-2105-11-555 . ISSN 1471-2105 . PMC 2996407. PMID 21070651 .   
  3. ↑ Nussinov, R.; Wolfson, HJ (1991-12-01). "Detección eficiente de motivos estructurales tridimensionales en macromoléculas biológicas mediante técnicas de visión por computadora" . Actas de la Academia Nacional de Ciencias de los Estados Unidos de América . 88 (23): 10495– 10499. Bibcode : 1991PNAS...8810495N . doi : 10.1073/pnas.88.23.10495 . ISSN 0027-8424 . PMC 52955. PMID 1961713 .   
  • Wolfson, HJ y Rigoutsos, I (1997). Hashing geométrico: una visión general. IEEE Computational Science and Engineering, 4(4), 10-21.