Об одном алгоритме сжатия случайных сигналов (с потерями)

Аннотация

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

К сожалению, мне не известны способы, которые могли бы по реализации случайной величины восстановить моделирующий её алгоритм. Ситуацию можно представить себе следующим образом. Допустим, у нас есть бильярдный стол с одним шаром на нём, мы ударяем кием по шару и делаем выборки положения шара через равные промежутки времени. Полагаем, что трения нет, а удары о стенки стола абсолютно упругие. Так мы получаем реализацию случайной величины по алгоритму похожему на конгруэнтный. Если мы знаем параметры стола, время, через которое производились выборки, положение и вектор скорости шара в какой-либо момент времени, то мы можем восстановить положение шара в моменты времени и до и после выбранного. Но если мы знаем только относительное положение шара на плоскости и то, что выборки производились через равные промежутки времени – нам остаётся только гадать о том, как перемещался шар и куда он будет перемещаться. Гадать можно неопределённо долго. Имея же реализацию ВЧ сигнала мы знаем относительное положение шара в каждый из выборочных моментов времени, но надо построить такой стол и выбрать промежуток времени так, чтобы взяв какую-либо выборку (отсчёт) вначале и «ударив» по ней кием она принимала все последующие положения в ВЧ сигнале. Интуитивно понятно, что в общем случае подобрать такой стол для всей реализации вряд ли возможно.

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

Приведённый здесь алгоритм относится к классу редких на сегодня (12 окт 2004 г.) алгоритмов для сжатия ВЧ сигналов (изображений), в отличие от алгоритмов, основанных на преобразовании Фурье, косинусном преобразовании, вейвлет преобразовании, ориентированных на НЧ сигналы (изображения). Для последних можно сказать, что если сигнал гладкий, то степень сжатия будет очень хорошей. Для ВЧ алгоритмов наоборот – чем более сигнал похож на случайную величину, тем лучше будет сжатие и/или процесс сжатия. Однако, я думаю, что природу не обманешь и если сигнал будет «тождественен» независимой случайной величине, то мой алгоритм будет давать плохое, либо вообще никакого приближения к исходному сигналу. К счастью, такая ситуация очень маловероятна как вы увидите из экспериментов (либо её можно сделать маловероятной).

В качестве примера я взял столбец с номером colnum = 160 (считая от нуля) из тестового изображения bird.bmp. Далее план действий для этого одномерного случая следующий:

1. Декорреляция. Формируем две случайные последовательности ξ1 и ξ2 с равномерным распределением, которые будут участвовать в перемежении сигнала (перестановкой отсчётов). Как я упоминал выше, сигнал должен быть похож на случайную величину. Желательно, чтобы длины этих последовательностей были в несколько раз больше длины сигнала N (это нужно для качественного перемешивания). Последовательности должны быть повторяемыми, т. е. с заданным алгоритмом формирования и его параметрами (они будут использованы при восстановлении сигнала).

2. Перемешиваем отсчёты входного сигнала. Используется следующий алгоритм. Переставляем два элемента из сигнала, индекс первого берётся из значения случайной величины nξ1, второго – из значения случайной величины nξ2. nξ1 и nξ2 получаются из ξ1 и ξ2 путём их соответствующего масштабирования и квантования.

3. Если возможно, опознаём закон распределения значений сигнала и запоминаем его параметры. Формируем ещё одну случайную величину ξ3 с равномерным законом распределения. Длина реализации должна быть значительно больше длины исходного сигнала N. Пропускаем эту равномерно распределённую случайную величину через формирующий фильтр. Параметры фильтра вычисляются в соответствии с законом распределения значений отсчётов сигнала. В простейшем случае ξ3 можно просто привести к масштабу изменений значений сигнала (как это сделано в примере ниже).

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

5. На выходе процедуры сохраняем:

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

Если этой информации по объёму будет меньше, чем длина исходного сигнала, то произойдет сжатие (с потерями).

Обратная последовательность действий проще:

1. Формируем три равномерно распределённые случайные величины по алгоритмам, используемым при сжатии.
2. Третью последовательность пропускаем через формирующий фильтр.
3. Зная длину и номера интервалов, восстанавливаем декоррелированный исходный сигнал.
4. Коррелируем его, т.е. применяем обратное перемешивание (деперемежение).

По времени алгоритм несимметричен.

Примечание

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

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

Стандартное тестовое изображение птицы bird.bmp занимает 66614 байт. «Сжатое» двумерным вариантом алгоритма текстовое представление данных в rar архиве занимает 10138 байт. Качество можно можно оценить и на глаз. Смысл в том, что я сжимал не гладкий сигнал, а фото, которое превратил в «шум», чтобы алгоритм мог найти в нём похожие детали. Реально же, если разделить изображение на НЧ и ВЧ части, то обычными гладкими алгоритмами можно сжимать НЧ часть, а ВЧ часть представленным алгоритмом.

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

Ссылки

1. Алгоритм сжатия с потерями (pdf, много картинок).
2. Архив с документами и расчётами (Mathcad).

Автор: ViacheslavMezentsev

Источник