В данной публикации я хотел бы представить ряд идей и опыт практического воплощения элемента теории Хаоса — фрактального преобразования в проекте разработке нового алгоритма сжатия аудио данных.
Чего вы не найдёте здесь:
Что вы найдёте здесь:
Думаю, что для большинства читателей этой публикации данная задача покажется странной. Обычно, понятие фрактала связывают с красивыми картинками — результатами выполнения фрактальных преобразований, именуемыми также фрактальными (или «странными») аттракторами. Однако, внимательное изучение фрактальных преобразований позволяет понять, что фракталы это не только красивые изображения. Фрактальные преобразования определяют проекции элементов в замкнутом множестве. Таким множествами могут быть цветные точки в 2.5 D пространстве, набор точек на 2 D плоскости, или набор дискретных выборок аудио потока в 1.5 D пространстве.
Я заинтересовался фрактальными преобразованиями с момента написания диссертации на соискания степени кандидата технических наук. Тема диссертации была — «Алгоритмы сокращения вычислительной сложности фрактального анализа в системах обработки визуальных данных». Диссертация была с успехом защищена и принята к публикации LAP LAMBERT Academic Publishing. Иногда встречаю ссылки на неё на сайтах Amazon и Ozon.
Я потратил много времени на изучение как теоретических основ, так и практических результатов исследований фрактальных преобразований и обнаружил только две попытки развития фрактальных преобразований до уровня индустриальных стандартов:
Однако, данные попытки не привели к значительному успеху. Причиной провалов послужила значительная вычислительная сложность.
Построение изображений на основе фрактальных преобразований не представляет математической сложности. Известный фрактал (фрактальное множество) Манделброта строится исходя из следующего преобразования:
Z(n+1) = Zn^2 + C where n = 1, 2, 3,…
Таким образом, очень сложная визуализация может быть достигнута очень простым выражением. Это приводит к следующему вопросу — возможно ли построить реальное изображение посредством фрактального преобразования? Данный вопрос был разрешён утвердительно. Более точно, можно найти такое фрактальное преобразование, которое способно построить изображение с искажениями меньшем или равными любому предопределённому значению. Это означает, что сгенерированное изображение может отличаться от оригинального на величину, неотличимую зрителем благодаря избыточности визуальной информации изображения. Таким образом, фрактальное кодирование изображения является технологией обработки изображения с потерей качества.
В книге — Amazon или Ozon можно найти точное доказательства применимости фрактального преобразования к задачам обработки изображений – теорема «Коллажа» Майкла Брансли.
Вы можете спросить – как выполнить фрактальное кодирование (или более точно – фрактальный анализ)? Визуализация фрактального множества Мандельброта весьма впечатляет, но оно было разработано после многих лет исследований. Попытка найти подходящее фрактальное преобразование путём простого перебора бесперспективна. Решение данной проблемы было предложено Майклом Брансли и его аспирантами (Майклом Брансли в дальнейшем основал Iterated Systems Incorporated). Они предложили блочную схему фрактального преобразования. С точки зрения выполнения фрактальных преобразований не существует различий в применимости фрактальных преобразований к множеству точек или к множеству блоков точек — partitioned iterated function systems (PIFS). Подобная схема базируется на извлечении копии точек из одной части множества точек, применении преобразований к копии и вставка результат в другую часть множества – это отличает данный подход от фрактальных преобразований для отдельных точек. PIFS схему можно представить в следующем виде:
где F – оригинальное множество точек, D и R множества областей точек из F,
— преобразование одной области из множества D и область множества R. Множества и определяют искомые фрактальные преобразования. Важно отметить, что если фрактальное преобразование для фрактального множества Мандельброта базируется на одном уравнении фрактального преобразования и идеи глобального самоподобия (то есть подобие всего множества любой его части), то PIFS схема базируется на группе фрактальных преобразований и идеи локальном подобии отдельных областей множества.
Вы можете спросить – как это относится к реальным изображениям? На реальных изображениях маловероятно найти глобальное самоподобие, но возможно установить подобие между разными областями реального изображения при условии допустимого отклонения. Если результирующий объём памяти для хранения системы уравнений фрактальных преобразований меньше объёма памяти для хранения оригинального изображения – то получается сжатие изображения с потерями. Данный подход обработки изображений отличается от классической идеи линейной интерполяции сигналов.
Для понимания данного различия требуется обратить внимание на три главных свойства фрактальных преобразований:
По аналогии с фрактальным преобразованием множества Манделброта, PIFS преобразование для реальных изображений можно представит в следующем виде:
где – преобразование в пространстве точек изображения, 
– сжимающее преобразование вектора с длинной 
в вектор с длинной 
, но что означают переменные 
и 
? Переменные и описывают преобразование на плоскости, но каждая точка реального изображения имеет специальное значение – интенсивность собственной яркости которая должна быть рассмотрена как часть пространства фрактального преобразования: – сжимающее преобразование яркости и – смещение интенсивности яркости (по аналогии уравнении прямой – f(y) = y*s+o).
Что делать с этом уравнением? Очень просто – выполнить данное выражение для всех групп преобразований (, , , ) что должно заполнить множество R, заполняющее все изображение F. И ещё раз, и ещё раз (рекурсивное выполнение), до бесконечности. В реальности, всё намного проще – после каждого рекурсивного выполнения итерации синтеза фрактального множества расстояние между точками уменьшается (сжимающее свойство фрактального преобразования), но если для аналитического пространства нет ограничений в делимости, то для дискретного пространства цифровых изображений новые точки будут попадать в отсечённое пространство между соседними выборками. Это случится после рекурсивных итераций PIFS.
Ожидаемый вопрос – как найти упомянутые коэффициенты, , для системы фрактальных преобразований? Задача подобного поиска может быть автоматизирована исходя из следующего уравнения:
задача поиска заключается в поиске пары
, которая минимизирует длину вектора отклонения 
. Если установить экстремальное значение допустимого отклонения равное 0, то можно вывести следующие приближения для и :
Данные выражения позволяют рассчитать оптимальные значения и , но неизвестными переменными остаются и пары . К сожалению, на настоящий момент отсутствуют аналитические решения для этих переменных – остаётся только задавать множества и пар , и перебирать их комбинации для минимизации уравнения:
Для эффективной минимизации требуется задавать большие диапазоны значений множества и пар , что ведёт к «комбинаторному взрыву» – необходимости к перебору сотен тысяч всевозможных комбинаций, на что требуется часы работы компьютерного процессора. Именно эта проблема и не позволяет перейти фрактальному анализу изображений из области экзотических исследований в сферу индустриальных стандартов.
Предвижу вопрос – всё выше описанное интересно, но причём тут звук и сжатие звуковых данных? Я полагаю многие уже поняли, что для фрактального анализа природа множеств не имеет значения – множество пикселей на плоскости или множество выборок из звукового потока. Если накапливать выборки входного звукового потока в буфере и затем обрабатывать их как отдельные множества, то можно сформировать систем фрактальных преобразований, из которых можно синтезировать фрактальные множества, приближённые к оригинальным выборкам звукового потока. Что и было реализованно в моём проекте, который включает кодер ROAD и декодер (в форме плагина для Winamp) — тестовые аудио файлы: Origa — Inner Universe 4Samples.road.wav и Alpha — Revolution in Paradise 4Samples.road.wav. Новый алгоритм сжатия звуковых данных позволил разработать формат с пятью уникальными свойствами:
Многие математические концепции имеют физические интерпретации. К примеру –
и окружность круга или натуральный логарифм и спиральная раковина моллюска. Часто указывают на связь фрактальных множеств с ростом кристалов или деревьев. Однако я бы хотел бы представить мою собственную интерпретацию фрактальных преобразований.
Я предлагаю рассмотреть базовое выражение фрактального преобразования PIFS:
Данное выражение можно представить в виде следующей схемы:
Учитывая тот факт, что указанное выражение описывает операции с векторами, рассмотрим схему операций над каждым элементом вектора:
Я полагаю что многие читатели увидят схожесть данной схемы со схемой искусственного нейрона:
преобразования и можно рассматривать как функцию сложения по входу, – чувствительность искусственного нейрона по входу, – уровень смещения — возбуждения искусственного нейрона. Внимательный читатель может указать, что чувствительность искусственного нейрона определяется для каждого входа, в то время как определяется как скаляр для всех входов. Также читатель укажет на необходимость на выходе функции для определения состояния искусственного нейрона в терминах Бинарной (Булевой) логики: активен или неактивен. Но являются ли такие требования важными? Допустимо ли, что бы чувствительность искусственного нейрона для всех входов была одинакова? Да, существуют алгоритмы обучения искусственных нейронных сетей с подобным правилом. Допустимо ли не бинарное значение на выходе искусственного нейрона? В начале развития теории искусственных нейронных сетей, когда схемы строились на транзисторах, конденсаторах и резисторах, и от них требовалось решать несложные задачи из области распознавания – к примеру распознавание почтовых индексов на почтовых конвертах и открытках с помощью перцептрона. Но с развитием нечёткой логики и открытием преимуществ «нечётких решений» (soft decisions) над «чёткими решениями» (hard decisions) необходимость подобной функции можно поставит под сомнение.
Что же получиться, если взглянуть на фрактальные преобразования с точки зрения теории искусственных нейронных сетей? Каждые элемент вектора
может быть рассмотрен как один искусственный нейрон. В этом случае векторе может быть рассмотрен как слой искусственных нейронов с общими свойствами. Однако, таких «слоёв» может быть несколько тысяч для небольшого изображения. Преобразование на плоскости может быть интерпретировано как трассировка связей между искусственными нейронами. Искусственная нейронная сеть с трассировкой связей–топологии между слоями искусственных нейронов для каждой индивидуальной задачи – звучит весьма необычно, не так ли? Какими особенностями могут могут обладать подобные искусственные нейронные сети:
Как можно назвать подобную искусственную нейронную сеть – рекурсивная, масштабируемая, асинхронная, не детерминированная искусственная нейронная сеть с трассировкой топологии и «мягким» решением. Интересным фактом является то, что уже существует искусственная нейронная сеть с подобными свойствами — искусственная нейронная сеть Хопфилда. Эта искусственная нейронная сеть Хопфилда также рекурсивна, также сходиться к устойчивому состоянию и может быть асинхронна. Однако она включает один слой, не включает трассировку топологии и не формирует «мягкое» решение. Интересно то, что фрактальные преобразования, как и искусственная нейронная сеть Хопфилда обладают общими свойствами фильтрации – восстановления повреждённых образов (конечно, фрактальные преобразования могут работать с реальными изображениями):
Вы можете видеть, что после удаления нескольких элементов фрактальные преобразования могут построить изображение, близкое к исходному после одной итерации. Однако изображение «Роза», которое сильно отличается от оригинального создаёт, весьма хаотичное распределение интенсивности пикселей. Это вполне соответствует свойству фильтрации – восстановления повреждённых образов.
На этом можно закончить данную статью. Надеюсь, высказанные идеи обратят ваше внимание на экзотическую область фрактальных преобразований.
Чего вы не найдёте здесь:
- Сложных уравнений. Цель данной публикации является представление идей и видение задачи. И как любое видение оно во многом абстрактно;
- Каких либо генераторов фрактальных изображений. Такие изображения выглядят интересно, но мня интересуют реальные задачи.
Что вы найдёте здесь:
- Краткий обзор применения фрактальных преобразований к задаче сжатия данных с потерями;
- Необычная интерпретация фрактальных преобразований;
- Ссылки на реальный код компрессора и декомпрессора аудио данных посредством фрактальных преобразований (декомпрессор представлен в форме плагина для аудио плейера Winamp);
- Описание нового формата для хранения сжатых аудио данных с пятью уникальными свойствами, отличающими новый формат от многих хорошо известных индустриальных аудио форматов.
Думаю, что для большинства читателей этой публикации данная задача покажется странной. Обычно, понятие фрактала связывают с красивыми картинками — результатами выполнения фрактальных преобразований, именуемыми также фрактальными (или «странными») аттракторами. Однако, внимательное изучение фрактальных преобразований позволяет понять, что фракталы это не только красивые изображения. Фрактальные преобразования определяют проекции элементов в замкнутом множестве. Таким множествами могут быть цветные точки в 2.5 D пространстве, набор точек на 2 D плоскости, или набор дискретных выборок аудио потока в 1.5 D пространстве.
Я заинтересовался фрактальными преобразованиями с момента написания диссертации на соискания степени кандидата технических наук. Тема диссертации была — «Алгоритмы сокращения вычислительной сложности фрактального анализа в системах обработки визуальных данных». Диссертация была с успехом защищена и принята к публикации LAP LAMBERT Academic Publishing. Иногда встречаю ссылки на неё на сайтах Amazon и Ozon.
Я потратил много времени на изучение как теоретических основ, так и практических результатов исследований фрактальных преобразований и обнаружил только две попытки развития фрактальных преобразований до уровня индустриальных стандартов:
- Video codec — 'ClearVideo' by company Iterated System Incorporated.
- Image/video codec — 'FIASCO' by Ullrich Hafner.
Однако, данные попытки не привели к значительному успеху. Причиной провалов послужила значительная вычислительная сложность.
Математические основы
Построение изображений на основе фрактальных преобразований не представляет математической сложности. Известный фрактал (фрактальное множество) Манделброта строится исходя из следующего преобразования:
Z(n+1) = Zn^2 + C where n = 1, 2, 3,…
Таким образом, очень сложная визуализация может быть достигнута очень простым выражением. Это приводит к следующему вопросу — возможно ли построить реальное изображение посредством фрактального преобразования? Данный вопрос был разрешён утвердительно. Более точно, можно найти такое фрактальное преобразование, которое способно построить изображение с искажениями меньшем или равными любому предопределённому значению. Это означает, что сгенерированное изображение может отличаться от оригинального на величину, неотличимую зрителем благодаря избыточности визуальной информации изображения. Таким образом, фрактальное кодирование изображения является технологией обработки изображения с потерей качества.
В книге — Amazon или Ozon можно найти точное доказательства применимости фрактального преобразования к задачам обработки изображений – теорема «Коллажа» Майкла Брансли.
PIFS
Вы можете спросить – как выполнить фрактальное кодирование (или более точно – фрактальный анализ)? Визуализация фрактального множества Мандельброта весьма впечатляет, но оно было разработано после многих лет исследований. Попытка найти подходящее фрактальное преобразование путём простого перебора бесперспективна. Решение данной проблемы было предложено Майклом Брансли и его аспирантами (Майклом Брансли в дальнейшем основал Iterated Systems Incorporated). Они предложили блочную схему фрактального преобразования. С точки зрения выполнения фрактальных преобразований не существует различий в применимости фрактальных преобразований к множеству точек или к множеству блоков точек — partitioned iterated function systems (PIFS). Подобная схема базируется на извлечении копии точек из одной части множества точек, применении преобразований к копии и вставка результат в другую часть множества – это отличает данный подход от фрактальных преобразований для отдельных точек. PIFS схему можно представить в следующем виде:
где F – оригинальное множество точек, D и R множества областей точек из F,
— преобразование одной области из множества D и область множества R. Множества и определяют искомые фрактальные преобразования. Важно отметить, что если фрактальное преобразование для фрактального множества Мандельброта базируется на одном уравнении фрактального преобразования и идеи глобального самоподобия (то есть подобие всего множества любой его части), то PIFS схема базируется на группе фрактальных преобразований и идеи локальном подобии отдельных областей множества. Вы можете спросить – как это относится к реальным изображениям? На реальных изображениях маловероятно найти глобальное самоподобие, но возможно установить подобие между разными областями реального изображения при условии допустимого отклонения. Если результирующий объём памяти для хранения системы уравнений фрактальных преобразований меньше объёма памяти для хранения оригинального изображения – то получается сжатие изображения с потерями. Данный подход обработки изображений отличается от классической идеи линейной интерполяции сигналов.
Для понимания данного различия требуется обратить внимание на три главных свойства фрактальных преобразований:
- фрактальное преобразование является рекурсивным – оно основано на идее неограниченного применении данного преобразования к множеству;
- фрактальное преобразование является сжимающим – это значит, результат всегда меньше оригинала;
- пространство фрактальное преобразование компактно – все преобразования над множеством отражается на само множество (самоподобие).
По аналогии с фрактальным преобразованием множества Манделброта, PIFS преобразование для реальных изображений можно представит в следующем виде:
где
– преобразование в пространстве точек изображения, – сжимающее преобразование вектора с длинной в вектор с длинной , но что означают переменные и ? Переменные и описывают преобразование на плоскости, но каждая точка реального изображения имеет специальное значение – интенсивность собственной яркости которая должна быть рассмотрена как часть пространства фрактального преобразования: – сжимающее преобразование яркости и – смещение интенсивности яркости (по аналогии уравнении прямой – f(y) = y*s+o). Что делать с этом уравнением? Очень просто – выполнить данное выражение для всех групп преобразований (
, , , ) что должно заполнить множество R, заполняющее все изображение F. И ещё раз, и ещё раз (рекурсивное выполнение), до бесконечности. В реальности, всё намного проще – после каждого рекурсивного выполнения итерации синтеза фрактального множества расстояние между точками уменьшается (сжимающее свойство фрактального преобразования), но если для аналитического пространства нет ограничений в делимости, то для дискретного пространства цифровых изображений новые точки будут попадать в отсечённое пространство между соседними выборками. Это случится после рекурсивных итераций PIFS. Ожидаемый вопрос – как найти упомянутые коэффициенты
, , для системы фрактальных преобразований? Задача подобного поиска может быть автоматизирована исходя из следующего уравнения:задача поиска заключается в поиске пары
, которая минимизирует длину вектора отклонения . Если установить экстремальное значение допустимого отклонения равное 0, то можно вывести следующие приближения для и : Данные выражения позволяют рассчитать оптимальные значения
и , но неизвестными переменными остаются и пары . К сожалению, на настоящий момент отсутствуют аналитические решения для этих переменных – остаётся только задавать множества и пар , и перебирать их комбинации для минимизации уравнения:Для эффективной минимизации требуется задавать большие диапазоны значений множества
и пар , что ведёт к «комбинаторному взрыву» – необходимости к перебору сотен тысяч всевозможных комбинаций, на что требуется часы работы компьютерного процессора. Именно эта проблема и не позволяет перейти фрактальному анализу изображений из области экзотических исследований в сферу индустриальных стандартов.Аудио
Предвижу вопрос – всё выше описанное интересно, но причём тут звук и сжатие звуковых данных? Я полагаю многие уже поняли, что для фрактального анализа природа множеств не имеет значения – множество пикселей на плоскости или множество выборок из звукового потока. Если накапливать выборки входного звукового потока в буфере и затем обрабатывать их как отдельные множества, то можно сформировать систем фрактальных преобразований, из которых можно синтезировать фрактальные множества, приближённые к оригинальным выборкам звукового потока. Что и было реализованно в моём проекте, который включает кодер ROAD и декодер (в форме плагина для Winamp) — тестовые аудио файлы: Origa — Inner Universe 4Samples.road.wav и Alpha — Revolution in Paradise 4Samples.road.wav. Новый алгоритм сжатия звуковых данных позволил разработать формат с пятью уникальными свойствами:
- Предпрослушивание. Данный термин звучит странно, но я решил использовать его по аналогии с термином «Предпросмотр» из описания формата сжатия изображения JPEG2000. Но что это может значить для аудио файла? Если взглянуть на выражение для расчёта коэффициента , то можно увидеть что оно рассчитывается на основе усреднения значений соседних выборок. В результате, через подстановку можно получить следующее выражение:
Это выражение показывает важный факт – часть коэффициентов фрактальных преобразований можно рассматривать как усреднённое значение пикселей изображения или выборок звукового потока. Это значение является «точкой роста» фрактального множества. Фрактальные преобразования нуждаются в подобных точках. Однако, при использовании PIFS для анализа звуковых данных можно ограничить размеры областей в 4 точки–выборки – это позволяет получить усреднённый звуковой поток в низкочастотной области (к примеру для оригинальной частоты звукового потока в 48000 Гц, усреднённый поток имеет частоту в 12000 Гц). В результате, сжатый поток можно прослушать с ухудшенным качеством без декодирования. Полагаю что данное свойство можно определить как «Предпрослушивание».
- Частичная совместимость. Из возможности организации отдельного низкочастотного потока звуковых данных из коэффициентов фрактальных преобразований возникает вопрос – как это реализовать? Можно резервировать отдельный участок потока данных, но факт что данный поток является несжатым потоком данных, приводит к идее, что данный поток может быть дополнительно сжат другим алгоритмом и упакован в известный индустриальный формат. В этом случае файл может быть воспроизведён в аудио проигрывателе, совместимым с индустриальным форматом с ухудшенным качеством. Данную идею можно реализовать в форме стека компрессоров. В моём проекте был выбран формат WAVE от Майкрософт. Этот формат не включает сжатие, но позволяет на практике реализовать стек форматов и частичную совместимость:
- Разгон. Идея данного свойства заключается в увеличении частоты декодированного аудио потока. Понять идею реализации данного свойства можно если рассмотреть почему данное свойство невозможно реализовать во многих индустриальных форматах. К примеру рассмотри формат mp3 – при попытке удвоения частоты декодированного аудио потока требуется увеличить базис обратного дискретно-косинусного преобразования с 128 до 256, но сжатые данные включают данные только для 128. Это приводит к проблеме неполноты базиса ортогонального преобразования. Подобная проблема возникает и с форматами на основе линейного предсказания. Однако, для фрактального анализа дело обстоит иначе. Рассмотренные ранее коэффициенты , , не связаны с размером базиса преобразования: и – скаляры интенсивности, – преобразование в пространстве – смещение, отражение и т.п… Близкой аналогией являются растровые и векторные форматы изображений: если в растровых форматах предполагается наличие одного аппроксимирующего базиса и исследуется его реакция на дискретное изображение, то в векторных форматах изображение синтезируется из системы уравнений. По аналогии, большинство индустриальных форматов сжатия звуковых данных исследуют реакцию аппроксимирующего базиса на входные звуковые данные и при декодировании восстанавливают звуковые данные по реакции из принципа обратимости аппроксимирующего базиса с конечной импульсной характеристикой. В тоже время, как фрактальный аппроксимирующий базис является рекурсивным с бесконечной импульсной характеристикой, синтезирующий результирующее фрактальное множество. Это важное отличие – коэффициенты , , определяют уравнения PIFS. В результате, возможно выбирать размер базиса и синтезировать больше выборок звукового потока в единицу времени чем было в оригинальном звуковом потоке. Подобный результат можно наблюдать при масштабировании векторных форматов изображений. Данное свойство реализовано в плагине для Winamp.
- Расширение динамического диапазона. Это логичное продолжение свойства увеличения частоты декодированного звукового потока – при увеличении разрядности потока с 16 бит до 32 бит новые выборки звукового потока будут синтезированы в расширенном диапазоне.
- Недетерминированное декодирование. Система PIFS предполагает множество фрактальных преобразований устанавливающих локальные подобия. Исходя из ранее рассмотренных выражений можно сделать вывод, что каждое из множества фрактальных преобразований может быть выполнено независимо, но возникает вопрос – в каком порядке их следует выполнять? Логично выполнять в порядке, в котором был проведён фрактальный анализ, но данное заключение ошибочно – каждое фрактальное преобразование эквивалентно любому другому из множества. Данная идея выражена в реализации выбора очередного фрактального преобразования генератором случайных чисел. Для большинства индустриальных форматов обратимость алгоритмов сжатия является главным требованием, но фрактальные преобразования избавлены от подобного условия.
Интерпретация
Многие математические концепции имеют физические интерпретации. К примеру –
и окружность круга или натуральный логарифм и спиральная раковина моллюска. Часто указывают на связь фрактальных множеств с ростом кристалов или деревьев. Однако я бы хотел бы представить мою собственную интерпретацию фрактальных преобразований. Я предлагаю рассмотреть базовое выражение фрактального преобразования PIFS:
Данное выражение можно представить в виде следующей схемы:
Учитывая тот факт, что указанное выражение описывает операции с векторами, рассмотрим схему операций над каждым элементом вектора:
Я полагаю что многие читатели увидят схожесть данной схемы со схемой искусственного нейрона:
преобразования
и можно рассматривать как функцию сложения по входу, – чувствительность искусственного нейрона по входу, – уровень смещения — возбуждения искусственного нейрона. Внимательный читатель может указать, что чувствительность искусственного нейрона определяется для каждого входа, в то время как определяется как скаляр для всех входов. Также читатель укажет на необходимость на выходе функции для определения состояния искусственного нейрона в терминах Бинарной (Булевой) логики: активен или неактивен. Но являются ли такие требования важными? Допустимо ли, что бы чувствительность искусственного нейрона для всех входов была одинакова? Да, существуют алгоритмы обучения искусственных нейронных сетей с подобным правилом. Допустимо ли не бинарное значение на выходе искусственного нейрона? В начале развития теории искусственных нейронных сетей, когда схемы строились на транзисторах, конденсаторах и резисторах, и от них требовалось решать несложные задачи из области распознавания – к примеру распознавание почтовых индексов на почтовых конвертах и открытках с помощью перцептрона. Но с развитием нечёткой логики и открытием преимуществ «нечётких решений» (soft decisions) над «чёткими решениями» (hard decisions) необходимость подобной функции можно поставит под сомнение. Что же получиться, если взглянуть на фрактальные преобразования с точки зрения теории искусственных нейронных сетей? Каждые элемент вектора
может быть рассмотрен как один искусственный нейрон. В этом случае векторе может быть рассмотрен как слой искусственных нейронов с общими свойствами. Однако, таких «слоёв» может быть несколько тысяч для небольшого изображения. Преобразование на плоскости может быть интерпретировано как трассировка связей между искусственными нейронами. Искусственная нейронная сеть с трассировкой связей–топологии между слоями искусственных нейронов для каждой индивидуальной задачи – звучит весьма необычно, не так ли? Какими особенностями могут могут обладать подобные искусственные нейронные сети:- Рекурсивность – результат работы искусственной нейронной сети становится входными данными для неё самой до установления равновесного состояния – называемого для фрактальных преобразований «аттрактором».
- Спиральная топология – условие локального самоподобия.
- Случайный выбор последовательности выполнения преобразований — слоёв.
- Предпрослушивание – возможность установки исходного уровня искусственной нейронной сети из реального источника: изображение или звук низкого качества.
- Разгон – простое масштабирование существующей искусственной нейронной сети путём добавления или удаления искусственных нейронов из каждого слоя без необходимости пересчёта конфигурации искусственной нейронной сети. Это позволяет создавать более детальное состояние сети с генерацией новых деталей.
Как можно назвать подобную искусственную нейронную сеть – рекурсивная, масштабируемая, асинхронная, не детерминированная искусственная нейронная сеть с трассировкой топологии и «мягким» решением. Интересным фактом является то, что уже существует искусственная нейронная сеть с подобными свойствами — искусственная нейронная сеть Хопфилда. Эта искусственная нейронная сеть Хопфилда также рекурсивна, также сходиться к устойчивому состоянию и может быть асинхронна. Однако она включает один слой, не включает трассировку топологии и не формирует «мягкое» решение. Интересно то, что фрактальные преобразования, как и искусственная нейронная сеть Хопфилда обладают общими свойствами фильтрации – восстановления повреждённых образов (конечно, фрактальные преобразования могут работать с реальными изображениями):
Вы можете видеть, что после удаления нескольких элементов фрактальные преобразования могут построить изображение, близкое к исходному после одной итерации. Однако изображение «Роза», которое сильно отличается от оригинального создаёт, весьма хаотичное распределение интенсивности пикселей. Это вполне соответствует свойству фильтрации – восстановления повреждённых образов.
Заключение
На этом можно закончить данную статью. Надеюсь, высказанные идеи обратят ваше внимание на экзотическую область фрактальных преобразований.
Поделиться с друзьями
myxo
ох уж эта манера письма, как будто вы пишете не людям, а рецензентам из акад. наук. Чтобы хоть что-то понять, пришлось читать дважды очень медленно. Но понятие разгона и расширения динамического диапазона я так и не осилил.
Это, если честно, не дает вам чести. Они публикуют всех, независимо от содержания работы =)
Xirexel
Ссылка на Amazon страницу хорошо смотрится в резюме.
Arastas
Это если Вы подаёте резюме на непрофильное направление. Если же общаетесь с профессионалами, то публикация LAP смотрится плохо.
Xirexel
Мой текущий работадатель был впечетлён ссылкой.
Vilyx
Совершенно нечитабельно. После прочтения остался неразрешённым вопрос, в чем преимущество перед аналогами? «Предпрослушивание» в прикладном мире называется «прогрессивное декодирование». Расширение динамического диапазона за пределы слышимости сомнительное достижение.
Xirexel
По вопросу «в чем преимущество перед аналогами?» — мне не известны аналогичные алгоритмы, расчитывающие уравнения по исходному аудио потоку, но по степени сжатия сравними с FLAC.
Vilyx
Простите, но не понял смысла вашей фразы
.За неимением аналогичного танка, сравниваем с бричкой.
Xirexel
Известные мне аудио форматы основаны на линейном базисе аппроксимации и сохраняют в файл реакцию базиса на входной поток, но фрактальный анализ позволяет найти уравнения, близко аппроксимирующие аудио поток. Это как разница между растровыми и векторными шрифтами.
Vilyx
Как я уже написал выше, отсутствие прямого аналога не освобождает от необходимости сравнить с другими алгоритмами сжатия. Вы смело сравнили степень сжатия с FLAC, но он сжимает без потерь, в отличие от вашего алгоритма. Даже если уровень сжатия сопоставим, то можно ли сравнивать производительности этих алгоритмов? Иначе выходит, что ваш алгоритм проигрывает по всем параметрам, кроме оригинальности.
Xirexel
Прошу, не будте таким жестоким. Представленный алгоритм отличается только оригинальностью (производительность очень и очень низкая — на кодирование 4 минутного трека требуется 2 часа!!!). Он представляет необычное инженерное приложение необычной математической концепции.
По поводу выигрыша, и проигрыша — формат FLAC имеет только одно преимущество перед другими форматами, но он популярен. В конечном счёте все решает рынок :)
Vilyx
Ни капли жестокости, обычная объективность. Чтобы алгоритм нашёл свою нишу, ему не обязательно быть популярным, достаточно обладать каким-то преимуществом, либо в производительности, либо в качестве работы. Но ваш алгоритм не обладает таковыми перед существующими аналогами. Он сжимает с потерями, значит с lossless кодеками его сравнивать нельзя, тогда надо смотреть на ogg и mp3, а с ними ваш алгоритм не может тягаться ни по времени сжатия, ни по степени.
Вероятно, ваш алгоритм мог бы заменить какой-то компонент в уже существующем алгоритме сжатия и тем самым повысить степень сжатия. Подумайте над этим.
А пока вы сделали работу just for fun.
Xirexel
Я не отрицаю что этот проект — "just for fun", как и большенство на GitHub. Это интересная инженерная задачка — применить элементы рекурсии к задаче, обычно решаемой не рекурсивными алгортмами. Идея сравнить фрактальные преобразования и искуственные нейронные сети мне показалась весьма занимательной.
Scratch
Главный вопрос — лучше ли оно MP3?
myxo
где-то в середине поста.
Xirexel
Пока формат хуже MP3. По степени сжатия сравними с FLAC.
interrupt
Ваше сравнение разгона с mp3 не понятно, у mp3 же вообще гибридный фильтрбанк (PFB + MDCT). Размер фрейма 1152 семпла, 32 subband (с децимацией), на каждое mdct преобразование остается 36 семплов. Откуда у вас 128?
Xirexel
Согласен с ошибкой о 128 семплов, но в «Salomon.D — data compression the complete reference 4th edition» — «The frequencies
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 семплами.
interrupt
Простите, но вы приводите цитату из описания психоакустического анализа для MPEG1 Layer2. В том же документе на который вы ссылаетесь несколькими страницами далее будет уже про Layer3:
Вот смотрю для подтверждения исходники Lame:
Xirexel
Согласен с вашим замечанием, но тогда как MDCT может быть быстрым? Размер базиса должен быть равен степени 2 от натурального числа — 2^N.
interrupt
Bluestein algorithm как вариант.
Xirexel
Это интересное замечание.
aamonster
Afaik не обязательно.
1. Для FFT есть эффективные алгоритмы не только для степеней двойки, но и для простых чисел и для произведения небольших простых чисел (они сложнее, чем для степени двойки) — вероятно, для MDCT они тоже есть.
2. Для небольших значений размера делаются свои алгоритмы со специфическими оптимизациями (типа учёта того, что cos(pi/4)=sin(pi/4) или что sin(pi/6)=1/2).
eugenero
Какой-то псевдо-математический язык. Или неграмотный перевод. Лучше дайте ссылки ссылка на оригинальные работы на английском языке.
Что такое длина вектора, это норма или размерность? Что означают бинарные операции «кружочек» и «звёздочка»?
Всем, кто заинтересовался, посмотрите статью 2011-го года, опубликованную здесь же, на Хабре. Там есть и ссылка на статью в трудах конференции, где есть математическое описание алгоритма. Более полный список источников есть в Википедии.
Vilyx
Обычный перепост научной статьи, не думаю, что автор ставил перед собой задачу написать грамотно и понятно, скорее чтобы выглядело «умно». Так пишут чтобы было поменьше вопросов у рецензентов или оппонентов. Чем хуже понял смысл написанного — тем меньше задаст вопросов.
Xirexel
Это статья является переписанной моей статьёй 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)"
Xirexel
Подробные математические определения вы можете найти в моей книге по ссылкам. Если вам жалко денег(всего то 5000 руб. — 100 AUD), то можете поискать в Интернете мою оригинальную диссертацию. Как я указал в начале — "В данной публикации я хотел бы представить ряд идей и опыт практического воплощения элемента теории Хаоса — фрактального преобразования в проекте разработке нового алгоритма сжатия аудио данных." Основная цель статьи — указать на связь фрактальных преобразований и искуственных нейронных сетей.
eugenero
Жалко? Ох, ЛОЛ. А ты смелый, псевдоучёный.
Vilyx
Это уже не первый случай, когда я сталкиваюсь с разработкой сомнительного качества и, на возникающие вопросы, автор отвечает предложением купить фекалию за большие деньги. Тенденция.
Xirexel
А кто вам предлагает что либо покупать? Это свободный мир Open Source.
Arastas
Мне правда интересно, а «Хаос», в Вашем прочтении, это имя собственное? Почему с заглавной?
Xirexel
С заглавной буквы для привлечения внимания. Сам термин "теория хаоса" крайне условен и связан с неустойчивостью динамических систем.
Arastas
О, не надо подробностей, я более-менее представляю, что такое хаотические системы.
Чисто в режиме занудства: привлечение внимания в названии ещё понятно, но в комментариях? Впрочем, это риторический вопрос.
Refridgerator
Извините, я не совсем понял. Вы делаете сжатие во временной области или частотной? Если временной, тогда искажения, вносимые алгоритмом, будут иметь намного более разрушительный характер. Ведь природа звука, как и механизм его восприятия, принципиально отличается от графики — ведь мы воспринимаем не мгновенные значения амплитуд как таковые, а спектральную составляющую звука (в сильно упрощённой интерпретации).
А поскольку ваш алгоритм с потерями, характер вносимых искажений намного более важен, чем время работы или степень сжатия. То, что не видно на картинке, будет ясно слышно в звуке, и наоборот — пример чего, например, является эффект Гиббса.
Xirexel
Сжатие в данном случае не совсем корретный термин. В алгоритме отсутствует сама концепция сжатия — удаления избыточности. Алгоритм НЕ включает психоакустические модели и НЕ включает удаление статистической избыточности. Алгоритм просто находит уравнения, выражаущие подобия. Сжатие получается за счёт того, что на 4 семпла по 16 бит (64 бита) алгоритм выдаёт 5 байт — 40 бит. Ядро алгоритмов сжатия с потерями изначально не формируют поток с меньшим числом бит — им требуется статистический кодер, который в данном алгоритме отсутствует. По поводу "будут иметь намного более разрушительный характер" — размер областей изменяется динамически от 32 семплов до 4 — 32/16/8/4 в зависимости от отклонения от среднего значения. Я думаю, что вы согласитесь, что во временной области аудио данные в пределах 4 семплов изменяются медленно. Конечно, особым случаем является шум и подобные ему звуки — при поиске подобия фактически оценивается корреляция разных областей. Корреляция шума близка к нулю и идентична корреляции для блоков без звука — тишины. Отклонения качества фрактального анализа от оригинального потока можно исправить путём вычисления отклонения фрактальной модели от оригинального потока.
По поводу "эффект Гиббса" — это явление характерно для востановления исходного сигнала по реакции ортогонального разложения — если часть данных была удалена или искажена, то возникает неполнота базиса. Однако, фрактальные преобразования формируют непрерывные не дифферинцируемые (аналитически) кривые (условия проекции одной области кривой в другую формирует точки разрыва первого рода). Это значит, что если в потоке есть резкие переходы значений большой амплитуды — точки разрыва первого рода, то они будут сохранены без "эффект Гиббса".
Refridgerator
Не соглашусь, потому что такая формулировка как минимум некорректна. Но дело вовсе не в этом.
Если в результате вашего алгоритма на краях областей возникают разрывы, это приведёт к появлению искажений во всей области частот, и особенно на частотах близких к частоте Найквиста. Также возможно, что полезная информация на них будет вообще полностью подавлена и подменена паразитными гармониками.
Эффект Гиббса же я упомянул прямо с противоположной целью — как искажение, которое хорошо видно графически (в jpeg) и практически не слышно в звуке — mp3.
Xirexel
Соглашусь, что рассуждения о 4 семплах интуитивны(через 2 семпла — точки можно интерполировать только прямую линию, 3 семпла — точки для кривой и 4 семпла — точки для удобства на обычной процессорной архитектуре).
Разрывы на краях областей могут возникать, если отклонения подобия будут велики. В проекте код сравнивает каждую текущую область с 1017 подобными областями. Значения разрывов крайне малы — в худшем случае 4 семпла по краям имеют усреднённое значение. Это НЕ приводит к паразитным гармоникам, потому что синтез и анализ ведутся во временной области — в таком случае понятие спектра и гармоники теряют смысл.
Refridgerator
Я вижу противоречие. Разве у вас в заголовке не написано — «Новый Алгоритм Сжатия»? Алгоритм сжатия без концепции сжатия?
Xirexel
Я ошибочно указал
Установление подобия между областями можно интерпретировать как удаление избыточности по аналогии с библиотечными алгоритмами энтропийного сжатия, однако дробность метрического пространства фрактальных преобразований наталкивается на ограничение неделимости одного семпла — каждый семпл подобен остальным и тогда возможен фрактальный анализ без потерь, но тогда на один семпл в 16 бит в алгоритме будет приходиться 5 байт — 40 бит. Эту ситуацию нельзя определить как сжатие. Однако, если определить минимальную область, на которой искуственно останавливаем делимость, равной 4 семплам, то на 4 семпла по 16 бит (64 бита) алгоритм выдаёт 5 байт — 40 бит. Это можно интерпретировать как сжатие, но с потерями. Уравнения фрактального преобразования выполняют сжатие в той-же мере, как параметрическое уравнение окружности сжимает растровое изображение окружности (по уравнению можно синтезировать растровое изображение окружности, идентичное оригинальному).
Xirexel
Прошу обратить внимание на "кривую Коха" — геометрический фрактал, который навёл меня на мысль о применения фрактальных преобразований в области звука — эта кривая похожа на осцилограмму звука.
Refridgerator
Совершенно не похоже. В осциллограмме одному значению времени соответствует только одно значение амплитуды, в то время как в кривой Коха это не так:
Xirexel
Похожа, но не эквивалентна.
В данном случае не надо прямо переносить "кривую Коха" на пространство аудио потока. Я хотел продемонстрировать применимость фрактальных преобразований 2D пространству в форме, похожей на осциллограмму. Выражение "одному значению времени соответствует только одно значение амплитуды" является только условием заполнения исходного множества — также как одному пикселю изображения соответствует одно значение яркости. Ещё раз — "одному значению времени соответствует только одно значение амплитуды" лишь условие ограничение, которое создаст фрактальное преобразование с подобным-же условием — если НЕТ семпла нарушающего подобного условия, то и фрактальное преобразование не создаст подобный семпл — данное условие будет отражено в УРАВНЕНИЯХ фрактальных преобразований.
Refridgerator
Есть ли уже скомпилированный кодер? В вашем проекте я не нашёл консольной версии, только под Qt.
Xirexel
К сожалению, проект только под Qt. Этот проект был также поводом для обновления моего старого опыта на Qt. Проект преостановлен достаточно давно.