Декорреляция изображений набором предсказателей

Декорреляция изображения – первый и самый ответственный этап кодирования. Здесь не происходит собственно компрессия данных, а выполняется лишь преобразование избыточности из одной формы в другую. Большая часть избыточности заключена во взаимной зависимости отсчётов и цветовых компонент изображения. Различают зависимость линейную и нелинейную. Линейная избыточность обусловлена корреляционными связями соседних отсчётов. Линейные свойства изображения легко оцениваются по "прошлым" отсчётам и прогнозируются на "будущие". Формализовать нелинейную часть избыточности, а тем более предсказать, практически невозможно. Поэтому в процессе кодирования приходится лишь констатировать о тех или иных свойствах изображения, не вкладывающихся в корреляционную модель. На рисунке 4 приведена схема алгоритма с набором предсказателей, рассчитанных на различные текстуры изображения в районе кодируемого отсчёта: плоские, наклонные участки, перепады яркости в различных направлениях. Приведённая схема является развитием опубликованной ранее [1].

Рис. 4. Структура декоррелятора

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

Арифметические операции в декорреляторе выполняются не на бесконечной числовой оси, а в замкнутом множестве чисел с использованием модулярной арифметики. Этот, скорее, технический приём предотвращает увеличение разрядности чисел и даёт незначительное повышение эффективности. Более подробно применение модулярной арифметики описано в [2].

Один предсказатель выбирается для группы отсчётов во фрагменте изображения размером W×W. В отдельных фрагментах изображения оптимальными будут различные значения W. Оптимальные состав и количество предсказателей также будут зависеть от локальных свойств изображения. Разделить изображение на неперекрывающиеся фрагменты различного размера очень сложно. Поэтому предлагается следующий компромиссный вариант: изображение делится на равные зоны размером W₂×W₂, которые делятся на более мелкие зоны размером W₁×W₁, которые, в свою очередь, делятся на ещё более мелкие фрагменты размером W₀×W₀. В этой структуре переменны только количество зон W₀×W₀ и их размеры.

Увеличение числа предсказателей предоставляет большие возможности выбора, но сдерживается возрастающей разрядностью номеров. В тоже время, в отдельно взятых участках изображения и не требуется большого многообразия предсказателей. Свойства изображения меняются медленно или, что точнее, постоянны в пределах ка-кого-то региона. Поэтому большинство предсказателей, оказавшихся лучшими в одном фрагменте изображения, скорее всего, будут лучшими и в соседних фрагментах. Для каждой зоны W₂×W₂ формируется множество ℵ₂ из n₂ предсказателей из N возможных. Из полученного множества формируется подмножество ℵ₁ ⊆ℵ₂ из n₁ ≤ n₂ предсказателей для каждой зоны W₁×W₁. Наконец, из полученного подмножества выбирается по одному предсказателю для каждой зоны W₀×W₀. Множества ℵ₁ и ℵ₂ могут состоять как из одного, так и из N предсказателей, т.е. 1 ≤ n₁ ≤ n₂≤ N. Такое пирамидальное кодирование номеров требует значительно меньшее количество бит, чем при прямой адресации среди N предсказателей. Возможность варьировать размеры множеств ℵ₁ и ℵ₂ позволяет регулировать степень применения предлагаемого алгоритма кодирования. Так на одних участках изображения будет применяться кодирование множеством предсказателей, а на других – одним предсказателем (n₁= n₂= 1). В последнем случае объём дополнительных данных будет незначителен, и алгоритм будет временно работать как обычный ДИКМ-кодер.

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

(1)

где I ' – количество информации в ошибках предсказания зоны W₂×W₂, I " – количество бит, требуемых для описания множеств ℵ₁ и ℵ₂.

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

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

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