Esqueleto topológico - Topological skeleton

Uma forma e seu esqueleto, calculados com um algoritmo de afinamento que preserva a topologia.

Na análise de formas , o esqueleto (ou esqueleto topológico ) de uma forma é uma versão fina dessa forma equidistante de seus limites . O esqueleto geralmente enfatiza as propriedades geométricas e topológicas da forma, como sua conectividade , topologia , comprimento , direção e largura . Juntamente com a distância de seus pontos ao limite da forma, o esqueleto também pode servir como uma representação da forma (eles contêm todas as informações necessárias para reconstruir a forma).

Esqueletos têm várias definições matemáticas diferentes na literatura técnica e existem muitos algoritmos diferentes para computá-los. Várias variantes diferentes de esqueleto também podem ser encontradas, incluindo esqueletos retos , esqueletos morfológicos , etc.

Na literatura técnica, os conceitos de esqueleto e eixo medial são usados indistintamente por alguns autores, enquanto outros os consideram relacionados, mas não iguais. Da mesma forma, os conceitos de esqueletização e desbaste também são considerados idênticos por alguns, e não por outros.

Esqueletos são amplamente usados em visão computacional , análise de imagens , reconhecimento de padrões e processamento digital de imagens para propósitos como reconhecimento óptico de caracteres , reconhecimento de impressões digitais , inspeção visual ou compressão . Dentro das ciências biológicas, os esqueletos encontraram amplo uso para caracterizar o dobramento de proteínas e a morfologia da planta em várias escalas biológicas.

Definições matemáticas

Esqueletos têm várias definições matemáticas diferentes na literatura técnica; a maioria deles leva a resultados semelhantes em espaços contínuos , mas geralmente produzem resultados diferentes em espaços discretos .

Pontos de têmpera do modelo de propagação de fogo

Em seu artigo original, Harry Blum dos Laboratórios de Pesquisa da Força Aérea de Cambridge na Base da Força Aérea Hanscom , em Bedford, Massachusetts , definiu um eixo medial para calcular um esqueleto de uma forma, usando um modelo intuitivo de propagação de fogo em um campo gramado, onde o campo tem a forma dada. Se alguém "atear fogo" em todos os pontos do limite daquele campo de grama simultaneamente, o esqueleto é o conjunto de pontos de resfriamento , ou seja, aqueles pontos onde duas ou mais frentes de onda se encontram. Esta descrição intuitiva é o ponto de partida para várias definições mais precisas.

Centros de discos máximos (ou bolas)

Um disco (ou bola ) B é considerado máximo em um conjunto A se

${\ displaystyle B \ subseteq A}$ , e
Se outro disco D contiver B , então . ${\ displaystyle D \ not \ subseteq A}$

Uma maneira de definir o esqueleto de uma forma A é como o conjunto de todos os discos de centros máximas na Uma .

Centros de círculos bi-tangentes

O esqueleto de uma forma A também pode ser definido como o conjunto de centros dos discos que tocam o limite de A em dois ou mais locais. Esta definição garante que os pontos do esqueleto sejam equidistantes do contorno da forma e sejam matematicamente equivalentes à transformação do eixo medial de Blum.

Cumes da função distância

Muitas definições de fazer uso esqueleto do conceito de função de distância , que é uma função que retorna para cada ponto x dentro de uma forma A sua distância ao ponto mais próximo do limite da A . Usar a função de distância é muito atraente porque seu cálculo é relativamente rápido.

Uma das definições de esqueleto usando a função de distância é como as cristas da função de distância. Existe um erro comum na literatura de que o esqueleto consiste em pontos que são "localmente máximos" na transformada de distância. Isso simplesmente não é o caso, pois até mesmo uma comparação superficial de uma transformação de distância e o esqueleto resultante irá mostrar. As cristas podem ter alturas variáveis, portanto, um ponto na crista pode ser mais baixo do que seu vizinho imediato na crista. Portanto, não é um máximo local, embora pertença ao cume. É, no entanto, menos afastado verticalmente do que sua distância do solo justificaria. Caso contrário, seria parte da inclinação.

Outras definições

Pontos sem segmentos a montante na função de distância. A montante de um ponto x é o segmento começando em x que segue o caminho do gradiente máximo.
Pontos onde o gradiente da função de distância é diferente de 1 (ou, equivalentemente, não está bem definido)
O menor conjunto possível de linhas que preservam a topologia e são equidistantes das bordas

Algoritmos de esqueletização

Existem muitos algoritmos diferentes para calcular esqueletos para formas em imagens digitais , bem como conjuntos contínuos .

Usando operadores morfológicos (ver esqueleto morfológico )
Suplementando operadores morfológicos com poda baseada em forma
Usando interseções de distâncias de seções de limite
Usando a evolução da curva
Usando conjuntos de níveis
Encontrar pontos de crista na função de distância
"Descascando" a forma, sem alterar a topologia, até a convergência

Algoritmos de esqueletização às vezes podem criar ramificações indesejadas nos esqueletos de saída. Os algoritmos de poda são freqüentemente usados para remover esses ramos.

Veja também

Notas

Referências

Abeysinghe, Sasakthi; Baker, Matthew; Chiu, Wah; Ju, Tao (2008), "Esqueletização livre de segmentação de volumes em tons de cinza para compreensão de formas", IEEE Int. Conf. Shape Modeling and Applications (SMI 2008) (PDF) , pp. 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), "Modelagem de forma e correspondência na identificação de estruturas de proteínas 3D" (PDF) , Computer-Aided Design , Elsevier, 40 (6): 708–720, doi : 10.1016 / j.cad.2008.01.013
Bai, Xiang; Longin, Latecki; Wenyu, Liu (2007), "Skeleton pruning by contour particioning with discrete curve evolution" (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", em Wathen-Dunn, W. (ed.), Models for the Perception of Speech and Visual Form (PDF) , Cambridge, Massachusetts: MIT Press, pp. 362-380.
Bucksch, Alexander (2014), "Uma introdução prática aos esqueletos para as ciências das plantas", Applications in Plant Sciences , 2 (8): 1400005, doi : 10.3732 / apps.1400005 , PMC 4141713 , PMID 25202647.
Cychosz, Joseph (1994), Graphics gems IV , San Diego, CA, EUA: Academic Press Professional, Inc., pp. 465-473 , ISBN 0-12-336155-9.
Dougherty, Edward R. (1992), An Introduction to Morphological Image Processing , ISBN 0-8194-0845-X.
Gonzales, Rafael C .; Woods, Richard E. (2001), Digital Image Processing , ISBN 0-201-18075-8.
Jain, Anil K. (1989), Fundamentals of Digital Image Processing , Bibcode : 1989fdip.book ..... J , ISBN 0-13-336165-9.
Jain, Ramesh; Kasturi, Rangachar; Schunck, Brian G. (1995), Machine Vision , ISBN 0-07-032018-7.
Ogniewicz, RL (1995), "Automatic Medial Axis Pruning Based on Characteristics of the Skeleton-Space", in Dori, D .; Bruckstein, A. (eds.), Shape, Structure and Pattern Recognition , ISBN 981-02-2239-4.
Petrou, Maria; García Sevilla, Pedro (2006), Processamento de Imagens Lidando com Textura , ISBN 978-0-470-02628-1.
Serra, Jean (1982), Image Analysis and Mathematical Morphology , ISBN 0-12-637240-3.
Sethian, JA (1999), Level Set Methods and Fast Marching Methods , ISBN 0-521-64557-3.
Tannenbaum, Allen (1996), "Three snippets of curve evolution theory in computer vision", Mathematical and Computer Modeling , 24 (5): 103-118, doi : 10.1016 / 0895-7177 (96) 00117-3.

Languages

In other projects