Предсказания по оси времени

Технология обработки видеоданных на IBM-совместимых персональных компьютерах с появлением современных микропроцессоров поколения Pentium, не говоря уже о Pentium II или Pentium Pro, преодолев множество барьеров, стала реальностью, и сегодня простой домашний PC может быть с успехом использован как для просмотра записанных на CD видеофильмов, так и для почти профессионального видеомонтажа с использованием достаточно сложных графических эффектов, еще каких-нибудь десять лет назад доступных лишь при использовании старших моделей компьютеров Sun SparcStation. Однако до сих пор широкому использованию современных технологий препятствуют огромные размеры графических файлов и файлов видеоданных.

При записи изображения обычно используется по 8 бит (1 байт) для представления 256 уровней яркости красного, зеленого и синего цветов (RGB). Таким образом, для хранения одного элемента изображения (пиксела) требуется 3 байта памяти. Стандартный видеокадр формата 352х288 пикселов требует 304128 байтов, а изображение на экране монитора даже при разрешении 640х480 занимает в памяти почти целый мегабайт! А если прибавить к этому частоту 25 или 30 кадров в секунду, то становится очевидным, что ввод в PC и хранение видеоданных без сжатия - затея достаточно дорогая.

Использование классических алгоритмов сжатия "без потерь", таких как RLE (кодирование длин серий) или LZW (метод Зива-Лемпела-Уэлча), не решает проблемы, поскольку предельные для них коэффициенты сжатия (2-3 в случае черно-белых полутоновых или 1,5-2 для RGB изображений) совершенно недостаточны для большинства приложений. Заметим, что коэффициент сжатия, достигаемый при использовании любого метода, зависит от характера изображения. Очевидно, что одноцветный фон в любом случае сожмется лучше полного мелких деталей изображения.

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

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

Как было сказано выше, при записи изображений традиционно используется RGB-представление, когда на каждую цветовую составляющую приходится по 1 байту. Альтернативный подход состоит в переходе от RGB к YCrCb-представлению:

Y=0,299*R+0,587*G+0,114*B

Cb=(B-Y)/0,866/2+128

Cr=(R-Y)/0,701/2+128

Чувствительность человеческого глаза к яркостному Y-компоненту и цветностным компонентам Cb и Cr неодинакова, поэтому вполне допустимым представляется выполнение этого преобразования с прореживанием (интерливингом) Cb и Cr компонентов, когда для группы из четырех соседних пикселов (2x2) вычисляются Y-компоненты, а Cb и Cr используются общие (схема 4:1:1). Более того, пре- и постфильтрация в плоскостях Cb и Cr позволяет использовать прореживание по схеме 16:1:1 без сколько-нибудь значительной потери качества! Нетрудно подсчитать, что уже схема 4:1:1 позволяет сократить выходной поток вдвое (вместо 12 байтов для четырех соседних пикселов достаточно шести). Схема 16:1:1 обеспечивает сокращение потока в 2,67 раза.

Далее. В основе ставших уже классическими стандартов сжатия JPEG (для статических изображений) и MPEG (для видеоданных), так же как и в сравнительно новых методах сжатия на основе Wavelet-преобразования, лежит переход от пространственного представления изображения к спектральному. В случае JPEG/MPEG для такого перехода используется дискретное косинус-преобразование (ДКП) на блоках 8(8, в случае Wavelet - система фильтров, примененных ко всему изображению. На рис. 3 слева вверху приведен фрагмент некоего изображения в виде блока (матрицы) пикселов размером 8(8 (разделенный по диагонали черно-белый квадрат). Применение к пиксельной матрице ДКП дает матрицу из 64 коэффициентов или спектральных составляющих. Нулевой коэффициент представляет собой среднюю яркость исходного блока, поэтому, отбрасывая при восстановлении коэффициенты с 1 по 63, мы получим просто серый квадрат (на рис. 1 - в верхнем ряду в центре). Добавление первого коэффициента позволяет достаточно грубо описать распределение яркостей в исходном блоке по горизонтали (вверху справа).

Рисунок 1.

Внизу слева и в центре приведены результаты восстановления исходного блока с использованием коэффициентов соответственно 6 и 15. Очевидно, что число ненулевых спектральных составляющих тем выше, чем больше мелких деталей содержалось в исходном блоке. Эксперименты показывают, что на типичных полутоновых изображениях более половины всех блоков 8(8 могут быть описаны менее чем 20 спектральными составляющими.

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

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

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

Гораздо более перспективным для получения больших коэффициентов сжатия представляется использование Wavelet-преобразования (wavelet - небольшая волна. Компьтерный словарь Lingvo, версия 5.0). Переход в частотную область в схемах на его основе, как было сказано выше, достигается применением наборов фильтров.

Рисунок 2.

Весьма приблизительно общую схему сжатия на основе Wavelet-преобразования можно описать так. Исходное изображение (естественно, после преобразования RGB - YCrCb) фильтруется с применением низкочастотного и высокочастотного фильтров по строкам и по столбцам с последующим прореживанием, так что вместо одного изображения размером MxN пикселов (рис. 2) после первого прохода синтезируются 4, размером (M/2)((N/2) каждое, причем наиболее информативным из них оказывается [hh] - то, которое было получено с использованием низкочастотного фильтра как по строкам, так и по столбцам (на рис. 3 - слева вверху).

Рисунок 3.

Применение низкочастотного фильтра по строкам и высокочастотного по столбцам [hg] или высокочастотного по строкам и низкочастотного по столбцам [gh] (соответственно справа вверху и слева внизу) дает значительно более "бедную" картинку, и совсем уж малоинформативным оказывается изображение [gg], полученное с использованием высокочастотного фильтра как по горизонтали, так и по вертикали (справа внизу). Дальнейшая судьба этих изображений (или саббэндов) неодинакова. Саббэнды [hg] и [gh] обычно квантуются и после применения статистического кодирования попадают непосредственно в выходной поток. Саббэнд [gg] чаще всего просто игнорируется, а вот [hh] ждет та же судьба, что и исходное изображение (рис. 4). И так далее. Для изображений "экранного" размера число уровней фильтрации составляет обычно 4-6.

Рисунок 4.

Максимально достижимые коэффициенты сжатия при использовании Wavelet-преобразования зависят от размеров исходного изображения, и при приемлемых искажениях на экранном разрешении можно говорить о 50-70-кратном сжатии.

Автор уверен, что прочитав последний абзац, разработчики собственных схем сжатия, основанных на Wavelet-преобразовании, часто весьма эффективных, возмутятся: "Чепуха! Моя схема сжимает в сто (в двести, пятьсот, тысячу... - ненужное зачеркнуть) раз, а не в какие-то жалкие 50-70!", - но - повторю еще раз - речь идет о приемлемых искажениях. Ограничения, подобного блоку 8(8 в JPEG/MPEG, Wavelet-преобразование не накладывает, но характерные для него искажения (рябь, размывание мелких деталей) также достаточно неприятны. И вообще следует сказать, что, по наблюдениям автора, Wavelet-преобразование обеспечивает лучшее, нежели JPEG, качество восстановленного изображения при больших коэффициентах сжатия и несколько уступает ему, когда требуется получить высокое качество (критерий - отношение сигнал/шум) при невысоких (10-15) степенях сжатия.

Схемы, основанные на Wavelet-преобразовании, традиционно считаются достаточно трудоемкими, и, тем не менее, в последнее время появились интересные программные реализации (см., например, http://www.cengines.com), позволяющие получать 15-20 кадров в секунду (не real time, но все-таки...) на компьютерах с процессором Pentium 133 (рис. 5 и 6), что делает возможным их использование в коммуникационных задачах (видеоконференции через Интернет, видеофон и т. д.)

Рисунок 5.Рисунок 6.

Вообще говоря, качество приведенных изображений не слишком высокое, и связано это прежде всего с невозможностью получения требуемого коэффициента сжатия (100-150) на малом изображении (176(144) без использования межкадрового сжатия. Отсутствие разбиения на блоки, обеспечивающего впечатляющее качество при 50-кратном сжатии неподвижных изображений, не позволяет использовать в Wavelet-схемах применяемую в MPEG простую и элегантную методику компенсации движения, а без такой компенсации говорить о сколько-нибудь серьезной конкуренции между Wavelet и MPEG, пожалуй, преждевременно. Возможно, именно в этом причина отсутствия общепринятого стандарта на Wavelet-компрессию видеоданных и, как следствие, непопулярность ее у разработчиков "железа".

Если говорить о перспективах, то не очень понятно, есть ли они у Wavelet. Дело в том, что по мере роста пропускной способности каналов связи и емкости носителей с одной стороны и требований к качеству изображений с другой, необходимость в использовании мощных методов сжатия, обеспечивающих всего лишь "приемлемое" качество восстановленных изображений, кажется сомнительной. Может быть, стоит вспомнить о неискажающем сжатии, но не классическом, о котором речь шла в начале статьи, а о мощных предиктивных методах, подобных JBIG, способных обеспечить 6-8-кратное сжатие неподвижных черно-белых полутоновых изображений при полном отсутствии искажений? Ведь добавить к JBIG цвет (RGB-YCrCb хотя бы как 4:1:1 - потери-то мизерные), сделать предсказатель трехмерным (третье измерение - вдоль оси времени), и... Но об этом - как-нибудь в другой раз.