Быстрые методы сжатия и распаковки в системах картографирования

УДК 621.372

В.Е. Золотовский, Е.В. Ляпунцова, Д.А. Беспалов, И.И. Головченко

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

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

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

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

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

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

В работе проводилась оценка основных параметров алгоритмов для каждого типа карт каждого типового размера и были получены следующие результаты: коэффициент сжатия: от 9 до 260 (дли худшего и лучшего вариантов рельефа), время распаковки: от 0.01 сек. до 0.7 сек (для размеров карт 250х250 точек и 1000х1000 точек соответственно).

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

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