Comments 51
принята к публикации LAP LAMBERT Academic Publishing
Это, если честно, не дает вам чести. Они публикуют всех, независимо от содержания работы =)
расчитывающие уравнения по исходному аудио потоку.
За неимением аналогичного танка, сравниваем с бричкой.
Известные мне аудио форматы основаны на линейном базисе аппроксимации и сохраняют в файл реакцию базиса на входной поток, но фрактальный анализ позволяет найти уравнения, близко аппроксимирующие аудио поток. Это как разница между растровыми и векторными шрифтами.
Прошу, не будте таким жестоким. Представленный алгоритм отличается только оригинальностью (производительность очень и очень низкая — на кодирование 4 минутного трека требуется 2 часа!!!). Он представляет необычное инженерное приложение необычной математической концепции.
По поводу выигрыша, и проигрыша — формат FLAC имеет только одно преимущество перед другими форматами, но он популярен. В конечном счёте все решает рынок :)
Вероятно, ваш алгоритм мог бы заменить какой-то компонент в уже существующем алгоритме сжатия и тем самым повысить степень сжатия. Подумайте над этим.
А пока вы сделали работу just for fun.
Я не отрицаю что этот проект — "just for fun", как и большенство на GitHub. Это интересная инженерная задачка — применить элементы рекурсии к задаче, обычно решаемой не рекурсивными алгортмами. Идея сравнить фрактальные преобразования и искуственные нейронные сети мне показалась весьма занимательной.
have to be computed from the samples. This is why the first step in MPEG audio
encoding is a discrete Fourier transform, where a set of 512 consecutive audio samples is
transformed to the frequency domain. Since the number of frequencies can be huge, they
are grouped into 32 equal-width frequency subbands (layer III uses different numbers
but the same principle).» mdct не может быть над 36 семплами.
The MDCT uses n input samples xk (where n is either 36 or 12) to obtain n/2 (i.e.,
18 or 6) transform coefficients Si
Вот смотрю для подтверждения исходники Lame:
/*-------------------------------------------------------------------*/
/* */
/* Function: Calculation of the MDCT */
/* In the case of long blocks (type 0,1,3) there are */
/* 36 coefficents in the time domain and 18 in the frequency */
/* domain. */
/* In the case of short blocks (type 2) there are 3 */
/* transformations with short length. This leads to 12 coefficents */
/* in the time and 6 in the frequency domain. In this case the */
/* results are stored side by side in the vector out[]. */
/* */
/* New layer3 */
/* */
/*-------------------------------------------------------------------*/
Согласен с вашим замечанием, но тогда как MDCT может быть быстрым? Размер базиса должен быть равен степени 2 от натурального числа — 2^N.
1. Для FFT есть эффективные алгоритмы не только для степеней двойки, но и для простых чисел и для произведения небольших простых чисел (они сложнее, чем для степени двойки) — вероятно, для MDCT они тоже есть.
2. Для небольших значений размера делаются свои алгоритмы со специфическими оптимизациями (типа учёта того, что cos(pi/4)=sin(pi/4) или что sin(pi/6)=1/2).
Что такое длина вектора, это норма или размерность? Что означают бинарные операции «кружочек» и «звёздочка»?
Всем, кто заинтересовался, посмотрите статью 2011-го года, опубликованную здесь же, на Хабре. Там есть и ссылка на статью в трудах конференции, где есть математическое описание алгоритма. Более полный список источников есть в Википедии.
Это статья является переписанной моей статьёй Applying algorithm of the Chaos Theory on development of the new technology of compression of audio data. — "Best C++ Article of October 2014 (First Prize)"
Подробные математические определения вы можете найти в моей книге по ссылкам. Если вам жалко денег(всего то 5000 руб. — 100 AUD), то можете поискать в Интернете мою оригинальную диссертацию. Как я указал в начале — "В данной публикации я хотел бы представить ряд идей и опыт практического воплощения элемента теории Хаоса — фрактального преобразования в проекте разработке нового алгоритма сжатия аудио данных." Основная цель статьи — указать на связь фрактальных преобразований и искуственных нейронных сетей.
А поскольку ваш алгоритм с потерями, характер вносимых искажений намного более важен, чем время работы или степень сжатия. То, что не видно на картинке, будет ясно слышно в звуке, и наоборот — пример чего, например, является эффект Гиббса.
Сжатие в данном случае не совсем корретный термин. В алгоритме отсутствует сама концепция сжатия — удаления избыточности. Алгоритм НЕ включает психоакустические модели и НЕ включает удаление статистической избыточности. Алгоритм просто находит уравнения, выражаущие подобия. Сжатие получается за счёт того, что на 4 семпла по 16 бит (64 бита) алгоритм выдаёт 5 байт — 40 бит. Ядро алгоритмов сжатия с потерями изначально не формируют поток с меньшим числом бит — им требуется статистический кодер, который в данном алгоритме отсутствует. По поводу "будут иметь намного более разрушительный характер" — размер областей изменяется динамически от 32 семплов до 4 — 32/16/8/4 в зависимости от отклонения от среднего значения. Я думаю, что вы согласитесь, что во временной области аудио данные в пределах 4 семплов изменяются медленно. Конечно, особым случаем является шум и подобные ему звуки — при поиске подобия фактически оценивается корреляция разных областей. Корреляция шума близка к нулю и идентична корреляции для блоков без звука — тишины. Отклонения качества фрактального анализа от оригинального потока можно исправить путём вычисления отклонения фрактальной модели от оригинального потока.
По поводу "эффект Гиббса" — это явление характерно для востановления исходного сигнала по реакции ортогонального разложения — если часть данных была удалена или искажена, то возникает неполнота базиса. Однако, фрактальные преобразования формируют непрерывные не дифферинцируемые (аналитически) кривые (условия проекции одной области кривой в другую формирует точки разрыва первого рода). Это значит, что если в потоке есть резкие переходы значений большой амплитуды — точки разрыва первого рода, то они будут сохранены без "эффект Гиббса".
Я думаю, что вы согласитесь, что во временной области аудио данные в пределах 4 семплов изменяются медленно
Не соглашусь, потому что такая формулировка как минимум некорректна. Но дело вовсе не в этом.
Если в результате вашего алгоритма на краях областей возникают разрывы, это приведёт к появлению искажений во всей области частот, и особенно на частотах близких к частоте Найквиста. Также возможно, что полезная информация на них будет вообще полностью подавлена и подменена паразитными гармониками.
Эффект Гиббса же я упомянул прямо с противоположной целью — как искажение, которое хорошо видно графически (в jpeg) и практически не слышно в звуке — mp3.
Не соглашусь, потому что такая формулировка как минимум некорректна. Но дело вовсе не в этом.
Соглашусь, что рассуждения о 4 семплах интуитивны(через 2 семпла — точки можно интерполировать только прямую линию, 3 семпла — точки для кривой и 4 семпла — точки для удобства на обычной процессорной архитектуре).
Если в результате вашего алгоритма на краях областей возникают разрывы,
Разрывы на краях областей могут возникать, если отклонения подобия будут велики. В проекте код сравнивает каждую текущую область с 1017 подобными областями. Значения разрывов крайне малы — в худшем случае 4 семпла по краям имеют усреднённое значение. Это НЕ приводит к паразитным гармоникам, потому что синтез и анализ ведутся во временной области — в таком случае понятие спектра и гармоники теряют смысл.
Сжатие в данном случае не совсем корректный термин. В алгоритме отсутствует сама концепция сжатия — удаления избыточности.
Я вижу противоречие. Разве у вас в заголовке не написано — «Новый Алгоритм Сжатия»? Алгоритм сжатия без концепции сжатия?
Я ошибочно указал
отсутствует сама концепция сжатия — удаления избыточности
Установление подобия между областями можно интерпретировать как удаление избыточности по аналогии с библиотечными алгоритмами энтропийного сжатия, однако дробность метрического пространства фрактальных преобразований наталкивается на ограничение неделимости одного семпла — каждый семпл подобен остальным и тогда возможен фрактальный анализ без потерь, но тогда на один семпл в 16 бит в алгоритме будет приходиться 5 байт — 40 бит. Эту ситуацию нельзя определить как сжатие. Однако, если определить минимальную область, на которой искуственно останавливаем делимость, равной 4 семплам, то на 4 семпла по 16 бит (64 бита) алгоритм выдаёт 5 байт — 40 бит. Это можно интерпретировать как сжатие, но с потерями. Уравнения фрактального преобразования выполняют сжатие в той-же мере, как параметрическое уравнение окружности сжимает растровое изображение окружности (по уравнению можно синтезировать растровое изображение окружности, идентичное оригинальному).
Прошу обратить внимание на "кривую Коха" — геометрический фрактал, который навёл меня на мысль о применения фрактальных преобразований в области звука — эта кривая похожа на осцилограмму звука.
Похожа, но не эквивалентна.
одному значению времени соответствует только одно значение амплитуды
В данном случае не надо прямо переносить "кривую Коха" на пространство аудио потока. Я хотел продемонстрировать применимость фрактальных преобразований 2D пространству в форме, похожей на осциллограмму. Выражение "одному значению времени соответствует только одно значение амплитуды" является только условием заполнения исходного множества — также как одному пикселю изображения соответствует одно значение яркости. Ещё раз — "одному значению времени соответствует только одно значение амплитуды" лишь условие ограничение, которое создаст фрактальное преобразование с подобным-же условием — если НЕТ семпла нарушающего подобного условия, то и фрактальное преобразование не создаст подобный семпл — данное условие будет отражено в УРАВНЕНИЯХ фрактальных преобразований.
К сожалению, проект только под Qt. Этот проект был также поводом для обновления моего старого опыта на Qt. Проект преостановлен достаточно давно.
..\..\..\..\ROAD-development\ROADcodec\ROADdecoder\Driver\DataDriver.cpp: In static member function 'static std::unique_ptr<ROADdecoder::Driver::IDataReadDriver> ROADdecoder::Driver::DataDriver::getIDataReadDriver(std::shared_ptr<unsigned char>&, PlatformDependencies::ROADUInt32, Endian::EndianType)':
..\..\..\..\ROAD-development\ROADcodec\ROADdecoder\Driver\DataDriver.cpp:12:90: error: 'std::unique_ptr<Endian::IEndianConvertor>' is an inaccessible base of 'PlatformDependencies::Unique_ptr<Endian::IEndianConvertor>'
std::unique_ptr<IDataReadDriver> result(new DataReadDriver(aData, aLength, lconvertor));
^
..\..\..\..\ROAD-development\ROADcodec\ROADdecoder\Driver\DataDriver.cpp: In static member function 'static std::unique_ptr<ROADdecoder::Driver::IDataReadDriver> ROADdecoder::Driver::DataDriver::getIDataReadDriver(ROADdecoder::Driver::DataContainer*, PlatformDependencies::ROADUInt32, Endian::EndianType)':
..\..\..\..\ROAD-development\ROADcodec\ROADdecoder\Driver\DataDriver.cpp:23:90: error: 'std::unique_ptr<Endian::IEndianConvertor>' is an inaccessible base of 'PlatformDependencies::Unique_ptr<Endian::IEndianConvertor>'
std::unique_ptr<IDataReadDriver> result(new DataReadDriver(aData, aLength, lconvertor));Я что-то не так делаю?
Почему вы не хотите выложить исполняемый файл(ы)?
Применение нелинейной динамики и теории Хаоса к задаче разработки нового алгоритма сжатия аудио данных