Topologiskt skelett

En form och dess skelett, beräknad med en topologibevarande uttunningsalgoritm.

I formanalys är skelett (eller topologiskt skelett ) av en form en tunn version av den form som är lika långt till dess gränser . Skelettet betonar vanligtvis geometriska och topologiska egenskaper hos formen, såsom dess anslutning , topologi , längd , riktning och bredd . Tillsammans med avståndet mellan dess punkter till formgränsen kan skelettet också fungera som en representation av formen (de innehåller all information som behövs för att rekonstruera formen).

Skelett har flera olika matematiska definitioner i den tekniska litteraturen, och det finns många olika algoritmer för att beräkna dem. Olika olika varianter av skelett kan också hittas, inklusive raka skelett , morfologiska skelett , etc.

används begreppen skelett och mediala axel omväxlande av vissa författare, medan vissa andra författare betraktar dem som relaterade, men inte likadana. På liknande sätt betraktas begreppen skelettbildning och gallring också som identiska av vissa, och inte av andra.

Skelett används i stor utsträckning inom datorseende , bildanalys , mönsterigenkänning och digital bildbehandling för ändamål som optisk teckenigenkänning , fingeravtrycksigenkänning , visuell inspektion eller komprimering . Inom biovetenskapen hittade skelett omfattande användning för att karakterisera proteinveckning och växtmorfologi på olika biologiska skalor.

Matematiska definitioner

Skelett har flera olika matematiska definitioner i den tekniska litteraturen; de flesta av dem leder till liknande resultat i kontinuerliga utrymmen , men ger vanligtvis olika resultat i diskreta utrymmen .

Släckningspunkter för brandutbredningsmodellen

Harry Blum från flygvapnets Cambridge Research Laboratories vid Hanscom Air Force Base i Bedford, Massachusetts , definierade i sin framträdande artikel en medial axel för att beräkna ett skelett av en form, med hjälp av en intuitiv modell av eldutbredning på ett gräsfält, där fältet har formen av den givna formen. Om man "tänder eld" på alla punkter på gränsen till det gräsfältet samtidigt, är skelettet uppsättningen av släckningspunkter , dvs de punkter där två eller flera vågfronter möts. Denna intuitiva beskrivning är utgångspunkten för ett antal mer exakta definitioner.

Center för maximala skivor (eller bollar)

En skiva (eller boll ) B sägs vara maximal i en mängd A if

$B\subseteq A$ , och
Om en annan skiva D innehåller B , då $D\not \subseteq A$ .

Ett sätt att definiera skelettet för en form A är som uppsättningen av centra för alla maximala skivor i A .

Centrum för bi-tangenta cirklar

Skelettet av en form A kan också definieras som den uppsättning centra av skivorna som vidrör gränsen för A på två eller flera platser. Denna definition säkerställer att skelettpunkterna är lika långt från formgränsen och är matematiskt ekvivalent med Blums mediala axeltransform.

Åsar av distansfunktionen

Många definitioner av skelett använder sig av begreppet avståndsfunktion , som är en funktion som för varje punkt x inuti en form A returnerar sitt avstånd till den närmaste punkten på gränsen till A. Att använda avståndsfunktionen är mycket attraktivt eftersom dess beräkning är relativt snabb.

En av definitionerna av skelett som använder avståndsfunktionen är som åsarna för avståndsfunktionen. Det finns en vanlig missuppfattning i litteraturen att skelettet består av punkter som är "lokalt maximum" i avståndstransformen. Detta är helt enkelt inte fallet, vilket till och med översiktlig jämförelse av en avståndstransform och det resulterande skelettet kommer att visa. Åsar kan ha varierande höjd, så en punkt på åsen kan vara lägre än sin närmaste granne på åsen. Det är alltså inget lokalt maximum trots att det hör till åsen. Det är dock mindre långt bort vertikalt än dess markavstånd skulle motivera. Annars skulle det vara en del av backen.

Andra definitioner

Punkter utan uppströmssegment i distansfunktionen. Uppströms om en punkt x är det segment som börjar vid x som följer den maximala gradientbanan.
Punkter där gradienten för avståndsfunktionen skiljer sig från 1 (eller, på motsvarande sätt, inte väldefinierad)
Minsta möjliga uppsättning linjer som bevarar topologin och är lika långt från gränserna

Skelettiseringsalgoritmer

Det finns många olika algoritmer för att beräkna skelett för former i digitala bilder , såväl som kontinuerliga uppsättningar .

Använda morfologiska operatorer (Se Morfologiskt skelett )
Komplettera morfologiska operatorer med formbaserad beskärning
Använda korsningar av avstånd från gränssektioner
Använder kurvutveckling
Använda nivåuppsättningar
Hitta nockpunkter på distansfunktionen
"Peeling" av formen, utan att ändra topologin, tills konvergens
Zhang-Suen gallringsalgoritm

Skelettiseringsalgoritmer kan ibland skapa oönskade grenar på utgående skelett. Beskärningsalgoritmer används ofta för att ta bort dessa grenar.

Se även

Anteckningar

Abeysinghe, Sasakthi; Baker, Matthew; Chiu, Wah; Ju, Tao (2008), "Segmentationsfri skelettisering av gråskalevolymer för formförståelse", IEEE Int. Konf. Shape Modeling and Applications (SMI 2008) (PDF) , s. 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), "Shape modeling and matching in identifiing 3D protein structures" (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 partitioning with discrete curve evolution" (PDF) , IEEE Transactions on Pattern Analysis and Machine Intelligence , 29 ( 3 ) : 449–462, doi : 10.1109/TPAMI5.2007.2007.2007 . , S2CID 14965041 .
Blum, Harry (1967), "A Transformation for Extracting New Descriptors of Shape", i Wathen-Dunn, W. (red.), Models for the Perception of Speech and Visual Form (PDF) , Cambridge, Massachusetts: MIT Press, s. 362–380 .
Bucksch, Alexander (2014), "A practical introduction to skeletons for the plant sciences", Applications in Plant Sciences , 2 (8): 1400005, doi : 10.3732/apps.1400005 , PMC 4141713 , PMID 27202644 .
Cychosz, Joseph (1994), Graphics gems IV , San Diego, CA, USA: Academic Press Professional, Inc., s. 465–473 , ISBN 0-12-336155-9 .
Dougherty, Edward R. (1992), En introduktion till morfologisk bildbehandling , ISBN 0-8194-0845-X .
Golland, Polina ; Grimson, W. Eric L. (2000), "Fixed topology skeletons" (PDF) , 2000 Conference on Computer Vision and Pattern Recognition (CVPR 2000), 13-15 juni 2000, Hilton Head, SC, USA , IEEE Computer Society, s. 1010–1017, doi : 10.1109/CVPR.2000.855792 , S2CID 9916140
Gonzales, Rafael C.; Woods, Richard E. (2001), Digital bildbehandling , 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 .
Kimmel, Ron; Skakad, Doron; Kiryati, Nahum; Bruckstein, Alfred M. (1995), "Skeletonization via distance maps and level sets" (PDF) , Computer Vision and Image Understanding , 62 (3): 382–391, doi : 10.1006/cviu.1995.1062
Ogniewicz, RL (1995), "Automatisk beskärning av mediala axeln baserat på egenskaper hos skeleton-utrymmet", i Dori, D.; Bruckstein, A. (red.), Shape, Structure and Pattern Recognition , 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), 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 .

Programvara med öppen källkod

externa länkar