Such Algorithmus zum ausfüllen eines Objekts mit einer Farbe

[p_mork]

Hallo,

ich habe ein Bild in dem farbige Objekte sind. Nun möchte ich ein Objekt in der Farbe x mit einer anderen Farbe ausfüllen. Alle Pixel der Farbe X sollen also eine andere Farbe kriegen. Wie macht man das am Besten?

MfG Mark

[Pascal]

Gibt es die Farbe x nur in dem betreffenden Objekt?

[p_mork]

Leider nicht, denn dann könnte man ja einfach nur alle Pixel auf dem Bild ersetzen. Es dürfen aber nur die Pixel von dem jeweiligen Objekt sein. Wie machen denn das Zeichenprogramme wie Paint mit seinem "Farbfüller"?

[Pascal]

Wie ist dann das Objekt genau festgelegt, wenn die Farbe nicht eindeutig auf das Objekt schließen lässt? Also anders formuliert: Bisher hast du als Eigenschaft nur die Farbe der Pixel. Da aber auch andere Pixel diese Farbe haben, musst du ja noch ein anderes Merkmal haben, durch das das Objekt bestimmbar ist.

[p_mork]

Ich versuch mal mein Problem mit 2 Bildern zu erklären:

siehe unten...


Aus dem blauen Kreis unten rechts ist ein grüner geworden. Der andere blaue Kreis ist unverändert. Nur die zusammenhängenden Pixel im rechten Kreis wurden grün.

MfG Mark

[Duke of Doom]

Heißt das du kennt wenigsten einen Pixel der sich in diesem Objekt befindet?

[p_mork]

Ja, natürlich, die Position eines Pixels ist mir bekannt.

[Duke of Doom]

Auf die schnelle würd ich sagen:
überprüf doch einfach jeden umliegenden Pixel vom Ausgangspixel auf die jeweilige Farbe, dannach die umliegenden der gerade überprüften usw......
Ist zwar sicher nicht das performanteste aber sollte funktionieren.

[Phantomix]

im prinzip willst du was was alle handelsüblichen malprogramme können, nachprogrammieren, also wirds schon irgendwie effizient gehen.

das beste wär allerdings, wenn du ein wenig Speicher frei hast, um dir paar nachfolgende pixel-koordinaten zu merken (oder rekursion - wobei dir da der stack überlaufen könnte)

[Phantomix]

Hier mal ein Algorithmus:



Objekt-Ausmal-Algorithmus

Dieser Algorithmus geht über ein Objekt und malt alle Pixel einer Farbe mit einer anderen Farbe aus. Begrenzungen sind bestimmt durch eine andere Farbe als die ursprüngliche.

Ausgangspunkt und Bestimmer der zu übermalenden Farbe ist dabei ein beliebiger Pixel innerhalb des Zielobjektes.

Der Algorithmus benutzt dabei zwei Tabellen um gefundene Startpunkte, die noch nicht an der Reihe sind, zu merken: einmal für die Richtung nach oben, und einmal für die Richtung nach unten.

Leider werden momentan noch alle pixel doppelt geprüft (einmal beim gucken ob darüber/darunter, und einmal beim gucken ob links/rechts) da ließe sich sicher auch noch was optimieren!

Pseudocode:


- Startpixel in beide Tabellen tun

- solange Tabellen nicht leer sind:

- nach oben suchen:

- Pixel aus tabelle1 nehmen
- einfärben
- andere_farbe_flag setzen

- nach links gehen bis vor andersfarbigen pixel

- darüber andere farbe? -> andere_farbe_flag setzen
- darüber gleiche farbe?
- andere-farbe-flag gesetzt:
- andere-farbe-flag löschen
- gefundener pixel -> tabelle1
- andere-farbe-flag nicht gesetzt:
- nix tun
- einfärben

- andere-farbe-flag löschen

- nach rechts gehen bis vor andersfarbigen pixel

- siehe nach-links-gehen

- nach unten suchen:

- äquivalent zu nach oben suchen



Edit:
hab grad festgestellt da fehlt noch was:
wenn der algo zb nach oben und links geht, und geht gerade so über eine andere farbe hinweg, wird darunter nicht nach neuen gleichfarbigen pixeln gesucht. scheinbar reichen da 2 vergleiche doch nicht, allerdings kann man ihn dann an ner anderen stelle vereinfachen und nur 1 tabelle benutzen, ich arbeite dran...

Nochmal Edit:
siehe http://www.gkrueger.com/java/aufgaben/aufg14.html
Punkt 39c dort wird ein ziemlich effizienter algorithmus beschrieben.

[p_mork]

Hallo Phantomix,

vielen Dank für den Algo und den Link. Mittlerweile habe ich selbst eine Methode entwickelt, die aber nicht so effizient ist, weshalb ich den Algorithmus aus dem Link nehmen werde.

MfG Mark

[p_mork]

Hallo,

ich habe gerade den Füllalgo aus dem Link angewendet. Komischerweise ist dieser viel langsamer als meiner, obwohr er eigentlich schneller erscheint und auch kürzer ist. Anscheinend braucht der µC zu viel Zeit, um die Linien auf den Stack zu legen.

MfG Mark

[Phantomix]

das ist mist. worin programmierst du? assembler?


schau nach dass du die sachen im RAM ablegst (asm: wenn du den stack mit push/pop verwendest und immer register pusht sollte das gehen)



Edit: Mich würde generell mal bissl code von dir interessieren (wie du beides umgesetzt hast ^^)

[p_mork]

Hallo Phantomix,

ich programmier in C++, da der ARM7-Assembler für mich viel zu schwer ist. Ich kann hier den Code posten, aber ich glaub nicht dass das hilft, da der Code ziemlich unübersichtlicht ist und einige systemspezifische Sachen enthält. Das Prinzip ist folgendes:

Finde die erste Linie und fülle sie aus

loop:
scanne das bild nach unten ab nach einer linie
wenn eine linie gefunden:
wenn es einen ausgefüllten punkt über der linie gibt dann füll die linie aus und merke, dass etwas ausgefüllt wurde

wenns nicht ausgefüllt dann fertig

scanne das bild nach oben ab nach einer linie
wenn eine linie gefunden:
wenn es einen ausgefüllten punkt unter der linie gist dann füll die linie
aus und merke, dass etwas ausgefüllt wurde

wenn nichts ausgefüllt dann fertig
ansonsten goto loop

MfG Mark

PS: bitte zuerst die Füllfunktion nach der Methode aus dem Link angucken, weil dort wichtige Zusatzinformationen stehen!