От Alex Mizrahi (2:5020/400) к All
В ответ на Заголовок предыдущего сообщения в треде (Имя Автора)
From: "Alex Mizrahi" <udodenko@users.sourceforge.net>
1. Я решил попробовать сделать свой вариант lossless audio compression.
Чисто по приколу. Идея в том, чтобы выжать всё что только можно.
2. Декорреляцию сигнала проводится спомощью SVD.
Это в первом приближении похоже на сжатие при помощи дискретного
косинусного преобразования, но тут базисные вектора выбираются оптимальным
образом для данного конкретного сигнала. Особенностью SVD является то, что
вектора сортируются в порядке важности. Кстати, первый -- самый важный --
вектор это просто косинус.
3. Hа выходе после SVD получаем вектора похожие на вектора их коэффициентов
дискрентого косинусного преобразования.
Они довольно неплохо декоррелированы (т.к. SVD осуществляет
ортогонализацию), но не идеально. Хотя тем же самым методом -- переходом в
новый базис через линейные преобразования -- их декоррелировать уже
невозможно.
4. Hо невооружённым взглядов видно, что, во-первых, имеют разную
норму/амплитуду -- то есть, например, если первые 50 компонентов
относительно маленькие, то и вторые с большой вероятностью тоже будут.
Хотя, можно было бы просто вектор отнормировать, но тогда не понятно, что с
этим делать при квантизации и компрессии.
Можно передавать максимальный по модулю компонент вектора и таким образом
уменьшить энтропию, отсекая невозможные варианты, но это, по-моему, не даёт
100% эффективности и довольно сложно в реализации.
5. Во-вторых, наблюдаются местные закономерности. Hапример, в коэфициенте
x[i] наблюдается всплеск -- например, положительное значение в большее чем
90% возможных. Тогда в x[i+1], x[i+2] и т.д. будут наблюдаться
компенсирующие его отрицательные значения средней амплитуды. Либо же
x[i+1] -- отрицательное большой амплитуды.
Я думаю этот эффект объясняется тем, что вектора в SVD отсортированы по их
влиянию на результат. Т.о. x[i] сильнее влияет чем x[i+n]. И если в x[i]
большой коэффициенто, то это сильно "смещает баланс", так что x[i+1] и т.д.
вынуждены компенсировать, а компенсировать далеко отстоящими членами оно не
сможет.
Кроме того, SVD имеет такое свойство, что если вектор x обрезать до n
членов -- все остальные занулить, например, -- то это обеспечит оптимальную
апроксимацию из n членов. (Это вытекает из ортогональности и
упорядоченности.)
Т.о. если x[i] смещает баланс, то его должны компенсировать именно рядом
стоящие члены последовательности.
(Хотя я не вполне понимаю почему вектора согласованы по знаку.)
Чтобы исследовать это дело, я изучил статистику n-грамм из компонентов,
квантизованным по квантилям.
То есть компонент x[i] преобразовывается в целое число [-2..2], так чтобы -2
были наименьшие 20 процентов x[i], -1 -- вторые двадцать процентов и т.д.
Затем рассматриваются для всех i n-граммы {x[i], x[i+1], x[i+2], x[i+3],
x[i+4]}.
Оказывается, закономерности там есть и довольно сильные, но в плане энтропии
это почти ничего не даёт -- суммарная энтропия н-грамм всего на 5% ниже чем
суммарная энтропия по статистике x[i].
Так что я не могу даже в точности сказать, какая закономерность здесь имеет
место быть. Значительная часть этого снижения энтропии может объясняться
банально разной амплитудой векторов. Хотя, невооружённым взглядом я видел
корреляцию по знакам в статистике, но видимо она очень мало влияет на
суммарную энтропию.
Поэтому есть такой вопрос -- как можно оптимально считать n-граммы так,
чтобы наблюдать наибольшее изменение энтропии?
Я, к примеру, разбил равномерно по квантилям, но может быть имеет смысл
разбивать неравномерно, т.к. чем шире диапазон, тем меньше он информации
даёт, с одной стороны. А с другой стороны, значения вблизи нуля дают мало
информации.
При этом, я замечу, у меня довольно мало фреймов из-за громоздкости, так что
брутфорс методы -- типа, разбить по процентам, рассматривать длинные
контексты, искать в тупую корреляцию между компонентами по номерам -- не
подходят, они дадут очень большую погрешность.
6. Я наблюдаю также визуально некоторые закономерности в амплитуде x[i] в
некоторых подпоследовательностях. Т.е., например, x[25]...x[50] могут все
лежать в отрезке [-0.05..0.06], тогда как в других подпоследовательностях
отрезок шире, т.о. энтропия выше. Hо я не знаю, насколько значимая это
закономерность и как её проверить. Статистика описанная в пункте 5 частично
её может использовать, но там контекст ограничен, а здесь он намного шире.
Использовать это можно точно так же как в пункте 4, просто разбив на
подпоследовательности.
7. Если считать накопительную сумму y[i] = sum(x[j], j=0..i), то видны
определённые закономерности, но я не знаю как их можно использовать.
8. И ещё, мне не помешал бы улучшенный способ вычисления энтропии. Я сечас
считаю по простой формуле sum(-p_i*log(p_i)), и она даёт хороший результат
если p_i считать как частоту, но только в том случае, если кол-во точек
намного больше количества возможных величин.
В противном случае оценки p_i некорректны и энтропия получается смещённой.
Я читал статьи на эту тему, оказывается, там всё очень сложно и есть много
разных оценок с разными характеристиками.
Hо вот чего я не нашёл, так это относительно простой оценки с известными
характеристиками.
Есть, например, поправка имени М.-М. -- простая оценка по формуле описанной
выше смещена на (m-1)/(2*N) вниз, где m -- кол-во символов в алфавите, N --
колво наблюдаемых точек. Hо уже дисперсию или даже доверительный интервал
мне найти не удалось :(
Кроме того, я знаю как рабоче-крестьянскими методами уточнить оценку,
сгладив гистограмму -- если f[i] = 0, то f[i] = (f[i+1] + f[i-1])/2.
Hо тогда характеристики просто неизвестны...
--- ifmail v.2.15dev5.4
* Origin: Demos online service (2:5020/400)
Ответы на это письмо:
From: Username
Заголовок следующего сообщения в треде может быть длинным и его придется перенести на новую строку
From: Username
Или коротким