Count objects in a binarized image without scipy

Question

I'm trying to count the number of objects in an image, which I already binarized, however, I'm not allowed to use scipy or numpy packages, therefore I can’t use scipy.ndimage.label, any ideas? My attempt counts over 80 objects, but there are only 13 (counted with scipy)

def label(img):
    n=1
    for i in range(h):
        for j in range(c):
            if img[i][j]==255:
                if img[i-1][j]!=0 and img[i-1][j]!=255:
                    img[i][j]=img[i-1][j]
                elif img[i+1][j]!=0 and img[i+1][j]!=255:
                    img[i][j]=img[i-1][j]
                elif img[i][j+1]!=0 and img[i][j+1]!=255:
                    img[i][j]=img[i][j+1]                    
                elif img[i][j-1]!=0 and img[i][j-1]!=255:
                    img[i][j]=img[i][j-1]
                else:
                    img[i][j]=n
                    if img[i-1][j]!=0:
                        img[i-1][j]=img[i][j]
                    if img[i+1][j]!=0:
                        img[i+1][j]=img[i][j]                        
                    if img[i][j+1]!=0:
                        img[i][j+1]=img[i][j]
                    if img[i][j-1]!=0:
                        img[i][j-1]=img[i][j]                        
                    n+=1
            elif img[i][j]!=0:
                if img[i-1][j]!=0:
                    img[i-1][j]=img[i][j]
                if img[i+1][j]!=0:
                    img[i+1][j]=img[i][j]  
                if img[i][j+1]!=0:
                    img[i][j+1]=img[i][j]  
                if img[i][j-1]!=0:
                    img[i][j-1]=img[i][j]                
    return img,n

Answer 1

You will want something like https://codereview.stackexchange.com/questions/148897/floodfill-algorithm, which implements https://en.wikipedia.org/wiki/Flood_fill. It's a good fit for numba or cython if that's feasible for you.

Perhaps you can use OpenCV, which already offers floodfill: https://docs.opencv.org/3.4/d7/d1b/group__imgproc__misc.html#gaf1f55a048f8a45bc3383586e80b1f0d0.

Suppose you have binarized so background is color one and objects are color zero. Set c = 2, scan for a zero pixel, and floodfill it with color c. Now increment c, scan for zero, fill it, lather, rinse, repeat. You will wind up with each object bearing a distinct color so you can use it as an isolation mask. Distinct colors are very helpful during debugging, but of course three colors suffices (or even two) if you just want a count. The final bitmap will be uniformly the background color in the two-color case.

Using a 4-element Von Neumann neighborhood versus an 8-element neighborhood will make a big difference in the final result. It's easier for paint to "leak" through diagonal connectivity in the 8-element setting. Doing edge detection and thickening can help to reduce unwanted color leakage.