Фрактальное сжатие цифровых изображений

Введение

Метод сжатия цифровых изображений

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

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

Фрактальное изображение может быть математически описано как итерационная система функций (IFS). Для этого используется следующая разделенная итерационная система функций (PIFS):

Разделите область изображения на диапазонные блоки Ri размером s×s. Для каждого Ri выполните поиск по изображению, чтобы найти блок Di размером 2s×2s, который очень похож на Ri. Выберите функции отображения таким образом, чтобы H(Di) = Ri для каждого i. На втором этапе важно найти подходящий блок, чтобы IFS точно представлял входное изображение, поэтому необходимо рассмотреть достаточное количество блоков-кандидатов для Di. С другой стороны, обширный поиск по множеству блоков является вычислительно затратным. Это ограничение, связанное с поиском подобных блоков, является причиной того, что фрактальное кодирование PIFS намного медленнее, чем, например, DCT и представление изображений на основе вейвлетов. Изначальный алгоритм, основанный на квадратичном разделении и полном переборе, предложенный Жаккином, служит отправной точкой для дальнейших исследований и расширений в различных направлениях: различные способы разделения изображения на диапазонные блоки разных размеров и форм; быстрые методы для быстрого поиска достаточно близкого соответствующего доменного блока для каждого диапазонного блока, вместо полного перебора, такие как алгоритмы быстрой оценки движения; различные способы кодирования отображения из доменного блока в диапазонный блок и т.д. Другие исследователи пытаются разработать алгоритмы для автоматического кодирования произвольного изображения в виде RIFS (рекуррентных итерационных функциональных систем) или глобальных IFS, а не PIFS; а также алгоритмы для фрактального сжатия видео, включая компенсацию движения и трехмерные итерационные функциональные системы. Фрактальное сжатие изображения имеет много общего с векторной квантовым сжатием изображения.

Особенности

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

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

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

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

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

История

Майкл Барнсли возглавил разработку фрактального сжатия с 1985 года в Технологическом институте Джорджии (где Барнсли и Слоан были профессорами на математическом факультете). Работа финансировалась DARPA и исследовательской корпорацией Georgia Tech. В результате проекта в 1987 году было получено несколько патентов. Аспирант Барнсли, Арно Жаквин, реализовал первый автоматический алгоритм в программном обеспечении в 1992 году. Все методы основаны на фрактальном преобразовании с использованием итерационных функциональных систем. Майкл Барнсли и Алан Слоан основали компанию Iterated Systems Inc. в 1987 году, которой было выдано более 20 дополнительных патентов, связанных с фрактальным сжатием. Ключевым прорывом для Iterated Systems Inc. стал автоматический процесс фрактального преобразования, который устранил необходимость ручного вмешательства при сжатии, что было характерно для ранних экспериментов с технологией фрактального сжатия. В 1992 году Iterated Systems Inc. получила государственный грант в размере 2,1 миллиона долларов США на разработку прототипа чипа для хранения и декомпрессии цифровых изображений с использованием технологии фрактального сжатия изображений. Фрактальное сжатие изображений применялось в ряде коммерческих продуктов: onOne Software, разработанный по лицензии Iterated Systems Inc., и Genuine Fractals 5 – плагин для Photoshop, способный сохранять файлы в сжатом формате FIF (Fractal Image Format). На сегодняшний день наиболее успешным применением фрактального сжатия статических изображений является использование его компанией Microsoft в мультимедийной энциклопедии Encarta, также по лицензии. Iterated Systems Inc. поставляла shareware-кодировщик (Fractal Imager), автономный декодер, плагин для Netscape и пакет разработки для использования в Windows. Распространение "DLL-декомпрессора", предоставляемого ColorBox III SDK, регулировалось строгими лицензионными условиями – либо за диск, либо из года в год – для поставщиков проприетарного программного обеспечения, а также дискреционной схемой, предусматривающей продвижение продуктов Iterated Systems для определенных категорий пользователей. ClearVideo, также известный как RealVideo (Fractal) и SoftVideo, был одним из первых продуктов для сжатия видео с использованием фракталов. ClearFusion был свободно распространяемым плагином для потокового видео Iterated для веб-браузеров. В 1994 году SoftVideo был лицензирован компании Spectrum Holobyte для использования в ее CD-ROM играх, включая Falcon Gold и Star Trek: The Next Generation A Final Unity. В 1996 году Iterated Systems Inc. объявила о партнерстве с корпорацией Mitsubishi для продвижения ClearVideo среди японских клиентов. Оригинальный драйвер декодера ClearVideo 1.2 по-прежнему поддерживается Microsoft в Windows Media Player, хотя кодировщик больше не поддерживается. Две компании, Total Multimedia Inc. и Dimension, заявляют, что владеют или имеют исключительную лицензию на видеотехнологию Iterated, но ни одна из них пока не выпустила рабочий продукт. Технологической основой, по всей видимости, являются патенты Dimension в США № 8639053 и № 8351509, которые были тщательно проанализированы. В целом, это простая система копирования блоков quadtree, которая не обладает ни пропускной способностью, ни качеством PSNR традиционных кодеков на основе DCT. В январе 2016 года TMMI объявила о полном отказе от фрактальных технологий. В исследовательских работах, опубликованных в период с 1997 по 2007 год, обсуждались возможные решения для улучшения фрактальных алгоритмов и аппаратного кодирования.

Michael Barnsley led the development of fractal compression from 1985 at the Georgia Institute of Technology (where both Barnsley and Sloan were professors in the mathematics department). The work was sponsored by DARPA and the Georgia Tech Research Corporation. The project resulted in several patents from 1987. Barnsley's graduate student Arnaud Jacquin implemented the first automatic algorithm in software in 1992. All methods are based on the fractal transform using iterated function systems. Michael Barnsley and Alan Sloan formed Iterated Systems Inc. in 1987 which was granted over 20 additional patents related to fractal compression. A major breakthrough for Iterated Systems Inc. was the automatic fractal transform process which eliminated the need for human intervention during compression as was the case in early experimentation with fractal compression technology. In 1992, Iterated Systems Inc. received a US$2.1 million government grant to develop a prototype digital image storage and decompression chip using fractal transform image compression technology. Fractal image compression has been used in a number of commercial applications: onOne Software, developed under license from Iterated Systems Inc., Genuine Fractals 5 which is a Photoshop plugin capable of saving files in compressed FIF (Fractal Image Format). To date the most successful use of still fractal image compression is by Microsoft in its Encarta multimedia encyclopedia, also under license. Iterated Systems Inc. supplied a shareware encoder (Fractal Imager), a stand alone decoder, a Netscape plug in decoder and a development package for use under Windows. The redistribution of the "decompressor DLL" provided by the ColorBox III SDK was governed by restrictive per disk or year by year licensing regimes for proprietary software vendors and by a discretionary scheme that entailed the promotion of the Iterated Systems products for certain classes of other users. ClearVideo also known as RealVideo (Fractal) and SoftVideo were early fractal video compression products. ClearFusion was Iterated's freely distributed streaming video plugin for web browsers. In 1994 SoftVideo was licensed to Spectrum Holobyte for use in its CD ROM games including Falcon Gold and Star Trek: The Next Generation A Final Unity. In 1996, Iterated Systems Inc. announced an alliance with the Mitsubishi Corporation to market ClearVideo to their Japanese customers. The original ClearVideo 1.2 decoder driver is still supported by Microsoft in Windows Media Player although the encoder is no longer supported. Two firms, Total Multimedia Inc. and Dimension, both claim to own or have the exclusive licence to Iterated's video technology, but neither has yet released a working product. The technology basis appears to be Dimension's U. S. patents 8639053 and 8351509, which have been considerably analyzed. In summary, it is a simple quadtree block copying system with neither the bandwidth efficiency nor PSNR quality of traditional DCT based codecs. In January 2016, TMMI announced that it was abandoning fractal based technology altogether. Research papers between 1997 and 2007 discussed possible solutions to improve fractal algorithms and encoding hardware.

Реализация

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