Berechnung von "Rissen" in einem Bild

[3_of_8]

Morgen.

Ich habe gerade folgendes Problem:

Ich habe eine Matrix von Punkten, die Pixel repräsentieren, aber auch noch andere Informationen besitzen, z.B. "Lebenspunkte".

Wenn ein Pixel "stirbt", soll überprüft werden, ob das Bild dadurch in mehrere Teile gerissen wird. Und genau das ist das Problem. Ich muss irgendwie alle Pixel markieren, die einer bestimmten "Gruppe" des Bildes angehören, also einem der verbleibenden Teile.

Momentan mache ich das so:
Zuerst wird allen Pixeln die Gruppe -1 zugewiesen. Anschließend wird für den ersten Nachbar des zerstörten Pixels ein Graphendurchlauf gestartet, bei dem alle erreichten Pixel als Gruppe 0 markiert werden. Das wird dann für alle noch nicht markierten Nachbarn des zerstörten Pixels durchgeführt.

Das funktioniert wunderbar, aber es ist leider unglaublich langsam. Die "Tötung" einzelner Pixel bewegt sich (bei einem relativ großen Bild) im Bereich von 60ms, ein "Flächenschaden" mit einem Radius von etwa 7 Pixel ist schon bei 10 Sekunden. Das ist für eine Echtzeitberechnung natürlich absolut inakzeptabel.

Gibt es irgendeine effizientere Lösung für so ein Problem?

[Cyberstorm]

Zeig doch mal deinen Code.
Villeicht ist da noch was zu verbessern / zu optimieren.

[inherited]

Das wird kaum zu optimieren sein, zumindest nicht das es akzeptabel schneller werden würde. Ich denke ein effektiverer Algorithmus muss her.

[3_of_8]

Ich hab den Code mal hochgeladen, aber ich denke, inherited hat Recht.

EDIT: ich hab auch nochmal ein Testprojekt mit hochgeladen.

[Nikolas]

Das ist ein ziemlich heftiges Problem. Ein paar Ideen:

- Lies mal was über den Begriff der Zusammenhangskomponenten eines Graphen.
- Versuche dein Gebiet etwas zu unterteilen.
- Unterscheide deine Strategie je nachdem, wie viele Pixel schon getötet wurden und wie viele Gebiete es gibt.
- Graphentheorie ist vielleicht nicht der beste Ansatz, da du damit Informationen über die maximale Anzahl von Nachbarn eines Pixels und über die Position von Pixeln verlierst. (Eine Breitensuche hat keine Ahnung, wie weit ein gerade betrachteter Pixel vom Startpunkt entfernt ist)
- Beschleunige besonders den Fall, in dem erkannt wird, dass kein Gebiet getrennt wird, da er sehr häufig vorkommt.

[3_of_8]

Hmmm... wie soll ich es machen, wenn nicht mit einem Graphen? Und wie soll ich es unterteilen?

[Nikolas]

Zur Unterteilung:

Wenn du ein Pixel tötest, schaust du dir die Umgebung an (5Px in jede Richtung). Wenn du da nur eine Gruppe hast (recht wahrscheinlich, wenn du dein Gebiet noch nicht stark zerrissen hast) kannst du prüfen, ob diese Knoten noch zusammenhängen. (Also nur diese 100px)
Wenn ja, bist du schnell fertig, ansonsten kannst du diese Gruppe ganz durchsuchen, in dem du von einem einzelnen Pixel eine Breitensuche startest und die erreichten Pixel zählst.
Wenn ja, bist du fertig. (x) Ansonsten betrachtest du ein Pixel, das in diese Gruppe war, aber nicht erwischt wurde und beginnst von diesem aus eine neue Gruppe. Jetzt solltest du alle Pixel in der ursprünglichen Gruppe erreicht haben. Wenn nicht, goto (x).
Also insgesamt ein stufenförmiges Vorgehen, so dass du die häufigen Fälle sehr schnell erkennen kannst und den Aufwand bei den besonderen Fällen steigerst.

Wie klein sollen denn die Gebiete werden? Wie viele Gebiete wirst du haben?

[3_of_8]

Das ganze schau ich mir später nochmal genau durch...

Wie klein? Naja, beliebig klein. Und wieviele? Beliebig viele, theoretisch, wobei ich vllt ab einer Größe von 4 Pixel das ganze dann verwerfe. Eigentlich wollte ich es ja so machen, dass "zerrissene" Teile getrennt werden, aber das mache ich später.

[Nikolas]

Hast du schon mal getestet, ob FloodFill schnell genug ist?

[stahli]

Hallo 3_of_8,

ist das Problem noch aktuell? Ich habe leider gerade keine Zeit, mich daran zu versuchen, trotzdem mal ein paar Überlegungen...
In Deinem Code vermisse ich die Prüfung, ob ein Riß besteht und dieser durchgehend ist. Erst wenn das feststeht lohnt sich die Aufteilung in Gruppen (oder Bereiche).

Also ich würde das (nach jetzigen Überlegungen) so angehen:

1.) Vorbereitung
- globale Variable MaxBereich=0
- globale Variable RißNr=0
- jedem Punkt wird der Bereich 0 zugewiesen
- jedem Punkt wird die Stabilität 8 zugewiesen
- jeder Punkt erhält die Eigenschaft RissNr=0
- jeder Punkt erhält die Eigenschaft Used=False

2.) KillPoint
- KLickPoint.Bereich in gobale Variable OriginalBereich speichern
- im Umkreis von 4 Pixeln wird die Stabilität um 4..1 Pixel vermindert
- wenn Stabilität auf 0 fällt, wird der Punkt gekillt (rekursiv)
(sonst hier noch nichts weiter machen)

3.) jetzt auf durchgehenden Riß testen (vom KlickPoint aus)
- globale Variablen Endlos1 und Endlos 2 auf False
- Point.Used:=True
- rekursiv alle benachbarten Punkte testen, ob sie gekillt sind nicht Used
-> wenn ja: wenn Rand erreicht ist oder der KillPunkt.RißNr>0 (oder als Sonderfall der Ausgangspunkt) dann Endlos1 auf True, Rekursion dieser Richtung abbrechen
-> sonst: weiter rekursiv testen
=> am Ende jeden rekursiven Aufrufes "rückwärts" Used wieder auf False
- wenn Endlos1=True weitere Richtung testen für Endlos2
- alle gefundenen KillPunkte bei dieser Suche in eine Liste speichern
- wenn Endlos1 und Endlos2 = True ist der Riss durchgehend
! IF RißNichtDurchgehend THEN GOTO 6.)

4.) Riß verwalten
- Globale Variable RißNr erhöhen
- allen Punkten aus der gefundenen Riß-Liste die RißNr zuweisen

5.) Bereiche zuweisen
- Globale Variable MaxBereich erhöhen
- vom KlickPoint aus alle umgebenenden Punkte Used auf True und testen, ob sie dem OriginalBereich entsprechen
-> dann rekursiv Used auf True und Point.Bereich := MaxBereich
=> am Ende jeden rekursiven Aufrufes "rückwärts" Used wieder auf False

6.) Riß-Liste wieder freigeben


Schade, dass ich gerade nicht selbst dafür Zeit habe...

stahli