Введение к работе
Актуальность темы. В задачах автоматизации научных исследований, при проектировании и создании различных систем обработки графической информации в робототехнике, медицинской и технической диагностике, создании ГАП, САПР, ГИС и т. д. , приходится иметь дело с большими массивами данных высокой размерности, среди которых выделяется трехмерные данные. К таким данным относятся бинарные и полутоновые изображения, модели метрической информации в картографии, всевозможные геофизические поля, данные, полученные в результате измерений в физике, медицине, модели 3-мерных сцен и т. д.
Анализ существующих в настоящее время специализированных систем обработки, а также задач, которые ставит перед исследователями сегодня практика, позволил сформулировать основные требования, которым должен удовлетворять сложный многоэтапный процесс автоматической обработки, включающий в себя большое количество различных методов и алгоритмов: фильтрация, сжатие, хранение и поиск, анализ и принятие решений. Такими требованиями являются: локальный характер обработки, оптимизация сокращения избыточности, кодирование существенными отсчетами, а не обобщенными коэффициентами разложения, адаптивная фильтрация с контролем максимальной покоординатной ошибки, синтез эффективных структур представления информации в памяти ЭВМ, высокая технологичность организации вычислительного процесса при реализации алгоритмов обработки, анализа и принятия решений на таких структурах, возможность распараллеливания вычислений на многопроцессорных комплексах и т. д.
В сеязи с этим большое внимание должно уделяться построении различных моделей представления входной информации, обеспечивающих
эффективное решение задач на разных этапах обработки. Причем, эти модели должны быть достаточно универсальными, и вместе с тем учитывать специфику решаемых задач и физическую природу входного сигнала.
В последние 10-15 лет сформировалось новое направление в создании моделей представления экспериментальных данных, получивших название иерархические. В настоящее время такой путь в свете новых требований к системам обработки и анализа видеоинформации является по-видимому одним из наиболее перспективных. Наиболее распространенными иерархическими моделями представления видеоинформации являются квадродеревья и пирамиды изображений. Анализ таких моделей показал, что до настоящего времени не решены в комплексе вопросы, которые возникают при их построении, хранении, преобразовании и использовании. Прежде всего, это выбор аппроксимирующей функции, критерия точности, синтез быстрых алгоритмов построения, устранение межблочных разрывов, эффективное кодирование в памяти ЭВМ, обеспечение информационной сохранности видеоданных на всех уровнях описания и т. д. Вследствие этого квадродеревья, а также различные пирамиды изображений, не всегда удовлетворяют требованиям, предъявляемым к моделям обработки и анализа. В частности, все такие модели, как правило, имеют дело с обобщенными значениями признаков на разных уровнях описания, а не со значениями существенных отсчетов. Поэтому разработка и исследование новых иерархических моделей с учетом перечисленных требований является очень актуальной задачей.
В 70-х годах Ю.Г. Васиным был разработан новый подход к задачам обработки графической информации, в значительной мере удовлетворяющий сформулированным требованиям к сложному конвейеру обработки. В его основе лежат методы конструктивного формирования локальных хорошо приспособлениях базисных функций (ЛОХПБФ), иерархических структур представления исходных данных, а также методы аппроксима-
ции, фильтрации, сжатия, синтеза, анализа и принятия решений -на их основе.
Настоящая работа посвящена дальнейшему развитио данного подхода и связана с разработкой и исследованием новых иерархических структур представления трехмерных данных на основе ЛОХПБФ , а также методов и алгоритмов в задачах обработки и принятия решений на таких структурах.
Цель работы. Целье настоящей работы является разработка мето дов и алгоритмов построения и исследование эффективных иерархических структур представления данных вида F(x,y) на основе ЛОХПБФ и двойной ортогональной развертки, исследование и выбор эффективных форматов кодирования таких структур в памяти ЭВМ, разработка методов и алгоритмов решения задач обработки, а также принятия решений в задачах вычислительной геометрии и видимости на их основе.
Научная новизна. В работе построен новый класс иерархических структур представления трехмерных данных в виде бинарных деревьев, предложены эффективные форматы кодирования в памяти ЭВМ, получены оценки сложности процедур поиска на структурах при различных схемах кодирования, предложены методы и алгоритмы построения таких структур, методы и алгоритмы обработки, принятия решений в задачах вы числительной геометрии и видимости на структурах, создан пакет прикладних программ на базе предложенных алгоритмов.
Практическая и теоретическая ценность. В работе предложен метод рекурсивной аппроксимации, позволяющий синтезировать новые эффективные процедуры сжатия видеоинформации и построения иерархиче ских структур представления. Построенный класс структур может найти применение при решении различных исследовательских задач в АСНИ, связанных с обработкой и анализом видеоинформации, при разработке пакетов прикладных программ специального назначения, при проектиро-
вании и создании САПР, ГИС и т.п. Предложенные методы принятия решений на структурах могут быть положены в основу синтеза алгоритмов для решения большого класса исследовательских и прикладных задач. Разработанные программы используются при решении практических задач, выполняемых по планам НИР, а также по заданию директивных органов, внедрены в ряде организаций.
Методы и средства исследований. В работе используется методы математического анализа, линейной алгебры, теории графов, вычислительной геометрии, программирования. Для проведения численных экспериментов использовалась персональная ЭВМ типа івм рс.
Лппробация работы. Результаты работы докладывались на ежегод-ных итоговых научных конференциях Нижегородского государственного университета, на семинарах лаборатории научно-исследовательского института прикладной математики и кибернетики. Кроме того, были сделаны доклады на Всесоюзной конференции "Обработка изображений и дистанционные исследования". {Новосибирск, 1984), на 3-ей и 4-ой Всесоюзных конференциях "Методы и средства обработки сложной графической информации" (Горький, 1988,1991), на Всесоюзной конференции "Автоматизированные системы обработки изображений" (Ленинград, 1989), на 2-ом Республиканском семинаре "Проблемы создания систем обработки, анализа и распознавания изображений" (Ташкент, 1989), на 2-ой Всероссийской конференции "Распознавание образов и анализ изображений" (Ульяновск, 1995).
Публикации. По теме диссертационной работы опубликовано 11 печатных работ, список которых приведен в конце автореферата.
Обьем и структура работы. Работа состоит из одного тома, включающего введение, шесть глав, заключение, приложения и список литературы из 140 названий. Обьем тома - 218 страниц машинописного текста.