Звук

Попробовал сжать звук с помощью 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, при сравнимых показателях качества сжатия?