автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Исследование и разработка алгоритмов визуального анализа и представления данных в физических приложениях

ГОСУДАРСТВЕННЫЙ НАУЧНЫЙ ЦЕНТР РОССИЙСКОЙ ФЕДЕРАЦИИ

ИНСТИТУТ ФИЗИКИ ВЫСОКИХ ЭНЕРГИИ

I НБР

РГБ од

4 - двг ет

98-36 На правах рукописи

Матвеев Сергей Владимирович

ИССЛЕДОВАНИЕ И РАЗРАБОТКА АЛГОРИТМОВ ВИЗУАЛЬНОГО АНАЛИЗА И ПРЕДСТАВЛЕНИЯ ДАННЫХ В ФИЗИЧЕСКИХ ПРИЛОЖЕНИЯХ

05.13.11— математическое и программное обеспечение вычислительных машин,

комплексов, систем и сетей

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Протвино 1998

М-2

УДК 519.85;681.3.06

Работа выполнена в Институте физики высоких энергий (г.Протвино).

Научный руководитель - кандидат технических наук В.Н. Кочин.

Официальные оппоненты: доктор физ.-мат. наук Е.В. Шикин (МГУ), кандида! физ.-мат. наук В.А. Куликов (ИФВЭ).

Ведущая организация - Филиал института ядерной физики СО РАН (г. Протвино).

Защита диссертации состоится "_" _ 1998 г. I

_часов на заседании диссертационного совета К034.02.01 по адресу: 142284.

г. Протвино Московской области.

С диссертацией можно ознакомиться в библиотеке ИФВЭ.

Автореферат разослан "_" _ 1998 г.

Ученый секретарь

диссертационного совета К034.02.01 В.Н.Ларин

© Государственный научный центр Российской Федерации Институт физики высоких энергий, 1998

Общая характеристика работы

Актуальность задачи

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

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

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

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

• Исследование и решение проблем, возникающих при визуализации объемных скалярных полей, заданных на грубых сетках.

• Разработка методов выделения из двоичных двумерных данных (изображений) элементов заданной формы.

Научная новизна

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

2. Исследована проблема топологической неоднозначности возникающей в алгоритме движущегося кубика (marching cube). Разработан новый подход к решению этой проблемы на гранях. Вводится понятие критерия сложности топологии аппроксимируемой изоповерхности. Предложен новый способ получения топологически корректной изоповерхности внутри кубика.

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

Практическая ценность

Алгоритм визуализации поведения заряженной частицы в электромагнитных полях использован для визуального анализа и представления результатов моделирования движения вторичных электронов в калориметре.

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

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

Автор защищает:

• Разработку алгоритма представления и последующей обработки 2-мерных бинарных данных в виде блочной структуры. Алгоритм выделения блоков заданной формы из данных.

• Метод решения проблемы получения топологически корректной изоповерхности внутри объема с данными, заданными на грубой сетке. Способ решения проблемы неоднозначности на гранях в методе движущегося кубика. Критерий оценки сложности топологии поверхности, аппроксимируемой внутри кубика.

• Способ визуального анализа поведения заряженной частицы в электрических полях сложной конфигурации.

Апробация работы и публикации

Результаты, положенные в основу диссертационной работы, опубликованы в работах [1-5] и докладывались на научных семинарах ИФВЭ, на международных школах "Автоматизация исследований, конструирования и производства" в 1992 г.

; Обнинске и в 1993 г. в Дубне, на Российско-германском семинаре в РАН в .993 г., на "IEEE Workshop on Visualization and Machine Vision" в июне 1994 г. Seattle , USA), на Международной конференции "Visualization'94" в октябре 1994 г. Washington DC, USA), на Международной конференции "Visual Data Exploration ,nd Analysis II" в феврале 1995 г. (San Jose, USA), на семинаре "Automatische Analyse von Tomographie-Daten" в апреле 1996 г. (München, Germany).

Структура диссертации

Диссертация состоит из введения, четырех глав, заключения и списка литературы. Объем диссертации 78 страниц, включая 34 рисунка и 1 таблицу. Список штературы содержит 87 наименований.

Содержание работы

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

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

На выбор методов обработки и представления данных влияют типы данных 1 способы их получения. Тип данных определяется размерностью координатного 1ространства данных и размерностью пространства параметров и зависит от типа оучаемого физического явления.

Одним из источников получения данных может быть дискретный физический грибор. В этом случае мы будем иметь некоторую последовательность 2-мерных *аборов данных (сечений). Эти сечения могут быть затем подвергнуты процедуре 2-мерной реконструкции в объемные наборы данных путем связывания сечений и интерполяции данных между ними. Другим источником данных является N-мерная математическая модель физического процесса.

Таким образом, метод визуального анализа 3-мерных данных может включать i себя алгоритмы обработки изображений (image processing) на стадии получения, а затем уже непосредственно алгоритмы объемной визуализации. Визуальный шализ n-мерных данных — это работа с проекциями этих данных в 3-мерное 1ространство.

Важным элементом обработки изображений является процедура сегментации (image segmentation) исходного изображения. Сегментация означает идентификацию границ изображения. Другими словами, это алгоритмы представления изображения э виде набора неперекрывающихся областей, объединение которых даст исходное изображение.

Наиболее активной частью научной визуализации является объемная визуали зация. Объемная визуализация, это процесс проецирования многомерных множест: данных на двумерную плоскость изображения для того, чтобы получить правильно' представление о структуре (или ее отсутствии) объемной информации. Чаще всег множество данных определено на трехмерной решетке с одной или с нескольким] скалярными или векторными величинами в каждом узле решетки.

Объемные данные обычно представляются в виде массива объемных элемен тов — вокселов (voxel) или массива ячеек (cell). Эти два подхода объясняютс: необходимостью дискретизации объема в узлах сетки во время процесса отобра жения данных. Дискретизация, требующая интерполяции данных, присутствуе' почти в каждом алгоритме объемной визуализации.

Для отображения (rendering) объемного набора данных объемные элементы мо гут непосредственно проецироваться или "переводиться" в 2-мерную плоскост] пикселов в виде растра в буфере кадра. Этот процесс, который называется прямыв отображением объема (direct volume rendering) DVR, включает в себя процедурь просмотра и закраски (полутоновой обработки) объемной картинки.

Наиболее часто используемый алгоритм прямых методов объемной визуализа ции — алгоритм выброса луча.

С другой стороны, объемные данные могут быть сначала преобразованы в reo метрические примитивы в результате процесса, называемого оконтуриванием ил! выделением изоповерхности (isocontouring, is о surfacing). Затем геометрические при митивы (набор полигонов или контуров) отображаются на экран традиционным! средствами машинной графики. Этот процесс называется отображением поверхно сти (surface rendering) SR и включает в себя оконтуривание, просмотр и полуто новую обработку объемной картинки.

К непрямым методам относятся алгоритм непрозрачного куба (opaque cube о cuberille), алгоритм Maching cubes, использующий подход "разделяй и властвуй' для построения поверхности внутри логического (воображаемого) куба, созданной из восьми пикселов, каждые четыре из которых принадлежат разным сечениям.

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

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

Для проектирующихся экспериментов на су перко л лай дер ах требуются детекто ры, работающие в условиях больших радиационных нагрузок (до 1 Град/год) i

Рис. 1. Канал транспортировки.

обладающие малым, до 30 не, временем сбора заряда, образующегося при прохождении релятивистских частиц через рабочее вещество детектора.

В.И. Рыкалиным и Г.С. Бицадзе1'2 был предложен новый тип калориметра, основанный на регистрации медленных вторичных эмиссионных электронов, проходящих через абсорбер.

Основной проблемой стала разработка канала транспортировки вторичных электронов, обеспечивающего малое время их сбора. Вторичный электрон вылетает из произвольной точки внешней поверхности канала (г0,г2) и имеет любой, физически допустимый угол вылета (см. рис. 1). Выбор начальной кинетической энергии электрона осуществлялся с использованием энергетического спектра вторичных электронов, выбитых релятивистскими электронами или протонами.

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

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

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

F = F(t,p,ß,z,W,Q(a,<p)),

Г

Рис. 2. Углы эмиссии.

где £ — время; р, ¡3, г — координаты в цилиндрической системе координат; УУ — начальная кинетическая энергия частицы; 0(а, <р) — углы вылета (см. рис. 2).

При фиксированных значениях УУ начальной кинетической энергии и угле вылета электрона 0(а, <р) получается траектория движения частицы в канале. Начальная энергия частицы может меняться в пределах IV 6 {УУтт! Жши}, и угол вылета может лежать в пределах некоторого телесного угла 0таа:. Это сильно усложняет задачу как по количеству разыгрываемых событий, удовлетворяющих указанным выше условиям, так и по возможностям графического представления получаемых

1Bitsadze G.S. et al. "On the possibility of design of secondary emission flight type calorimeter", 3rd Workshop on Physics at XJNK, Protvino, Russia, p.21., Sept. 1990.

2Bitsadze G.S. et al. "Module of electromagnetic secondary emission flight type calorimeter", Nuclear Instruments and Methods in Physics Research, A 334, pp. 399- 408, 1993.

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

Исследовалось поведение потока частиц с набором энергий {Wi, W2, •••, Wn} при фиксированном угле вылета 0(а, ip)=const. Затем фиксировалась энергия частиц W=const и в качестве параметра использовалась функция 0(а, (р).

В этом случае задача разбивается на две:

— 0(а, ц> = const) (рис. 3),

— 0(а = const, ip) (рис. 4).

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

На рис. 5-8 показаны потоки частиц в калориметре при различных значениях параметров. В случае осаждения частицы на стенках или на нити траектория прерывается. Движение частиц происходит по направлению к наблюдателю. На рис. 5 показан пучок вторичных электронов с фиксированным углом вылета и различными энергиями. Виден фокусирующий эффект добавочного поля. Геометрически все частицы лежат на поверхности конуса. Касание стенки электроном в этом случае возможно только в начале траектории.

На рис. б вторичные электрону имеют одну энергию 1 эВ. Все частицы лежат в пределах; телесного угла. Видно, что в данном случае электроны образуют довольно плотный пучок. Пучок при движении прецессирует вокруг оси коаксиала. В случае слабого фокусирующего поля касание стенок происходит за счет прецессии пучка. Интересный результат получается в случае, когда изменяется угол в плоскости, перпендикулярной оси коаксиала Q(a=const,<p) (см. рис. 4). На рис. 7 видно, что пучок состоит из двух поверхностей с точкой разрыва при (р= const. В случае увеличения энергии частиц до 4 эВ весь пучок осаждается на стенках и на нити (см. рис. 8).

Рис. 3. W=const, 0(а,<р = const)

Рис. 4. W=const,Q(a=const,ip).

Рис. 5. Пучок вторичных электронов с фиксированным углом вылета и различными энергиями.

Рис. 6. Вторичные электроны имеют одну энергию 1 эВ. Все частицы лежат в.пределах телесного угла 0.

Рис. 7. Переменный угол в плоско- Рис. 8. То же, но с энергией 4 эВ.

сти перпендикулярной оси ко-аксиала 0(a=const,<p); энергия 2 эВ.

В третьей главе исследуется проблема топологической неоднозначности, возникающей при визуализации объемных скалярных данных методом движущегося кубика (Marching Cube). Описывается новый способ решения этой проблемы на гранях кубика. Дается описание предложенного автором критерия оценки сложности топологии аппроксимируемой внутри кубика изоповерхности. Описывается новый метод получения топологически корректной изоповерхности внутри кубика.

Алгоритм движущегося кубика3 разработан для визуализации трехмерного набора скалярных данных Fijk — F(x, у, z), заданных в узлах прямоугольной объемной решетки, в виде изоповерхностей:

Sp = {(x,y,z):F(x,y,z) = l3y

(1)

3Lorensen W.E. and Cline H.E. "Marching Cubes: A High-Resolution 3D Surface Construction Algorithm". SIGGRAPH 87 Conference Proceedings, Computer Graphics, Vol. 21, No. 4, July 1987, pp.163-169.

С учетом симметрии 256 различных вариантов пересечений поверхности с гранями куба могут быть сведены к 14 типам пересечений. Данный набор называется таблицей соответствия (lookup-table). Для каждого кубика производится анализ типа пересечения с изоповерхностью и выбирается вариант из таблицы соответствия. Однако последующий анализ выявил ряд проблем, которые возникают при использовании данного метода.

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

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

ников (в общем случае полигонов), х корректно аппроксимирующих изопо-

верхность.

Автором предложен следующий

Рис. 9. Ячейка.

метод решения указанных проблем. Пусть в узлах кубика задано восемь значений функции В{ (см. рис. 9). Естественным описанием функции внутри ячейки будет трилинейная интерполяция.

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

F(x, у, z) = а + Ьх + су + dz + еху + /х z + дух + Ьcyz,

где 0 < х < 1,0 < у < 1, 0 < z < 1. Константы определяются:

(2)

а =

Ь = Bi — Bi,

с в4 — Bi,

d = в$ — В1,

е = B3 -f B\ — Bi -BA

f = Be + B\ — Bi -B5

9 = B& + B\ — B4 -Bs

h = Вт + B5 + В4 + B2

(3)

-■»в,

Решение на грани ячейки

На гранях ячейки уравнение (2) дает билинейное описание пересечения изопо-верхности и грани. Для анализа поведения функции на грани будем использовать проекцию грани в единичный квадрат. Тогда поведение функции на грани в локальных u, v будет описываться уравнением

F( u, v) = а + bu + cv + ¿uv, (4)

где 0 < и < 1, 0 < v < 1.

Для прямой u = const уравнение (4) будет зависеть только от одной переменной

F(u = const, v) = F(v),

(5)

и, следовательно, будет иметь не более чем один корень на отрезке от 0 до 1, т.е. не более чем одно пересечение с изоповерхностью. Отсортируем точки пересечения ребер с изоповерхностью по и и соединим их в данной последовательности попарно. В этом случае будет удовлетворено правило "одного пересечения". При этом для v = const это правило удовлетворяется автоматически.

Решение внутри ячейки

Теперь рассмотрим поведение функции внутри ячейки. В качестве критерия сложности топологии поверхности будем использовать количество ее пересечений с диагоналями кубика (см. рис. 10).

В случае трех пересечений (рис.Юг) топологию поверхности известными способами восстановить невозможно. Необходимо получение дополнительных точек, принадлежащих изо-цоверхности внутри кубика.

Построим на диагоналях кубика шесть прямоугольных сечений, каждое из которых определяется двумя диагоналями (см. рис. 11):

¿>1476 (точки Ви В4, В7, Вв), 5*2385> ¿"тв) 5З456, <$1573 И 52684-Здесь индексы сечения опреде-пяются номерами узлов кубика, на которых они построены.

А

у \Л

/

ч

^ (

г

б)

е)

г)

Типы пересечений с диагональю.

/ /1 \ А

% X

/

У /

/Л

/ А

г

- - 7\

Рис. 11. Конфигурация сечений.

Введем локальную переменную связанную с положением точки на диагонали (см. рис. 12). Можно показать, что смещению по трем координатным осям, связанным с началом диагонали, соответствует смещение по диагонали I = £\/3-

Тогда уравнения, описывающие поведение функции на диагоналях В\ — Вт, В2 — Ва, В4 — Ве, В5 — Вз соответственно, есть

0 = a, + (Ь + c + d)U(e + f + g)e + he,

= а + Ь + (-Ъ + с + Л + е + /)1; +

+ {-z-f+9+h)e-hi\

= а + с + (Ъ-с + <1+е + д)(+ (6)

+ (-е + / - * + Л)*а - Л*3,

= а + <1 + {Ь + с-с1 + / + д)£ +

где 0 < £ < 1.

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

\ 4

// V\ s

//Щ

Рис. 12. Координата на диагонали. Рис. 13. Сечение 53456 в локальных координатах.

Рассмотрим сечение £3456, показанное на рис. 13. Перейдем в локальную систему координат (u,v), связанную с этим сечением. Тогда для прямой u = const уравнение (2) будет иметь линейную зависимость

F(£, const, const) = F(Q,

а для прямой v = const — квадратичную зависимость

F{const,l-£,£) = F{£2).

(7)

(8)

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

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

{Ь, г,..., Ь, Ь,г, ...,г, 6, Ь,..., Ь}, где Ь(оип<1агу) — граничные точки; 1(пз1с1е) — внутренние точки; а набор изолиний

{М, *>}, {Ь,г, Ъ}, {6,..., Ь}.

Будем считать, что точки являются узлами графа, а отрезки — его дугами (см. рис. 14). Здесь отмечены точки принадлежащие границе ячейки (лежащие на гранях), а — точки, находящиеся внутри. Принадлежность каждой из четырех диагоналей куба трем сечениям позволяет получить объемный набор отрезков (соединений) внутри куба. Построим матрицу смежности данного графа

/о ... 1 ... 1 ..Л

О 0 ... 1 ......

0 0 О ... 1 ...

adj =

ООО

0

(9)

Рис. 14. Граф соединений точек изоповерх-ности в кубе.

Здесь 0 в позиции ij означает отсутствие соединения между точками i и j, а 1 — наличие соединения или nqyTH, равного 1. При этом элементы главной диагонали и элементы под главной диагональю равны 0, так как нам достаточно учесть только один раз, что узел г соединяется с узлом j.

Теперь рассмотрим выражение

(аф'(г, 1) and adj(l,j)) or (adj(i,2) and adj(2,j)) or ... (10)

or (аф'(т, 1) and adj(m,j))}

где and и or — операции логического и и или.

В этом выражении каждый элемент строки г матрицы смежности умножается на соответствующий элемент столбца j той же матрицы. Если хотя бы одна из фигурных скобок равна 1, то значение всего выражения равно 1. Это означает, что существует путь длиной 2 из узла г в узел j. Из этого же выражения можно определить, через какой узел графа соединяются эти узлы. Так, например, если

(adj{i% к) and adj(k,j)) = 1, (11)

то точки г и j соединяются через точку к.

Из формулы (10) видно, что а<1]2(1,,)) — это элемент (г^) матрицы асЦ2, которая равна булеву произведению матрицы смежности на себя. Что в общем случае запишем следующим образом:

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

Элемент (г, ]) получившейся матрицы асЦ12 равен 1 в случае, если узлы i и ] являются вершинами треугольника. Третий узел можно определить из выражения (10), которое использовалось для построения матрицы аф2.

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

Четвертая глава посвящена разработке алгоритмов и программного обеспечения, предназначенных для сегментации и последующей обработки 2-мерных бинарных данных в виде блочной структуры. Дается описание разработанного автором однопроходного алгоритма выделения блоков в данных. Представлены псевдокоды алгоритмов.

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

Электронная голограмма состоит из элементов 10x10 мкм, каждый из которых "рисуется" за 10 — 20 проходов лазерного луча. Таким образом, для записи голограммы 12x12 мм требуется более 106 элементов. Устройство, записывающее голограмму, может быть запрограммировано на прорисовку элементов различного размера. То есть поле, состоящее и ЫхМ одинаковых элементов может быть представлено и записано как один элемент. Сокращение времени на позиционирование лазерного луча при переходе от одного элемента к другому, позволяет писать голограммы большого размера (так как система, требующая позиционирования, нестабильна во времени).

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

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

аф'2 = асЦ ® асЦ.

(12)

а^12 = аф апс1 асЦг.

(13)

Предложенный диссертантом алгоритм состоит из трех фаз:

I. Исходное изображение подвергается процедуре пороговой обработки. В результате получается набор двоичных сечений, каждое из которых соответствует определенному интервалу полутонов (цветов).

II. Алгоритм присвоения пикселам меток, определяемых соседними пикселами.

III. Извлечение блочных регионов, с заранее определенной формой.

Фазы II и III применяются последовательно ко всем двоичным сечениям:

for each binary slice {

do pixels "labelling" phase (II) do blocks segmentation phase (III)

}

Фаза присвоения "меток" — это однопроходный алгоритм линейного сканирования двоичного изображения. "Метка" пиксела £(х, у) определяется наличием в трех соседних позициях пикселов, принадлежащих объекту (см. рис. 15). В терминах теории множеств

Таблица

определим следующую морфологическую операцию:

«>з

(14)

где маска представляется матрицей

'(1) M

m

(ьЛ =

4 2

f(x> у) f(x+i> y)

\ + 0x01

+ 5 4,

/(х.У+1) f(x+ly+l)

Рис. 15. Присвоение пикселу.

Hex

0x00 0x01 0x02 0x03 0x04 0x05 0x06 0x07 0x08

Bin

0000 0001 0010 0011 0100 0101 ОНО 0111 1111

Phase I

0 0

0 0

I 0

0 0

1 1

0 0

1 0

0 1

1 1

0 1

1 0

1 0

1 1

1 0

1 0

1 1

1 1

1 1

Phase II

0 0

0 0

1 0

0 0

2 1

0 0

3 0

0 1

4 1

0 1

5 0

1 0

6 1

1 0

7 0

1 1

8 1

1 1

Все возможные случаи присвоения "меток" показаны в таблице. Из таблицы можно видеть, что для хранения информации о "метке" достаточно четырех бит. Используется стандартный набор блоков в соответствии с требованиями постпроцессора. Это может быть набор с ограниченным числом типов (формы) блоков, или ограниченным типом и размером. Например, можно использовать блоки в форме квадратов с произвольными или ограниченными размерами в форме горизонтальных, вертикальных или наклонных линий. Набор блоков может быть любой произвольной формы, которая должна быть описана в процедурах извлечения блоков. Каждому набору блоков соответствует набор функций, которые осуществляют проверку на принадлежность пиксела какому-либо блоку из набора. Тест на принадлежность горизонтальной линии имеет следующий код:

function HorLineTest(x, у)

if ( f(x,y) == 0x02 or f(x,y) == 0x04 or f(x,y) == 0x06)

than return(TRUE) else return(FALSE)

Аналогично определяются другие функции тестирования. Следует заметить, что тестирование пикселов должно начинаться с проверки на принадлежность к блокам, имеющим более сложную топологию. (Если сначала извлечь из изображения все линейные элементы, то ни одного 2-мерного элемента после этого не останется).

Следующий шаг — это разработка функций извлечения блоков заданной формы и удаления этих блоков из изображения. При удалении пиксела /(¡с, у) из изображения необходимо изменить "метки" соседних пикселов. Псевдокод функции, которая удаляет пиксел из изображения реализован следующим образом:

function remove(х, у)

if (f(x-l,y)^0x00 and х^0 than h(x-l,y) = f(x-l, у) - 0x01

if (f(x-l, y-l)^0x00 and хф 0 and y^0) than h(x-l, y-1) = f(x-l, y-1) - 0x02 if (f(x, y-l)^0x00 and y^0) than h(x, y-1) = f(x, y-1) - 0x04

h(i, j) = 0x00

Внутри этой функции проводится проверка на наличие у соседних пикселей метки фона. На основе функций тестирования и удаления пикселов реализуются функции, которые извлекают из изображения блоки заданной формы, удаляют их и изменяют "метки" соседних пикселов.

В Заключении сформулированы основные результаты диссертации.

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

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

• Предложен алгоритм сегментации и последующей обработки 2-мерных бинарных данных в виде блочной структуры, реализованный в виде:

— однопроходной процедуры преобразования бинарных данных в 2-мерный набор "меток";

— однопроходной процедуры выделения блоков заданной формы, основанный на анализе "меток";

— процедуры удаления блока из данных и изменения соответствующих "меток" .

Список литературы

.] Матвеев С.В. Аппроксимация изоповерхности в методе движущегося кубика: неоднозначность на гранях: Препринт ИФВЭ 93-133. — Протвино, 1993.

!] Матвеев С.В. Представление изображения в виде укрупненной блочной структуры: Препринт ИФВЭ 97-89. — Протвино, 1997.

!] Matveyev S.V. Resolving the Topological Ambiguity in Approximating the Isosurface of Scalar Function. // Proceedings of IEEE Workshop on Visualization and Machine Vision, 1994, pp. 18-21.

I] Matveyev S.V. Approximation of Isosurface in the Marching Cube: Ambiguity Problem. // Proceedings of Visualization'94, IEEE Computer Society Press. Washington DC, 1994, pp. 288-292.

)] Matveyev S.V., Ryabov A.D., Ryabova T.D. and Rykalin V.I. Visualization for Modelling of Charged Particles Behaviour inside Electromagnetic Complex Fields. // Proceedings of Visual Data Exploration and Analysis II, San Jose, SPIE 1995, vol 2410, pp. 155-160.

Рукопись поступила 27 мая 1998 г.