Новая версия

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

В результате качество записанного видео "штормило" вместе с квантователем.

В моем алгоритме сжатия используется два типа кадров: полный и разностный. Полный кадр - это просто сжатое с использованием вейвлет-преобразования изображение. А в разностном кадре храниться разница между предыдущим и текущим кадром, сжатая с помощью того же преобразования.

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

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

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

В результате удалось поднять качество записанного изображения и увеличить производительность кодека. Теперь он позволяет записывать 2 кадра в секунду.

Пока писал предыдущий пост, записал 30 минут видео с экрана. Оно сжалось до 74 Мбайт. Это очень хороший результат, особенно, с учетом того, что сам алгоритм сжатия у меня пока еще далек от идеала.

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

Также добавил возможность сжатия видео из последовательности bitmap'ов, а также возможность сохранения стоп-кадра в формате bitmap'а  из проигрывателя.

В стандарте MPEG используется не два, а три типа кадров. Реализовать третий тип в случае вейвлет преобразования на тех же принципах, что и MPEG, затруднительно из-за разности подходов при осуществлении преобразования. Есть идея, как можно сделать 3-ий тип кадра, но пока не ясно, нужно ли. Требуется провести дополнительные эксперименты.

D2 vs D4

Мое предположение, что более простой вейвлет будет лучше сжимать простые данные, подтвердилось. Но, к сожалению, особой практической ценности оно не несет.

Например, при сжатии экрана, на котором практически не было полутоновых изображений, вейвлет Хаара дал размер видеофайла 8117 Кбайт, а D4 - чуть побольше: 8201 Кбайт. То есть преимущество не значительное.

Если же на экране присутствовали хотя бы на четверти экрана полутоновые изображения, все менялось кардинально. Хаар - 20 Мбайт, D4 - 17 Мбайт.

Естественно, все остальные параметры сжатия были одинаковы.

Но, у Хаара все же есть небольшое преимущество - более высокая скорость преобразования. В частности, само преобразование выполняется практически в 2 раза быстрее, чем D4. А общий процесс сжатия быстрее на 15% в случае наличия на экране меняющихся полутоновых изображений. Если же полутоновых изображений на экране нет, то ускорение немного больше - 22%. Это связано с тем, что после вейвлет-преобразования в случае более простого изображения остается меньше данных для дальнейшего сжатия.

Тот же результат показало и сжатие одиночных изображений. Малоцветное изображение сжимается чуть лучше Хааром (60277 байт против 70557 у D4). А вот с полноцветным изображением все, естественно, хуже: 1516 Кбайт против 1182 Кбайт. В данном случае сравнивались результаты при минимальном потери качества изображения.

Зато Хаар давал изображение в этом случае вообще без потери качества. Но, тем не менее, до PNG ему далеко.

Возникает интересный вопрос: будет ли существенный выигрыш, если использовать вейвлеты более высокого порядка?

Кстати, насколько я смог понять на основе файла, любезно подсказанного мне Иваном, в JPEG 2000 используется также вариант вейвлета D4, просто с более сложным вариантом преобразования двухмерных данных, чем обычно описывается в литературе.

Анализ сравнения

Сравнение форматов сжатия графических изображений, проведенное в предыдущей записи, на мой взгляд, ясно показало, что вейвлет преобразование имеет серьезное преимущество при сильном сжатии изображений. Даже мои самодельйные варианты показывают лучшее качество, чем JPEG. Мне кажется, что если бы этот же подход использовался при сжатии видео, можно было бы добиться двухкратного снижения объема данных по сравнению с различными вариантами MPEG при прочих равных условиях.

Профессиональные форматы жмут изображения лучше, чем мои разработки. Почему? Тут может быть несколько причин:

1. Использование более сложных вейвлет-преобразований.
2. Более сильное сжатие после вейвлет-преобразований без потерь данных.
3. Использование специальных фильтров после восстановления изображения для устранения артефактов сжатия.

Наиболее вероятной причиной мне кажется п. 2, менее вероятной п. 1. Хотя возможно и сочетание обоих факторов. А вот п. 3 мне кажется невероятным. По слухам, использование фильтров сильно улучшает визуальное качество сжатого изображение, однако почему-то разработчики очень редко их реализуют.

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

А давайте-ка их сравним!

Объективное сравнение методов сжатия изображения с потерями - дело трудное и неблагодарное. Поэтому сразу облечгу себе жизнь и попробую провести субъективное оценивание.

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

А потом возьмем и сожмем ее достаточно сильно разными методами сжатия до примерно одного размера. Вот табличка:

Формат	Размер, байт
JPEG	37573
JPEG2000	38299
WI	37715
Мой D4	36757
Мой Хаара	35845

С форматами, пожалуй, все понятно, кроме WI. Это какой-то, возможно, проприетарный формат сжатия, предстваленный в Corel Draw. Собственно, с помощью этой программы и производилось сжатие в стандартные форматы. Сжатие достаточно сильное, такое, что бы артефакты сжатие были хорошо заметны невооруженным глазом.

А теперь попробуйте угадать, где какой формат. На самом деле задачка очень легкая. )

1.

2.

3.

4.

5.

Какой вейвлет лучше?

Точнее, какой из них лучше сжимает изображение с компьютерного монитора?

Вообще, вейвлетов велкое множество. В данном случае речь идет в основном о вейвлетах Добеши разного порядка, так как именно их я использую для сжатия видео.

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

Например, простейший вейвлет Хаара (вейвлет Добеши второго порядка) обнуляет уточнящие коэффициенты вейвлет-преобразование в случае постоянного уровня сигнала (например, яркости изображения). То есть, с точки зрения задачи сжатия, он хорошо сжимает функции вида y=const. А, например, вейвлет Добеши 4 порядка может хорошо сжимать как функции y=const, так и линейные функции y=kx+b. Вейвлеты более выских порядков, соответственно, позволяют сильнее сжимать изображения, имеющие более сложные функциональные зависимости.

Алгоритму же JPEG проще всего было бы сжимать изображения, которые описываются гармоническими колебаниями достаточно высокой частоты.

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

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

А как думаете вы, какой вариант будет лучше?