Кандидат наукГоловко А.В.
Национальныйинститут кораблестроения г. Николаева
Определениесвязанного множества пикселей на бинарном изображении
Приведен один изалгоритмов реализации задачи определения связанного множества объектов набинарном изображении. Определены базовые параметры, которые должна определятьфункция. Произведено детальное описание алгоритма, приведена иллюстрация егоработы. Разработана тестовая программа, в которой реализован описанныйалгоритм. Проведен анализ временных параметров работы функции.
Приведений один із алгоритмів реалізації задачі визначеннязв’язаної безлічі об’єктів на бінарному зображенні. Визначені базові параметри,які повинна визначати функція. Проведений детальний опис алгоритму з додаваннямілюстрацій його роботи. Розроблена тестова програма, в якій реалізованийописаний алгоритм. Проведений аналіз тимчасових параметрів роботи функції.
On a binary image one of algorithms of realization of task ofdetermination of the linked great number of objects is resulted. Baseparameters which a function must determine are certain. The detaileddescription of algorithm is made, illustration of his work is resulted. Thetest program the described algorithm is realized in which is developed. Theanalysis of temporal parameters of work of function is conducted.
Обзор.Задача определениясвязанного множества довольно актуальна в вопросах анализа цифровогоизображения. Определение отдельных объектов дает возможность решать большое количествозадач. Одной из основных задач является избавление от шумов и помех вопределении движения, которые появляются в процессе оцифровки аналоговогосигнала. Алгоритм определения связанного множества также используют в задачахраспознавании печатного текста и обнаружения лица на изображении [5].
Существует общая методикарешения поставленной задачи. Одним из вариантов реализации является функция bwlabel, в языке моделирования Matlab. Функция bwlabelищет на бинарном изображении связные области пикселов объектов и создаетматрицу, каждый элемент которой равен номеру объекта, которому принадлежитсоответствующий пиксел изображения.
К недостаткам функции bwlabel следует отнести низкую скоростьвыполнения, а также отсутствие возможности подсчета количества пикселей,которые определяют объект. Возможность определения количества пикселейпринадлежащих объекту является ключевым моментом в задачах распознаваниямашинных номеров, обнаружения лиц, а также фильтрации шумов и помех, влияющиена корректность определения области движения.
Постановка задачи. Разработать алгоритм, которыйпозволит определять связанные множества на бинарном изображении. Предусмотретьвозможность определения количества пикселей, принадлежащих определенномуобъекту. Реализовать алгоритм во внешнем приложении, и произвести анализвременных характеристик работы алгоритма. Максимально оптимизировать программупо временным характеристикам, для возможности использования функции в анализевидеопотока.
Решениезадачи. Связноемножество (область) — множество пикселей, у каждого пикселя которого есть хотябы один сосед, принадлежащий данному множеству. Виды связности:
· 4связность — соседями для пикселя считаются 4 пикселя: сверху, слева, справа,снизу (1).
/> (1)
· 8связность — соседями для пикселя считаются 8 пикселей, т.е. все к немуприлежащие, в том числе и по диагонали (2).
/> (2)
Анализубудет подвергаться монохромное (бинарное) изображение. Бинарное изображение –это изображение, каждый пиксель которого может иметь значение 0 или 1. Будемсчитать, что в нашем изображении 0 – это значение фона, 1 – значениеинтересующего объекта. Уровень связности – 8.
Зададимсябазовыми параметрами, которые должна определять функция поиска связанныхобъектов:
1. Определениеобщего количества связанных объектов.
2. Нумерацияотдельного связанного объекта уникальным индексом, т.е. все пикселя, которыепринадлежат к объекту номер 1, в массиве изображения должны иметь значение 1,принадлежащие к объекту 2 – значение 2, и т.д.
3. Подсчетколичества пикселей, которые определяют каждый объект.
Рассмотримосновной алгоритм работы функции, и переменные, необходимые для ее работы.
Входнымпараметром функции является двухмерный монохромный массив, размерном h – высота и w – ширина изображения,размерностью integer. Хранение бинарного изображения в 32х разрядной переменной имеетследующие предпосылки:
· Нумерациюнайденных связанных объектов можно производить непосредственно в исходноммассиве, что избавляет от необходимости объявления дополнительных переменных,что даст небольшую экономию времени работы всего алгоритма
· Количествосвязанных объектов может достигать 2^32 — верхняя граница данного типа. Размер значительнопревышает количество пикселей, которые могут содержаться в изображении, разрешением1024х768.
· Integer является самым быстрым типом переменных в языке программирования Visual C++, поскольку имеет 32хразрядную адресацию к памяти. Из соображений оптимизации алгоритма по времени,в функции будут использоваться преимущественно переменные с размерностью integer.
Такжев реализации функции участвуют следующие переменные:
· bIndexCount – переменная принимает значение 0 или 1 (флаг первичного счетасвязанных объектов). При инициализации функции обнуляется
· bIsRound – флаг соседства. Принимает значение 1, если в пределах связнойобласти есть хотя бы один сосед, значение которого отлично от 0. В моментинициализации функции имеет значение 0.
· id – значениепикселя в матрице.
· val – значениепикселя в индексном массиве.
· index_count – счетчиксвязанных объектов. В момент инициализации функции имеет значение 2. Этообусловлено тем, что в исходном массиве значение 1 означает наличие объекта.
· index[3][hw] – индексный трехмерный массив. Схема массива приведена нарисунке 4.
Циклыс переменными iи j перебирают все элементыдвухмерного массива mas[i][j]. Во вложенном цикле j происходит проверка на 4граничных условия – верхний ряд, нижний ряд, последний столбец и первый элементмассива (рисунок 1)./> />
Рисунок 1
Послеуспешной проверки граничных условий, происходит выполнение подфункции А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. И.М.Журавель «Обнаружение лиц наоснове цвета».