Статья: Определение связанного множества пикселей на бинарном изображении

После успешной проверки граничных условий, происходит выполнение подфункции А1 и (или) А2 и (или) … А5. На рисунке 2 приведен алгоритм работы подфункции А1. Отличие А2 … А5 заключается в индексах массива. Подфункции выполняют проверку соседних элементов проверяемого пикселя, и производят заполнение индексированного массива. Проверка производится 1, 2, 3 и 4го пикселей (2).

Рисунок 2

Рассмотрим работу алгоритма на примере исходного бинарного массива (3). Работа функции начинается с того, что находится первый элемент массива, значение которого 1 (элемент mas[1][5]).

(3)

Элементы 1, 2, 3, 4 (2) равны 0 (поскольку было найдено первое значение, отличное от 0). Этому значению записывается значение переменной index_count (значение при инициализации равно 2), сама переменная инкрементируется. Элемент массива принимает значение 2, index[0][2]=2. Аналогичная ситуация происходит для следующего элемента (предположим что элемент 2 не граничит с элементом 3) и элемента 7. Четвертый найденный элемент граничит со вторым. Значение index[0][2]=2, index[0][4]= index[0][mas[0][2]]=2. Аналогичная ситуация с шестым найденным элементом, который граничит с третьим. Предположим ситуацию, в которой пятый найденный элемент граничит с элементом массива, в котором записано число 4. Однако ранее было определено, что 4й элемент относится ко 2му (4).

(4)

По приведенному алгоритму переменной id присваивается значение найденного элемента, id=4. Переменная val=index[0][id(4)]=2. Операция выполняется до тех пор, пока значение id и val не будут равны. И только после этого index[0][5]=index[0][2]=2. Схематически работа функции приведена на рисунке 4 (заполнение нулевой строки)

После перебора цикла i и j, происходит полное индексирование массива. В переменной index_count хранится количество проиндексированных элементов. Размер массива, после выполнения циклов будет index[3][ index_count].

Подфункция B выполняет окончательную сортировку проиндексированных объектов и подсчет количества пикселей, которые относятся к каждому объекту (Рисунок 2. Заполнение первой и второй строки). Оптимизация таблицы соответствий производится аналогично поиску соседства пятого объекта, т.е. используя переменные id и val и бесконечный цикл while с предусловием равенства переменных. Следует также учесть, что после окончательной сортировки значения в индексном массиве смещаются на одно значение влево. То есть, нумерация найденных объектов начинается с единицы, следовательно, количество пикселей, принадлежащих первому элементу, хранится по адресу index[1][1]=3 (рисунок 4, первая строка). Количество итерация цикла подфункции B равна значению переменной index_count.

Подфункция C формирует массивы выделенных объектов. Каждый элемента исходного массива заменяется по формуле mas[i][j]=index[2][mas[i][j]]. Выходной массив будет выглядеть следующим образом (5).

(5)

Преимущества реализованного метода заключается в том, что существует возможность установить фильтр размера объектов без дополнительных временных затрат. К примеру, объекты, в которых количество элементов меньше 10, исключить из дальнейшего анализа, что поможет избавиться от всяческих помех, а также ускорить дальнейший анализ.

Рисунок 4.

На рисунке 4 приведен интерфейс программы, в которой реализован описанный алгоритм. Основную часть программы занимает графическое окно, в котором можно нарисовать объекты. Предусмотрен интерфейс сохранения и загрузки изображения. Приводятся основные параметры выполнения алгоритма: время выполнения, количество объектов, количество отдельных цветов (переменная index_count) а также количество пикселей в каждом объекте. Каждый распознанный объект выделяется уникальным цветом.

Анализу подвергается изображение, разрешением 320х240. Время выполнения алгоритма изменяется в пределах от 0 до 20 мс, при изменении объектов/цветов от 5/87 до 3300/3400 (случайно сгенерированный набор пикселей).

Выводы

1. Определение связанного множества объектов позволяет производить анализ бинарного изображения и ввести критерий размера объекта. Это возможно благодаря тому, что функцией производится подсчет количества пикселей, которые определяют объект.

2. Время анализа довольно мало, что позволяет использовать приведенный алгоритм в задачах анализа потокового видео.

3. Работа функции с бинарным изображением накладывает соответствующие ограничения на входные данные. При решении задач, связанных с анализом цветных либо полутоновых изображений, необходимо предусмотреть механизмы конвертирования, что также приведет к дополнительным потерям времени.

Литература

1. Гонсалес Р., Вудс Р., Эддинс С. Цифровая обработка изображения в среде MATLAB. Москва 2006 г.

2. Б. Пахомов. C/C++ и MS Visual C++ 2008 для начинающих. БХВ-Петербург, 2008 г.

3. Александр Вежневец. Выделение связных областей в цветных и полутоновых изображениях. Компьютерная графика и мультимедиа. Выпуск №4(4)/2003.

4. И.М.Журавель "Типы изображений".

5. И.М.Журавель "Обнаружение лиц на основе цвета".