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

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

ПЛЕСКОВ Александр Владимирович

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

05.13.1в—Применение вычислительной техники, математического моделирования и математических методов в научных исследованиях

Автореферат

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

НИЖНИЙ НОВГОРОД, 1995

Работа' выполнена в НИИ прикладной математики н кибернетики при Нижегородском государственном университете им. Н. И. Лобачевского.

Научный руководитель: доктор технических наук, профессор, член-корреспондент АТН Ю. Г. Васин.

Официальные оппоненты:

доктор технических наук В, В. Сергеев;

кандидат технических наук С. И. Ротков.

Ведущая организация: Санкт-Петербургский электротехнический университет, г. Санкт-Петербург.

Защита состоится ^Р"декабря 1995 г. в. .чае. на заседании

диссертационного совета КР 063.43.01 в НИИ прикладной математики и. кибернетики при Нижегородском университете по адресу: 603005, Нижний Новгород, ул. Ульянова, д. 10.

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

Автореферат разослан ноября 1995 г.

Ученый секретарь диссертационного совета доктор технических наук, профессор

Ю. Л. Кетков

ОБЩАЯ ХАРАКТЕРИСТИКА ДИССЕРТАЦИОННОЙ РАБОТЫ

Актуальность темы. В задачах автоматизации научных исследований. при проектировании и создании различных систем обработки графической информации в робототехнике, медицинской и технической диагностике, создании ГАП, САПР, ГИС и т. д. , приходится иметь дело с большими массивами данных высокой размерности, среди которых выделяются трехмерные данные. К таким данным относятся бинарные и полутоновые изображения, модели метрической информации в картографии, всевозможные геофизические поля, данные, полученные в результате измерений в физике, медицине, модели 3-мерных сцен и т. д.

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

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

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

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

В 70-х годах С.Г. Васиным был разработан новый подход к задачам обработки графической информации, в значительной мере удовлетворяющий сформулированным требованиям к сложному конвейеру обработки. В его основе лежат методы конструктивного формирования локальных хорошо приспособленных базисных функций (ЛОХПБФ), иерархических структур представления исходных данных, а также методы аппроксима-

ции, фильтрации, сжатия, синтеза, анализа и принятия решений -на их основе.

Настоящая работа посвящена дальнейшему развитие данного подхода и связана с разработкой и исследованием новых иерархических структур представления трехмерных данных на основе ЛОХПБФ , а также методов и алгоритмов в задачах обработки и принятия решений на таких структурах.

Цель работы. Целью настоящей работы является разработка мето дов и алгоритмов построения и исследование эффективных иерархических структур представления данных вида F(x,y) на основе ЛОХПБФ и двойной ортогональной развертки, исследование и выбор эффективных форматов кодирования таких структур в памяти ЭВМ, разработка методов и алгоритмов решения задач обработки, а также принятия решений в задачах вычислительной геометрии и видимости на их основе.

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

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

вании и создании САПР, ГИС и т.п. Предложенные методы принятия решений на структурах могут быть положены в основу синтеза алгоритмов для решения большого класса исследовательских и прикладных задач. Разработанные программы используются при решении практических задач, выполняемых по планам НИР, а также по заданию директивных органов, внедрены в ряде организаций.

Методы и средства исследований. В работе используется методы математического анализа, линейной алгебры, теории графов, вычислительной геометрии, программирования. Для проведения численных экспериментов использовалась персональная ЭВМ типа ibm pc.

Аппробация работы. Результаты работы докладывались на ежегод-

1

ных итоговых научных конференциях Нижегородского государственного университета, на семинарах лаборатории научно-исследовательского института прикладной математики и кибернетики. Кроме того, были сделаны доклады на Всесоюзной конференции "Обработка изображений и дистанционные исследования". {Новосибирск, 1984), на 3-ей и 4-ой Всесоюзных конференциях "Нетоды и средства обработки сложной графической информации" (Горький, 1988,1991), на Всесоюзной конференции "Автоматизированные системы обработки изображений" (Ленинград, 1989), на 2-ом Республиканском семинаре "Проблемы создания систем обработки, анализа и распознавания изображений" (Ташкент, 1989), на 2-ой Всероссийской конференции "Распознаваний образов и анализ изображений" (Ульяновск, 1995).

Публикации. По теме диссертационной работы опубликовано 11 печатных работ, список которых приведен в конце автореферата.

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

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

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

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

В главе 2 излагается метод рекурсивной аппроксимации дискретных данных вида Р={ £ } , 1 « « 2" « 1, на основе ЛОХПБФ и двойной ортогональной развертки, описаны методы и алгоритмы построения бинарных иерархических структур представления, в основе которых лежит данный метод аппроксимации.

Рекурсивная аппроксимация определяется через рекурсивное преобразование исходной матрицы Р с использованием двойной ортогональной развертки и локальной восстанавливающей функции к>>={а)..... а^)

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

' 1, для <3=1)"1+ 21(к-1)+1>, к=1,2____

О, ДЛЯ (;)*1)л(:1«21"1+21 ()с-1)+1)у(1=21"1+ 2* <к-1)+1)л

л; (^г^в^-^мт-^г'-М/г'^т/г^ а\= у'Из-ьг"1]/:1!^)!,

1-1 I и ! -1*2 ) /2 1../2

для (х=21_1+21(к-1)+1)л(з=2'(¡3-1)+1)л

/М-т/2<[^-1 + 21~*)/21] зт/2) , к=1,2,---- 8 = 1,2,...

Л,"'*" <• пI мттриц в1, задающих преобразование строк, определяются как элементы транспонированных матриц а1, то есть в'=(а1)т .

Рекурсивное преобразование матрицы Г уровня п, (0 < п < 2п),

л

обозначается и определяется для п = 2к, С1 2 к < п) следующим

образом:

рП,о_ р>

'•-1 I Г^1, для 1*2*-1лС8-1)+1,

где 1 < < 2п+1, рч« Р, Р = ?,г'1Вк:-1/г , для четного I, и

Ч1( , ДЛЯ 11=гк-и-,,<'«-«С5-1)+1. 1й2п-к+<1-»'" +1

1. J [ епл 4 и '

для >2к-и-,>/2-ч5-1м,

где 1 < i,j < 2п+1, д1(бй. 0=Ак-и-"/г Г "-1, для нечетного I,

* л

О < п. Для п = 2к-1, (1 < к £ п), Гп,п определяется аналогично, причем формулы (1) и (2) меняются местами.

Вводится понятие рекурсивных матриц Рк, 1 5 к 5 п, которые образуются из отсчетов исходной матрицы Г следующим образом: Г 1* , 1< 1 j < г* + 1. 1. =2(1'~1) + 1,

^^С,^-!) + 1 . Показано, что для выполнения рекурсивного преобразования уровня п достаточно знать значения элементов рекурсивной матрицы Рк, где к=п-л/2.

Далее определяются матрицы ошибок аппроксимации уровня п :

Ел,п= ? -9я-п , " СЗ)

и максимальная ошибка аппроксимации:

С" 1еиЛ1

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

отсчетов последовательно на рекурсивных матрицах Р°, Р1.....р"

в первом случае и на матрицах р" , рп"1.....р°, во втором случае.

Показано, что в случае организации вычислительного процесса по методу от общего к частному допускается реализация однопроходного алгоритма сжатия, то есть сложность вычислений не превышает о(Н2т), где N=2" + 1. Во втором случае сложность вычислений определяется по формуле:'

П П-1С + 1

(з-г2""2^") ^Гт' к= 1

Далее подробно рассматривается рекурсивная аппроксимация для ш=2. Функция Кг имеет вид (0.5, 0.5). Вводится понятие фрагментов матрицы уровня л - ф" , (о*тг*2п), угловыми отсчетами которых служат отсчеты рекурсивной матрицы р" с индексами (1к, зк), удовлетворявшие условиям: ^е 1е {1,1 + 1}, вСЛИ л = 2к, И {21-1, 21 + 1}, если п=2к-1.

Множество фрагментов {Ф^} для любого заданного значения л включает в себя все отсчеты исходной матрицы. Показано, что рекурсивное преобразование уровня л в случае т = 2 можно выполнять независимо на каждом из фрагментов ф" . При этом значение любого отсчета матрицы Ргп-П>гп-П с индексами е ф™ можно вычислить по значениям четырех угловых отсчетов фрагмента . На множестве

Е

всех фрагментов для 0зл*2п определяется рекурсивная или иерархическая модель аппроксимации.

Установлено взаимнооднозначное соответствие между фрагментами и вершинами бинарного дерева. Процесс рекурсивной аппроксимации рассматривается как процесс иерархического разбиения (объединения) фрагментов. Значения отсчетов хранятся как атрибуты внутренних вершин бинарного дерева. Преимущества построенной иерархической модели по сравнении с традиционными, основанными на пирамидальном подходе, заключается в отсутствии избыточности описания и межблочных промежутков при поуровневом воспроизведении данных. Объем памяти для хранения информации в построенном полном бинарном дереве составляет (2п+1)2 , то есть совпадает с оЬьемом памяти для хранения исходной матрицы. Построенная иерархическая модель называется бинарной иерархической структурой (БИС).

В результате реализации рекурсивного преобразования уровня 2п-п

на произвольном фрагменте вычисляются величины ошибок 2п~п

для 2°~к (х-1)+158«2п"к1+1, 2п"к (з~1) при Л=2к, И ДЛЯ

2п-к>1 И-о.)+15852'"1+1, 2л~к +1*^2а~к]+1, при л=2к-1, а

также величина максимальной ошибки аппроксимации е2"'"1 2п~пи,;)) :

чв *

гп-п,2п-п.. ., гп-п.гп-п

(1,3) -шах еш1 (5)

(.,4)6

Фрагмент называется непроизводным фрагментом в случае реализации схемы "сверху-вниз", если выполняется следующее условие: V »*,,,, Оад<п, таких, что »"с ф", ,, e2n"',• г"~" (!<-, 1') > V, а " Н.Л 1 о» где V - заданный порог точности.

Фрагмент называется непроизводным фрагментом в случае

реализации схемы "снизу-вверх", если выполняется условие: V ♦ ,, п*т*2п, таких, что **.,.<= е2^"*' 2П"* (Г, V) * О, а для

такого, что с е^""*1' (д/,> б. Непроизводные -

фрагменты соответствуют листьям неполного бинарного дерева.

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

Предложены и конструктивно описаны алгоритмы построения УБИС как способом разбиения ("сверху-вниз"), так и способом объединения ("снизу-вверх") фрагментов. Показано, что сложность вычислений первого алгоритма составляет О(Ы-п), где N » (2П + I)2. При реализации второго алгоритма допускается обработка матрицы фрагментами уровня

7)

■по которые последовательно загружается в ОП ЭВМ согласно об-

ходу по г- развертке уровня п0- При вычислении максимальной покоординатной ошибки на фрагментах для тг г чо, используется формула (5), а для п < т) происходит оценка максимальной покоординатной ошибки по формуле:

МР.1 ^ вм,( ц/;)).А!р+а), (6)

вг «в*

где о^р<2п-л, 1 (а,з) -значение максимальной ошибки первого

уровня на фрагменте , Л(р) -коэффициенты, не зависящие от значений индексов и вычисляемые по рекуррентным формулам, которые почуч?ны в работе.

Показано, что сложность вычислений второго алгоритма составляет 0((п к ) 2 г" + | VI ), где п = 2к или 71 = 2к -1.

О О О 0 0

Главу 2 завершает описание усеченной бинарной иерархической

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

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

Рассматриваются следующие форматы кодирования.- регулярный формат без указателей; регулярный формат с указателями; поуровневый формат без указателей; поуровневый формат с указателями,- форматы с о-окрестностями.

Проведено исследование предложенных форматов с точки зрения выполнения следующих базовых операций на структурах: поиск адреса поля произвольного фрагмента в структуре, поиск соседнего фрагмента в заданном направлении, поиск значений угловых отсчетов фрагмента. Получены ассимптотические оценки средней сложности выполнения перечисленных операций на каждом формате. УБИС в регулярном формате без указателей, который формируется в процессе построения структуры, согласуется с известным оптимальным кодом Закса кодирования бинарных деревьев, однако не обеспечивает эффективное выполнение введенных операций. Установлено, что верхняя граница сложности выполнения всех операций на таком формате составляет о(IVI). На УБИС в

- Ю -

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

о - окрестности произвольного фрагмента представляют собой две треугольные призмы П {1,з,) и П а,1,п,1) ) . Вершинами П^з-.^л.о^ являются точки в и3 с координатами (в^.г ±о ), (В+ЗБ, С, £ 1±01Ь (в+5а'а вершинами П, (±, з <п ) - точки с координатами (э, с, г ш ), (8+«в^+ас, г „ . +

±Б2), (а^+гь,^ причем

Г 2п"к(1-1)+1, л»2к, 1 г"""*1 (1-г)+1, п»2к-1,

(:-2п"к<;1--1>+1,

58

2"~\ П-2к, 2"'к*1, Л»2к-1,

Величины и Ог в случае полной БИС вычисляются по формулам:

тах |Р1 (8' , С , 1, з,п)-г>( , I • <1' at.it'

D2« max IPj(e',t',i,j,n)-fe4,l, (7)

ttSt'st'st*3t

если я»2k,

Г в'-в, t'- \

{ He'-E

где et'

-в)/2], если п»2к-1,

a Pt и РГплоскости, построенные соответственно на точках (B,t,f>t), (e+ae,t,fj4at t>, (s+is,t+6t,f>iii(lt6t), и (s,t,f>t), (a+is,t+6t,

£..e.,t.it>< (e<t+it'£..fSt»-

В случае УБИС (7) записываются следующим образ out

D.- max IP, <s',t' j,n) - £ , ,l ,

Л' *

1 (•' , t' >« м'

D ■ max

2

|Р(8',С'Д^,ГГ) - С , . I, (.' ,1')« М' 2 ' 1

где м'»{ (в', I:')/вав'ав+бв.^е'«+31:, (в',ь') -существенные отсчеты}.

В случае полной БИС любая точка (в',«:',£ #1<), такая, что (в',С)е Ф^, находится внутри призмы П^ если вав'М+«8, СзЬ'^+бИ' и внутри призмы Пг, если 8*в'«в+«в, t+6t'st'st+ít. В случае УБИС справедливо аналогичное свойство для точек восстановленной поверх-, ности.

Множество призм {П. ^.я.о )} и {П (1 ,:э_,п,о )}, для всех

1 71 «I I 2 И 71 в

*„»:}„. называется о - покрытием уровня л. БИС или УБИС, для всех внутренних фрагментов котбрых построены о-окрестности, называется соответственно БИС или УБИС с о -окрестностями.

Содержится конструктивное описание алгоритмов построения предложенных форматов.

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

Сложность построения триангуляции на структуре в отличие от

применения стандартных процедур триангуляции линейно зависит от числа непроизводных фрагментов.

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

Основное свойство существенных отсчетов, положенное в основу .метода построения Делоне-триангуляции, формулируется в следующей теореме •.

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

Описана процедура построения граничных отсчетов произвольного фрагмента ф" . Показано, что среднее число таких отсчетов не зависит от размера фрагмента и объема структуры, и составляет 9. Таким образом, средняя вычислительная сложность построения локальной триангуляции составляет 0(1), а сложность построения триангуляции на всей структуре О (I"V (>, где |\7к1 - число непроизводных фрагментов.

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

В основу методов построения линий равного уровня положена

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

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

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

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

В главе 5 описаны методы и алгоритмы выделения яркостных перепадов и построения линий перепадов на изображениях, представленных УБИС.

Оценки величины перепада яркости предлагается вычислять не на исходной матрице отсчетов, а на фрагментах УБИС, что позволяет зна-значительно экономить вычисления и строить линии перепадов с заданной точностью.

Для формального описания линий перепадов в работе предложен лингвистический подход. Множество линий перепадов на структуре об-

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

Для оценки величины перепада яркости на любом непроизводном фрагменте введены локальные операторы дифференцирования Рд!*™^. как функции его угловых отсчетов 1^34, где а- номер лока-

льного оператора.

Фрагмент ф"} содержит границу между двумя областями, если выполняется условие:

рх<*7;> * V <8)

где од- заданный порог .

Фрагменты, на которых выполнено (8), назовем контурными элементами. Обозначим множество контурных элементов структуры н* .

Линией перепадов будем называть линию, образованную последовал

телыюстью фрагментов {Ф " }, З.зузк, из множества V»', удовлетворя-вщих следующим условиям: п л

Ф " е к(Ф ), у > 1, (9)

V V 1>-1 У-1

где к(ф" ) -множество соседних контурных элементов для ф"^

{ Ф^,/<Флв<*и>) А <*Г}'* ^ '

а лв(Ф™ ) -множество соседних элементов, определяемых по 8-связной схеме.

П

Кроме того последовательность {Ф ) может быть разбита на подпоследовательности длины ш, каждая из которых удовлетворяет критерию оптимальности

л л л

, ф/*1 ..... «)

*( «. , , ..... ) (Ю)

.. ж«" . .

»"11 б К(Ф ) , Ф г а с К(1 1 1).....€ -О

» 3 V V 1

В качестве критерия * берется вьфахение: *< ..........» -£ + РХ(4>.

Описан алгоритм построения линий перепадов, каждый контурный элемент которых удовлетворяет условиям (9) и (10) при т»1, эквивалентный введенной грамматике, а также реализация этого алгоритма на УБИС, записанной в регулярном формате с указателями.

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

В главе 6 изложены методы решения задачи видимости поверхности на базе предложенных БИС.

В связи с этим рассмотрены двё модели аппроксимации на фрагментах. Первая модель обеспечивает аппроксимацию по схеме, предопределяемой двойной ортогональной разверткой и локальной восстанавливающей фукцией кг< Получен аналитический вид аппроксимирующей функции, которая в этом случае является билинейной. Вторая модель обеспечивает кусочно-линейную аппроксимацию и представляет собой для каждого фрагмента пару плоскостей, построенных. в точках Б3, определяемых его угловыми отсчетами. Если первая модель удобна для решения задачи на УБИС без О-окрестностей, то вторая модель может быть использована при решении аналогичной задачи на структуре

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

Подробно рассматриваются свойства введенных моделей применительно к задаче видимости поверхности. Предложены и конструктивно описаны алгоритмы решения задачи' видимости точки поверхности на структуре без Б -окрестностей и с о -окрестностями. Показано, что вычислительная сложность этих алгоритмов составляет в среднем о (п + ао), где а - для первого алгоритма - число непроизводных фрагментов, пересекаемых отрезком обзора, а для второго алгоритма это число всех фрагментов, пересекаемых отрезком обзора. Предложена методика решения более общих случаев задачи видимости поверхности, представленной УБИС.

Главу завершает описание экспериментов по сравнению эффективности предложенных алгоритмов.

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

В приложениях содержится пошаговое описание алгоритмов и отдельных процедур.

Автор выражает глубокую признательность научному руководите-телю доктору технических наук Юрию Григорьевичу Васину за постановку задачи, ценные советы и указания при выполнении работы, а также старшим научным сотрудникам НИИ ПМК Валентине Петровне Игнатьевой и Татьяне Викторовне Фирсовой за плодотворные совместные обсуждения.

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

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

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

3. Разработаны методы и алгоритмы построения различных форматов кодирования бинарных иерархических структур в памяти ЭВМ.

4. Получены оценки сложности поисковых операции на структурах при различных схемах кодирования.

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

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

7. Разработаны методы и алгоритмы принятия решений в задаче видимости поверхности вида F(X,Y), представленной бинарной иерархической структурой.

8. На основе разработанных алгоритмов создан пакет прикладных программ.

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

1. Васин С. Г., Плесков А. В. Выделение контурных перепадов на полутоновых изображениях с предварительным сжатием информации // Автоматизация обработки сложной графической информации: Межвуз. сб.

науч. тр. /Под ред. ¡0. Г. Васина; Горьк. гос. ун-т, Горький, 1985,

с. 17.

2. Васин Ю. Г., Плесков А. В. Рекурсивные структуры представления видеоинформации и их использование в задачах выделения линий перепадов и построения изолиний // Автоматизация обработки сложной графической информации: Межвуз. сб. науч. тр. /Под ред. Ю. Г. Васина,- Горьк. гос. ун-т, Горький, 1988, с. 4. Я. Васин П. Г. , Плесков А. В. Рекурсивные структуры представления двумерных данных на базе ЛОХПБФ в задаче построения зон видимости и невидимости. - В кн,-: 2 республиканский семинар. Проблемы создания систем обработки, анализа и распознавания изображений. Ч. 2. / Тез. докл., Акад. наук Узбекской ССР, Ташкент,

1989, с. 94.

4. Васин Ю. Г. , Плесков А. В. Решение задачи видимости с использованием бинарных рекурсивных структур представления видеоинформации //Автоматизация обработки сложной графической информации: Межвуз. сб. науч. тр. /Под ред. Ю. Г. ВасинаГорьк. гос. ун-т, Горький,

1990, с. 5.

5. Васин Ю. Г. , Плесков А. В. Эксперименты по выделение линий перепадов яркости на изображениях, представленных бинарными иерархическими структурами, с использованием различных градиентных операторов. - В кн. 4 Всесоюзная конференция. Методы и средства обработки сложной графической информации. / Тез. докл., Горьк. гос. ун-т. Горький, 1991, с. 106.

6. Васин Ю. Г. , Плесков А. В. Исследование эффективности различных стратегий в задачах видимости в пространстве R3 с использованием бинарных иерархических структур. -В кн. : 4 Всесоюзная конференция. Методы и средства обработки сложной графической информации. / Тез. докл., Горьк. гос. ун-т. Горький, 1991, с. 107.

7. Васин Ю. Г., Бакараева В. П., Плесков A.B. Комплекс программ построения рекурсивных структур представления видеоданных. В кн.: Всесоюзная конференция. Автоматизированные системы обработки изображений (АСОИЗ-89). / Тез. докл., Ленинград, 1989.

8. Васин Ю. Г., Бакараева В. П., Плесков А. В., Крахнов А. Д. Оперативное решение специальных задач обработки графической информации в системах управления. -В кн. : 3 Всесоюзная конференция. Методы и средства обработки сложной графической информации. Ч. 2 / Тез. докл., Горьк. гос. ун-т, Горький, 1988, с. 84.

9. Плесков A.B., Буров A.B. Построение усеченной рекурсивной структуры (УРС) описания полутоновых изображений на основе ЛОРРФ. -

В кн. : Научная конференция молодых ученых Волго-вятского региона. /Тез. докл., Горький, 1987, о. 56.

10. Плесков А. В., Фирсова Т. В. Построение пленарной Делоне-триашу-ляции на точках бинарной иерархической структуры. В кн. :4 Всесоюзная конференция. Методы и средства обработки сложной графической информации. /Тез. докл., Горьк.'гос. ун-т. Горький, 1991, с. 105.

11. Васин Ю. Г., Плесков A.B. 0 вычислительной сложности решения задач обработки и анализа видеоинформации на базе бинарных иерархических структур представления. В кн.: 2 Всероссийская конференция. Распознавание образов и анализ изображений. Ч. 2 / Тез. докл., Ульян, гос. тех. ун-т, Ульяновск, 1995, с. 77.