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 indistintamente los conceptos de esqueleto y eje medial , [1] [2] [3] [4] [5] mientras que otros autores [6] [7] [8] los consideran como relacionados, pero no lo mismo. De manera similar, los conceptos de esqueletización y adelgazamiento también son considerados idénticos por algunos, [2] y no por otros. [6]
Los esqueletos se utilizan ampliamente en visión por computadora , análisis de imágenes , reconocimiento de patrones y procesamiento de imágenes digitales para fines tales como reconocimiento óptico de caracteres , reconocimiento de huellas dactilares , inspección visual o compresión . Dentro de las ciencias de la vida, los esqueletos encontraron un uso extenso para caracterizar el plegamiento de proteínas [9] y la morfología de las plantas en varias escalas biológicas. [10]
Definiciones matemáticas
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 generalmente dan resultados diferentes en espacios discretos .
Puntos de extinción del modelo de propagación del fuego
En su artículo seminal, Harry Blum [11] 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 en una hierba. campo, donde el campo tiene la forma de la forma dada. Si uno "prende fuego" en todos los puntos en el 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 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 manera de definir el esqueleto de una forma A es como el conjunto de centros de todos los discos máximas en A . [12]
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. [13] Esta definición asegura que los puntos del esqueleto son equidistantes del límite de la forma y es matemáticamente equivalente a la transformación del eje medial de Blum.
Crestas de la función de distancia
Muchas de las definiciones de uso hacen esqueleto 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 como las crestas de la función de distancia. [6] Hay una declaración errónea común en la literatura de que el esqueleto consiste en puntos que son "localmente máximos" en la transformación de distancia. Este simplemente no es el caso, como se mostrará 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 en la cresta puede ser 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 de la pendiente.
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 del gradiente máximo.
- Puntos donde el gradiente de la función de distancia es diferente de 1 (o, de manera equivalente, no está bien definido)
- El conjunto de líneas más pequeño posible que conservan la topología y son equidistantes a los bordes.
Algoritmos de esqueletización
Existen muchos algoritmos diferentes para calcular esqueletos de formas en imágenes digitales , así como conjuntos continuos .
- Usando operadores morfológicos (Ver Esqueleto morfológico [13] )
- Complementar los operadores morfológicos con podas basadas en formas [14]
- Uso de intersecciones de distancias desde secciones de límites [15]
- Utilizando la evolución de la curva [16] [17]
- Usando conjuntos de niveles [8]
- Encontrar puntos de cresta en la función de distancia [6]
- "Pelar" la forma, sin cambiar la topología, hasta la convergencia [18]
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.
Ver también
- Eje medial
- Esqueleto recto
- β-esqueleto
- Transformación Grassfire
- Fuentes basadas en trazos
Notas
- ^ Jain, Kasturi y Schunck (1995) , Sección 2.5.10, p. 55.
- ↑ a b Gonzales & Woods (2001) , Sección 11.1.5, p. 650
- ^ http://people.csail.mit.edu/polina/papers/skeletons_cvpr00.pdf
- ^ Dougherty (1992) .
- ^ Ogniewicz (1995) .
- ↑ a b c d A. K. Jain ( 1989 ), Sección 9.9, p. 382.
- ^ Serra (1982) .
- ↑ a b Sethian (1999) , Sección 17.5.2, p. 234.
- ^ Abeysinghe y col. (2008)
- ^ Bucksch (2014)
- ^ Harry Blum ( 1967 )
- ^ AK Jain ( 1989 ), sección 9.9, p. 387.
- ↑ a b Gonzales & Woods (2001) , Sección 9.5.7, p. 543.
- ^ Abeysinghe y col. (2008) .
- ^ R. Kimmel, D. Shaked, N. Kiryati y AM Bruckstein. https://www.cs.technion.ac.il/~ron/PAPERS/skeletonization_CVIU_1995.pdf Comp. Comprensión de la visión y la imagen, 62 (3): 382-391, 1995.
- ^ Tannenbaum (1996)
- ^ Bai, Longin y Wenyu (2007) .
- ^ AK Jain ( 1989 ), sección 9.9, p. 389.
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 y aplicaciones 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; Baker, Matthew; Chiu, Wah (2008), "Modelado y emparejamiento de formas en la identificación de estructuras de proteínas 3D" (PDF) , Diseño asistido por computadora , Elsevier, 40 (6): 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), "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 de las plantas", Aplicaciones en ciencias de las plantas , 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.
- 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.
- Jain, Ramesh; Kasturi, Rangachar; Schunck, Brian G. (1995), Visión artificial , ISBN 0-07-032018-7.
- Ogniewicz, RL (1995), "Poda automática del eje medial basada en las características del espacio esquelético", en Dori, D .; Bruckstein, A. (eds.), Reconocimiento de formas, estructuras y patrones , ISBN 981-02-2239-4.
- Petrou, Maria; García Sevilla, Pedro (2006), Image Processing Dealing with Texture , 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 conjunto 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 la curva en la visión por computadora", Modelado matemático y por computadora , 24 (5): 103-118, doi : 10.1016 / 0895-7177 (96) 00117-3 CS1 maint: parámetro desalentado ( enlace ).
Software de código abierto
- ITK (C ++)
- Skeletonize3D (Java)
- Gemas gráficas IV (C)
- EVG-Thin (C ++)
enlaces externos
- Esqueletización / Transformación del eje medial
- Esqueletos de una región
- Esqueletos en el procesamiento de imágenes digitales (pdf)
- Comparación de 15 algoritmos de adelgazamiento de líneas
- Esqueletización mediante métodos de conjunto de niveles
- Esqueletos de curvas
- Esqueletos de nubes de puntos escaneadas con láser (página de inicio)