martes, 15 de abril de 2014

Como saber si dos figuras son similares y para que me puede servir?

Bueno para responder la primer parte de la pregunta, les comento que voy a hablar sobre Hausdorff. Seguramente se preguntaran porque, o por lo menos yo no tenia ningún conocimiento de su existencia.



Como primer medida vamos a ver la definición, tomada de Wikipedia:

"""
En matemáticas, la distancia de Hausdorff, o métrica de Hausdorff, también llamada distancia de Pompeiu-Hausdorff, mide cuan lejos se encuentran dos sub-conjuntos de medidas en el espacio el uno del otro.

Convierte el conjunto de subconjuntos compactos no vacíos de un espacio métrico en un espacio métrico en si mismo. Este lleva el nombre de Felix Hausdorff.
Informalmente, dos conjuntos están cerca de la distancia de Hausdorff si cada punto de alguno de los conjuntos está cerca de algún punto de la otra serie de puntos. La distancia de Hausdorff es la distancia más larga a la que puede ser obligado a viajar por un adversario que elige un punto en uno de los dos conjuntos, de donde luego debe viajar al otro conjunto. En otras palabras, es la mayor de todas las distancias de un punto en un juego hasta el punto más cercano en el otro conjunto.

Parece ser que esta distancia se introdujo por primera vez por Hausdorff en su libro Grundzüge der Mengenlehre, publicado por primera vez en 1914.

En computación, la distancia de Hausdorff se puede utilizar para encontrar una plantilla dada en una imagen de destino arbitrario. La plantilla y la imagen a menudo son pre-procesadas a través de un detector de bordes dando una imagen binaria.
A continuación, cada punto en la imagen binaria de la plantilla es tratado como un punto en un conjunto, la "forma" de la plantilla. Del mismo modo, un área de la imagen de destino binario se trata como un conjunto de puntos.
Un algoritmo, trata de encontrar la distancia de Hausdorff entre la plantilla y una cierta área de la imagen de destino. El área en la imagen de destino con la mínima distancia de Hausdorff a la plantilla, puede ser considerado el mejor candidato para la localización de la plantilla en el objetivo.

En gráficos generados por computadora la distancia de Hausdorff se utiliza para medir la diferencia entre dos representaciones diferentes del mismo objeto 3D, especialmente cuando se genera el nivel de detalle para la visualización eficiente de complejos modelos en 3D.

"""

En resumen la distancia de Hausdorff es la distancia máxima de un conjunto hasta el punto más cercano en el otro conjunto.

En mi caso tenia que verificar que dos objetos que eran posicionados por GPS estén realizando el mismo recorrido, ustedes dirán porque no ver si las posiciones que nos envían son iguales. Ahora este es el problema y el motivo de porque termino en la investigación de este algoritmo:

- Los GPS no son absolutamente precisos.
- Los objetos a los que se realiza el seguimiento utilizan diferentes tipos de GPS, por lo tanto las posiciones enviadas por mas que estén utilizando los mismos satélites, pueden enviar diferentes posiciones.
- Las posiciones no son enviadas necesariamente al mismo tiempo.

Al tener estos problemas en mente, no me sirve la simple comparación por ejemplo, si la posición que me enviá el GPS 1, es la misma que la del GPS 2, ya que si una fue enviada con 1 minuto de diferencia de la otra, mas la impresicion que pueden llegar a tener, obviamente que me pueden dar resultados muy diferentes, a pesar de que probablemente estén en el mismo lugar. Lo ideal es tener dos conjuntos de ubicaciones y verificar si estos son relativamente similares, lo que indicaría que están realizando el mismo recorrido, por lo tanto "viajan juntos". De ahí vino que fue necesario utilizar este algoritmo, que debo aclarar, me lo recomendó un ex-compañero del trabajo, Valentin ;)

En este enlace podrán encontrar el código fuente de la función que termine utilizando: Gist
En el código verán que trabajo con valores x e y, esto se debe a que realizó un traspaso, de latitud y longitud a un par de ejes de coordenadas para manejar las ubicaciones ;)

Enlaces de interés:
Hausdorff distance wikipedia
Hausdorff distance between convex polygons
Measuring difference between two meshes





Espero que a alguno le haya resultado de utilidad este post, en realidad puede tener muchas mas utilidades, y es un tema realmente interesante. Otro ejemplo de uso, es el encontrar figuras en imágenes, por ejemplo países como EEUU toman imágenes aéreas y con algoritmo similares a estos en las imágenes buscan por ejemplo aviones de combate u otro tipo de armamento escondido en diferentes lugares. Lo único que se tiene que tener es dos figuras a comparar y un poco de imaginación para lo que se lo pueda utilizar ;)

Saludos a todos, Gabriel