Лекции - Технологии Мультимедиа, страница 10

Именно этот печальный фактне позволяет применять его в полиграфии, где качество ставится во главу угла.Однако формат JPEG не является пределом совершенства в стремлении уменьшитьразмер конечного файла. В последнее время ведутся интенсивные исследования в областитак называемого вейвлет - преобразования (или всплеск - преобразования). Основанные насложнейших математических принципах вейвлет - кодеры позволяют получить большеесжатие, чем JPEG, при меньших потерях информации.

Несмотря на сложность математикивейвлет - преобразования, в программной реализации оно проще, чем JPEG. Хотя алгоритмывейвлет - сжатия пока находятся в начальной стадии развития, им уготовано большое будущее.52Фрактальное сжатиеЭта группа алгоритмов, по-видимому, является самой перспективной и развиваетсясейчас наиболее бурно. Первые практические результаты были получены сравнительно недавно - в 1992 году - и произвели ошеломляющее впечатление. В декабре 1992 года компания Microsoft выпустила свой новый компакт - диск Microsoft Encarta. С тех пор эта мультимедиа - энциклопедия, содержащая информацию о животных, цветах, деревьях и живописных местах, не покидает списки наиболее популярных энциклопедий на компакт-дисках. Коэффициент сжатия у фрактальных алгоритмов варьируется в пределах 2-2000. Причем большие коэффициенты достигаются на реальных изображениях, что, вообще говоря, нетипичнодля предшествующих алгоритмов.

Кроме того, при разархивации изображение можно масштабировать. Уникальная особенность этого алгоритма заключается в том, что увеличенноеизображение не дробится на квадраты. Во фрактальном сжатии используется принципиальноновая идея - не близость цветов в локальной области, а подобие разных по размеру областейизображения. Это, безусловно, наиболее прогрессивный подход на сегодняшний день. Алгоритм ориентирован на полноцветные изображения и изображения в градациях серого цвета.Его особенностью является потребность в колоссальных вычислительных мощностяхпри архивации.

При этом распаковка требует меньше вычислений, чем у JPEG. Причем, еслиу предыдущих алгоритмов коэффициент симметричности(отношение времени архивации ко времени разархивации) не превышал 3, то у фрактального алгоритма он колеблется в пределах 1000-10000. Как следствие - основные работысейчас ведутся по распараллеливанию и ускорению его работы. Фрактальное сжатие реализовано в формате FIF.Идея фрактальная архивация основана на том, что с помощью коэффициентов системы функций изображение представляется в более компактной форме.

Прежде чем рассматривать процесс архивации, разберем, как IFS (система итерируемых функций) строит изображение.Строго говоря, IFS - это набор трехмерных аффинных преобразований, переводящиходно изображение в другое. Преобразованию подвергаются точки в трехмерном пространстве (x координата, у координата, яркость).Наиболее наглядно этот процесс продемонстрировал сам Барнсли (который в 1985 году привел вместе со Стефаном Демко довольно стройную теорию фракталов) в своей книге"Фрактальное сжатие изображения". В ней введено понятие Фотокопировальной Машины,состоящей из экрана, на котором изображена исходная картинка, и системы линз, проецирующих изображение на другой экран.

Каждая линза проецирует часть исходного изображения. Расставляя линзы и меняя их характеристики, можно управлять получаемым изображе-53нием. Линзы должны уменьшать в размерах проектируемую часть изображения. Кроме того,они могут менять яркость фрагмента и проецируют не круги, а области с произвольной границей.Один шаг Машины состоит в построении с помощью проецирования по исходномуизображению нового.

Утверждается, что на некотором шаге изображение перестанет изменяться. Оно будет зависеть только от расположения и характеристик линз, и не будет зависеть от исходной картинки. Это изображение называется неподвижной точкой. Посколькуотображение линз является сжимающим, каждая линза в явном виде задает самоподобныеобласти в нашем изображении. Благодаря самоподобию мы получаем сложную структуруизображения при любом увеличении.Наиболее известны два изображения, полученных с помощью IFS треугольник Серпинского и папоротник Барнсли Первое задается тремя, а второе - пятью аффинными преобразованиями (или, в нашей терминологии, линзами).

Каждое преобразование задается буквально считанными байтами, в то время, как изображение, построенное с их помощью, может занимать и несколько мегабайт.Становится понятно, как работает архиватор, и почему ему требуется так много времени. Фактически, фрактальная компрессия - это поиск самоподобных областей в изображении и определение для них параметров аффинных преобразований.В худшем случае, если не будет применяться оптимизирующий алгоритм, потребуется перебор и сравнение всех возможных фрагментов изображения разного размера. Даже длянебольших изображений при учете дискретности мы получим астрономическое число перебираемых вариантов.

Даже резкое сужение классов преобразований, например, за счет масштабирования только в определенное число раз, не позволит добиться приемлемого времени.Кроме того, при этом теряется качество изображения. Подавляющее большинство исследований в области фрактальной компрессии сейчас направлены на уменьшение времени архивации, необходимого для получения качественного изображения.Для фрактального алгоритма компрессии, как и для других алгоритмов сжатия с потерями, очень важны механизмы, с помощью которых можно будет регулировать степень сжатия и степень потерь. К настоящему времени разработан достаточно большой набор такихметодов. Во - первых, можно ограничить количество преобразований, заведомо обеспечивстепень сжатия не ниже фиксированной величины. Во - вторых, можно потребовать, чтобы вситуации, когда разница между обрабатываемым фрагментом и наилучшим его приближением будет выше определенного порогового значения, этот фрагмент дробился обязательно(для него обязательно заводится несколько линз).

В-третьих, можно запретить дробить фрагменты размером меньше, допустим, четырех точек. Изменяя пороговые значения и приори-54тет этих условий, можно очень гибко управлять коэффициентом компрессии изображения:от побитного соответствия, до любой степени сжатия.Сравнение с JPEGСегодня наиболее распространенным алгоритмом архивации графики является JPEG.Сравним его с фрактальной компрессией.Во-первых, заметим, что и тот, и другой алгоритм оперируют 8-битными (в градацияхсерого) и 24-битными полноцветными изображениями.

Оба являются алгоритмами сжатия спотерями и обеспечивают близкие коэффициенты архивации. И у фрактального алгоритма, иу JPEG существует возможность увеличить степень сжатия за счет увеличения потерь. Крометого, оба алгоритма очень хорошо распараллеливаются.Различия начинаются, если мы рассмотрим время, необходимое алгоритмам для архивации/разархивации.

Так, фрактальный алгоритм сжимает в сотни и даже в тысячи раз дольше, чем JPEG. Распаковка изображения, наоборот, произойдет в 5-10 раз быстрее. Поэтому,если изображение будет сжато только один раз, а передано по сети и распаковано множествораз, то выгодней использовать фрактальный алгоритм.JPEG использует разложение изображения по косинусоидальным функциям, поэтомупотери в нем (даже при заданных минимальных потерях) проявляются в волнах и ореолах награнице резких переходов цветов. Именно за этот эффект его не любят использовать присжатии изображений, которые готовят для качественной печати: там этот эффект можетстать очень заметен.Фрактальный алгоритм избавлен от этого недостатка. Более того, при печати изображения каждый раз приходится выполнять операцию масштабирования, поскольку растр (илилиниатура) печатающего устройства не совпадает с растром изображения.

При преобразовании также может возникнуть несколько неприятных эффектов, с которыми можно боротьсялибо масштабируя изображение программно (для дешевых устройств печати типа обычныхлазерных и струйных принтеров), либо снабжая устройство печати своим процессором, винчестером и набором программ обработки изображений (для дорогих фотонаборных автоматов). Как можно догадаться, при использовании фрактального алгоритма таких проблемпрактически не возникает.Улучшение визуального качества изображений путем поэлементного преобразованияВ большом числе информационных систем применяется представление результатовобработки данных в виде изображения, выводимого на экран для использования наблюдателем.