Подсчитайте количество «отверстий» в растровых изображениях

Question

Рассмотрим растровое изображение MxN, где ячейки равны 0 или 1. «1» означает заполнение, а «0» означает «пусто».

Найдите количество «отверстий» в растровом изображении, где отверстие является смежной областью пустых ячеек.

Например, это имеет два отверстия:

11111 
10101 
10101 
11111 

... и это имеет только один:

11111 
10001 
10101 
11111 

Что является самым быстрым способом, когда M и N являются как между 1 и 8?

Уточнение: диагонали не считаются смежными, только вопросы со стороны смежности.

Примечание: Я ищу что-то, что использует формат данных. Я знаю, как преобразовать это в график и [BD] FS, но это кажется излишним.

Answer 1

Вам необходимо сделать connected component labeling на Ваше изображение. Вы можете использовать Two-pass algorithm, описанные в статье I Википедии, приведенной выше. Учитывая небольшой размер вашей проблемы, может быть достаточно One-pass algorithm.

Вы также можете использовать BFS/DFS, но я бы рекомендовал вышеуказанные алгоритмы.

Answer 2

Это похоже на приятное использование структуры данных с несвязанными наборами.
Преобразование растрового изображения в 2d массива
петли через каждый элемент
если текущий элемент является 0, объединить его с набором из одного его «предыдущих» пустых соседей (уже посещенных)
, если он не имеет пустых соседей , добавить его в свой собственный набор

затем просто посчитать количество комплектов

Answer 3

Там могут быть преимущества, полученные с помощью табличного поиска и операции побитового.

Например, целая линия из 8 пикселей может быть просмотрена в таблице 256 элементов, поэтому число отверстий в поле 1xN получается путем однократного поиска. Тогда может быть какая-то таблица поиска из 256xK элементов, где K - это количество конфигураций отверстий в предыдущей строке, что соответствует количеству полных отверстий и конфигурации следующего отверстия. Это просто идея.