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

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

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

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

Суть метода

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

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

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

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

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

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

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

Реализации

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

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

• Dirac
• ECW
• EZW
• JPEG 2000
• Motion Wavelet
• MrSID
• Pixlet
• Rodudu
• SIF1
• Snow
• SPIHT
• StreamLogic
• Tarkin
• Windows HD Photo
• ICER

Ссылки

• web.cecs.pdx.edu/~mperkows/CAPSTONES/HAAR/u9kvl.pdf
• www.uwec.edu/walkerjs/media/imagecompchap.pdf‎
• arxiv.org/ftp/arxiv/papers/1010/1010.4084.pdf

Отрывок, характеризующий Сжатие с использованием вейвлет

– А знаете, графиня, – сказал он, вдруг обращаясь к ней, как к старой давнишней знакомой, – у нас устраивается карусель в костюмах; вам бы надо участвовать в нем: будет очень весело. Все сбираются у Карагиных. Пожалуйста приезжайте, право, а? – проговорил он.
Говоря это, он не спускал улыбающихся глаз с лица, с шеи, с оголенных рук Наташи. Наташа несомненно знала, что он восхищается ею. Ей было это приятно, но почему то ей тесно и тяжело становилось от его присутствия. Когда она не смотрела на него, она чувствовала, что он смотрел на ее плечи, и она невольно перехватывала его взгляд, чтоб он уж лучше смотрел на ее глаза. Но, глядя ему в глаза, она со страхом чувствовала, что между им и ей совсем нет той преграды стыдливости, которую она всегда чувствовала между собой и другими мужчинами. Она, сама не зная как, через пять минут чувствовала себя страшно близкой к этому человеку. Когда она отворачивалась, она боялась, как бы он сзади не взял ее за голую руку, не поцеловал бы ее в шею. Они говорили о самых простых вещах и она чувствовала, что они близки, как она никогда не была с мужчиной. Наташа оглядывалась на Элен и на отца, как будто спрашивая их, что такое это значило; но Элен была занята разговором с каким то генералом и не ответила на ее взгляд, а взгляд отца ничего не сказал ей, как только то, что он всегда говорил: «весело, ну я и рад».
В одну из минут неловкого молчания, во время которых Анатоль своими выпуклыми глазами спокойно и упорно смотрел на нее, Наташа, чтобы прервать это молчание, спросила его, как ему нравится Москва. Наташа спросила и покраснела. Ей постоянно казалось, что что то неприличное она делает, говоря с ним. Анатоль улыбнулся, как бы ободряя ее.
– Сначала мне мало нравилась, потому что, что делает город приятным, ce sont les jolies femmes, [хорошенькие женщины,] не правда ли? Ну а теперь очень нравится, – сказал он, значительно глядя на нее. – Поедете на карусель, графиня? Поезжайте, – сказал он, и, протянув руку к ее букету и понижая голос, сказал: – Vous serez la plus jolie. Venez, chere comtesse, et comme gage donnez moi cette fleur. [Вы будете самая хорошенькая. Поезжайте, милая графиня, и в залог дайте мне этот цветок.]
Наташа не поняла того, что он сказал, так же как он сам, но она чувствовала, что в непонятных словах его был неприличный умысел. Она не знала, что сказать и отвернулась, как будто не слыхала того, что он сказал. Но только что она отвернулась, она подумала, что он тут сзади так близко от нее.
«Что он теперь? Он сконфужен? Рассержен? Надо поправить это?» спрашивала она сама себя. Она не могла удержаться, чтобы не оглянуться. Она прямо в глаза взглянула ему, и его близость и уверенность, и добродушная ласковость улыбки победили ее. Она улыбнулась точно так же, как и он, глядя прямо в глаза ему. И опять она с ужасом чувствовала, что между ним и ею нет никакой преграды.
Опять поднялась занавесь. Анатоль вышел из ложи, спокойный и веселый. Наташа вернулась к отцу в ложу, совершенно уже подчиненная тому миру, в котором она находилась. Всё, что происходило перед ней, уже казалось ей вполне естественным; но за то все прежние мысли ее о женихе, о княжне Марье, о деревенской жизни ни разу не пришли ей в голову, как будто всё то было давно, давно прошедшее.
В четвертом акте был какой то чорт, который пел, махая рукою до тех пор, пока не выдвинули под ним доски, и он не опустился туда. Наташа только это и видела из четвертого акта: что то волновало и мучило ее, и причиной этого волнения был Курагин, за которым она невольно следила глазами. Когда они выходили из театра, Анатоль подошел к ним, вызвал их карету и подсаживал их. Подсаживая Наташу, он пожал ей руку выше локтя. Наташа, взволнованная и красная, оглянулась на него. Он, блестя своими глазами и нежно улыбаясь, смотрел на нее.

Только приехав домой, Наташа могла ясно обдумать всё то, что с ней было, и вдруг вспомнив князя Андрея, она ужаснулась, и при всех за чаем, за который все сели после театра, громко ахнула и раскрасневшись выбежала из комнаты. – «Боже мой! Я погибла! сказала она себе. Как я могла допустить до этого?» думала она. Долго она сидела закрыв раскрасневшееся лицо руками, стараясь дать себе ясный отчет в том, что было с нею, и не могла ни понять того, что с ней было, ни того, что она чувствовала. Всё казалось ей темно, неясно и страшно. Там, в этой огромной, освещенной зале, где по мокрым доскам прыгал под музыку с голыми ногами Duport в курточке с блестками, и девицы, и старики, и голая с спокойной и гордой улыбкой Элен в восторге кричали браво, – там под тенью этой Элен, там это было всё ясно и просто; но теперь одной, самой с собой, это было непонятно. – «Что это такое? Что такое этот страх, который я испытывала к нему? Что такое эти угрызения совести, которые я испытываю теперь»? думала она.
Одной старой графине Наташа в состоянии была бы ночью в постели рассказать всё, что она думала. Соня, она знала, с своим строгим и цельным взглядом, или ничего бы не поняла, или ужаснулась бы ее признанию. Наташа одна сама с собой старалась разрешить то, что ее мучило.
«Погибла ли я для любви князя Андрея или нет? спрашивала она себя и с успокоительной усмешкой отвечала себе: Что я за дура, что я спрашиваю это? Что ж со мной было? Ничего. Я ничего не сделала, ничем не вызвала этого. Никто не узнает, и я его не увижу больше никогда, говорила она себе. Стало быть ясно, что ничего не случилось, что не в чем раскаиваться, что князь Андрей может любить меня и такою . Но какою такою ? Ах Боже, Боже мой! зачем его нет тут»! Наташа успокоивалась на мгновенье, но потом опять какой то инстинкт говорил ей, что хотя всё это и правда и хотя ничего не было – инстинкт говорил ей, что вся прежняя чистота любви ее к князю Андрею погибла. И она опять в своем воображении повторяла весь свой разговор с Курагиным и представляла себе лицо, жесты и нежную улыбку этого красивого и смелого человека, в то время как он пожал ее руку.