Сделай Сам Свою Работу на 5

Рекурсивный (волновой) алгоритм





Особенности изображения как типа данных

1. Изображение (как и видео) обычно требует для хранения гораздо большего объема памяти, чем текст. Так, скромная не очень качественная иллюстрация на обложке книги размером 500x800 точек занимает 1,2 М б - столько же, сколько художественная книга из 400 страниц (60 знаков в строке, 42 строки на странице

2. Второй особенностью изображений является то, что человеческое зрение при анализе изображения оперирует контурами, общим переходом цветов и сравнительно нечувствительно к малым изменениям в изображении. Таким образом, мы можем создать эффективные алгоритмы архивации изображений, в которых декомпрессированное изображение не будет совпадать с оригиналом, однако человек этого не заметит.

3. Мы можем легко заметить, что изображение в отличие, например, от текста обладает избыточностью в двух измерениях. То есть как правило,соседние точки, как по горизонтали, так и по вертикали, в изображении близки по цвету. Кроме того, мы можем использовать подобие между цветовыми плоскостями R, G и В в наших алгоритмах, что дает возможность создать еще более эффективные алгоритмы. Таким образом, присоздании алгоритма компрессии графики мы используем особенности структуры изображения.



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

Статические растровые изображения представляют собой двумерный массив чисел. Элементы этого массива называют пикселами (от английского pixel - pictureelement). Все изображения можно подразделить на две группы - с палитрой и без нее. У изображений с палитрой в пикселе хранится число- индекс в некотором одномерном векторе цветов, называемом палитрой. Чаще всего встречаются палитры из 16 и 256 цветов. Изображения без палитры бывают в какой-либо системе цветопредставления и в градациях серого (grayscale). Для последних значение каждого пиксела интерпретируется как яркость соответствующей точки. Чаще всего встречаются изображения с 2, 16 и 256 уровнями серого. При использовании некой системы цветопредставления каждый пиксел представляет собой запись (структуру), полями которой являются компоненты цвета. Самой распространенной является система RGB, в которой цвет передается значениями интенсивности красной (R), зеленой (G) и синей (В) компонент.



Неформальное определение наиболее распространенных классов изображений.

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

Класс 2. Изображения с плавными переходами цветов, построенные на компьютере. Примеры: графика презентаций, эскизные модели в САПР, изображения, построенные по методу Гуро.

Класс 3. Фотореалистичные изображения. Пример: отсканированные фотографии.

Класс 4.Фотореалистичные изображенияс наложением деловой графики.Пример: реклама.

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

(Заметим, что этот класс не тождественен классу 4).

 

Алгоритм RLE

ПЕРВЫЙ ВАРИАНТ АЛГОРИТМА

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

Замена их на пары <счетчик повторений, значение> уменьшает избыточность данных. Алгоритм рассчитан на деловую графику - изображения с большими областями повторяющегося цвета. Ситуация, когда файл увеличивается, для этого простого алгоритма не так уж редка. Ее можно легко получить, при меняя групповое кодирование к обработанным цветным фотографиям. Для того чтобы увеличить изображение в 2 раза, его надо применить к изображению, в котором значения всех пикселов больше двоичного 11000000 и подряд попарно не повторяются.



ВТОРОЙ ВАРИАНТ АЛГОРИТМА

Второй вариант этого алгоритма имеет большую максимальную степень сжатия и меньше увеличивает в размерах исходный файл. Как можно легко подсчитать, в лучшем случае этот алгоритм сжимает файл в 64 раза (а не в 32 раза, как в предыдущем варианте), в худшем увеличивает на 1/128. Средние показатели степени компрессии данного алгоритма находятся на уровне показателей первого варианта.

 

Характеристики алгоритма RLE:

Степени сжатия:первый вариант: 32, 2, 0,5. Второй вариант: 64, 3,128/129. (Лучшая, средняя, худшая степени).

Класс изображений:ориентирован алгоритм на изображения с небольшим количеством цветов: деловую и научную графику.

Симметричность:примерно единица.

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

АЛГОРИТМ LZW

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

и далеко не все одинаковые подцепочки в нашем изображении будут использованы при сжатии. Однако в предлагаемом алгоритме выгодно сжимать даже цепочки, состоящие из 2 байт.Процесс сжатия выглядит достаточно просто. Мы считываем последовательно символы входного потока и проверяем, есть ли в созданной нами таблице строк такая строка. Если строка есть, то мы считываем следующий символ, а если строки нет, то мы заносим в поток код для предыдущей найденной строки, заносим строку в таблицу и начинаем поиск снова. Особенность LZW заключается в том, что для декомпрессии нам не надо сохранять таблицу строк в файл для распаковки. Алгоритм построен таким образом, что мы в состоянии восстановить таблицу строк, пользуясь только

потоком кодов. Мы знаем, что для каждого кода надо добавлять в таблицу строку, состоящую из уже присутствующей там строки и символа, с которого начинается следующая строка в потоке.

Характеристики алгоритма LZW:

Степени сжатия:примерно 1000, 4, 5/7 (лучшее, среднее, худшее сжатие). Сжатие в 1000 раз достигается только на одноцветных изображениях размером кратным примерно 7 Мб. (Почему 7 Мб – становится понятно при расчете наилучшей степени сжатия.)

Класс изображений:ориентирован LZW на 8-битовые изображения,построенные на компьютере. Сжимает за счет одинаковых подцепочек в потоке.

Симметричность:почти симметричен, при условии оптимальной реализации операции поиска строки в таблице.

Характерные особенности:ситуация, когда алгоритм увеличивает изображение, встречается крайне редко. Универсален.

 

Проблемы алгоритмов сжатия с потерями

Одна из серьезных проблем машинной графики заключается в том,что до сих пор не найден адекватный критерий оценки потерь качества изображения.А теряется оно постоянно - при оцифровке, при переводе в ограниченную палитру цветов, при переводе в другую систему цветопредставления для печати и, что для нас особенно важно, при сжатии с потерями. Лучше всего потери качества изображений оценивают наши глаза. Отличным считается сжатие, при котором невозможно на глаз различить первоначальное и распакованное изображения. Хорошим - когда сказать, какое из изображений подвергалось сжатию, можно только сравнивая две находящиеся рядом картинки. При дальнейшем увеличении степени сжатия, как правило, становятся заметны побочные эффекты, характерные для данного алгоритма. На практике, даже при отличном сохранении качества, в изображение могут быть внесены регулярные специфические изменения.

Алгоритм JPEG

JPEG - один из новых и достаточно мощных алгоритмов. Практически он является стандартом де-факто для полноцветных изображений [1]. Оперирует алгоритм областями 8x8, на которых яркость и цвет меняются срав-

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

Недостатки алгоритма Не очень приятным свойством JPEG является также то,что нередко горизонтальные и вертикальные полосы на дисплее абсолютно не видны и могут проявиться только при печати в виде муарового узора. Он возникает при наложении наклонного растра печати на горизонтальные и вертикальные полосы изображения.

Характеристики алгоритма JPEG:o

Степень сжатия:2-200 (задается здльзователем). ,

Класс изображений:полноцветные 4 битовые изображения или изображения в градациях серого без резюцс переходов цветов .(фотографии).

Симметричность: 1.

Характерные особенности:в некоторых случаях алгоритм создает "ореол" вокруг резких горизонтальных и вертикальных границ в изображении (эффект Гиббса). Кроме того, при высокой степени сжатия изображение распадается на блоки 8x8 пикселов.

Алгоритм JPEG 2000

Лучшее качество изображения при сильной степени сжатия. Или,что то же самое, большая степень сжатия при том же качестве для высоких степеней сжатия. Фактически это означает заметное уменьшение размеров графики "Web-качества", используемой большинством сайтов.Поддержка кодирования отдельных областей с лучшим качеством.Известно, что отдельные области изображения критичны для восприятия человеком (например, глаза на фотографии), в то время как качеством других можно пожертвовать (например, задним планом). Основной алгоритм сжатия заменен на wavelet. Помимо указанного повышения степени сжатия это позволило избавиться от 8-пиксельной блочности, возникающей при повышении степени сжатия. Кроме того, плавное проявление изображения теперь изначально заложено в стандарт (Progressive JPEG, активно применяемый в Интернете, появился много позднее JPEG).

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

ИДЕЯ АЛГОРИТМА jpeg2000

Базовая схема JPEG 2000 очень похожа на базовую схему JPEG. Отличия заключаются в следующем:

• вместо дискретного косинусного преобразования (DCT) используется

дискретноеwavelet -преобразование (DWT);

• вместо кодирования по Хаффману используется арифметическое сжатие;

• в алгоритм изначально заложено управление качеством областей изображения;

• не используется явно дискретизация компонент U и V после преобразования цветовых пространств, поскольку при DWT можно достичь тогоже результата, но более аккуратно.

Характеристики алгоритма JPEG 2000:

Степень сжатия:2-200 (задается пользователем). Возможно сжатие без потерь.

Класс изображений:полноцветные 24-битовые изображения. Изображения в градациях серого без резких переходов цветов (фотографии).1-битовые изображения.

Симметричность: 1-1.5.

Характерные особенности:позволяет удалять визуально неприятные эффекты, повышая качество в отдельных областях. При сильном сжатии появляется блочность и большие волны в вертикальном и горизонтальном направлениях.

 

Фрактальный алгоритм

ИДЕЯ МЕТОДА

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

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

Характеристики фрактального алгоритма:

Степень сжатия:2-2000 (задается пользователем).

Класс изображений: полноцветные 24 битовые изображения или изображения в градациях серого без резких переходов цветов (фотографии).

Желательно, чтобы области большей значимости (для восприятия) были более контрастными и резкими, а области меньшей значимости - неконтрастными и размытыми.

Симметричность: 100-100 000.

Характерные особенности: может свободно масштабировать изображение при разжатии, увеличивая его в 2-4 раза без появления "лестничного эффекта". При увеличении степени компрессии появляется "блочный" эффект на границах блоков в изображении.

 

Рекурсивный (волновой) алгоритм

Ориентирован алгоритм на цветные и черно-белые изображения с плавными переходами. Идеален для картинок типа рентгеновских снимков.Степень сжатия задается и варьируется в пределах 5-100. При попытке задать больший коэффициент на резких границах, особенно проходящих по диагонали, проявляется лестничный эффект- ступеньки разной яркости размером в несколько пикселов.

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

Так, два числа a-ц и а^пвсегда можно представить в виде b',=(ci2t+a2i+\)/2иЪ'\={агГа2н-\)12. Аналогично последовательность а, может быть попарно переведена в последовательность bUj.

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

Характеристики волнового алгоритма:

Степень: 2-200 (задается пользователем).

Класс изображений: как у фрактального и JPEG.

Симметричность: -1.5.

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

 

ПРИМЕР РАБОТЫ АЛГОРИТМА

Разберем конкретный пример: пусть мы сжимаем строку из восьми значений яркости пикселов (а,): (220, 211, 212, 218, 217, 214, 210, 202). Мы получим следующие последовательности b'tи Ь2{. (215.5, 215, 215.5, 206) и

(4.5, -3, 1.5,4). Заметим, что значения Ь2,- достаточно близки к нулю. Повторим операцию, рассматривая Ь\ как а,. Данное действие выполняется как бы рекурсивно, откуда и название алгоритма. Мы получим из (215.5,215,215.5,

206): (215.25, 210.75) (0.25, 4.75). Полученные коэффициенты, округлив до целых и сжав, например, с помощью алгоритма Хаффмана с фиксированными таблицами, мы можем поместить в файл.

 

СЖАТИЕ ВИДЕОДАННЫХ

При сжатии используется несколько типов избыточности:

1) когерентность областей изображения - малое изменение цвета изображения в соседних пикселах (свойство, которое эксплуатируют все алгоритмы сжатия изображений с потерями);

2) избыточность в цветовых плоскостях - используется большая важность яркости изображения для восприятия;

3) подобие между кадрами - использование того факта, что на скорости 25 кадров в секунду, как правило, соседние кадры изменяются незначительно.

 

 








Не нашли, что искали? Воспользуйтесь поиском по сайту:



©2015 - 2024 stydopedia.ru Все материалы защищены законодательством РФ.