Cómputo de la similitud entre figuras geométricas

Abstract

En este trabajo se aborda el problema de determinar similitud o semejanza entre figuras geométricas; la importancia de dicho problema radica en su vasta aplicabilidad. Aunque el humano es capaz de ligar entidades distintas (personas, situaciones políticas, etc.) en base a su similitud/disimilitud, con aparente facilidad, los mecanismos empleados aún son desconocidos.

La dificultad de encontrar un método cuyo criterio de comparación sea universalmente aceptado aún en un contexto particular (imágenes, secuencias, objetos3D, ontologías, códigos fuente, textos, etc.), hace que el problema de semejanza sea el foco de atención para muchos investigadores.

En este trabajo se presentan dos métodos para representar y buscar similitud entre figuras geométricas. Por representación se refiere a la codificación de las entidades(figuras geométricas), por medio de secuencias, dicha representación resulta conveniente para la detección de relaciones de similitud adimensional (RNA Fuzzy ART) y dimensional (Dynamic Time Warping).

El primer método para representar y buscar similitud entre figuras geométricas, no contempla etapas de extracción, selección, y/o construcción de características clásicas; dicho método utiliza una tripleta de secuencias acopladas para representar una figura dado, cada secuencia representa un solo eje cartesiano (X, Y, y Z); estas secuencias son presentadas a una tripleta de RNA’s Fuzzy ART, éstas comparten los mismos valores de parámetros, y determinan la pertenencia de una figura a una clase utilizando la tripleta de categorías en forma de cadenas binarias que han sido generadas por las RNA Fuzzy ART y la distancia de Hamming.

El segundo método, representa figuras y su respectiva matriz de adyacencia, en secuencias; y determina distancias de semejanza usando Dynamic Time Warping(DTW). Aunque se ha probado la eficacia de DTW sobre la métrica Euclidiana, en este trabajo se exploran algunas de las propiedades de DTW, como los detalles de implementación y su complejidad temporal.

Son presentadas pruebas experimentales con figuras geométricas creadas con herramientas DAC (Diseño Asistido por Computadora), aplicando los métodos propuestos en este trabajo. Métodos y técnicas son detalladas y analizadas 2 cuidadosamente de forma aislada. Adicionalmente, se muestran dos técnicas para representar e indexar figuras en estructuras multidimensionales.

Los códigos utilizados en este trabajo son proporcionados en programas auto-contenidos, sin aspectos gráficos que puedan alejar al lector del problema de similitud. No es propósito del trabajo desarrollar una herramienta sino desarrollar ideas.