Фрактальное сжатие

2 треугольника, пример, показывающий, как работает фрактальное сжатие.

Фрактальное сжатие — это сжатия метод цифровых изображений с потерями , основанный на фракталах . Этот метод лучше всего подходит для текстур и естественных изображений, поскольку части изображения часто напоминают другие части того же изображения. Фрактальные алгоритмы преобразуют эти части в математические данные, называемые «фрактальными кодами», которые используются для воссоздания закодированного изображения.

Итерированные функциональные системы

Основная статья: Итерированная система функций

Представление фрактального изображения можно математически описать как систему итерированных функций (IFS).

Для бинарных изображений

Начнем с представления двоичного изображения , где изображение можно рассматривать как подмножество $\mathbb {R} ^{2}$. IFS — это набор сжимающих отображений ƒ ₁ ,..., ƒ _N ,

$f_{i}:\mathbb {R} ^{2}\to \mathbb {R} ^{2}.$

Согласно этим функциям отображения IFS описывает двумерное множество S как неподвижную точку оператора Хатчинсона.

$H(A)=\bigcup _{i=1}^{N}f_{i}(A),\quad A\subset \mathbb {R} ^{2}.$

То есть H — оператор, отображающий множества в множества, а S — уникальный набор, удовлетворяющий ( S ) = S. H Идея состоит в том, чтобы построить IFS так, чтобы этот набор S был входным двоичным изображением. Множество S можно восстановить из IFS итерацией с точкой : для любого непустого начального множества итерация _A0 Ak + _{неподвижной 1} = H ( Ak _{компактного} сходится к S. )

Множество S самоподобно, поскольку из H ( S ) = S следует, что S является объединением отображенных копий самого себя:

$S=f_{1}(S)\cup f_{2}(S)\cup \cdots \cup f_{N}(S)$

что IFS — это фрактальное представление S. Итак, мы видим ,

Расширение оттенков серого

Представление IFS можно расширить до изображения в оттенках серого изображения , рассматривая график как подмножество изображений. $\mathbb {R} ^{3}$. Для изображения в оттенках серого u ( x , y ) рассмотрим набор S знак равно {( Икс , у , ты ( Икс , у ))}. Тогда, как и в двоичном случае, S описывается IFS с использованием набора сжимающих отображений ƒ ₁ ,..., ƒ _N , но в $\mathbb {R} ^{3}$,

$f_{i}:\mathbb {R} ^{3}\to \mathbb {R} ^{3}.$

Кодировка

Сложная проблема текущих исследований представления фрактальных изображений заключается в том, как выбрать ƒ ₁ ,..., ƒ _N так, чтобы его фиксированная точка аппроксимировала входное изображение, и как сделать это эффективно.

Простой подход для этого используется следующая система секционированных итерированных функций (PIFS):

1. Разделите область изображения на блоки диапазона R _i размера s × s .
2. Для каждого R _i выполните поиск изображения, чтобы найти блок D _i размером 2 s × 2 s , который очень похож на R _i .
3. Выберите функции отображения такие, что H ( D _i ) = R _i для каждого i .

На втором этапе важно найти аналогичный блок, чтобы IFS точно представлял входное изображение, поэтому достаточное количество блоков-кандидатов для D _i необходимо рассмотреть . С другой стороны, большой поиск с учетом множества блоков требует больших вычислительных затрат. Это узкое место в поиске похожих блоков является причиной того, что фрактальное кодирование PIFS происходит намного медленнее, чем, например, представление изображений на основе DCT и вейвлетов .

Первоначальный алгоритм разделения квадратов и перебора, представленный Жакеном, обеспечивает отправную точку для дальнейших исследований и расширений во многих возможных направлениях: различные способы разделения изображения на блоки диапазонов различных размеров и форм; быстрые методы для быстрого поиска достаточно близко совпадающего блока домена для каждого блока диапазона вместо грубого поиска, такие как оценки быстрого движения алгоритмы ; различные способы кодирования отображения блока домена в блок диапазона; и т. д.

Другие исследователи пытаются найти алгоритмы для автоматического кодирования произвольного изображения как RIFS (системы рекуррентных итерированных функций) или глобальные IFS, а не PIFS; и алгоритмы фрактального сжатия видео, включая компенсацию движения и системы трехмерных итерированных функций.

Фрактальное сжатие изображений во многом похоже на сжатие изображений векторного квантования .

Особенности

При фрактальном сжатии кодирование чрезвычайно затратно в вычислительном отношении из-за поиска самоподобий. Декодирование, однако, происходит довольно быстро. Хотя эта асимметрия до сих пор делала его непрактичным для приложений реального времени, когда видео архивируется для распространения с дискового хранилища или для загрузки файлов, фрактальное сжатие становится более конкурентоспособным.

При обычных коэффициентах сжатия, примерно до 50:1, фрактальное сжатие дает результаты, аналогичные алгоритмам на основе DCT, таким как JPEG . При высоких коэффициентах сжатия фрактальное сжатие может обеспечить превосходное качество. Для спутниковых изображений соотношение более 170:1. были достигнуты с приемлемыми результатами. Коэффициенты фрактального сжатия видео 25:1–244:1 были достигнуты за разумное время сжатия (от 2,4 до 66 с/кадр).

Эффективность сжатия увеличивается с увеличением сложности изображения и глубины цвета по сравнению с простыми в оттенках серого изображениями .

от разрешения и

Неотъемлемой особенностью фрактального сжатия является то, что изображения становятся независимыми от разрешения. после преобразования во фрактальный код. Это связано с тем, что повторяющиеся функциональные системы в сжатом файле масштабируются бесконечно. Это неопределенное свойство масштабирования фрактала известно как «фрактальное масштабирование».

Фрактальная интерполяция

Независимость разрешения фрактально-кодированного изображения можно использовать для увеличения разрешения изображения. Этот процесс также известен как «фрактальная интерполяция». При фрактальной интерполяции изображение кодируется во фрактальные коды посредством фрактального сжатия, а затем распаковывается с более высоким разрешением. использовались системы итерированных функций Результатом является изображение с повышенной дискретизацией, в котором в качестве интерполянта . Фрактальная интерполяция очень хорошо сохраняет геометрические детали по сравнению с традиционными методами интерполяции, такими как билинейная интерполяция и бикубическая интерполяция . Однако, поскольку интерполяция не может обратить вспять энтропию Шеннона, она в конечном итоге приводит к повышению резкости изображения за счет добавления случайных, а не значимых деталей. Например, невозможно увеличить изображение толпы, где лицо каждого человека состоит из одного или двух пикселей, и надеяться идентифицировать их.

История

Майкл Барнсли руководил разработкой фрактального сжатия с 1985 года в Технологическом институте Джорджии (где и Барнсли, и Слоан были профессорами математического факультета). Работу спонсировали DARPA и Технологическая исследовательская корпорация Джорджии . В результате проекта было получено несколько патентов с 1987 года. Аспирант Барнсли Арно Жакен реализовал первый автоматический алгоритм в программном обеспечении в 1992 году. Все методы основаны на фрактальном преобразовании с использованием итерированных систем функций . Майкл Барнсли и Алан Слоан основали Iterated Systems Inc. в 1987 году было получено более 20 дополнительных патентов, связанных с фрактальным сжатием.

Крупным прорывом для Iterated Systems Inc. стал процесс автоматического фрактального преобразования, который устранил необходимость вмешательства человека во время сжатия, как это было в случае ранних экспериментов с технологией фрактального сжатия. В 1992 году Itered Systems Inc. получила государственный грант в размере 2,1 миллиона долларов США. разработать прототип чипа для хранения и декомпрессии цифровых изображений с использованием технологии сжатия изображений с фрактальным преобразованием.

Фрактальное сжатие изображений использовалось в ряде коммерческих приложений: onOne Software , разработанная по лицензии Iterated Systems Inc., Genuine Fractals 5. Это плагин Photoshop , способный сохранять файлы в сжатом формате FIF (формат фрактального изображения). На сегодняшний день наиболее успешное использование фрактального сжатия неподвижных изображений реализовано компанией Microsoft в ее Encarta . мультимедийной энциклопедии тоже по лицензии.

Iterated Systems Inc. предоставила условно-бесплатный кодировщик (Fractal Imager), автономный декодер, подключаемый декодер Netscape и пакет разработки для использования под Windows. Распространение «DLL-декомпрессора», предоставляемого ColorBox III SDK, регулировалось ограничительными режимами подискового или годового лицензирования для поставщиков проприетарного программного обеспечения, а также дискреционной схемой, которая влекла за собой продвижение продуктов Iterated Systems для определенных классов. других пользователей.

ClearVideo, также известный как RealVideo (Fractal), и SoftVideo были первыми продуктами фрактального сжатия видео. ClearFusion был свободно распространяемым плагином потокового видео Iterated для веб-браузеров. получила лицензию на SoftVideo В 1994 году компания Spectrum Holobyte для использования в своих играх на компакт-дисках, включая Falcon Gold и Star Trek: The Next Generation A Final Unity .

В 1996 году компания Itered Systems Inc. объявила альянс с корпорацией Mitsubishi для продвижения ClearVideo своим японским клиентам. Исходный драйвер декодера ClearVideo 1.2 по-прежнему поддерживается. от Microsoft в проигрывателе Windows Media, хотя кодировщик больше не поддерживается.

Две фирмы, Total Multimedia Inc. и Dimension, заявляют, что владеют или имеют исключительную лицензию на видеотехнологию Iterated, но ни одна из них еще не выпустила рабочий продукт. В основе технологии лежат патенты США 8639053 и 8351509 компании Dimension, которые подверглись тщательному анализу. Подводя итог, можно сказать, что это простая система копирования блоков квадрантов, не обладающая ни эффективностью использования полосы пропускания, ни качеством PSNR традиционных кодеков на основе DCT. В январе 2016 года TMMI объявила, что полностью отказывается от фрактальной технологии.

В исследовательских работах, опубликованных в период с 1997 по 2007 год, обсуждались возможные решения по улучшению фрактальных алгоритмов и аппаратного обеспечения кодирования.

Реализации

Библиотеку под названием Фиаско создал Ульрих Хафнер. В 2001 году Fiasco был освещен в Linux Journal . Согласно руководству Fiasco 2000-04 , Fiasco можно использовать для сжатия видео. Библиотека Netpbm включает библиотеку Fiasco .

Фемтософт разработала реализацию фрактального сжатия изображений в Object Pascal и Java .

См. также

• Итерированная система функций
• Сжатие изображения
• Вейвлет

Внешние ссылки

• Пульчини и Компрессор Веррандо.
• Степень магистра наук Кейта Хауэлла 1993 г. диссертация «Фрактальное сжатие изображений для космических транспьютеров»
• Моя главная проблема: фрактальное сжатие , ноябрь 1993 г., Wired.
• Fractal Basics на FileFormat.Info Описание
• Сайт Superfractals, посвященный фракталам изобретателя фрактального сжатия.