GPU blob bounding box connected component labeling

Question

I have a binary image that will have one or more blobs. I want a list of pixels for each blob. If I can find one seed point for each blob, I can flood fill to find the pixels of the blob.

Doing some research for this problem, I think the algorithm I want is "Connected component labeling." Most examples I see just color code the blobs output. With this algorithm will I be able to gather: one point on the blob, and the axis aligned bounding box of the blob?

Does connected component labeling sound like the right algorithm for what I need? Does anyone have a good CUDA implementation?

Yes, connected components is what you want. If you have an image with each blob labeled a different color the bounding box can trivially be computing by taking the maximum and minimum pixel coordinate for each color in the image. — jodag
A CUDA implementation is arduous because processing is heavily data dependent and irregular. Splitting the image in subimages is also difficult because you have to patch the pieces up after processing the tiles. — Yves Daoust

Yves Daoust Yves Daoust · Accepted Answer · 2017-08-09T07:21:26

Your suggestion is a good starting point.

Scan the image row by row and when you meet a black pixel start flood filling it. While you fill, you can keep the bounding box updated. After filling, you just continue the scan.

Fill(img, x, y, xm, xM, ym, yM):
    img[x][y]= white
    xm= min(xm, x); xM= max(xM, x); ym= min(ym, y); yM= max(yM, y);
    if x >= 0 and img[x-1][y] == black:
        Fill(img, x-1, y)
    if x < w  and img[x+1][y] == black: 
        Fill(img, x+1, y)
    if y >= 0 and img[x][y-1] == black: 
        Fill(img, x, y-1)
    if y < h  and img[x][y+1] == black: 
        Fill(img, x, y+1)

FloodFill(img):
    for y in range(h):
        for x in range(w):
            if Img[x][y] == black:
                xm= xM= x; ym= yM= y
                Fill(img, x, y, xm, xM, ym, yM)
                Store(x, y, xm, xM, ym, yM)

As flood filling is stack-intensive, a scanline-based approach is recommended.

GPU blob bounding box connected component labeling

1 Answers