«Гришин Максим Леонидович Связь с автором: MaxAkaAltmer МЕТОДЫ ПОСТРОЕНИЯ ИНФОРМАЦИОННОИЗМЕРИТЕЛЬНЫХ СИСТЕМ ГЛОБАЛЬНОГО ГЕОМОНИТОРИНГА ПОДВИЖНЫХ ОБЪЕКТОВ В РЕАЛЬНОМ ВРЕМЕНИ Специальность 05.11.16 – ...»

МИНОБРНАУКИ РОССИИ

Федеральное государственное бюджетное образовательное

учреждение высшего профессионального образования

«Тульский государственный университет»

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

Гришин Максим Леонидович

Связь с автором: [email protected]

МЕТОДЫ ПОСТРОЕНИЯ ИНФОРМАЦИОННОИЗМЕРИТЕЛЬНЫХ СИСТЕМ ГЛОБАЛЬНОГО

ГЕОМОНИТОРИНГА ПОДВИЖНЫХ ОБЪЕКТОВ

В РЕАЛЬНОМ ВРЕМЕНИ

Специальность 05.11.16 – Информационно-измерительные и управляющие системы (промышленность) Диссертация на соискание ученой степени кандидата технических наук

Научный руководитель:

д.техн.н., профессор Данилкин Ф.А.

Тула Содержание Введение

1. Структура информационно-измерительных систем геомониторинга подвижных объектов

1.1. Жизненный цикл измерительной информации

1.2. Механизмы сжатия результатов измерений

1.3. Модель геосферы

1.4. Выводы

2. Информационно-измерительное обеспечение систем геомониторинга подвижных объектов

2.1. Измерение позиции подвижного объекта с учетом избыточной информации

2.2. Сжатие пакетов измерительной информации в датчике контроля состояния подвижного объекта

2.2.1. Адаптивное разностное кодирование сигналов и битовых полей...... 2.2.2. Префиксный код с регулируемым приращением

2.3. Архивирование измерительной информации

2.3.1. Аффинно-разностное сжатие цифровых сигналов

2.3.2. Комбинаторное кодирование информации

2.4. Прямая сегментация геосферы на основе пучков плоскостей

2.5. Выводы

3. Разработка систем глобального геомониторинга подвижных объектов........ 3.1. Построение протокола датчик-сервер

3.2. Методика проектирования датчиков контроля состояния подвижного объекта

3.3. Устройство архиватора измерительной информации

3.4. Интеграция разработанного метода сегментации геосферы

3.4.1. Геозависимая обработка измерительной информации

3.4.2. Трехмерная визуализация

3.4.3. Импорт и экспорт картографического материала

3.5. Выводы

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

4.1. Тестирование фильтра данных о позиции объекта измерения................ 4.2. Испытания механизмов сжатия результатов измерений

4.2.1. Оценка компактности протокола датчик-сервер

4.2.2. Показатели алгоритмов архивирования результатов измерений...... 4.3. Сравнение методов сегментации геосферы

4.4. Разработанное программное и аппаратное обеспечение

4.5. Выводы

Заключение

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

Приложение 1. Табличная функция для фильтра данных о позиции................ Приложение 2. Акт об использовании результатов кандидатской диссертационной работы

Приложение 3. Способ калибровки фильтра данных о позиции объекта измерения

Приложение 4. Примеры префиксных кодов

Приложение 5. Расчеты взаимодействия векторных примитивов и траектории объекта на геосфере

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

Введение Актуальность темы.

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

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

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

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

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

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

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

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

Работ посвященных системам геомониторинга подвижных объектов очень мало, что обусловлено сравнительно короткой историей подобных систем, основную часть составляют диссертации [69; 70; 71] и публикации, посвященные отдельным узкоспециализированным вопросам геомониторинга подвижных объектов. В современной теории информационно-измерительных систем [64; 65; 66; 67; 68] системы геомониторинга подвижных объектов редко рассматриваются как самостоятельный класс, при этом уделено недостаточное внимание их геоинформационному аспекту, который определяет процессы визуализации и геозависимого анализа измеряемой информации. Труды, посвященные геоинформационным [72; 75; 77; 79; 82] и глобальным навигационным [88; 89; 90; 91; 92] системам, позволяют во многом компенсировать недостаток специализированной литературы, но это не заменяет целостный подход в рассматриваемой области.

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

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

Аналитический обзор материала связанного с обработкой измерительной информации [65; 67; 68; 69; 70; 71; 72] выявил слабую освещенность следующих вопросов. Недостаточное внимание уделено способам сокращения избыточности данных о местоположении, притом, что данные о позиции могут составлять до 100% транслируемой датчиком информации. Слабость подходов в области построения протоколов передачи измерительной информации с точки зрения универсальности и возможностей сжатия. Под универсальностью подразумевается не всеобъемлющий охват всего разнообразия измерительной информации, а возможности протоколов по расширению состава данных без необходимости обновлять реализацию принимающей информацию серверной части. Сжатие результатов измерений в канале передачи данных рассматривается в отрыве от конкретного подхода к построению протокола, что не может не сказываться на качестве конечных решений. Открытым остался вопрос архивирования накапливаемой в системе измерительной информации, универсальные методы дают хорошие результаты, но если в процессе архивации учитывать специфику данных, то можно добиться большей степени сжатия.

измерительной информации, а также доступа к данным с географической геоинформационных систем [72; 75; 76; 77; 78; 79; 81; 82], основное внимание было уделено глобальным системам, которые являются относительно новыми и в силу этого слабо представлены в научной литературе. Отмечено, что уделяется мало внимания модели геосферы, от которой зависят процессы организации, визуализации и геозависимой обработки результатов измерений.

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

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

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

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

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

3) Разработать методику применения созданных алгоритмов для проектирования информационно-измерительных систем глобального геомониторинга подвижных объектов.

4) Провести экспериментальные исследования и оценить качество предложенных решений.

В работе использовались методы исследования из следующих областей:

теории цифровой обработки сигналов, теории кодирования и сжатия информации, теории вероятностей, теории алгоритмов, сферической тригонометрии и математической картографии. При этом использовались труды отечественных и зарубежных ученых: Волынский Б.А., Клейн Ф., Ландау Л.Д., Мальдеброт Б.Б., Степанов Н.Н., Тот А.Ф., Амелькин В.А., Левенштейн В.И., Давыдов А.В., Белл Т., Серапинас Б.Б., Ленгли Р.Б., и др. Разработка алгоритмов и программ осуществлялась с применением императивной, обобщенной и объектно-ориентированной парадигм программирования.

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

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

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

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

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

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

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

Положения, выносимые на защиту.

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

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

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

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

нижеуказанных конференциях: Всероссийская научно-техническая конференция. «Интеллектуальные и информационные системы» (Тула, ТулГУ, 2007-2011 гг.). 2. Итоговые научные конференции (Тула, ТулГУ, 2008-2010 гг.).

3. 4th International Conference «Earth From Space – The Most effective Solutions»

(Moscow, 2009). 4.

комплексов, средств управления войсками и оружием. (Тула, Тульский АИИ, 2010г.). 5. Международная научная заочная конференция «Актуальные вопросы техники и технологии» (Липецк, 2011г.). 6. Актуальные проблемы науки:

Международная научно-практическая конференция. (Тамбов, 2011.).

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

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

1. Структура информационно-измерительных систем геомониторинга подвижных объектов Все многообразие современных информационно-измерительных систем геомониторинга подвижных объектов сводятся к общей структуре (рис. 1.1). В основе рассматриваемой системы лежат: глобальные навигационные системы [89; 90; 91] (ГЛОНАСС [88], GPS [92]); беспроводные сетевые технологии;

сервера баз данных; геоинформационные системы [82]; датчики контроля состояния подвижного объекта измерения [106; 115] (далее просто датчики).

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

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

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

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

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

2) Сенсорный элемент для приема спутниковых навигационных сигналов систем ГЛОНАСС, GPS и/или другой системы. Как правило, подобные сенсоры представляют собой модуль с последовательным интерфейсом, который поддерживает протокол вещания NMEA [94].

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

4) Буферный элемент на основе энергонезависимой памяти – служит для хранения настроек и записи результатов измерений при отсутствии связи с сервером. Самой оптимальной на данный момент является флешь память.

Типичный прикладной программный комплекс (ППК) (рис. 1.2) информационно-измерительных систем геомониторинга состоит из двух частей: программного обеспечения (ПО) сервера и диспетчерских терминалов.

В основе которых выделяется ряд базовых программных компонент:

1) база данных мониторинга;

2) геоинформационная база данных;

3) средства моделирования геопространства;

4) средства формирования отчетов;

5) протоколы взаимодействия составляющих ППК.

Рис.1.2. Структура прикладного программного комплекса База данных мониторинга представляет собой набор таблиц (рис. 1.3), которые делятся на три группы.

1) Структура служебных таблиц зависит от специфики проектируемой системы геомониторинга.

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

3) Технические таблицы хранят записи полезные администраторам.

Рис.1.3. Состав базы данных мониторинга Геоинформационная база – это многомерный информационный массив (рис. 1.4), в котором хранятся разнородные данные с географической привязкой. В геоинформации можно выделить до семи измерений: первые три измерения являются пространственными координатами, четвертым измерением является время, остальные три измерения являются искусственными и введены для классификации данных. Пятое измерение отвечает за хранение разных уровней детализации пространственных данных, необходимых для быстрого масштабирования при визуализации геопространства. Шестое измерение – это набор слоев. Слои отвечают за разделение геоданных по их типу и форме представления. По форме представления пространственные данные делятся на растровые и векторные слои. Типы пространственных данных крайне разнообразны. Это могут быть карты дорог, растительности, высот, батиметрии и другая пространственная информация. Седьмое измерение отвечает за альтернативные версии или варианты геоинформации.

Рис.1.4. Организация массива геоинформации Средства визуализации геопространства отвечают за формирование сцены окна геомониторинга и используют широкий набор программных техник, могут быть реализованы в виде WEB-приложения или компьютерной программы. В глобальных системах мониторинга геопространство подвергается сегментации, в рамках которой часто применяют технологии квадротомических деревьев [21] для управления детализацией и виртуальные текстуры [26] для визуализации огромных (до сотен гигабайт) растровых карт, например Google Earth или NASA World Wind [73].

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

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

Протокол доступа к данным геомониторинга, как правило, реализуется через язык запросов к используемой базе данных. Протокол доступа к геопространственной информации определяется ее структурой, которая может быть крайне сложной и разнородной, поэтому наибольшую популярность в данной области, несмотря на избыточность, приобретают XML-подобные решения [95]. Примерами могут служить KML [99] в Google Earth и OSM-XML в OpenStreetMap [86].

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

1.1. Жизненный цикл измерительной информации В жизненном цикле измерительной информации систем геомониторинга подвижных объектов можно выделить несколько периодов по месту пребывания результатов измерений:

1. Период накопления результатов измерений датчиком, длительность которого зависит от наличия связи с сервером.

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

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

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

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

Таблица 1.1. Классификация и типизация измерительной информации Класс Основной Прикладной Первоначальная обработка измерительной информации подразумевает количественных показателей и цифровую фильтрацию сигналов [47; 48] для устранения шума, дребезга и некорректной информации, а так же удаления в процессе измерения избыточных данных, не дающих новой информации о измерительной информации, то особого внимания заслуживает обработка пространственных данных играет ключевую роль в процессе геомониторинга и, как правило, составляет большую часть измерительной информации. Данные о позиции принято делить на две составляющих.

1) Относительные данные – это результат работы инерциальной навигационной системы, в основе которой лежат акселерометры, гироскопы, магнитометры и другие датчики, способные дать полезную информацию о движении объекта.

2) Глобальные данные – основным источником является глобальная система навигации (ГЛОНАСС/GPS). При отсутствии сигналов со спутников в качестве дополнительных источников данных глобальной позиции наблюдаемого объекта могут использоваться радио-метки [14] и пеленг приемо-передатчика в пределах беспроводной сети.

Точность относительных данных о позиции объекта значительно выше глобальных, но относительная информация имеет свойство накапливать ошибку и не способна дать ответ на то, в какой точке земного шара находится объект без периодического обновления глобальной составляющей. Поэтому инерционная навигационная система либо не используется, либо дополняет глобальную систему навигации. Во втором случае возникает необходимость в интеграции данных обеих систем, которая эффективно решается с помощью различных модификаций фильтра Калмана [52, 53, 63]. В некоторых работах для интеграции навигационных систем предлагается использовать нейронные сети, в том числе совместно с фильтром Калмана [54, 58, 59].

Данные пространственного положения в чистом виде неудобны для использования, несут много излишней информации и часто содержат значительный шум (рис. 1.5). Источниками шума глобальных данных позиционирования являются погрешности часов спутников, неравномерное распространение спутниковых сигналов в атмосфере Земли, погрешности вносимые приемником, геометрия расположения спутников, отражения сигналов и другие факторы [89; 90; 92], а шум относительных данных будет ограничен погрешностью датчиков инерциальной навигационной системы.

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

Рис. 1.5. Пример необработанных данных о позиции неподвижного объекта Фильтрацию данных о позиции наблюдаемого объекта наиболее разумно реализовывать на измерителе (датчике) в процессе их формирования, что значительно снижает нагрузку на канал передачи данных и сервер, но такой подход требует со стороны алгоритма минимум вычислений, посильный для большинства микроконтроллеров. Выявленные решения в данной области основаны на прореживании выборок по времени, расстоянию, скорости, фактору потери точности [93] и/или прямолинейности траектории [55, 62]. В некоторых работах предлагается предварительно использовать фильтр Калмана [55]. Рассмотренные решения имеют недостатки.

1) Ошибки связанные с механизмом предсказаний в фильтре Калмана, которые проявляются в виде «заносов» объекта на поворотах. В процессе интеграции навигационных систем такой эффект отсутствует, поскольку вместо предсказания вектора состояния подвижного объекта используются показатели инерционной навигационной системы, то есть предсказание заменяется фактами. В некоторых работах [61] для компенсации данного эффекта предлагается делать коэффициент усиления измеренного значения тем ближе к единице, чем выше скорость объекта. Но в таком случае оценка погрешности на выходе фильтра теряет смысл и не может считаться достоверной.

2) Потеря полезной информации при прореживании по времени, расстоянию и скорости.

3) Нарушение режима реального времени при прореживании по прямолинейности траектории.

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

В процессе трансляции измерительная информация подвергается ряду преобразований в рамках используемого протокола датчик-сервер, от которого напрямую зависит удобство разработки и объем полезной передаваемой информации. Все рассмотренные открытые протоколы датчиков состояния подвижного объекта делятся на бинарные и текстовые. В качестве примеров можно привести: Meiligao [98], OpenDMTP [100] и Wialon IPS[102]. Бинарные протоколы в отличие от текстовых обладают большей компактностью представления данных, но менее гибкие и удобные в использовании, поскольку поля имеют жесткую разметку. Помимо основной функции заключающейся в обмене данными и командами между сервером и датчиком, протокол может криптографическая защита и сжатие данных. Контроль целостности реализован в подавляющем большинстве рассмотренных протоколов, остальные функции отсутствуют, но могут быть реализованы протоколами нижнего уровня. Тем не менее, отсутствие сжатия измерительной информации является существенным упущением, поскольку сжатие информации с учетом ее структуры и специфики является наиболее эффективным. Ни один из рассмотренных протоколов не позволяет описывать структуру транслируемой измерительной информации.

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

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

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

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

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

1.2. Механизмы сжатия результатов измерений Исходный поток результатов измерений типичного датчика невелик и составляет несколько десятков байт в секунду, основную долю которых составляют данные пространственного положения (10-20 байт/с); остальные данные, зависящие от назначения датчика, редко требуют ежесекундного обновления, поэтому средний их поток, как правило, значительно ниже потока данных о позиции. Если принять поток данных равным 20 байт/с, то сетевого интерфейса 100 Мбит/с хватит для приема информации от более полумиллиона датчиков, загрузка шины памяти и ресурсов центрального процессора современной системы составит менее одного процента, поэтому можно считать что число датчиков в системе принципиально не ограниченно. Но суммарный объем измерительной информации может быть огромным, например, накопленные за год данные одной тысячи датчиков составят более шестисот гигабайт информации.

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

Таблица 1.2. Цели сжатия измерительных данных и способы достижения Сокращение времени Продление периода архивного хранения Сжатие при предобработке в датчике выполняется фильтром избыточной информации с учетом точности измерений, что, по сути, является сжатием информации с потерями [33; 37] и влияет на достижение всех указанных целей.

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

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

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

Поэлементный подход к сжатию данных измерений представлен слабо, из рассмотренных решений наиболее эффективным является дельта кодирование кодированием [40; 35; 41].

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

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

1.7). Экстраполяция роста производительности относительно пропускной способности шины памяти выполнялась по формуле:

производительности процессоров, k = 1.55 / d – нормализованный новейший коэффициент роста производительности процессора под функцию факториала, а n – число лет экстраполяции.

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

геомониторинга подразумевается сжатая универсальным архиватором (RAR, ZIP, TAR или любой другой) выгрузка из базы данных (наиболее распространен текстовый формат SQL). Данный подход позволяет уменьшить объем архивной измерительной информации в среднем от трех до пяти раз, и с точки зрения объемов современных жестких дисков этого более чем достаточно. Но если рассматривать всю доступную оперативную память, как один большой кэш, в который периодически подгружаются данные из архива и удаляются по мере ненадобности, то роль архивного хранения меняется: сжатие в архиве будет влиять не только на период архивного хранения, но и на время обработки данных измерений. Из графиков на рисунке 1.8 видно, что ресурсы оперативной памяти являются основным барьером при обработке данных измерений большого числа объектов на больших интервалах времени. Как только запросы к серверу на обработку измерительной информации превзойдут указанный барьер, решающую роль начнет играть скорость доступа к данным на жестких дисках, рост которой с каждым годом замедляется (таблица 1.3).

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

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

Референц-поверхности подробно рассматриваются математической картографией. Для большинства планет и их спутников в качестве референцповерхности применяют двухосный эллипсоид, в редких случаях используют трехосный [81]. Для Земли разработано множество эллипсоидов, наиболее распространенным является эллипсоид WGS-84, в России применяется эллипсоид ПЗ-90.

Сегментация поверхности при моделировании геосферы, как правило, рассматривается совместно с выбранной проекцией поверхности на плоскость, за исключением тех случаев, когда картографируемый объект изначально описывается в трехмерном виде, тогда сегментация либо не применяется, либо выполняется по пространственной решетке, которую можно эффективно сочетать с технологией граничащих кубов [22]. Существует большое количество проекций разработанных для плоских карт [81; 84], но в трехмерных геоинформационных системах широкое применение получили лишь цилиндрические проекции, которые используются в таких популярных программах, как «Google Earth», «NASA World Wind» и «Celestia» [85].

Несмотря на широкое применение, сегментация по меридианам и параллелям при трехмерном моделировании дает наихудшее качество сегментной сетки.

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

Наиболее перспективным решением в данной ситуации видится проецирование не на плоскость, а на выпуклый многогранник. Как правило, в качестве опорного многогранника используются Платоновы тела, в редких случаях встречаются проекции на Архимедовы тела, например проекция Фуллера на кубооктаэдр [87]. Из Платоновых тел, как правило, используются куб, октаэдр, и икосаэдр [5], который является идеальным кандидатом (рис.

1.9), поскольку все его грани – правильные треугольники. Проекции на базе икосаэдра известны достаточно давно, но широкого применения не имели, например проекция Фуллера для икосаэдра от 1954-го года [84].

Рис. 1.9. Развертка проекции Земной поверхности на икосаэдр Сегментация на базе икосаэдра, как и любая другая, может быть прямой или итеративной [20]. Единственным выявленным прямым методом является сегментация граней икосаэдра, после чего сегментные вершины поднимаются на геоид, а процесс построения проекции происходит путем опускания точек сферического треугольника на грань через начало координат. Итеративные методы формируют сегменты путем деления дуг, что дает очень хорошее качество сегментной сетки в отличие от предыдущего метода, но итеративный характер процесса не позволяет напрямую вычислить вершины произвольно взятых сегментов, кроме того, обратное преобразование становится трудновыполнимой задачей. Традиционно сегментацию выполняют треугольниками, это обеспечивает строгое подчинение между дочерними и родительскими сегментами, а логическое объединение соседних треугольников в пары формой ромба позволяет оптимально использовать память текстур. Но бывают исключения, когда используют другие примитивы, например, в проекте PYXIS [83] используются шестигранники с узловыми пятигранниками, что несколько снижает производительность.

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

Квадротомическое дерево используется для упорядочивания в двух пространственных измерениях, в случае проекции на икосаэдр деревьев будет десять, а в случае цилиндрической проекции – одно. Индекс сегмента задается строкой цифр с основанием счисления равным ветвлению дерева (рис. 1.10), при этом длина строки соответствует уровню сегментации. Если необходимо работать в трех измерениях, то аналогичным образом применяются октотомические деревья.

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

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

геомипмаппинга [31].

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

Существует множество подходов к моделированию геосферы [23; 27; 28;

29; 30], но ни одно из выявленных решений нельзя назвать в достаточной мере удовлетворяющим данным требованиям.

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

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

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

4) Рассмотрены механизмы сжатия результатов измерений на всех этапах жизненного цикла, выполнена экстраполяция роста ресурсов профессиональных ПК на основе данных за последнее десятилетие для обоснования тактики сжатия измерительной информации в рамках систем геомониторинга подвижных объектов. В результате было сделано два вывода.

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

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

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

2. Информационно-измерительное обеспечение систем геомониторинга подвижных объектов В первой главе диссертационной работы были выявления ключевые элементы информационно-измерительной системы, которые должны быть усовершенствованы для повышения эффективности процессов формирования и обработки измерительной информации. В данной главе будет описано разработанное для этого информационно-измерительное обеспечение, а телеметрической информации в канале передачи данных [110; 112] и архиве [105; 108; 111; 114], а также прямой метод сегментации поверхности геосферы на основе пучков плоскостей [104; 107; 113; 118]. Предложенные методы активно используются при формировании и обработке измерительной информации в выделенных элементах схемы на рисунке 2.1.

Рис.2.1. Упрощенная схема обработки данных в проектируемой системе 2.1. Измерение позиции подвижного объекта с учетом избыточной информации Разработанный метод измерения позиции подвижного объекта основан на программном фильтре, который можно разделить на две части:

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

Рис.2.2. Общая схема фильтра данных о позиции В схеме фильтра (рис.2.2), под оригинальной выборкой подразумевается минимально необходимый набор данных по протоколу NMEA, формируемый модулем определения позиции, далее просто выборка, в географическом смысле – позиция (рис.2.3):

Т – время по Гринвичу (от 1970 года);

– широта в градусах (от -90 до 90, положительное значение примем в соответствие северному полушарию);

– долгота в градусах (от -180 до 180, положительное значение примем в соответствие восточному полушарию);

h – эллипсоидная высота в метрах (может иметь отрицательное значение);

P – позиционный фактор потери точности (в пространстве);

V – вертикальный фактор потери точности (только по высоте);

H – горизонтальный фактор потери точности (на плоскости касательной к рассматриваемой точке поверхности эллипсоида);

M – режим определения местоположения (учитывая разнообразие протоколов и различный подход к формированию данного параметра, обозначим это как набор состояний: 0 – Данные отсутствуют, 1 – Доступно только время, 2 - Двухмерный режим позиционирования, 3 - Трехмерный режим позиционирования).

Рис.2.3. Иллюстрация системы координат Предварительная фильтрация устраняет выборки, которые являются ошибочными, неполными или не соответствуют режиму. На данном этапе фильтрации формируются события «потеря сигнала» и «начало работы фильтра». Дополнительно, в зависимости от требований к качеству данных, можно устранять выборки, в которых значения факторов потери точности выходят за максимально допустимые пределы, указанные в настройках фильтра, при этом все три рассматриваемых фактора потери точности связаны отношением: P = V 2 + H 2 [93].

Алгоритм предварительной стадии фильтрации, изображен на рисунке 2.4. При старте предложенный алгоритм проверяет поступающие выборки до позиционирования M min, для генерации события «начало работы фильтра», затем инициализируются вспомогательные переменные, и начинается основной позиционирования остается неизменным ( M – текущий режим) и отвечает минимальному значению, вызывается фильтр избыточных данных, в противном случае выполняется сброс указанного фильтра, и если новая выборка не отвечает минимальному режиму позиционирования, то формируется событие «потеря сигнала». Для каждой поступающей на вход фильтра (рисунок 2.2) выборки рассчитывается значение точности позиционирования A в метрах.

Рис.2.4. Алгоритм предварительной фильтрации Точность позиционирования A необходима для анализа данных на предмет их избыточности. Аналогично факторам потери точности применяется три типа точности позиционирования [56; 57; 60]:

AP – позиционная точность (в пространстве) в метрах, AV – вертикальная точность (только по высоте) в метрах, рассматриваемой точке поверхности эллипсоида) в метрах.

Известно, что AP, AV и AH зависят от псевдо диапазона измерений и прямо пропорциональны значениям P, V и H соответственно [92]. Поскольку точность позиционирования не определяется из оригинальной выборки, для получения значений AP, AV и AH необходимо экспериментальным путем подобрать коэффициенты к соответствующим значениям P, V и H:

где K P, KV и K H – соответствующие коэффициенты для факторов потери точности в метрах, далее просто коэффициенты, они указываются в настройках фильтра (рисунок 2.2).

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

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

где q – рассматриваемая координата (, или h ) результирующей точки, q j – соответствующие координаты входящих точек, а m j – величины обратно пропорциональные точностям позиционирования Aq для соответствующих результирующей точки рассчитывается как отношение размера кластера с учетом погрешностей по заданной координате к корню квадратному из числа точек входящих в состав кластера. Таким образом, учитывается избыточность измерений [49; 50]:

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

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

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

при этом в качестве A и A для двухмерного случая берется горизонтальная точность центра кластера AH и новой точки AH, а для трехмерного – позиционные точности AP и AP. Если данное условие нарушено, то есть новая выборка не является избыточной, осуществляется переход к формированию выходных выборок и событий. Прежде чем сформировать выборку на основе центра кластера, необходимо проверить совпадает ли время первой T0 и последней T выборок кластера, если нет, формируется событие «начало движения объекта». Это может понадобиться при дальнейшей обработке выборок, например для более точного вычисления скорости наблюдаемого объекта, обнаружения пробок, подсчета времени его нахождения в подвижном состоянии и других случаев, когда важно точно знать момент начала движения.

Если условие кластеризации фильтра избыточных данных выполняется, то осуществляется коррекция центра кластера по формулам (2.1) и (2.2).

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

В алгоритме на рисунке 2.6 есть критический момент, требующий относительно больших вычислительных ресурсов. Для вычисления расстояния L = ( xk xi ) 2 + ( y k yi ) 2 + ( z k zi ) 2 между двумя позициями и коррекции центра кластера необходимо использовать формулы перевода эллипсоидных координат в декартовы [92, С. 44]:

где a и b являются параметрами используемого эллипсоида (рис.2.3):

a – большая полуось, b – малая полуось.

Формулы (2.3), (2.4) и (2.5) требуют использования чисел с плавающей запятой двойной точности, что является крайне сложной задачей для большинства недорогих микроконтроллеров.

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

здесь ( ) и ( ) используются вместо параметров эллипсоида (рис. 2.2). При этом формула (2.2) примет вид:

где в качестве f ( ) для широты берется ( ), для долготы ( ), а для высоты позиционирования берется AH, а для высоты AV.

( ) const = 360° (2 R ) – функция, вычисляющая соотношение градусов широты к одному метру расстояния на указанной в качестве параметра широте. Под величиной R подразумевается средний радиус Земли.

Вычислено, что обратные значения данной функции меняются на протяжении от 0 до 90 градусов широты незначительно, всего на 31 см./сек.Ш.

(30,715…31.025 м./сек.Ш.), поэтому ( ) допустимо приравнивать константе, равной 1/30.87 = 0,03239391 сек.Ш./м. или 8,9983 10 -6 °Ш./м. на любой широте.

Графически смысл единицы измерения (°Ш./м.) можно увидеть на рисунке 2. ( ) 360° (2 R cos( ) ) – вычисляет соотношение градусов долготы к одному метру расстояния на указанной широте. На рисунке 2.8 значения ( ) можно представить как, очевидно, что оно значительно меняется ближе к высоким широтам. Значение данной функции в ± 90° широты переходит в бесконечность, таким образом, данный фильтр нельзя считать эффективным на полюсах, там применение проектируемого устройства маловероятно, но допустимо, если для точек полюсов предусмотреть вместо бесконечности некоторое максимальное значение. Непосредственное последующей линейной интерполяцией для промежуточных значений широты.

В качестве минимального изменения была взята 1 секунда долготы, шаг j по широте равен 1°, в качестве результата в таблицу записаны значения 1 / l j.

При расчётах значений ( ) и ( ), h была принята равной 100 м., если говорить о точности, то l из расчёта на 1 секунду широты при изменении высоты от 0 до 1000 метров над уровнем эллипсоида изменяется всего на 5 мм, поэтому высотой можно пренебречь для расчёта этих значений.

Графический смысл алгоритма фильтрации избыточных данных в упрощенном подходе примет вид представленный на рисунке 2.9.

Относительно масштабов, фигуру со сторонами 2 ( ) AH на 2 ( ) AH можно обозначить как прямоугольник, а если задействовать третье измерение ( 2 AV ) то, как параллелепипед. Таким образом, критерием кластеризации является пересечение данных фигур.

Рис.2.9. Иллюстрация к упрощенному варианту При упрощенных расчетах кластеризации будет теряться некоторое количество потенциально полезной информации о позиции, если за идеал принять фильтрацию с пересчетом системы координат, графически представленную на рисунке 2.5. Для двухмерного режима потери можно приблизительно оценить так: 4 R 2 / R 2 1,27, т.е. на 127 отсеянных выборок придется примерно 27 потенциально полезных выборок. Для трехмерного режима: 6 R 3 R 3 1.91, аналогично на 191 отсеянную выборку придется около 91-й потенциально полезной выборки. Подобные потери вполне допустимы, если принять во внимание, что избыточные выборки используются для уточнения координат центра кластера. Взамен получается значительное сокращение вычислений, и возможность использования вычислений с фиксированной запятой, таким образом, алгоритм фильтрации становится легко реализуемым и требует минимум вычислительных ресурсов.

разработанного фильтра.

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

Рис.2.10. Процесс сжатия данных измерений в датчике информация, данные в которой согласно таблице 1.1 делятся на три типа:

события, количественные и качественные значения. Сжатию не подвергаются преобразовать в форму событий, то есть передавать лишь в случае их изменений. Остальные данные можно разделить на два класса: цифровые сигналы и битовые поля. Битовые поля образуются путем объединения в группы качественных значений с одинаковой дискретизацией по времени. В задачу фильтра входит устранение избыточных данных, не дающих никакой новой информации о наблюдаемом объекте, и подача на вход преобразователя только полезной и пригодной для дальнейшего сжатия измерительной информации. Для цифровых сигналов, таких как счетчики и время, фильтрация не нужна, но те значения, которые содержат в себе шум, связанный с погрешностью измерений, необходимо фильтровать, таким образом, чтобы отправлять новые данные только в случае, когда изменение значения превысит погрешность его измерения. Фильтрация данных о позиции осуществляется медом, описанным в разделе 2.1.

В некоторых случаях применяется компандирование сигналов [46] для обеспечения равномерной полезности дискретных уровней количественных преобразованию:

Для битовых полей фильтрация не выполняется.

2.2.1. Адаптивное разностное кодирование сигналов и битовых полей Для преобразования цифровых измерительных сигналов к виду удобному для дальнейшего кодирования в более компактное представление была разработана разновидность дельта-кода, которая обладает адаптивностью.

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

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

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

Рис.2.12. Пример разностного кодирования сигналов с максимальной Битовые поля предлагается преобразовывать в разностную форму посредством операции сложения по модулю два. Адаптивность достигается перестановкой бит в поле на основе таблицы частот, в которой ведется учет изменений на противоположное значение по каждому биту поля, она же является ключом к восстановлению кодированной последовательности данных с позиции отличной от начала. В таблице 2.1 приведен пример кодирования текста предложенным методом, условный выигрыш в данном примере составил 26 бит при 90 битах оригинальных данных, расчеты выполнялись путем исключения последовательности нулей в начале битовых полей и результатов перестановки.

Таблица 2.1. Адаптивное разностное кодирование полей на примере текста П 11001111 11001111 1,1,0,0,1,1,1,1 7,6,5,4,3,2,1,0 р 11110000 00111111 1,1,1,1,2,2,2,2 5,4,7,6,3,2,1,0 и 11101000 00011000 1,1,1,2,3,2,2,2 7,6,5,4,3,2,1,0 в 11100010 00001010 1,1,1,2,4,2,3,2 7,6,5,4,2,1,0,3 е 11100101 00000111 1,1,1,2,4,3,4,3 7,6,5,4,2,0,1,3 т 11110010 00010111 1,1,1,3,4,4,5,4 7,6,5,4,2,0,3,1, 00101100 11011110 2,2,1,4,5,5,6,4 7,6,5,4,3,2,0,1 м 11101100 11001100 3,3,1,4,7,7,6,4 5,7,6,4,0,3,2,1 и 11101000 00000100 3,3,1,4,7,8,6,4 5,7,6,4,0,1,3,2 р 11110000 00011000 3,3,1,5,8,8,6,4 5,7,6,4,0,1,3,2 ! 00100001 11010001 4,4,1,6,8,8,6,5 5,7,6,0,4,1,3,2 Если значение какого-либо из счетчиков таблицы частот выходит за допустимые пределы, она подвергается коррекции путем сдвига всех ее элементов на один разряд вправо. При этом скорость адаптации можно регулировать максимально допустимым значением счетчика, чем меньше данный параметр, тем быстрее происходит адаптация к потоку данных.

2.2.2. Префиксный код с регулируемым приращением Для компактного хранения или передачи полученных разностей необходимо использовать префиксные коды переменной длины [40]. Среди таких кодов наиболее известны коды Элиаса и коды Голомба, которые являются общим случаем Унарного кода и кодов Райса. Коды Голомба в данном случае малопригодны, поскольку имеют быстрый линейный рост, а диапазон значений разностей заранее не известен. Поэтому в подобных случаях наиболее выгодно применять коды Элиаса, рост которых близок к логарифмическому, но оперировать битовыми потоками, как правило, не удобно, а при выравнивании данных будут возникать ощутимые потери. На основании изложенного было выдвинуто два главных требования к префиксному коду шифратора:

1) близкий к логарифмическому характер роста;

2) регулируемый шаг роста размера кода.

Для выполнения поставленных требований было разработано семейство префиксных кодов формата p q(s ). Данный метод префиксного кодирования предусматривает: префикс переменной длины, кодирующий номер интервала чисел, с шагом приращения p ; индекс в заданном интервале с шагом приращения q ; модификатор s начального интервала.

представления малых значений, при параметре s меньшем нуля, или удлинения начального интервала, при параметре s большем нуля, но меньшем q, с целью компенсировать всплески значений разностного кода в процессе адаптации к характеру поступающей телеметрической информации. При s меньше нуля, используется дополнительный интервал, кодируемый числом из ( s ) бит, диапазон значений соответствующий интервалу будет [0; L ), где L = 2 s 1.

Все числа выходящие за рамки диапазона дополняются префиксом из ( s ) единиц.

Параметр удлинения начального интервала h определяется выражением:

Длина начального интервала определяется формулой:

отсюда диапазон значений [0; L0 ), которые линейно кодируются p + q битами.

Оставшиеся интервалы в рамках первого шага префикса имеют длину:

где номер интервала i меняется от 1 до 2 p 2. При этом код индекса I в данных интервалах не эквивалентен его линейному значению I и вычисляется по формуле:

Длины дальнейших интервалов i = 2 p 1... определяются формулой:

Индекс кодируется линейно, а старшая часть длиной h бит заполняется единицами и присоединяется к первой части префикса.

При декодировании номер интервала определяется формулой:

где Q0 – начальный элемент индекса, а Pj элементы префикса кода длиной по p бит. Если Pj, содержит значение 2 p 1, это говорит о том, что впереди есть еще один элемент Pj +1, здесь j может меняться от одного до бесконечности.

Количество разрядов N отведенных под значение индекса заданного интервала вычисляется по формуле:

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

при этом кодируемые в интервале числа будут ограничены значениями от V (i 1) + 1 до V (i ) включительно, при этом принять V ( 1) = 1.

В приложении 4 приводятся примеры построения некоторых префиксных кодов из предложенного PQS-семейства и упомянутых кодов Голомба и Омегакода Элиаса. На рисунке 2.13 показан характер роста размеров префиксных кодов относительно размера кодируемого числа, которому соответствует нижний график. Жирной линией выделен график демонстрирующий рост PQSкода формата 1x3(0), чуть выше его огибает график для Омега-кода Элиаса.

График с линейным ростом соответствует коду Голомба с m=511.

Если посмотреть на графики разностей последовательности данных (рис.

2.11 и 2.121), то можно заметить, что абсолютное значение разности достаточно резко меняется в местах адаптации. Данную особенность можно использовать при префиксном кодировании для повышения качества сжатия, путем использования дополнительного интервала PQS-кода для значений, которые шифруются при стабилизировавшемся уровне разности. Заштрихованная область на рисунке 2.14 демонстрирует выигрыш выделенного толстой линией PQS-кода формата 1x4(2) относительно пересекающегося с ним PQS-кода формата 1x4(0) в начальном диапазоне, на последующих диапазонах происходит существенное отставание.

Рис. 2.13. Пример использования дополнительного интервала PQ-кода Предложенный метод префиксного кодирования встраивается не только в бинарные, но и в текстовые протоколы путем использования подмножества алфавита, размер которого равен степени двойки. Например, для обычной шестнадцатеричной строки можно воспользоваться PQS-кодом формата 1x3(0,1,2) или 4х4(0,1,2,3).

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

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

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

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

Аффинное или фрактальное [8; 33] сжатие информации реализуется выполняется путем итерации аффинных преобразований до достижения неподвижной точки.

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

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

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

здесь, n – размер последовательности, а h – коэффициент искривления.

Фактически, первый компонент суммы в формуле (2.7) является разностью прямых, которые наилучшим образом аппроксимируют рассматриваемую последовательность и подобие.

Для достижения неподвижной точки необходимо соблюсти два условия.

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

Вычисление коэффициентов и поправки аффинного преобразования реализуется методом наименьших квадратов [16], который дает следующие системы линейных уравнений для формулы (2.6):

и для формулы (2.7) с использованием линейной аппроксимации:

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

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

Оценка потерь информации при аффинном кодировании производится через сравнение оригинальной последовательности данных и полученной по формуле (2.6) или (2.7) из рассматриваемого подобия.

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

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

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

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

Здесь, можно предложить три тактики поиска подобий в порядке возрастания вычислительных затрат: поиск до первого пригодного подобия, до первого пригодного классического подобия и полный перебор с выбором наилучшего подобия. Таким образом, аффинный код для последовательности будет состоять из значений l, s, k,, а также h при l > 2.

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

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

4. Для ограничения числа не нужных проверок и вычислений по формулам (2.8) и (2.9), в качестве быстрого теста на соответствие введена проверка энергии сигнала и нормированных энергий гармоник ряда Фурье оригинальной последовательности и подобия с вычетом аппроксимирующей прямой. Энергия сигнала вычисляется по формуле:

где Li определяется формулой:

параметры a и b определяются методом наименьших квадратов:

Нормированная энергия заданной гармоники определяется формулой:

здесь j – номер гармоники. Энергии для выборки подобий рассчитываются аналогично и заранее для всех допустимых по количеству экстремумов подобий. Порог расхождения энергий оригинальной последовательности и подобия рассчитывается исходя из допустимых потерь:

где f ( Li ) дополненный погрешностью сигнал с вычетом аппроксимирующей прямой, например, при заданном максимальном отклонении d от оригинальной последовательности f ( Li ) примет вид:

Условием для дальнейшей проверки подобия на совпадение с оригинальной последовательностью будет:

где E и E j – энергии, рассчитанные для подобия. Опытным путем было установлено, что достаточно использования энергии первых трех-четырех гармоник, это позволяет сократить время поиска подобий на порядок.

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

Полученные аффинные параметры l, s, k,, и h необходимо привести к виду удобному для сжатия различными энтропийными методами [37], которые позволяют получить дополнительный выигрыш в процессе архивации.

Параметр длины последовательности l преобразуется следующим образом:

l = 0 – резервируется для обозначения начала блока разностного кода, в котором сначала указывается количество разностей c, а затем размещается дельта-код в указанном объеме;

l = ± (l 1) – кодирует длину кода в виде каком виде используется подобие: развернутом или нормальном порядке следования элементов. Далее, коэффициент искривления h преобразуется к целому числу с фиксированной точкой, число разрядов за которой равно l + 1.

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

где m = 2 – длина рассматриваемого подобия. Амплитудная поправка округляется до ближайшего целого значения. Затем l,, и h преобразуются в беззнаковую форму посредством следующей функции:

где под значением v понимается один из параметров l,, или h.

Коэффициент масштабирования k в большинстве случаев бывает ближе к своему максимуму k max, чем к нулю, поэтому преобразование к беззнаковой форме имеет вид:

Смещение на последовательность подобия s в процессе сжатия реализуется как инкрементная переменная, которая уже считается закодированной и помещается в архив без изменений, но при доступе к подобию она декодируется в два этапа:

где t – смещение на кодируемую или декодируемую последовательность, второй этап выполняет поправку смещения в кольце:

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

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

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

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

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

Затем, выполняется множество проходов, в которых выполняются аффинные преобразования по функциям (2.6) и (2.7), параметры которых записаны в аффинных кодах, до тех пор, пока не будет достигнута неподвижная точка.

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

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

Исходную последовательность данных можно представить в виде массива D[N ], где N – количество элементов сжимаемой выборки. При сканировании массива D[N ] формируется расширенная статистика, которая представлена четырьмя таблицами:

A[n ] – символы алфавита, упорядоченные по возрастанию;

F [n ] – частоты встреч символов алфавита в рассматриваемых данных;

M [n ] – частоты повторов символов алфавита;

K [n ][ n ] – частоты корней и префиксов;

где, n – размер алфавита. В последнем массиве под понятием корня подразумевается пара символов исходной последовательности D[i ] и D[i + 1], такая что D[i ] < D[i + 1], в противном случае D[i ] воспринимается в качестве префикса, а ячейка K [T ( D[i ])][T ( D[i + 1])] содержит число подобных событий, где функция T (x ) вычисляет порядковый номер рассматриваемого символа в алфавите. Таким образом, верхняя правая половина матрицы содержит статистику корней, а нижняя левая, включая диагональ, содержит статистику префиксов. На рисунке 2.15 приведен пример разбиения последовательности на слова, при этом содержимое таблиц статистики будет иметь вид:

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

1) простое комбинаторное кодирование на основе таблицы частот F [n ] ;

2) серийное комбинаторное кодирование с учетом повторов символов на основе таблицы повторов M [n ] и ее разности с таблицей частот F [n ] M [n ] ;

3) словарное комбинаторное кодирование с учетом соседства символов на основе таблицы корней и префиксов K [n ][ n ].

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

Номер сочетания определяется согласно алгоритму изображенному на рисунке 2.16. Есть некоторая булева последовательность L[t + f ], состоящая из t последовательности ее инициализированный нулем номер сочетания I в случае истинного значения будет увеличиваться на количество комбинаций, которые могли бы быть составлены из остатка последовательности, если бы текущий элемент был заменен ложным из оставшихся элементов.

Рис.2.16. Алгоритм вычисления номера сочетания Процесс восстановления булевой последовательности по номеру сочетания I и указанной статистики истинных t и ложных f значений представлен на рисунке 2.17. Здесь необходимо отметить, что факториал нуля равен единице.

Рис. 2.17. Алгоритм восстановления булевой последовательности Простое комбинаторное кодирование заключается в вычислении кода ограниченного мультиномиальным коэффициентом:

Процесс простого комбинаторного кодирования при этом можно записать в виде выражения:

последовательности с F [i ] истинных значений, которыми считаются все значения равные A[i ], с ложных значений, на последовательности данных Di, из которой исключены уже рассмотренные символы алфавита.

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

Серийный комбинаторный код тесно связан с другим алгоритмом сжатия – кодированием длин серий. Интересный факт: каждый элемент, кодирующий длину серии, является частным случаем простого комбинаторного кода нулевого размера. Оригинальная последовательность D[N ] предварительно должна быть преобразована в разделенный на два массива код длин серий, где D [N ] содержит символы, а S [N ] длины серий. Ограничение серийного комбинаторного кода определяется формулой:

где C вычисляется по формуле:

здесь и далее C – биномиальный коэффициент. Таблица FM [n ] является разностью таблиц частот и повторов комбинаторного кодирования определяется выражением:

последовательности с M [i ] истинных значений и F [i ] M [i ] 1 ложных значений из элементов кода длин серий, чей код символа равен A[i ]. Булева последовательность формируется при сканировании кодов длин серий, если D [ j ] эквивалентен A[i ], то записывается S [ j ] истинных значений и одно ложное, кроме самого последнего. Процесс декодирования строится обратно процессу кодирования, при этом требуются алфавит, таблица повторов и разность таблицы частот и повторов.

Словарное комбинаторное кодирование использует разбиение исходной последовательности данных на части (слова) W [N ] состоящие из корня и префиксов (рис. 2.15). Исключением является последнее слово, которое может быть пустым, как в проиллюстрированном примере, или состоять из одних лишь префиксов. Каждое слово рассматривается как стек с вершиной при последнем символе. При этом код будет ограничен значением:

где qi и q j определяются выражением:

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

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

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

Минимальное число бит необходимое для хранения комбинаторного кода определяется выражением B =] log 2 (V 1)[, при значении V равном единице, размер кода берется равным нулю. В программной реализации, вычисление логарифма заменяется сканированием числа V до первой значащей двоичной единицы, подобно ассемблерной команде BSR [97].

В отличие от арифметического сжатия и метода Хаффмана [36], для которых событием является очередной символ последовательности данных с сжатия событием является вся последовательность данных со всеми зависимостями, отраженными статистикой. Это позволяет повысить эффективность сжатия относительно энтропии нулевого порядка при сохранении универсальности в отношении потока данных. Например, для простого комбинаторного кодирования суммарная условная энтропия N порядка H SN = log 2 (V N ), а затраты на хранение комбинаторного кода можно записать, как B = ]H SN [.

2.4. Прямая сегментация геосферы на основе пучков плоскостей Разработанный метод прямой сегментации геосферы, обеспечивает хорошее качество сегментной сетки при сколь угодно большой глубине (уровне) сегментации. Чтобы метод сегментации был прямым, была введена сегментная система координат, которая гарантирует однозначный переход к сферической системе координат и обратно. Данная система координат использует 20 базовых треугольников основанных на икосаэдре [5] (рис.2.18), образующих 10 базовых сегментов, каждый из которых является локальной системой координат с осями x и y. При сегментации по данным осям пограничные вершины соседних базовых сегментов полностью совпадают, тем самым гарантируется бесшовная визуализация. Важно отметить, что допустимо интерпретировать входные и выходные сферические координаты как эллипсоидные, но со стороны сегментной системы координат, в ходе преобразований, они воспринимаются именно как сферические.

Рис. 2.18. Развертка икосаэдра применительно к географической системе Расчет вершин икосаэдра (опорных точек) Vi (где i = 0...11 ) производится по формулам:

1. Широты опорных точек:

где - угол между любыми соседними вершинами и вычисляется по формуле:

2. Долготы опорных точек:

осуществляется в два этапа. На первом, определяется номер базового сегмента, в котором находится искомая точка P. Для этого необходимо определить, между какими опорными точками по долготе находится заданная точка:

где k вычисляется по формуле:

затем, с помощью подстановки декартовых координат P в уравнение плоскости V( k +1) mod10+1Vk +1O (где O - начало координат), в зависимости от знака результата, определяется, к какому из двух возможных, верхнему (четному) или нижнему (нечетному) сегменту принадлежит заданная точка.

На втором этапе вычисляются значения локальных координат x и y в выбранном сегменте. Все базовые сегменты состоят из пары сферических треугольников ABC и ACD (рис.2.19), чтобы минимизировать искажения, для каждого треугольника используется своя координатная полу-сеть, где средняя ось xy служит как недостающая ось для обоих полусегментов. Таким образом, две координатных полу-сети логически объединены в одну с осями x и y.

Рис.2.19. Локальная система координат в базовом сегменте Далее, проверяется положение точки P относительно плоскости ACO, тем самым определяется полусегмент, которому принадлежит точка. Допустим, P принадлежит ABC (рис.2.20), для нахождения локальных координат нужно задать направляющие вектора N x и N y, которые, по сути, являются осями пучков плоскостей, формирующих локальную координатную сетку. Они вычисляются следующим образом:

затем, определяются вектор X как результат пересечения трех плоскостей:

и вектор Y :

Значения нормированных локальных координат будут:

Аналогично во втором полусегменте:

В результате получаем координаты точки в виде P = ( j, x, y ), где j - номер сегмента.

Рис.2.20. Преобразование координат в базовом полусегменте При обратном преобразовании координат из сегментных в сферические, полусегмент, которому принадлежит точка, определяется через сравнение x и вычисляются точки X и Y на дуге AC. Это можно сделать различными способами, но наиболее наглядным будет поворот вектора A на угол = t вокруг оси вращения R = ( x, y, z ) = A C, где t принимает значение x для X и y для Y. Матрица поворота M ( R, ) имеет вид:

где m1, m2 и m3 рассчитываются по формулам:

Таким образом, Далее вычисляется точка P, как точка пересечения трех плоскостей, если искомая точка принадлежит треугольнику ABC :

если ACD :

затем, полученное значение P нормируется или преобразуется в сферические (эллипсоидные) координаты.