Параллельный алгоритм выделения однородных сегментов изображения

Известия ТРТУ

Специальный выпуск

Рабочая среда подсистемы - Windows 3,1 или Windows 95. Среда разработки - Visual Basic 3,0. Программа занимает около 500 Кбайт, объем, занимаемый одним городом в базе данных, - 50 байт.

УДК 681.03.06

Б.И. Левин ПАРАЛЛЕЛЬНЫЙ АЛГОРИТМ ВЫДЕЛЕНИЯ ОДНОРОДНЫХ СЕГМЕНТОВ ИЗОБРАЖЕНИЯ

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

Для выделения объектов на изображении был разработан следующий двух,

градиента в пределах некоторой ограниченной зоны. Для этого все точки исходного изображения первоначально считаются несвязанными. В ходе анализа каждой несвязанной точки считается, что она может принадлежать объекту с начальными цветовыми компонентами (R,G,B) и центром (X,Y), соответствующими положению и характеристикам самой точки. Если в окрестностях такой точки находится некоторая другая несвязная точка, которая удалена от центра объекта на расстоя-,

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

Описанный метод можно рассматривать как модифицированный метод Брайса и Феннема, с введенными дополнительными ограничивающими порогами, для , . можно говорить о выполнении условий слияния областей: две области R1 и R2 и

периметры P1 и Р2 сливаются, если выполняются условия D/ min{Pl,P2} > £2 или D/C > £з , где C - длина общей границы; D-даина участка границы, на котором A Y < £1 ( AY - перепад яркости); £1 , £2, и £з - пороговые значения. На второй фазе сегментации данные от каждого процессора, представляющие собой описания субсегментов изображения, объединяются в единые сегменты по методу Брайса и Феннема. Значительное снижение объема данных после проведения пред-

Секция вычислительной техники

варительной сегментации позволяет резко повысить производительность системы и добиться равномерной загрузки процессоров.

УДК 681.03.06

АЛ. Костюк РЕКУРСИВНО-ИЕРАРХИЧЕСКАЯ СИСТЕМА ОБРАБОТКИ ВИДЕОИНФОРМАЦИИ

Вводимые в ЭВМ видеоданные (или, более широко, информационное поле) представляются в виде некоторой регулярной, иерархической, не зависящей от содержания данных структуры. Эта структура описывается рекурсивно, путем указания элементарной ячейки и закона ее развития. Специальная нумерация элемен-, , исходного многомерного скалярного или векторного поля и работать с плоским графом (ре^лярным деревом), сохраняющим в то же время все свойства много.

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

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

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