Vektorisierung von Rastern

[tromai]

Hallo zusammen,

ich denke die Antwort auf meine Frage ist realtiv simpel. Im Prinzip suche ich nur nach einem Stichwort um in meinen recherchen weiterzukommen. Aber vielleicht hat ja auch jemand ein Package parat, das ganz genau das macht was ich suche.

Das Problem:
Ich möchte eine Rasterfläche vektorisieren. Sprich: Ein Polygon um eine Fläche legen.

Mein aktueller Ansatz:
Ich habe das Raster in ein Array mit Nullen und Einsen gespeichert. Das genügt erstmal meinen Ansprüchen.

1.Schritt: Ich extrahiere von der Fläche die Randpixel mit convolve() und where() Anweisungen. Das klappt auch ganz gut.
Also aus
0 0 0 0 0 0 0
0 0 1 0 0 0 0
0 1 1 1 1 0 0
0 0 1 1 1 1 0
0 1 1 1 1 1 0
0 1 1 1 1 1 0
0 0 0 0 0 0 0
mache ich
0 0 0 0 0 0 0
0 0 1 0 0 0 0
0 1 0 1 1 0 0
0 0 1 0 0 1 0
0 1 0 0 0 1 0
0 1 1 1 1 1 0
0 0 0 0 0 0 0
2. Schritt: Alle Indizies von Einser-Pixeln werden in eine Liste gespeichert.
3. Schritt: Ich mache eine Linienverfolgung entlang der Randpixel beginnend beim ersten Pixel der Index-Liste aus Schritt 2. Ich kenne den Namen des Algorythmusses leider nicht aber hier der Ansatz:
- an einem Einser-Pixel wird links abgebogen
- an einem Nuller-Pixel wird rechts abgebogen
- um Schleifenschlüsse zu vermeiden muß spätestens nach dreifachem Rechts- bzw. Linksabbiegen immer links bzw. rechts abgebogen werden.
- dazu kommen noch ein paar Sonderfälle
Der Index des gefundenen Pixels wird aus der Indize-Liste gestrichen um später zwischen verschiedenen Flächen unterscheiden zu können.
4. Schritt: Wenn der Anfangspixel der Linienverfolgung erreicht ist ist das Polygon geschlossen. Es wird mit Schritt 2 fortgefahren und solange immer wieder dort angefangen bis die Index-Liste leer ist.

ich hoffe das war jetzt einigermaßen verständlich.

Das Prinzip funktioniert, ist aber ziemlich lahm. Das muss aber doch irgendwie auch schneller gehen! Z.B. arbeitet jeder Zauberstab in einem Bildbearbeitungsprogramm quasi in Echtzeit. Jetzt weiß ich allerdings nicht ob da wirklich eine Vektorisierung durchgeführt wird.

Vielleicht hat jemand eine zündende Idee wonach man suchen könnte, bzw. ob es dafür irgendein Package gibt.

Danke für die Hilfe im Voraus!

Grüße
tromai

[veers]

Der Vorgang nennt sich soweit mir bekannt tracing. Mit dem Stichwort bringt auch Google einige Resultate.

Des weiteren weiss ich das Inkscape so etwas kann. Du kannst ja da mal rein schauen.

Gruss,
Jonas

[BlackJack]

Der Zauberstab in Malprogrammen vektorisiert nichts, das ist ein Flächenfüllalgorithmus der aufgrund der Pixel im Bild die Selektionsmaske füllt. Wobei man üblicherweise eine Toleranzgrenze festlegen kann wie weit ein Pixel in der Farbe abweichen darf und trotzdem noch zur Fläche gehört.

Wozu brauchst Du das denn? So wie Du vorgehst vektorisierst Du die einzelnen Pixel, d.h. das Ergebnis hat die "Treppenstufen" die man üblicherweise bei der Vektorisierung loswerden will. Wenn die bleiben kann man ja gleich mit Pixeldaten weiterarbeiten.

Ein anderer Ansatz wäre es die Ausgangsdaten zu nehmen und einen "Scan" von oben nach unten zu machen und dabei die Flächen aufzubauen.

[tromai]

Wegen des Zauberstabes:
Es wird ja in der Regel der Umkreis der Fläche gestrichelt umrandet. Ich bin davon ausgegangen, dass das über Vektoren passiert. Also ich meine jetzt nur die Darstellung. Dazu muss er ja zumindest ermitteln, wie die Grenze verläuft. Ich habe keinen Plan wie das gemacht wird. Aber es könnte ein Ansatz sein.

Im Prinzip ist es erstmal egal ob die Treppenstufen erhalten bleiben. Ich will eigentlich nur Polygone, die ich dann in ein Geodatenformat abspeichern möchte, damit ich dort bequem damit weiterarbeiten kann.

Bei dem Algorhythmus wie ich ihn beschreiben habe entstehen allerdings gar keine Stufen. Ein gerader Strich besteht lediglich aus unnötig vielen Punkten, die man allerdings bereinigen kann. das soll also nicht das Problem sein.

Ein Großteil der Zeit wird bei meinem Algorythmus beim suchen der Randpixel verplempert ich mache es folgendermaßen:

Code: Alles auswählen

a = convolve(array([1,2]), arr.flatten())[:-1].reshape((len(arr),len(arr[1])))
b = convolve(array([1,2]), .arr.transpose().flatten())[:-1].reshape((len(arr),len(.arr[1]))).transpose()
c = fliplr(convolve(array([1,2]), fliplr(arr).flatten())[:-1].reshape((len(arr),len(arr[1]))))
d = fliplr(convolve(array([1,2]), fliplr(arr.transpose()).flatten())[:-1].reshape((len(arr),len(arr[1])))).transpose() 
rand = where(a == 1, a, rand)
rand = where(b == 1, b, rand)
rand = where(c == 1, c, rand)
rand = where(d == 1, d, rand)

Wobei rand der Array ist in dem nur noch die Ränder vorhanden sind und arr der Eingangsarray.

Vielleicht hat auch jemand eine Idee, wie man das schneller machen könnte.

Ich werde mal schauen ob sich mit Tracing etwas machen lässt aber ich denke da muss es noch einen anderen Weg geben.

[BlackJack]

Die Umrandung bei der Selektion in Malprogrammen wird da angezeigt, wo es in der Selektionsmaske einen Übergang von unter 50% zu über 50% gibt. Selektionsmasken sind ja üblicherweise Graustufenkanäle. Das ist recht schnell und einfach programmiert und verbraucht keinen zusätzlichen Speicherplatz. Man denke nur mal an die zusätzlichen Vektordaten bei einem grossen Bild bei dem jedes zweite Pixel schachbrettartig selektiert ist.

Das bei Dir keine Treppenstufen entstehen verstehe ich nicht. Nehmen wir mal dieses Dreieck:

Code: Alles auswählen

......
.X....
.XX...
.XXX..
.XXXX.
......

"Ordentlich" vektorisiert ist das ein Polygon mit drei geraden Linien, insbesondere die von links oben nach rechts unten ist *eine* Linie. So wie sich Dein Algorithmus anhört, zeichnet der aber die Pixel nach und es gibt eine "Treppe" von links oben nach rechts unten.

[tromai]

Der Algorythmus gibt gibt mir die Koordinaten der Pixel zurück.
Die schräge Linie in deinem Beispiel setzt sich aus den Koordinaten 1/1, 2/2, 3/3, 4/4 zusammen. Wenn du da jetzt eine Linie zeichnest gibt es einen geraden Strich. Also ich umrande die Pixel nicht sondern ziehe eine Linie über ihre Koordinaten. Das hat zwar den Nachteil, dass der halbe Pixel nicht mehr in der Fläche liegt. Das ist allerdings erstmal nicht tragisch.

Oder mache ich da jetzt gerade einen Denkfehler?

[tromai]

Ok, ich habe jetzt eines der Probleme ausmachen können.
Ich lasse über mein Raster ein numpy.convolve() und hatte den falschen Mode. Dadurch musste ich ihn einmal von rechts nach links laufen lassen und einmal von links nach rechts um die Randpixel extrahieren zu können. Das ganze wurde dann nochmal für die Senkrechte fällig. Also waren es insgesamt 4 convolutions. Ich habe jetzt einen anderen Mode genommen. Dadurch kann ich das in einem Rutsch machen. Zumindest für die waagrechte und die senkrecht. Also spare ich mir 2 convolutions und ich bin deutlich schneller.

[CM]

Klingt interessant. Magst Du Deine Lösung hier posten, wenn Sie fertig ausgearbeitet ist? Vielleicht unter Codeschnipsel oder so?

Gruß,
Christian

[tromai]

Um die Fühler nochmal in eine andere Richtung auszustrecken:

Kennt sich jemand mit Fast Fourier Transformationen aus? Könnte man vielleicht damit eine Isolation der Randpixel erreichen?

[EyDu]

Kennt sich jemand mit Fast Fourier Transformationen aus? Könnte man vielleicht damit eine Isolation der Randpixel erreichen?

Nein, das wird nichts.

Schau dir mal den Marr-Hildreth-Operator an. Ein ganz typisches BBA/BVA-Anwendungsgebiet.

[tromai]

Ah, ok. Da gibts wohl auch eine scipy-funktion dazu. Ich werde mal etwas herumprobieren und dann berichten.

[tromai]

Also ich habe es jetzt mit
scipy.ndimage.filters.laplace() versucht. Das ist bei tests ca. 33% schneller als das was ich bisher gemacht habe. Die Logik ist im Prinzip die gleiche. Ich habe im Prinzip 2 mal einen 1d-Laplace-Filter benutzt und dadurch eine Menge Zeit verplempert.

Die Beschreibung der Funktion lautet:

laplace(input, output = None, mode = 'reflect', cval = 0.0)
Calculate a multidimensional laplace filter using an estimation for the second derivative based on differences.

Mehr habe ich nicht gefunden. Kann mir da evtl. jemand weiterhelfen was die restlichen modes angeht bzw. was cval festlegt?

Was das angeht kommt es mir vor, als ob hier für die Geschwindigkeit erstmal Schluss ist. Sollte noch jemand eine Idee haben, wie man es noch schneller machen kann wäre ich natürlich dankbar.

Ich werde mich dann nochmal an den Linienverfolgungsalgorythmus machen und dann berichten. Da fehlen noch ein paar Sonderfälle und es dürfte noch etwas Geschwindigkeit herauszuholen sein.

[tromai]

Nur für die, die es interessiert. Der oben vorgestellte Algorythmus funktioniert nach der Definition von zwei Sonderfällen ganz gut. Durch die Nutzung von "psyco" konnte das ganze auch nochmal um ca. 30% beschleunigt werden.
Probleme macht der Algorythmus eigentlich nur noch bei Inseln, die mit den umrandenden Randpixeln der Fläche Pixel gemeinsam haben.

Also bei so etwas z.B.:
0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 1 1 1 1 1 1 1 1 1 1 0
0 1 0 0 0 0 0 0 0 0 0 1 0
0 1 0 0 0 0 0 0 0 0 0 1 0
0 1 0 0 0 0 0 0 0 0 0 1 0
0 1 0 0 0 0 0 0 0 0 0 1 0
0 1 0 0 0 1 1 1 1 0 0 1 0
0 1 0 0 1 0 0 0 1 0 0 1 0
0 1 1 1 1 1 1 1 1 1 1 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0

In diesem Fall wird Dummerweise bei einem zu Insel gehörenden Pixel mit der Linienverfolgung angefangen und wenn die Randpixel erreicht werden dort weitergemacht. Der In der Insel liegende Punkt wird dann nie wieder erreicht und eine Endlosschleife beginnt. Das ist eigentlich der letzte problematische Punkt (hoffe ich). vielleicht hat ja jemand eine spontane Idee.

Eine relativ große Komplexe fläche wird in immerhin ca. 0,5 sec detektiert. Das ist mehr als ich mir erhofft hatte. ich muss mal noch schauen ob die Nutzung von pyrex oder ctypes nochmal etwas bringt.

[thelittlebug]

was mir bis jetzt noch nicht ganz klar ist:
willst du alle linien erkennen oder einen "umriss".

lgherby

[CM]

Probleme macht der Algorythmus eigentlich nur noch bei Inseln, die mit den umrandenden Randpixeln der Fläche Pixel gemeinsam haben.

Hierbei könnte eine Fourier-Transformation allerdings doch helfen: Wenn Du das Bild vorher einem vorsichtigen LowPass-Filter unterwirfst. Die erkannten Grenzen kannst Du ja wieder auf das Original beziehen. Bedingung ist natürlich, daß Du nicht zu wenige Pixel im Bild hast - also mehr als im allerersten Beispiel. Aber so ab 32x32 habe ich damit schon ganz gute Erfahrungen gemacht (allerdings in einer anderen Skriptsprache).

Gruß,
Christian

edit: Rechtschreibung

[tromai]

Ich will den Umriss einer bzw. mehrerer Flächen samt Löchern aus einem Raster erkennen.

@CM: Bin mir nicht ganz sicher was mit der Teifpassfilter bringt. Bzw. was ich daraus gewinne. Vielleicht kannst du das genauer erläutern, wie du das meinst (also nicht den Filter, sondern das "Danach").