Krautkanal.com

Veröffentlicht am 2016-09-29 07:55:33 in /prog/

/prog/ 9248: Hier ist schon ein reger Faden zur Regionen da, drum br...

ayalacw Avatar
ayalacw:#9248

Hier ist schon ein reger Faden zur Regionen da, drum bringe ich noch einen mit meinen Problem.

Angenommen ich habe auch ein zweidimensionales Array, wo zu jeder x,y Koordinate eine Zugehörigkeit zur einer Region verzeichnet ist. Die Regionen sind zusammenhängend und eindeutig einmalig da. Diese Regionen können in einander verschachtelt sein. Ich habe das im Bild so angezeigt, und dabei auch jede Region zur besseren Anschauung mit einer anderen Farbe versehen.

Meine Frage ist, wie kann ich diese Verschachtelung am Besten maschinell rausfinden und zur späteren Verarbeitung in eine Liste packen?

Also ich will zum Schluss etwas Ähnliches wie das hier haben:

{
Rot{
Grün{
Gelb,
Cyan
},
Blau
}

}


Falls Parser, wie immer, die Tabs schluckt, ist die Liste auch als Bild oben da.

ffbel Avatar
ffbel:#9249

Du meinst, dass du Rechtecke mit den Koordinaten x0, y0, x1, y1 hast, und herausfinden möchtest, ob ein Rechteck (1.) innerhalb eines anderen Rechtsecks liegt, oder (2.) benachbart zu einem anderen Rechteck?

Das blaue und gelbe Rechteck haben zwar werder (1.) noch (2.) Relation zueinander, aber das sollte egal sein, weil sich wohl immer andere Rechtecke finden lassen, die diese Relation zueinander haben.

Ich würde das erst so speichern (Pseudo-LISP-Code):

(
(red, (green, blue)),
(green, (yellow, cyan)),
(yellow, ()),
(cyan, ()),
(blue, ())
)

Wobei jedes Element hier die Form (source, (target0, target1, ...)) hat. Und dann einen gerichteten, azyklischen Graphen bzw. genauer Baum draus machen. Also einfach für jeden target-Knoten, die Source-Knoten finden. Dann sollte ja deine Struktur mit {Rot { Grün { ... }} automatisch bei rauskommen.

gojeanyn Avatar
gojeanyn:#9250

Weiter >>9249

Obwohl natürlich eigentlich

(red, (green, yellow, cyan, blue))

ist. Liegen ja alle Rechtecke in dem roten Rechteck.

Dann könnte man yellow und cyan von mir aus rausnehmen aus red, wenn man green bearbeitet/durchläuft/traversiert. Oder so ähnlich.

Erinnert Bernd übrigens ein bisschen an SHRDLU, so ein Experiment der frühen Forschung zur Künstlichen Intelligenz mit Bauklötzen in relation zueinander von 1972.

http://hci.stanford.edu/~winograd/shrdlu/index.html

dmackerman Avatar
dmackerman:#9252

Mal wieder ne supergenau gestellte Frage. Nicht.
Welche Ausgabe erwartet OP für Bild relatiert?

kinday Avatar
kinday:#9253

>>9252
Dieser Fall kann nicht eintreten. Regionen sind von einander klar getrennt.

RussellBishop Avatar
RussellBishop:#9254

Flood Fill + Breitensuche.

t1mmen Avatar
t1mmen:#9255

>>9254
>Flood Fill + Breitensuche.

Zum Erstellen so einer Graphik vielleicht. Aber weshalb Breitensuche?

>Regionen sind von einander klar getrennt.

Ohje, das heißt das sind keine riesigen schwarzen Ränder zwischen den Regionen, sondern schwarze Lücken? Sind die Regionen selbst planar oder liegen sie übereinander?

ntfblog Avatar
ntfblog:#9256

Du suchst eigentlich wir Worte.
Abgekürzt wird es oft als JSON beschrieben.

Faden kann dann geschlossen werden.

_zm Avatar
_zm:#9260

>>9256
nein, was ich suche ist, die Möglichkeit die Schachtelung der einzelner klar getrennter Regionen in einer zweidimensionaler Struktur mit einer vorgegebener Metrik herauszufinden, und möglichst mit einer nicht explodierender Zeitkomplexität.

murrayswift Avatar
murrayswift:#9264

>>9248
Wenn jede Region nur ein direkt übergeordnetes Rechteck hat, in das es eingepackt ist, handelt es sich doch um einen Baum.

rangafangs Avatar
rangafangs:#9265

Iteriere über das gesamte Bild und merke dir für jede Farbe die maximalen und minimalen x und y Werte. Daraus kannst du dann die Regionen als (x,y,w,h) Tuple wiederherstellen.

Deine Liste ist ein Baum indem jeder Knoten eine Region ist deren Kinder alle Regionen sind die von ihr umschlossen werden. In deinem Beispiel sind die Blätter Blau, Gelb und Cyan. Die Wurzel ist eine imaginäre Region die das gesamte Bild umfasst.

Wenn du die Regionen, absteigend nach ihrer Fläche sortiert, in den Baum einfügst hast du am Ende deine Liste. Die Funktion zum einfügen beginnt bei der Wurzel und sucht nach dem Kind das die einzufügende Region umschließt. Falls es so eine gibt ruft sich die Funktion rekursiv mit diesem Kind als Wurzel auf. Wenn kein passendes Kind gefunden wird, wird die neue Region als Kind in den aktuellen Knoten hinzugefügt.

Da die Regionen nach Größe sortiert in den Baum eingefügt werden sollten nur Blätter hinzugefügt werden müssen, bin mir aber nicht sicher.

Die Laufzeit ist O(n1 + n2 * n2). Wobei n1 die Zahl der Pixel im Bild ist und n2 die Zahl der Regionen. Im Worst-Cast ist n1 = n2. Man kriegt das vielleicht auf O(n1 + n2 * lg(n2)) runter wenn man einen selbstbalancierend Baum nimmt.

Beispielkot in Rust: https://gist.github.com/flanfly/f603ccea871943f180fded62a7247592

mat_stevens Avatar
mat_stevens:#9266

>>9265
wird es für beliebige, also nicht rechteckige Regionen funktionieren?

aiiaiiaii Avatar
aiiaiiaii:#9267

>>9265
Der 2. Teil mit dem Baum schon. Die Polygone aus dem Bild zu extrahieren ist aber deutlich schwerer als mit Rechtecken.

itsracine Avatar
itsracine:#9268

>>9267
War für
>>9266

ademilter Avatar
ademilter:#9270

Da der Faden nun tatsächlich etwas auflebt (aber OP sich nach wie vor praktisch komplett raushält und es nicht für nötig hält, sein Problem mal ausführlich zu beschreiben), meldet sich hier nochmal >>Flood Fill + Breitensuche zu Wort.

Die Idee ist, das Bild pixelweise zu besuchen: von außen nach innen.
Es gibt eine Queue, in der noch zu besuchende Pixel gespeichert werden.
Begonnen wird, indem alle Randpixel (also ein Rechteck der Stärke 1px) in die Queue gelegt werden.
Nun wird wiederholt solange der älteste Eintrag aus der Queue entnommen, bis diese leer ist.
- Für jeden der Queue entnommenen Pixel wird Flood Fill von diesem Pixel aus gestartet. Dabei wird sich die Farbe des ersten Pixels gemerkt. Sobald man im Flood-Fill-Schritt auf einen Nachbarpixel trifft, der eine andere Farbe hat, wird dieser Pixel an die Queue angehängt, aber von Flood Fill in diesem Schritt nicht weiter besucht.
- Alle von Flood Fill besuchten Pixel werden als ERLEDIGT markiert. Das geht, indem man eine zusätzliche Farbe einführt, die auf dem Bild nicht vorkommt. Dann kann die ERLEDIGT-Markierung direkt im Originalbild gesetzt werden.
- Ist der oberste Pixel der Queue bereits ERLEDIGT, wird er ignoriert, also Flood Fill nicht gestartet.

Durch die konkrete Implementierung von Flood Fill kann man definieren, wann zwei Pixel eine Nachbarschaftsbeziehung haben (gelten z.B. diagonale Pixel auch schon als benachbart?).

Der Baum kommt nun wie folgt zustande (die Knoten des Baumes sind Farben, die Kanten Eltern-Kind-Beziehungen).
In die Queue werden nicht nur die koordinaten eines Pixels gespeichert, sondern auch die Farbe des Eltern-Bereiches. Diese Farbe entspricht der Farbe, die der erste Pixel im jeweiligen Flood-Fill-Schritt hatte.
Jetzt fügt man für jeden von der Queue genommenen Eintrag, der nicht ERLEDIGT ist, eine Kante von der Eltern-Farbe zur Farbe des gequeten Pixel ein. Ggf. muss man hier berücksichtigen, wenn eine Farbe mehrmals verwendet wird.

Lineare Laufzeit.

Noch offen: Wie erkenne ich, ob die Baum-Annahme des OPs verletzt ist?

mbilderbach Avatar
mbilderbach:#9271

>>9270
Nachtrag: Lineare Laufzeit stimmt nicht ganz, das Einfügen aller Kanten in den Baum ist, je nach Datenstruktur, evtl. langsamer als linear.

Hier nochmal als Pseudocode:
Eingabe: Ein MxN großes 2D-Array A mit den Elementen a_ij. Der Wert von a_ij steht für die Farbe des Pixels.
Ausgabe: Ein Baum (V, E), der alle zusammenhängende Bereiche aus A als Knoten und deren Eltern-Kind-Beziehungen als Kanten enthält.

// Einschränkungen: Es darfe keine zwei Bereiche mit der selben Farbe geben und die Bereiche müssen hierarchisch angeordnet sein, sonst ist das Ergebnis undefiniert.

- wähle eine noch nicht benutzte Farbe als Wert für die Konstante WURZEL
- wähle eine noch nicht benutzte Farbe als Wert für die Konstante ERLEDIGT
- erstelle Queue der Größe m*n
- für alle Randpixel x von A (also a_11,...,a_m1, a_11,...,a_1n, a_m1,...,a_mn, a_1n,...,a_mn)
- füge das Tupel (Koordinaten von x, WURZEL) an die Queue an

- solange die Queue nicht leer ist:
// nächster Schritt Breitensuche:
- nehme ältesten Eintrag (e, f) = (Koordinaten eines Pixels, Elternfarbe) aus der Queue
- falls a_e == ERLEDIGT: continue
- setze Farbe := a_e

// Baum erweitern:
- ergänze ggf. V um die Knoten Elternfarbe und Farbe
- füge Kante von Elternfarbe nach Farbe in E ein

// Flood-Fill-Schritt
- starte Flood Fill bei a_e
- für jeden besuchten Pixel an der Stelle g: setze a_g := ERLEDIGT
- immer, wenn Flood Fill auf einen Pixel an der Stelle g mit a_g != Farbe trifft: Füge (g, a_g) an die Queue an, aber besuche a_g nicht

Neuste Fäden in diesem Brett: