Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
2 треугольника, пример, показывающий, как работает фрактальное сжатие

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

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

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

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

Для двоичных изображений [ править ]

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

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

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

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

Таким образом , мы видим , что МФС является фракталом представление S .

Расширение до оттенков серого [ править ]

Представление IFS можно расширить до изображения в градациях серого , рассматривая граф изображения как подмножество . Для изображения u ( x , y ) в оттенках серого рассмотрим набор S = {( x , y , u ( x , y ))}. Затем аналогично двоичном случае, S описывается КСФ с использованием набора сжимающих отображений ƒ 1 , ..., ƒ N , но в ,

Кодировка [ править ]

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

Простым подходом [2] для этого является следующая система многораздельных итеративных функций (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 и вейвлетов .

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

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

Сжатие фрактального изображения во многом похоже на сжатие изображения с векторным квантованием . [6]

Особенности [ править ]

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

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

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

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

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

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

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

История [ править ]

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

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

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

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

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

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

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

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

За последние несколько лет было опубликовано множество исследовательских работ, в которых обсуждаются возможные решения для улучшения фрактальных алгоритмов и аппаратного кодирования. [29] [30] [31] [32] [33] [34] [35] [36] [37]

Реализации [ править ]

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

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

См. Также [ править ]

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

Примечания [ править ]

  1. Перейти ↑ May, Mike (1996). «Сжатие фрактальных изображений». Американский ученый . 84 (5): 442–451. Bibcode : 1996AmSci..84..442M . JSTOR  29775747 . ProQuest 215266230 . 
  2. ^ a b Фишер, Юваль (12 августа 1992 г.). Пшемыслав Прусинкевич (ред.). Примечания к курсу SIGGRAPH'92 - Фрактальное сжатие изображений (PDF) . СИГГРАФ . Фракталы - от народного искусства к гиперреальности. ACM SIGGRAPH .
  3. ^ Саупе, Дитмар; Хамзауи, Рауф (ноябрь 1994 г.). «Обзор литературы по сжатию фрактальных изображений». ACM SIGGRAPH Компьютерная графика . 28 (4): 268–276. DOI : 10.1145 / 193234.193246 . S2CID 10489445 . 
  4. Перейти ↑ Lacroix, Bruno (1999). Сжатие фрактальных изображений (Дипломная работа). DOI : 10.22215 / ETD / 1999-04159 . OCLC 1103597126 . ProQuest 304520711 .  
  5. ^ Фишер, Юваль (2012). Сжатие фрактальных изображений: теория и применение . Springer Science & Business Media. п. 300. ISBN 978-1-4612-2472-3.
  6. ^ Генри Сяо. «Фрактальное сжатие» . 2004 г.
  7. ^ Джон Р. Дженсен, «Учебники по дистанционному зондированию» , Альтернативы сжатия изображений и аспекты хранения мультимедиа (ссылка на время сжатия / декомпрессии) , Университет Южной Каролины , заархивировано из оригинала 03.03.2008
  8. ↑ Стив Хит (23 августа 1999 г.). Мультимедиа и коммуникационные технологии . Focal Press. С. 120–123. ISBN 978-0-240-51529-8. Ссылка Focal Press
  9. ^ Сайуд, Халид (2006). Введение в сжатие данных . Эльзевир. С. 560–569. ISBN 978-0-12-620862-7.
  10. ↑ Ви Мэн Ун; Энтони Тунг Шуэн Хо; Тао Ю; Сиу Чунг Там; Сионг Чай Тан; Лиан Тек Яп (2000). «Достижение высокого сжатия данных самоподобных спутниковых снимков с помощью фракталов». IGARSS 2000. Международный симпозиум IEEE 2000 по геонаукам и дистанционному зондированию. Принимая пульс планеты: роль дистанционного зондирования в управлении окружающей средой. Труды (Кат. № 00Ч37120) . 2 . С. 609–611. DOI : 10.1109 / IGARSS.2000.861646 . ISBN 0-7803-6359-0. S2CID  14516581 .
  11. Перейти ↑ Fisher, Y. (июль 1995 г.). Фрактальное кодирование видеопоследовательностей . Кодирование и анализ фрактальных изображений. Тронхейм. ИНИСТ : 1572685 .
  12. ↑ Walking, Talking Web. Архивировано 6 января 2008 г. встатье журнала Wayback Machine Byte Magazine о фрактальном сжатии и независимости разрешения.
  13. ^ Хэ, Чуань-цзян; Ли, Гао-пин; Шэнь, Сяо-на (май 2007 г.). «Метод интерполяционного декодирования с переменными параметрами для сжатия фрактальных изображений». Хаос, солитоны и фракталы . 32 (4): 1429–1439. Bibcode : 2007CSF .... 32.1429H . DOI : 10.1016 / j.chaos.2005.11.058 .
  14. ^ Наваскес, MA; Себастьян, М.В. (2006). «Гладкая фрактальная интерполяция». Журнал неравенств и приложений . 2006 : 1–20. DOI : 10.1155 / JIA / 2006/78734 . S2CID 20352406 . 
  15. ^ Уэмура, Сатоши; Хасеяма, Мики; Китадзима, Хидео (28 января 2003 г.). «EFIF を 用 い た 自己 フ ン ク タ ル 形 拡 大 処理 に 関 す る» [Замечание о технике расширения самоаффинных фрактальных объектов с использованием расширенных функций фрактальной интерполяции]. Технический отчет IEICE (на японском языке). 102 (630): 95–100. DOI : 10.11485 / itetr.27.9.0_95 . NAID 110003171506 . 
  16. ^ Курода, Хидео; Ху, Сяотун; Фудзимура, Макото (1 февраля 2003 г.). «ラ ク タ ル 画像 ス ケ ー リ ン グ フ タ に 関 す» [Исследования по коэффициенту масштабирования для кодирования фрактальных изображений]. Труды Института инженеров электроники, информации и связи (на японском языке). 86 (2): 359–363. NAID 110003170896 . 
  17. ^ Патент США 4941193  - Барнсли и первый Слоана итерированным система функция патент, поданной в октябре 1987 года
  18. ^ Использование фрактального кодирования для индексации содержимого изображения для технического отчета цифровой библиотеки
  19. ^ Jacquin, AE (1992). «Кодирование изображений на основе фрактальной теории повторяющихся сжимающих преобразований изображений». IEEE Transactions по обработке изображений . 1 (1): 18–30. Bibcode : 1992ITIP .... 1 ... 18J . CiteSeerX 10.1.1.456.1530 . DOI : 10.1109 / 83.128028 . PMID 18296137 .  
  20. ^ Iterated Systems Inc. изменила свое название на MediaBin Inc. Inc. в 2001 году и, в свою очередь, была выкуплена Interwoven, Inc. в 2003 году)
  21. ^ NIST SP950-3, «Сбор и интеграция медицинской информации о пациентах для улучшения доступности»; см. стр. 36, «Технология на основе фракталов MediaBin для сжатия файлов цифровых изображений». Архивировано 23 сентября 2015 г. в Wayback Machine.
  22. ^ Обзор продукта Genuine Fractals
  23. ^ "MAW 1998: Тематическое эссе" . www.mathaware.org . Архивировано из оригинального 31 августа 2016 года . Проверено 18 апреля 2018 года .
  24. ↑ Эйткен, Уильям (май 1994). «Большое сжатие». Мир персональных компьютеров .
  25. ^ 1994 Руководство с указанием на странице 11 SoftVideo по лицензии Spectrum Holobyte
  26. ^ "Mitsubishi Corporation подписывает соглашение с Iterated Systems" (пресс-релиз). Итерированные системы. 29 октября 1996 года Архивировано из оригинала 8 июля 2012 года.
  27. ^ «Проигрыватель Windows Media для кодеков, поддерживаемых Windows XP» . 31 октября 2003 года Архивировано из оригинала 28 октября 2004 года.
  28. ^ «Апрель - 2014 - Комплексное исследование фрактальной видеотехнологии» . paulschlessinger.wordpress.com . Проверено 18 апреля 2018 года .
  29. ^ Kominek, Джон (1 июня 1997). «Достижения в области фрактального сжатия для мультимедийных приложений». Мультимедийные системы . 5 (4): 255–270. CiteSeerX 10.1.1.47.3709 . DOI : 10.1007 / s005300050059 . S2CID 6016583 .  
  30. ^ Харада, Масаки; Кимото, Тадахико; Фудзии, Тошиаки; Танимото, Масаюки (2000). «Быстрый расчет параметров IFS для кодирования фрактальных изображений». В Нган, король N; Сикора, Томас; Сунь, Мин-Тинг (ред.). Визуальные коммуникации и обработка изображений 2000 . 4067 . п. 457–464. Bibcode : 2000SPIE.4067..457H . DOI : 10.1117 / 12.386580 . S2CID 30148845 . ИНИСТ : 1380599 . 
  31. ^ Раджкумар, Ватхап Сапанкумар; Кулькарни, М.В. Дхор, ML; Мали, С. Н. (2006). «Синтез производительности фрактального сжатия изображения посредством HV-разбиения». 2006 Международная конференция по передовым вычислениям и коммуникациям . С. 636–637. DOI : 10,1109 / ADCOM.2006.4289976 . ISBN 978-1-4244-0715-6. S2CID  15370862 .
  32. ^ Простые и быстрые схемы сжатия фрактальных изображений , сигналы и системы - 2003
  33. ↑ Ву, Мин-Шэн; Дженг, Джих-Хорнг; Се, Джер-Гуан (июнь 2007 г.). «Схема генетического алгоритма сжатия фрактальных изображений». Технические приложения искусственного интеллекта . 20 (4): 531–538. DOI : 10.1016 / j.engappai.2006.08.005 .
  34. ^ Ву, Сяньвэй; Джексон, Дэвид Джефф; Чен, Хуэй-Чуань (сентябрь 2005 г.). «Быстрый метод кодирования фрактальных изображений, основанный на интеллектуальном поиске стандартного отклонения». Компьютеры и электротехника . 31 (6): 402–421. DOI : 10.1016 / j.compeleceng.2005.02.003 .
  35. ^ Ву, Сяньвэй; Джексон, Дэвид Джефф; Чен, Хуэй-Чуань (2005). «Новый алгоритм кодирования фрактальных изображений, основанный на системе повторяющихся функций полного бинарного дерева без поиска». Оптическая инженерия . 44 (10): 107002. Bibcode : 2005OptEn..44j7002W . DOI : 10.1117 / 1.2076828 .
  36. ^ Чыонг, Trieu-Кийны; Дженг, Джих Х. (2000). «Метод быстрой классификации фрактального сжатия изображений». В Schmalz, Mark S (ред.). Математика и приложения кодирования, сжатия и шифрования данных / изображений III . Математика и приложения кодирования данных / изображений . 4122 . С. 190–193. Bibcode : 2000SPIE.4122..190T . DOI : 10.1117 / 12.409247 . S2CID 120032052 . 
  37. Перейти ↑ Erra, Ugo (2005). «К сжатию фрактальных изображений в реальном времени с использованием графического оборудования». Достижения в области визуальных вычислений . Конспект лекций по информатике. 3804 . С. 723–728. DOI : 10.1007 / 11595755_92 . ISBN 978-3-540-30750-1.
  38. ↑ Хафнер, Ульрих (2001). "FIASCO - Открытый кодек для фрактальных изображений и последовательностей" . Linux Journal (81) . Проверено 19 февраля 2013 года .
  39. ^ "Manpage фиаско" . castor.am.gdynia.pl . Архивировано из оригинала 9 марта 2012 года . Проверено 18 апреля 2018 года .
  40. ^ "Руководство пользователя Pnmtofiasco" . netpbm.sourceforge.net . Проверено 18 апреля 2018 года .
  41. ^ "Руководство пользователя Fiascotopnm" . netpbm.sourceforge.net . Проверено 18 апреля 2018 года .
  42. ^ "Архивная копия" . Архивировано из оригинала на 2010-10-23 . Проверено 10 июля 2010 .CS1 maint: заархивированная копия как заголовок ( ссылка )

Внешние ссылки [ править ]

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