terminated by signal SIGSEGV (Address boundary error) on python program with reccursive methods

Question

I am trying to read all the touching pixels with the same color in a image.

For that I use reccursive functions. When I check one pixel, I look on the right, left, top and bottom if the pixel close to it is the same color. If it is I add it to an array otherwise I don't.

The code is as follow:

vimport tkinter as tk
from PIL import Image

import sys
sys.setrecursionlimit(200000)

## WINDOWS
# to launch in debug mode
imgToDraw = Image.open('assets-test\\smile-face.png')
# to launch normaly
# imgToDraw = Image.open('..\\assets-test\\smile-face.png')
## LINUX
# imgToDraw = Image.open('../assets-test/smile-face.png')

imgPixels = imgToDraw.load()

imgWidth = imgToDraw.size[0]
imgHeight = imgToDraw.size[1]

# an element is a part of the image, it's a bunch of pixels with approximately the same color
# and each pixel touch at least one other pixel of the same element
elements = [];

isPixelChecked = [[ False for y in range( imgWidth ) ] for x in range( imgHeight )]

# min tolerable difference between two colors to consider them the same
# the higher the value is the more colors will be considered the same
COLOR_TOLERANCE = 10

reccursionCount = 0

class Element:
    def __init__(self, color):
        self.pixels = [];
        self.color = color;
    
    def addPixel(self, pixel):
        self.pixels.append(pixel);

class Pixel:
  def __init__(self, x, y, color):
    self.x = x # x position of the pixel
    self.y = y # y position of the pixel
    self.color = color # color is a tuple (r,g,b)

def cutImageInElements():
    global element
    completeElement(element.pixels)

def completeElement(elemPixels):
    global reccursionCount
    global isPixelChecked
    reccursionCount += 1

    nbPixels = len(elemPixels);
    xIndex = elemPixels[nbPixels - 1].x
    yIndex = elemPixels[nbPixels - 1].y
    xRightIdx = elemPixels[nbPixels - 1].x + 1
    xLeftIdx = elemPixels[nbPixels - 1].x - 1
    yBottomIdx = elemPixels[nbPixels - 1].y + 1
    yTopIdx = elemPixels[nbPixels - 1].y - 1

    isPixelChecked[xIndex][yIndex] = True
    if((xRightIdx < imgWidth) and isPixelChecked[xRightIdx][yIndex] == False):
        if(isColorAlmostSame(imgPixels[elemPixels[0].x, elemPixels[0].y], imgPixels[xRightIdx, yIndex])):
            pixelAppended = Pixel(xRightIdx, yIndex, imgPixels[xRightIdx, yIndex])
            elemPixels.append(pixelAppended)
            
            completeElement(elemPixels)
    
    if((xLeftIdx >= 0) and isPixelChecked[xLeftIdx][yIndex] == False):
        if(isColorAlmostSame(imgPixels[elemPixels[0].x, elemPixels[0].y], imgPixels[xLeftIdx, yIndex])):
            pixelAppended = Pixel(xLeftIdx, yIndex, imgPixels[xLeftIdx, yIndex])
            elemPixels.append(pixelAppended)

            completeElement(elemPixels)

    if((yBottomIdx < imgHeight) and isPixelChecked[xIndex][yBottomIdx] == False):
        if(isColorAlmostSame(imgPixels[elemPixels[0].x, elemPixels[0].y], imgPixels[xIndex, yBottomIdx])):
            pixelAppended = Pixel(xIndex, yBottomIdx, imgPixels[xIndex, yBottomIdx])
            elemPixels.append(pixelAppended)

            completeElement(elemPixels)
    
    if((yTopIdx >= 0) and isPixelChecked[xIndex][yTopIdx] == False):
        if(isColorAlmostSame(imgPixels[elemPixels[0].x, elemPixels[0].y], imgPixels[xIndex, yTopIdx])):
            pixelAppended = Pixel(xIndex, yTopIdx, imgPixels[xIndex, yTopIdx])
            elemPixels.append(pixelAppended)

            completeElement(elemPixels)
    

def isColorAlmostSame(pixel1, pixel2):
    redDiff = abs(pixel1[0] - pixel2[0])
    greenDiff = abs(pixel1[1] - pixel2[1])
    blueDiff = abs(pixel1[2] - pixel2[2])
    if(redDiff < COLOR_TOLERANCE and greenDiff < COLOR_TOLERANCE and blueDiff < COLOR_TOLERANCE):
        return True
    else:
        return False

def printPixelsArr(pixelsArr):
    for x in range(0, len(pixelsArr)):
        print(pixelsArr[x].x, pixelsArr[x].y, pixelsArr[x].color)
        
if __name__ == '__main__':
    pixel = Pixel(0, 0, imgPixels[0, 0]);
    element = Element(pixel.color);
    element.addPixel(pixel);
    cutImageInElements();
    print("NbReccursive call: ", reccursionCount)

This code works for small images of size 100x100 but crashes with an image of 400x400 with the error "terminated by signal SIGSEGV (Address boundary error)" when I launch the program on wsl2. When I run the program on cmd or powershell it just crashes but with no error code/msg.

I cannot understand why it would work with some size of images and not others. I can only think that the memory runs out or something but in the task manager the program uses almost no memory.

Answer 1

Not sure why that's failing, but that much recursion in Python isn't a great idea. I'd suggest reading about tail recursion that other languages use to make some recursive algorithms consume constant stack space. Note that your algorithm is not tail recursive, so this optimisation wouldn't help even if Python supported it.

I hacked together the following flood fill implementation. It uses Numpy so that it's only 10x slower than Pillow's ImageDraw.floodfill.

import numpy as np

def floodfill(im, row, col, threshold):
    similar = np.mean(np.abs(im - im[row, col]), 2) < threshold
    mask = np.zeros_like(similar)
    mask[row, col] = 1
    m2 = mask.copy()
    while True:
        m2[:,:] = mask
        m2[1:,:] |= mask[:-1]
        m2[:-1,:] |= mask[1:]
        m2[:,1:] |= mask[:,:-1]
        m2[:,:-1] |= mask[:,1:]
        m2 &= similar
        if np.all(m2 == mask):
            return mask
        mask[:,:] = m2

As an example of using this, you could do;

import requests
from io import BytesIO

res = requests.get("https://picsum.photos/300")
res.raise_for_status()

src = Image.open(BytesIO(res.content))

mask = floodfill(np.array(src, int), 10, 10, 40)

where the random image I got and the output mask are: