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

На правах рукописи

Белоголовый Андрей Владимирович

КОДОВОЕ КВАНТОВАНИЕ ПРИ СЖАТИИ ВИДЕОИЗОБРАЖЕНИЙ

Специальность: 05.13.01 "Системный анализ, управление и обработка информации (в технике и технологиях)"

Автореферат диссертации на соискание ученой степени кандидата технических наук

Санкт-Петербург 2004 г.

Работа выполнена на кафедре безопасности информационных систем Государственного образовательного учреждения высшего профессионального образования "Санкт-Петербургский государственный университет

аэрокосмического приборостроения" (ГУАП)

Научный руководитель:

доктор технических наук, профессор Крук Евгений Аврамович

Официальные оппоненты:

доктор технических наук, профессор Таубин Феликс Александрович кандидат технических наук, старший научный сотрудник Бабкин Владимир Федорович

Ведущая организация:

Санкт-Петербургский институт информатики РАН

Защита состоится /КС.^_ 2004 Г. в 15 час. 00 мин. на

заседании диссертационного совета Д 212.233.02 при Государственном образовательном учреждении высшего профессионального образования "Санкт-Петербургский государственный университет аэрокосмического приборостроения" по адресу: 190000, г. Санкт - Петербург, ул. Большая Морская, д. 67.

С диссертацией можно ознакомиться в библиотеке ГУАП

Автореферат разослан

Ученый секретарь диссертационного совета

ОБЩЛЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Актуальность работы обусловлена тем, что с развитием и распространением цифровых средств мультимедиа (изображения, видео, аудио и т.д.) задачи сжатия вышли на первое место, так как медиа данные занимают несравнимо большие объемы по сравнению с текстами или программами. Степени сжатия, приемлемые для обычных данных, оказались недостаточными, и, следовательно, возникла необходимость в новых методах сжатия, ориентированных именно на мультимедиа.

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

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

Для достижения поставленной цели в работе решались следующие основные задачи и вопросы:

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

• разработка алгоритмов сжатия изображений, основанных на использовании кодах, исправляющих ошибки;

• разработка конечных декодеров для кодов в непрерывном канале;

• • исследование возможности и выгодности совместного использования

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

Методы исследования: для решения поставленных задач в работе

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

Научной новизной обладают следующие результаты работы:

• метод квантования для сжатия изображений, основанный на использовании кодов, исправляющих ошибки.

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

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

• метод декодирования с использованием надежностей, который возможно применять для ускорения поиска в задаче нахождения квантователя.

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

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

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

Апробация результатов работы.

Основные положения и результаты диссертации докладывались и обсуждались на У,У1 научных сессиях аспирантов ГУЛП (г. Санкт-Петербург 2002,2003), Ш и IV международной школе-семинаре Бикамп-01 и Бикамп-03 (г. Санкт-Петербург), а также на семинарах кафедры «Безопасность информационных систем» СПГУАП (2000-2004) и кафедры «Информационных систем» СП6ТУАП (2004).

Публикации. По теме диссертации опубликовано 8 печатных работ.

Основные положения, выносимые на защиту:

1. Алгоритм сжатия, основанный на декодировании по надежностям кодов с низкой плотностью проверок на четность.

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

3. Способ использования пространственных и спектральных преобразований и группировок совместно с кодовым квантованием для сжатия изображений.

Структура работы. Диссертационная работа изложена на 117 страницах и состоит из введения, 4-х глав с выводами, заключения, списка использованных источников литературы, включающего 72 наименования, и приложения. Основное содержание работы включает 38 рисунков и 11 таблиц.

СОДЕРЖАНИЕ РАБОТЫ

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

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

При кодировании отдельных изображений при помощи векторного квантования во временной области можно выделить 4 основных типа доменов:

1.фон без резких переходов;

2. плавные направленные переходы (градиентные переходы яркости);

3. текстуры;

4. контуры, отдельные резкие детали.

Для типов 2, 3, 4 наблюдаются очень большие среднеквадратичные ошибки. Однако на типе 3 (текстуры), большая среднеквадратичная ошибка визуально не воспринимается до тех пор, пока восстановленный объект по-прежнему представляет из себя структуру, то есть, пока нет искажения текстуры до равномерного фона. Следовательно, текстуры - хороший объект для векторного квантования. На типах 2 и 4 большая среднеквадратичная ошибка означает неприемлемое визуальное качество восстановленного изображения. Это означает, что векторное квантование, примененное в общем виде, на данных группах хороших результатов не даст.

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

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

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

1. повороты доменов на 90 градусов

2. циклические сдвиги строк и столбцов доменов

3.транспонирование (зеркальное отображение) доменов

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

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

с преобразованиями без преобразований ВЫИГ1 рыш

еж РЯХИ БЖ РБМ* БМ* РБМ*

g_airplane.bmp 29,38 32,10 28,03 30,75 1,35 1,35

g_arctichare.bmp 35,57 36,62 34,11 35,16 1,47 1,47

g_baboon.bmp 18,75 24,41 17,71 23,36 1,04 1,04

g_barbara.bmp 21,97 27,86 20,91 26,80 1,06 1,06

g_boat.bmp 24,34 29,68 23,33 28,67 1,01 1,01

g_cat.bmp 24,05 28,49 22,66 27,10 1,39 1,39

g_fruits.bmp • 27,67 31,70 26,33 30,35 1,34 1,34

g_lena.bmp 25,22 31,86 24,08 30,72 1,14 1,14

g_peppers.bmp 25,36 31,97 24,12 30,74 1,23 1,23

g_pooI.bmp 24,48 38,43 23,44 37,38 1,05 1,05

Табл. 1. Восстановление проквантованных изображений с 8 преобразованиями, размер домена - 8x8 точек, 256 слов в кодовой книге

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

Направленное формирование векторов означает, что в качестве входных векторов для процедуры векторного квантования из матриц деталей шауеЫ-разложений формируются линии коэффициентов так, как это показано на Рис.1: матрица вертикальных деталей вытягивается в линии по горизонтали, матрица горизонтальных деталей вытягивается в линии по вертикали, матрица диагональных деталей - по диагонали. В случае многоуровневых разложений матрицы деталей следующих уровней также вытягиваются в вектора направленно.

Рис. 1. Формирование векторов с использованием направленной группировки деталей

квадратные домены направленно вытянутые выигрыш

SNR PSNR SNR PSNR SNR PSNR

g_airplane.bmp 25 27,73 25,63 28,36 0,63 0,63

g_arctichare.bmp 31,29 32,34 31,92 32,97 0,63 0,63

g_baboon.bmp 16,43 22,08 16,76 22,41 0,33 0,33

g_barbara.bmp 18,65 24,54 18,86 24,75 0,21 0,21

g_boat.bmp 21,19 26,54 21,87 27,21 0,68 0,67

g_catbmp 20,2 24,64 20,54 24,98 0,34 0,34

g_fruits.bmp 23,43 27,45 23,91 27,94 0,48 0,49

g_lena.bmp 22,15 28,79 22,43 29,07 0,28 0,28

g_peppers.bmp 22,1 28,71 22,63 29,24 0,53 0,53

g_pool.bmp 19,74 33,69 19,84 33,79 0,1 0,1

Табл. 2. Выигрыши от использования направленного формирования векторов. Двухуровневое разложение, длина векторов 16,8 слов в кодовых книгах

По результатам экспериментов в случае использования кодового квантования для сжатия изображений перед самой процедурой кодового квантования имеет смысл использовать некую детерминированную группировку элементов в вектора [44]. Такая группировка может применяться как отдельно, так и в совокупности с каким-либо преобразованием, после которого будет известно, как коррелированны между собой элементы результатов преобразования. Общая схема такого подхода изображена на Рис.2, частным случаем такого декомпозиционного преобразования может являться wavelet-разложение, как это было показано ранее.

Рис. 2. Схема сжатия изображений с использованием векторного квантования, декомпозиций и преобразований

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

• со свойствами изображений как объекта квантования (типов изображений, областей и т.д.)

• с особенностями процедуры квантования

• с особенностями построенной кодовой книги (кодовых книг)

Используя такие преобразования и группировки, на тестовых изображениях

были получены выигрыши по качеству восстановленных изображений от 0.1 до 0.63 децибела при равных степенях квантования и сжатия.

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

Любой код можно рассматривать как покрытие некого множества доменов радиусом R. Тогда процесс кодового квантования можно рассматривать как отображение множества доменов в кодовые слова. Если рассматривать код как покрытие, то тогда преобразования, сохраняющие код, можно рассматривать как расширение и перегруппировку множества базисных кодовых слов, при этом, естественно, радиус покрытия R станет меньше:.

Рис. 3. Покрытие пространства кодом, инвариантным относительно преобразований

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

численное представление цепочки преобразований, приводящих слово wk в слово = т^-трМ^ , находящееся от домена на расстоянии меньше либо равном Я. Пары чисел (к,р) будут сохранены. Коэффициент сжатия отдельного домена будет определяться сложностью кодирования домена и размерностью базиса Источником ошибок будет являться неполное соответствие кодовых слов кода W доменам реального изображения. Данный подход может применяться не только для сжатия статических изображений, но и для сжатия видеопоследовательностей.

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

Пусть Ж - код, инвариантный относительно множества преобразований М, Ж0 - его базис (множество кодовых, из которого при помощи преобразований можно получить все остальные кодовые слова), и при помощи такого кода мы собираемся производить трансформационную компенсацию движения. Это означает, что каждый домен текущего кадра будет предсказываться тремя параметрами: номер кодового слова из базиса Цг0

• цепочка преобразований из М , задающая по кодовому слову из }¥0 слово, покрывающее домен радиусом Я

• каким-либо образом закодированная разность между реальным доменом и предсказанным.

Тогда задачей трансформационной компенсации будет поиск минимальной цепочки преобразований.

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

Рис. 4. Трансформационная компенсация с построением базиса по базовому кадру

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

1.Для текущего кадра проводится процедура традиционной компенсации движения. Получается разностный кадр.

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

3.Для множества доменов 5 выполняется процедура блоковой трансформационной компенсации. Получившиеся разностные блоки вставляются в разностный кадр на места блоков из множества 5.

Рис. 5. Схема работы традиционной компенсации движения совместно с трансформационной компенсацией движения

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

Процент выигрышей по расстоянию в -евклидовой метрике Процент выигрышей по числу байт, требуемому разностному JPEG

фрагмент фильма «Groundhog Day», 30 fps 2,15% 31,52%

стандартный фрагмент «Clair» 0,38% 18,27%

трейлер фильма «Phenomenon» 15 fps 24,76% 35,53%

трейлер фильма «Robison», 15 fps 18,50% 31,36%

фрагмент фильма «The Truman Show», 30 fps 8,73% 27,27%

Табл. 3. Выигрыши от использования трансформационной компенсации с формированием базиса по предыдущему кадру. 16 слов в базисе

Трансформационная компенсация на различных тестовых фрагментах.дала различные результаты: худший процент выигрышей по евклидовой метрике оказался на фрагменте «Clain>>, где нет смены сцен и нет изменения больших областей. Лучшими результатами обладал фрагмент, представляющий собой трейлер фильма и имеющий частые смены сцен, наплывы кадров и прочие видеоэффекты.

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

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

Трансформационная компенсация может проводиться не только на видеопоследовательностях, но и на отдельных изображениях, так как базис для кода

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

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

Пусть есть некое пространство С и некий код W, полностью покрывающий пространство С радиусом Я. Это означает, что для любой точки пространства С найдется кодовое слово кода W, расстояние от которого до точки пространства не превышает Я:

Зи>еЖ: Усе С, <1(с,™)<К

Пусть С - пространство, точками которого являются реальные домены изображения и пусть есть набор обратимых преобразований М, определешхый над множеством точек пространства С так, что результат преобразований из М всегда принадлежит пространству С:

Ус'е С',те М:с = тс', се С

Рис. 6. Преобразования, сохраняющие расстояние

Таким образом, любую точку из пространства С можно при помощи преобразований из М перевести в точку пространства С, где она будет покрыта кодом Ж с радиусом Я, и следовательно, использование кодового слова из Ж в

качестве квантователя для точек вида не будет давать ошибку

квантования больше, чем Я.

Тогда можно сформулировать общий алгоритм трансформационного квантования:

• Каждый домен х; изображения отображается при помощи преобразований в точку С,- пространства С, покрытого кодом W.

• В пространстве С точка с-, квантуется ближайшим к нему кодовым словом , принадлежащим коду W.

При квантовании точек пространства возникает задача поиска ближайшего кодового слова для произвольной точки пространства. В общем случае эта задача может быть решена полным перебором всех кодовых слов. Но предположим, что есть некий код второго уровня, покрывающий пространство. Тогда, по аналогии с помехоустойчивым кодированием, можно рассматривать произвольную точку пространства с как некое кодовое слово а с добавленным вектором ошибки е: а = с+е,се С

Будем назвать весом ошибки расстояние от точки, соответствующей вектору ошибки до нулевого вектора (вектора, элементами которого являются нули): = ¿(е,0)

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

е:а = с + е,се С,м(е)<й

В терминах помехоустойчивого кодирования эта задача может быть описана как задача декодирования кода С в радиусе до Я .

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

Для кодов с низкой плотность проверок на четность предлагается быстрый итеративный алгоритм декодирования - многопороговое декодирование.

Будем называть множеством множество символов принятого вектора,

которые входят в т -ю проверку: Н(т) = {п Нт п = 1} , где Н - проверочная матрица кода с низкой плотностью проверок на четность. Будем называть множеством М(п) множество проверок, в которых участвует л -й символ

принятого вектора:

Общая схема работы многопорогового декодера является следующей:

• Инициализация декодера: для всех элементов принятого вектора У) вычисляется жесткое решение Л-,- и надежность Л?,-, надежность является абсолютным значением У), а также для всех те Л/(и) присваиваются

• Для каждой итерациивычисляется пороговое значение Т1Щ'. Производится вычисление новых значений надежностей проверок и

символов: для всех п и тнеЛ/(л) вычисляются суммы

Для

ЕЛЧт)\л

всех п

и

вычисляются

те //(и)

значения

вычисляются

У.. ига.

ТП ,п

гт.л=к+ I (-1)

т'еМ{п)\т

Для тех символов, для которых новое значение надежности оказывается меньше порога 77Л?,-, происходит изменение текущих значений символов «жесткого» решения надежностей проверок и символов на новые значения, а новое значение надежности принимается равным абсолютному значению пересчитанной надежности. Водится «зона неопределенности»: для всех остальных символов если значение надежности оказалось меньше нуля, надежность принимается равной нулю: для всех п вычисляются >0

7 Г <тк X

2 (-1)5-"Ут.птш, СЛ=Г

4(п)\т [1<

• Декодирование итеративно продолжается до тех пор, пока вектор С не станет кодовым словом или не будет выполнено заданное число итераций.

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

и

Рис. 7. Вероятность ошибки при декодировании (2048,1649)-кода с низкой плотностью проверок на четность при помощи различных декодеров для различных отношений сигнал/шум в канале

Применительно к изображением алгоритм используется следующим образом.

Пусть {Аг(} - яркостные компоненты изображения, которые будут подвергаться квантованию, - коды с низкой плотностью проверок на

четность, N — чисто бит, требуемых для двоичного представления {Л"(} . Будем называть уровнями квантования поиск квантователей для отдельных битов, из которых потом будут восстанавливаться яркостные компоненты . Число

уровней квантования также будет равно N . Через (а}, обозначим функцию

выделения I -ГО бита двоичного представления числа а, (а^ - старший бит. Тогда алгоритм квантования с выставлением надежностей может быть сформулирован следующим образом:

На первом уровне квантования формируется множество бт{х]}, где дс?

- старшие биты чисел X¡, х| и множество надежностей битов

{/,'}. Надежности битам выставляются с учетом исходных значений X,-по формуле: формируются вектора,

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

которого являются вектора битов

• На каждом последующем уровне квантования к, 2<k<N, вычисляются разности rf = Xt — ' 2N~m , формируется множество бит {•£*}, где

X,* = j ' '^ ^ ^ и выставляются надежности этим битам

/*=(/}* — 2N~k + х*)2 . Из пар (xf,/*) аналогично формируются вектора, являющиеся входными данными для декодера по надежностям, а затем производится декодирование по надежностям в коде Сt , результатами

которого являются вектора битов х* .

После прохождения всех N уровней будут получены проквантованные значения xf , которые будут считаться составляющими битовых плоскостей изображения. Так как коды Q являются алгебраическими структурами (линейными

кодами), то для восстановления всего кодового слова с = {с0,...сл.1} необходимо знать информационную совокупность слова с, вектор {с^>•••Cj-, } кода С,-.

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

Так как кодовое квантование битовых плоскостей с выставлением надежностей в работе оперирует доменами изображения, то есть возможность использовать его совместно с каким-либо иным алгоритмом сжатия, использующим разбиение изображения на домены, например, алгоритмом JPEG, по следующему принципу:

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

• Все домены изображения сжимаются при помощи кодового квантования, а затем разности между исходными доменами и восстановленными после кодового квантования кодируются

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

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

• процент выигрышей по числу байт, требуемому разностному JPEG выигрыш по общему сжатию, байт SNR

g_airplane.bmp 4.37 % 500 37.25

g_arctichare.bmp 0.07 % 0 41.84

g_baboon.bmp 51.10% 16500 33.02

g_barbara.bmp 14.72 % 3000 33.42

g_boat.bmp 21.00% 4000 33.38

g_cat.bmp 10.25 % 1800 35.35

g_fruits.bmp 4.83 % 800 35.29

gjcna.bmp 5.27 % 800 32.19

g_peppers.bmp 4.52 % 800 32.89

g_pool.bmp 0.76 % 0 30.96

Табл. 4. Выигрыши от использования кодового квантования совместно с алгоритмом

JPEG

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

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ

В работе были получены следующие основные результаты:

1. Проведен сравнительный анализ преимуществ и недостатков наиболее известных алгоритмов векторного квантования по сравнению с алгоритмами, не использующими векторное квантование, сформулированы открытые проблемы.

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

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

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

5. Предложен метод кодового квантования изображений, основанный на алгебраической теории кодов, исправляющих ошибки. Данный метод был

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

6. Предложен алгоритм многопорогового декодирования по надежностям для кодов с низкой плотностью проверок на четность, обладающий низкой сложностью, и при этом улучшающий качество декодирования кодов как в гауссовском канале, так и при кодовом квантовании изображений по сравнению с другими алгоритмами декодирования по надежностям.

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Белоголовый А.В., Использование спектральных преобразований и разложений в сочетании с векторным квантованием для сжатия изображений. // VI Научная сессия аспирантов СПбГУАП: Тез. докл.,- СПб, 2003. стр

2. Белоголовый А.В. Чернышев В.А., Использование градиентных переходов совместно с многоуровневым векторным квантованием или алгоритмом JPEG при сжатии изображений. // Труды конференции «Четвертая международная молодежная школа-семинар БИКАМП'ОЗ», СПб, 2003, стр.159 - 162.

3. Белоголовый А.В., Ускорение поиска в компенсации движения при сжатии видеоинформации. // Труды конференции «Третья международная молодежная школа-семинар БИКАМП'01», СПб, 2001, стр. 145 - 146.

4. Белоголовый А.В., Ефимов А.Г., Использование пространственных преобразований для компенсации движения. // Труды конференции «Четвертая международная молодежная школа-семинар БИКАМП'ОЗ», СПб, 2003, стр. 155 -157.

5. Белоголовый А.В., Применение кодов, исправляющих ошибки, для сжатия видеоизображений. // Тезисы докладов Второй международной молодежной школы-семинара БИКАМП'99, СПб, 1999, стр. 119.

6. Белоголовый А.В. Декодирование линейных блоковых кодов при помощи механизма надежностей // XXIV Всероссийская молодежная научная конференция «Гагаринские чтения», М. 1998, стр. 68.

7. Белоголовый А.В., Фомин А.Д., Двуступенчатое декодирование по информационным совокупностям. // Тезисы докладов Первой международной молодежной школы-семинара БИКАМП'99, СПб, 1998, стр. 55 - 57.

8. Белоголовый А.В., Козлов Л.В., Приоритетное транспортное кодирование для передачи видеоизображений. // Труды конференции «Четвертая международная молодежная школа-семинар БИКАМП'ОЗ», СПб, 2003, стр. 157 - 158.

Формат 60x84 1/16. Бумага офсетная. Печать офсетная. Тираж 100 экз. Заказ

Отдел оперативной полиграфии ГОУ ВПО «ГУАП» 190000, Санкт-Петербург, ул. Б. Морская, 67

»-8170

Введение

1. Векторное квантование при сжатии изображений

1.1. Сжатие изображений с потерями. Постановка задачи^

1.2. Обзор известных подходов

Сжатие, основанное на ДКП;

Сжатие, основанное на ДВП

Сравнение работы алгоритмов

1.3. Векторное квантование изображений

1.4. Построение кодовых книг для векторного квантования

Обобщенный алгоритм Ллойда

1.5. Основные способы векторного квантования изображений

Векторное квантование во временной области

Векторное квантование в спектральной области

1.6. Сравнение векторного квантования изображений с другими алгоритмамиЗО

1.7. Выводы по разделу

2. Векторное квантование с использованием пространственных преобразований

2.1. Использование преобразований для компактного задания кодовых книг 33 Пространственные преобразования

2.2. Специальное формирование векторов для процедуры векторного квантования

Направленное формирование векторов

2.3. Обобщение пространственных и спектральных преобразований

2.4. Выводы по разделу

3. Трансформационные коды для сжатия изображений

3.1. Определение трансформационного кода

3.2. Трансформационный код как покрытие видеоизображения

3.3. Сжатие изображений при помощи трансформационных кодов

3.4. Трансформационное квантование кодовой книгой как способ сжатия статических изображений;

Выбор преобразований

Расширение множества преобразований

3.5. Трансформационная компенсация как сжатие видеопоследовательностей

Традиционная компенсация движения^

Трансформационная компенсация■

Совместное использование традиционной и трансформационной компенсации

3.6. Выводы по разделу

4. Трансформационные коды, основанные на алгебраических конструкциях

4.1. Преобразования для покрытий и конструктивных кодов

Общий алгоритм трансформационного квантования

Декодирование как поиск квантователя

4.2. Коды с низкой плотностью проверок на четность

4.3. Итеративное декодирование кодов с низкой плотностью проверок на четность

Симметричные каналы с двоичным входом

Декодирование ошибок канала

Жесткое» декодирование

Декодирование по вероятностям"

4.4. Быстрое декодирование по надежностям

4.5. Многопороговое декодирование по надежностям

4.6. Квантование изображений кодами с низкой плотностью проверок на четность

Выставление надежностей при квантовании битовых плоскостей

Алгоритм квантования битовых плоскостей с выставлением надежностей

4.7. Выбор параметров кодов для квантования

4.8. Использование кодового квантования совместно с другими алгоритмами

4.9. Выводы по разделу

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

Изначально задача сжатия информации предполагала необходимость полного и однозначного восстановления данных. Разработанные алгоритмы сжатия (алгоритм Хаффмена, алгоритм Лемпеля-Зива и др.) были направлены именно на такое сжатие и могут применяться для сжатия информации произвольного вида, при этом, например, сжатие текстовой информации может составлять 3-5 раз.

С развитием и распространением цифровых средств мультимедиа (изображения, видео, аудио и т.д.) задачи сжатия стали еще более актуальны, так как медиа данные занимают несравнимо большие объемы по сравнению с текстами или программами. Степени сжатия в 3-5 раз оказались, недостаточными, и, следовательно, возникла необходимость в новых методах сжатия, ориентированных именно на мультимедиа.

Сжатие изображений с потерями качества - это отдельная группа алгоритмов и программ. Такие алгоритмы позволяют сжимать статические кадры в 10 и более раз, а видеофильмы в 50-100 раз и более, используя тот факт, что различные детали изображений имеют разную важность для человеческого зрения, а, следовательно, наименее важные детали можно опустить, повысив за счет этого степень сжатия. Существует множество алгоритмов, библиотек и стандартов, использующих те или иные принципы или модели человеческого восприятия, однако наиболее известными и широко распространенными стали так называемые алгоритмы JPEG и MPEG, в основе которых лежит дискретное косинусное преобразование. Это произошло отчасти и потому, что сложность реализации всех составляющих алгоритмов стандарта JPEG небольшая, поэтому все другие подходы и алгоритмы, требующие существенно большего числа операций и, соответственно, мощности вычислительной техники, остались в стороне.

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

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

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

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

Научная новизна диссертационной работы заключается в следующем:

1. Предложен метод квантования для сжатия изображений, основанный на использовании кодов, исправляющих ошибки.

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

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

4. Предложен метод декодирования с использованием надежностей, который возможно применять для ускорения поиска в задаче нахождения квантователя.

5. Получены экспериментальные оценки эффективности предложенных методов на различных типах изображений и видеопоследовательностей.

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

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

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

Основные положения, выносимые на защиту

1. Алгоритм сжатия, основанный на декодировании по надежностям кодов с низкой плотностью проверок на четность.

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

3. Способ использования пространственных и спектральных преобразований и группировок совместно с кодовым квантованием для сжатия изображений.

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

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

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

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

4.9. Выводы по разделу

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

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

2. Степень сжатия; непосредственно от квантования определяется скоростями используемых кодов: чем ниже скорость - тем, выше сжатие. Однако при размере доменов 8x8 точек длина кодового слова равна 64, и размерность низкоскоростных кодов оказывается слишком маленькой для обеспечения существенного выигрыша в качестве восстановленных изображений, а, следовательно, необходимо ввести в рассмотрение домены больших размеров и более длинные коды.

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

4. Алгоритм дает различный эффект по качеству на различных типах доменов. Наилучшие результаты получаются на доменах с ровным фоном или плавным переходом яркости и текстурах. Тем не менее, как и все ранее рассмотренные алгоритмы кодового квантования, оперируя блоками? (доменами) изображений, алгоритм допускает совместную работу с другими алгоритмами сжатия, использующими блоки, например, алгоритмом JPEG.

Предложенный в разделе алгоритм многопорогового декодирования кодов, с низкой плотностью проверок на четность, при сложности декодирования в 10 раз меньшей, чем у традиционных алгоритмов, позволяет в гауссовском канале получить вероятность ошибки декодирования всего на 0.10.2 децибела хуже, чем локально-оптимальные алгоритмы. По сравнению с быстрыми алгоритмами декодирования при практически одинаковой сложности многопороговое декодирование выигрывает 0.3-0.4 децибела по вероятности ошибки.

Схема совместного использования кодового квантования с алгоритмом JPEG, предложенная в разделе, позволяет на 5 процентах доменов получить выигрыши в степени сжатия по сравнению с алгоритмом JPEG на изображениях в среднем, а на отдельных изображениях выигрыши по сжатию могут были получены более чем на 50 процентах доменов.

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

По материалам раздела были получены следующие результаты:

1. Предложен метод кодового квантования изображений, основанный на выставлении надежностей битам, полученным при разбиении изображения на битовые плоскости.

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

3. Предложена схема совместного использования кодового квантования с алгоритмом JPEG.

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

Заключение

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

В работе были получены следующие основные результаты:

1. Проведен сравнительный анализ преимуществ и недостатков наиболее известных алгоритмов векторного квантования по сравнению с алгоритмами, не использующими векторное квантование, сформулированы открытые проблемы.

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

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

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

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

6. Предложен алгоритм многопорогового декодирования по надежностям для кодов с низкой плотностью проверок на четность, обладающий низкой сложностью, и при этом улучшающий качество декодирования кодов как в гауссовском канале, так и при кодовом квантовании изображений по сравнению с другими алгоритмами декодирования по надежностям.

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

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

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

В сочетании с кодированием на транспортном уровне сетей передачи данных [70,71] и многоуровневым кодовым квантованием за счет выбора скоростей используемых кодов и их согласованием с параметрами системы передачи данных по сети можно получить дополнительные параметры для оптимизации объективным качеством восстановленного изображения при передаче.

Зачастую в задачах компьютерной графики возникает необходимость синтезировать специальные изображения, например — текстуры [36]. Текстуры являются особым классом изображений или областей изображений. С одной стороны, сами по себе они не несут существенной информации для человеческого глаза, а с другой стороны плохо поддаются формальному описанию. Существует целый ряд алгоритмов синтеза текстур по фрагментам и образцам. Кодовое квантование может применяться для синтеза текстур, при этом дополнительные выигрыши могут быть получены за счет того, что можно компактно хранить образцы (кодовые книги) при помощи преобразований и использовать алгебраические конструкции кодов.

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

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

1. Pennebaker William В., Mitchel Joan L., JPEG still image data compression standard, - NY, 1993. - 638 p.

2. Watanabe H., chairman, Information Technology Coding of moving pictures and associated audio at up to about 1.5 Mbit/s - Part 2: Video, ISO/IEC 11172-2:1993, -International Organization for Standardization, Geneva, Switzerland, 1993. — 112 p.

3. Koenen R., editor, Overview of the MPEG-4 Standard, ISO/IEC JTC1/SC29/WG11, No 3931, Januaiy 2001, 69 p.

4. Witten I., Neal R., Cleary J. Arithmetic Coding For Data Compression. // Communications of the ACM, vol. 30, no. 6, June 1987, pp.520-540*

5. Huffman D., A Method for the Construction of Minimum-Redundancy Codes. // Proceedings of IRE, vol:40, N9, September 1952, pp. 1098-1101.

6. Long D., Jia W. Optimal Maximal Prefix Coding and Huffman Coding. // Proceedings of The Seventh International Conference on Distributed Multimedia Systems, Taipei, Taiwan, Sept. 26-28, 2001, pp. 101-107.

7. Ziv J., Lempel A. A Universal Algorithm for Sequential Data Compression. // IEEE Transactions on Information Theory, Vol. IT-23, No. 3, May 1977, pp.337-343*.

8. Ziv J., Lempel A., Compression of Individual Sequences via Variable-Rate Coding. // IEEE Transactions on Information Theory, Vol. IT-24, No. 5, Sept. 1978, pp.530-536.

9. F. M. Ji Willems, Y. M. Shtarkov, and T. J. Tjalkens, "The context-tree weighting method: basic properties," IEEE Trans. Info. Theory, vol. IT-41, May 1995, pp. 653 — 664.

10. Da Silva E. А. В., Sampson D. G., Ghanbari M., Image coding using successive approximation wavelet vector quantization. // Proceedings of ICASSP, volume 4, May 1995, pp 2201-2204:

11. De Natale, F.G.B.; Desoli, G.S.; Fioravanti, S.; Giusto, D.D. An Edge-based Splitting Criterion for Adaptive Transform Coding. // In Proceedings of IEEE ICASSP93, vol. 5, 1993, pp. 409-412.

12. Lepsoy S., Oien G. E., Ramstad T. A. Attractor Image Compression with a Fast Non-iterative Decoding Algorithm. // In Proceedings of IEEE ICASSP93, vol. 5,1993, pp 337-340.

13. Gharavi-Alkhansari M., Huang Т., Generalized image coding using fractal-based methods. // in Proc. ICIP, 1994, pp. 440-443.

14. Subhasis Saha, Image Compression from DCT to Wavelets: A Review. http://www.acm.org/crossroads/xrds6-3/sahaimgcoding.html

15. Park H. W., Lee Y. L., A Postprocessing Method for Reducing Quantization Effects in Low Bit-Rate Moving Picture Coding. // IEEE Transactions on Circuits and Systems for Video Technology, vol. 9, no. 1, Feb. 1999, pp 161-171.

16. Wiegand T, editor. Text of Final Committee Draft of Joint Video Specification (ITU-T Rec. H.264 | ISO/IEC 14496-10 AVC), Klagenfurt, AT, July 2002 191 p.

17. Strang G., Nguyen Т., Wavelets and Filter Banks, Wellesley-Cambridge Press, 1996,-490 p.

18. Skodras A., Christopoulos C., Ebrahimi Т., The JPEG 2000 Still Image Compression Standard. // IEEE Signal Processing Magazine, September 2001, pp 36 -58.

19. Ping Yu Venetsanopoulos, A.N. Hierarchical Finite-State Vector Quantization for Image Coding // IEEE Transactions on Communications, vol. 42, November1994, pp 3020-3026.

20. Watanabe H., chairman, Information technology — JPEG 2000 image coding system Part 1: Core coding system, ISO/IEC 15444-1:2000, 2002-07-31, http://www.ipeg.org/public/fcdl 5444-1 .pdf, - 226 p.

21. Watanabe H., chairman, Information technology JPEG 2000 image coding system - Part 3: Motion JPEG 2000, ISO/IEC 15444-3:2000, 2002-09-26, http://www.ipeg.org/public/fcdl5444-3.pdf, -35 p.

22. J. Ziv, "Coding of sources with unknown statistics—I: Probability of encoding error," IEEE Trans. Info. Theory, vol. IT-18, May 1972, pp. 384 389.

23. H. Abut, editor, Vector Quantization. IEEE Reprint Collection, IEEE Press, Piscataway, NJ, May 1990. 566 p.

24. Vaishampayan V. A., Sloane N. J. A., Servetto S. D., Multipledescription vector quantization with lattice codebooks: Design and analysis, // IEEE Transactions on Information Theory, vol. 47, no. 5, July 2001, pp. 1718 1734.

25. Gray R. M. Fundamentals of Vector Quantization. http://www-isl.stanford.edu/~gray/compression.html

26. Li J., Gray R. M., Olshen R., Joint Image Compression and Classification with Vector Quantization and Two Dimentional Hidden Markov Model // Data Compression Conference, IEEE Computer Society TCC, 1999, pp 23-32.

27. Hung A. C., Tsern E. K., Meng Т. H., Error-resilient pyramid vector quantization for image compression. // IEEE Trans, on Image. Process., voL 7, Oct. 1998, pp. 1373- 1386.

28. Lin J.-H., Vitter J. S., Nearly Optimal Vector Quantization via Linear Programming. // Data Compression Conference, IEEE Computer Society TCC. 1992, pp. 22-31.

29. Cosman P. C., Oehler K. L., Riskin E. A., Gray R. M. Using vector quantization for image processing. // Proc. of the IEEE, vol. 81, no. 9, September 1993, pp. 13261341.

30. Bayazit U., Pearlman W. A., Variable-Length Constrained Storage Tree-Structured Vector Quantization. IEEE Trans. Image Processing, vol. 8 no. 3, March 1999, pp 321-331.

31. Bradley, J.N. Brislawn, C.M., Wavelet transform-vector quantization compression of supercomputer ocean models. // Data Compression Conference, 1993. DCC, May 1993, pp 224-233.

32. Raffy, P., Antonini M., Barlaud M., Distortion-Rate Models for Entropy-Coded Lattice Vector Quantization. // IEEE Transactions on Image Processing, vol. 9, number 12, 2000, pp. 2006-2017.

33. Garey M. R., Johnson D. S., Witsenhausen H. S., The complexity of the generalized Lloyd-Max problem. // IEEE Trans. Inform. Theory, vol. 28, no. 2, 1982, pp. 255-256.

34. Gersho A., Gray R.M., Vector Quantization and Signal Compression, Kluwer Academic Publishers, January 1992, 732 p.

35. Li-Yi Wei Marc Levoy, Fast Texture Synthesis using Tree-structured Vector Quantization, Stanford University, http://graphics.stanford.edu/proiects/texture/

36. Linde Т., Buzo A., Gray R. M., An Algorithm for Vector Quantization // IEEE Trans, on Communications, vol. 28, no. 1, 1980, pp. 84-95.

37. Lloyd S. P. Least Square Quantization in PCM. // IEEE Transactions on Information Theory, IT-28. March 1982, pp. 127-135.

38. V.V.Aleksandrov and N.D.Gorsky, Image Representation and Processing: A Recursive Approach. Kluwer Academic Publishers, 1993, 196 pp.

39. Э.Маделунг. Математический аппарат физики. М.: Наука, 1968, - 618 стр.

40. Ф.Наттерер. Математические аспекты компьютерной томографии. М.: Мир. 1990.-288 с.

41. Э.Хеннан. Многомерные временные ряды. М. Мир. 1974, 576 с.

42. Трахтман A.M., Трахтман В.А. Основы теории дискретных сигналов на конечных интервалах. — М.: Советское радио, 1975. — 208 с.

43. Белоголовый А.В., Использование спектральных преобразований и разложений в сочетании с векторным квантованием для сжатия изображений. // VI Научная сессия аспирантов СПбГУАП: Тез. докл.,- СПб, 2003. стр

44. Knudsen K.S., and Bruton L.T., Moving Object Detection and Trajectory Estimation in the Transform/Spatiotemporal Mixed Domain. // IEEE International Conference on Acoustics, Speech, and Signal Processing, 1992. ICASSP-92, vol. 3, 1992, 533-536.

45. Белоголовый A.B., Ускорение поиска в компенсации движения при сжатии видеоинформации. // Труды конференции «Третья международная молодежная школа-семинар БИКАМП'01», СПб, 2001, стр. 145 146.

46. Белоголовый А.В;, Ефимов А.Г., Использование пространственных преобразований для компенсации движения. // Труды конференции «Четвертая международная молодежная школа-семинар БИКАМП'ОЗ», СПб, 2003, стр. 155 157.

47. Блейхут Р. Теория и практика кодов, контролирующих ошибки. — М.: Мир, 1986.-576с.

48. Ф. Дж. Мак-Вильямс, Н. Дж. А. Слоэн, Теория кодов, исправляющих ошибки, М., Связь, 1979, 744с.

49. Дж.Кларк,мл., Дж.Кейн, Кодирование с исправлением ошибок в системах цифровой связи, М. Радио и связь, 1987, - 391с.

50. Питерсон У., Уэлдон Э. Коды, исправляющие ошибки. М.: Мир, 1976.-594с.

51. Белоголовый А.В. Применение кодов, исправляющих ошибки, для сжатия видеоизображений. // Тезисы докладов Второй международной молодежной школы-семинара БИКАМП'99, СПб, 1999, стр. 119.

52. Gallager R., Low-density Parity-Check codes. PhD thesis, 1963., 90 p.

53. Gallager R. G., Low-density parity-check codes. // IEEE Trans, on Inform. Theory, vol. IT-8, Jan. 1968, pp. 21-28.

54. MacKay D.J.C., Neal R.M., Near Shannon limit performance of low density parity check codes. // IEE Electronics Letters, vol. 32, no. 18, 29 Aug. 1996, pp. 1645-1655.

55. Djurdjevic I., Xu J., Abdel-Ghaffar K., Lin S. A class of low-density parity-check codes constructed based on Reed-Solomon codes with two information symbols. // IEEE Communications Letters, vol. 7, no. 7, July 2003. pp. 317-319.

56. Kou Y., Lin S., Fossorier M. P.C., Low Density Parity Check Codes Based on Finite Geometries: A Rediscovery and New Results // IEEE Transactions on Information Theory, vol. IT-47, Nov., 2001. pp. 2711-2736.

57. Chung; S. Forney G.D., Richardson T.J., Urbanke R., On the design of low-density parity-check codes within 0.0045 dB of the Shannon limit. // IEEE Comm. Letters, vol.5, Feb. 2001., pp,58-60.

58. Rosenthal J., Vontobel P. O., Constructions of regular and irregular LDPC codes using Ramanujan graphs and ideas from Margulis. // Proc. IEEE ISIT, Washington, DC, USA, Jun. 24-29,2001, p.5.

59. T. J. Richardson, M. A. Shokrollahi, and R. L. Urbanke, "Design of capacity approaching irregular low-density parity-check codes," IEEE Trans. Information Theory, vol.47, pp.619-637, Feb. 2001.

60. Fossorier M.P.C., Mihaljevic M., Imai H., Reduced complexity iterative decoding of low-density parity check codes based on belief propagation. // IEEE Transactions on Communications, 47(5), May 1999, pp.673-680.

61. Robertson P., Villebrun E., and Hoeher P., A comparison of optimal and sub-optimal map decoding algorithms operating in the log domain // Proc. of IEEE ICC-95, vol. 2, June 1995. pp. 1009 1013.

62. В.Д.Колесник, Е.Т.Мирончиков, Декодирование циклических кодов. — М. Связь, 1968,-252 с.

63. V. D. Kolesnik, Probability decoding of majority codes. // Prob. Peredachi Inform., vol. 7, July 1971, pp. 3-12.

64. A.B.Белоголовый. Декодирование линейных блоковых кодов при помощи механизма надежностей // XXIV Всероссийская молодежная научная конференция «Гагаринские чтения», М. 1998, стр. 68.

65. Белоголовый А.В., Фомин А.Д., Двуступенчатое декодирование по информационным совокупностям. // Тезисы докладов Первой международной молодежной школы-семинара БИКАМП'99, СПб, 1998, стр. 55 57.

66. Кабатянский Г.А., Крук Е.А. Кодирование уменьшает задержку // В кн. «X Всесоюзная школа-семинар по вычислительным сетям» Ч.2.- Москва-Тбилиси.-1985.- стр.23-26.

67. Белоголовый А.В., Козлов А.В., Приоритетное транспортное кодирование для передачи видеоизображений. // Труды конференции «Четвертая международная молодежная школа-семинар БИКАМП'ОЗ», СПб, 2003, стр. 157 158.

68. Freeman W. Т., Jones T.R., Pasztor Е. С., Example-based Super-resolution. // MERL, Mitsubishi Electric Research Labs. 201 Broadway, Cambridge, MA 02139 TR-2001-30 August 2001, http://www.merl.com/