Introduction

Bitmap hole counting is really a connected-components problem: find empty regions that are enclosed by foreground pixels and do not touch the image border. Once you frame it that way, the problem becomes much more manageable and the implementation is a clean combination of flood fill and graph traversal.

Define What Counts as a Hole

Assume a binary bitmap where 1 means boundary or filled pixel, and 0 means empty space. A fully bound hole is a connected region of 0 pixels that is completely surrounded by 1 pixels.

The key exception is the outer background. Any 0 region that touches the edge of the image is not a hole, because it is open to the outside world.

That means the problem is not "count all zero-regions." It is "count zero-regions that are not connected to the border."

The Standard Algorithm

The most reliable approach has two passes:

1. Mark every background 0 pixel reachable from the image border.
2. Count the remaining unmarked 0 components. Each of those components is a hole.

This works because border-connected empty space can never be enclosed. After removing that outside region from consideration, every remaining empty island is fully bounded.

A Working Python Implementation

The code below uses breadth-first search with a queue. It assumes four-direction connectivity, which is common for grid problems.

1from collections import deque
2
3
4def count_holes(bitmap):
5    rows = len(bitmap)
6    cols = len(bitmap[0]) if rows else 0
7    visited = [[False] * cols for _ in range(rows)]
8    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
9
10    def bfs(start_row, start_col):
11        queue = deque([(start_row, start_col)])
12        visited[start_row][start_col] = True
13
14        while queue:
15            row, col = queue.popleft()
16            for dr, dc in directions:
17                nr, nc = row + dr, col + dc
18                if 0 <= nr < rows and 0 <= nc < cols:
19                    if not visited[nr][nc] and bitmap[nr][nc] == 0:
20                        visited[nr][nc] = True
21                        queue.append((nr, nc))
22
23    # Step 1: mark all background zeros connected to the border
24    for row in range(rows):
25        for col in (0, cols - 1):
26            if cols > 0 and bitmap[row][col] == 0 and not visited[row][col]:
27                bfs(row, col)
28
29    for col in range(cols):
30        for row in (0, rows - 1):
31            if rows > 0 and bitmap[row][col] == 0 and not visited[row][col]:
32                bfs(row, col)
33
34    # Step 2: count zero-components that remain
35    holes = 0
36    for row in range(rows):
37        for col in range(cols):
38            if bitmap[row][col] == 0 and not visited[row][col]:
39                holes += 1
40                bfs(row, col)
41
42    return holes
43
44
45bitmap = [
46    [1, 1, 1, 1, 1, 1],
47    [1, 0, 0, 1, 0, 1],
48    [1, 0, 1, 1, 0, 1],
49    [1, 1, 1, 1, 1, 1],
50]
51
52print(count_holes(bitmap))  # 2

The two enclosed zero-regions in that example are separate holes because they are not connected to each other and neither touches the border.

Why Border Flood Fill Is the Key Insight

If you try to count holes directly, you have to decide for every empty region whether it is enclosed. That can get messy. Border flood fill makes the test trivial: any empty region you can reach from the border is outside, not a hole.

This is a standard pattern in image processing and grid-search problems. You first eliminate the exterior region, then connected-component counting becomes the answer.

Connectivity Changes the Result

You must decide whether pixels are connected in four directions or eight directions. With four-direction connectivity, diagonal touching does not connect two regions. With eight-direction connectivity, it does.

If your bitmap interpretation treats diagonal gaps as open, use eight-direction traversal instead:

1directions = [
2    (1, 0), (-1, 0), (0, 1), (0, -1),
3    (1, 1), (1, -1), (-1, 1), (-1, -1),
4]

The choice depends on the problem definition. In many programming problems, the connectivity rule is what determines whether the final count is correct.

Complexity and Practical Use

The algorithm visits each pixel at most once, so the time complexity is O(rows * cols). The memory cost is also O(rows * cols) because of the visited matrix and the queue in the worst case.

That is efficient enough for many bitmap-analysis tasks, including shape analysis, OCR preprocessing, puzzle grids, and occupancy maps.

If memory is tight, you can sometimes modify the bitmap in place instead of storing a separate visited grid, but that only works when destroying the input is acceptable.

Common Pitfalls

The biggest mistake is counting every zero-component as a hole. Regions connected to the border are background, not enclosed holes.

Another common issue is forgetting to define connectivity clearly. A test case can produce one answer under four-direction rules and a different answer under eight-direction rules.

It is also easy to swap the meaning of 0 and 1. The algorithm still works, but only if you consistently treat one value as empty space and the other as boundary.

Summary

• A fully bound hole is an empty connected region that does not touch the bitmap border.
• The standard solution is border flood fill followed by connected-component counting.
• Four-direction and eight-direction connectivity can change the answer.
• Breadth-first search or depth-first search both work for traversal.
• The overall complexity is linear in the number of pixels.