Звук

Попробовал сжать звук с помощью wavelet-преобразования.

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

Немного, прямо скажем. Но резервы есть, если перейти на сжатие с переменным квантизатором.

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

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

Scalar SSE

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

Для оценки времени выполнения я использовал, в отличии от Ивана (см. комментарии к предыдущему сообщению), другой метод. С помощь пары команд процессора RDTSC/RDTSCP я получаю количество тактов процессора, потребовавшихся на исполнение функции вычисления скалярного произведения. Для того, что бы избавится от случайностей, функция вычисляется 100 раз. Результаты сортируются, 10 наибольших и наименьших значений отбрасываются, а среднее считается по оставшимся 80 измерениям.

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

Вот полученные результаты:

	AMD FX-4350 4.2 GHz (очень редко)	Intel Core i3 3227u 1.9 GHz	AMD FX-4350 4.2 GHz (обычно)
4 элементные векторы
SSE	143	184	408
SSE3	157	184	408
SSE4	161	178	417
Pure Pascal	167	182	464
FPU	149	181	415
Scalar SSE	145	182	399
Векторы произвольной длины
Pure Pascal	216	154	628
FPU	164	143	432
Scalar SSE	151	165	408

Сначала про SSE. Анализ показывает, что скорость вычисления векторного произведения для чисел с плавающей точкой одинарной точности не зависит от выбранного способа решения задачи!

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

С чем это связано, мне трудно сказать. Возможно, я сгенерировал не самый лучший код для SSE. Возможно, дело в самой задачи. Как заметил Иван в комментарии к прошлому посту, SSE по идее могут выполнять две инструкции за такт: сложение и умножение. Но в случае векторного произведения эти две операции жестко связаны: не выполнив умножение, нельзя посчитать сложение. Поэтому и не достигается максимальная производительность. Использование команды DPPS (входит в набор SSE4) не приводит к заметному улучшению производительности, причем на обоих платформах (на АМД даже медленнее чуть-чуть).

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

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

В случае же АМД все предсказуемо. Но замедление не так значительно, так как целочисленные команды, команды FPU и команды SSE могут выполнятся параллельно и независимо друг от друга. Если, конечно, они не взаимозависимы по данным.

Пока что на основе приведенного исследования можно сделать следующий вывод: для чисел с плавающей точкой использование команд SSE на текущий момент не очень оправдано. По крайней мере при расчете векторного произведения.

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

SSE3 и SSE4

Оптимизация под набор команд SSE3 и SSE4 не дала вообще никакого прироста производительности. Все три варианты выполняются за стабильно одинаковое количество тактов. А скалярная версия под FPU чуть-учть быстрее.

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

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

Еще можно попробовать использовать команды SSE для вычислений в скалярном режиме. Возможно, это даст какой-то выигрыш.

SSE

Начал пытаться оптимизировать под SSE wavelet-преобразование.

Чисто теоретически система команд SIMD позволяет одновременно выполнить сразу несколько команд (4 в случае SSE). Правда, за это приходится платить тем, что данные для таких команд надо подготовить. Ситуации, когда данные расположены не подряд в памяти, не так уж редки. В наборе команд SSE1 (самой первой версии), специальных инструкций для таких случаев я не обнаружил.

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

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

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

Для выполнения вейвлет-преобразования необходимо выполнить векторное произведение. Если его написать тупо, вот так например:

result := 0;
for i := 0 to 3 do
  result := result+v1[i]*v2[i]

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

result := v1[0]*v2[0]+v1[1]*v2[1]+v1[2]*v2[2]+v1[3]*v2[3]

то тут есть где разгуляться современному процессору.

Ну так вот. Такой код при включенной оптимизации работает лишь чуть медленнее варианта на  ассемблере под SSE1. Это показалось мне подозрительным и я переписал исходный скалярный код с паскаля на ассемблер. Вуаля: это код работает чуть быстрее, чем SSE1.

Хотя, может это просто мой процессор дешевый и модуль SSE у него не быстрый? Еще одна тема вызывает у меня удивление: это набор команд SSE. Наверное, я чего-то не понимаю, но мне они показались чрезвычайно неудобными.

Теперь продолжу эксперименты с более новыми версиями SSE, там в версии 4 есть даже вариант, который, собственно, считает векторное произведение. Может, это существенно ускорит работу SIMD.

Wavelet и музыка

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

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

Все оказалось именно так, как я и думал. Степень сжатия таких музыкальный фрагментов существенно ниже, чем у голоса. Но, тем не менее можно ожидать порядка 6-х кратного сжатия. С учетом того, что обычно во всем музыкальном произведении все же не всегда используется весь диапазон, то в среднем можно ожидать сжатие в районе 10-12 раз. Что, на мой взгляд, весьма неплохо.

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

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

Когда-нибудь доберусь и попробую сделать простенькую реализацию сжатия файлов.

Wavelet и голос

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

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

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

По левой оси отложено % коэффициентов прямого вейвлет-преобразования, которые по абсолютной величине меньше 1/256 и 1/16. При оценки степени сжатия я исхожу из того, что первые данные можно в принципе вообще отбросить, а вторые достаточно сильно сжать. Исходя их эти предположений я рассчитываю теоретический предельный уровень сжатия, данные по которому привязаны к правой оси. Таким образом по левой оси 4 графика (по два на каждый эксперимент) и на правой два (по одному на каждый эксперимент).

Выводы

Исходя из представленных данных можно сделать следующие выводы:

1. Вполне ожидаемый. По достижении определенного порядка вейвлет-преоборазования его дальнейшее увеличение не ведет к повышению степени сжатия. Для голосовых данных насыщение наступает в районе 18-20 порядка, для зашумленных чуть позже. Это связано как с тем, что вейвлет-преобразование осуществляется многократно, так и с тем, что зависимости более высокого порядка отсутствуют в исходных данных. Но в музыкальных данных такие зависимости могут быть.
2. Даже без учета психоакустических особенностей слуха можно с помощью вейвлет-преобразования можно добиться результатов, сравнимых с преобразованием Фурье, а возможно, и несколько лучше.
3. Однако отсутствие учета психоакустических особенностей может привести и к существенным искажениям данных, что сделает прослушивание такого звука малоприятным.

Что дальше

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

Звук

Интересно, насколько сильно можно сжать звук с помощью вейвлет-преобразования?

Мои собственные попытки в 2004 году оказались не очень удачные в этом плане. MPEG audio, используя психоакустические особенности восприятия звука человеком, достигает примерно 10-кратного сжатия звука, которое практически не заметно на слух (для большинства, за исключением меломанов и профессионалов).

С ходу в русскоязычном интернете я не нашел каких-либо значимых работ в этом направлении. Но сильно не усердствовал, так как мне интересна проблема само по себе, вне контекста других работ в этом направлении.

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

Основой сжатия MPEG audio является  преобразование Фурье, базисом которого как раз и являются синусоидальные функции. В то время как базисом вейвлет-преобразования Добеши являются полиномы.

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

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

1. Во сколько улучшится степень сжатия при использовании вейвлетов более высоких порядков?
2. Каков оптимальный порядок вейвлетов для осуществления сжатия звука с учетом достижения оптимальной производительности преобразования?
3. Можно ли достичь или даже превысить коэффициент сжатия, достигнутый MPEG audio, при сравнимых показателях качества сжатия?

Обновление

Выложил очередное обновление программок. Сделал немножко более "человеколюбивый" интерфейс.

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

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

Но это когда-нибудь потом... )

Очередная версия

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

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

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

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

Переменный квантизатор

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

Посмотрим, что это дало. Первое изображения - с постоянным квантизатором, взято из одного из предыдущих постов. Это вейвлет Добеши 4 порядка. k=1.

Это вейвлет того же порядка, но с k=2, то есть после каждого этапа преобразования квантизатор увеличивается в два раза, пока не достигнет некоторой границы.

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

А вот тот же вейвлет с k=4.

Еще более плавный фон. И еще меньше детализация.

Еще ради интереса реализовал вейвлет Добеши 6 порядка. Вот он с k=2.

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

Вот он же с k=4.

Еще более плавный фон, меньше размытие, но и меньше деталей на изображении.

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

Что касается вейвлет преобразования 2 порядка, или Хаара, то там все просто. Отбрасывание ненулевых коэффициентов приводит просто к снижению разрешения, так как такой простой вейвлет не моделирует каких-либо зависимостей, кроме y=const.

PS: и да, не забудьте. Изображения, показанные здесь, были сжаты примерно в 50 раз.

JPEG 2000

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

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

1. JPEG2000 использует более продвинутый вейвлет, построенный с использованием лифтинга. Я не настолько хорошо знаю математику, но, по моим прикидкам, он примерно соответствуют вейвлету Добеши 8 порядка. Правда, в отличие от вейвлета Добеши, он наверняка обладает какими-то дополнительными полезными свойствами. С ходу можно отметить его симметричность. А использование лифтинга позволяет существенно снизить вычислительные затраты на его получение, правда, за счет немного большей потребности в памяти и потенциальном усложнении его оптимизации под SIMD команды.
2. Сэкономив на вычислениях вейвлет-преобразования, разработчики JPEG2000 потратили освободившиеся ресурсы процессора на более сложную процедуру энтропийного сжатия. Они отказались от использования квантизатора, подобного тому, что применяется в обычном JPEG. Вместо этого они, похоже, анализируют вейвлет-коэффициенты, и в зависимости от них, определяют значимость того или иного коэффициента и то, насколько точным его необходимо сохранить. Академический английский, используемый в тексте, труден для понимания, поэтому пока еще не до конца въехал в смысл данного алгоритма. Но алгоритм реально крут, потому как, кроме эффективного сжатия, еще и обеспечивает сохранение четких границ без ряби вокруг них.
   Дело в том, что и рассматриваемые вейвлет-преобразования, и преобразование Фурье для функций, имеющих разрыв первого рода, дают ненулевые и существенные значения для всех  коэффициентов ряда. Если в результате сжатия с потерями (обнулением некоторых коэффициентов) восстановить данные по таким коэффициентам, то вблизи разрыва мы получим волновую функцию, вид которой зависит от исходной базисной функции преобразования.
   Для изображений таким разрывом в функции является любая четкая граница между объектом и фоном. В результате после восстановления с потерями в изображении возле границы появляются затухающие волны на основе какого-либо полинома (для рассматриваемого вейвлет преобразования). И чем выше порядок вейвлет-преобразования, тем длиннее получается волна.
   Так вот, алгоритм JPEG2000 позволяет очень эффективно бороться с такими искажениями даже при сильном сжатии изображения.
3. Завершающим этапом энтропийного сжатия является арифметическое кодирование, которое несколько эффективнее Хаффмана. Я пока арифметический кодер к своей программке не прикрутил.

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

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

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

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

Отказался от нормирования я сознательно, так как это снизит вычислительные затраты алгоритма. Но, с учетом вейвлет преобразования, возникает одна тонкость. После каждого этапа преобразования низкочастотные коэффициенты фильтра возрастают в sqrt(2) раз от среднего.  В случае яркости коэффициенты на каждом этапе возрастали, так как большинство изображений имеют яркость в районе среднего, а очень темные встречаются относительно редко. В то время как каналы цветности, хоть и отклонялись сильно от нуля, но в среднем были к нулю близки. То есть после полного преобразования всего изображения множество коэффициентов в каналах цветности были близки к нулю, а в канале яркости - были как раз далеки от него. Естественно, нули при переходе к энтропийному сжатия отбрасываются и каналы цветности оказываются гораздо меньше по размеру.

Поэтому я решил провести нормировку, и теперь все каналы имеют диапазон от -1 до +1. Только применение этого подхода позволяет снизить размер изображения до 20% (если средняя яркость близка к среднесерому). Если в предыдущем варианте сжатия лучше всего сжимались темные изображения, а хуже всего - светлые, то сейчас преимущество имеют изображения со средней яркостью, коих, как мне кажется, большинство.

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

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

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

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

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

Новая версия

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

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

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

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

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

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

В результате удалось поднять качество записанного изображения и увеличить производительность кодека. Теперь он позволяет записывать 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). Но у более простого вейвлета количество ненулевых высокочастотных слагаемых будет меньше.

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

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

Немного статистики

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

Похоже, это любо глюк Delphi, либо Windows. Или, наоборот, это фича такая?

При многократном рендеринге в битмап возникает "тихая" ошибка. Точнее, с какой-то итерации рендеринг прекращается, ошибки не возникает, а исходный битмап не меняется. Рендеринг, это на самом деле BitBlt с десктопа. Идея была в том, что бы не создавать на каждой итерации TBitmap, а просто рендерить в один раз созданный. Естественно, ради производительности. Но, похоже, издержки по создания TBitmap не так уж высоки, поэтому пока отложил этот вопрос куда-то в неопределенное будущее.

Параллельно посмотрел статистику, какие же операции наиболее затратные при сжатии видео. У меня были некие идеи о том, какие операции будут наиболее медленным. Но я их вообще не угадал. )))

Процесс	Время, с	% от общего времени
Screen copy	14.724	11.60%
Color conversation	13.649	10.75%
Wavelet conversation	57.431	45.24%
Data loss reduction	23.41	18.44%
RLE reduction	13.087	10.31%
Haffman coding	4.65	3.66%

Совершенно неожиданно, больше всего заняло wavelet-преобразование, несмотря на его простоту. Соответственно, можно ожидать и большого эффекта от оптимизации этого кода.

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

Второй подход состоит в том, что 2, 3 и 4 пункты можно объединить и выполнять в одной процедуре. Каждая из этих процедур обрабатывает целиком все внутреннее представление изображения, которое занимает достаточно солидный объем. Выигрыш здесь потенциально состоит в том, что данные чаще будут попадать в кэш, это снизит нагрузку на подсистему памяти и повысит производительность. Но будет ли существенный эффект от этого?

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

Также можно примерно оценить и то, сколько можно снять копий экрана в секунду, при максимальной загрузке одного ядра и использовании операции BitBlt. По результатам статистики, если убрать все остальные операции, это даст примерно 9 кадров в секунду. С учетом того, что ядро в текущем варианте загружено в среднем на 30-40 процентов, можно ожидать съема до 20-30 кадров в секунду.

Исправление

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

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

Захват видео

Выложил тестовую однопоточную версию сжатия видео с использованием wavelet-преобразования. Я как раз в прошлом сообщении об этом писал.

Версия очень-очень тестовая, чисто на посмотреть, как оно вообще жмет и немного оценить качество самого преобразования.

Программки чрезвычайно сырые и глюкавые. Но тем не менее.

Из явных глюков: 

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

Также пока не доступны некоторые настройки, в основном из-за ограничения по быстродействию (программа не оптимизирована вообще никак), а некоторые возможности просто не протестированы.

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

Если кто захочет побаловаться, сразу предупреждаю, нужен достаточно мощный и современный процессор. Настройки установлены для максимально возможного на текущий момент сжатия для разрешения 1280х1024. Если у вас другое разрешение, то битрейт необходимо пересчитать, а то качество и так не блещет при 30-кратном сжатии.

Расчет очень прост: w*h*3/1024/fps/30,

где w - ширина изображения экрана, h - его высота, fps=1 - частота кадров.

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

С точки зрения лягушки

Когда-то в подростковом возрасте прочитал статью, про то, как видят лягушки, а на самом деле, земноводные и пресмыкающиеся. Они не "видят" все поле зрения, а реагируют только на изменения яркости. Очень удобно при охоте. Сразу видно движение, а фон не отвлекает внимание.

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

Мелкий точечный шум в начале и конце ролика не имеет отношения к лягушачьему зрению. Это артефакты MPEG сжатия. Когда разница между кадрами невелика, алгоритм пытается улучшить мелкую детализацию изображения. Из-за этого и возникает такой шум.

А вот исходный ролик:

Какая разница, да? Хоть она и велика, в реальности зрение человека чем-то похоже на зрение  более низко развитых животных. Оно также реагирует только на изменение интенсивности сигнала, а неизменный сигнал не воспринимает. Почему же мы видим не фрагменты двигающихся объектов, а яркое, насыщенное изображение по всему полю зрения? Это помогают очень мелкие, незаметные для человека, движения глазного яблока. Так называемый нистагм. Так что яркую и сочную картинку мы видим из-за того, что наши глаза постоянно дрожат.

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

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

Вейвлеты

Когда-то, наверное, в 2003 году, не помню уж откуда и почему, нас на кафедре завлекла тема вейвлетов. Нас - это на самом деле меня и Артема. Есть подозрение, что это Артем ее где-то и нарыл. Он хорошо знает математику и любит ее и всякие новшества. В отличие от меня, консерватора.

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

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

В частности, я написал программку, которая сжимала изображение не хуже, чем JPEG. На самом деле при сильной компрессии она давала лучшее качество изображения, чем JPEG. При малой компрессии она чуть-чуть проигрывала JPEG в детализации. Для сжатия без потерь использовался алгоритм арифметического сжатия. Первый вариант такого алгоритма в рамках курсового проекта сделал под моим руководством Александр Шендриков. Я же использовал несколько переработанную версию этой реализации.

Естественно, эта разработка не представляла какого-то практического интереса, в силу наличие известного и широко распространенного стандарта JPEG. Поэтому я потихоньку потерял к ней интерес, да и времени не оставалось ею заниматься.

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

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

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

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

Сейчас, даже без какой либо оптимизации, на тестовой программе возможно снимать 1 кадр/с с экрана разрешением 1280х1024 при 40-50% загрузке одного ядра.

32 vs 64: Assembler

Все ж мне стало любопытно, почему 64-битный код работает медленнее 32-битного. Уже было ясно, что дело в компиляторе, потому что тесты Ивана на С++ показали, что 64-битный режим работает быстрее 32-битного.
Ведь нельзя сказать, что компилятор дельфи совсем нечего не делает. Потому что оптимизированный 64-битный код все же работает быстрее не оптимизированного. Просмотр в режиме отладчика тоже никаких явных корявостей не обнаружил. Поэтому я решил вспомнить, что такое ассемблер и переписал быструю сортировку вручную.

Стало немного быстрее, но 32-битный код я так и не догнал. Переписал 32-битный вариант и понял, что я что-то делаю не так, потому что мой ассемблерный 32-битный код оказался медленнее кода на дельфи.
Начал смотреть, что делает компилятор. И понял, что давным-давно регистровая оптимизация для x86 и x64 не очень актуальна. Благодаря теневым регистрам и предсказанию ветвления. Это вам не RISC. А я-то  как раз пытался все в регистры перенести. Еще один момент связан с заполнение конвейера, но сюда я уже не стал глубоко залазить.

Короче, добился, что бы мой 32-битный ассемблерный код работал почти также быстро, как и скомпилированный. Но перенос его на 64 бита оказался все равно медленнее 32-битного.
Как выяснилось, дело здесь в том, что я обрабатывал 32-битные данные в 64-битных регистрах. Исходя из предположения, что на современных процессорах что 32-битная, что 64-битная регистровая операция производится примерно с одинаковой скоростью. По всей видимости, из того же предположения исходили и разработчики компилятора. :)
Так вот, это не так. Как только я начал работать с половинками 64-битный регистров, я сразу догнал по производительности 32-битный код.

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

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