GDCT - новый принцип сжатия изображений

Предисловие. Наиболее важной, но и наиболее «тяжелой» частью мультимедийного информационного потока являются изображения и телевизионный видеоряд. Передача изображений и видео по радиоканалам, которые жестко регламентированы стандартами по мощности сигнала, ширине спектра и уровню помех, требует существенного сжатия информационного потока. Еще на заре цветного телевидения инженеры проявили недюжинную находчивость, упаковав три цвета телевизионного сигнала в ширину канала 6.5 МГц черно-белого телевидения. Переход к цифровой передаче сигнала резко увеличил ширину спектра сигнала. Простые расчеты показывают, что цветное телевизионное изображение после оцифровки требует ширину канала 216 МГц. Начался поиск наилучшего алгоритма сжатия сигнала.

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

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

Естественно, что в качестве базисных функций для спектрального преобразования были взяты хорошо известные синусоидальные функции. Так в основу преобразования было положено дискретное косинусное преобразование (DCT), породившее ряд стандартов: JPEG для сжатия изображений, MPEG 1-4 и Н.261-264 для сжатия видео. Конечно, старая добрая синусоида хорошо поработала в алгоритмах цифрового сжатия сигналов. Однако наследница аналогового века исчерпала свои возможности. Уже давно начался поиск других базисных функций, более приспособленных к цифровой форме сигнала. К сожалению, очень удобные для этих целей функции Уолша, Хаара и др. не подошли из-за медленного убывания спектра и, соответственно, информационной избыточности.

Затем на горизонте появилось Wavelet преобразование. Однако, Wavelet преобразование требует больших вычислительных ресурсов и плохо дружит с динамическим видеорядом телевизионного сигнала. Так что реальный выход этого способа сжатия телевизионного сигнала оказался к настоящему времени не столь впечатляющим. Кроме того, DCT и Wavelet аппаратно и программно несовместимы.

В запасе у математиков был еще один интересный класс функций — классические ортогональные полиномы. В математических расчетах они часто используются из-за ряда замечательных свойств. Но попытки приспособить ортогональные полиномы к цифровой обработке сигналов, привели к неудаче. Одной из причин неудачи является то, что при расчете спектральных коэффициентов полиномы применяются совместно с весовыми функциями, которые в наиболее интересных для практики случаях стремятся к бесконечности. Затруднения в попытке обойти на практике эту особенность заставили некоторых исследователей говорить о «проклятии весовой функции».

Дискретное полиномиальное преобразование.

При работе М. Радченко над диссертационной темой, посвященной разработке и анализу алгоритмов сжатия изображений, появилась идея, как справиться с особенностями ортогональных полиномов. Для этого необходимо применить формулы численного интегрирования гауссовского типа. В таком случае исчезает проблема весовых функций. Кроме того, из всех методов численного интегрирования, квадратурные формулы гауссовского типа являются самыми точными. Это открывает возможность существенно сократить число отсчетов. В том случае, когда исходное изображение представляется в цифровой форме, исходные отсчеты можно прореживать по определенному закону и, тем самым, ввести еще одну ступень сжатия в алгоритм компрессии сигнала. На I-ой Международной конференции по цифровой обработке сигналов – DSPA1998 эта идея была представлена научной общественности [1] и своей необычностью вызвала ряд вопросов как теоретического, так и практического характера. Например, как реализовать полиномиальное преобразование в виде «быстрых» алгоритмов с уменьшенным числом операций. В качестве ответа на этот вопрос в [2] был указан один из путей конструирования таких алгоритмов, использующих симметрию полиномов и их рекуррентную взаимосвязь.

Применение полиномиального чебышевского преобразования (GDCT) в видеокодировании.

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

Анализ свойств полиномиального преобразования, содержащийся в диссертационной работе М. Радченко, выявил его еще одну интересную особенность – неинвариантность обобщенного спектра к сдвигу фрагментов. Это свойство позволило получить спектральные алгоритмы обнаружения подвижных фрагментов изображений и оценки их векторов сдвига. Кроме того, было установлено, что данные алгоритмы обнаружения подвижных фрагментов изображений и оценки их векторов сдвига требуют небольшого числа спектральных компонент, которые в свою очередь могут быть вычислены по небольшому числу отсчетов. Это открывает возможность построения «быстрых» и эффективных вычислительных процедур для их реализации в соответствующих подсистемах. Данная идея отражена в работе [3] и др.

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

Соотношения для DCT:

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

Прямое и обратное чебышевское преобразование:

,

Итак, прямое чебышевское преобразование при сходстве с прямым DCT, имеет иные исходные посылки.

В обратном чебышевском преобразовании число спектральных коэффициентов не привязано к числу сэмплов . Но самое существенное, размер восстановленного блока имеет отсчетов. Таким образом,  — коэффициент геометрического масштабирования восстановленного блока. Причем, может быть произвольным: или У чебышевского преобразования высокая степень алгоритмической совместимости с DCT, что делает возможным создание унифицированного видеокодека, который в зависимости от решаемых задач, пропускной способности канала связи и наличия помех может переключаться с одного типа преобразования на другой. Поэтому Чебышевское преобразование в диссертации М. Радченко было названо GDCT (Generalised DCT — обобщенное DCT). В дальнейшем под этой аббревиатурой было реализовано семейство кодеков изображения, звука и телевизионного видеосигнала.

Итак, в 2000г. в диссертационной работе М. Радченко был предложен, исследован и реализован новый тип видеокодирования – GDCT, не имеющий аналогов в мире. Незадолго до защиты диссертации М. Радченко погиб.

Послесловие. Что дальше? Последующую работу по исследованию возможностей GDCT и практической реализации кодека продолжил Ю.С. Радченко со своими учениками и молодыми коллегами. Была проделана большая работа по алгоритмическому и программному совершенствованию кодека GDCT. Был реализован на этом принципе и аудиокодек. Результаты этой работы доложены на 9 Международной конференции DSPA2007 [4]. На рисунке приведен скриншот интерфейса исследовательской версии кодека GDCT для обработки звука и изображения.

Дальнейшие исследования позволили разработать видеокодек MGDCT для сжатия телевизионного видеосигнала, который превосходит по характеристикам стандарты Н.262-Н.263. Этот видеокодек входит в состав перспективной системы, реализующей «ситуационную осведомленность» (Situational Awareness) в чрезвычайных ситуациях, сетевом мониторинге некоторой области в реальном времени и в реальных координатах [5]. Большие возможности, заложенные в новом принципе кодирования сигнала, далеко не исчерпаны. Продолжение работ, начало которым было положено М. Радченко, позволит усовершенствовать и широко внедрить новую систему видеокодирования с отличными характеристиками.

1. Радченко М.Ю., Радченко Ю.С. Оптимальные быстрые алгоритмы представления изображений в базисе ортогональных полиномов. Труды 1 международной конференции «Цифровая обработка сигналов и ее применения» - DSPA’98, 1998, Москва, т. III, с. 163-166. M. Yu. Radchenko, Yu. S. Radchenko. Optimal Fast Algorithms for Image Representation in Orthogonal Polynomials Basis.,. The 1 International Conference «Digital Signal Processing and its Applications» DSPA’98, Moscow , Russia, v-IIIE, pp. 104-107.
2. Радченко М.Ю. Исследование быстрых алгоритмов дискретизации динамических изображений. Труды молодых ученых ВГУ, Выпуск 1. Воронеж 2000г, с.16-20.
3. Радченко Ю.С., Кожин А.Ю., Радченко М.Ю. Быстрое обнаружение и оценка параметра сдвига сигналов, сжатых с помощью ортогональных полиномов. //«Радиотехника», 1999, № 6, (вып. 37) , с. 17-19.
4. Радченко Ю.С. Экспериментальный кодек чебышевского сжатия/восстановления изображений (GDCT) и программный комплекс для его исследования / Ю.С. Радченко, Т.А. Радченко, А.А. Агибалов, А.В.Булыгин // Цифровая обработка сигналов и ее применение -DSPA 2007. Труды 9- й Международной конференции. - Москва, 2007. – выпуск IX-2, с. 286-289 (рус.), 289 (англ.).
5. Радченко Ю.С. Принципы построения видеокодека MGDCT / Радченко Ю.С., Сохнышев С.В., Булыгин А.В.// Цифровая обработка сигналов и ее применение . - DSPA 2010. : Труды 12-й Международной конференции. - Москва, март 2010. – выпуск XII-2, С. 151-154.