«… у меня идея возникла. Не написать ли научно-популярную статью
о сжатии изображений и видеоконференцсвязи?
Скажем, для какого-нибудь глянцевого компьютерного журнала.»
(Из письма М. Ю. Радченко к Ю.С. Радченко от 30.10.2000г.)
GDCT - новый принцип сжатия изображений
Предисловие. Наиболее важной, но и наиболее «тяжелой» частью мультимедийного информационного потока являются изображения и телевизионный видеоряд. Передача изображений и видео по радиоканалам, которые жестко регламентированы стандартами по мощности сигнала, ширине спектра и уровню помех, требует существенного сжатия информационного потока. Еще на заре цветного телевидения инженеры проявили недюжинную находчивость, упаковав три цвета телевизионного сигнала в ширину канала 6.5 МГц черно-белого телевидения. Переход к цифровой передаче сигнала резко увеличил ширину спектра сигнала. Простые расчеты показывают, что цветное телевизионное изображение после оцифровки требует ширину канала 216 МГц. Начался поиск наилучшего алгоритма сжатия сигнала.
Исследования показали, что из двух путей – сжатие информации без потерь и с регулируемыми потерями для фотореалистических изображений и цветного телевидения годится только второй путь. Первый путь оказался или малоэффективным, или приводил к обратному эффекту, когда результат преобразования превосходил исходный файл в своих размерах.
Реализация второго пути основывается на спектральном преобразовании исходного сигнала по некоторым базисным функциям. Поскольку спектры неравномерны и, как правило, затухают с увеличением номера коэффициента, то появляется возможность отбросить малозначительные спектральные компоненты, а оставшиеся проквантовать. Количество информации сразу сокращается в десятки и даже сотни раз (для видео).
Естественно, что в качестве базисных функций для спектрального преобразования были взяты хорошо известные синусоидальные функции. Так в основу преобразования было положено дискретное косинусное преобразование (DCT), породившее ряд стандартов: JPEG для сжатия изображений, MPEG 1-4 и Н.261-264 для сжатия видео. Конечно, старая добрая синусоида хорошо поработала в алгоритмах цифрового сжатия сигналов. Однако наследница аналогового века исчерпала свои возможности. Уже давно начался поиск других базисных функций, более приспособленных к цифровой форме сигнала. К сожалению, очень удобные для этих целей функции Уолша, Хаара и др. не подошли из-за медленного убывания спектра и, соответственно, информационной избыточности.
Затем на горизонте появилось Wavelet преобразование. Однако, Wavelet преобразование требует больших вычислительных ресурсов и плохо дружит с динамическим видеорядом телевизионного сигнала. Так что реальный выход этого способа сжатия телевизионного сигнала оказался к настоящему времени не столь впечатляющим. Кроме того, DCT и Wavelet аппаратно и программно несовместимы.
В запасе у математиков был еще один интересный класс функций – классические ортогональные полиномы. В математических расчетах они часто используются из-за ряда замечательных свойств. Но попытки приспособить ортогональные полиномы к цифровой обработке сигналов, привели к неудаче. Одной из причин неудачи является то, что при расчете спектральных коэффициентов полиномы применяются совместно с весовыми функциями, которые в наиболее интересных для практики случаях стремятся к бесконечности. Затруднения в попытке обойти на практике эту особенность заставили некоторых исследователей говорить о «проклятии весовой функции».
Дискретное полиномиальное преобразование.
При работе Ю.С. Радченко и М.Ю. Радченко над диссертационной темой, посвященной разработке и анализу алгоритмов сжатия изображений, появилась идея, как справиться с особенностями ортогональных полиномов. Для этого необходимо применить формулы численного интегрирования гауссовского типа. В таком случае исчезает проблема весовых функций. Кроме того, из всех методов численного интегрирования, квадратурные формулы гауссовского типа являются самыми точными. Это открывает возможность существенно сократить число отсчетов. В том случае, когда исходное изображение представляется в цифровой форме, исходные отсчеты можно прореживать по определенному закону и, тем самым, ввести еще одну ступень сжатия в алгоритм компрессии сигнала. На I-ой Международной конференции по цифровой обработке сигналов – DSPA1998 эта идея была представлена научной общественности [1], и своей необычностью вызвала ряд вопросов как теоретического, так и практического характера. Например, как реализовать полиномиальное преобразование в виде «быстрых» алгоритмов с уменьшенным числом операций. В качестве ответа на этот вопрос в [2] был указан один из путей конструирования таких алгоритмов, использующих симметрию полиномов и их рекуррентную взаимосвязь.
Применение полиномиального - чебышевского преобразования (GDCT) в видеокодировании.
Современный видеокодер состоит из целого набора подсистем: матричного спектрального преобразователя, квантователя, обнаружителя изменений в кадре, блока оценки вектора сдвига подвижных фрагментов, блока прогноза и реконструкции текущего кадра, энторопийного кодера и др.
Анализ свойств полиномиального преобразования выявил его еще одну интересную особенность – неинвариантность обобщенного спектра к сдвигу фрагментов. Кроме того, было установлено, что алгоритмы обнаружения подвижных фрагментов изображений и оценки их векторов сдвига требуют небольшого числа спектральных компонент, которые в свою очередь могут быть вычислены по небольшому числу отсчетов. Это открывает возможность построения «быстрых» и эффективных вычислительных процедур для их реализации в соответствующих подсистемах. Данная идея отражена в работе [3] и др.
Итак, было установлено, что полиномиальное преобразование обладает целым набором новых и важных свойств для целей эффективного видеокодирования. Необходимо было выбрать подходящий вид ортогонального полинома, обладающего кроме замечательных математических свойств еще и удобством в числовой реализации. После двух лет расчетов и экспериментов было реализовано нужное преобразование на основе полиномов Чебышева. Находка оказалась удачной. Чтобы оценить ее достоинства, приведем две пары формул для прямого и обратного DCT, а также для прямого и обратного чебышевского преобразования. (Для простоты приводится преобразование по одной координате).
Соотношения для DCT:
Здесь 
- равномерные отсчеты сигнала, 
- типичный размер блока отсчетов, число спектральных коэффициентов равно числу отсчетов. 
при 
, и 
при 
.
Прямое и обратное чебышевское преобразование:
, 
.
Здесь 
- вторичные отсчеты – сэмплы, цифрового сигнала, расположение которых неравномерно, N1 - число первичных равномерных отсчетов в блоке (пикселей), N- число сэмплов для преобразования, N<N1. В зависимости от гладкости сигнала коэффициент прореживания может быть разным: N1/N = 14/8, 12/8, 8/6, 12/6. На рисунке приведен пример двумерного блока с сэмплированием в соотношении N1/N = 8/6. На рисунке пиксели расположены в узлах равномерной решетки, а сэмплы указаны точками.
Итак, прямое чебышевское преобразование при сходстве с прямым DCT , имеет иные исходные посылки.
В обратном чебышевском преобразовании число спектральных коэффициентов M не привязано к числу сэмплов N. Но самое существенное, размер восстановленного блока имеет L отсчетов. Таким образом, k=L/N1 - коэффициент геометрического масштабирования восстановленного блока. Причем, k может быть произвольным: k<=1 или k>1. Заметим, что при использовании DCT операция масштабирования, осуществляется весьма громоздко. Сначала восстановленное изображение передискретизируют, а новые отсчеты определяются путем интерполяции. Затем отсчеты передискретизированного сигнала прореживаются в нужной пропорции. В чебышевском преобразовании эта задача решается легко и автоматически при огромном выигрыше в числе операций.
У чебышевского преобразования высокая степень алгоритмической совместимости с DCT, что делает возможным создание унифицированного видеокодека, который в зависимости от решаемых задач, пропускной способности канала связи и наличия помех может переключаться с одного типа преобразования на другой. Поэтому Чебышевское преобразование было названо GDCT (Generalised DCT- обобщенное DCT). В дальнейшем под этой аббревиатурой было реализовано семейство кодеков изображения, звука и телевизионного видеосигнала.
Итак, в 2000г. был предложен, исследован и реализован новый тип видеокодирования – GDCT, не имеющий аналогов в мире.
Послесловие. Что дальше? Последующую работу по исследованию возможностей GDCT и практической реализации кодека Ю.С. Радченко продолжил со своими учениками и молодыми коллегами. Была проделана большая работа по алгоритмическому и программному совершенствованию кодека GDCT. Был реализован на этом принципе и аудиокодек. Результаты этой работы доложены на 9 Международной конференции DSPA2007 [4]. На рисунке приведен скриншот интерфейса исследовательской версии кодека GDCT для обработки звука и изображения.
Дальнейшие исследования позволили разработать к 2010 году видеокодек MGDCT для сжатия телевизионного видеосигнала, который превосходит по характеристикам стандарт Н.263. Этот видеокодек входит в состав перспективной системы, реализующей «ситуационную осведомленность» (Situational Awareness) в чрезвычайных ситуациях, сетевом мониторинге некоторой области в реальном времени и в реальных координатах. Этот видеокодек ориентирован для работы с неподвижной платформой.
К 2012 г был реализован видеокодек MGDCT2, который имел возможность работать на подвижной платформе. Данная видеосистема обладает развитой структурой пред и постобработки видеосигнала, улучшающих качество восстановленного изображения. Среди наиболее интересных опций обработки изображений можно выделить новый эффективный способ гистограммной коррекции – бета коррекцию, возможность масштабировать восстановленное изображение с любым коэффициентом линейного увеличения 0.25 <= K <= 1 без применения интерполяции и децимации отсчетов, спектральный алгоритм оценки сдвига фрагментов кадра, анализ анизотропии изображения. В данном видеокодеке опробован алгоритм «орлиный глаз», когда часть изображения передается и восстанавливается с высоким качеством, а остальная часть изображения передается и восстанавливается со средним качеством. Это позволяет детально рассматривать интересующие объекты, сохраняя контроль над остальным пространством. На снимках приведены кадры видеопоследовательности, иллюстрирующие работу данного алгоритма. Область более высокого разрешения обведена рамкой.
Для подавления блочного эффекта в восстановленном кадре был разработан алгоритм gdct_deblock, использующий аппроксимацию отсчетов изображения вблизи границ блоков кривыми Безье-Бернштейна.
В работе [5] приведен достаточно полный обзор основных характеристик MGDCT2.
Среди других алгоритмов, реализованных в виде опциональных возможностей MGDCT2 можно назвать следующие:
а) контурный анализ и повышение резкости границ фрагментов изображений,
б) обнаружение и сопровождение подвижных объектов в кадре с помощью спектрального и пространственно-временного корреляционного анализа,
в) обнаружение и выделение лиц в кадре на основе расширенного алгоритма Виолы-Джонса.
Большие возможности, заложенные в новом принципе кодирования сигнала, далеко не исчерпаны. Продолжение работ позволит усовершенствовать и широко внедрить новую систему видеокодирования с отличными характеристиками.
Литература.
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. Радченко Ю.С. Алгоритмы обработки кадров в системе удаленного видеонаблюдения на базе кодека MGDCT2 / Ю.С. Радченко, А.В. Булыгин // Цифровая обработка сигналов и ее применение - DSPA 2016. Труды 18 международной конференции.- Москва. 2016. вып. XVIII-2, с.665-671.