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.