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

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

  • 1) непосредственное преобразование элементов данных с помощью динамики клеточного автомата;
  • 2) использование клеточного автомата для подготовки элементов данных к последующему статистическому сжатию;
  • 3) построение декоррелирующего преобразования на основе динамики клеточного автомата.

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

Рассмотрим данный подход в контексте сжатия цифровых изображений. Как и ранее, представим изображение в виде дискретной функции двух переменных f(x, у) с областью определения Е = {0,..., гп— 1} х {0,..., п— 1} и областью значений D {0,1,..., L — 1}. Разобьем изображение на некоторое количество непереескающих- ся блоков размера m х nj, тогда множество Е окажется разбито на гпп/{т,хп) непересекающихся подмножеств Е = У Е^-, к =

к-1

Введем отображение

если V(xi,yj) е Ejt, i = l,mb j = l,ni.

Также введем понятие глобальной функции перехода клеточного автомата т: Z" —> А, представляющей собой результат одновременного применения локальной функции перехода а ко веем клеткам решетки, и с ее помощью опишем переход клеточного автомата из состояния с1 в состояние ct+a как ct+s = тнс1. Тогда отображением, служащим непосредственно для сжатия данных, будет Т: s при

с'1 = т^с®, в результате чего матрица значений функции f(x, у) будет заменена матрицей меньшего размера a {sij)i 1 j-i > sij € Z-, что соответствует сжатию в mn/(m {) раз при условии, что хранение элементов матрицы S не потребует большего объема памяти, чем хранение элементов исходной функции f(x,y). Кроме того, преобразованные элементы данных могут быть подвергнуты дальнейшему сжатию с помощью статистического кодирования.

Однако возникает ряд сложностей связанных с разработкой методов сжатия данных, реализующих описанный подход:

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

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

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

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

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

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

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ ОРИГИНАЛ   След >