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

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

В подобных случаях применяют методы сжатия растровых изображений без потерь (lossless) или с ограниченными потерями (near lossless), например JPEG-LS (LOCO-I). Но несмотря на высокую сложность реализации, они имеют низкую эффективность при обработке мелких деталей или высокочастотных составляющих спектра.

Постановка задачи

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

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

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

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

Рис. 1. Тестовое изображение Lena

Для иллюстрации особенностей срезов изображения на рис. 2а и рис. 2б приведены графики корреляционных характеристик между РДИ и внутренних, в зависимости от разряда для тестового изображения Lena (см. рис. 1).

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

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

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

М-последовательность представляет собой псевдослучайную последовательность (ПСП), содержащую в себе полный непоследовательный числовой ряд заданной разрядности, за исключением 0.

Коэффициент

а)

б)

Рис. 2. Зависимость коэффициента корреляции в изображении Lena между соседними РДИ (а) и между строками изображения в РДИ (б)

Она строится с помощью h ( x ) – первообразующего примитивного неприводимого полинома n -ой степени:

n h (x) = S hi xi,             (1)

i =0

где h(0) = h(n) = 1; h i = {0, 1} при 0 <  i <  n ; x - коэффициент поля Галуа Gf2.

Значения М-последовательности задаются следующим образом:

n -1

a n + j =® S °. + j h i , j = 0,1’2-, L — 1 , (2) i = 0

где L - длина последовательности; ф - знак суммирования по модулю два.

При этом начальное значение регистра не должно быть нулевой комбинацией [2].

Описание алгоритма

Для проведения аппроксимации предлагается простой алгоритм. Он реализуется следующим образом: РДИ цифрового полутонового изображения разбивается на квадратные участки размерности 8×8 бит. Затем для каждого блока генерируется 16 возможных М-последо-вательностей со значением первообразующего регистра в виде первой значащей (ненулевой)

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

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

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

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

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

Описанная методика была реализована программно. Аппроксимированные значения записывались вместо данных РДИ. Номер последовательности записывался в значения 8 разряда блока по вертикали.

Результаты работы алгоритма

Результаты работы алгоритма приведены на рис. 3-4. Визуально изменения можно оценить по рис. 3, на котором приведено младшее РДИ изображения Lena до (см. рис. 3а) и после (см. рис. 3б) обработки. На рис. 3 б видно существенное увеличение пространственного подобия фрагментов сечения. При обработке данных получен выигрыш по степени сжатия за счет уменьшения разрядности. Он составляет значения 1,2-1,5 для каждого сечения при условии использования алгоритма rLE при передаче. При кодировании младшего РДИ алгоритмом rLE без обработки по алгоритму выигрыш по объему передаваемых данных отсутствует.

а)

б)

Рис. 3. Исходное (а) и обработанное по описанному алгоритму (б) младшее РДИ тестового изображения Lena размером 256×256 пикселей

Рис. 4. Значения межстрочных коэффициентов корреляции в РДИ тестовых изображений до (график №1) и после (график №2) обработки по описанному алгоритму

Полученные результаты были проверены на младших битовых сечениях десяти тестовых изображений. Результаты приведены на графиках на рис. 4. График №1 – значения коэффициента корреляции между строками РДИ до обработки, график №2 – после. Наблюдается его повышение от значений 0,0010,005 до 0,2-0,3, то есть возрастание достигает 300 раз.

Выводы

Полученные результаты показывают эффективность аппроксимации ВЧ составляющих изображения при помощи фрагментов М-последовательностей. Достигнуто уменьшение разрядности хранимых данных. Коэффициент сжатия при передаче составляет 1 ,2-1 ,5 для каждого младшего РДИ при использовании rLE кодирования при передаче.

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

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