Đếm số "lỗ hổng" trong bitmap

Question

Xem xét bitmap MxN trong đó các ô là 0 hoặc 1. '1' có nghĩa là đã điền và '0' có nghĩa là trống.

Tìm số lượng lỗ '' trong bitmap, trong đó lỗ là vùng tiếp giáp của ô trống.

Ví dụ, điều này có hai lỗ:

11111 
10101 
10101 
11111 

... và điều này chỉ có một:

11111 
10001 
10101 
11111 

gì là cách nhanh nhất, khi M và N đều giữa 1 và số 8?

Làm rõ: đường chéo không được coi là tiếp giáp, chỉ các vấn đề phụ kề nhau.

Lưu ý: Tôi đang tìm kiếm thứ gì đó tận dụng được định dạng dữ liệu. Tôi biết làm thế nào để biến đổi điều này thành một đồ thị và [BD] FS nó nhưng điều đó có vẻ quá mức cần thiết.

Answer 1

Bạn cần làm connected component labeling trên hình ảnh của mình. Bạn có thể sử dụng số Two-pass algorithm được mô tả trong bài viết Wikipedia tôi đã liên kết ở trên. Với kích thước nhỏ của vấn đề của bạn, One-pass algorithm có thể đủ.

Bạn cũng có thể sử dụng BFS/DFS nhưng tôi khuyên bạn nên sử dụng các thuật toán trên.

Answer 2

Điều này có vẻ như là sử dụng tốt đẹp cấu trúc dữ liệu được phân tách.
Chuyển đổi bitmap vào một mảng 2ngày
lặp qua mỗi phần tử
nếu các yếu tố hiện tại là 0, kết hợp nó với các thiết lập của một trong các nước láng giềng 'trước' rỗng (đã truy cập)
nếu nó không có hàng xóm rỗng , thêm nó vào thiết lập riêng của nó

sau đó chỉ cần đếm số lượng các bộ

Answer 3

có thể có lợi thế đạt được bằng cách sử dụng tra cứu bảng và các hoạt động trên bit.

Ví dụ: toàn bộ dòng 8 pixel có thể được tra cứu trong bảng phần tử 256, do đó số lỗ trong trường 1xN được nhận bằng tra cứu đơn lẻ. Sau đó, có thể có một số bảng tra cứu các phần tử 256xK, trong đó K là số cấu hình lỗ trong dòng trước đó, số lượng lỗ hoàn chỉnh và số lỗ tiếp theo. Đó chỉ là một ý tưởng.