3. Aufruf rekursiver Funktion verursacht Segmentation Fault

Aufruf rekursiver Funktion verursacht Segmentation Fault

  • M

    Hallo,

    als Ausgangspunkt habe ich eine binäre Bildmaske in Form einer Matrix mit den Werten 0.0 bzw. 1.0. Ich möchte im Rahmen eines morphologischen Operators den Hintergrund dieser Maske mit 1.0 füllen und habe mir dafür eine rekursive Funktion geschrieben, die ausgehend von einem Startpunkt und einer 8er-Nachbarschaft den Hintergrund füllt.

    Das Prinzip versuche ich mal mit folgendem Pseudocode darzustellen:

    function setze_nachbar(maske, x, y, hintergrund, marker)
{
  wenn( maske(x+1,y) == hintergrund)
  {
    maske(x+1,y) = marker;
    setze_nachbar( maske, x+1, y, hintergrund, marker );
  }

  /* alle anderen Nachbarschaften folgen hier */
}

/* Beispielaufruf */
setze_nachbar(maske, 0, 0, 0.0, 1.0 );

    Abfragen auf Bildgrenzen und sonstiges habe ich der Einfachheit halber mal ausgelassen.

    Auf vielen Bildern funktioniert der Code und ich bin ihn schon zigmal durchgegangen. Ich bekomme mit einigen Bildern einen Segmentation Fault. Das Beispielbild ist 352x288 Pixel groß und der Hintergrundbereich nimmt einen großen Teil des Bildes ein.

    Zu der Frage: Kann es sein, dass der Segmentation Fault durch die extreme Tiefe der Rekursion verursacht wird?

    Danke für alle Antworten.

    0
  • B

    Wie tief wird die Rekursion ausgeführt? Reicht der Stack dafür?

    Erhöh mal den verfügbaren Stack, und probiers noch mal;)

    0
  • M

    Mahlzeit,
    ist wohl ein Stack-Overflow wg. Rekursionstiefe.
    Benutze besser einen iterativen Füllalgo, der ist dann auch noch etwas schneller.

    0
  • M

    Rekursionstiefe kann ich nur abschätzen. Bei einem Bild der Größe 352x288 und einem Anteil des Hintergrunds von vielleicht 90% würde ich sagen, sie liegt bei maximal 352x288x0.9 = 91238.4

    Hm. also fällt mir jetzt auch gerade auf, dass das etwas groß ist 😉 Leider läuft der iterative Ansatz nicht perfekt beim Füllen, wenn der Hintergrund zum Beispiel hinter einer Ecke versteckt ist. Aber ich versuch mal gerade, da was zu kombinieren.

    0
  • C
    Mod

    Du könntest die Marker für alle Nachbarschaften setzen, bevor der rekursive Aufruf erfolgt, das löst zwar das Grundproblem nicht, reduziert aber die maximale Rekursionstiefe um einen festen Faktor n-1 bei n Nachbarschaften.

    0
  • M

    camper schrieb:

    Du könntest die Marker für alle Nachbarschaften setzen, bevor der rekursive Aufruf erfolgt, das löst zwar das Grundproblem nicht, reduziert aber die maximale Rekursionstiefe um einen festen Faktor n-1 bei n Nachbarschaften.

    Ja, das wäre ein Ansatz. Ich habe gerade den ersten iterativen Ansatz, den ich programmiert habe, wieder rausgegraben. Ich gehe dabei zunächst in einer Schleife von links oben bis rechts unten alle Pixel des Bildes durch und setze entsprechend die Marker. Um das Problem der Ecken zu beheben, lasse ich danach den rekursiven Ansatz nochmals laufen. Das reduziert die Rekursionstiefe anscheinend auch ungemein. Das Problem ist damit vorerst gelöst.

    Danke.

    0
  • M

    Hier findest Du ein Beispiel für iteratives Füllen, Löcher in den Ecken bleiben eigentlich nicht übrig.

    http://de.wikipedia.org/wiki/Floodfill

    0
  • M

    MiP schrieb:

    Hier findest Du ein Beispiel für iteratives Füllen, Löcher in den Ecken bleiben eigentlich nicht übrig.

    http://de.wikipedia.org/wiki/Floodfill

    Is ja super. Da hätt ich ja auch selber drauf kommen müssen. Wusste nicht, dass das Floodfill heisst. Witzigerweise beschreiben die unter dem Titel 'Teiliterative Flutfüllung' genau das, was ich jetzt mache.

    Vielen Dank für den Link.

    0
Anmelden zum Antworten