FloodFill-Algorithmus - Alternative

hustbaer

Also ich denke man kann an dem Algorithmus so wie du ihn momentan hast sicher noch einiges optimieren.

z.B. kannst du den Test ob du "weiter füllen" musst (also das if(image->pixelValues1D[position] != 0.0f) ) VOR dem rekursiven Aufruf bzw. VOR dem pushen der nächsten Position in den std::stack machen.
Das sollte in beiden Varianten einiges bringen.

Und du kannst zumindest eine Richtung als "while" implementieren, also manuell die letzte Tail-Recursion wegoptimieren.

Und dann gibt es weitere Optimierungs-Möglichkeiten.

Wenn du z.B. die Richtung "y+1" (also "nach unten") per "while" implementierst, dann musst du...

nur beim ersten Schleifenaufruf auch einen "y-1" ("nach oben") Call absetzen/Position in den Stack pushen. Ab dem 2. Aufruf weisst du ja, dass der Pixel oberhalb der aktuellen Position bereits bearbeitet wurde.
beim "nach unten gehen" kannst du dir merken, ob der Pixel "x-1" ("nach links") im letzten Schleifendurchlauf der zu füllenden Farbe entsprochen hat. Hat er das im letzten Durchlauf, dann kannst du im nächsten den "x-1" Call weglassen, bzw. musst die "x-1" Position nicht in den Stack pushen. Ganz einfach weil sichergestellt ist, dass der bereits erfolgte "x-1, y-1" Call/... sich auch um den aktuellen Pixel "x-1, y" gekümmert hat bzw. kümmern wird.
Dasselbe kannst du für "x+1" machen.

Zusätzlich kannst du für die "y-1" Calls (also "nach oben", also gegen die "primäre Füllrichtung") eine eigene Funktion machen, deren primäre Füllrichtung auch "nach oben" ist statt "nach unten". Weiters kannst du in dieser Funktion die rekursiven Calls mit "y+1" weglassen, da auch sichergestellt ist dass sich darum bereits die aufrufende Funktion gekümmert hat bzw. kümmern wird.

Oder du bastelst gleich 4 Funktionen, je eine pro primärer Füllrichtung. Oder...

Ich bin mir auch sicher dass es einige gute Papers zu dem Thema gibt, ist ja schliesslich nicht so dass das ein all zu neues oder "seltenes" Problem wäre.

Es gibt noch den "scanline flood fill". Der Ding ist typischerweise schneller und beansprucht den Stack nicht so sehr.

PeterHJ schrieb:

Danach habe ich aus der rekursive Version eine iterative gemacht und bin mit der Geschwindigkeit nicht zu frieden.

Release + Compiler Optimierungen einschalten.

Das

if(image->pixelValues1D[position] != 0.0f) {

funktioniert nicht besonders gut. Bei Berechnungen, die eigentlich 0 ergeben, könnte eine Wert herauskommen, der nur sehr nahe an 0 liegt. Dann schlägt dein Vergleich fehl.

Lars

knivil

Er setzt den Wert aber hart mit .. ohne Berechnung.

outputImage[position] = 0.0f;

padreigh

PeterHJ schrieb:

void Segmentation::floodFillI(int x,int y, std::vector<int> *object) {
	
	float *outputImage = image->pixelValues1D;
	int imageWidth = image->getImageWidth();
	
	std::stack<int> stack;
	int position = y*imageWidth + x;
	stack.push(position);

	while(!stack.empty()) {
		position = stack.top();
		stack.pop();
		if(outputImage[position] != 0.0f) {
			y = position/imageWidth;
			x = position - y*imageWidth;

			outputImage[position] = 0.0f;
			object->push_back(position);
			
			if( (y+1) < 204 ) stack.push((y+1)*imageWidth + x); 
			if( (x-1) >= 0 ) stack.push(y*imageWidth + (x-1)); 
			if( (y-1) >= 0 ) stack.push((y-1)*imageWidth + x);
			if( (x+1) < 204 ) stack.push(y*imageWidth + (x+1));

		}
	}
		
 
}

Versteh ich das richtig?

Du packst den Startpixel auf den Stack
Du poppst den obersten Pixel wieder und prüfst ob er schwarz ist (ich interpretier 0.0f mal als Grauwert nicht als Transparenz o.ä.)
Wenn JA: passiert nix, Algo terminiert
Wenn NEIN:
- Schaust du ob du in einer Zeile < 203 bist, wenn ja pusht du den Pixel darunter rein
- Schaust du ob du in einer Spalte > 0 bist, wenn ja pusht du den Pixel links daneben rein
- Schaust du ob du in einer Zeile > 0 bist, wenn ja pusht du den Pixel dadrüber rein
- Schaust du ob du in einer Spalte < 204 bist, pusht du den Pixel rechts daneben rein
gehe zu 2

Im Endeffekt macht das doch nur einen schwarzen Bereich in einem beliebigen Bild der von 0,0 bis 203,203 reicht ... ist das nicht einfacher zu erreichen?

Erstmal danke ich allen die mit ihre Anregungen/Ideen geholfen haben.

padreigh schrieb:

PeterHJ schrieb:
void Segmentation::floodFillI(int x,int y, std::vector<int> *object) {
	
	float *outputImage = image->pixelValues1D;
	int imageWidth = image->getImageWidth();
	
	std::stack<int> stack;
	int position = y*imageWidth + x;
	stack.push(position);

	while(!stack.empty()) {
		position = stack.top();
		stack.pop();
		if(outputImage[position] != 0.0f) {
			y = position/imageWidth;
			x = position - y*imageWidth;

			outputImage[position] = 0.0f;
			object->push_back(position);
			
			if( (y+1) < 204 ) stack.push((y+1)*imageWidth + x); 
			if( (x-1) >= 0 ) stack.push(y*imageWidth + (x-1)); 
			if( (y-1) >= 0 ) stack.push((y-1)*imageWidth + x);
			if( (x+1) < 204 ) stack.push(y*imageWidth + (x+1));

		}
	}
		
 
}
Versteh ich das richtig?

Du packst den Startpixel auf den Stack

Du poppst den obersten Pixel wieder und prüfst ob er schwarz ist (ich interpretier 0.0f mal als Grauwert nicht als Transparenz o.ä.)
Wenn JA: passiert nix, Algo terminiert
Wenn NEIN:
- Schaust du ob du in einer Zeile < 203 bist, wenn ja pusht du den Pixel darunter rein
- Schaust du ob du in einer Spalte > 0 bist, wenn ja pusht du den Pixel links daneben rein
- Schaust du ob du in einer Zeile > 0 bist, wenn ja pusht du den Pixel dadrüber rein
- Schaust du ob du in einer Spalte < 204 bist, pusht du den Pixel rechts daneben rein

gehe zu 2

Im Endeffekt macht das doch nur einen schwarzen Bereich in einem beliebigen Bild der von 0,0 bis 203,203 reicht ... ist das nicht einfacher zu erreichen?

Die drei Schritte hast du richtig beschrieben und das Bild wird schwarz am Ende. Aber, die Pixel die vorher nicht schwarz waren, habe ich im Stack gespeichert und somit eine Segmentierung der Szene erreicht.

@padreigh:
Um die Vorgehensweise zu verstehen, ist es wichtig zu wissen wie die Szene aussieht. In meiner Szene befinden sich zwei Personen die ich segmentieren will. Die Pixel, die für das Ergebnis nicht wichtig sind, sind alle schwarz(0.0). Alle anderen Pixel müssen untersucht und somit gespeichert werden.

hustbaer

@padreigh:
Er macht nicht das ganze Bild schwarz.
Er füllt bloss einen *zusammenhängenden* Bereich nicht-schwarzer Pixel mit Schwarz an.

Andere nicht-schwarze Bereiche, die nicht mit dem "Startpunkt" zusammenhängen, "löscht" er dabei nicht.

padreigh

Edit: Hab wohl immer noch nen Denkfehler: Du startest mit einem != 0.0f Pixel füllst die erste Person, auf dem resultieren Bild suchste wieder einen !=0.0f Pixel und füllst die nächste?

text gelöscht, hatte noch keinen Kaffee