Una forma y su esqueleto, calculados con un algoritmo de adelgazamiento que preserva la topología.
En el análisis de formas , el esqueleto (o esqueleto topológico ) de una forma es una versión delgada de esa forma que es equidistante a sus límites . El esqueleto generalmente enfatiza las propiedades geométricas y topológicas de la forma, como su conectividad , topología , longitud , dirección y ancho . Junto con la distancia de sus puntos al límite de la forma, el esqueleto también puede servir como representación de la forma (contienen toda la información necesaria para reconstruir la forma).
Los esqueletos tienen varias definiciones matemáticas diferentes en la literatura técnica y existen muchos algoritmos diferentes para calcularlos. También se pueden encontrar diversas variantes diferentes de esqueleto, incluyendo esqueletos rectos , esqueletos morfológicos , etc.
En la literatura técnica, algunos autores utilizan indistintamente los conceptos de esqueleto y eje medial , [1] [2], mientras que otros autores [3] [4] [5] los consideran relacionados, pero no iguales. Del mismo modo, algunos consideran que los conceptos de esqueletización y adelgazamiento son idénticos [2] y otros no. [3]
Los esqueletos tienen varias definiciones matemáticas diferentes en la literatura técnica; la mayoría de ellos conducen a resultados similares en espacios continuos , pero normalmente producen resultados diferentes en espacios discretos .
Puntos de extinción del modelo de propagación del fuego.
En su artículo fundamental, Harry Blum [8] de los Laboratorios de Investigación de Cambridge de la Fuerza Aérea en la Base de la Fuerza Aérea Hanscom , en Bedford, Massachusetts , definió un eje medial para calcular el esqueleto de una forma, utilizando un modelo intuitivo de propagación del fuego sobre una hierba. campo, donde el campo tiene la forma de la forma dada. Si uno "prende fuego" simultáneamente en todos los puntos del límite de ese campo de hierba, entonces el esqueleto es el conjunto de puntos de extinción, es decir, aquellos puntos donde se encuentran dos o más frentes de onda. Esta descripción intuitiva es el punto de partida para una serie de definiciones más precisas.
Centros de discos máximos (o bolas)
Se dice que un disco (o bola ) B es máximo en un conjunto A si
, y
Si otro disco D contiene B , entonces .
Una forma de definir el esqueleto de una forma A es como el conjunto de centros de todos los discos máximos en A. [9]
Centros de circunferencias bitangentes
El esqueleto de una forma A también se puede definir como el conjunto de centros de los discos que tocan el límite de A en dos o más ubicaciones. [10] Esta definición asegura que los puntos del esqueleto sean equidistantes del límite de la forma y es matemáticamente equivalente a la transformada del eje medial de Blum.
Crestas de la función de distancia.
Muchas definiciones de esqueleto hacen uso del concepto de función de distancia , que es una función que devuelve para cada punto x dentro de una forma A su distancia al punto más cercano en el límite de A. Usar la función de distancia es muy atractivo porque su cálculo es relativamente rápido.
Una de las definiciones de esqueleto que utiliza la función de distancia es como las crestas de la función de distancia. [3] Hay una afirmación errónea común en la literatura de que el esqueleto consta de puntos que son "localmente máximos" en la transformada de distancia. Este simplemente no es el caso, como lo demostrará incluso una comparación superficial de una transformación de distancia y el esqueleto resultante. Las crestas pueden tener diferentes alturas, por lo que un punto de la cresta puede estar más bajo que su vecino inmediato en la cresta. Por tanto, no es un máximo local, aunque pertenece a la cresta. Sin embargo, está menos lejos verticalmente de lo que justificaría su distancia al suelo. De lo contrario sería parte del talud.
Otras definiciones
Puntos sin segmentos aguas arriba en la función de distancia. La corriente arriba de un punto x es el segmento que comienza en x y que sigue la trayectoria de gradiente máximo.
Puntos donde el gradiente de la función de distancia es diferente de 1 (o, equivalentemente, no está bien definido)
Conjunto de líneas más pequeño posible que preservan la topología y son equidistantes a los bordes.
Uso de intersecciones de distancias desde secciones de límites [12]
Usando la evolución de la curva [13] [14]
Usando conjuntos de niveles [5]
Encontrar puntos de cresta en la función de distancia [3]
"Pelar" la forma, sin cambiar la topología, hasta la convergencia [15]
Algoritmo de adelgazamiento de Zhang-Suen [16]
Los algoritmos de esqueletización a veces pueden crear ramas no deseadas en los esqueletos de salida. A menudo se utilizan algoritmos de poda para eliminar estas ramas.
^ ab Gonzales & Woods (2001), Sección 9.5.7, p. 543.
^ Abeysinghe y col. (2008).
^ Kimmel y col. (1995).
^ Tannenbaum (1996)
^ Bai, Longin y Wenyu (2007).
^ AK Jain (1989), sección 9.9, pág. 389.
^ Zhang, TY; Suen, CY (1 de marzo de 1984). "Un algoritmo paralelo rápido para adelgazar patrones digitales". Comunicaciones de la ACM . 27 (3): 236–239. doi :10.1145/357994.358023. ISSN 0001-0782. S2CID 39713481.
Referencias
Abeysinghe, Sasakthi; Panadero, Mateo; Chiu, Wah; Ju, Tao (2008), "Esqueletización sin segmentación de volúmenes en escala de grises para comprender la forma", IEEE Int. Conf. Aplicaciones y modelado de formas (SMI 2008) (PDF) , págs. 63–71, doi :10.1109/SMI.2008.4547951, ISBN 978-1-4244-2260-9, S2CID 15148296.
Abeysinghe, Sasakthi; Ju, Tao; Panadero, Mateo; Chiu, Wah (2008), "Modelado de formas y coincidencia en la identificación de estructuras de proteínas 3D" (PDF) , Diseño asistido por computadora , 40 (6), Elsevier: 708–720, doi :10.1016/j.cad.2008.01.013
Bai, Xiang; Longin, Latecki; Wenyu, Liu (2007), "Poda de esqueleto mediante partición de contornos con evolución de curva discreta" (PDF) , IEEE Transactions on Pattern Analysis and Machine Intelligence , 29 (3): 449–462, doi :10.1109/TPAMI.2007.59, PMID 17224615 , S2CID 14965041.
Blum, Harry (1967), "A Transformation for Extracting New Descriptors of Shape", en Wathen-Dunn, W. (ed.), Modelos para la percepción del habla y la forma visual (PDF) , Cambridge, Massachusetts: MIT Press, págs. 362–380.
Bucksch, Alexander (2014), "Una introducción práctica a los esqueletos para las ciencias vegetales", Aplicaciones en ciencias vegetales , 2 (8): 1400005, doi :10.3732/apps.1400005, PMC 4141713 , PMID 25202647.
Cychosz, Joseph (1994), Graphics gems IV, San Diego, CA, EE. UU.: Academic Press Professional, Inc., págs. 465–473, ISBN 0-12-336155-9.
Dougherty, Edward R. (1992), Introducción al procesamiento de imágenes morfológicas , ISBN 0-8194-0845-X.
Golland, Polina ; Grimson, W. Eric L. (2000), "Esqueletos de topología fija" (PDF) , Conferencia de 2000 sobre visión por computadora y reconocimiento de patrones (CVPR 2000), 13-15 de junio de 2000, Hilton Head, SC, EE. UU. , IEEE Computer Society, págs. 1010–1017, doi :10.1109/CVPR.2000.855792, S2CID 9916140
González, Rafael C.; Woods, Richard E. (2001), Procesamiento de imágenes digitales , ISBN 0-201-18075-8.
Jain, Anil K. (1989), Fundamentos del procesamiento de imágenes digitales , Bibcode : 1989fdip.book..... J, ISBN 0-13-336165-9.
Jainista, Ramesh; Kasturi, Rangachar; Schunck, Brian G. (1995), Visión artificial , ISBN 0-07-032018-7.
Kimmel, Ron; Sacudido, Doron; Kiryati, Nahum; Bruckstein, Alfred M. (1995), "Esqueleto mediante mapas de distancia y conjuntos de niveles" (PDF) , Visión por computadora y comprensión de imágenes , 62 (3): 382–391, doi :10.1006/cviu.1995.1062
Ogniewicz, RL (1995), "Poda automática del eje medial basada en las características del espacio-esqueleto", en Dori, D.; Bruckstein, A. (eds.), Reconocimiento de formas, estructuras y patrones , ISBN 981-02-2239-4.
Petrou, María; García Sevilla, Pedro (2006), Procesamiento de imágenes relacionado con la textura , ISBN 978-0-470-02628-1.
Serra, Jean (1982), Análisis de imágenes y morfología matemática , ISBN 0-12-637240-3.
Sethian, JA (1999), Métodos de fijación de niveles y métodos de marcha rápida , ISBN 0-521-64557-3.
Tannenbaum, Allen (1996), "Tres fragmentos de la teoría de la evolución de curvas en visión por computadora", Modelado matemático y por computadora , 24 (5): 103–118, doi : 10.1016/0895-7177(96)00117-3.
