[C#] Recursieve functie geeft StackOverflowException

[Maarten Kroon]

Ik heb een eenvoudige loop die een 2 dimensionaal array met kleuren doorloopt en kijkt of de kleur van de betreffende pixel zwart is. Als deze zwart is geef ik de pixel een nieuwe kleur en roep ik een recursieve functie aan die de kleur van de buurpixels bekijkt. Als deze ook zwart zijn geef ik ze weer een nieuwe kleur en bekijk ik ook de buurpixels van deze pixels weer totdat er geen aaneengesloten zwarte pixels meer gevonden worden.

Dit werkt goed op kleine afbeeldingen maar bij grote afbeeldingen van 8192 * 8192 pixels krijg ik al snel een StackOverflowException. Ik houd een counter bij om te meten wanneer dit gebeurd, dit gebeurd bij ongeveer 8000 calls al.

Ik heb al wat dingetjes geprobeerd om de functie kleiner te maken maar helaas zonder succes. Hopelijk ziet iemand wat ik hier fout doe want ik kan me niet voorstellen dat 8000 calls zoveel ruimte op de stack innemen.

Dit is de recursieve functie die de de buurpixels van een bepaalde pixel bekijkt:

C#:

    private void checkNeighbours(Vector location, ref Building newBuilding)
    {
        stackCount++;
        //Check the pixel left of us
        if (location.x != 0 && buildingMapArray2D[location.x - 1, location.y] == Color.black)
        {
            Vector newLocation = new Vector(location.x - 1, location.y);
            labelPixel(newLocation, ref newBuilding);
            checkNeighbours(newLocation, ref newBuilding);
        }
        //Check the right left of us
        if (location.x != (width - 1) && buildingMapArray2D[location.x + 1, location.y] == Color.black)
        {
            Vector newLocation = new Vector(location.x + 1, location.y);
            labelPixel(newLocation, ref newBuilding);
            checkNeighbours(newLocation, ref newBuilding);
        }
        //Check the pixel above us
        if (location.y != 0 && buildingMapArray2D[location.x, location.y - 1] == Color.black)
        {
            Vector newLocation = new Vector(location.x, location.y - 1);
            labelPixel(newLocation, ref newBuilding);
            checkNeighbours(newLocation, ref newBuilding);
        }
        //Check the pixel below us
        if (location.y != (height - 1) && buildingMapArray2D[location.x, location.y + 1] == Color.black)
        {
            Vector newLocation = new Vector(location.x, location.y + 1);
            labelPixel(newLocation, ref newBuilding);
            checkNeighbours(newLocation, ref newBuilding);
        }
    }

Vector is een klasse bestaande uit een int x en y.

C#:

    class Vector
    {
        public int x, y;

        public Vector(int x, int y)
        {
            this.x = x;
            this.y = y;
        }
    }

Building is een eenvoudige klasse die bestaat uit een lijstje met Vectoren en een kleur die gebruikt wordt als label.

C#:

    class Building
    {
        public List<Vector> buildingPixels;
        public Color32 labelColor;

        public Building(Color32 labelColor)
        {
            this.labelColor = labelColor;
            buildingPixels = new List<Vector>();
        }
    }

De labelPixel functie geeft de pixels een andere kleur en voegt de Vectoren toe aan de lijst uit Building

C#:

    private void labelPixel(Vector location, ref Building building)
    {
        building.buildingPixels.Add(location);
        buildingMapArray2D[location.x, location.y] = building.labelColor;
    }

[Verwijderd]

Het gaat sowieso mis als je 2 zwarte pixels naast of onder elkaar hebt - die 'detecteren' elkaar steeds, en roepen elkaars checkNeighbours steeds aan.

edit: nevermind - gemist dat je die pixel eerst verandert...

[ Voor 19% gewijzigd door Verwijderd op 02-08-2017 16:18 ]

[EddoH]

In recursie niveau van 8000 is al aardig diep IMO. Je moet je afvragen of recursie hier de goede oplossing is.
Ik zou je algoritme herschrijven naar een gewone loop.

Overigens is de .NET stack grootte default 1 MB. Je kunt hem wel vergroten, maar dan moet je wel een goede reden hebben.

[Verwijderd]

Effectief geef je alle zwarte pixels de waarde building.labelColor - dat hoeft dus helemaal niet recursief.

[Maarten Kroon]

EddoH schreef op woensdag 2 augustus 2017 @ 16:19:
In recursie niveau van 8000 is al aardig diep IMO. Je moet je afvragen of recursie hier de goede oplossing is.
Ik zou je algoritme herschrijven naar een gewone loop.

Overigens is de .NET stack grootte default 1 MB. Je kunt hem wel vergroten, maar dan moet je wel een goede reden hebben.

Ik ga het proberen met een loopje ipv.. recursie. Wel jammer want recursie leek me hier juist toepasselijk.

[Maarten Kroon]

Verwijderd schreef op woensdag 2 augustus 2017 @ 16:42:
Effectief geef je alle zwarte pixels de waarde building.labelColor - dat hoeft dus helemaal niet recursief.

labelColor veranderd elke keer dat er een nieuwe blob gevonden wordt. Dus alleen aaneengesloten pixels krijgen dezelfde kleur. Deze code zit elders in het programma.

[Verwijderd]

Dan is het dus eigenlijk een flood fill routine. Wat je daar aan kunt optimaliseren is bijvoorbeeld uitgaan van het vullen van horizontale lijnen, zodat je met een simpele for-loop een serie pixels naast elkaar kunt vullen.

Voor elke pixels kijk je dan of de pixels erboven of eronder gevuld moeten worden, en de pixel links daarvan niet (dat worden twee aparte tests, want vanaf de eerste regel ga je omhoog en omlaag werken). Die pixels stop je in een tijdelijk array, waarbij je ook aangeeft of van daaruit omhoog of omlaag gezocht moet worden.

Als je je eerste lijn hebt getekend ga je dat array langs om te kijken of je erboven of eronder nog wat moet doen. Zo ja, dan heb je het beginpunt voor de lijn, en kun je vandaar weer naar rechts werken, terwijl je weer kijkt of re boven of onder een nieuwe lijn begint.

Voorbeeldje - punt is andere kleur, o is zwarte pixels, en de cijfers zijn ook zwart maar worden verderop uitgelegd. Stel je begint bij >, en zoekt van daar naar rechts voor de eerste zwarte pixel.

JavaScript:

................
................
.....2oooo......
>..1oooooo..5o..
......3ooooooo..
...4oooo........

Je gaat van 1 naar rechts zolang het zwart is, en kijkt erboven en eronder of je daar ook zwart tegenkomt. Dan vind je eerst 2, en daarna 3. Die sla je op (2 = 6, 3 omhoog en 3 = 7, 5 omlaag).

Als je aan het eind komt van de zwarte lijn op regel 4 ga je kijken of er nog wat in je array staat. Nummer 2 is simpel, en bij nummer 3 komt je direct een zwarte pixel eronder tegen. Van daaruit ga je naar links om het begin van die lijn te zoeken, die je vervolgens weer in je array stopt (4, 6 omlaag).

Verder gaand met 3 kom je uiteindelijk 5 tegen (13, 4 omhoog), en als je die afgewerkt hebt ben je klaar met dit vlak en ga je weer op zoek naar het volgende door vanaf het eindpunt van lijn 1 verder te gaan.

edit: oh ja, dit werkt ook recursief, maar per rij en niet per pixel, wat flink zal schelen.

[Maarten Kroon]

Verwijderd schreef op woensdag 2 augustus 2017 @ 17:34:
Dan is het dus eigenlijk een flood fill routine. Wat je daar aan kunt optimaliseren is bijvoorbeeld uitgaan van het vullen van horizontale lijnen, zodat je met een simpele for-loop een serie pixels naast elkaar kunt vullen.

Voor elke pixels kijk je dan of de pixels erboven of eronder gevuld moeten worden, en de pixel links daarvan niet (dat worden twee aparte tests, want vanaf de eerste regel ga je omhoog en omlaag werken). Die pixels stop je in een tijdelijk array, waarbij je ook aangeeft of van daaruit omhoog of omlaag gezocht moet worden.

Als je je eerste lijn hebt getekend ga je dat array langs om te kijken of je erboven of eronder nog wat moet doen. Zo ja, dan heb je het beginpunt voor de lijn, en kun je vandaar weer naar rechts werken, terwijl je weer kijkt of re boven of onder een nieuwe lijn begint.

Voorbeeldje - punt is andere kleur, o is zwarte pixels, en de cijfers zijn ook zwart maar worden verderop uitgelegd. Stel je begint bij >, en zoekt van daar naar rechts voor de eerste zwarte pixel.

JavaScript:

................
................
.....2oooo......
>..1oooooo..5o..
......3ooooooo..
...4oooo........

Je gaat van 1 naar rechts zolang het zwart is, en kijkt erboven en eronder of je daar ook zwart tegenkomt. Dan vind je eerst 2, en daarna 3. Die sla je op (2 = 6, 3 omhoog en 3 = 7, 5 omlaag).

Als je aan het eind komt van de zwarte lijn op regel 4 ga je kijken of er nog wat in je array staat. Nummer 2 is simpel, en bij nummer 3 komt je direct een zwarte pixel eronder tegen. Van daaruit ga je naar links om het begin van die lijn te zoeken, die je vervolgens weer in je array stopt (4, 6 omlaag).

Verder gaand met 3 kom je uiteindelijk 5 tegen (13, 4 omhoog), en als je die afgewerkt hebt ben je klaar met dit vlak en ga je weer op zoek naar het volgende door vanaf het eindpunt van lijn 1 verder te gaan.

edit: oh ja, dit werkt ook recursief, maar per rij en niet per pixel, wat flink zal schelen.

Bedankt voor je antwoord, ik pas nu een soortgelijke methode toe. Als ik een zwarte pixel vind verander ik de kleur en sla ik de locatie op in een lijst. Daarna kijk ik naar de buurpixels. Als deze zwart zijn verander ik de kleur en stop ik ook hun locatie in de lijst. De originele pixel verwijder ik daarna weer uit de lijst.

Ik blijft net zolang door de lijst heen loopen tot deze leeg is (zolang er dus aaneengesloten zwarte pixels gevonden worden). Dit werkt goed en snel.

[Verwijderd]

Bij mijn methode sla je alleen maar 1 pixel per reeks op in die lijst, dus erg lang kan die niet worden.

Maar goed - die methode was geoptimaliseerd voor de tijd dat games nog in 640K moesten passen, en die mate van efficiency is tegenwoordig meestal niet meer nodig.

[P_Tingen]

Wat je nu toepast is het breadth-first algoritme. Zeer geschikt voor dit soort dingen

[Maarten Kroon]

Verwijderd schreef op woensdag 2 augustus 2017 @ 17:52:
Bij mijn methode sla je alleen maar 1 pixel per reeks op in die lijst, dus erg lang kan die niet worden.

Maar goed - die methode was geoptimaliseerd voor de tijd dat games nog in 640K moesten passen, en die mate van efficiency is tegenwoordig meestal niet meer nodig.

De code die ik gebruik is voor een stukje beeldbewerking dat niet realtime hoeft te gebeuren. Binnen enkele seconden is nu de hele afbeelding doorlopen, ik weet zeker dat dit nog sneller kan maar die efficiëntie is voor nu niet nodig. Bedankt voor je hulp!

[Maarten Kroon]

P_Tingen schreef op donderdag 3 augustus 2017 @ 10:06:
Wat je nu toepast is het breadth-first algoritme. Zeer geschikt voor dit soort dingen

Goed om een naam bij het algoritme te hebben, ik zal het algoritme even Googlen en me er op inlezen.