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

редактировать

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

Содержание

1 Итерационные системы функций
- 1.1 Для двоичных изображений
- 1.2 Расширение до оттенков серого
- 1.3 Кодирование
2 Функции
- 2.1 Независимость разрешения и фрактальное масштабирование
- 2.2 Фрактальная интерполяция
3 История
4 Реализации
5 См. Также
6 Примечания
7 Внешние ссылки

Системы повторяющихся функций

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

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

Мы начинаем с представления двоичного изображения, где изображение можно рассматривать как подмножество $R 2 {\ displaystyle \ mathbb {R} ^ {2}}$ $\ mathbb {R} ^ {2}$ . IFS - это набор сжимающих отображений ƒ1,..., ƒ N,

f i: R 2 → R 2. {\ displaystyle f_ {i}: \ mathbb {R} ^ {2} \ to \ mathbb {R} ^ {2}.}

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

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

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

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

То есть H - оператор, отображающий множества в множества, а S - уникальный набор, удовлетворяющий H (S) = S. Идея состоит в том, чтобы построить IFS так, чтобы это множество S было входным двоичным изображением. Набор S может быть восстановлен из IFS с помощью итерации с фиксированной точкой : для любого непустого compact начального набора A 0 итерация A k + 1 = H (A k) сходится к S.

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

S знак равно е 1 (S) ∪ е 2 (S) ∪ ⋯ ∪ е N (S) {\ displaystyle S = f_ {1} (S) \ чашка f_ {2} (S) \ чашка \ cdots \ cup f_ {N} (S)}

S = f_ {1} ( S) \ чашка f_ {2} (S) \ чашка \ cdots \ cup f_ {N} (S)

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

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

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

fi: R 3 → R 3. {\ displaystyle f_ {i}: \ mathbb {R} ^ {3} \ to \ mathbb {R} ^ {3}.}

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

Кодирование

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

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

Разделите область изображения на блоки диапазона R i размером s × s.
Для каждого R i выполните поиск изображения, чтобы найти блок D i размером 2s × 2s, который очень похож на R i.
Выберите функции отображения, такие что 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 с / кадр).

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

Независимость разрешения и фрактальное масштабирование

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

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

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

История

Майкл Барнсли руководил разработкой фрактального сжатия в 1987 году и получил несколько патентов на эту технологию. Наиболее широко известный практический алгоритм фрактального сжатия был изобретен Барнсли и Аланом Слоаном. Аспирант Барнсли Арно Жакен реализовал первый автоматический алгоритм в программном обеспечении в 1992 году. Все методы основаны на фрактальном преобразовании с использованием систем повторяющихся функций. Майкл Барнсли и Алан Слоан в 1987 году основали компанию Iterated Systems Inc., которой было выдано более 20 дополнительных патентов, связанных с фрактальным сжатием.

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

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

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

В 1990-е годы Iterated Systems Inc. и ее партнеры затратили значительные ресурсы на фрактальное сжатие видео. Хотя результаты сжатия были многообещающими, компьютерному оборудованию того времени не хватало вычислительной мощности для фрактального сжатия видео, которое было бы практичным за пределами нескольких избранных применений. Для сжатия одной минуты видео требовалось до 15 часов.

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

. Iterated Systems Inc. объявила об альянсе с Mitsubishi Corporation для продвижения ClearVideo для своих японских клиентов. Исходный драйвер декодера ClearVideo 1.2 все еще поддерживается Microsoft в Windows Media Player, хотя кодировщик больше не поддерживается.

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

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

Реализации

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

Компания Femtosoft разработала реализацию сжатия фрактальных изображений в Object Pascal и Java.

См. Также

Примечания

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

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