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:

... and this has only one:

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.

Why does this smell of either homework or code-golf? @Florin, thanks for the update. Please consider this remark "rescinded". We'll take your word. — jcolebrand, Oct 26 '10 at 16:59
It is not homework, but it doesn't matter. I'm trying to solve a bigger problem and this is just a subproblem. — florin, Oct 26 '10 at 17:02
Are the holes only orthogonal connected? Or is diagnonal also allowed? — Peer Stritzinger, Oct 26 '10 at 17:02
The fastest way depends strongly how the bitmaps are stored before the algorithm. NxM Matrix or bitfields or? — Peer Stritzinger, Oct 26 '10 at 17:04
@Peer Stritzinger ~ Since he calls it a bitfield I think we can assume a bitmap. Additionally, we can easily convert this ahead of time into an NxM matrix before processing, so I think it's safe to assume we have a rectangular matrix with easily defined `(i-1,j-1)...(i+1,j+1)` neighbors for calculations sake. — jcolebrand, Oct 26 '10 at 17:06
@Sam Dufel - upside-down does not matter - the number of holes is the same. — florin, Oct 26 '10 at 18:09
The Euler number or Euler characteristic will give you the number of holes. And it can be computed just by examining each 2x2 neighborhood once. Here’s a nice write up: https://sydney4.medium.com/the-euler-number-of-a-binary-image-1d3cc9e57caa — Cris Luengo, Oct 07 '21 at 20:03

score 22 · Accepted Answer · edited Nov 04 '16 at 12:46

22

You need to do connected component labeling on your image. You can use the Two-pass algorithm described in the Wikipedia 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.

edited Nov 04 '16 at 12:46

murrayc

2,103
4
17
32

answered Oct 26 '10 at 17:01

Jacob

34,255
14
110
165

1

Yes, connected component labeling should do the trick. Also, congrats to 10k, @Jacob (or almost - I guess you hit rep-cap for today). – Jonas Oct 26 '10 at 18:00
@Jonas: I know! Hopefully florin will accept this answer today :) – Jacob Oct 26 '10 at 19:02
@Jonas: I can acknowledge the congrats now :D – Jacob Oct 26 '10 at 22:03
I slightly changed Two-pass algorithm but the main idea is there https://gist.github.com/atonamy/3c50f63aebdecc9b881756e889fb5278 give your comments if solution looks acceptable for coding interview – Arsenius Apr 11 '20 at 11:06

Sam Dufel · Answer 2 · 2010-10-26T17:28:55.230

6

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

edited Oct 26 '10 at 17:28

answered Oct 26 '10 at 17:07

Sam Dufel

17,560
3
48
51

I wrote this answer before looking at his. – Sam Dufel Oct 26 '10 at 17:26

score 0 · Answer 3 · answered Oct 26 '10 at 19:36

0

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.

answered Oct 26 '10 at 19:36

Vovanium

3,798
17
23

I just started building my 2^64 lookup table, but I ran out of the budget for the year for RAM 8^) – florin Oct 26 '10 at 21:07
florin: Use distributed computing! =) – Vovanium Oct 26 '10 at 21:14
I found this puzzle very interesting and I spent some free time to make a sketch of 'line by line' algorithm with lookups and bitwise operations, using only 560 bytes of tables (for 8 bit wide patterns). Here's the code: http://dl.dropbox.com/u/13343791/holecount2.c Sorry if code not well documented. – Vovanium Nov 03 '10 at 12:14

score 0 · Answer 4 · answered Oct 08 '21 at 09:48

I wrote an article describe the answer on Medium https://medium.com/@ahmed.wael888/bitmap-holes-count-using-typescript-javascript-387b51dd754a

but here is the code, the logic isn't complicated and you can understand it without reading the article.

export class CountBitMapHoles {
    bitMapArr: number[][];
    holesArr: Hole[] = [];
    maxRows: number;
    maxCols: number;

    constructor(bitMapArr: string[] | number[][]) {
        if (typeof bitMapArr[0] == 'string') {
            this.bitMapArr = (bitMapArr as string[]).map(
                (word: string): number[] => word.split('').map((bit: string): number => +bit))
        } else {
            this.bitMapArr = bitMapArr as number[][]
        }
        this.maxRows = this.bitMapArr.length;
        this.maxCols = this.bitMapArr[0].length;
    }

    moveToDirection(direction: Direction, currentPosition: number[]) {
        switch (direction) {
            case Direction.up:
                return [currentPosition[0] - 1, currentPosition[1]]

            case Direction.down:
                return [currentPosition[0] + 1, currentPosition[1]]

            case Direction.right:
                return [currentPosition[0], currentPosition[1] + 1]

            case Direction.left:
                return [currentPosition[0], currentPosition[1] - 1]

        }
    }
    reverseDirection(direction: Direction) {
        switch (direction) {
            case Direction.up:
                return Direction.down;
            case Direction.down:
                return Direction.up
            case Direction.right:
                return Direction.left
            case Direction.left:
                return Direction.right
        }
    }
    findNeighbor(parentDir: Direction, currentPosition: number[]) {
        let directions: Direction[] = []
        if (parentDir === Direction.root) {
            directions = this.returnAvailableDirections(currentPosition);
        } else {
            this.holesArr[this.holesArr.length - 1].positions.push(currentPosition)
            directions = this.returnAvailableDirections(currentPosition).filter((direction) => direction != parentDir);
        }
        directions.forEach((direction) => {
            const childPosition = this.moveToDirection(direction, currentPosition)
            if (this.bitMapArr[childPosition[0]][childPosition[1]] === 0 && !this.checkIfCurrentPositionExist(childPosition)) {
                this.findNeighbor(this.reverseDirection(direction), childPosition)
            }
        });
        return
    }
    returnAvailableDirections(currentPosition: number[]): Direction[] {
        if (currentPosition[0] == 0 && currentPosition[1] == 0) {
            return [Direction.right, Direction.down]
        } else if (currentPosition[0] == 0 && currentPosition[1] == this.maxCols - 1) {
            return [Direction.down, Direction.left]
        } else if (currentPosition[0] == this.maxRows - 1 && currentPosition[1] == this.maxCols - 1) {
            return [Direction.left, Direction.up]
        } else if (currentPosition[0] == this.maxRows - 1 && currentPosition[1] == 0) {
            return [Direction.up, Direction.right]
        } else if (currentPosition[1] == this.maxCols - 1) {
            return [Direction.down, Direction.left, Direction.up]
        } else if (currentPosition[0] == this.maxRows - 1) {
            return [Direction.left, Direction.up, Direction.right]
        } else if (currentPosition[1] == 0) {
            return [Direction.up, Direction.right, Direction.down]
        } else if (currentPosition[0] == 0) {
            return [Direction.right, Direction.down, Direction.left]
        } else {
            return [Direction.right, Direction.down, Direction.left, Direction.up]
        }
    }
    checkIfCurrentPositionExist(currentPosition: number[]): boolean {
        let found = false;
        return this.holesArr.some((hole) => {
            const foundPosition = hole.positions.find(
                (position) => (position[0] == currentPosition[0] && position[1] == currentPosition[1]));
            if (foundPosition) {
                found = true;
            }
            return found;
        })

    }

    exec() {
        this.bitMapArr.forEach((row, rowIndex) => {
            row.forEach((bit, colIndex) => {
                if (bit === 0) {
                    const currentPosition = [rowIndex, colIndex];
                    if (!this.checkIfCurrentPositionExist(currentPosition)) {
                        this.holesArr.push({
                            holeNumber: this.holesArr.length + 1,
                            positions: [currentPosition]
                        });
                        this.findNeighbor(Direction.root, currentPosition);
                    }
                }
            });
        });
        console.log(this.holesArr.length)
        this.holesArr.forEach(hole => {
            console.log(hole.positions)
        });
        return this.holesArr.length
    }
}
enum Direction {
    up = 'up',
    down = 'down',
    right = 'right',
    left = 'left',
    root = 'root'
}

interface Hole {
    holeNumber: number;
    positions: number[][]
}

main.ts file

import {CountBitMapHoles} from './bitmap-holes'

const line = ['1010111', '1001011', '0001101', '1111001', '0101011']
function main() {
    const countBitMapHoles = new CountBitMapHoles(line)
    countBitMapHoles.exec()
}

main()

score -1 · Answer 5 · answered Sep 28 '21 at 13:51


function BitmapHoles(strArr) { 
    let returnArry = [];
    let indexOfZ = [];
    let subarr;
     for(let i=0 ; i < strArr.length; i++){
       subarr = strArr[i].split("");
      let index = [];
      for(let y=0 ; y < subarr.length; y++){
        if(subarr[y] == 0)
        index.push(y);
        if(y == subarr.length-1)
        indexOfZ.push(index);
      }
    }
    for(let i=0 ; i < indexOfZ.length; i++){
        for(let j=0; j<indexOfZ[i].length ; j++){
          if(indexOfZ[i+1] && (indexOfZ[i][j]==indexOfZ[i+1][j] || indexOfZ[i+1].indexOf(indexOfZ[i][j])))
          returnArry.indexOf(strArr[i]) < 0 ? returnArry.push(strArr[i]): false;
          if(Math.abs(indexOfZ[i][j]-indexOfZ[i][j+1])==1)
          returnArry.indexOf(strArr[i]) < 0 ? returnArry.push(strArr[i]): false;
        }
    }
    
      return returnArry.length; 
    
    }
       
    // keep this function call here 
    console.log(BitmapHoles(readline()));

This answer might be more useful if you explain how the code works and how it relates to the question. — Cris Luengo, Aug 13 '22 at 14:24

Areeb Ahmad · Answer 6 · 2022-08-13T12:55:36.300

-1

function findHoles(map) {
    let hole = 0;

    const isHole = (i, j) => map[i] && map[i][j] === 0;

    for (let i = 0; i < map.length; i++) {
        for (let j = 0; j < map[i].length; j++) {
            if (isHole(i, j)) {
                markHole(i, j);
                hole++;
            }
        }
    }

    function markHole(i, j) {
        if (isHole(i, j)) {
            map[i][j] = 2;
            markHole(i, j - 1);
            markHole(i, j + 1);
            markHole(i + 1, j);
            markHole(i - 1, j);
        }
    }

    return hole;
}

edited Aug 13 '22 at 12:55

answered Aug 13 '22 at 12:53

Areeb Ahmad

1
3

3

This answer might be more useful if you explain how the code works and how it relates to the question. – Cris Luengo Aug 13 '22 at 14:24

Count the number of "holes" in a bitmap

6 Answers6