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

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

Приведений один із алгоритмів реалізації задачі визначення зв'язаної безлічі об'єктів на бінарному зображенні. Визначені базові параметри, які повинна визначати функція. Проведений детальний опис алгоритму з додаванням ілюстрацій його роботи. Розроблена тестова програма, в якій реалізований описаний алгоритм. Проведений аналіз тимчасових параметрів роботи функції.

On a binary image one of algorithms of realization of task of determination of the linked great number of objects is resulted. Base parameters which a function must determine are certain. The detailed description of algorithm is made, illustration of his work is resulted. The test program the described algorithm is realized in which is developed. The analysis 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.

--> ЧИТАТЬ ПОЛНОСТЬЮ <--