Count the number of "holes" in a bitmap

Question

Consider a MxN bitmap where the cells are 0 or 1. '1' means filled and '0' means empty.

Find the number of 'holes' in the bitmap, where a hole is a contiguous region of empty cells.

For example, this has two holes:

11111  
10101  
10101  
11111  

... and this has only one:

11111  
10001  
10101  
11111

What is the fastest way, when M and N are both between 1 and 8?

Clarification: diagonals are not considered contiguous, only side-adjacency matters.

Note: I am looking for something that takes advantage of the data format. I know how to transform this into a graph and [BD]FS it but that seems overkill.

Answer 1

You need to do connected component labeling on your image. You can use the Two-pass algorithm described in the article I linked above. Given the small size of your problem, the One-pass algorithm may suffice.

You could also use BFS/DFS but I'd recommend the above algorithms.

Answer 2

This seems like a nice use of the disjoint-set data structure.
Convert the bitmap to a 2d array
loop through each element
if the current element is a 0, merge it with the set of one its 'previous' empty neighbors (already visited)
if it has no empty neighbors, add it to its own set

then just count the number of sets

Answer 3

There may be advantages gained by using table lookups and bitwise operations.

For example whole line of 8 pixels may be looked up in 256 element table, so number of holes in a field 1xN is got by single lookup. Then there may be some lookup table of 256xK elements, where K is number of hole configurations in previous line, contatining number of complete holes and next hole configuration. That's just an idea.