Содержание к диссертации
Введение
1. Векторное квантование при сжатии изображений 10
1.1. Сжатие изображений с потерями. Постановка задачи 10
1.2. Обзор известных подходов 12
Сжатие, основанное на ДКП 13
Сжатие, основанное на ДВП 14
Сравнение работы алгоритмов 16
1.3. Векторное квантование изображений 18
1.4. Построение кодовых книг для векторного квантования 21
Обобщенный алгоритм Ллойда 21
1.5. Основные способы векторного квантования изображений 22
Векторное квантование во временной области 22
Векторное квантование в спектральной области^ 26
1.6. Сравнение векторного квантования изображений с другими алгоритмами 30
1.7. Выводы по разделу 31
2. Векторное квантование с использованием пространственных преобразований 33
2.1. Использование преобразований для компактного задания кодовых книг 33
Пространственные преобразования. 33
2.2. Специальное формирование векторов для процедуры векторного квантования 36
Направленное формирование векторов 38
2.3. Обобщение пространственных и спектральных преобразований 39
2.4. Выводы по разделу 41
3. Трансформационные коды для сжатия изображений 43
3.1. Определение трансформационного кода 43
3.2. Трансформационный код как покрытие видеоизображения 44
3.3. Сжатие изображений при помощи трансформационных кодов 45
3.4. Трансформационное квантование кодовой книгой как способ сжатия статических изображений 47
Выбор преобразований 48
Расширение множества преобразований 49
3.5. Трансформационная компенсация как сжатие видеопоследовательностей52
Традиционная компенсация движения 52
Трансформационная компенсация - 53
Совместное использование традиционной и трансформационной компенсации 55
3.6. Выводы по разделу 58
4. Трансформационные коды, основанные на алгебраических конструкциях 61
4.1. Преобразования для покрытий и конструктивных кодов 61
Общий алгоритм трансформационного квантования 63
Декодирование как поиск квантователя 65
4.2. Коды с низкой плотностью проверок на четность 67
4.3. Итеративное декодирование кодов с низкой плотностью проверок на четность 69
Симметричные каналы с двоичным входом 69
Декодирование ошибок канала 70
«Жесткое» декодирование 71
Декодирование по вероятностям" 72
4.4. Быстрое декодирование по надежностям 74
4.5. Многопороговое декодирование по надежностям 76
4.6. Квантование изображений кодами с низкой плотностью проверок на четность 80
Выставление надежностей при квантовании битовых плоскостей 82
Алгоритм квантования битовых плоскостей с выставлением надежностей 83
4.7. Выбор параметров кодов для квантования 85
4.8. Использование кодового квантования совместно с другими алгоритмами 87
4.9. Выводы по разделу 89
Заключение 92
Литература 95
Приложения 102
- Векторное квантование изображений
- Обобщение пространственных и спектральных преобразований
- Сжатие изображений при помощи трансформационных кодов
- Преобразования для покрытий и конструктивных кодов
Введение к работе
Актуальность темы. В связи с бурным развитием возможностей вычислительной техники и повсеместным использованием сетей передачи данных задачи обработки информации приобретают особую роль. Увеличиваются объемы обрабатываемой, хранимой и передаваемой информации, что выдвигает задачу сжатия данных на одно их наиболее важных мест среди всех задач обработки информации.
Изначально задача сжатия информации предполагала необходимость полного и однозначного восстановления данных. Разработанные алгоритмы сжатия (алгоритм Хаффмена, алгоритм Лемпеля-Зива и др.) были направлены именно на такое сжатие и могут применяться для сжатия информации произвольного вида, при этом, например, сжатие текстовой информации может составлять 3-5 раз.
С развитием и распространением цифровых средств мультимедиа (изображения, видео, аудио и т.д.) задачи сжатия стали еще более актуальны, так как медиа данные занимают несравнимо большие объемы по сравнению с текстами или программами. Степени сжатия в 3-5 раз оказались недостаточными, и, следовательно, возникла необходимость в новых методах сжатия, ориентированных именно на мультимедиа.
Сжатие изображений с потерями качества - это отдельная группа алгоритмов и программ. Такие алгоритмы позволяют сжимать статические кадры в 10 и более раз, а видеофильмы в 50-100 раз и более, используя тот факт, что различные детали изображений имеют разную важность для: человеческого зрения, а, следовательно, наименее важные детали можно опустить, повысив за счет этого степень сжатия. Существует множество алгоритмов, библиотек и стандартов, использующих те или иные принципы или модели человеческого восприятия, однако наиболее известными и широко распространенными стали так называемые алгоритмы JPEG и MPEG, в основе
которых лежит дискретное косинусное преобразование. Это произошло отчасти и потому, что сложность реализации всех составляющих алгоритмов стандарта JPEG небольшая, поэтому все другие подходы и алгоритмы, требующие существенно большего числа операций и, соответственно, мощности вычислительной техники, остались в стороне.
Однако в настоящее время, когда производительность вычислительной
техники существенно возросла по сравнению с возможностями техники во
время принятия стандартов JPEG и т.д., появились новые стандарты и
рекомендации по сжатию статических изображений и
видеопоследовательностей, ориентированные на специальные применения, например, потоковую передачу по сетям. Поэтому представляется целесообразным обратить внимание на другие подходы и методы, требующие существенно большего числа операций, если при этом возможно будет повысить качество изображений или степень сжатия. Одним из таких направлений являются алгоритмы сжатия, основанные на векторном квантовании.
В диссертационной работе рассматривается векторное квантование изображений, анализируются основные алгоритмы векторного квантования, предлагаются подходы к решению задачи векторного квантования на основе использования пространственных преобразований и аппарата теории кодирования.
Основной целью работы является: разработка и исследование методов сжатия изображений и; видеопоследовательностей на основе векторного квантования^ использующего коды, исправляющие ошибки.
Методы исследования. Для достижения цели в работе используются методы цифровой обработки сигналов, теории информации, теории
кодирования, комбинаторного анализа, алгебры и теории сложности алгоритмов.
Научная новизна диссертационной работы заключается в следующем:
Предложен метод квантования для сжатия изображений, основанный на использовании кодов, исправляющих ошибки.
Разработаны алгоритмы трансформационной компенсации, реализующие кодовое кантование для сжатия статических изображений и видеопоследовательностей с использованием кодового квантования, пространственных преобразований и декодирования по надежностям.
Предложен метод выставления надежностей, основанный на разбиении изображения на битовые плоскости, для использования в кодовом квантовании.
Предложен метод декодирования с использованием надежностей, который возможно применять для ускорения поиска в задаче нахождения квантователя,
Получены экспериментальные оценки эффективности предложенных методов на различных типах изображений и видеопоследовательностей.
Практическая ценность и реализация результатов. Практическая ценность работы определяется том, что предложенные методы позволяют получить выигрыши по сжатию или по качеству восстановленных изображений для некоторых типов изображений, а также допускают совместное использование с традиционными алгоритмами.
Результаты работы использовались в разработках ряда организаций и в учебном процессе Санкт-Петербургского Университета аэрокосмического приборостроения.
Публикации. Материалы, отражающие основное содержание и результаты диссертационной работы, опубликованы в 8 печатных работах.
Основные положения, выносимые на защиту
Алгоритм сжатия, основанный на декодировании по надежностям кодов с низкой плотностью проверок на четность.
Многопороговый алгоритм декодирования кодов с низкой плотностью проверок на четность по надежностям.
Способ использования^ пространственных и спектральных преобразований и группировок совместно с кодовым квантованием для сжатия изображений..
Структура работы. Первый раздел представляет собой постановку задачи сжатия изображений с потерей качества, обзор и анализ наиболее известных подходов и методов сжатия изображений, в том числе - основанных на векторном квантовании. В разделе приводятся основные алгоритмы и описываются проблемы, возникающие при векторном квантовании изображений.
Второй раздел посвящен применению различных преобразований для использования совместно с векторным квантованием изображений. Рассматриваются конкретные наборы преобразований, позволяющие повысить качество восстановленного изображения и уменьшить размер кодовых книг при векторном квантовании.
В третьем разделе вводится понятие кодов, инвариантных относительно преобразований, и на основе введенных определений формулируется задача кодового квантования изображений для сжатия статических изображений и видеопоследовательностей. В разделе приводятся описания алгоритмов трансформационного кодирования и трансформационной компенсации и
приводятся результаты работы алгоритмов на реальных
видеопоследовательностях.
Четвертый раздел посвящен использованию алгебраических конструкций кодов для кодового квантования изображений. В разделе рассматриваются алгоритмы декодирования кодов с низкой плотностью проверок на четность и описываются процедуры квантования, основанные на декодировании кодов, исправляющих ошибки. В данном разделе также приведены результаты использования кодового квантования с использованием алгебраических конструкций.
Векторное квантование изображений
Из двух кодовых книг равного размера для процедуры, векторного квантования изображения лучшей будем считать ту, которая при использовании дает меньшую среднеквадратичную ошибку между исходным изображением и восстановленным.
Если бы оптимальная кодовая книга для какого-то изображения состояла из одного вектора, то очевидно, что таким; вектором должен быть центр масс всех векторов-доменов исходного изображения: каждая координата вектора кодовой книги должна быть средневзвешенным значением всех соответствующих координат векторов исходного изображения. В случае, когда векторов в кодовой книге больше, явного пути указать, какими должны быть все вектора для того, чтобы кодовая книга была оптимальной, нет. Однако существуют эвристические или итеративные алгоритмы, позволяющие строить: кодовые книги для заданного множества входных векторов.
Приводимый здесь алгоритм был предложен одновременно несколькими авторами и поэтому имеет множество названий: обобщенный алгоритм Ллойда для векторного квантования (GLA, 1980 год), алгоритм Forgey, k-mean, Linde-Buzo-Gray (LBG) алгоритм [34-38]. Далее в работе алгоритм будет называться "обобщенным алгоритмом Ллойда" [38]. Обобщенный алгоритм Ллойда Обобщенный алгоритм Ллойда состоит из следующих шагов: 1. Задается, число кодовых слов N, то есть — размерность кодовой КНИГИ: 2. Неким образом выбираются N векторов, они считаются начальным заполнением кодовой книги или кодовыми словами. 3. Все множество входных векторов разбивается на подмножества (группы) по принципу близости к кодовым словам. Будем считать группой -21 кодового слова множество векторов, для которых евклидово расстояние от вектора до данного кодового слова минимально по всем кодовым словам. 4. Кодовая книга перестраивается, вычисляется новое множество кодовых слов: для каждой группы векторов вычисляется центр масс (вектор, координатами которого являются средние значения соответствующих координат векторов группы данного кодового слова), эти вектора-центры считаются новой кодовой книгой. 5. Шаги 3-4 повторяются до тех пор, пока либо изменений в кодовой книге больше не происходит, либо достигнуто заранее заданное число итераций. Алгоритм является локально-оптимальным [38]. Приведенный выше алгоритм очень сильно зависит от начальных условий, то есть, от начального заполнения кодовой книги. Чем лучше будет заполнена кодовая книга изначально, тем лучшие результаты даст алгоритм. Известно несколько способов начального заполнения кодовой книги: Равномерное заполнение. Кодовая книга заполняется векторами, в которых все элементы равны между собой. Случайное заполнение элементами из квантуемого множества. Специальное заполнение: многомерные решетки и другие алгебраические структуры. 1.5. Основные способы векторного квантования изображений Векторное квантование во временной области Векторное квантование во временной области предполагает, что цифровое изображение, представленное в виде яркостных (или яркостной и цветоразностных) компонент, разбивается домены (блоки фиксированного размера), как это было описано в п. 1.3. и изображено на Рис. 1.11, а затем полученные вектора-домены подвергаются процедуре векторного квантования -22 по обобщенному алгоритму Ллойда. В качестве начального заполнения кодовой книги используется случайное заполнение книги доменами из входного изображения [24,30]. Лучшие результаты такое векторное квантование изображений дает на изображениях, содержащих большое количество областей однородного фона без контуров и градиентных переходов. Хорошее качество получается на областях текстур. Худшие результаты алгоритм дает там, где тестовые изображения содержали контура, резкие скачки фона или градиентный переход яркости. При этом для того, чтобы обеспечить качество восстановленного изображения около 30 децибел; для изображения 512x512 точек, состоящего только из 256 градаций серого, необходимо использовать кодовую книгу размером 8 килобайт для доменов 4x4 точки. (Пример векторного квантования изображения приведен в приложении 3, Рис. 6.2.)
Основным недостатком векторного квантования является его сложность, выражаемая в терминах поиска при кодировании, и объеме памяти, требуемом для хранения кодовых книг кодера и декодера. Сложность поиска полным перебором при кодировании и размер кодовых книг растут как 0(2 ) и 0(к2кт) соответственно, где к - длина вектора и г - число бит на символ при кодировании. Более того; как уже отмечалось, сам процесс построения кодовой книги для конкретного множества доменов — задача, требующая больших вычислительных затрат.
Вычислительную сложность и объемы кодовых книг можно сократить, если кодировать изображения не за один раз целиком, аза несколько этапов, причем на каждом этапе использовать кодовые книги сравнительно небольшого объема [25,31]. Такой способ получил название древовидного векторного квантования.
Обобщение пространственных и спектральных преобразований
Это, судя по всему, связано с особенностью человеческого восприятия мелких случайных деталей: конкретное расположение деталей не важно, а важно их общее количество. Следовательно, текстуры. — хороший объект для векторного квантования.
На типах 2 и 4 большая среднеквадратичная ошибка означает неприемлемое визуальное качество восстановленного изображения. Это означает, что, примененное в общем виде векторное квантование на данных группах хороших результатов не даст.
Кодирование коэффициентов разложений, или кодирование с использованием спектральных преобразований, является в настоящее время одним из наиболее мощных средств сжатия с потерями. Но в случае векторного квантования прямое векторное квантование коэффициентов оказывается не продуктивным, так как оно использует корреляционные свойства входных данных, которых после преобразований уже нет. Также не дает хороших результатов использование битовых плоскостей, которое для скалярного квантования деталей вейвлетных разложений дает наилучший результат.
Еще одним очень существенным недостатком векторного квантования; является большой размер кодовых книг, так как кодовую книгу необходимо передавать вместе с лроквантованными значениями векторов, составляющих исходное изображение. В случае древовидных способов векторного квантования кодовые книги, тем не менее; удается существенно сократить (в количественном отношении — уменьшить до 10 раз), но все равно, даже небольшую кодовую книгу необходимо передавать.
В разделе были рассмотрены основные алгоритмы, методы, и подходы к сжатию изображений с потерями качества, особое внимание- было уделено-способам, использующим векторное квантование, и сравнению этих подходов как между собой, так и с алгоритмами, не использующими векторное квантование. Приводимый выше анализ недостатков векторного квантования изображений позволяет сформулировать открытые проблемы: 1. Традиционное векторное квантование, использованное для сжатия изображений, приводит к формированию кодовых книг больших размеров, которые необходимо передавать вместе с проквантованными значениями, что существенно снижает степени сжатия. Это означает, что степени сжатия можно значительно повысить, если избавиться от необходимости передачи кодовой книги вместе с изображением. 2. На определенных типах доменов изображений векторное квантование оказывается неэффективным и априори по качеству проигрывает любым другим алгоритмам сжатия, а следовательно, нужны какие-то способы либо выделения доменов, на которых векторное квантование использоваться не должно с последующим кодированием их другими алгоритмами, либо переведение «плохих» для векторного квантования доменов в другие, на которых векторное квантование может дать лучшие результаты. 3: Наиболее известные спектральные преобразования, используемые перед векторным квантованием изображений, не приносят ощутимых выигрышей, тем не менее, для многих типов доменов преобразования необходимы для повышения качества восстановленного изображения, и, следовательно, необходим поиск произвольных преобразований, которые возможно продуктивно использовать именно с векторным квантованием. Данная работа посвящена исследованию и разработке методов решения вышеперечисленных проблем на основе использования пространственных и спектральных преобразований и аппарата теории кодирования. 2. Векторное квантование с использованием пространственных преобразовании Как уже рассматривалось ранее, в. простейшем случае при сжатии изображений при помощи векторного квантования изображение разбивается на одинаковые блоки (домены), которые затем подаются на вход процедура векторного квантования. В зависимости от того, каким было исходное изображение, как было произведено разбиение на блоки, каким был выбран размер кодовой книги и каким был алгоритм ее формирования, по качеству восстановленные изображения будут не одинаковы. При одном и том же алгоритме формирования кодовой книги и фиксированном ее размере для разных доменов качество восстановленного изображения будет разным, причем наилучшим будет восстановление для доменов, представляющих собой ровный фон без переходов, то есть, для доменов, имеющих между собой высокую корреляцию. Пространственные преобразования Разобьем изображение на квадратные домены одинакового размера и введем множество преобразований над доменами, состоящее из следующих операций:
Сжатие изображений при помощи трансформационных кодов
Если точки покрываемого пространства являются доменами некоего изображения, то сжатие будет состоять в том, что каждый домен будет заменен на пару чисел: (к,р), где к — номер кодового слова из базиса wk WQ, а р — численное представление цепочки преобразований, приводящих слово wk в слово wl=mr..mwk , находящееся от домена на расстоянии меньше либо равном R . Пары чисел (к,р) будут сохранены. Коэффициент сжатия отдельного домена будет определяться сложностью кодирования домена и размерностью базиса W0 . Источником ошибок будет являться неполное соответствие кодовых слов кода W доменам реального изображения.
С точки зрения сжатия и последующего восстановления радиус полученного покрытия для изображения влияет на качество восстановленного изображения: чем больше радиус, тем хуже объективное качество. На радиус покрытия будут влиять как количество слов в коде W, так и расположение этих слов в пространстве относительно точек покрываемого множества.
Предположим, что разбиение изображения производилось на домены пхп . Точки-домены, полученные при таком разбиении реального видеоизображения на домены, заполнят далеко не все п2 -мерное пространство, а лишь незначительную его часть. Традиционная же задача построения покрытия требует, чтобы любая точка из пространства находилась на расстоянии не больше, чем-Л от какого-либо кодового слова матричного кода. Очевидно, что данное требование является избыточным при кодовом покрытии видеоизображений;
Рассмотрим конкретный пример. Стандартное тестовое изображение «Lena» имеет размеры 512 на 512 точек. Если использовать разбиение на домены размером 8 на 8 точек, то изображение будет представлено в виде 4096 доменов; причем все пространство, точками которого являются домены 8 на 8 точек, каждая точка является оттенком 256-серого, будет насчитывать 25664 =2 ы =2я: «10!54 точек. При использовании доменов 4 на 4 точки для того же изображения число доменов при разбиении будет равным 16384, а пространство всех возможных доменов будет содержать 25616 =28 16 =3.4 1038 точек.
На практике, более того, какие-то домены изображения могут оказаться одинаковыми (например, фоновая область изображения) или отличаться между собой незначительно, и, следовательно, число различных доменов в изображении будет еще меньше, так что использовать покрытия для всего многомерного пространства бессмысленно.
В случае видеопоследовательностей, если разбивать кадры на домены, то количество доменов увеличивается, однако, так как в подряд идущих кадрах видео имеет место наличие целых одинаковых областей (что и используется при компенсации движения при сжатии видео), то общее количество различных доменов, которые требуется передать, по-прежнему остается маленьким по сравнению со всей мощностью пространства доменов соответствующей размерности.
Все вышеизложенное означает, что для сжатия изображений могут использоваться кодовые покрытия, покрывающие не все пространство возможных доменов, а лишь некоторое множество доменов, присутствующее на конкретном; изображении, или множество доменов, наиболее типичных для? изображений.
Задача преобразований при кодовом покрытии, таким образом, как раз и будет состоять в том, чтобы перевести, преобразовать все множество доменов, которые необходимо покрыть кодом, к некоему множеству, легко описываемому или легко представляемому в виде базиса кода.
Как уже говорилось, сам способ сжатия статических изображений заключается в следующем: для каждого домена изображения производится, выбор наиболее похожего кодового слова из кода W , затем вместо самих доменов сохраняются (каким угодно образом) кодовые слова кода Ж, и именно они и используются при восстановлении изображения.
При сжатии изображения во временной і области,. как уже говорилось в подразделе Г.6., худшие результаты показывало: квантование на доменах, содержащих контура, градиентные переходы и т.п., то есть, имевших сильные пространственные различия с остальными доменами. Это означает, что для лучшей работы кодового квантования ;a необходимо либо изначально перевести домены, содержащие контура, к виду остальных доменов, либо расширить код, используемый для покрытия изображений, кодовыми словами, покрывающими плохие домены.
Преобразования для покрытий и конструктивных кодов
Коды с низкой плотностью проверок на четность являются линейными блоковыми кодами. Линейный код - это код, кодовые слова которого образуют линейное подпространство размерности к в линейном пространстве всех векторов- длины, и над кодовым алфавитом. Примером могут служить двоичные коды с проверкой на четность при записи алфавита в виде нулей и единиц, определении сложения кодовых слов как покомпонентного сложения векторов по модулю два и определении умножения кодового слова на символ алфавита как обычного умножения вектора на число.. Назовем число n длиной кода, число к — числом информационных символов и число г=-п — к — числом избыточных (проверочных) символов. Назовем скоростью кода отношение количества информационных символов к длине слова R.
Пронумеруем позиции кодового слова числами из множества N - {1,2,...и}. Информационной совокупностью кода будем назвать множество номеров позиций кодовых символов у = {j\,J2, — Jt }, 1 7 рЛ " Л - П если задание компонент кодового с лова с элементами из у однозначно определяет это слово. Двоичный код— это код, компоненты кодовых слов которого выбираются из алф авита, состоящего из двух элементов (обычно их обозначают нулем и; единицей). Любое линейное пространство задается своим базисом. Следовательно, линейный код также можно описать, задав базис соответствующего ему подпространства. Этот базис, записанный в форме матрицы, будем называть порождающей матрицей линейного кода. При этом операция; кодирования задается умножением информационного вектора на порождающую , матрицу. Подпространство можно также описать с помощью базиса ортогонального ему подпространства. Базис подпространства, ортогонального подпространству кода, записанный в виде матрицы, называется проверочной матрицей линейного кода. Она называется проверочной, так как любое слово линейного кода, умноженное на транспонированную проверочную матрицу, дает нулевой вектор. Сами строки матрицы будем называть проверками. В случае двоичных кодов, проверочная матрица задает проверки на четность данного кода, Коды с низкой плотность проверок на четность были впервые предложены Р. Галлагером в 1963 году как высокоскоростные коды с малой вероятностью ошибки для передачи по каналам с шумом [56,57]. Коды с низкой плотностью проверок на четность — это линейные коды, определяемые проверочной матрицей, содержащей в основном нулевые элементы и относительно небольшое количество ненулевых. Для случая двоичных кодов с низкой плотностью проверок на четность проверочная матрица состоит из небольшого числа единиц и нулей на всех остальных позициях матрицы. Пример проверочной матрицы с низкой плотность проверок на четность приведен на Рис. 4.4. Для всего класса кодов с низкой плотность проверок на четность [58-63] существуют декодеры, основывающиеся только на свойствах разреженности проверочной матрицы и не использующие никакие свойства самого пространства кодовых слов. Эти алгоритмы декодирования имеют низкую сложность и позволяют достичь малой вероятности ошибки при передаче в канале с аддитивным нормально-распределенным (гауссовским) шумом [56-58,64,65]. Итеративное декодирование кодов с низкой плотностью проверок на четность Рассмотрим итеративное декодирование кодов с низкой плотность проверок на четность в двоичном симметричном канале и канале с аддитивным белым гауссовским шумом. Симметричные каналы с двоичным входом Симметричный канал с двоичным входом будем называть дискретный по времени канал со следующими свойствами: Входной алфавит X состоит из двух символов, обозначаемых 0 и 1. Выходной алфавит Y может быть представлен как дискретное либо непрерывное вещественное множество чисел. Выход у в заданный отсчет времени зависит только от одного входного символа х. Для всех выходов у выполняется свойство симметрии: Р0(у) = Pi(-y)-Здесь под Рх (у) понимается плотность распределения вероятности, если Y - непрерывный выход, и условная вероятность, если Y — дискретное множество. примеры симметричных каналов с двоичным входом.
