Пусть в области задан сигнал , предположим, что в некоторой части заданной области сигнал удовлетворяет дифференциальному уравнению вида:
, (8)
где: - некоторый дифференциальный оператор, - правая часть. Краевые условия , заданные в области , таким образом, что: . Функцию , заданную в области , будем называть паттерном исходного сигнала . Зная уравнение (8) и паттерн сигнала , можно восстановить исходный сигнал в области . Таким образом, суть анализа дифференциальной структуры сигнала , состоит в выборе анализирующего уравнения (или уравнений) (8) и отыскании паттерна .
Определение краевых условий, путём анализа дифференциальной структуры заданного сигнала, является обратной задачей вычислительной математики.
Рассмотрим формирование паттерна на примере одномерного сигнала . Положим, что есть непрерывный прообраз дискретного образа некоторого сигнала , при этом описывается во всех областях анализирующим уравнением вида:
. (9)
Переходя к дискретному образу и полагая, что он задан на сетке , с равномерным шагом , где , для всех , можно записать уравнение (9) в виде:
. (10)
Выражая из (10) , получим:
. (11)
Вычислять паттерн будем по следующей схеме.
1. В начале положим, что во всей области все значения паттерна равны значениям сигнала т.е.: .
2. Далее выберем некоторое числовое значение -критерия, по которому будем производить исключение элементов из паттерна.
3. Следующим шагом будем вычислять для всех значений в области значения в соответствии с выражением, полученным с учётом (11):
, (12)
если условие истинно, то значение (для соответствующего ) исключается из паттерна, в противном случае, элемент остаётся в паттерне.
В результате выполнения указанной последовательности действий, мы получим паттерн сигнала .
На изображении (рис. 2) показан пример исходного сигнала (data) и паттерна (patt).
Рис. 2. Исходный сигнал (data) и паттерн (patt).
Очевидно, что паттерн (рис. 2) содержит значительно большее число равнозначных элементов, чем исходный сигнал, что позволяет его эффективнее сжать. В качестве признака исключения элемента из паттерна соответствующее значение возможно, например, приравнивать нулю. Такой принцип может вызвать неоднозначные («спорные») ситуации, например, если в исходном сигнале присутствуют нулевые значения, т.к. для восстановления сигнала необходимо точно знать принадлежит конкретный элемент паттерна краевым условиям или нет. Избежать такой ситуации поможет изменение «спорных» значений в исходном сигнале на некоторую определённую величину в зависимости от формата и допустимого диапазона цифрового сигнала. В качестве признака того, что элемент не является частью краевых условий, можно использовать величины выходящие за диапазон значений сигнала, но допустимые форматом данных.
Изменяя значение величины -критерия, можно управлять числом элементов вошедших в паттерн, от этого будет зависеть количество исключаемой информации и степень сжатия, соответственно. Для точного восстановления сигнала потребуется принять значение -критерия меньше шага квантования сигнала и в некоторых случаях сохранять, например, в виде битовой маски, данные позволяющие восстановить нулевые (или другие «спорные») значения в сигнале. На изображении (рис. 3) показан исходный сигнал (рис. 3, a.) и его поле паттернов (рис. 3, b.). Поле паттернов получено в результате объединения серии паттернов (для различных значений -критерия) в один массив. Чёрный цвет соответствует нулевым элементам паттерна, не являющимися краевыми условиями, прочие (оттенки серого) являются краевыми условиями. При увеличении значения -критерия происходит уменьшение числа элементов паттерна, принадлежащих множеству краевых условий.
Рис. 3. Сигнал (a.) и его поле паттернов (b.) в зависимости от -критерия.
Паттерн, содержащий относительно небольшое число элементов, являющихся краевыми условиями, позволяющими достаточно точно восстановить исходный сигнал, может быть получен только в случае хорошо подобранного уравнения для формирования паттерна, что в большинстве случаев возможно лишь для гладких функций. Следовательно, применение данного способа для сжатия шумоподобных сигналов (с высокой энтропией) неэффективно.
Изменяя порядок производных дифференциального оператора (8) и выбирая некоторые функции правой части , можно влиять на качество восстановления сигнала и число исключённых элементов из паттерна.
Восстановление исходного сигнала осуществляется с помощью решения выбранного ранее в качестве анализирующего дифференциального уравнения и краевых условий, содержащихся в паттерне. Численное решение можно осуществить, например, с помощью метода конечных разностей (МКР).
4. Сжатие многомерных цифровых сигналов с помощью анализа их дифференциальной структуры
Наиболее востребовано сжатие для данных называемых медиа-контент, к ним относятся статические и динамические (видео) изображения, аудио данные и др. В последнее время активно развиваются различные форматы видео данных [5,11], на базе которых синтезируются объёмные видео-сцены изображения высокой четкости и др. Цифровые изображения это один из видов сигналов, к которым можно эффективно применять сжатие за счёт анализа дифференциальной структуры. Многие изображения содержат достаточно значительные поля градиентных переходов (цвета, яркости); контрастные границы объектов в пространстве для статических и во времени и пространстве для динамических изображений. Границы объектов, содержащихся в изображениях, можно рассматривать как краевые условия, а поля достаточно плавных переходов, как области, удовлетворяющие выбранному анализирующему дифференциальному уравнению.
В качестве примера рассмотрим последовательно все этапы сжатия и восстановления статического изображения при помощи анализа дифференциальной структуры. Далее приведено краткое описание последовательности действий для сжатия и восстановления изображения.
Сжатие изображения:
- выбор дифференциального анализирующего уравнения (или системы) и цветового пространства для формирования паттерна;
- если необходимо преобразование цветового пространства;
- формирование паттерна (граничных условий);
- компрессия паттерна и дополнительной информации для восстановления сигнала.
Восстановление изображения:
- декомпрессия паттерна и дополнительной информации;
- восстановление изображения при помощи решения дифференциального уравнения (или системы) с учётом граничных условий;
- если необходимо, преобразование цветового пространства.
Подробно рассмотрим каждый из перечисленных выше пунктов. Первая задача это выбор анализирующего уравнения (или системы) для формирования паттерна и последующего восстановления двумерного сигнала изображения , заданного на плоскости . Остановимся на уравнении Лапласа, т.к. оно хорошо описывает плавные переходы (градиент цвета и яркости) в областях между граничными условиями:
. (13)
Выбрав шаблон дифференцирования для функции (рис. 4), переходим к дискретной форме . Считая что шаг сетки, с учётом индексации пикселей изображения, , уравнение (13) можно записать в виде:
. (14)
Рис. 4. Шаблон дифференцирования функции .
Выбор шаблона может оказать значительное влияние на конечный результат, в данном случае (рис. 4) выбран шаблон, показавший достаточно высокую эффективность в рамках рассматриваемого метода.
Выражая из (14) , получим:
. (15)
Следующая задача - выбор цветового пространства. Практические исследования показали, что наиболее компактный паттерн, следовательно, наиболее высокое сжатие, можно получить в цветовом пространстве RGB и YCbCr (вариация Y709CbCr), в зависимости от специфики изображения. Цветовое пространство RGB ассоциировано с особенностями восприятия зрительной системы человека и в нём хорошо передаётся специфика цветового градиента, сохраняются цвета исходного изображения. Пространство YCbCr может более эффективно обеспечить сохранение границ объектов изображения при некоторой потери цветовой информации.
Формирование паттерна является ключевым этапом сжатия изображения. От качества формирования паттерна будет зависеть возможное качество восстановленного сигнала и эффективность сжатия. Отметим некоторые особенности, замеченные при экспериментах с различными подходами к формированию паттерна. Наиболее высокое качество восстановленного сигнала удаётся получить при генерации паттерна, в котором каждому значащему элементу ставится в соответствие все компоненты цветового пространства. При этом конфигурация паттернов, с точки зрения положения элементов граничных условий, всех цветовых слоёв одинакова, а цвет элементов граничных условий остаётся в полном соответствии с исходным изображением. В результате того, что паттерны всех цветовых компонентов (слоёв) совпадают, возможно, сжимать последовательность серий, не значащих элементов для одного слоя и использовать его как шаблон для восстановления других, что позволяет существенно повысить фактор сжатия.
В паттерн обязательно включаются граничные пиксели изображения (два столбца - справа и слева, и две строки - сверху и снизу). Для исключения элементов из паттерна применяют -критерий на базе сравнения абсолютной величины разности значения вычисленного по (15) и фактического в точке , с некоторым заданным коэффициентом. Причём для каждого компонента цветового пространства, возможно своё значение -критерия и, следовательно, различное количество исключённой информации о дифференциальной структуре сигнала.
В программе (листинг 1) приведён пример кода формирования внутренних элементов паттерна, наружные элементы паттерна формируются с помощью копирования. Двумерный массив data[][] содержит исходное изображение, каждый элемент массива имеет тип IImage, паттерн формируется в массиве pattern[][] каждый элемент массива имеет тип ColorSpace. Изначально в массив pattern[][] полностью копируется изображение data[][], далее в циклах (листинг 1) часть элементов исключается (исключением считается приравнивание к нулю). Переменные (delLo, delAv, delHi) содержат значения -критериев сравнения, по каждому цветовому каналу. Маскирование (корректировка) изначально нулевых значений, содержащихся в изображении и скопированных в паттерн, необходима для их отличия от исключённых из паттерна и исключения «спорных» ситуаций. Отметим, что расчёт производится по несколько видоизменённому выражению (15), к виду:
, (16)
причём, умножение на четыре в программе производится с помощью поразрядного сдвига влево (<<2), такой подход позволяет выполнять все вычисления в целочисленной арифметике с сохранением точности расчётов. Выполнение целочисленных операций процессор производит существенно быстрее, чем операции над числами с плавающей точкой. От величины -критериев зависит число исключённых из паттерна элементов, а в конечном счёте, и степень сжатия изображения. Чем больше величина -критерия для цветового канала, тем больше значений будет исключено.
Листинг 1. Фрагмент программы формирования внутренних элементов паттерна полноцветного изображения (C++).
//====================================================
...
// цветовая палитра
// покомпонентное представление, в скобках указаны компоненты
// палитр (RGB) и (YCbCr) соответственно
struct ColorSpace {
uchar byteLo; // компонента младший байт (Lower) (R) (Y)
uchar byteAv; // компонента средний байт (Average) (G) (Cb)
uchar byteHi; // компонента старший байт (Hight) (B) (Cr)
};
// структура для сохранения цветов в виде int
struct IImage {
int iLo; // компонента младший "байт" (Lower) (R) (Y)
int iAv; // компонента средний "байт" (Average) (G) (Cb)
int iHi; // компонента старший "байт" (Hight) (B) (Cr)
};
...
for (iy=1; iy<Ysize; iy++) {
for (ix=1; ix<Xsize; ix++) {
...
// расчёт разностных элементов для сравнения с критерием
int sLo=abs(data[iy-1][ix].iLo+data[iy+1][ix].iLo+
data[iy][ix-1].iLo+data[iy][ix+1].iLo-(data[iy][ix].iLo<<2));
int sAv=abs(data[iy-1][ix].iAv+data[iy+1][ix].iAv+
data[iy][ix-1].iAv+data[iy][ix+1].iAv-(data[iy][ix].iAv<<2));
int sHi=abs(data[iy-1][ix].iHi+data[iy+1][ix].iHi+
data[iy][ix-1].iHi+data[iy][ix+1].iHi-(data[iy][ix].iHi<<2));
// сравнение разностных элементов с критериями
// исключение из паттерна
if (sLo<=delLo && sAv<=delAv && sHi<=delHi) {
// установка признака исключения элемента из паттерна
// (не являются краевыми условиями)
pattern[iy][ix].byteLo=0;
pattern[iy][ix].byteAv=0;
pattern[iy][ix].byteHi=0;
} else {
// корректировка нулевых элементов паттерна
if (!pattern[iy][ix].byteLo) {
pattern[iy][ix].byteLo=1;
}
if (!pattern[iy][ix].byteAv) {
pattern[iy][ix].byteAv=1;
}
if (!pattern[iy][ix].byteHi) {
pattern[iy][ix].byteHi=1;
}
}
}
}
...
//================================================
В том случае, если полученный в результате рассмотренного выше преобразования паттерн содержит значительное число повторяющихся элементов и граничных условий достаточно для восстановления исходного сигнала с заданной точностью, можно говорить о эффективном (с целью сжатия) исключении избыточной информации.
Для сжатия паттерна предлагаются следующие преобразования. Первое преобразование ориентированно на сжатие значительного числа повторяющихся элементов (кодирование длин серий), в первую очередь элементов исключённых из паттерна и отмеченных в данной реализации нулевым значением. Как уже было сказано, наилучшее качество восстановления изображения получается при одинаковой структуре (по положению исключённых элементов) для всех цветовых компонент, а число последовательных серий, исключённых элементов кратно трём (по числу элементов цветового пространства), что можно учесть при сжатии серий. Полученные на выходе, после кодирования длин серий, данные могут быть сжаты статистическим методом на основе преобразования Хаффмана или арифметического кодирования.
Восстановление изображения производится в обратной последовательности, начиная с декомпрессии паттерна. После получения массива паттерна его используют в качестве граничных условий для решения МКР анализирующего дифференциального уравнения (13) (или другого выбранного при сжатии), в соответствии с разностной схемой (15) и шаблоном (рис. 4). Итерационную схему решения можно выразить уравнением:
, (17)
где - шаг итерации. Если сопоставлять начало итерации с началом циклов обхода массива восстанавливаемого изображения, а завершение итерации с завершением циклов обхода, то выбрав в циклах положительное приращение значений счётчиков, и используя для последующих расчётов ранее вычисленные значения (), уравнение (17) можно записать в виде: