Использование фракталов для компрессии - Интересное о компьютерах
Работая с рекламой или базами данных, люди все чаще стремятся использовать изображения. В развлечениях или образовании мы уже не представляем себе продуктов без тщательно проработанной графики или видео. В любых телекоммуникациях успех средств коммуникации напрямую связан с возможностью передачи изображений. С другой стороны, множество людей еще пользуется обычными телефонными линиями для передачи данных и не имеет возможности воспроизведения MPEG или хранения гигабайтов данных. Существующая технология телекоммуникаций скорее пригодна для работы с текстами и таблицами, чем с изображениями, видео и звуком. Именно здесь фракталы могут проявить всю свою мощь — наибольший коэффициент сжатия данных и удобство эффективной работы с изображениями позволяют им приспособить любые гипертекстовые файлы к современной технологии.
Математики считают, что фракталы — самый удобный способ описания изображений наиболее естественным путем. Основным свойством фракталов является самоподобие, а фрактальные картины состоят из подобных образцов в нескольких шкалах размерностей. Изображение можно описать как последовательность соотношений одних частей с другими с помощью «фрактального захвата» основного ядра картины. Именно оно и кодируется математическими уравнениями, которые позволяют исследовать подобные образцы или производить масштабирование без изменения качества изображения.
Одна из первых компаний, применившая фракталы в мультимедийных приложениях, — Iterated Systems (Атланта, США), которую основал в 1987 г. Майкл Барнслей (Michael Barnsley). Он считает, что к 2000 г. практически все изображения и видео будут создаваться с помощью фрактальной технологии.
Фрактальная технология компрессии (Fractal Compression Technology) отличается четырьмя уникальными возможностями.
Качество. По качеству изображения при заданном размере файла она вне всякой конкуренции.
Скорость. Практическая скорость декомпрессии в этой технологии намного выше, чем в других известных подходах, что предопределяет ее выбор для приложений с большим количеством изображений.
Масштабируемость. Абсолютно уникальная возможность изменять масштаб изображения с сохранением качества независимо от разрешения оригинала.
Программная реализация. Фрактальная технология не нуждается в аппаратной поддержке.
Компрессия — это процесс уменьшения размеров файла данных без их потери или с минимальными потерями. Преобразование растрового изображения во фрактальный формат (Fractal Image Format — FIF) является компрессией, так как при этом уменьшается размер файла. Файлы цветных изображений могут быть очень большими: специалисты работают с файлами, размер которых превышает 100 MB. И хотя запоминающие устройства дешевеют, а емкость жестких дисков непрерывно возрастает, хранение больших файлов все еще представляет проблему. Сжатые изображения проще распространять. Передача больших массивов данных по локальным сетям или телефонным линиям занимает много времени и, соответственно, является весьма дорогостоящей. Даже популярные CD-ROM’ ы не устраняют необходимости компрессии.
Все методы компрессии можно разделить на две категории: с потерями и без потерь информации. Методы без потерь информации обладают свойством полного восстановления оригинальных данных после декомпрессии. Они используются в случаях, когда потери данных недопустимы, — для компрессии текстовых файлов, медицинских изображений (например, томограмм) и т. п. Эти методы дают среднюю степень сжатия 3 : 1. Методы с потерями информации допускают некоторую потерю данных в процессе компрессии, которые невозможно воспроизвести при декомпрессии. Их применяют, в основном, для сжатия изображений. Файлы изображений часто содержат избыточную информацию, которая может быть опущена без видимых искажений картины. Степень сжатия при этом варьируется в широких пределах и определяется желаемым качеством изображения, скоростью компрессии и размерами файла. Фрактальная компрессия позволяет получить степень сжатия более 100: 1 в зависимости от индивидуальных особенностей изображения.
Один из широко распространенных сегодня методов компрессии с потерями информации разработан Объединенной группой экспертов фотографии (JPEG — Joint Photographic Experts Group). Метод JPEG основан на анализе пикселов и определяет способ сохранения цветного или черно-белого изображения в меньшем количестве байтов. Плата за достаточно высокую степень сжатия в формате JPEG — значительное отличие качества изображения после декомпрессии от оригинала. JPEG при кодировании опускает явно несущественную информацию изображения или сохраняет лишь фрагменты полных данных какой-либо его области. При увеличении степени сжатия теряется информация о мелких деталях, и в некоторый момент появляется блочная структура.
При использовании метода фрактальной компрессии не анализируется каждый пиксел, поэтому получается лучшее качество репродукций любого разрешения, включая высококачественные изображения в любых приложениях от баз данных до мультимедиа-энциклопедий. Природа фрактальных преобразований такова, что данные, теряемые при кодировке, наименее существенны для визуального восприятия, например, тонкие детали в текстурах. В процессе компрессии фрактальные преобразования позволяют контролировать теряемые данные. В отличие от других методов, формат FIF вносит меньшее количество артефактов.
Что касается степени сжатия, то, например, растровый файл размером 921 KB после фрактального преобразования сжимается до 10 KB в формате FIF, так что на стандартном флоппи-диске могут поместиться более 100 изображений. Конкурирующие методы позволяют разместить на аналогичном диске не более 25 изображений того же качества.
FIF-изображения менее зависят от разрешения, нежели обычные растровые файлы: их можно воспроизводить с большим и меньшим разрешением, чем оригинальное изображение. Эта особенность фрактальных методов хорошо проиллюстрирована на рис. 5—6.
Наглядно преимущество фрактальной технологии компрессии представлено на приведенных изображениях: оригинал размером 4 MB был преобразован в файлы форматов JPEG и FIF с одинаковым коэффициентом компрессии 100 : 1, так что оба результирующих изображения имеют размер 40 KB и оба содержат видимые искажения. Однако природа искажений совершенно различна. Фрактальная технология приводит только к некоторой потере тонкой структуры и небольшому уменьшению контрастности, в то время как JPEG приобретает весьма неприятную блочную структуру.