Отправляет email-рассылки с помощью сервиса Sendsay

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

Рассылка закрыта

Вы можете найти рассылки сходной тематики в Каталоге рассылок.

←   Октябрь 2010   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
Автор
smkibermax@inbox.ru

Статистика

3 подписчиков
0 за неделю
←   Все выпуски   →

Фрактальное сжатие изображений. Тенденции развития алгоритмов сжатия статических растровых


Тенденции развития алгоритмов сжатия статических растровых изображений

Полную версию смотрите на fic.bos.ru

Автор: Д.С.Ватолин "Тенденции развития алгоритмов архивации графики"
Источник: Журнал Открытые системы. Номер 4. Зима 1995

Введение

В последнее время изображения и иллюстрации стали использоваться повсеместно. Проблема, связанная с их большим размером, появилась при работе и на рабочих станциях, и на персональных компьютерах. Так, одно полноэкранное (640х480) полноцветное TrueColor - 24 бита на точку) изображение занимает почти мегабайт. Учитывая то, что обычно используется несколько иллюстраций, и то, что они часто бывают гораздо большего размера (например при цветной печати), держать их в неупакованном виде становится накладно. В последние годы решению этой проблемы уделяется достаточно серьезное внимание. Разработано большое количество различных алгоритмов архивации графики: использовались как видоизмененные универсальные, так и абсолютно новые алгоритмы, ориентированные только на изображения. Более того, были разработаны алгоритмы, ориентированные только на конкретный класс изображений. В этой статье сделана попытка выделить основные тенденции развития алгоритмов архивации статической графики.

Основные понятия

Для того, чтобы вести речь об изображениях, необходимо определить, что под ними понимается. В статье будут рассмотрены статические растровые изображения, представляющие собой двумерный массив чисел - пикселов. Все изображения можно подразделить на две группы: с палитрой и без нее. У изображений с палитрой в пикселе хранится число - индекс в некотором одномерном векторе цветов, называемом палитрой. Чаще всего встречаются палитры из 16 и 256 цветов.
Изображения без палитры бывают в какой-либо системе цветопредставления и в градациях серого. Для последних значение каждого пиксела интерпретируется как яркость соответствующей точки. Встречаются изображения с 2, 16 и 256 уровнями серого. Одна из простых, но интересных задач заключается в приведении цветного или черно-белого изображения к двум градациям яркости, например, для печати на лазерном принтере. При использовании некой системы цветопредставления каждый пиксел представляет собой запись (структуру), полями которой являются компоненты цвета. Самой распространенной является система RGB, в которой цвет представлен значениями интенсивности красного (В), зеленого (G) и синего (В) компонента. Существуют и другие системы цветопредставления, такие, как CMYK, CIE XYZccir60-1 и т.п.

Классы изображений

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

Рассмотрим следующие примеры неформального определения классов изображений:
- изображения с небольшим количеством цветов (4-16) и большими областями, заполненными одним цветом (примеры: деловая графика - гистограммы, диаграммы, графики и т.п.);
- изображения, с использованием плавных переходов, построенные на компьютере (примеры: графика презентаций, эскизные модели в САПР, изображения построенные по методу закраски Гуро);
- фотореалистичные изображения (пример: отсканированные фотографии);
- фотореалистичные изображения с наложением деловой графики.

В качестве отдельных классов могут быть предложены некачественно отсканированные в 256 градаций серого цвета страницы журналов или растровые изображения топографических карт. Формально являясь 8 или 24-битными, они несут даже не растровую, а векторную информацию. Отдельные классы могут образовывать и совсем специфичные изображения: рентгеновские снимки или фотографии в профиль и фас из электронного досье.
Достаточно сложной и интересной задачей является поиск наилучшего алгоритма для конкретного класса изображений.

Критерии оценки алгоритмов

Для того, чтобы корректно оценивать направление изменения алгоритмов, недостаточно определить только классы изображений. Необходимо задать и определенные критерии:

  1. Худший, средний и лучший коэффициенты сжатия. То есть доля, на которую возрастет размер изображения, если исходные данные будут наихудшими; некий среднестатистический коэффициент для того класса изображений, на который ориентирован алгоритм; и, наконец, лучший коэффициент. Последний необходим лишь теоретически, поскольку показывает степень сжатия наилучшего (как правило, абсолютно черного) изображения, не редко - фиксированного размера.
  2. Класс изображений, на который ориентирован алгоритм. Иногда указано также, почему на других классах изображений получаются худшие результаты.
  3. Симметричность. Характеризует ресурсоемкость процессов кодирования и декодирования. Для нас наиболее важными являются два коэффициента: отношение времени кодирования ко времени декодирования и требования на память.
  4. Есть ли потери качества? И если есть, то за счет чего изменяется коэффициент архивации? Дело в том, что у большинства алгоритмов сжатия с потерей информации существует возможность изменения коэффициента сжатия.
  5. Характерные особенности алгоритма и изображений, к которым его применяют.

Полную версию смотрите на fic.bos.ru
В избранное