Фрактальные методы

Топологической размерностью множества в линейном пространстве называют число линейно независимых координат, которыми описывают его точки. Например, окружность имеет топологическую размерность 1, круг (т.е. часть плоскости, лежащая внутри окружности), сфера — 2, а шар (как часть объема, ограниченная сферой) —3. Фрактальной размерностью множества называется размерность пространства, которое полностью заполняется множеством. Фракталом называют множество, для которого фрактальная размерность не совпадает с топологической. Например, фракталом может быть линия бесконечной длины, ограничивающая конечную по площади часть плоскости.

Картинку, нарисованную человеком, можно представить в виде комбинаций геометрических фигур, в результате получится векторное изображение. Такие геометрические фигуры, как линия, прямоугольник, треугольник, круг, эллипс, дуга и т.п., можно описать формулами и несложными алгоритмами построения. Пейзаж или портрет описать набором таких элементарных фигур очень сложно, вот почему мы не можем представить фотографию в векторной форме. В 70-е годы 20 века математики стали проявлять интерес к новому классу геометрических фигур, фракталам. Уже первые исследования показали, что фракталы удивительно похожи на природные объекты: листья, соцветия, капли и т.п. В 1977 г. бельгийский математик Б. Мандельброт высказал смелое предположение, что это не просто совпадение, а действительно те очертания природных объектов, которые мы привыкли называть нечеткими или расплывчатыми, на самом деле представляют собой фракталы. Пока что биология не подтвердила эту гипотезу, однако существуют результаты вычислительных экспериментов, подтверждающие целесообразность использования данной идеи в практических целях. Фрактальное преобразование описывает обработку форм различных размеров, похожих между собой по структуре (пример таких объектов — чипсы). При этом изображение можно масштабировать в широких пределах — ведь картина рисуется кривыми, только более сложными, чем в векторной графике. Теоретически это позволяет сжимать графическую информацию до 10 тыс. раз, причем появляющиеся при этом искажения будут гораздо менее заметны человеческому глазу по сравнению с результатами применения алгоритма JPEG.

В 1981 г. Д. Хатчинсон предложил метод системы итерируемых (IFS, Iterated Function System) функций для фрактального сжатия изображений. В 1987 г. американец М. Барнсли основал компанию Iterated Systems, основной деятельностью которой является создание новых алгоритмов и ПО с использованием фракталов. Первая практическая реализация метода IFS в виде компьютерного алгоритма появилась только в 1990 г. Фрактал представляется в виде набора рекурсивных преобразований, коэффициенты в которых и являются описанием изображения. В процессе сжатия информации происходит определение этих коэффициентов.

Практическим результатом работы компании Iterated Systems стал графический формат FIF, использующий принцип фрактального сжатия. Для создания FIF-файлов существует специальная программа, а также plugin к редактору Adobe Photoshop. Однако, несмотря на всю свою привлекательность, FIF пока что не стал таким же общедоступным форматом для Web, как GIF или JPEG.

Фрактальное сжатие изображений является сейчас важной темой для многих серьезных исследований. Конечно, 10000-крат-ной компрессии фрактальными методами пока еще достичь не удалось, но сжатие изображения в 50 раз так, что искажения практически не заметны, — уже реальный результат. Однако при всех своих преимуществах фрактальные алгоритмы сжатия, даже уже довольно известный IFS, пока не нашли широкого применения. Причина в том, что схожесть очертаний любых природных объектов с фракталами пока что не доказана, а лишь подтверждена эмпирическим путем на ограниченном наборе фотографий. А это значит, что при коммерческом применении фирма, использующая в свох продуктах фрактальные методы, пока не может гарантировать своим пользователям жестко определенные показатели качества работы.

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