FloodFill-Algorithmus - Alternative



  • Hallo,
    ich habe den Floodfill-Algorithmus umgesetzt und musste feststellen, dass er einen Stack-Overflow verursacht. Danach habe ich aus der rekursive Version eine iterative gemacht und bin mit der Geschwindigkeit nicht zu frieden. Ich habe die rekursive Version in Java ausprobiert und erhielt keinen Stack-Overflow. Allerdings wendete ich den Algorithmus in Java für ein einziges Bild und in c++ für ein Video. Kann es sein, dass ich den Stack nach jedem Frame löschen muss, wenn ich den in c++ verwende? Wenn ja, wie kann ich das machen?

    Ich würde mich freuen, wenn mir einer eine Lösung, oder eine Alternative vorschlagen kann. Ich bin dringend auf die Lösung, die der Algorithmus liefert angewiesen. Vor allem muss es Echtzeit fähig sein.

    Danke für Eure Bemühungen im Voraus.

    Hier noch der Code-Ausschnitt für die rekursive Lösung:

    void Segmentation::floodFillR(int y, int x, std::vector<int> *object) {
    	int imageWidth = image->getImageWidth();
    	int position = y*imageHeight + x;
    	if(image->pixelValues1D[position] != 0.0f) {
    
    		object->push_back(position);
    		image->pixelValues1D[position] = 0.0f;
    
    			if( (y+1) < 204 ) floodFillR(y+1,x,object); // unten
    			if( (x-1) >= 0 ) floodFillR(y,x-1,object); // links
    			if( (y-1) >= 0 ) floodFillR(y-1,x,object); // oben
    			if( (x+1) < 204 ) floodFillR(y,x+1,object); // rechts
    	}
    
    }
    

    Hier die iterative Lösung:

    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));
    
    		}
    	}
    
    }
    


  • Kann es sein, dass ich den Stack nach jedem Frame löschen muss

    Nein, er ist lokal.

    Vor allem muss es Echtzeit fähig sein.

    Was immer das in deinem Fall heisst ... Du koenntest Speicher deines Stacks von der Groesse des Bildes reservieren. Das gleiche gilt fuer std::vector<int> *object.

    Ohne genaueren Zusammenhang wird es schwer sein, Optimierungsmoeglichkeiten anzugeben.



  • Danke für deine Antwort knivil.

    Damit keine Missverständnisse entstehen, wollte ich sicher stellen, dass nicht der Stack-Container aus dem zweiten Code-Abschnitt(iterative Lösung) gemeint ist, sondern aus dem ersten Code-Abschnitt(rekursive Lösung).

    Außerdem frage ich mich, warum ich mit Java kein Stack-Overflow hatte. Der rekursive Algorithmus hat ca. 7 ms für die Berechnung gebraucht.
    Ich habe mit Java-Programmierung mehr Erfahrung und deshalb habe ich erst mit Java realisiert, um zu erfahren, ob die Lösung für mich brauchbar ist. Leider ist das so, dass es die LÖSUNG ist.

    Um mehr Geschwindigkeit zu bekommen, habe ich mir eine Multithreading-Lösung überlegt(für die iterative Lösung). Nur bin ich mir nicht sicher, ob sich die Geschwindigkeit deutlich erhöht.

    Mit Echtzeit meine ich, dass der Algorithmus für die Berechnung ca. 15 ms benötigen sollte.



  • 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...

    1. 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.

    2. 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



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

    outputImage[position] = 0.0f;
    


  • 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?

    1. Du packst den Startpixel auf den Stack
    2. 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
    3. 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?

    1. Du packst den Startpixel auf den Stack
    2. 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
    3. 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.



  • @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.



  • 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 😉


Log in to reply