Fastest way to find 4-connected regions-CodePudding

I have a 2D numpy array filled with values in range [0,1] and I want to loop on the 4-connected region where value < 0.2. In order to do that, I currently go through all pixels of the array and check each of its neighbours recursively to find the corresponding region. However, I feel this a common problem and there exists a more efficient way to do this. What is the fastest way to achieve this?

def pixel_neighbours_4way(pixel_coord: Union[np.ndarray, List, tuple]) -> np.ndarray:
    assert len(pixel_coord) == 2, "pixel coordinates (pixel_coord) must be of length 2"

    neighbours = np.array([[0, 1], [0, -1], [1, 0], [-1, 0]])

    return neighbours   pixel_coord


def grow_region(origin_pixel, difference_map):
    region_pixels = [origin_pixel]

    # Mark pixel as already visited
    difference_map[origin_pixel] = 1

    idx = 0

    while idx < len(region_pixels):
        for neigh_pixel in pixel_neighbours_4way(region_pixels[idx]):
            if difference_map[neigh_pixel] <= self.rho:
                region_pixels.append(neigh_pixel)
                # Mark pixel as already visited
                difference_map[neigh_pixel] = 1

        idx  = 1

    return region_pixels



my_array = np.random.rand(500, 500)

for x in range(500):
  for y in range (500):
    if my_array[x, y] <= 0.2:
      region = grow_region((x, y), my_array)
      my_processing(region)

CodePudding user response：

1. Raster scan method

process the image row by row and detect the runs of "white" pixels;
from one row to the next, match the runs that overlap by at least one pixel;
use the union-find technique to form the blobs.

2. Simple contouring method

scan the image row by row until you hit a "white" pixel;
start following the contour, marking the pixels with some convention; when you are back, continue the scan;
when you meet a marked pixel, jump to the one facing it.

If the region has holes, this second method will not detect them. But if there is just one region without holes, the method can be fast as it will not explore all pixels.

3. Full contouring

Refer to "Satoshi Suzuki and others. Topological structural analysis of digitized binary images by border following. Computer Vision, Graphics, and Image Processing, 30(1):32–46, 1985."

Note that your 4-ways filling method is not so bad, but has a big weakness: it can require huge stack space. An algorithm better in this respect is available in Graphics Gems: https://github.com/erich666/GraphicsGems/blob/master/gems/SeedFill.c