Fuzzy-Skelettierung

Die Fuzzy-Skelettierung ist ein Erosions-Verfahren (als Weiterentwicklung der Steppenfeuer-Verfahren) zur Skelettierung von Bildern. Der Vordergrund wird nicht „abgebrannt“ (Steppenfeuer) sondern „abgebröckelt“ (Erosion).

Inhaltsverzeichnis

Algorithmus

Die Fuzzy-Skelettierung berechnet für jeden Bildpunkt (Pixel) $P$ einen Wert $P_{H}$, über den sich der Abstand des Pixels vom Rand der Linie/Fläche bestimmen lässt. Dieser Wert liegt innerhalb eines Intervalls von min bis max. Die Punkte aus der Hintergrundmenge erhalten z.B. den Wert min = 0 und die aus der Vordergrundmenge max = 2047. Bei Schwarz-Weiß-Bildern sind Hintergrund und Vordergrund leicht zu definieren, bei Grauwert- und Farbbildern muss zunächst eine Fuzzy-Funktion zur Bestimmung des relativen Hintergrundes definiert werden.

Dann werden für festgelegte Umgebungen eines Vordergrund-Punktes für alle Punkte, die im Hintergrund liegen oder nicht mehr den Maximalwert besitzen, fest vorgegebene Werte von $P_{H}$ subtrahiert. Für Hintergrundpixel (nur in Schwarz-Weiß-Bildern) werden die Werte entsprechend addiert.

Umgebungen

Sinnvolle Umgebungen und Werte sind z.B.

D	N	D
N	P	N
D	N	D

Um den Randabstand exakt aus dem Wert berechnen zu können, muss folgende Bedingung erfüllt sein:

$2W(D)+2W(N)+W(P)>4W(D)+4W(N)$, also

$W(P)>2W(D)+2W(N)$

---

$W(D)=W(N)=W(P)=1$

1	1	1
1	1	1
1	1	1

Da $1<=4$ ist die Bedingung hier leider nicht erfüllt. Daher kann der Randabstand nur auf 2 Pixel genau ermittelt werden, d.h. es gibt eine Ungenauigkeit von 1 Pixel in einigen Fällen. Siehe nächste Variante.

---

$W(D)=W(N)=1,W(P)=5$

1	1	1
1	5	1
1	1	1

Da $5>4$ ist die Bedingung erfüllt.

---

$W(D)=1$, $W(N)=2$, $W(P)=7$

1	2	1
2	7	2
1	2	1

Mit $7>=6$ ist die Bedingung erfüllt.

---

$W(D)=2$, $W(N)=3$, $W(P)=11$

2	3	2
3	11	3
2	3	2

Mit $11>=10$ ist die Bedingung ebenfalls erfüllt.

Eigenschaften

Im Folgenden zu beweisen:

1. aus dem Wert des Pixels lässt sich direkt der Abstand zum Rand ermitteln, wenn die Werte der Umgebung passend gewählt werden.
2. das Originalbild ist im Ergebnis enthalten
3. das Originalbild ist aus den Skelettpunkten mit vernachlässigbaren Verlusten rekonstruierbar (weniger Verluste als bei JPG)
4. verschiedene Liniendicken/Zeichengrößen können unterschieden werden
5. dadurch ist Extraktion von Überschriften bereits in diesem Schritt möglich
6. übereinander liegende Linien verschiedener Dicke können getrennt werden
7. Stabilität bezüglich Aufwand und Ergebnis gegenüber zerklüfteten Rändern

Weitere Eigenschaften

• einfacher Algorithmus, daher
• direkt durch Hardware (z.B. zusätzliche Layer im Foto-Chip) realisierbar,
• wodurch erstmals Echtzeitfähigkeit erreicht wird.
• eine Parallelisierung, z.B. auf Grafikkarten, ist ebenfalls möglich.

Beweis

noch nicht beschrieben, aber er existiert.

Literatur

• Hamid R. Tizhoosh: Fuzzy-Bildverarbeitung: Einführung in Theorie und Praxis. 1997, S. 212 ff. (eingeschränkte Vorschau in der Google-Buchsuche [abgerufen am 27. Dezember 2014]). 

Weblinks

• [1]: Patentschrift zum Download als PDF
• Patent DE000019738230A1: Fuzzy-Skelettierung, ein Verfahren zur Skelettierung von Bildern. Angemeldet am 2. September 1997, veröffentlicht am 2. April 1998, Anmelder: Ralf Peine, Erfinder: Ralf Peine.‌
• http://www.jupiter-programs.de/prj_public/fsk/fuzzysk.htm Übersicht

Dieser Wikipedia-Artikel wurde, gemäß GFDL, CC-by-sa mit der kompletten History importiert.