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

На правах рукописи

ЧАПЛЫГИН АЛЕКСАНДР АЛЕКСАНДРОВИЧ

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

Специальность 05.13.05 - Элементы и устройства вычислительной техники и систем управления

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

Курск-2005

Работа выполнена на кафедре программного обеспечения вычислительной техники в Государственном образовательном учреждении высшего профессионального образования «Курский государственный технический университет» Министерства образования и науки Российской Федерации

Научный руководитель - доктор технических наук, профессор

Довгаль Виктор Митрофанович

Официальные оппоненты: д.т.н., профессор Бурмака A.A.

к.т.н., доцент Лушникова Е.И.

Ведущая организация: ОКБ «Авиаавтоматика» (г. Курск)

Защита состоится «<?<$» 42- 2005 г. в /^ часов на заседании диссертационного совета Д 212.105.02 при Курском государственном техническом университете по адресу: 305040, г. Курск, ул. 50 лет Октября, 94 (конференц-зал).

Заверенные отзывы на автореферат в двух экземплярах направлять по адресу: 305040, г. Курск, ул. 50 лет Октября, 94, ученому секретарю диссертационного совета Д 212.105.02.

С диссертацией можно ознакомиться в библиотеке Курского государственного технического университета.

Автореферат разослан « 2$ » //_2005 г.

Ученый секретарь диссертационного совета, /

канд. техн. наук /^СГЁ. А. Титенко

po/>6 -*

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

Решению проблем визуализации объектов многомерного пространства посвятили свои работы А.И Галушкин, К. Фу, К. Пирсон, К Фукунага, Н.Г. Загоруйко, P.C. Лбов и другие отечественные и зарубежные авторы.

К наиболее распространенным методам визуализации объектов многомерного пространства в интерактивных системах принятия решений относятся нелинейные R-отображения <p: Rn—»R2. При визуализации объектов многомерного пространства рассматриваемые образы могут быть вытянуты вдоль одного или нескольких параметров или иметь сложный топологический портрет. Такие образы называются пространственно распределенными. Между тем в результате использования нелинейных R-отображений для визуализации пространственно распределенных образов часто возникают ситуации их ложного пересечения, в результате чего может произойти ошибочное принятие решения. Это обстоятельство определяет основную проблемную ситуацию данного диссертационного исследования. В системах принятия решений обрабатываемые данные носят преимущественно многомерный характер с большим числом признаков, что требует для визуализации значительных временных затраты. Для сокращения времени визуализации, требуются аппарат-но-технические средства акселерации. Сущность основной решаемой задачи заключается в развитии существующих методов и разработке аппаратно-технических средств для визуализации точечных многомерных объектов в пространственно распределенных образах со сложными топологическими портретами на основе нелинейных отображений. На основании изложенного тема диссертационной работы является перспективной и актуальной. Работа выполнялась в рамках НИР по гранту Г02-4.2-5 (2002-2005 г.г.) «Разработка методов, алгоритмов, программных и технических средств быстрых символьных вычислений» при непосредственном участии автора.

Объектом исследования являются многомерные пространства,

включающие в себя объекты с больа i

БИБЛИОТЕКА I

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

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

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

1) анализ существующих методов визуализации объектов многомерного пространства и обоснование необходимости развития существующих методов для визуализации пространственно распределенных образов со сложными топологическими портретами;

2) разработка метода и алгоритма секущих гиперплоскостей как развитие метода нелинейного отображения объектов многомерного пространства;

3) разработка устройства визуализации пространственно распределенных образов со сложными топологическими портретами, реализующего метод секущих гиперплоскостей;

4) моделирование устройства визуализации, получение его временных характеристик и сравнение с аналогичными устройствами визуализации.

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

Научная новизна работы заключается в следующем:

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

2) разработан алгоритм секущих гиперплоскостей, который за счет сокращения количества циклов вычислений позволяет сократить время визуализации объектов п-мерного пространства;

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

Практическая ценность работы состоит в следующем:

построенный новый алгоритм метода секущих гиперплоскостей реализован виде программных продуктов «Навигатор» и «Нави-гатор-2» для решедия практически важных задач в различных областях принятия решений;

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

На защиту выносятся:

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

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

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

Апробация работы. Основные положения диссертационной работы докладывались на международных и российских конференциях: "Распознавание - 2003" (г. Курск, 2003 г.), "Медико-экологические информационные технологии - 2003, 2004 (г. Курск, 2003, 2004 гг.), "Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации" (г. Курск, 2003 г.), а также в научно-практическом вестнике «Человек и его здоровье» (г. Курск, 2005 г.).

Результаты работы внедрены на кафедрах дерматовенерологии и гистологии Курского государственного медицинского университета, в НПО «Экран» Минздрава РФ. Акты внедрения прилагаются к материалам диссертации.

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

Личный вклад автора в работы, написанные в соавторстве, заключается в разработке метода секущих гиперплоскостей [4,5], основных алгоритмических построениях [6,7] и в создании предпосылок к разработке устройства визуализации [1,2] с последующим моделированием его работы [3].

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

ОСНОВНОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИОННОЙ РАБОТЫ

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

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

Для задач визуализации характерно, что большие объемы обрабатываемых данных имеют высокую размерность п » 3, а результирующие данные должны иметь размерность от 1 до 3.

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

К основным линейным методам визуализации данных относятся: метод главных компонент (МГК), факторный анализ, линейный дискриминант-ный анализ, разложение Корунена-Лоева.

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

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

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

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

ский синтез 1-автомата, что создает предпосылки к сокращению аппаратных затрат за счет минимизации и обобщения микроопераций.

Во второй главе рассматриваются математические аспекты нелинейного отображения и развитие метода нелинейного Л-отображения путем разработки метода секущих гиперплоскостей.

Нелинейное ^отображение включает в себя 2 преобразования, последовательно выполняемых для каждой точки исследуемой совокупности:

1. Ъ-отображение точки г п-мерного пространства Р° на плоскость II-отображения (линейная часть).

2. 8-отображение полученной точки двумерного пространства Р2 (нелинейная часть).

Линейное отображение ставит в соответствие каждому вектору г = ('г1, г2,...,г„) из п-мерного пространства Р" вектор я = двумерного про-

странства Р2. Линейное отображение представляет собой ортогональную проекцию го вектора г на Р) в базисе оьо2.

Ортогональная проекция вектора г на Р| в базисе оьо2 имеет вид:

го = а^! + а2о2, (1)

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

где

(2)

01

Рис. 1 Проекция точки многомерного пространства на плоскость

В основе Б-отображения лежит преобразование, позволяющее при переходе из пространства Р° в пространство Р2 оставить неизменным расстояние от определенной фиксированной точки до всех остальных точек исследуемого множества. Направление для осуществления Б-отображения в двумерном пространстве Р2 задается прямой, проходящей через начало координат и точку я = (аь а2).

В качестве меры близости объектов в исходном признаковом пространстве Р" и в 2-мерном пространстве Р2 при Я-отображении используется евклидово расстояние, вычисляемое по формуле

Это расстояние откладывается от начала координат вдоль прямой, проходящей через начало координат и точку я (рис. 2).

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

Пусть коэффициенты а!... а„задают угол наклона гиперплоскостей, а А<3 = с!)- &г - расстояние между ними. Тогда уравнения гиперплоскостей будут иметь вид:

(3)

aiXj + a2x2 + ... + anx„ = d2

(4)

аре, + а2х2 + ... + апхп = й2 (5)

При режиме отсечения гиперплоскостями отображаются только те объекты, которые лежат между гиперплоскостями. Для того чтобы определить расположение точки с координатами в], в2, ... V мевду гиперплоскостями, вычисляется расстояние <1:

(1 = а^! + а2з2 + ... + а,,^ (6)

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

Если <1] < с1 < d2, то точка лежит между гиперплоскостями и должна отображаться, в противном случае точка лежит в пределах отсекаемой части пространства и отображаться не должна.

При визуализации пространственно распределенных образов исследуется срез пространства в местах возможного пересечения образов или в окрестности сложной топологической структуры (впадины, выпуклости и

др)-

При алгоритмизации метода нелинейного отображения традиционно использовалась матричная форма линейного отображения:

г,

п п п

-1 -COS

71 /ГСО-!)-. — 1),

—...—cos(— —-)...—cos(—--)

n n n

(7)

Это линейное отображение реализуется в виде цикла из п итераций. Затем необходимо рассчитать эвклидово расстояние по формуле (3), что требует еще один цикл из п итераций.

Новизна предлагаемого алгоритма заключается в использовании одного цикла из п итераций вместо двух. В этом цикле будет накапливаться результат линейного отображения, скалярного произведения исходного вектора на самого себя для последующего извлечения квадратного корня и получения евклидова расстояния и скалярного произведения исходного вектора на нормаль к гиперплоскости, необходимого для отсечения. Для реализации S-отображения полученный в результате линейного преобразования вектор нормализуется и умножается на скаляр, представляющий собой значение эвклидова расстояния. Подобный алгоритм позволяет сократить время вычисления координат многомерного объекта для отображения на плоскости. При алгоритмизации были введены следующие обозначения: п - размерность пространства, v - исходный вектор размерностью п, Vj - i-й элемент исходного вектора, х,у - координаты получившейся точки на плоскости, dist - эвклидово расстояние, angle - угол наклона текущей оси координат, angle step - угол между соседними осями координат, 1еп - длина получившегося после линейного преобразования вектора, а, - i-й элемент век-

тора нормали, d, - свободный член уравнения первой гиперплоскости, d2 -свободный член уравнения второй гиперплоскости, flag - результат отсечения, если flag = 1, то исходная точка лежит между гиперплоскостями, в противном случае точка находится вне гиперплоскостей и должна быть отсечена. Алгоритм метода секущих гиперплоскостей представлен на рисунке

3.

Рис. 3 Схема алгоритма секущих гиперплоскостей

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

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

Устройство визуализации представляет собой операционное устройство, работающее под управлением хост-машины. Структурная схема устройства представлена на рисунке 4.

Рис. 4 Операционное устройство визуализации пространственно распределенных образов

Операционное устройство состоит из управляющего автомата Мура и операционного I-автомата. Управляющий автомат посылает операционному автомату управляющие сигналы у, в зависимости от которых операционный автомат выполняет необходимую микрооперацию. Операционный автомат посылает осведомительные сигналы х, которые управляют переключением состояний управляющего автомата. Хост-машина посылает в управляющий автомат сигналы start (начало выполнения операции) и clock (синхронизирующий тактовый сигнал). Кроме того, с операционным автоматом хост-

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

Операционный автомат синтезирован в виде 1-автомата. Достоинством I-автомата являются низкие аппаратные затраты вследствие использования минимизированных микроопераций и обобщенных микрооператоров.

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

Выходными данными являются:

- Хг - координата х точки после преобразования;

- Yr - координата у точки после преобразования;

- flag - флаг отсечения (равен 1, если точка лежит между гиперплоскостями, 0 в противном случае).

Данные в операционный автомат поступают в потоковом режиме. В каждой итерации i цикла хост-машина посылает одно i-e значение исходного вектора и i-e значение коэффициента гиперплоскости. Это позволяет ограничивать размерность пространства только разрядностью входного параметра п, что при п = 32 бит составляет 232. Такая размерность пространства подходит для большинства задач принятия решений.

Операционный автомат состоит из блока регистров, шины результата Z, шин операндов SI, S2, комбинационной схемы Ф. Схема операционного автомата представлена на рисунках 5 и 6.

Блок регистров соединен с шинами S1 и S2 через мультиплексированные каналы, которые управляются сигналами as и bs соответственно. Шина Z соединяется с блоком регистров через мультиплексированный канал, управляемый сигналами dz. Шины S1 и S2 являются входами комбинационной схемы Ф, шина Z - выход комбинационной схемы Ф. Комбинационная схема управляется сигналами f. Управляющие сигналы у состоят из нескольких сигналов: as, bs, dz и f.

Операции sin, cos целесообразно рассчитывать табличным методом, сохраняя данные в ПЗУ. Углы из градусной меры переводятся в 32-х битные целые числа.

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

cos (angle) = sin (angle + 90)

(8)

I Э2

Рис. 5 Схема операционного автомата

Рис. 6 Комбинационная часть операционного автомата На рисунке обозначено: DIV - схема деления, MUL - умножитель, ADD - сумматор, SIN - схема синуса, SQRT - схема извлечения квадратного корня.

Для высокоскоростного умножения используется модифицированный параллельный синхронный умножитель, основанный на продукционном символьном умножении (рис. 7).

32

Рис. 7 Схема модифицированного параллельного синхронного умножителя

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

ур+1] = (уИ + х/у[Ц)/2, (9)

где х - число из которого извлекается корень, у[1] - текущее значение квадратного корня.

Управляющий автомат представляет собой автомат Мура с жесткой логикой. На рисунке 8 представлена диаграмма состояний управляющего автомата.

Рис. 8 Диаграмма состояний управляющего автомата Здесь |уо -г ум} - множество управляющих сигналов, а {х1, х2} -

множество осведомительных сигналов.

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

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

Число измерений (п) Время (1), с

2 0.3

10 0.5

40 1.06

100 2.17

200 4.03

400 7.74

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

На рисунках 9 и 10 показаны графики сравнения времени визуализации синтезированного устройства и аналогов. Для всех устройств использовалось 28000 многомерных объектов. Тактовая частота всех сравниваемых устройств равна 25 МГц.

-Синт устройство - Проц. визуализации Мультипроце ссор

10 20 30

размерность пространства

Рис. 9 Сравнение времени визуализации устройств при размерности пространства от 2 до 30

60 80 100 300 500 700 размерность пространства

Синт. устройство Проц.

визуализации Мультипроцессор

Рис. 10 Сравнение времени визуализации устройств при размерности пространства от 40 до 800

В заключении приводятся основные результаты и выводы диссертационного исследования.

В приложении размещен листинг программных средств для моделирования работы алгоритмов и устройств.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ

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

2. Исследованы особенности метода нелинейного отображения точки n-мерного пространства и получены аналитические выражения определения факта отсечения точки n-мерного пространства параллельными гиперплоскостями.

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

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

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

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Чаплыгин, A.A. Шпилевая, H.H. Распознавание образов с помощью программы «Навигатор-2» [Текст] / А. А. Чаплыгин, H.H. Шпилевая // Материалы б-й Межд. науч.-техн. конф. «Медико-экологические информационные технологии-2003». Курск, 2003. С. 177-179.

2. Чаплыгин, А. А. Программа «Навигатор» [Текст] / А. А. Чаплыгин // Материалы 7-й Межд. науч.-техн. конф. «Медико-экологические информационные технологии-2004». Курск, 2003. С. 97.

3. Чаплыгин, A.A. Шпилевая, H.H. Распознавание образов с помощью программы «Навигатор-2» [Текст] / A.A. Чаплыгин, H.H. Шпилевая // Материалы 6-й Межд. конф. «Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации» («Распознавание-2003»), Курск, 2003. С. 41-42.

4. Чаплыгин, A.A. Шпилевая, H.H. К вопросу создания компьютерных систем поддержки принятия решений в экологии [Текст] / A.A. Чаплыгин, H.H. Шпилевая // Материалы 6-й Межд. конф. «Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации» («Распознавание-2003»). Курск, 2003. С. 315-316.

5. Чаплыгин, A.A. Шпилевая, H.H. Диалоговая система распознавания ситуаций экологических состояний [Текст] / A.A. Чаплыгин, H.H. Шпилевая // Материалы 6-й Межд. конф. «Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации» («Распознавание-2003»), Курск, 2003. С. 316-318.

6. Довгаль, В.М. Чаплыгин, A.A. Использование методов отображения многомерных объектов для распознавания протяженно распределенных образов [Текст] / В.М. Довгаль, A.A. Чаплыгин // Научно-практический вестник «Человек и его здоровье».-2005,- №4. Курск, 2005. С. 46-51.

7. Попов, A.B. Чаплыгин, A.A. Пушкина, Т.В. Попов, В.Е. Использование метода отображения многомерных объектов для распознавания протяженно распределенных образов с целью выработки эталона по прогнозированию качества подготовки специалиста дерматовенеролога [Текст] / A.B. Попов, A.A. Чаплыгин, Т.В. Пушкина, В.Е. Попов // Научно-практический вестник «Человек и его здоровье».-2005,- №4. Курск, 2005. С. 67-75.

Соискатель Чаплыгин A.A.

ИД №06430 от 10.12.01

Подписано в печать Формат 60x84 1/16. Печать офсетная.

Печ. л. 1. Тираж 100 экз. Заказ Курский государственный технический университет. Издательско-полиграфический центр Курского государственного технического университета. 305040, г. Курск, ул. 50 лет Октября, 94

г

í

г

РНБ Русский фонд

2006-4 26231

Введение.

Глава 1. Аналитический обзор методов, алгоритмов и аппаратных средств

1.1 Введение.

1.2 Обзор методов распознавания образов.

1.3 Области применения и особенности задач визуализации объектов 11-мерного пространства.

1.4 Основные методы визуализации многомерных данных.

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

1.6 Выводы по главе.

Глава 2. Разработка математических методов распознавания образов.

2.1 Введение.

2.2 Существующие методы отображения многомерных объектов.

2.2.1 Линейное отображение.

2.2.2 Нелинейное отображение.

2.2.3 Ортогональная проекция.

2.2.4 Геометрический смысл нелинейного ¡{-отображения точки 11-мерного пространства на плоскость.

2.2.5 Перенос начала координат п-мерного пространства и биплоскостные сечения.

2.3 Метод секущих гиперплоскостей.

2.4 Алгоритм секущих гиперплоскостей.

2.5 Выводы по главе.

Глава 3. Разработка устройства нелинейного отображения с секущими гиперплоскостями.

3.1 Введение.

3.2 Общее описание устройства.

3.3 Синтез операционного автомата.

3.4 Синтез управляющего автомата.

3.5 Временные характеристики операционного устройства.

3.6 Выводы по главе.

Глава 4. Сравнительный анализ устройства нелинейного отображения с аналогами.

4.1 Введение.

4.2 Аналог 1.

4.3 Аналог 2.

4.4 Сравнение временных характеристик синтезированного устройства с аналогами.

4.5 Выводы по главе.

Актуальность работы. Задачи визуализации объектов n-мерного пространства находят применение в системах управления технологическими процессами, в системах диагностики и распознавания образов, экспертных системах и системах принятия решений в технике, экономике и медицине, в лингвистике и психологии. В последнее время широкое распространение получили интерактивные системы принятия решений, в которых ответственное лицо принимает решение и оценивает их последствия на основе визуализированных данных.

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

Решению проблем визуализации объектов многомерного пространства посвятили свои работы А.И Галушкин, К. Фу, К. Пирсон, К Фукунага, Н.Г. Загоруйко, P.C. Лбов и другие отечественные и зарубежные авторы.

К наиболее распространенным методам визуализации объектов многомерного пространства в интерактивных системах принятия решений относятся нелинейные R-отображения ф: Rn—»R2. При визуализации объектов многомерного пространства рассматриваемые образы могут быть вытянуты вдоль одного или нескольких параметров или иметь сложный топологический портрет. Такие образы называются пространственно распределенными. Между тем в результате использования нелинейных R-отображений для визуализации пространственно распределенных образов часто возникают ситуации их ложного пересечения, в результате чего может произойти ошибочное принятие решения. Это обстоятельство определяет основную проблемную ситуацию данного диссертационного исследования. В системах принятия решений обрабатываемые данные носят преимущественно многомерный характер с большим числом признаков, что требует для визуализации значительных временных затраты. Для сокращения времени визуализации, требуются аппаратно-технические средства акселерации. Сущность основной решаемой задачи заключается в развитии существующих методов и разработке аппаратно-технических средств для визуализации точечных многомерных объектов в пространственно распределенных образах со сложными топологическими портретами на основе нелинейных отображений. На основании изложенного тема диссертационной работы является перспективной и актуальной. Работа выполнялась в рамках НИР по гранту Г02-4.2-5 (2002-2005 г.г.) «Разработка методов, алгоритмов, программных и технических средств быстрых символьных вычислений» при непосредственном участии автора.

Объектом исследования являются многомерные пространства, включающие в себя объекты с большим числом признаков.

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

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

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

1) анализ существующих методов визуализации объектов многомерного пространства и обоснование необходимости развития существующих методов для визуализации пространственно распределенных образов со сложными топологическими портретами;

2) разработка метода и алгоритма секущих гиперплоскостей как развитие метода нелинейного отображения объектов многомерного пространства;

3) разработка устройства визуализации пространственно распределенных образов со сложными топологическими портретами, реализующего метод секущих гиперплоскостей;

4) моделирование устройства визуализации, получение его временных характеристик и сравнение с аналогичными устройствами визуализации.

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

Научная новизна работы заключается в следующем:

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

2) разработан алгоритм секущих гиперплоскостей, который за счет сокращения количества циклов вычислений позволяет сократить время визуализации объектов п-мерного пространства;

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

Практическая ценность работы состоит в следующем:

- построенный новый алгоритм метода секущих гиперплоскостей реализован виде программных продуктов «Навигатор» и «Навигатор-2» для решения практически важных задач в различных областях принятия решений;

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

На защиту выносятся:

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

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

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

Апробация работы. Основные положения диссертационной работы докладывались на международных и российских конференциях: "Распознавание - 2003" (г. Курск, 2003 г.), "Медико-экологические информационные технологии - 2003, 2004 (г. Курск, 2003, 2004 гг.), "Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации" (г. Курск, 2003 г.), а также в научно-практическом вестнике «Человек и его здоровье» (г. Курск, 2005 г.).

Результаты работы внедрены на кафедрах дерматовенерологии и гистологии Курского государственного медицинского университета, в НПО «Экран» Минздрава РФ. Акты внедрения прилагаются к материалам диссертации.

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

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

4.5 Выводы по главе

1. Рассмотрены устройства аналогичные синтезируемому устройству: устройство визуализации объектов п-мерного пространства и мультипроцессор распознавания образов.

2. Измерены времена работы устройств при фиксированном числе объектов п-мерного пространства.

3. Синтезируемое устройство имеет преимущество во времени работы, особенно проявляющееся на высоких значениях мерности пространства (п > 40).