Hashing geométrico: Algoritmos eficientes para el reconocimiento y la comparación de imágenes

Por Fouad Sabry

¿Qué es el 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, a través de extensiones. existen 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 hash como una clave y los índices de los puntos básicos como un valor. Luego se selecciona un nuevo par de puntos básicos y se repite el proceso. En el paso en línea (reconocimiento), se consideran como bases candidatas pares de puntos de datos seleccionados aleatoriamente. Para cada base candidata, los puntos de datos restantes se codifican según 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.

Cómo se beneficiará

(I) Insights, y validaciones sobre los siguientes temas:

Capítulo 1: Hashing geométrico

Capítulo 2: Geometría analítica

Capítulo 3: Sistema de coordenadas cartesiano

Capítulo 4: Gráficos por computadora 2D

Capítulo 5: Sistema de coordenadas

Capítulo 6: Traslación (geometría)

Capítulo 7: Transformada de Hough

Capítulo 8: Transformación de características invariantes de escala

Capítulo 9: Homografía

Capítulo 10: Aprendizaje de características geométricas

(II) Respondiendo las principales preguntas del público sobre hash geométrico.

(III) Ejemplos del mundo real para el uso de hash geométrico en muchos campos.

Para quién es este libro

Profesionales, estudiantes de pregrado y posgrado, entusiastas, aficionados y aquellos que quieran ir más allá del conocimiento o información básica para cualquier tipo de Hashing Geométrico.

 

 

• Idioma: Español
• Editorial: Mil Millones De Conocimientos [Spanish]
• Fecha de lanzamiento: 11 may 2024

Vista previa del libro

Capítulo 1: Hash geométrico

Hay expansiones para varias representaciones y transformaciones de objetos, pero en ciencias de la computación, el hash geométrico se usa para ubicar de manera eficiente objetos en dos dimensiones representadas por puntos discretos que han sufrido una transformación afín. Fuera de línea, cada par de puntos se utiliza como base geométrica para codificar los objetos. Dos parámetros permiten una representación invariante de la base de los puntos restantes. La tabla hash mantiene un par de valores: los índices de los puntos básicos de cada clave y las coordenadas convertidas cuantificadas de cada valor. A continuación, se repite el procedimiento, esta vez utilizando un conjunto diferente de puntos básicos. En la fase en línea (reconocimiento), los emparejamientos arbitrarios de puntos de datos se evalúan como posibles fundamentos. Con el fin de encontrar correspondencias factibles entre el objeto y cada base candidata, los puntos de datos restantes se codifican de acuerdo con la base. Si una fracción lo suficientemente grande de los puntos de datos apunta a una base de objeto constante, se acepta la base candidata.

En visión artificial, el hash geométrico se propuso por primera vez para el reconocimiento de objetos 2D y 3D, el reconocimiento de objetos mediante hash geométrico.

Supongamos que queremos comprobar si una imagen de modelo se puede ver en una imagen de entrada.

El hash geométrico es un método que se puede utilizar para lograr esto.

La técnica podría usarse para identificar un solo objeto entre muchos en una base de datos, en este escenario, la tabla hash debe realizar un seguimiento tanto de los datos de pose como del índice base del modelo de objetos.

Con el fin de mantener el ejemplo sencillo, simplemente usaremos algunas características de puntos y asumiremos que sus descripciones provienen únicamente de sus coordenadas (en la práctica, los descriptores locales como SIFT podrían usarse para la indexación).

Conozca las características definitorias del modelo.

Supongamos que se encuentran 5 puntos característicos en la imagen del modelo con las coordenadas (12,17); (45,13); (40,46); (20,35); (35,25) , vea la fotografía.

Proporcione una base para describir las coordenadas de los puntos de entidad.

Los dos puntos que proporcionan la base para una transformación de similitud en el espacio bidimensional.

El punto de partida se encuentra a mitad de camino de la línea que une los dos puntos (P1, P2), el P4 de nuestro caso de estudio, el x' eje se dirige hacia uno de ellos, el es y' ortogonal y pasa por el origen.

La escala se selecciona de tal manera que el valor absoluto de x' para ambos puntos básicos sea 1.

Explique dónde están las cosas en relación con ese fundamento, es decir,

Calcule las transformaciones en los nuevos ejes.

Para que el reconocimiento sea más resistente al ruido, las coordenadas deben discretizarse, se utiliza un contenedor de 0,25 unidades.

Así obtenemos las coordenadas (-0.75,-1.25); (1.00,0.00); (-0.50,1.25); (-1.00,0.00); (0.00,0.25)

Utilice una tabla hash con las entidades como índice para almacenar la base (solo las coordenadas transformadas en este caso). El número de artículos que se van a almacenar con el par base si hay más de dos con los que coincidir.

Cambie a un nuevo par base y continúe desde allí (Paso 2). Para hacer frente a las oclusiones, esto es esencial. Lo ideal es que se enumeren todos los pares que no son lineales. Después de dos iteraciones, en las que se elige el par (P1, P3), presentamos la tabla hash.

Tabla hash:

La mayoría de las tablas hash no permiten que las claves duplicadas se asocien con valores separados.

Por lo tanto, en la vida real no se codificarán las claves básicas (1.0, 0.0) y (-1.0, (tabla hash, valor de 0).

Localice los puntos de atractivo visual en la imagen dada.

Elige un punto de partida aleatorio. Es probable que la imagen de entrada no contenga el elemento de destino si no hay una base arbitraria adecuada para determinar si está presente o no.

Detalle las ubicaciones de los puntos de entidad del nuevo sistema de coordenadas. Realice la cuantificación tradicional de las coordenadas resultantes.

Verifique las entidades de puntos convertidos de la imagen de entrada con respecto a la tabla hash. En el caso de que las entidades de punto sean iguales o muy similares, se debe aumentar el recuento de la base relevante (y el tipo de objeto, si lo hay).

Si el recuento de una determinada base es mayor que algún umbral, es probable que esta base corresponda a una base de imagen seleccionada en el paso 2. Para hacer esto, primero convertimos el sistema de coordenadas de la imagen al del modelo (para el objeto ficticio). Si funciona, el elemento está localizado. Si no es así, vuelva al paso anterior.

Parece que las únicas transformaciones que este enfoque puede manejar son las de tamaño, posición y orientación. Sin embargo, es posible que el elemento ya exista en la imagen suministrada en un formato de imagen reflejada. En consecuencia, el objeto también debe ser detectable mediante hash geométrico. Los objetos reflejados se pueden identificar de dos maneras diferentes.

Haz que el lado izquierdo del gráfico vectorial sea positivo y el lado derecho negativo. Para obtener el mismo resultado al multiplicar por x, simplemente suma -1.

Usa una tríada como punto de partida. Esto permite la identificación de reflejos (u objetos). Otro método de hash geométrico utiliza un conjunto de tres puntos como base.

El hash funciona de manera similar para datos de dimensiones superiores, como se muestra arriba. Se requieren tres puntos para la base de los datos tridimensionales. El eje x está definido por los dos primeros puntos y el eje y por el tercero (con el primer punto). Usando la regla de la mano derecha, se puede construir un eje y el eje z será perpendicular a él. La base resultante es sensible a la secuencia en la que se introducen los puntos.

{Fin del capítulo 1}

Capítulo 2: Geometría analítica

La geometría analítica, a menudo llamada geometría de coordenadas o geometría cartesiana, es una rama de las matemáticas que se ocupa del estudio de la geometría desde una perspectiva cartesiana. La geometría sintética es lo opuesto a esto.

La física, la ingeniería, la aviación, la cohetería, la ciencia espacial y los viajes espaciales hacen uso de la geometría analítica. Es la base de varias ramas de la geometría contemporánea, como la geometría algebraica, diferencial, discreta y computacional.

Cuando se trabaja con ecuaciones que involucran planos, líneas rectas y círculos, se suele utilizar el sistema de coordenadas cartesianas. En geometría, se estudia el plano euclidiano bidimensional y el espacio euclidiano tridimensional. La geometría analítica, tal como se define y enseña típicamente en los libros de texto, se ocupa de crear y representar formas geométricas en un sentido numérico, y extraer información numérica de estas representaciones. El axioma de Cantor-Dedekind garantiza que los cálculos en la geometría del continuo lineal se pueden realizar usando solo el álgebra de los números reales.

Se ha argumentado que el matemático griego Menecmo desarrolló la geometría analítica debido a su uso de una técnica que se asemejaba al uso de coordenadas en la resolución de problemas y la demostración de teoremas.

El matemático persa del siglo XI Omar Khayyam vio una fuerte relación entre la geometría y el álgebra y se estaba moviendo en la dirección correcta cuando ayudó a cerrar la brecha entre el álgebra numérica y el álgebra geométrica: 248

La geometría analítica fue inventada independientemente por René Descartes y Pierre de Fermat, la geometría cartesiana, sinónimo de geometría analítica, lleva el nombre de Descartes.

Descartes hizo progresos significativos con los métodos en un ensayo titulado La Géométrie (Geometría), un apéndice de su Discurso sobre el método para dirigir correctamente la razón y buscar la verdad en las ciencias, publicado en 1637.

La Geometrie, compuesta íntegramente en su lengua materna, el francés, sus fundamentos teóricos, etc., sentó las bases para el desarrollo del cálculo en Europa.

El trabajo fue recibido con escepticismo al principio, debido, en parte, a los numerosos agujeros en el argumento y a las matemáticas enredadas.

La obra maestra de Descartes no fue reconocida por lo que era hasta después de que Van Schooten la tradujera al latín y añadiera comentarios en 1649 (y después de que continuara trabajando en ella).

Como resultado de tomar este rumbo, a Descartes se le encomendó la tarea de resolver ecuaciones más intrincadas, lo que requirió el refinamiento de las técnicas para manejar ecuaciones polinómicas de mayor grado.

Leonhard Euler fue el primero en investigar sistemáticamente curvas y superficies en el espacio utilizando el método de coordenadas.

En geometría analítica, se introduce un sistema de coordenadas para el plano y a cada punto se le asignan dos números reales. A cada punto del espacio euclidiano también se le asignan tres coordenadas. La importancia de las coordenadas viene determinada por el punto de referencia elegido. Existen muchos sistemas de coordenadas diferentes, pero los siguientes son los más comunes:

Las coordenadas cartesianas, en las que cada punto tiene una coordenada x que representa su posición horizontal y una coordenada y que representa su posición vertical, son el sistema de coordenadas más utilizado. Por lo general, se presentan como una expresión pareada (x, y). Cada punto en el espacio euclidiano tridimensional se puede representar mediante un triple ordenado de coordenadas usando este método (x, y, z).

En notación polar, cada punto del plano está representado por su distancia r desde el