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 manera invariante con respecto a esta base utilizando dos parámetros. Para cada punto, sus coordenadas transformadas cuantificadas se almacenan en la tabla hash como una clave y los índices de los puntos base como un valor. Luego, se selecciona un nuevo par de puntos base y se repite el proceso. En el paso en línea (de reconocimiento), los pares de puntos de datos seleccionados aleatoriamente 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 una cantidad suficientemente grande de puntos de datos indexa una base de objeto consistente.
El hash geométrico es un método utilizado para el reconocimiento de objetos. Supongamos que queremos comprobar si una imagen de modelo se puede ver en una imagen de entrada. Esto se puede lograr con 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 posición, sino también el índice del modelo del objeto en la base.
Puntos del objeto en el sistema de coordenadas de la imagen y ejes del sistema de coordenadas de la base (P2, P4)
Encuentre los puntos característicos del modelo. Suponga que se encuentran 5 puntos característicos en la imagen del modelo con las coordenadas , vea la imagen.
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), el eje se dirige hacia uno de ellos, es ortogonal y pasa por el origen. La escala se selecciona de modo que el valor absoluto de para ambos puntos base sea 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 resistente al ruido; tomamos el tamaño del bin 0,25. De este modo, obtenemos las coordenadas
Almacenar 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 base.
Repita el proceso para un par de bases diferente (Paso 2). Es necesario para manejar oclusiones . Lo ideal es que se enumeren 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 vida real no se codificarán las claves base (1.0, 0.0) y (-1.0, 0.0) en una tabla hash.
Fase de reconocimiento
Encuentre puntos característicos 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.
Describir las coordenadas de los puntos característicos en la nueva base. Cuantificar las coordenadas obtenidas como se hizo antes.
Compare todas las características de puntos transformadas en la imagen de entrada con la tabla hash. Si las características de puntos son idénticas o similares, aumente el recuento para la base correspondiente (y el tipo de objeto, si lo hay).
Para cada base cuyo recuento supere 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 hacerlos coincidir. Si tiene éxito, se habrá encontrado el objeto. De lo contrario, vuelva al Paso 2.
Encontrar el patrón reflejado
Parece que este método solo es capaz de manejar escala, traslación y rotación. Sin embargo, la imagen de entrada puede contener el objeto en transformación reflejada. 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 como base. Esto permite detectar imágenes reflejadas (u objetos). En realidad, utilizar 3 puntos como base es otro enfoque para el hashing geométrico.
Hashing geométrico en dimensiones superiores
De manera similar al 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 utilizando la regla de la mano derecha. Observe que el orden de los puntos afecta la base resultante.
^ 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.
^ Moll, Mark; Bryant, Drew H.; Kavraki, Lydia E. (11 de noviembre de 2010). "El algoritmo LabelHash para la correspondencia de subestructuras". BMC Bioinformatics . 11 : 555. doi : 10.1186/1471-2105-11-555 . ISSN 1471-2105. PMC 2996407 . PMID 21070651.
^ 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. 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 Computational Science and Engineering, 4(4), 10-21.
