Компрессия (стр. 6 )

В соответствии с данным методом изображение разбивается на множество неперекрывающихся ранговых подизображений (range subimages) и определяется множество перекрывающихся доменных подизображений (domain subimages). Для каждого рангового блока алгоритм кодирования находит наиболее подходящий доменный блок и аффинное преобразование, которое переводит этот доменный блок в данный ранговый блок. Структура изображения отображается в систему ранговых блоков, доменных блоков и преобразований.

Основная сложность метода.

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

На данный момент известно достаточно большое количество алгоритмов оптимизации перебора, возникающего при фрактальном сжатии, поскольку большинство статей, исследовавших алгоритм были посвящены этой проблеме, и во время активных исследований (1992-1996 года) выходило до 300 статей в год. Наиболее эффективными оказались два направления исследований: метод выделения особенностей (feature extraction) и метод классификации доменов (classification of domains).

Патенты.

Майклом Барнсли и другими было получено несколько патентов на фрактальное сжатие в США и других. Например, U. S. Patents 4,941,193, 5,065,447, 5,384,867, 5,416,856 и 5,430,812. Эти патенты покрывают широкий спектр возможных изменений фрактального сжатия и серьёзно сдерживают его развитие.

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

3.2 Сжатие с использованием вейвлет.

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

Существенную роль в алгоритмах вейвлетной компрессии играет концепция представления результатов вейвлет-разложения в виде нуль-дерева (zero-tree).

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

Суть метода.

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

Для работы с дискретными изображениями используется вариант вейвлет-преобразования, известный как алгоритм Малла, названный в честь его изобретателя Стефана Малла (фр. Stephane Mallat). Исходное изображение раскладывается на две составляющие — высокочастотные детали (состоящие в основном из резких перепадов яркости), и сглаженную уменьшенную версию оригинала. Это достигается применением пары фильтров, причём каждая из полученных составляющих вдвое меньше исходного изображения. Как правило, используются фильтры с конечным импульсным откликом, в которых пикселы, попавшие в небольшое «окно», умножаются на заданный набор коэффициентов, полученные значения суммируются, и окно сдвигается для расчёта следующего значения на выходе. Между вейвлетами и фильтрами есть тесная связь. Вейвлеты непосредственно не фигурируют в алгоритмах, но если итерировать соответствующие фильтры на изображениях, состоящих из единственной яркой точки, то на выходе будут все отчётливей проступать вейвлеты.

Поскольку изображения двумерны, фильтрация производится и по вертикали, и по горизонтали. Этот процесс повторяется многократно, причём каждый раз в качестве входа используется сглаженная версия с предыдущего шага. Так как изображения «деталей» состоят обычно из набора резких границ, и содержат обширные участки где интенсивность близка к нулю. Если допустимо пренебречь некоторым количеством мелких деталей, то все эти значения можно просто обнулить. В результате получается версия исходного изображения, хорошо поддающаяся сжатию. Для восстановления оригинала снова применяется алгоритм Малла, но с парой фильтров, обратной к исходным.

Алгоритмы JPEG и MPEG, в отличие от вейвлетного, сжимают по отдельности каждый блок исходного изображения размером 8 на 8 пикселов. В результате, за счёт потери данных при сжатии, на восстановленном изображении может быть заметна блочная структура. При вейвлетном сжатии такой проблемы не возникает, но могут появляться искажения другого типа, имеющие вид «призрачной» ряби вблизи резких границ. Считается, что такие артефакты в среднем меньше бросаются в глаза наблюдателю, чем "квадратики", создаваемые JPEG.

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

ФБР ввело стандарт на вейвлетное сжатие изображений отпечатков пальцев. Впрочем, свобода выбора фильтров может оказаться очень полезной в задаче сжатия: алгоритмы, основанные на принципе «наилучшего базиса», подбирают оптимальный фильтр для отдельных участков изображения, а алгоритмы, использующие вейвлет — пакеты, достигают эффективного представления деталей, варьируя глубину фильтрации на разных участках.

Сжатие видеопоследовательностей.

Ещё одна проблема состоит в том, как эффективно использовать схожесть последовательных кадров при сжатии видео. В ранних алгоритмах, таких как Motion JPEG, этот фактор игнорировался, и кадры сжимались индивидуально. MPEG использует алгоритм сравнения блоков, который старается выделить участки, изменившиеся при смене кадра. Блоки же, которые не изменились, можно не сохранять. При третьем подходе, удобном для вейвлетного сжатия, время рассматривается как третье измерение массива данных, к которому применяется алгоритм Малла. Отсутствие перемещений проявляется в обнулении соответствующих деталей по временному направлению. Эксперименты показывают, что этот метод даёт хорошие результаты, хотя и требует больших вычислений.

Наконец, надо заметить, что вейвлет-преобразование само по себе ничего не сжимает. Оно лишь осуществляет препроцессинг изображения, после которого эффективность обычных методов сжатия резко возрастает, причём даже при использовании универсальных алгоритмов и программ (таких, как LZW и pkzip), не адаптированных к конкретной задаче. Впрочем, использование методов кодирования, учитывающих структуру вейвлет — преобразования, может существенно повысить степень сжатия. Один из широко используемых методов такого типа — метод нуль-дерева (англ. zero-tree compression). Он основан на предположении, что если некоторая область изображения не содержит нетривиальной информации на некотором уровне разрешения, то с большой вероятностью она не будет информативной и на более тонком уровне разрешения. Вейвлет — преобразование изображения можно хранить в виде дерева, корнем которого является сильно сглаженная версия оригинала, а ветви, представляющие отдельные блоки, обрываются на том уровне, где дальнейшая обработка не даёт заметного уточнения. Такое дерево можно с успехом сжать обычными методами типа хаффмановского или арифметического кодирования, которые используются почти во всех алгоритмах сжатия.

Реализации.

Наиболее известный алгоритм вейвлетной компрессии - JPEG-2000. Вейвлетная компрессия используется также при кодировании в формат DjVu. Существует также множество нестандартизированных алгоритмов кодирования изображений и видео-последовательностей основанных на вейвлетной компрессии и предназначенных для специализированного применения.

Примеры вейвлетной компрессии:

● JPEG 2000

● Windows Media Photo

● Tarkin

● SPIHT

● MrSID

● Dirac

● Snow

● Pixlet

● ECW

● StreamLogic

  3.3  JPEG.

JPEG (англ. Joint Photographic Experts Group — русск. Объединенная группа экспертов в области фотографии) — является широкоиспользуемым методом сжатия фотоизображений. Формат файла, который содержит сжатые данные обычно также называют именем JPEG; наиболее распространённые расширения для таких файлов. jpeg, .jfif, .jpg, .JPG, или. JPE. Однако из них. jpg самое популярное расширение на всех платформах.

Алгоритм JPEG является алгоритмом сжатия с потерей качества.

Область применения.

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

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

Сжатие.

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

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