La coincidencia de gráficos es el problema de encontrar similitudes entre gráficos . [1]
Los gráficos se utilizan comúnmente para codificar información estructural en muchos campos, incluida la visión por computadora y el reconocimiento de patrones , y la coincidencia de gráficos es una herramienta importante en estas áreas. [2] En estas áreas, se asume comúnmente que la comparación se realiza entre el gráfico de datos y el gráfico del modelo .
El caso de coincidencia exacta de gráficas se conoce como problema de isomorfismo de gráficas . [1] El problema de la correspondencia exacta de un gráfico con una parte de otro gráfico se denomina problema de isomorfismo de subgráfico .
La coincidencia inexacta de gráficas se refiere a problemas de coincidencia cuando la coincidencia exacta es imposible, por ejemplo, cuando el número de vértices en las dos gráficas es diferente. En este caso, es necesario encontrar la mejor coincidencia posible. Por ejemplo, en las aplicaciones de reconocimiento de imágenes , los resultados de la segmentación de imágenes en el procesamiento de imágenes suelen producir gráficos de datos con un número de vértices mucho mayor que en los gráficos del modelo con los que se espera que los datos coincidan. En el caso de los gráficos atribuidos , incluso si el número de vértices y aristas es el mismo, la coincidencia todavía puede ser solo inexacta. [1]
Dos categorías de métodos de búsqueda son las que se basan en la identificación de posibles e imposibles emparejamientos de vértices entre los dos gráficos y métodos que formulan la coincidencia de gráficos como un problema de optimización . [3] La distancia de edición de gráficos es una de las medidas de similitud sugeridas para la comparación de gráficos. [4] [5] La clase de algoritmos se denomina coincidencia gráfica tolerante a errores. [5]
Ver también
Referencias
- ^ a b c Endika Bengoetxea, "Coincidencia de gráficos inexactos mediante la estimación de algoritmos de distribución" , Ph. D., 2002, Capítulo 2: El problema de emparejamiento de gráficos (consultado el 28 de junio de 2017)
- ^ Endika Bengoetxea, Ph.D., Resumen
- ^ Métodos basados en gráficos en visión artificial: desarrollos y aplicaciones , p. 58
- ^ Reducción de la brecha entre la distancia de edición de gráficos y las máquinas de núcleo , p. dieciséis
- ↑ a b Horst Bunke, Xiaoyi Jang, "Graph Matching and Similarity", en: Intelligent Systems and Interfaces , págs. 281-304 (2000) doi : 10.1007 / 978-1-4615-4401-2_10