CODEWITHSUNDEEP
image-processingf#stack-overflow
EinsL
EinsL

Reputation: 73

Why is the recursive function throwing a stack overflow exception?

I'm implementing a fill holes algorithm, the value of byte 0 is used as the background because I need to implement a floodfill algorihtm first.
My code is giving me a Stack Overflow Exception if I use the check8 for the position of TopLeft, Left or BotLeft of my current pixel.
But its fine if I just use the Top, TopRight, Right, BotRight and Bot.
I checked using the instruments-allocation tool and yes I was getting a lot of malloc calls. But I don't know why it is behaving like that.

let FillHoles (img : Bitmap) =
    let bd = img.LockBits(Rectangle(0,0,img.Width,img.Height),ImageLockMode.ReadWrite,PixelFormat.Format32bppArgb)
    let mutable (p:nativeptr<byte>) = NativePtr.ofNativeInt (bd.Scan0)

    let rec check8 (point:nativeptr<byte>) x y =
        try 
            if (x>=0 && x<=img.Width-1 && y>=0 && y<=img.Height-1)then
                if((NativePtr.get point 0)=(byte 0)) then
                    NativePtr.set point 0 (byte 255)
//                  if (x<>0) then
//                      check8 (NativePtr.add point -4) (x-1) y //Left -4
//                  if (x<>0 && y<>0) then
//                      check8 (NativePtr.add point -(bd.Stride + 4)) (x-1) (y-1) //TopLeft
                    if (y<>0) then
                        check8 (NativePtr.add point -(bd.Stride)) x (y-1) //Top
                    if (x<>img.Width-1 && y<>0) then
                        check8 (NativePtr.add point -(bd.Stride - 4)) (x+1) (y-1)  //TopRight
                    if (x<img.Width-1) then
                        check8 (NativePtr.add point 4) (x+1) y //Right
                    if (x<>img.Width-1 && y<>img.Height-1) then
                        check8 (NativePtr.add point (bd.Stride + 4)) (x+1) (y+1) //BotRight
                    if (y<>img.Height-1) then
                        check8 (NativePtr.add point (bd.Stride)) x (y+1) //Bot
//                    if (x<>0 && y<>img.Height-1) then
//                        check8 (NativePtr.add point (bd.Stride - 4)) (x-1) (y+1) //BotLeft
        with
            | :? System.NullReferenceException as ex -> (printfn "%A" ex.Message)
            | :? System.StackOverflowException as ex -> (printfn "%A" ex.Message)

    for row in 0 .. img.Height-1 do
        for col in 0 .. img.Width-1 do
            if (row=0 || row=img.Height-1 || col=0 || col=img.Width-1) then
                check8 p row col
            p <- NativePtr.add p 4
        done
    done
    img.UnlockBits(bd)
    img

Upvotes: 0

Views: 204

Answers (2)

Daniel
Daniel

Reputation: 47904

A tail call cannot occur in a try-catch. See How are tail calls compiled? in this blog post by the F# Team.

Upvotes: 2

EinsL
EinsL

Reputation: 73

I was trying to do a tail recursive flood fill but I ran out of time so I implemented it with a stack.
The recursive one I couldn't debug it properly, my IDE was behaving strangely all the stack frames probably were messing with it.
There is probably a more functional approach.

let FloodFill (img : Bitmap) =
    let bd = img.LockBits(Rectangle(0,0,img.Width,img.Height),ImageLockMode.ReadWrite,PixelFormat.Format32bppArgb)

    let check4 x y =
        let (checkPointer:nativeptr<byte>) = NativePtr.add (NativePtr.ofNativeInt (bd.Scan0)) (bd.Stride*y+x*4)
        if(NativePtr.get checkPointer 0 = byte 0) then
            let st = Stack()
            st.Push(x,y)
            while(st.Count > 0) do
                let current = st.Pop()
                let xx = fst current
                let yy = snd current
                let (pointer:nativeptr<byte>) = NativePtr.add (NativePtr.ofNativeInt (bd.Scan0)) (bd.Stride*yy+xx*4)
                NativePtr.set pointer 0 (byte 255)

                if(xx+1<=img.Width-1)then
                    let (point:nativeptr<byte>) = NativePtr.add (NativePtr.ofNativeInt (bd.Scan0)) (bd.Stride*yy+(xx+1)*4)
                    if(NativePtr.get point 0 = byte 0) then
                        st.Push(xx+1,yy)
                if(xx-1>=0)then
                    let (point:nativeptr<byte>) = NativePtr.add (NativePtr.ofNativeInt (bd.Scan0)) (bd.Stride*yy+(xx-1)*4)
                    if(NativePtr.get point 0 = byte 0) then
                        st.Push(xx-1,yy)
                if(yy+1<=img.Height-1)then
                    let (point:nativeptr<byte>) = NativePtr.add (NativePtr.ofNativeInt (bd.Scan0)) (bd.Stride*(yy+1)+xx*4)
                    if(NativePtr.get point 0 = byte 0) then
                        st.Push(xx,yy+1)
                if(yy-1>=0)then
                    let (point:nativeptr<byte>) = NativePtr.add (NativePtr.ofNativeInt (bd.Scan0)) (bd.Stride*(yy-1)+xx*4)
                    if(NativePtr.get point 0 = byte 0) then
                        st.Push(xx,yy-1)

    for row in 0 .. img.Height-1 do
        for col in 0 .. img.Width-1 do
            if (row=0 || row=img.Height-1 || col=0 || col=img.Width-1) then
                check4 row col
        done
    done
    img.UnlockBits(bd)
    img

Upvotes: 0

Related Questions