- PVSM.RU - https://www.pvsm.ru -
В данной публикации я хотел бы представить ряд идей и опыт практического воплощения элемента теории Хаоса — фрактального преобразования в проекте разработке нового алгоритма сжатия аудио данных.
Чего вы не найдёте здесь:
Что вы найдёте здесь:
Думаю, что для большинства читателей этой публикации данная задача покажется странной. Обычно, понятие фрактала связывают с красивыми картинками — результатами выполнения фрактальных преобразований, именуемыми также фрактальными (или «странными») аттракторами. Однако, внимательное изучение фрактальных преобразований позволяет понять, что фракталы это не только красивые изображения. Фрактальные преобразования определяют проекции элементов в замкнутом множестве. Таким множествами могут быть цветные точки в 2.5 D пространстве, набор точек на 2 D плоскости, или набор дискретных выборок аудио потока в 1.5 D пространстве.
Я заинтересовался фрактальными преобразованиями с момента написания диссертации на соискания степени кандидата технических наук. Тема диссертации была — «Алгоритмы сокращения вычислительной сложности фрактального анализа в системах обработки визуальных данных». Диссертация была с успехом защищена и принята к публикации LAP LAMBERT Academic Publishing. Иногда встречаю ссылки на неё на сайтах Amazon [1] и Ozon [2].
Я потратил много времени на изучение как теоретических основ, так и практических результатов исследований фрактальных преобразований и обнаружил только две попытки развития фрактальных преобразований до уровня индустриальных стандартов:
Однако, данные попытки не привели к значительному успеху. Причиной провалов послужила значительная вычислительная сложность.
Построение изображений на основе фрактальных преобразований не представляет математической сложности. Известный фрактал (фрактальное множество) Манделброта строится исходя из следующего преобразования:
Z(n+1) = Zn^2 + C where n = 1, 2, 3,…
Таким образом, очень сложная визуализация может быть достигнута очень простым выражением. Это приводит к следующему вопросу — возможно ли построить реальное изображение посредством фрактального преобразования? Данный вопрос был разрешён утвердительно. Более точно, можно найти такое фрактальное преобразование, которое способно построить изображение с искажениями меньшем или равными любому предопределённому значению. Это означает, что сгенерированное изображение может отличаться от оригинального на величину, неотличимую зрителем благодаря избыточности визуальной информации изображения. Таким образом, фрактальное кодирование изображения является технологией обработки изображения с потерей качества.
В книге — Amazon [1] или Ozon [2] можно найти точное доказательства применимости фрактального преобразования к задачам обработки изображений – теорема «Коллажа» Майкла Брансли.
Вы можете спросить – как выполнить фрактальное кодирование (или более точно – фрактальный анализ)? Визуализация фрактального множества Мандельброта весьма впечатляет, но оно было разработано после многих лет исследований. Попытка найти подходящее фрактальное преобразование путём простого перебора бесперспективна. Решение данной проблемы было предложено Майклом Брансли и его аспирантами (Майклом Брансли в дальнейшем основал 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 [3] и декодер [4] (в форме плагина для Winamp) — тестовые аудио файлы: Origa — Inner Universe 4Samples.road.wav [5] и Alpha — Revolution in Paradise 4Samples.road.wav [6]. Новый алгоритм сжатия звуковых данных позволил разработать формат с пятью уникальными свойствами:
Это выражение показывает важный факт – часть коэффициентов фрактальных преобразований можно рассматривать как усреднённое значение пикселей изображения или выборок звукового потока. Это значение является «точкой роста» фрактального множества. Фрактальные преобразования нуждаются в подобных точках. Однако, при использовании PIFS для анализа звуковых данных можно ограничить размеры областей в 4 точки–выборки – это позволяет получить усреднённый звуковой поток в низкочастотной области (к примеру для оригинальной частоты звукового потока в 48000 Гц, усреднённый поток имеет частоту в 12000 Гц). В результате, сжатый поток можно прослушать с ухудшенным качеством без декодирования. Полагаю что данное свойство можно определить как «Предпрослушивание».
Многие математические концепции имеют физические интерпретации. К примеру – и окружность круга или натуральный логарифм и спиральная раковина моллюска. Часто указывают на связь фрактальных множеств с ростом кристалов или деревьев. Однако я бы хотел бы представить мою собственную интерпретацию фрактальных преобразований.
Я предлагаю рассмотреть базовое выражение фрактального преобразования PIFS:
Данное выражение можно представить в виде следующей схемы:
Учитывая тот факт, что указанное выражение описывает операции с векторами, рассмотрим схему операций над каждым элементом вектора:
Я полагаю что многие читатели увидят схожесть данной схемы со схемой искусственного нейрона:
преобразования и можно рассматривать как функцию сложения по входу, – чувствительность искусственного нейрона по входу, – уровень смещения — возбуждения искусственного нейрона. Внимательный читатель может указать, что чувствительность искусственного нейрона определяется для каждого входа, в то время как определяется как скаляр для всех входов. Также читатель укажет на необходимость на выходе функции для определения состояния искусственного нейрона в терминах Бинарной (Булевой) логики: активен или неактивен. Но являются ли такие требования важными? Допустимо ли, что бы чувствительность искусственного нейрона для всех входов была одинакова? Да, существуют алгоритмы обучения искусственных нейронных сетей с подобным правилом. Допустимо ли не бинарное значение на выходе искусственного нейрона? В начале развития теории искусственных нейронных сетей, когда схемы строились на транзисторах, конденсаторах и резисторах, и от них требовалось решать несложные задачи из области распознавания – к примеру распознавание почтовых индексов на почтовых конвертах и открытках с помощью перцептрона. Но с развитием нечёткой логики и открытием преимуществ «нечётких решений» (soft decisions) над «чёткими решениями» (hard decisions) необходимость подобной функции можно поставит под сомнение.
Что же получиться, если взглянуть на фрактальные преобразования с точки зрения теории искусственных нейронных сетей? Каждые элемент вектора может быть рассмотрен как один искусственный нейрон. В этом случае векторе может быть рассмотрен как слой искусственных нейронов с общими свойствами. Однако, таких «слоёв» может быть несколько тысяч для небольшого изображения. Преобразование на плоскости может быть интерпретировано как трассировка связей между искусственными нейронами. Искусственная нейронная сеть с трассировкой связей–топологии между слоями искусственных нейронов для каждой индивидуальной задачи – звучит весьма необычно, не так ли? Какими особенностями могут могут обладать подобные искусственные нейронные сети:
Как можно назвать подобную искусственную нейронную сеть – рекурсивная, масштабируемая, асинхронная, не детерминированная искусственная нейронная сеть с трассировкой топологии и «мягким» решением. Интересным фактом является то, что уже существует искусственная нейронная сеть с подобными свойствами — искусственная нейронная сеть Хопфилда [7]. Эта искусственная нейронная сеть Хопфилда также рекурсивна, также сходиться к устойчивому состоянию и может быть асинхронна. Однако она включает один слой, не включает трассировку топологии и не формирует «мягкое» решение. Интересно то, что фрактальные преобразования, как и искусственная нейронная сеть Хопфилда обладают общими свойствами фильтрации – восстановления повреждённых образов (конечно, фрактальные преобразования могут работать с реальными изображениями):
Вы можете видеть, что после удаления нескольких элементов фрактальные преобразования могут построить изображение, близкое к исходному после одной итерации. Однако изображение «Роза», которое сильно отличается от оригинального создаёт, весьма хаотичное распределение интенсивности пикселей. Это вполне соответствует свойству фильтрации – восстановления повреждённых образов.
На этом можно закончить данную статью. Надеюсь, высказанные идеи обратят ваше внимание на экзотическую область фрактальных преобразований.
Автор: Xirexel
Источник [8]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/matematika/187060
Ссылки в тексте:
[1] Amazon: https://www.amazon.ca/Algoritmy-fraktalnogo-szhatiya-izobrazheniy-problematiki/dp/365924581X
[2] Ozon: http://www.ozon.ru/context/detail/id/31807391/
[3] ROAD: https://github.com/Xirexel/ROAD
[4] декодер: https://github.com/Xirexel/WinampPlugin_in_road
[5] Origa — Inner Universe 4Samples.road.wav: https://drive.google.com/file/d/0B9pVRwN4TMxNbkFHMHEzV1E4UTg/view?usp=sharing
[6] Alpha — Revolution in Paradise 4Samples.road.wav: https://drive.google.com/file/d/0B9pVRwN4TMxNWjZRQ3NwbGZxLWc/view?usp=sharing
[7] искусственная нейронная сеть Хопфилда: https://ru.wikipedia.org/wiki/Нейронная_сеть_Хопфилда
[8] Источник: https://habrahabr.ru/post/309906/?utm_source=habrahabr&utm_medium=rss&utm_campaign=sandbox
Нажмите здесь для печати.