Usuari:Mcapdevila/Esquelet topològic
Per calcular els esquelets hi ha una classe d'algorismes utilitzats en l'anàlisi de les formes. Es tracta de reduir una forma en un conjunt de corbes, anomenades esquelets, centrades en la forma original. El càlcul de l'esquelet és una eina d'anàlisi no-escalar de formes, que conserva les propietats topològiques de la forma original així com les propietats geomètriques, segons el mètode utilitzat.
Definicions i propietats[modifica]
En termes simples, el càlcul de l'esquelet consisteix en aprimar una forma fins a obtenir un conjunt de corbes centrades. El conjunt resultant és llavors denominat esquelet o eix mig.
En la literatura tècnica, els conceptes esquelet i eix mitjà són utilitzats indistintament per alguns autors,[1][2][3][4][5] mentre que altres autors[6][7][8] els consideren relacionats, però que no són idèntics. De la mateixa manera, els conceptes càlcul de l'esquelet i aprimament també són considerats com a iguals per part d'alguns,[2] i no per altres.[6]
Hi ha diferents definicions per al càlcul de l'esquelet.
Analogia del foc a la prada[modifica]
La següent definició va ser enunciada per Harry Blum i es coneix com la analogia del foc a la prada. Ofereix una visió intuïtiva del càlcul de l'esquelet.
Sigui un prat coberta homogèniament per l'herba seca i Ω un conjunt de punts en aquesta praderia. Inicialment, tots els punts del contorn de Ω s'encenen simultàniament. El foc es propaga de manera uniforme i s'estén a través de la prada a una velocitat constant. El esquelet del conjunt de punts Ω (denotat MA (Ω)) es defineix com el lloc geomètric dels punts on els fronts de foc es reuneixen.
Definició formal[modifica]
Hi ha una definició formal de l'esquelet basada en el concepte de discos o boles màxims (maximals). L'esquelet d'una forma S, denotada MA (S), es defineix pel conjunt dels centres dels discos (boles) màxims (maximals) en S.
Esquelet ponderat[modifica]
L'esquelet ponderat o la transformació de l'eix mitjà d'una manera S, denotada MAT (S), és el conjunt de parells compostos del centre i radi dels discos (boles) màxims de S.
Exosquelet i endoesquelet[modifica]
Els esquelets no són només els objectes ubicats dins de les formes. Si reprenem l'analogia del foc a la prada, el procés de càlcul de l'esquelet no només transforma l'interior de la forma, sinó també l'exterior. Després, s'anomena endoesquelet a la part de l'esquelet que es troba dins de la forma i exosquelet a la part de l'esquelet que es troba fora de la forma.
Sovint la confusió es dóna entre esquelet i endoesquelet, ja que aquesta part de l'esquelet és la més estudiada en l'anàlisi de les formes. De la mateixa manera, en aquest article, considerem que els esquelets corresponen a endoesquelets.
Propietats dels esquelets[modifica]
Els esquelets tenen diverses propietats interessants:
- Els esquelets són teòricament invariants sota les transformacions lineals (translació, rotació i canvi d'escala),
- El càlcul d'un esquelet és una transformació homotòpica: conserva les propietats topològiques de la forma.
Altres propietats són específiques dels esquelets ponderats:
- Tots els esquelets ponderats són únics,
- En el cas dels esquelets ponderats, el càlcul de l'esquelet és una transformació reversible en el sentit que és possible reconstruir la forma original a partir de l'esquelet ponderat,
- Un esquelet ponderat proporciona una descripció jeràrquica de la forma: els punts de l'esquelet allunyats del contorn descriuen l'aparença general de la forma i els punts de l'esquelet més propers al contorn descriuen les particularitats que apareixen en aquest.
Una altra propietat dels esquelets es considera, en general, un defecte: el càlcul de l'esquelet és una transformació semi-contínua. En efecte, la més mínima alteració en el contorn oa l'interior de la forma pot produir la creació d'una branca important en l'esquelet.
Mètodes per calcular els esquelets[modifica]
Hi ha una gran varietat de mètodes per construir els esquelets a partir de les formes. En la majoria de les publicacions científiques, els mètodes de càlcul dels esquelets es poden classificar en quatre classes.
Aprimament topològic[modifica]
El aprimament topològic consisteix a retirar "en la seva justa mesura" els punts del contorn de la forma, preservant les seves característiques topològiques. Els punts de l'esquelet són afegits quan es forma una cantonada (la corba del contorn es fa discontínua) o quan els punts del contorn es reuneixen.
Extracció del Mapa de distància[modifica]
El Mapa de distància d'una forma S consisteix a associar a cada punt de S seva distància al punt més proper del contorn.
Una de les definicions de l'esquelet mitjançant la funció de la distància és com les 'crestes' (aquells punts en què la funció distància disminueix a banda i banda) de la funció de la distància.[6] Hi ha un malentès en la literatura que l'esquelet consisteix dels punts que són "màxims locals" en la transformació de distància. Això no és cert com tot[Cal aclariment] una ràpida comparació d'una transformació de distància i l'esquelet resultant pot mostrar.
Simulació del front de foc[modifica]
Els mètodes que treballen mitjançant la simulació del front de foc es basen en l'analogia del foc a la prada. Ells estudien l'evolució del front de foc a través del temps. Cada formació de xoc al front s'agrega a l'esquelet.
Càlcul analític[modifica]
La recerca del esquelet està relacionat amb un problema geomètric. Els mètodes d'aquesta classe fan servir eines geomètriques, com ara el diagrama de Voronoi o la poligonització de les corbes de nivell (en el cas del càlcul de l'esquelet en els espais discrets).
Altres criteris de classificació[modifica]
Els mètodes de càlcul de l'esquelet es poden classificar segons el tipus d'espai al qual s'apliquen. Alguns mètodes de càlcul de l'esquelet s'apliquen a espais continus. Aquests mètodes són generalment exactes i precisos. Altres mètodes de càlcul de l'esquelet s'apliquen a espais discrets. Aquests mètodes són necessaris només en alguns casos i requereixen sovint d'una seqüència d'operacions per afinar l'esquelet.
Alguns mètodes de càlcul de l'esquelet s'apliquen a formes en un pla o objectes tridimensionals i més.
Aplicacions[modifica]
El càlcul d'esquelets té moltes aplicacions, com ara el reconeixement de patrons, el modelatge de sòlids per al disseny i la manipulació de formes, l'organització de la dispersió (núvols de punts), la recerca de camins, animacions, etc. S'utilitza en la medicina i la biologia des dels seus inicis, així com en mineralogia. S'han trobat aplicacions en la indexació d'imatges en les bases de dades i en compressió. Només cal unes poques aplicacions en l'arquitectura i l'urbanisme, en el context de l'anàlisi morfològica.
Els investigadors han demostrat que, en el procés de la percepció visual, la nostra sensibilitat inconscient és màxima en l'esquelet.
Orígens[modifica]
El càlcul d'esquelets és un mètode que va ser desenvolupat originalment en els anys seixanta per Harry Blum, per crear un nou descriptor de formes. Aquest mètode ha guanyat l'interès de molts investigadors. En l'actualitat, el càlcul d'esquelets és un mètode ben conegut en l'anàlisi d'imatges. Hi ha molts algorismes proposats per transformar una forma en esquelet.
Referències[modifica]
- ↑ Jain, Ramesh; Kasturi, Rangachar & Schunck, Brian G. (1995), Machine Vision, ISBN 0-07-032018-7, Section 2.5.10, p. 55.
- ↑ 2,0 2,1 Gonzales, Rafael C. & Woods, Richard E. (2001), Digital Image Processing, ISBN 0-201-18075-8, Section 11.1.5, p. 650
- ↑ http://people.csail.mit.edu/polina/papers/skeletons_cvpr00.pdf
- ↑ Dougherty, Edward R. (1992), An Introduction to Morphological Image Processing, ISBN 0-8194-0845-X
- ↑ Ogniewicz, R. L. (1995), Dori, D. & Bruckstein, A., eds., Shape, Structure and Pattern Recognition, ISBN 981-02-2239-4
- ↑ 6,0 6,1 6,2 Jain, Anil K. Fundamentals of Digital Image Processing, 1989. ISBN 0-13-336165-9.., Section 9.9, p. 382.
- ↑ Serra, Jean (1982), Image Analysis and Mathematical Morphology, ISBN 0126372403
- ↑ Sethian, J. A. (1999), Level Set Methods and Fast Marching Methods, ISBN 0-521-64557-3, Section 17.5.2, p. 234.
Bibliografia[modifica]
- Dominique Attali. squelettes et graphes de Voronoi 2D et 3D. These de doctorat, Université Joseph Fourier - Grenoble I, octobre 1995.
- Harry Blum. A transformation for extracting new descriptors of shape. In Wathen Dunn, editor, Proceedings of Models for the Perception of Speech and Visual Form, pages 362-380. MIT Press, 1967.
- Frédéric Fol-Leymarie. Three-dimensional shape representation via schock flows. PhD thesis, Brown University, Providence, Rhode Island, USA, May 2003. 209 p.
- Benjamin B. Kimia. On the role of medial geometry in human vision. Journal of Physiology, 97 (2-3) :155-190, March-maig 2003.
- Sven Loncaric. A survey of shape analysis techniques. Pattern Recognition, 31 (8) :983-1001, 1998.