Fastest Way To Find 4-connected Regions
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)
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
- → What are the pluses/minuses of different ways to configure GPIOs on the Beaglebone Black?
- → Django, code inside <script> tag doesn't work in a template
- → React - Django webpack config with dynamic 'output'
- → GAE Python app - Does URL matter for SEO?
- → Put a Rendered Django Template in Json along with some other items
- → session disappears when request is sent from fetch
- → Python Shopify API output formatted datetime string in django template
- → Shopify app: adding a new shipping address via webhook
- → Shopify + Python library: how to create new shipping address
- → shopify python api: how do add new assets to published theme?
- → Access 'HTTP_X_SHOPIFY_SHOP_API_CALL_LIMIT' with Python Shopify Module