Get n largest regions from binary image

Question

I have given a large binary image (every pixel is either 1 or 0).

I know that in that image there are multiple regions (a region is defined as a set of neighboring 1s which are enclosed by 0s).

The goal is to find the largest (in terms of pixel-count or enclosed area, both would work out for me for now)

My current planned approach is to:

• start an array of array of coordinates of the 1s (or 0s, whatever represents a 'hit')

• until no more steps can be made:

  • for the current region (which is a set of coordinates) do:

  • see if any region interfaces with the current region, if yes add them togther, if no continue with the next iteration

My question is: is there a more efficient way of doing this, and are there already tested (bonus points for parallel or GPU-accelerated) implementations out there (in any of the big libraries) ?

Answer 1

You want to use connected component analysis (a.k.a. labeling). It is more or less what you suggest to do, but there are extremely efficient algorithms out there. Answers to this question explain some of the algorithms. See also connected-components.

This library collects different efficient algorithms and compares them.

From within Python, you probably want to use OpenCV. cv.connectedComponentsWithStats does connected component analysis and outputs statistics, among other things the area for each connected component.

With regards to your suggestion: using coordinates of pixels rather than the original image matrix directly is highly inefficient: looking for neighbor pixels in an image is trivial, looking for the same in a list of coordinates requires expensive searchers.

Answer 2

You could Flood Fill every region with an unique ID, mapping the ID to the size of the region.