stringtranslate.com

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

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

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

Системы итерационных функций

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

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

Начнем с представления бинарного изображения , где изображение можно рассматривать как подмножество . IFS — это набор отображений сжатия ƒ 1 ,..., ƒ N ,

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

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

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

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

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

Представление IFS можно расширить до изображения в оттенках серого , рассматривая график изображения как подмножество . Для изображения в оттенках серого u ( x , y ) рассмотрим множество S = {( x , y , u ( x , y ))}. Тогда, аналогично двоичному случаю, S описывается IFS с использованием набора отображений сжатия ƒ 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] Однако, поскольку интерполяция не может обратить вспять энтропию Шеннона, она в конечном итоге повышает резкость изображения, добавляя случайные, а не значимые детали. Например, нельзя увеличить изображение толпы, где лицо каждого человека составляет один или два пикселя, и надеяться идентифицировать их.

История

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

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

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

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

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

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

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

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

Реализации

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

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

Смотрите также

Примечания

  1. ^ Мэй, Майк (1996). «Фрактальное сжатие изображений». American Scientist . 84 (5): 442–451. Bibcode : 1996AmSci..84..442M. JSTOR  29775747. ProQuest  215266230.
  2. ^ ab Fischer, Yuval (1992-08-12). Przemyslaw Prusinkiewicz (ред.). Заметки к курсу SIGGRAPH'92 - Фрактальное сжатие изображений (PDF) . SIGGRAPH. Том. Фракталы - от народного искусства к гиперреальности. ACM SIGGRAPH . Архивировано из оригинала (PDF) 2017-09-12 . Получено 2017-06-28 .
  3. ^ Saupe, Dietmar; Hamzaoui, Raouf (ноябрь 1994 г.). «Обзор литературы по фрактальному сжатию изображений». ACM SIGGRAPH Computer Graphics . 28 (4): 268–276. doi :10.1145/193234.193246. S2CID  10489445.
  4. ^ Лакруа, Бруно (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. ^ Джон Р. Дженсен, «Учебники по дистанционному зондированию», Альтернативы сжатия изображений и соображения по хранению на носителях (ссылка на время сжатия/распаковки) , Университет Южной Каролины , архивировано из оригинала 2008-03-03
  8. ↑ Стив Хит (23 августа 1999 г.). Мультимедиа и коммуникационные технологии. Focal Press. С. 120–123. ISBN 978-0-240-51529-8.Ссылка на Focal Press
  9. ^ Сайуд, Халид (2006). Введение в сжатие данных . Elsevier. С. 560–569. ISBN 978-0-12-620862-7.
  10. ^ Wee Meng Woon; Anthony Tung Shuen Ho; Tao Yu; Siu Chung Tam; Siong Chai Tan; Lian Teck Yap (2000). "Достижение высокого сжатия данных самоподобных спутниковых изображений с использованием фрактала". IGARSS 2000. Международный симпозиум IEEE 2000 по геонаукам и дистанционному зондированию. Измерение пульса планеты: роль дистанционного зондирования в управлении окружающей средой. Труды (кат. № 00CH37120). Том 2. стр. 609–611. doi :10.1109/IGARSS.2000.861646. ISBN 0-7803-6359-0. S2CID  14516581.
  11. ^ Фишер, Ю. (Июль 1995). Фрактальное кодирование видеопоследовательностей . Фрактальное кодирование и анализ изображений. Тронхейм. INIST 1572685. 
  12. ^ Walking, Talking Web Архивировано 06.01.2008 в статье журнала Wayback Machine Byte Magazine о независимости фрактального сжатия и разрешения
  13. ^ Хэ, Чуань-цзян; Ли, Гао-пин; Шэнь, Сяо-на (май 2007 г.). «Метод интерполяционного декодирования с переменными параметрами для сжатия фрактальных изображений». Хаос, солитоны и фракталы . 32 (4): 1429–1439. Bibcode : 2007CSF....32.1429H. doi : 10.1016/j.chaos.2005.11.058.
  14. ^ Наваскуэс, Массачусетс; Себастьян, М.В. (2006). «Гладкая фрактальная интерполяция». Журнал неравенств и приложений . 2006 : 1–20. дои : 10.1155/JIA/2006/78734 . S2CID  20352406.
  15. ^ Уэмура, Сатоши; Хасеяма, Мики; Китадзима, Хидео (28 января 2003 г.). «EFIFを用いた自己アフィンフラクタル図形の拡大処理に関する考察» [Замечание о методе расширения самоаффинных фрактальных объектов с использованием расширенных функций фрактальной интерполяции]. Технический отчет IEICE (на японском языке). 102 (630): 95–100. дои : 10.11485/itetr.27.9.0_95. НАИД  110003171506.
  16. ^ Курода, Хидео; Ху, Сяотун; Фудзимура, Макото (1 февраля 2003 г.). «フラクタル画像符号化におけるスケーリングファクタに関する考察» [Исследования коэффициента масштабирования для кодирования фрактальных изображений]. Труды Института инженеров электроники, информации и связи (на японском языке). 86 (2): 359–363. НАИД  110003170896.
  17. ^ Барнсли, Майкл; Слоан, Алан (январь 1988). «Лучший способ сжатия изображений». Байт . С. 215–223.
  18. ↑ Патент США 4,941,193  – первый патент Барнсли и Слоана на систему итерационных функций , поданный в октябре 1987 г.
  19. ^ Использование фрактального кодирования для индексации содержимого изображений для Технического отчета цифровой библиотеки
  20. ^ Jacquin, AE (1992). «Кодирование изображений на основе фрактальной теории итерированных сжимающих преобразований изображений». Труды IEEE по обработке изображений . 1 (1): 18–30. Bibcode :1992ITIP....1...18J. CiteSeerX 10.1.1.456.1530 . doi :10.1109/83.128028. PMID  18296137. 
  21. ^ Iterated Systems Inc. сменила название на MediaBin Inc. Inc. в 2001 году и, в свою очередь, была куплена Interwoven, Inc. в 2003 году)
  22. ^ NIST SP950-3, «Сбор и интеграция информации о состоянии здоровья пациентов для улучшения доступности»; см. стр. 36, «Фрактальная технология MediaBin для сжатия файлов цифровых изображений». Архивировано 23 сентября 2015 г. на Wayback Machine
  23. ^ Обзор продукта Genuine Fractals
  24. ^ "MAW 1998: Theme Essay". www.mathaware.org . Архивировано из оригинала 31 августа 2016 года . Получено 18 апреля 2018 года .
  25. ^ Эйткен, Уильям (май 1994). "Большое сжатие". Мир персональных компьютеров .
  26. ^ 1994 Руководство, указанное на странице 11 SoftVideo по лицензии Spectrum Holobyte
  27. ^ "Mitsubishi Corporation подписывает соглашение с Iterated Systems" (пресс-релиз). Iterated Systems. 29 октября 1996 г. Архивировано из оригинала 8 июля 2012 г.
  28. ^ "Поддерживаемые кодеки проигрывателя Windows Media для Windows XP". 31 октября 2003 г. Архивировано из оригинала 28 октября 2004 г.
  29. ^ "Апрель - 2014 - Due Diligence Study of Fractal Video Technology". paulschlessinger.wordpress.com . Получено 18 апреля 2018 .
  30. ^ Коминек, Джон (1 июня 1997 г.). «Достижения в области фрактального сжатия для мультимедийных приложений». Мультимедийные системы . 5 (4): 255–270. CiteSeerX 10.1.1.47.3709 . doi :10.1007/s005300050059. S2CID  6016583. 
  31. ^ Харада, Масаки; Кимото, Тадахико; Фуджи, Тошиаки; Танимото, Масаюки (2000). «Быстрый расчет параметров IFS для кодирования фрактальных изображений». В Нгане — король Н; Сикора, Томас; Сунь, Мин-Тин (ред.). Визуальные коммуникации и обработка изображений 2000 . Том. 4067. стр. 457–464. Бибкод : 2000SPIE.4067..457H. дои : 10.1117/12.386580. S2CID  30148845. ИНИСТ 1380599. 
  32. ^ Раджкумар, Ватхап Сапанкумар; Кулкарни, МВ; Дхоре, МЛ; Мали, СН (2006). «Синтез производительности фрактального сжатия изображений с помощью HV-разбиения». Международная конференция по передовым вычислениям и коммуникациям 2006 г. С. 636–637. doi :10.1109/ADCOM.2006.4289976. ISBN 978-1-4244-0715-6. S2CID  15370862.
  33. ^ Простые и быстрые схемы, сигналы и системы фрактального сжатия изображений - 2003
  34. ^ Wu, Ming-Sheng; Jeng, Jyh-Horng; Hsieh, Jer-Guang (июнь 2007 г.). «Схема генетического алгоритма для сжатия фрактальных изображений». Engineering Applications of Artificial Intelligence . 20 (4): 531–538. doi :10.1016/j.engappai.2006.08.005.
  35. ^ Wu, Xianwei; Jackson, David Jeff; Chen, Hui-Chuan (сентябрь 2005 г.). «Быстрый метод кодирования фрактальных изображений на основе интеллектуального поиска стандартного отклонения». Computers & Electrical Engineering . 31 (6): 402–421. doi :10.1016/j.compeleceng.2005.02.003.
  36. ^ Wu, Xianwei; Jackson, David Jeff; Chen, Hui-Chuan (2005). "Новый алгоритм фрактального кодирования изображений, основанный на системе итерированных функций без поиска на полном двоичном дереве". Optical Engineering . 44 (10): 107002. Bibcode :2005OptEn..44j7002W. doi :10.1117/1.2076828.
  37. ^ Truong, Trieu-Kien; Jeng, Jyh H. (2000). "Быстрый метод классификации для сжатия фрактальных изображений". В Schmalz, Mark S (ред.). Mathematics and Applications of Data/Image Coding, Compression, and Encryption III . Vol. 4122. pp. 190–193. Bibcode :2000SPIE.4122..190T. doi :10.1117/12.409247. S2CID  120032052.
  38. ^ Эрра, Уго (2005). «К реальному времени фрактального сжатия изображений с использованием графического оборудования». Достижения в области визуальных вычислений . Конспект лекций по информатике. Том 3804. С. 723–728. doi :10.1007/11595755_92. hdl :11563/14075. ISBN 978-3-540-30750-1.
  39. ^ Хафнер, Ульрих (2001). "FIASCO - кодек фрактальных изображений и последовательностей с открытым исходным кодом". Linux Journal (81) . Получено 19 февраля 2013 г.
  40. ^ "Manpage of fiasco". castor.am.gdynia.pl . Архивировано из оригинала 9 марта 2012 . Получено 18 апреля 2018 .
  41. ^ "Руководство пользователя Pnmtofiasco". netpbm.sourceforge.net . Получено 18 апреля 2018 г. .
  42. ^ "Руководство пользователя Fiascotopnm". netpbm.sourceforge.net . Получено 18 апреля 2018 г. .
  43. ^ "Femtosoft Technologies - Fractal Imaging Software". Архивировано из оригинала 2010-10-23 . Получено 2010-07-10 .

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