Книги по разным темам Pages:     | 1 | 2 | Электронный журнал ИССЛЕДОВАНО В РОССИИ 627 Применение вейвлет анализа для компрессии видеоинформации, формируемой прибором астроориентации.

Пузиков Д. Ю. (dpuz@chat.ru) Московский Физико-Технический Институт НПО Лептон Введение.

Совершенствование приборов ориентации для космических аппаратов в настоящее время является одним из ключевых моментов развития космической техники. Успехи промышленности в совершенствовании электронной элементной базы позволяют применять новые методы определения положения и ориентации космического аппарата в пространстве. Один из таких методов заключается в определении ориентации аппарата по направлению на звёзды [1], [2].

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

Для регистрации изображения участка звёздного неба в современных приборах используется ПЗС матрица.

В процессе работы системы астроориентации, как и любой другой сложной системы, всегда возможны отклонения от нормального функционирования. Причин этих отклонений может быть несколько: появление в поле зрения прибора большого количества ложных объектов, расстройка оптической системы, всевозможные повреждения и т. д. Чтобы иметь возможность выявить и по возможности устранить источник подобного рода сбоев необходимо организовать передачу наблюдаемого фрагмента звёздного неба на Землю. Кроме того, так как при работе системы астроориентации обработка каждого кадра происходит с учётом предыдущих и последующих кадров, есть необходимость в передаче целых непрерывных серий таких кадров. Простые оценки показывают, что поток данных в этом случае без использования какой либо компрессии составляет примерно 50 Мбит/с. Очевидно, что организовать такой канал дорого, а в некоторых случаях просто невозможно [3], [4]. В связи с этим возникает вопрос о компрессии данных. Кроме того, компрессия должна производиться без потерь, чтобы наземные отладочные системы имели возможность полностью промоделировать процессы, происходящие в бортовой системе астроориентации и достоверно определить характер неисправности. Предполагаемая система компрессии должна обладать также относительной простотой реализации, так как речь идёт о бортовых системах, и применение громоздких и энергоёмких вычислительных элементов не представляется возможным.

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

Для того, чтобы разработать наиболее оптимальный метод компрессии, для начала необходимо изучить статистику изображений, которые необходимо архивировать. На рис. 1 приведён пример такого изображения. Из рисунка видно, что изображение сформировано двумя основными компонентами: фоновым шумом и Электронный журнал ИССЛЕДОВАНО В РОССИИ 628 звёздами. Следовательно, при выборе наиболее оптимального алгоритма компрессии должны быть учтены оба этих компонента.

Компрессия изображения звезды и вейвлет анализ.

Рассмотрим трёхмерное изображение звезды и спектр этого изображения (рис. 2, 3). На рис. 2 видно, что характерный диаметр изображения звезды на ПЗС матрице видео датчика составляет примерно 4-5 пикселей. Это говорит о том, что данная функция фактически является -функцией, и её спектр будет слабо спадающим вплоть до частоты Найквиста, что мы и видим на рис. 3.

В связи с этим можно сделать вывод о том, что обычное преобразование Фурье не приведёт к появлению большого количества нулевых или близких к нулю компонент. Следовательно, использование такого алгоритма компрессии как JPEG [5] не приведёт к желаемым результатам, так как в его основе лежит именно Фурье преобразование. Кроме того, компрессия с помощью JPEG всегда сопряжена с потерей некоторой незначительной информации, что недопустимо в нашем случае.

Рассмотрим методику компрессии, основанную на вейвлет анализе [6], [7]. Легче всего понять основную идею вейвлет анализа на примере одномерных массивов.

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

Особенности фильтров таковы, что один из них представляет собой фильтр нижних частот (ФНЧ), а другой - фильтр верхних частот (ФВЧ). Кроме того, частота среза обоих фильтров находится на уровне половины частоты Найквиста. Таким образом, из одного массива путём фильтрации можно получить два, причём один из них будет содержать высокочастотные (ВЧ) компоненты, а другой - низкочастотные (НЧ). В соответствии с теорией дискретизации [8], [9] в обоих из полученных массивов мы можем выбросить каждый второй элемент, и при этом исходный массив может быть полностью восстановлен по оставшимся цифровым отсчётам. В дальнейшем каждый из получившихся НЧ либо ВЧ массивов в свою очередь может быть подвергнут аналогичному анализу.

Аналогично выглядит анализ двумерных массивов [10]. Производится анализ каждой строки и столбца в соответствии с приведённой на рис. 4 схемой. И в итоге исходное изображение оказывается разбитым на четыре четверти. Одна содержит НЧ компоненты как по вертикали так и по горизонтали, одна ВЧ компоненты по вертикали и по горизонтали, одна ВЧ по горизонтали и НЧ по вертикали, и одна НЧ по горизонтали и ВЧ по вертикали. И, как и в случае одномерного массива, в дальнейшем любая из получившихся четвертей может быть разбита подобным же образом на четверти.

В настоящее время наиболее распространённым является метод октавного анализа, основанный на вейвлет анализе [11]. Этот метод основывается на том факте, что в среднем по статистике изображений их спектр спадает от низких частот к высоким почти экспоненциально. Поэтому если мы разобьём наш частотный диапазон на октавы как показано на рис. 5, то на каждый диапазон в среднем будет приходиться одинаковый по энергетике сигнал. В терминах вейвлет анализа октавное разбиение означает последовательное разбиение каждого НЧ блока полученного на предыдущем шаге анализа на ВЧ и НЧ компоненты. Пример трёхуровневого октавного вейвлет анализа изображения фрагмента звёздного неба представлен на рис. 6. Здесь на каждом очередном шаге низкочастотный блок размещается в левой верхней четверти, а затем в свою очередь подвергается анализу и разбиению на четверти. На приведённом примере видно, что наиболее значимые пиксели оказались в прямоугольнике в левом верхнем углу. Остальные же прямоугольники образованы пикселями, значение которых близко к Электронный журнал ИССЛЕДОВАНО В РОССИИ 629 нулевому. Фактически это означает, что реальное количество бит, которое необходимо для описания пикселя в этих ВЧ блоках меньше исходного (исходная картинка была получена в 12-ти битовой оцифровкой). Так как вейвлет анализ обратим, т. е. исходная картинка может быть полностью восстановлена по полученным блокам, так как суммарное количество пикселей в блоках равно исходному, а реальное количество бит на пиксель уменьшилось, мы получили систему архивации изображений без потерь.

Определим теперь количество уровней разбиения, которое оптимально для нашей задачи. Так как характерный диаметр изображения звезды равен ~5 пикселям, то после разбиения 3-го4-го уровня будет представлять собой фактически -функцию, и дальнейшее разбиение не будет приносить результатов. На рис. 7 показаны результаты после одно-, двух- трёх- и четырёхуровневого разбиения изображения звезды. Из рисунка видно, что если изначально для передачи изображения необходимо было примерно log2 2000 11 бит, то для архивации изображения подвергнутого вейвлет анализу достаточно порядка 9-ти бит для ВЧ блоков и 7-ми бит для НЧ блоков. Таким образом, мы получили возможность осуществлять компрессию изображения приблизительно на 30% без потерь. При этом следует заметить, что уровень шума во всех блоках одинаков и равен уровню шума в исходном изображении.

Кодирование Хаффмана.

Кодирование Хаффмана основано на некоторых статистических данных, набранных по большому количеству изображений [12], [13]. Допустим нас интересует компрессия 8-ми битных изображений. Для того чтобы компрессия была оптимальной необходимо набрать статистику по вероятности встретить тот или иной 8-ми битовый символ в изображении. Далее эти символы выстраиваются в порядке убывания вероятности, после чего строится перекодировочная таблица. Основная идея метода заключается в том, чтобы заменить наиболее часто встречающиеся 8-ми битные символы более короткими битовыми последовательностями, а для наиболее редко встречающихся символов зарезервировать длинные битовые последовательности.

На рис. 8 приведена гистограмма изображения звёздного неба. По гистограмме видно, что основным компонентом картинки является шум, имеющий характерное гауссовское распределение. Таким образом, задача компрессии фактически сводится к архивации гауссовского шума. Так как основным источником шума в данном случае является темновой ток фоточувствительных элементов ПЗС матрицы [14], то шумы пикселей никак не коррелированны между собой. Это вызвано тем, что фоточувствительные элементы представляют собой в достаточной степени независимые устройства. В связи с этим никакая дополнительная обработка (например спектральная) не может привести к существенным результатам [15]. Применение адаптированного кодирования Хаффмана непосредственно к рассматриваемой картинке привёло к сжатию приблизительно в 3,2 раза.

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

Комбинированное использование вейвлет анализа и кодирования Хаффмана.

Так как исходное изображение фрагмента звёздного неба является суммой изображений звёзд и шумов темнового тока фотоэлементов, то для оптимизации компрессии необходимо применять совокупность методов. Из теории цифровой обработки сигналов [8], [9] известно, что применение цифровой фильтрации аналогичной вейвлет анализу не может изменить структуру распределения и Электронный журнал ИССЛЕДОВАНО В РОССИИ 630 спектральные свойства гауссовского шума. В связи с этим, применение вейвлет анализа к изображению звёздного неба с одной стороны не приведёт к изменениям фонового шума, с другой стороны позволит произвести предварительную компрессию изображений звёзд. Далее, можно применить алгоритм, соптимизированный под исходный гауссовский шум. При этом его эффективность нисколько не ухудшится. В таблице 1 приведены результаты численных экспериментов по применению кодирования Хаффмана без использования вейвлет анализа и с использованием вейвлет анализа различных уровней.

Таблица 1.

Количество уровней анализа Коэффициент сжатия Без использования вейвлет анализа 3,09 раза 1 уровень 3,24 раза 2 уровня 3,93 раза 3 уровня 4,29 раза 4 уровня 4,42 раза 5 уровней 4,46 раза 6 уровней 4,47 раза Из таблицы видно, что предварительное применение вейвлет анализа перед кодированием Хаффмана приводит к увеличению эффективности сжатия в среднем на 50%. Кроме того, применение анализа выше четвёртого уровня не приводит к какому либо дальнейшему существенному улучшению результата, как и было показано в пункте Компрессия изображения звезды и вейвлет анализ.

Сравнение основных характеристик вейвлет компрессии и некоторых стандартных архиваторов.

В таблице 2 приведены данные по степени сжатия, обеспечиваемой различными стандартными архиваторами на примере 12-ти битного изображения звёздного неба, приведённого на рис. 1.

Таблица 2.

Название архиватора Коэффициент сжатия Вейвлет анализ (6 уровней) + Хаффман 4,Хаффман 3,ARC 3,ARJ 3,AIN 3,HA 3,ICE 2,LZH 3,RAR 3,ZIP 3,Из приведённой таблицы видно, что коэффициент сжатия всех приведённых стандартных программ компрессии находится на уровне обычного сжатия Хаффмана. В тоже время применение вейвлет анализа увеличивает эффективность компрессии в среднем на 50%.

Проведём теперь сравнение методов с точки зрения простоты их реализации на электронных компонентах. Все приведённые выше стандартные методы используют некоторые перекодировочные таблицы. Основной вычислительный ресурс при Электронный журнал ИССЛЕДОВАНО В РОССИИ 631 компрессии связан с построением таких таблиц. Используемые алгоритмы построения примерно одинаковы и, по сути, схожи с алгоритмом Хаффмана. Таким образом, с хорошей точностью объём вычислительных ресурсов необходимый для реализации всех этих алгоритмов примерно одинаков. Отсюда видно, что предлагаемый в работе метод компрессии основанный на вейвлет анализе более ресурсоемкий. Он отличается от приведённых методов необходимостью реализации вейвлет фильтрации. Оценим необходимый для этого ресурс.

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

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

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

Заключение.

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

Pages:     | 1 | 2 |    Книги по разным темам