Skelettierung (Bildverarbeitung)

Ein Bildobjekt mit Skelettlinie

Als Skelettierung wird eine Klasse von Verfahren der Bildverarbeitung bezeichnet. Bei der Skelettierung wird ein flächenhaftes Bildobjekt in eine 1 Bildpunkt breite, innere Skelettlinie umgewandelt.

Die Skelettierung wird beispielsweise eingesetzt, um Linien zu verdünnen. Die verdünnten Linien lassen sich gut vektorisieren. Auch kann ein Skelett zur Datenreduktion eingesetzt werden. Weitere Anwendungen finden sich unter anderem in der Medizin, Biologie, Schrift-, Muster- und Fingerabdruckerkennung.

Definition

Es existieren mehrere verschiedene Definitionen für das Skelett einer Bildregion. Eine der ersten stammt von H. Blum (1967). Als Anschauung wählte Blum ein Steppenfeuer. Eine trockene Steppengrasfläche, die eine Bildregion repräsentiert, wird an ihren Grenzen gleichzeitig angezündet, so dass das Feuer sich gleichmäßig nach Innen ausbreitet. Das Skelett besteht nun aus jenen Stellen, an denen mindestens zwei Brandfronten aufeinandertreffen. Diese Definition lässt sich formalisieren:

Sei $D(x,y)$ eine Distanzfunktion, die den Abstand eines inneren Punktes $(x,y)$ zu dem naheliegendsten Randpunkt angibt. Das Skelett bzw. die Mittelachse ist nun definiert durch die Menge der inneren Punkte $p$, für die $D(p)$ ein lokales Maximum in einer bestimmten Richtung ist, z.B. der X- / Y-Achse oder einer der beiden Diagonalen XY und -XY.

Die Punkte, die das Skelett bilden, werden auch als Skelettpunkte oder Skelettpixel bezeichnet.

Skelettierungs-Algorithmen

Es gibt verschiedene Algorithmen, um Skelette zu berechnen.

• "Steppenfeuer"-Definition: Berechnung der Distanzfunktionen $D$ und der lokalen Maxima
  • "Erosionsverfahren" als Weiterentwicklung der Steppenfeuer-Definition, z.B. Fuzzy-Skelettierung
• Thinning/Verdünnungs-Verfahren: Randpixel werden solange entfernt, bis keine weitere Verdünnung mehr möglich ist. Ein Beispiel hierfür ist der einfache, parallelisierbare Zhang-Suen Algorithmus. Siehe auch Mathematische Morphologie
• Voronoi-Diagramm

Weblinks

• P. Golland and W.E.L. Grimson. Fixed Topology Skeletons. In Proceedings of CVPR: IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 10-17, 2000. (PDF-Datei; 437 kB)
• Christoph Bullmann. Vergleich und Anwendungen von Skelettierungsalgorithmen in der digitalen Bildverarbeitung. HTWK Leipzig, 2008 (PDF-Datei; 7,7 MB)
• http://users.informatik.haw-hamburg.de/~ubicomp/projekte/master06-07/gruendel/report.pdf (PDF-Datei; 358 kB)
• http://homepages.inf.ed.ac.uk/rbf/HIPR2/skeleton.htm
• http://www.cosc.canterbury.ac.nz/mukundan/covn/Thin.html - Java-Applet, Darstellung eines Thinning-Algorithmus