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 una 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 varias variantes diferentes de esqueleto, incluidos esqueletos rectos , esqueletos morfológicos , etc.
En la literatura técnica, algunos autores utilizan los conceptos de esqueleto y eje medial de forma indistinta, [1] [2] mientras que otros autores [3] [4] [5] los consideran relacionados, pero no iguales. De manera similar, algunos autores también consideran idénticos los conceptos de esqueletización y adelgazamiento [2] , mientras que otros no. [3]
Los esqueletos tienen varias definiciones matemáticas diferentes en la literatura técnica; la mayoría de ellas conducen a resultados similares en espacios continuos , pero generalmente producen resultados diferentes en espacios discretos .
Puntos de extinción del modelo de propagación del fuego
En su artículo seminal, Harry Blum [8] de los Laboratorios de Investigación de la Fuerza Aérea de Cambridge en la Base Aérea Hanscom , en Bedford, Massachusetts , definió un eje medial para calcular un esqueleto de una forma, utilizando un modelo intuitivo de propagación del fuego en un campo de hierba, donde el campo tiene la forma de la forma dada. Si uno "prende fuego" en todos los puntos del límite de ese campo de hierba simultáneamente, 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 (o bolas) máximos
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 círculos 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 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. El uso de 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 la de las crestas de la función de distancia. [3] En la literatura se suele afirmar erróneamente que el esqueleto está formado por puntos que son "máximos localmente" en la transformación de distancia. Esto simplemente no es así, como lo demuestra incluso una comparación superficial de una transformación de distancia y el esqueleto resultante. Las crestas pueden tener una altura variable, por lo que un punto de la cresta puede estar más bajo que su vecino inmediato en la cresta. Por lo tanto, no es un máximo local, aunque pertenece a la cresta. Sin embargo, está menos alejado verticalmente de lo que justificaría su distancia al suelo. De lo contrario, sería parte de la pendiente.
Otras definiciones
Puntos sin segmentos ascendentes en la función de distancia. El ascendente de un punto x es el segmento que comienza en x y 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 más pequeño posible de líneas que preservan la topología y son equidistantes a los bordes.
Utilizando intersecciones de distancias desde secciones limítrofes [12]
Utilizando la evolución de curvas [13] [14]
Uso de 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. Los algoritmos de poda se utilizan a menudo para eliminar estas ramas.
^ ab Gonzales & Woods (2001), Sección 9.5.7, pág. 543.
^ Abeysinghe y otros (2008).
^ Kimmel y otros (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; Baker, Matthew; Chiu, Wah; Ju, Tao (2008), "Esqueletización sin segmentación de volúmenes en escala de grises para la comprensión de formas", IEEE Int. Conf. Modelado de formas y aplicaciones (SMI 2008) (PDF) , págs. 63–71, doi :10.1109/SMI.2008.4547951, ISBN 978-1-4244-2260-9, Número de identificación del sujeto 15148296.
Abeysinghe, Sasakthi; Ju, Tao; Baker, Matthew; Chiu, Wah (2008), "Modelado y correspondencia de formas para identificar estructuras proteínicas en 3D" (PDF) , Computer-Aided Design , 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 contorno 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), "Una transformación para extraer nuevos descriptores de la forma", 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), "Fixed topology skeletons" (PDF) , Conferencia de 2000 sobre visión artificial 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
Gonzales, 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 03-07-2018-7.
Kimmel, Ron; Shaked, Doron; Kiryati, Nahum; Bruckstein, Alfred M. (1995), "Esqueletización mediante mapas de distancias y conjuntos de niveles" (PDF) , Computer Vision and Image Understanding , 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 esquelético", en Dori, D.; Bruckstein, A. (eds.), Forma, estructura y reconocimiento de 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 nivelación 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 la visión por computadora", Mathematical and Computer Modelling , 24 (5): 103–118, doi : 10.1016/0895-7177(96)00117-3.
