Inhalt
KurzbeschreibungEinsatzmöglichkeiten
Realisierungsmöglichkeiten
Patent-IDs
Erfinder
Kontakt
English Version
Fuzzy Skelettierung (patentiert) |
InhaltKurzbeschreibungEinsatzmöglichkeiten Realisierungsmöglichkeiten Patent-IDs Erfinder Kontakt |
English Version
|
Fuzzy-Skelettierung ist ein neuartiges, patentiertes Verfahren im Bereich der Bildverarbeitung. Skelettierungsverfahren werden benötigt, wenn aus Pixelgrafiken linienhafte Strukturen extrahiert werden sollen. Solche Grafiken entstehen z.B. durch das Einscannen von technischen Zeichnungen, Schriftstücken, durch Aufnahmen elektronischer Kameras o. ä.. Die durch die Skelettierung gewonnenen Linienfragmente werden dann durch einen Vektorisierer in ein für den Computer nutzbares Format umgewandelt und können anschließend von einem Schrifterkennungs-, CAD- oder Archivierungsprogramm eingelesen und weiterverarbeitet werden.
Die Fuzzy Skelettierung extrahiert das Skelett eines digitalen Bildes (schwarz/weiß, grauwertig oder farbig). Der Algoritmus generiert für jedes Vordergrundpixel (grau markiert in der ersten Abbildung) so etwas wie einen Abstandswert zum Rand des Bildvordergrundes. Wie in der 3D-Ansicht (Abb. 2) zu erkennen, ist das Skelett eine Teilmenge der Grate und lokalen Maxima des erzeugten "Gebirges". Abbildung 3 zeigt die Grate für die Richtungen (x, y, xy, -xy) und die lokalen Maxima (fett umrandet). Man kann sich die Striche als Knick eines halb gefalteten Blattes vorstellen. In Richtung des Knicks ist die Höhe identisch, rechts und links vom Knick kleiner. Das Skelett kann nun bestimmt werden durch die Verbindungen der Gipfel: Man muss nur den Strichen (Graten) folgen (Das Prinzip ist dasselbe wie bei einer Höhenwanderung im Gebirge). Die Größe des Rechtecks wird durch den Abstandswert zum Rand bestimmt und lässt die direkte Berechnung des größten Quadrates zu, das noch in den Vordergrund passt und in dessen Mittelpunkt das untersuchte Pixel (Bildpunkt) liegt. Siehe Abbildung 3: Um das linke untere Maximum passt ein 4*4 Pixel großes Quadrat und rechts unten ein 5*5 Pixel großes, weshalb das rechts dargestellte Quadrat etwas größer ist als das linke.
Die Funktionsfähigkeit des Algorithmus zur Fuzzy-Skelettierung sowie seine Eingenschaften sind mathematisch bewiesen.
Das neue Verfahren bietet gegenüber dem aktuellen Stand der Technik folgende Vorteile:
Eine genauere Beschreibung findet sich in der Patentschrift und in der Demo-Software, die auf Wunsch bei dem Erfinder ebenso wie die mathematischen Beweise eingesehen werden können.
Hinweis: Die Erfindung realisiert natürlich nur den ersten Schritt - die Skelettierung des Pixelbildes.
Durch den äußerst einfachen Algorithmus ist die Realisierung als IC-Transistorschaltung leicht möglich: Das Prinzip der Schaltung liegt vor. Dadurch kann die Fuzzy-Skelettierung direkt in der Aufnahmeeinheit durchgeführt werden und benötigt in diesem Fall weniger als 1/100 Millisekunde pro Bild. Die Auflösung des Bildes sowie die Anzahl der Bildpunkte werden allein durch die Aufnahmeeinheit festgelegt. Die Aufnahmeeinheit (Scanner, Kopierer, Kamera, Roboterauge) liefert dann nicht mehr das Originalbild, sondern direkt das Fuzzy-Skelett für die weitere Verarbeitung. Dies ist in der Bildverarbeitung bisher unerreicht!
Die Herstellungskosten für einen solchen IC dürften sich auf demselben Preisniveau bewegen wie die für vergleichbare Speicher-ROMs.
Eine Implementierung des Algorithmus als reine Softwarelösung ist inzwischen ebenfalls möglich und als Library für C++ (reine Rechenfunktionalität) verfügbar. Sie benötigt z.B. für ein 1000 * 1000 Pixel großes Bild auf einem Laptop mit AMD Turion Prozessor (800MHz) einige Sekunden für 10 Iterationen.
Eine zweite Realisierungsmöglichkeit ist die Implementierung auf einer oder mehrerer Grafikkarten. Bei Taktraten im Giga-Hertz-Bereich ist auch für eine A0 (!) Zeichnung in weniger als einer Minute das Fuzzy-Skelett vollständig berechnet. (Falls die Daten entsprechend schnell gelesen und geschrieben werden können ...)
Ralf Peine, Dipl. Mathematiker, von 10/91 bis 12/97 für die KWU OI41 als Software-Entwickler, von 01/98-05/09 bei Siemens/Gigaset in Bocholt als Software-/ Tool- und CM-Architekt tätig.