Содержание к диссертации
Введение
1 Системный анализ способов представления пространственных данных в геоинформационных системах 13
1.1 Понятие о геоинформационных системах, области их применения и решаемые ими задачи 13
1.2 Организация представления пространственных данных в геоинформационных системах 25
1.3 Цель и задачи исследования 40
2 Разработка критерия скорости сходимости системы многочленов, представляющих криволинейные объекты геоинформационных систем 41
2.1 Исследование метода приближенного вычисления интегралов при помощи квадратурных формул 41
2.2 Представление энтропии конечных схем интегралами от рацио нальных функций 45
Выводы второй главы 65
3 Разработка алгоритма разложения функций из пространства L,2(R) по базисным функциям всплесковых систем 66
3.1 Анализ способов построения всплесковых рядов 68
3.2 Система Хаара как всплесковый базис для разложения функций из пространства ДгСФ 86
3.3 Применение кратномасштабного анализа в L2(R) для разработки алгоритма разложения и восстановления функций 91
Выводы третьей главы 105
4 Разработка подсистемы представления пространственных данных в геоинформационных системах 106
4.1 Место и роль подсистемы представления пространственных данных в общей структуре геоинформационной системы 106
4.2 Описание архитектуры программного комплекса 112
4.3 Примеры расчетов коэффициентов разложения 121
4.3.1 Расчет коэффициентов разложения для функции 121
4.3.2 Расчет коэффициентов разложения составной функции 125
Выводы четвертой главы 131
Заключение 132
Список литературы 134
Приложение 144
- Организация представления пространственных данных в геоинформационных системах
- Представление энтропии конечных схем интегралами от рацио нальных функций
- Система Хаара как всплесковый базис для разложения функций из пространства ДгСФ
- Описание архитектуры программного комплекса
Введение к работе
Актуальность темы. В настоящее время отчетливо видна тенденция уве- ч личения роли информационных технологий в различных областях. Расширение сферы применения ЭВМ, рост числа пользователей повлекли за собой неизбежный рост объема обрабатываемой информации. Актуальным становится вопрос о способах и средствах хранения постоянно увеличивающегося объема данных.
Экстенсивный путь решения данной проблемы заключается в увеличении количества средств хранения информации или в увеличении емкости каждого такого средства. Современные технологии пока вполне удовлетворяют этим запросам, однако определенный предел в данном пути все же существует. Работа с большими объемами данных предъявляет повышенные требования и к вычис- * лительной подсистеме компьютера.
Другой путь решения поставленной проблемы концептуализируется не на средствах хранения информации, а на способе ее представления в памяти ЭВМ. Следуя этому пути, мы сможем сэкономить физическую память, машинное время и, как следствие, получить экономический эффект.
Одной из множества областей информационных технологий, имеющих дело с большими объемами информации, являются геоинформационные системы. Из требований, предъявляемых к современным геоинформационным системам, следует выделить необходимость ввода, обработки, хранения и анализа больших объемов пространственных данных. Чем подробнее мы хотим представить некоторую местность, тем большее количество информации нам необходимо сохранить.
По способу представления пространственных данных в машинной памяти * различают растровые и векторные геоинформационные системы. Анализ суще ствующих в настоящее время геоинформационных систем показал, что боль- шинство из них используют растровую модель данных. Ее главным достоинст вом является простота. По сравнению с ней более сложная векторная модель требует меньшего объема машинной памяти, увеличивает скорость работы, а также обеспечивает большую точность представления пространственных данных. Таким образом, ее использование является более перспективным.
Большое значение в векторных геоинформационных системах имеет подсистема представления пространственных объектов. Естественным способом является рассмотрение таких объектов в виде функций из некоторого класса. Тогда задача представления пространственных объектов в векторных геоинформационных системах сводится к задаче сохранения в памяти ЭВМ функций определенного класса. Ее решение можно осуществить путем разложения заданной функции по некоторому базису и сохранения коэффициентов разложения в машинной памяти. Здесь очень важно выбрать нужный базис функций и определить алгоритм разложения и восстановления функций, обеспечивающий необходимую точность и скорость.
Таким образом, актуальность темы диссертационной работы определяется необходимостью создания такой новой технологии для разработки подсистемы представления пространственных данных в геоинформационных системах, чтобы обеспечивалась высокая скорость работы подсистемы.
Диссертационная работа выполнена в соответствии с межвузовской комплексной научно-технической программой 12.11 "Перспективные информационные технологии в высшей школе" в рамках одного из основных направлений Воронежского государственного технического университета "Проблемно-ориентированные системы управления".
Цель и задачи исследования. Целью диссертационной работы является разработка математического и программного обеспечения подсистемы представления пространственных данных в геоинформационных системах, обеспечивающего увеличение производительности подсистемы, а также позволяющего сократить объем используемой машинной памяти.
Для достижения поставленной цели необходимо решить следующие задачи: произвести системный анализ способов представления пространственных данных в геоинформационных системах; разработать критерий оценки скорости сходимости системы многочленов, представляющих криволинейные объекты геоинформационных систем; проанализировать возможные типы разложения функций заданного класса на основе теории информации и теории всплесков, скорость выполнения разложения, а также объем полученной в результате разложения информации; обосновать использование всплесковых базисов для разложения функций, представляющих криволинейные объекты геоинформационных систем; разработать алгоритм быстрого разложения функций заданного класса по всплесковым базисам; разработать подсистему представления пространственных данных в геоинформационных системах.
Методы исследования. При выполнении работы использовались методы системного анализа, элементы теории информации и теории множеств, методы теории всплесков, основные положения теории вероятности и функционального анализа.
Научная новизна. В диссертации получены следующие основные результаты, характеризующиеся научной новизной: алгоритм быстрого разложения функций из пространства L,2(R) по всплесковым базисам, обеспечивающий более высокую, по сравнению с классическим разложением Фурье, скорость разложения, за счет того, что значительно упрощена процедура вычисления коэффициентов разложения на каждом шаге; способ определения количества операций, осуществляемых в ходе разложения функций из пространства L.2(R) по всплесковому базису, позволяющий до начала работы алгоритма оценить время, затрачиваемое на разложение, вне зависимости от используемого базиса; процедура вычисления коэффициентов разложения функций из пространства L,2(R) по всплесковому базису Хаара, обеспечивающая значительное сокращение общего числа операций за счет того, что на каждом шаге вычисляются только те числа, коэффициенты которых отличны от нуля; способ представления энтропии конечных схем, отличающийся алгебраическим представлением, интерпретирующим энтропию посредством взаимного расположения нулей и полюсов некоторой мероморфной функции специального вида.
Практическая значимость и результаты внедрения. На основании разработанного в диссертационной работе алгоритма создан программный комплекс, реализующий разложение функций из пространства L2(R) по всплесковому базису Хаара и наглядно демонстрирующий работу алгоритма, что позволяет применять программный комплекс в учебном процессе.
Основные теоретические и практические результаты работы в виде алгоритмов и процедур внедрены и используются в ОАО «ЦЧР Агропромпроект»; в виде программного комплекса внедрены в учебный процесс кафедры «Системы автоматизированного проектирования и информационные системы» Воронежского государственного технического университета для студентов специальности 071900 «Информационные системы».
Апробация работы. Результаты диссертационной работы докладывались и обсуждались на следующих конференциях и семинарах: Всероссийской конференции "Интеллектуальные информационные системы" (Воронеж, 2001), Всероссийской конференции "Интеллектуализация управления в социальных и экономических системах" (Воронеж, 2002), Всероссийской конференции "Интеллектуализация управления в социальных и экономических системах" (Воронеж, 2003).
Публикации. Основное содержание диссертационной работы изложено в 8 печатных работах. В работах, опубликованных в соавторстве и приведенных в конце автореферата, лично соискателю принадлежат: в [1] применение квадратурных формул в представлении энтропии конечных схем, в [2] анализ возможности решения полученной системы уравнений.
Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, изложенных на 147 страницах машинописного текста, списка литературы из 124 наименований, приложения, содержит 22 рисунка, 4 табли-
Во введении обосновывается актуальность темы диссертационной работы, сформулированы цель и задачи исследования, научная новизна, практическая значимость полученных результатов, изложено краткое содержание глав диссертации.
Первая глава посвящена системному анализу способов представления пространственных данных в геоинформационных системах. Рассматриваются две модели данных: растровая и векторная, их преимущества и недостатки по сравнению друг с другом. В ходе анализа существующих в настоящее время геоинформационных систем выявлено, что системы, использующие векторную модель представления данных, менее распространены из-за своей сложности, однако являются более перспективными.
В качестве основного преимущества растровой модели представления пространственной информации выделена гораздо более простая структура данных по сравнению с векторной моделью. Как следствие, растровая модель имеет более простые методы для анализа данных. Из основных недостатков растровой модели как наиболее существенные отмечены требование больших объемов памяти в ЭВМ и ограничение точности представления географических сущностей.
Показана возможность представления криволинейных объектов векторных геоинформационных систем в виде функций определенного класса. Тогда некоторая функция, представляющая криволинейный объект, может быть разложена по заданному базису, а коэффициенты разложения могут быть сохранены в памяти ЭВМ. Разработана система управления процессом представления криволинейных объектов геоинформационных систем, где объектом управления является процесс представления криволинейных объектов, входным параметром - функция, представляющая криволинейный объект, выходным параметром - коэффициенты разложения, а управляющим параметром - базис разложения. В случаем если аппроксимация представляющей некоторый объект функции произошла с недостаточно малой погрешностью, производится выбор другого базиса разложения. Исходя из возможности представления криволинейных объектов векторных геоинформационных систем в виде функций определенного класса, сформулированы цель и задачи исследования.
Во второй главе рассматривается разложение функций, представляющих криволинейные объекты векторных геоинформационных систем, в ряды по системе многочленов с вещественными корнями. Важным критерием оценки разложения является скорость его сходимости. Анализируется возможность энтропийной оценки скорости сходимости системы многочленов с вещественными корнями к различным заданным функциям.
Предложен способ представления энтропии конечных схем, интерпретирующий энтропию посредством взаимного расположения нулей и полюсов некоторой мероморфной функции специального вида.
На основе разработанного способа представления энтропии конечных схем предложено использование критерия для оценки скорости сходимости рядов по системе многочленов с вещественными корнями к некоторой функции. Для этого необходимо обеспечить выполнение определенных условий. Рассматриваются требования, которые необходимо наложить на распределение нулей и полюсов функции некоторой функции R(x), а также пределов интегрирования, для выполнения этих условий.
Рассматривается задача выражения одних параметров (значения полюсов, нулей, пределов интегрирования) критерия через другие. Сложность такой задачи в основном определяется трудностью решения некоторого уравнения п-ной степени.
Доказано, что применение критерия для оценки скорости сходимости рядов по системе многочленов с вещественными корнями возможно при п=3 и п=4. Высказана гипотеза о возможности использования данного выражения для любых п при определенных условиях.
Третья глава посвящена разложению функций, представляющих криволинейные объекты геоинформационных систем по базисным функциям вспле-сковых систем. Предлагается использовать для представления криволинейных объектов функции из пространства L2(R). Функции такого класса представляют большой интерес в силу того, что являются моделями реальных физических сигналов. Основная особенность функций из L2(R) - это то, что все они являются ограниченными по мощности.
Рассматривается широкий класс функций, называемых всплесками. В качестве области применения всплесков отмечена возможность построения на их основе базиса в L2(R).
Отмечаются преимущества получаемого на основе всплесковых базисов разложения по сравнению с классическим рядом Фурье. Это локализованность и масштабирование, которые являются характерными для всех всплесковых разложений.
Предложен алгоритм разложения некоторой функции из пространства L2(R) по базисным функциям определенной всплесковой системы. Алгоритм отличается от, например, разложения Фурье скоростью вычисления, т.к. количество вычисляемых на каждом шаге коэффициентов разложения уменьшается в два раза по сравнению с предыдущим шагом. При необходимости вычисления большого количества коэффициентов, а это дает затем высокую точность восстановления исходной функции, время работы алгоритма существенно сокращается.
Приведены уточненные для системы Хаара формулы вычисления коэффициентов разложения, обеспечивающие значительное сокращение общего числа операций за счет того, что на каждом шаге вычисляются только те числа, коэффициенты которых отличны от нуля.
Получена формула для количества операций во всем алгоритме разложения для всплесковой системы Хаара. Описан способ определения количества операций для других всплесковых базисов.
Четвертая глава посвящена разработке программного комплекса, реализующего разработанный алгоритм разложения и восстановления функций из пространства L2(R). В качестве среды разработки была использована среда Microsoft Windows, которая является одной из самых распространенных опера- ционных систем в настоящее время. В качестве средства разработки были использованы средства Borland Delphi, предоставляющие широкий набор инструментов для проектирования и реализующие объектный подход к программированию.
Приведены требования, предъявляемые при разработке программного комплекса: комплекс предоставляет пользователю интуитивно-понятный интерфейс; комплекс позволяет задавать диапазон изменения параметра к, характеризующего количество отсчетов; реализована возможность перенаправления информации в дисковый файл для хранения; реализована возможность отдельного вычисления исходной информации; реализована возможность задания точности вычисления (округления результатов).
Программный комплекс имеет модульную структуру. В нем выделяются следующие модули: модуль вычисления исходной информации; модуль вычисления функции скалярного произведения; модуль вычисления коэффициентов разложения d& модуль вычисления вспомогательных коэффициентов s'k, модуль вычисления коэффициентов hk и gk. Приводится структура программного комплекса.
Дано краткое описание руководства пользователя. Приведены вычисленные с помощью разработанного программного комплекса коэффициенты /г^и gk в диапазоне к от -8 до 8.
Разработанный программный комплекс предполагается использовать в учебном процессе, лабораторном практикуме для рассмотрения способов представления информации в ЭВМ.
В качестве примера найдено разложение функций /(/) = /2+1 (~3)2, 02(R), и, следовательно, применение к ним разработанного алгоритма возможно.
В заключении приводятся основные результаты работы.
Организация представления пространственных данных в геоинформационных системах
При создании инструментальных геоинформационных систем общего назначения перед коллективом разработчиков сразу же возникает множество проблем, как технологических, так и концептуальных.
Первая задача - определение концепции новой системы: основных понятий, которые будут лежать в основе ГИС, а также объектов и процедур обработки информации, на основе которых будет строиться система [21, 51, 98]. Подходить к решению этой задачи необходимо очень ответственно, так как именно концепция будущей системы и совершенство модели данных определят её успех и живучесть на рынке. При этом разработчику приходится учитывать множество факторов - достоинства и недостатки концепций уже существующих систем, постоянно изменяющиеся требования со стороны прикладных задач, которые должна будет решать система, изменения в информационных технологиях и многое другое.
После определения концепции новой системы и базового набора её функциональных возможностей во весь рост встают технологические проблемы; как сделать так, чтобы а) система работала быстро с большими и даже гигантскими объемами данных; б) корректно работала в локальной сети при совместной работе многих пользователей; в) предоставляла возможность распределенной обработки данных в масштабе территории (например, многих организаций в городе), и множество других вопросов.
При разработке концепции ГИС нужно определиться с принципиальным выбором: взять за основу архитектуру одной из существующих систем и в дальнейшем приступить к её "улучшению", создавая свою версию архитектуры (другими словами, заняться определённым копированием чужих идей); взяться за разработку принципиально новой архитектуры, не имеющей аналогов.
Оба подхода имеют и достоинства, и недостатки [98]. В первом случае самой серьёзной проблемой является перспектива "изобретения велосипеда", и если его рыночная цена ещё и не очень сильно уступает цене других аналогичных систем, добившихся успеха на рынке, то новой ГИС суждено так и остаться в аутсайдерах. Основная причина неудачи - отсутствие в реализованном продукте технологической новизны в необходимом масштабе.
Второй путь позволяет создать, возможно, удивительный продукт, но существует опасность в его самобытности переборщить настолько, что потребителю будет непонятна вся глубина подхода, да и конкуренты постараются испортить впечатление от продукта. Только немалые вложения в разъяснения и рекламу способны позволить продукту завоевать рынок. Усложнить дело могут ошибки, связанные отладкой новой технологии. Таким образом, основной недостаток второго пути - прямая противоположность статичности - чрезмерная революционность.
Здравый смысл подсказывает, что целесообразно избрать в качестве руководства к действию "золотую середину", с которой связан эволюционный подход. В соответствии с ним до разработки необходимо проанализировать состояние технологий в предметной области, для которой создаётся ГИС, выявить проблемы, которые требуют своего быстрейшего решения, ознакомиться с существующими архитектурами ГИС, определить их недостатки и разработать новую архитектуру (концепцию) ГИС, избавленную от недостатков, осложняющих эффективное решение наиболее важных проблем предметной области.
Следование эволюционному подходу может привести к появлению такого продукта, в котором есть немало новаторских решений, который удобен в работе, позволяет решать задачи предметной области и не слишком шокирует пользователей, имеющих опыт работы с другими геоинформационными системами.
Геоинформатика - весьма молодая область, если учитывать, что первые достаточно серьёзные технологии в этой области появились в последнее де сятилетие (однако первые системы, относимые к ГИС, - возникли примерно 25-30 лет назад). Основным недостатком большинства существующих на сегодня инструментальных ГИС является недостаточная продуманность в подходе к формированию цифровой карты как существенно нереляционной модели данных [98].
Если рассматривать чисто предметный аспект, то, как правило, структура карты представляется линейным списком слоев. Пользователям таких систем достаточно создать один слой и можно сразу приступать к наполнению электронной карты пространственными объектами. Через некоторое время появляется красивая электронная карта участка территории и появляется иллюзия, что работы ведутся в нужном направлении. Лишь по прошествии некоторого времени пользователи начинают понимать, что все созданное является лишь картинкой, не столько подготовленной к автоматизированному анализу, сколько просто копирующей бумажные карты.
Для адекватного отражения объектов реального мира концепции слоев недостаточно - необходим современный объектно-ориентированный подход [51, 98]. При использовании инструментальных ГИС, реализующих такой подход, создание электронных карт начинается с анализа тех объектов реального мира, которые будут присутствовать в электронной карте. По результатам анализа при помощи объектно-ориентированных средств ГИС формируется классификация объектов, и лишь затем начинается наполнение электронной карты экземплярами пространственных объектов.
При проектировании современной инструментальной ГИС необходимо уделить повышенное внимание концепции и процедурам формирования классификатора пространственных объектов [21].
Для начала вместо термина слой необходимо ввести термин класс пространственных объектов, для которого определяется набор характеристик, присущих всем объектам данного класса. ГИС должна предоставлять пользователям возможность организации перечня всех классов не в виде линейного списка, а в виде множественных пересекающихся иерархий (не иерархии, по добной наследованию классов, а системе иерархий, подобной применяемой в файловой системе - каталоги и ссылки - ярлыки). Данное требование обусловлено тем, что при составлении сложных муниципальных карт, приходится оперировать не десятками, а сотнями и даже тысячами классов пространственных объектов.
Представление энтропии конечных схем интегралами от рацио нальных функций
Один из способов нахождения приближенного значения определенного интеграла состоит в замене его линейной комбинацией из конечного числа значений интегрируемой функции. Такие соотношения принято называть квадратурными формулами [54]. Понятно, что формула определяется выбором узлов интерполирования и соответствующих коэффициентов линейной комбинации. Следуя Гауссу, узлы можно выбрать так, чтобы формула была точной для возможно большего числа функций из некоторой заранее заданной счетной системы сок(х), к=0,1,2,.. . Собственно Гаусс решил такую задачу для случая полиномов, т.е. когда соь(х)=х2. Позднее аналогичные результаты были получены для других систем функций, например для достаточно широкого класса рациональных функций. Однако, до настоящего времени не рассматривалась задача обратная к данной. Пусть правая часть квадратурной формулы составлена из линейной комбинации значений некоторой заранее заданной функции, например натурального логарифма. Требуется определить, существует ли подынтегральные функции и пределы интегрирования, для которых квадратурная формула точна.
С такой постановкой задачи тесно связана проблема квадратур интегралов, зависящих от параметра в подынтегральной функции. Некоторое специальные случаи указанной задачи изучены в работах В.И. Крылова [54], а в последнее время получили естественное развитие в теории всплесков [57, 71,72]. Решение обратной задачи теории квадратур для логарифмической функции представляет особый интерес, т.к. хорошо известно, что энтропия конечной схемы определяется формулой К. Шеннона: В связи с поставленной задачей заметим, что имеет место соотношение р(х) где R(x) = - -L является некоторой рациональной функцией, Р(х) и Q(x) яв ляются приведенными полиномами, степень Р(х) меньше степени Q(x), множество {аХ.х - простые корни Q{x). Числа \ , \ должны быть соизмеримы над полем рациональных чисел. Тогда можно сказать, что ы /-і U \ai) При последующем рассмотрении (2.6) возникает мысль использовать данное выражение в качестве энтропийного критерия скорости сходимости рядов по системе многочленов с вещественными корнями. Для этого необходимо определить, существуют ли подынтегральные функции и пределы интегрирования, для которых выполняются условия (2.8). Можно предположить R(x) = "" , где {я„(х)}Г=1 - система многочленов с вещественными корнями. Эта задача является весьма актуальной, учитывая то, что с помощью таких многочленов возможно представить некоторую функцию из /,2(7?,). Таким образом, сделанное предположение будет являться важным для исследования с точки зрения представления определенного класса функций в машинной памяти. Для случая п=2 утверждение (2.6) уже было полностью доказано в [2].
Для п=3 запишем R(x) в следующем виде: Попробуем для извлечения квадратного корня из дискриминанта (2.25) применить теорему Маркова-Лукача о неотрицательных многочленах. По этой теореме всякий неотрицательный в [а,Ь] алгебраический многочлен степени меньшей либо равной п имеет вид (в нашем случае n=2v, т.е. четное): (некоторый многочлен степени у)2 + (6-/)(/-я)(некоторый многочлен степени У-1)2, t - переменная, в нашем случае это х2. Дискриминант (2.25) является положительным, если х2 у, другими словами, он положителен на отрезке [у, т], где т - некоторый параметр. Тогда можем записать следующее уравнение: 1. Предложен способ представления энтропии конечных схем, интерпретирующий энтропию посредством взаимного расположения нулей и полюсов некоторой мероморфной функции специального вида. 2. На основе разработанного способа представления энтропии конечных схем предложено использование критерия для оценки скорости сходимости рядов по системе многочленов с вещественными корнями к некоторой функции. 3. Выражение одних параметров (значения полюсов, нулей, пределов интегрирования) критерия через другие представляет собой сложную задачу.
Сложность в основном определяется трудностью решения некоторого уравнения «-ной степени. Для решения этой задачи предлагается использовать теорему Маркова-Лукача и способ Феррари. 4. Доказано, что применение критерия для оценки скорости сходимости рядов по системе многочленов с вещественными корнями возможно при п=3 и п=4. Делается предположение о том, что использование данного критерия возможно и при любых других значениях п.
Система Хаара как всплесковый базис для разложения функций из пространства ДгСФ
Первое преимущество состоит в том, что ряд Хаара является хорошо локализованным. Если мы интересуемся поведением функции / на подынтервале [а, Ь], то в разложении (3.34) мы берем только те индексы/ и к, для которых suppt//"k =[k2 J,(k + l)2 J\ пересекается с [a, bj, тогда как в разложении (3.35) нам потребуются все коэффициенты. Второе отличие состоит в том, что частичная сумма ряда Хаара по/ = 0,1,2,..., N является приближением исходной функции с точностью до масштаба 2 N l. Эти два свойства, лока-лизованность и масштабирование, являются характерными для всех всплесковых разложений. Суть кратномасштабного анализа заключается в возможности построения новых всплесковых базисов. Приведенный ниже метод учитывает все свойства, которыми должен обладать создаваемый базис. Далее выводы полученные в теории кратномасштабного анализа будут использованы нами в построении алгоритма разложения и восстановления функций. Наиболее распространенным является следующее определение крат-номасштабного анализа [71, 72]. Кратномасштабный анализ (КМА) - это последовательность {У; } eZ замкнутых подпространств L2(R), удовлетворяющая следующим свойствам: существует функция (peV0 такая, что последовательность {p( -k)}keZ образует базис Рисса в Vo. Если обозначить через Р3 ортогональный проектор на Vj, то из условия (3.37) следует, что lim Pjf = f для любой функции feI?(R). Условие (3.39) означает, что все подпространства Vj однозначно определяются из центрального подпространства Vo при помощи соответствующей замены переменных (соответствующего изменения масштаба). Из (3.39) и (3.40) следует, что для любой функции /еУ; функция f(—2 Jk) также принадлежит Vj при любом keZ. Пусть (pjk(t):=2inp(2Jt-k);j,kєZ. Из (3.39) и (3.41) следует, что последовательность { pjk )JeZ является базисом Рисса в Vj для любого / є Z. Не ограничивая общности, можно считать, что {# (--&)}2 - ОНБ в Vo (этого всегда можно достичь за счет ортогонализации (3.28)). Основным свойством КМА является возможность построения орто-нормированного всплескового базиса \yjk) keZ,y/jk(t) = 2J,2i//(2Jt-k), такого, что для любой функции / из L2(R)
Рассмотрев понятие кратномасштабного анализа, перейдем непосредственно к описанию процесса построения базиса, удовлетворяющего (3.42) [71]. Пусть Wj - это ортогональное дополнение Vj до V r - WtV}= VJtX. В силу (3.36) Последовательность {w}JeZ наследует от свойство Формула (3.42) эквивалентна тому, что при фиксированному последовательность yf/jkl z образует ортонормированный базис в Wj. В силу (3.45) последнее означает, что \fjk\jHZ - ортонормированный базис в L2(R). Заметим теперь, что свойство (3.46) гарантирует, что {v0 ) 6z будет базисом в W), если {у/ок }keZ является базисом в W0. Таким образом, задача построения вспле-скового базиса со свойством (3.42) сводится к нахождению функции ці такой, что последовательность {y(--k)}keZ образует ортонормированный базис в Wo. Для построения функции у/ нам потребуются некоторые свойства (р и W0. Так как cpeV0ciVl и щк }keZ - ортонормированный базис в VJt то Отметим, что на основании (3.47) построен весь алгоритм разложения и восстановления функций, приведенный далее.
Переходя к образам Фурье, имеем где т(а,) = 2Щ кег ке ка -Функцию ip называют масштабирующей (scaling), равенство (3.47)-масштабным, равенство (3.49) - уточняющим (refinement), функцию т - уточняющей маской (refinement mask) или масштабирующим фильтром (scaling filter). В силу доказанной выше теоремы для почти всех т. Если подставить (3.49) в (3.50), то получим, что Разбивая сумму на две (по четным и по нечетным Г) и учитывая 2п- периодичность w, имеем Охарактеризуем подпространство Wo в терминах образов Фурье [71]. Любая функция / из Wo принадлежит V/ и ортогональна Vo. Первое свойство означает, что / = Ы2/к9 и ГДЄ / = {/»Ри)« В образах Фурье имеем
Описание архитектуры программного комплекса
В общей структуре ГИС разработанный программный комплекс является подсистемой представления пространственных данных. Он представляет собой отдельный модуль, на вход которого подается описывающая пространственный объект функция, а на выходе мы имеем коэффициенты разложения функции по всплесковому базису. На программном уровне подсистема представления пространственных данных может быть реализована либо как DLL-библиотека, либо с помощью современных СОМ-технологий. Данный программный комплекс может быть использован в учебном процессе, например, в лабораторных работах для понимания способов представления информации в вычислительных машинах. При изучении же таких учебных дисциплин как, например, теория информации, программа поможет сверять результаты разложения некоторой функции, полученные вручную, с их машинным вычислением. Также возможно поставить обучаемым задачу восстановления функции по ее всплесковым коэффициентам, задав им в качестве начальных данных набор коэффициентов, представляющих исходную информацию. Различие между процессами работы программного комплекса в диалоговом (использование в учебном процессе) и недиалоговом (использование в ГИС) режимах заключается лишь в том, что исходную функцию и количество отсчетов пользователь задает вручную, а при работе внутри ГИС комплекс получает эту информацию из модуля растрово-векторного преобразования.
После окончания же разложения функции коэффициенты разложения передаются в модуль взаимодействия с базами данных (использование внутри ГИС), либо выводятся на экран (использование в учебном процессе). Разработанный программный комплекс имеет так называемую модульную структуру. Он состоит из отдельных самостоятельных подпрограмм (процедур и функций), взаимосвязанных между собой. Информация с выходов одних модулей подается на входы других, причем каждый модуль может быть связан с несколькими другими. В программном комплексе выделяются следующие модули: 1) модуль вычисления исходной информации; 2) модуль вычисления функции скалярного произведения; 3) модуль вычисления коэффициентов разложения d\; 4) модуль вычисления вспомогательных коэффициентов s k; 5) Модуль вычисления коэффициентов /і И gk. Структура программного комплекса приведена на рис. 4.2. Структура программного комплекса Опишем назначение каждого из модулей. Модуль вычисления исходной информации предназначен для вычисления на основе заданной и предназначенной для разложения функции, а также масштабирующей функции Хаара, исходной информации so. Он связан двусторонней связью с модулем вычисления скалярного произведения, в который передает информацию об исходной функции и количестве отсчетов. А затем получает обратно исходную информацию в виде вычисленных скалярных произведений. Модуль вычисления функции скалярного произведения является основополагающим модулем системы. Он основан на методе Симпсона для вычисления определенных интегралов, которыми, как известно, и определяется скалярное произведение.
Т.к. во всплесковой системе Хаара отсутствует мнимая составляющая, то нет необходимости в вычислении комплексно-сопряженной функции, и вычисляется только определенный интеграл. Данный модуль взаимосвязан с модулем вычисления исходной информации и модулем вычисления коэффициентов hkU gk- Исходными данными для модуля являются две функции, а выходными данными - их скалярной произведение. Модуль вычисления коэффициентов разложения d\, как видно из названия, вычисляет соответствующие коэффициенты разложения. В качестве исходной информации он получает на первом шаге данные из модуля вычисления исходной информации, на последующих шагах - данные из модуля вычисления вспомогательных коэффициентов Jk. На каждом шаге осуществляет взаимодействие с модулем вычисления коэффициентов hk и gh Модуль вычисления вспомогательных коэффициентов s?k на первом шаге получает исходную информацию из модуля вычисления исходной информации, на последующих шагах свою выходную информацию на предыдущих итерациях. На каждом шаге осуществляет взаимодействие с модулем вычисления коэффициентов hk и gk. Предоставляет входные данные для модуля вычисления коэффициентов разложения. Модуль вычисления коэффициентов hk и gk предоставляет на каждом шаге информацию для модулей вычисления коэффициентов разложения и вспомогательных коэффициентов. Взаимодействует с модулем вычисления функции скалярного произведения (в силу (3.48)).
Для более наглядного понимания устройства и принципов работы программного комплекса приведем DFD-диаграммы, описывающие основные процессы и потоки данных в комплексе. На рисунке 4.3 представлена контекстная диаграмма процесса разложения функции, представляющей некоторый пространственный объект. Контекстная диаграмма процесса разложения функции В данном случае мы имеем одну внешнюю сущность - ПОЛЬЗОВАТЕЛЬ. Для получения коэффициентов разложения некоторой функции, ПОЛЬЗОВАТЕЛЮ необходимо задать саму функцию и количество отчетов, влияющее на точность и скорость вычисления. Процесс РАЗЛОЖИТЬ ФУНКЦИЮ, представленный на контекстной диаграмме, может быть детализирован DFD-диаграммой 1-го уровня, представленной на рисунке 4.4. Детализация процесса РАЗЛОЖИТЬ ФУНКЦИЮ Эта диаграмма содержит 5 процессов и хранилище данных КОЭФФИЦИЕНТЫ S1 Процесс 1.1 (Вычислить исходную информацию sn) обеспечивает получение исходной информации для последующей работы программы. Он имеет на входе и выходе следующие потоки: - входной поток ИСХОДНАЯ ФУНКЦИЯ содержит информацию о виде функции, для которой вычисляются коэффициенты разложения; - входной поток КОЛИЧЕСТВО ОТСЧЕТОВ определяет число итераций на каждом шаге разложения. От его значения зависит точность и скорость разложения; - входной поток (f, p0tk) несет вычисленные скалярные произведения; - выходной поток ЗНАЧЕНИЯ/и (ро,к передает вид раскладываемой функции и базисной функции. Процесс 1.2 (Вычислить скалярное произведение) определяет скалярное произведение двух поступающих на его вход функций. Он имеет на входе и выходе следующие потоки: - входной поток ЗНАЧЕНИЯ /и (ро,к передает вид раскладываемой функции и базисной функции;
