автореферат диссертации по радиотехнике и связи, 05.12.04, диссертация на тему:Методы и устройства преобразования и квантования вейвлет-спектров при внутрикадровом сжатии цифровых телевизионных сигналов

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

Мочалов Иван Сергеевич

МЕТОДЫ И УСТРОЙСТВА ПРЕОБРАЗОВАНИЯ И КВАНТОВАНИЯ ВЕЙВЛЕТ-СПЕКТРОВ ПРИ ВНУТРИКАДРОВОМ СЖАТИИ ЦИФРОВЫХ ТЕЛЕВИЗИОННЫХ СИГНАЛОВ

Специальность 05.12.04 Радиотехника, в том числе системы и устройства телевидения

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

г дпр ^

Москва-2012

005019903

005019903

Работа выполнена на кафедре динамики электронных систем Ярославского государственного университета им. П.Г. Демидова

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

Приоров Андрей Леонидович

Официальные оппоненты: доктор технических наук

Бехтин Юрий Станиславович

кандидат технических наук Салтыков Константин Евгеньевич

Ведущая организация: ЗАО «МНИТИ»

Защита состоится « 10 » мая 2012 г. (в аудитории А-448) в 15 час. 00 мин. на заседании Совета по защите докторских и кандидатских диссертаций Д 219.001.01 при Московском техническом университете связи и информатики по адресу: Москва, Авиамоторная, д. 8а.

С диссертацией можно ознакомиться в библиотеке ФГОБУ ВПО МТУСИ.

Отзывы на автореферат в двух экземплярах, заверенные печатью, просим направлять по адресу: 111024, Москва, ул. Авиамоторная, 8а. Совет по защите докторских и кандидатских диссертаций Д 219.001.01 при ФГОБУ ВПО МТУСИ.

Автореферат разослан « 1 » ьлул^Х 2012 г.

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

кандидат технических наук, доцент /[ / __ Л Р.Ю. Иванюшкин

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

Актуальность темы. На протяжении последнего десятилетия объем видеоинформации, передаваемой через каналы связи, непрерывно растет. Совершенствование алгоритмов видеосжатия позволило сделать видеоконференцсвязь доступной широкому кругу пользователей. Одновременно с этим сегодня во всем мире успешно внедряются системы цифрового телевидения. При этом известно, что в видеопотоке основное место занимают, так называемые, I-кадры, сжимаемые без использования дополнительной информации, как статические изображения, поэтому рассмотрение проблем сжатия статических изображений является важной задачей в рамках разработки систем видеосжатия. В частности, мировой стандарт MPEG-2 использует стандарт сжатия изображений JPEG для I-кадров. Стандарт MPEG-4 part 10 (AVC) использует уже более сложную схему сжатия 1-кадров.

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

Степень разработанности проблемы.

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

Наиболее известными в данной области являются работы Вудса Р., Гонсалеса Р., Зубарева Ю.Б., Прэтта У., Сойфера В.А., Ярославского Л.П.

Большую роль в современных алгоритмах кодирования с преобразованием играют вейвлет-преобразования, которые обеспечивают частотную и временную локализацию, а так же возможность обрабатывать сигнал на разных масштабах. В этой области широко используются работы Ваттерли М., Добеши И., Ковачевич Д., Малла С., Стренга Г., Чуй К.

Непосредственно алгоритмам сжатия изображений и видео посвящены работы российских ученых: Чобану М.К., Умняшкина C.B., Бехтина Ю.С., Радченко Ю.С., а также зарубежных авторов: Pearlman W.A., Said A., Shapiro J.M., Taubman D., Wheeler F.W., Xiong Z., Ramchandran K.

Наряду с вейвлет-преобразованием кратности разложения 2 используется кратность M выше, чем 2. В развитии теории М-полосных банков вейвлет-фильтров большую роль сыграли работы таких авторов, как Дворкович В.П., Дворкович A.B., Приоров АЛ., Burus C.S., Gopinath R.A., Tewfïk А.Н., Vetterli M., Zou H.

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

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

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

- анализ выбранного энтропийного кодера БРШТ (БТМО в контексте современных алгоритмов кодирования;

- разработка алгоритма квантования вейвлет-коэффициентов, позволяющего повысить качество изображений по метрике Пик ОСШ при фиксированном числе бит по сравнению со скалярным квантованием;

- разработка преобразования, более эффективного для решаемой задачи, чем вейвлет-преобразование.

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

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

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

Научная новизна

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

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

3) Разработка преобразования для сжатия с потерями, основанного на нелокальном кодировании с предсказанием и квантованием в вейвлет-области.

Практическая значимость

Разработан и реализован алгоритм оценки параметров аддитивного и мультипликативного шумов. Разработанный алгоритм внедрен в организации ООО «Гипроприбор-Инвест» для оптимизации параметров алгоритмов сжатия видеоданных с камер наружного наблюдения с учетом действия шумов.

Разработан и внедрен в организации ООО «Информационные системы Криста» алгоритм двумерного нелокального предсказания для предсказания значений двумерных индикаторов на прогнозный период.

Разработанные методы носят исключительную практическую направленность и применимы для использования в системах сжатия изображений. Их совместное применение позволяет добиться выигрыша до 3 дБ по метрике Пик ОСШ по сравнению со стандартной схемой кодека БРШТ.

Личный вклад автора. Выносимые на защиту положения предложены и реализованы лично автором в ходе выполнения научно-исследовательских работ на кафедре динамики электронных систем Ярославского государственного университета им. П.Г.Демидова. Практическая реализация алгоритмов выполнялась лично автором с привлечением для проверки коллектива исследователей.

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

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

LV1-LXV научные сессии, посвященные Дню радио, Москва; международные научно-практические конференции «Перспективные технологии в средствах передачи информации», Владимир-Суздаль, 2007, 2011; 9-13 международные конференции и выставки «Цифровая обработка сигналов и сс применение», Москва, 2007-2011.

Публикации. Основное содержание диссертации отражено в 23 печатных работах, из них 3 статьи в журналах из перечня ВАК.

Структура и объем работы. Диссертация состоит из введения, 4-х глав, заключения, списка литературы, содержащего 107 наименований, и 2-х приложений. Основная текстовая часть изложена на 154 страницах (59 рис., 5 табл.). В приложении Б приведены копии документов, подтверждающие внедрение результатов работы.

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

1) Алгоритм оптимального и субоптимального квантования в системах сжатия с фиксированным энтропийным кодером SP1HT (STW), который может быть представлен как последовательность предобработки и скалярного квантования.

2) Преобразование, основанное на нелокальной обработке области вейвлет-коэффициентов.

3) Результаты тестирования разработанной системы сжатия для объективных метрик Пик OCI11 и кратномасштабной оценки структурного подобия.

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

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

В первой главе проведен анализ энтропийного кодера SP1HT в контексте современных алгоритмов сжатия.

Рассмотрены основные схемы сжатия:

а) рекурсивная схема сжатия с предсказанием;

б) нерекурсивная схема сжатия с преобразованием;

в) фрактальная схема сжатия.

Для того чтобы сравнить работу различных алгоритмов сжатия изображений вводится наиболее простая из известных оценок качества изображений -Пик ОСШ «Peak Signal Noise Ratio» (PSNR):

PSNR =101og)0(A'max/^)/Xi;(^ -P,J, (1)

1 j

где Л' - число пикселей, Р,; - пиксели изображения оригинала, Р, - - пиксели

восстановленного изображения.

Во второй главе рассмотрены алгоритмы построения системы квантования для источника без памяти. Предложен алгоритм квантования вейвлет-коэффициентов, позволяющий минимизировать искажение в вейвлет-области при фиксированной кодовой книге, числе бит и энтропийном кодере STW (SPIHT).

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

В силу указанных проблем в кодерах используют простое скалярное квантование последовательным уточнением (EZW, SPIHT, ЕВСОТ) с равномерной шкалой квантования и расширенной нулевой зоной. Существуют более эффективные методы векторного квантования, требующие дополнительных вычислительных ресурсов, но и они не решают указанную проблему в полной мере.

Необходимо построить систему квантования, учитывающую иерархическую структуру энтропийного кодера (например, SPIHT).

Для построения системы квантования необходимо определить разбиения пространства значений на набор интервалов .или областей part, и кодовую книгу code,, которая будет содержать значения, сопоставляемые /-й области при обратном квантовании (деквантовании). Когда система построена, процесс квантования скалярной или векторной величины х сводится к определению области, которой принадлежит величина i :хе part,. Индексы / проквантованных величин преобразуются энтропийным кодером в битовый поток. При деквантовании величина х восстанавливается по индексу и соответствующему значению из кодовой книги: 5с = code,.

Естественным требованием при построении системы квантования является минимизация ошибки восстановления величины х: х(| -> min при ограничениях на размер битового потока.

Разработанный алгоритм квантования основан на использовании иерархической структуры современных вейвлет-кодеков, в частности STW (SPIHT). При фиксированной кодовой книге суммарное искажение всегда может быть легко вычислено. Число же бит может быть представлено в виде рекурсивной структуры. На любом уровне разложения можно рассмотреть 4

коэффициента данного уровня (потомки одного предка) и соответствующие им 16 прямых потомков (рис. 1).

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

Pl/ ! Р-/

РЗ v : Р4 Л

Родители Потомки

Рис. 1. Структура соответствия родителей потомкам

Для каждого коэффициента выбирается значение из кодовой книги с определенным числом разрядов и знаком. Так число +7 соответствует в двоичной записи числу +111, обладает 3 разрядами и знаком. Число 0 соответствует О разрядам и не обладает знаком. В алгоритмах SP1HT и EZW число бит не зависит от значений проквантованных коэффициентов, а зависит только от числа их разрядов. Поэтому в дальнейшем изложении все цифры будут приводиться с позиции числа разрядов коэффициентов, а не их значений. Также не будет приводиться знак, так как с позиции числа разрядов он не играет никакой роли в числе бит.

Если потомков не существует (первый уровень вейвлет-преобразования), то число бит, требуемых для передачи 4 коэффициентов (j,), при условии того, что известно максимальное число разрядов т проквантованных коэффициентов, равно

4

4(1 + /я)-У(.$, w = max(j,). (2)

м 1

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

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

Для подсчета бит, соответствующих дереву из 341 элементов (5 уровней разложения), строится рекурсивная последовательность. Число бит на первом

уровне определяется независимо. После этого определяется дополнительное (к битам первого уровня) число бит для передачи 2-го уровня в контексте первого. После этого - 3-го в контексте 1-го и 2-го и т.д., пока не будет определено число бит для узла дерева.

Основной структурной единицей этой иерархической структуры является блок 2x2, имеющий одного общего предка с более высокого уровня. Когда у каждого из коэффициентов блока 2x2 имеются потомки, число бит уже определяется не только 4-мя родительскими коэффициентами. Пусть число разрядов 4-х родительских коэффициентов - I = 1,..,4, и пусть для каждого из 4-х семейств потомков (и прямых, и косвенных) максимальное число разрядов равно с,, / = 1,..,4. Для определения числа бит N получена следующая формула

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

Для каждого дерева необходимо определить соответствующие 341 разряд, минимизирующие функцию J = D + XR. Одно значение этой функции получается при скалярном квантовании каждого коэффициента в отдельности. В этом случае при фиксированной кодовой книге минимизируется искажение без учета битовых затрат. Обозначим результирующее искажение D0, число бит /*■„, а функцию Лагранжа J0 = D0 + .

В работе доказано, что искомый минимум функции J достигается при числе разрядов меньшем или равном числу разрядов при скалярном квантовании. Разработанный алгоритм использует этот факт для квантования. Каждый отсчет может быть проквантован в соответствии с простым скалярным квантователем, или на 1 разряд меньше. После проверки возможности уменьшения на 1 разряд коэффициентов дерева процедура повторяется для уменьшения еще на один разряд. Так как кодовая книга фиксирована, вносимое квантованием искажение всегда может быть легко найдено как {х-code,)1. Если на данном уровне посчитаны искажение и число бит, то они передаются на более высокий уровень для суммирования.

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

Шаг 1. Для каждого блока j, (2x2), имеющего общего родителя, на первом уровне

вейвлет-преобразования вычисляется /n = max(sy).

i

Для п = 0,..,т

(3)

+

¿1*/ " ci\~ sL(J„ci) + } = max(max(.9,),max(c,)

i-l ' 1

Максимальное число разрядов устанавливается в и. Те разряды, что больше п, уменьшаются до п. Таким образом определяется зависимость функции (п) для _/'-го блока. Переход на уровень 2.

Шаг 2. Для каждого блока 2x2, имеющего общего родителя, на данном уровне вейвлет-преобразования вычисляется т = тах[тах(.?( ),тах(с,)].

Для и = 0,..,т

Максимальное число разрядов устанавливается в п. Разряды si блока выбираются так, чтобы максимальный из них был равен п. Среди потомков с, перебираются все возможные варианты ./с' (к), к< п, где к -максимальный разряд потомков, такие, что для данного блока функция Лагранжа была минимальна среди всех возможных выборов к

J(n)-aIgm^a

К

'-1

Шаг 3. Переходим на более высокий уровень. Если это не корень дерева, то переходим к шагу 2.

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

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

В третьей главе рассмотрены условия, накладываемые на преобразование для сжатия алгоритмом БРШТ (STW). Предложено новое преобразование и рассмотрены случаи сжатия с потерями и без потерь.

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

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

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

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

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

При коэффициентах сжатия, не превышающих 0,5 бит/пиксель, особо эффективным становится преобразование сс!Р?/7 (биортогональное преобразование класса Добеши 4/4), реализованное через лифтинг схему, так как на таких коэффициентах сжатия проквантованные коэффициенты практически не коррелируют друг с другом. Кроме того, преобразования, требующие передачи дополнительных данных, начинают занимать большую долю в битовом потоке.

На особо низких коэффициентах сжатия (менее 0,1 бит/пиксель), когда остаются только визуальные очертания, детали стираются, а шум квантования становится сравним по мощности с полезным сигналом, превзойти вейвлеты могут только фрактальные методы. Но, так как рассматривается система преобразование-квантование-энтропийный кодер 8Р1НТ, то применение фрактального компрессора выходит за рамки обозначенной задачи. Отсюда следует не совсем очевидный вывод, что разрабатываемое преобразование должно при больших шагах квантования сходиться к вейвдетам. Таким образом, преобразование Г должно зависеть от шага квантования Р(С)5), и при возрастающем <38 должно переходить в сс1Г 9/7 или другое эффективное вейвлет-преобразование.

В работе заведомо опускается выбор конкретного вейвлет-преобразования, потому что такая задача уже была рассмотрена многими учеными, в частности Стефаном Мандатом. Им описан алгоритм выбора оптимального вейвлет-базиса по нескольким критериям. Такой базис может быть представлен в виде лифтинг схемы для быстрой реализации. В любом случае, это делает базис сигналозависимым. Поэтому для общности исследований будем далее считать, что вейвлет-базис выбран, и это с<ЗГ 9/7.

После того, как крайний случай максимального шага квантования определен, естественно определить преобразование для минимального шага квантования (<ЗЯ=1). На таких степенях сжатия может уже идти речь о сжатии без потерь, когда квантование не требуется. Существует множество методов сжатия без потерь, отличающихся на несколько процентов, и выбрать из них оптимальный невозможно в силу отсутствия модели изображения. Таким образом, необходимо определить преобразование, которое совпадало бы с сс^ 9/7 на низких степенях сжатия, не требовало передачи дополнительных данных и было бы эффективно при сжатии без потерь. Такое преобразование должно строиться на определенной модели изображения, адекватность которой должна быть в той или иной мере подтверждена экспериментально. На основе проведенных исследований о возможности применения методов нелокальной обработки для сжатия изображений разработан метод преобразования изображений, удовлетворяющий следующим требованиям:

1) совпадение с вейвлет-преобразованием при больших шагах квантования;

2) эффективность для компрессии без потерь;

3) нетребовательность к передаче дополнительных данных, кроме коэффициентов вейвлет-преобразоЕакия.

Рис. 2. Участки изображения «Барбара»

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

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

Изображения не являются однородными, и их структура меняется от точки к точке. На рис. 2 представлены вейвлет-преобразования двух участков изображения «Барбара» размером 128x128 каждый. Если для первого участка ВЧ компоненты первого уровня разложения имеют малую амплитуду, и потребуется немного бит для их сжатия, то второй участок требует намного больше бит в силу высокой энергии ВЧ компонент. При этом локально эти участки расположены довольно близко.

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

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

I! _]£с£Л

*/=£*/ * ' , №

] 1

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

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

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

Допустим, что декодер выделил часть битового потока, отвечающую за один тайл, извлек размеры этой области, и ему известно число уровней разложения. Тогда декодер может выделить место в памяти, где будет располагаться будущее изображение или его целочисленное вейвлет-преобразование. Декодеру известно, что поток был получен БР1НТ кодером, и, зная размеры изображения, он может восстановить пирамиду коэффициентов разработанного преобразования. Теперь декодер должен из пирамиды коэффициентов получить пирамиду вейвлет-коэффициентов, на основе которой и будет построено изображение. Таким образом, задача построение преобразования, удовлетворяющего наложенным ограничениям, заключается в поиске преобразования пирамиды коэффициентов в пирамиду вейвлет-коэффициентов. Естественно, что это преобразование с точки зрения БРИТ кодирования должно быть более эффективным, чем вейвлет-преобразование.

В разработанном преобразовании более высокие уровни пирамиды коэффициентов определяют метод преобразования для более низких.

Преобразование для ВЧ части строится на основе НЧ части и предыдущих (в растровом порядке) коэффициентов ВЧ части (рис. За).

С математической точки зрения обратное преобразование сначала выполняется для самого высокого уровня по формуле:

-1

/-1

(5)

где Д.

декодированный из

7=1

битового

№ потока

г-й коэффициент, х,

преобразованный вейвлет-коэффициент, а1 - веса, определяющиеся на основе

похожести окрестностей г-го

и у-го коэффициентов, и окрестностей

вектора

X,

X,

соответствующих коэффициентов в НЧ-области. Пусть окрестностей /-го и у'-го коэффициентов, а >' и У) - вектора окрестностей соответствующих коэффициентов в НЧ области, тогда

аи =е и" ■ (6)

Параметр А определяет спадание веса при увеличении расстояния между окрестностями.

Для уменьшения вычислительной сложности имеет смысл выбирать для усреднения лишь определенное число элементов с максимальными весами.

В такой модели невозможно передать самый верхний НЧ уровень, поэтому он должен совпадать с соответствующим уровнем вейвлет-области. Для ВЧ же уровня при растровой последовательности обработки коэффициенты с номерами больше (/,/) неизвестны, поэтому окрестность в ВЧ области должна иметь следующую форму (рис. 36).

ОООООО — ОЮОООО — <300 ООО ОрОООО к

о1ооо#©-—

ороооо •

•о •о

о о о •о •о

000090

----ЮГх

ОООООО

НЧ-часть У

оофобо-V-оси---

О'ООО

ОООООО ОООООО

ВЧ-часть

7 \_■

о

О

о о о о

ОООООО-

•и

ОООООО-ОООООО-ОООООО ОООООО

ооор©а

ОООООО.

ооог

■ о

■о

о о о •о

•о

ОООООО'

НЧ-часть }

ВЧ-часть

ООО......о

ООО......о

___ООО......о

оооЬш......О

О О об» О......о

ОООООО......о

ОООООО —о

ОООООО......о

а) б)

Рис. 3. Принцип взаимосвязи НЧ и ВЧ частей: а) области поиска; б) форма окрестностей

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

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

Сначала низкочастотные вейвлет-коэффициенты инициализируются -х,=А,. На основе НЧ вейвлет-коэффициентов и соответствующих Д, для данного уровня вычисляются х1 по формуле (5).

После того как на данном уровне пирамиды определены вейвлет-коэффициенты всех ВЧ частей, выполняется обратное целочисленное вейвлет-преобразование и переход к следующему уровню (рис. 4).

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

Щ 'Ё

шш

■ёт

Шл 11

Рис. 4. Принцип перехода между уровнями

Сжатие с потерями отличается от сжатия без потерь введением квантования. Это накладывает ограничения на использование формулы (5), так как при передаче в битовом потоке неквантованных коэффициентов Д, число бит нельзя сократить. Поэтому необходимо модифицировать формулу (5) с учетом квантования.

I ! ;-I

?, = (А, ) + ]Гал,*у(7)

здесь Д, - уже проквантованные значения, ах, - восстановленные значения вейвлет-коэффициентов, которые в силу ошибок квантования отличаются от истинных значений х,. Веса вычисляются по тем же формулам, но уже по искаженным значениям. Вейвлет-уровни обрабатываются в обратном порядке. Как только для Ы-го уровня на основе Д, получены х1г сразу выполняется обратное вейвлет-преобразование. которое будет НЧ областью для (М-Г)-го уровня.

Эффективность предложенного преобразования сильно зависит от того, какой блок сжимается. Проведены сравнения эффективности предложенного преобразования: и вейвлет-преобразования для участков с рис. 2 размером 128x128 на широком наборе шагов квантования и случая сжатия без потерь. Результаты приведены в табл. 1.

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

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

Таблица 1. Пил ООШ в зависимости от шага квантования

Изображение : ДВП «Барбара» участок 1 Предложенное преобразование участок 1 ДВП участок 2 Предложенное преобразование участок 2

бит/пиксель без потерь 4,64 4,63 6,20 5,72

41,28 ЛЬ74 40,51 43.56

05=8 38,05 38,23 34,33 1_37,49

08=16 34,40 34,55 ¿8,60 31,74

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

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

Алгоритм субоптимального квантования реализован в среде компьютерного моделирования МаИлЬ. Реализация алгоритма 5Р1НТ (ЭТ'Л'), используемая в | исследованиях в качестве энтропийного кодера, была выполнена доктором I Сакалли и доктором Пирлманом (автором этого алгоритма) и приведена на | официальном сайте Ма1ЬаЬ. При исследовании проводилось сравнение I разработанного субоптимального и скалярного алгоритмов квантования при одном и том же вейвлет-преобразовании (с<Ш/7) и энтропийном кодере без арифметического кодирования, X инициализировался по правилу Х = 305'2/8.

Результаты тестирования представлены в виде графиков зависимостей | Пик ОСШ от числа бит на пиксель. Для тестового изображения со сложной структурой «Барабара» разработанный алгоритм добавляет примерно постоянную величину в 0,7 дБ при степенях сжатия от 0,2 до 1,5 бит/пиксель (рис. 5).

Визуальное сравнение предложенного алгоритма квантования и скалярного квантования приведено в виде трех фрагментов на рис. 6.

Для тестирования метода нелокального кодирования с предсказанием в вейвлет-области использовались метрика Пик ОСШ и предложенная Вангом многомасштабная оценка структурного подобия (ММ ОСП), реализованная г непосредственно её автором.

Структура разработанного метода преобразования такова, что для каждого блока 128x128 на основе заданного значения параметра шага квантования выбирается X и преобразование (разработанное или вейвлет), чтобы минимизировать критерий Я + ХВ, учитывая, что для вейвлет-преобразования возможна оптимизация по этому критерию на основе алгоритма квантования из главы 2.

Barbara

OA 5fi Ь8 : 2 ч ijT" 'i е

бит/пиксел

Рис. 5. Зависимость Пик ОСШ от бит/пиксель для изображения «Барбара»

Рис, 6. Сравнение двух фрагментов изображения «Барбара»: а) исходный фрагмент; б) вРШТ; в) предложенный алгоритм

Результаты тестирования алгоритма на тестовом изображении «Лодка» представлены на рис. 7.

Сравнивались результаты алгоритм БРШТ с вейвлет-преобразованием сс!АЭ.7 и разработанного алгоритма при условии совпадения значений Пик ОСШ или ММ ОСП на всех блоках изображения. Изображение разбито на блоки 12.8x128, и в каждом блоке указано, во сколько раз уменьшается битовый поток при применении предложенного алгоритма. Как видно из рисунков, эффективность предложенного метода колеблется в широких пределах: от 1 для блоков, имеющих постоянное значение, до 2.5 раз. Такой разброс связан с неоднородной

, структурой изображений, поэтому очень трудно объективно оценить I эффективность предложенного алгоритма. Проведено тестирование для 5-ти ( изображений из базы изображений Университета Южной Калифорнии (http://sipi.usc.edu/database/): «Барбара», «Мост», «Лена», «Сан Диего», «Лодка» и трех шагов квантования: 4, 8 и 16. Результаты тестирования занесены в таблицы.

а)

Рис. 7. Уменьшение битового потока: а) фиксированный Пик ОСШ: б) фиксированная ММ ОСП

I В табл. 2 приведено во сколько раз уменьшится битовый поток при применении разработанного алгоритма по отношению к алгоритму БРШТ при фиксированном значении метрик Пик ОСШ и ММ ОСП.

Т^аблица_2^ Результаты тестирования предложенного алгоритма (раз)

Изобр. 08=4 (38=8 08=16

Пик ОСШ ММ ОСП Пик ОСШ ММ ОСП Пик ОСШ ММ ОСП

Барбара 1,14 1,09 1,16 1,12 1,22 1,17

Мост 1,07 1,05 1.08 1,05 1,14 1,02

Лена 1.16 1.08 1,13 1,05 1,18 1,12

Сан Диего 1,06 1,05 1,10 1,08 1,16 1.01

Лодка 1,15 1,11 1,13 1,05 1,15 1,07

В целом, результаты показывают, что предложенные преобразование и 5 алгоритм квантования позволяют в среднем на 14% сократить размер битового потока при фиксированном значении Пик ОСШ, и на 7,5% - при фиксированном значении ММ ОСП.

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

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

В диссертационной работе поставлены и решены ряд важных научно-практических задач, связанных с построением системы сжатия цифровых изображений с фиксированным энтропийным кодером SPIHT (STW).

[.Рассмотрены существующие высокоэффективные стандарты сжатия (Н.264, JPEG-2000), глубоко проработанные и охватывающие множество приложений. Для повышения коэффициентов сжатия изображений необходима методика, применяющая более эффективные преобразование, квантование и/или энтропийное кодирование. Обоснован выбор энтропийного кодера SPIHT, позволяющего осуществить параллельную обработку блоков вейвлет-спектра.

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

3. Реализованный субоптимальный алгоритм протестирован на наборе тестовых изображений из базы Университета Южной Калифорнии и показывает результаты на 0,5-1 дБ лучшие по шкале Пик ОСШ по сравнению со скалярным квантованием с энтропийным кодером SPIHT.

4. Предложено преобразование, основанное на нелокальном кодировании с предсказанием. Предложенное преобразование позволяет для фиксированного энтропийного кодера повысить до 3-х дБ по метрике Пик ОСШ качество восстановленного изображения. Рассмотрены случаи применения алгоритма для сжатия с потерями или без потерь.

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

6. Разработан, реализован и внедрен алгоритм оценки параметров аддитивного и мультипликативного шума.

7. Реализован ряд устройств для проверки достоверности научных положений. Моделирование показывает полное соответствие теоретических положений и практических результатов.

8. Предложенные преобразование и алгоритм квантования позволяют в среднем на 14% сократить размер битового потока при фиксированном значении Пик ОСШ, и на 7,5% при фиксированном значении ММ ОСП.

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ Статьи в журналах из перечня ВАК

1. Приоров А.Л., Мочалов И.С. Применение измененной схемы вейвлет-

преобразования для сжатия изображений // Электросвязь. 2009. № 11.

С. 29-34.

2. Приоров А.Л., Волохов В.А., Мочалов И.С. Параметризация двумерных

вейвлет-фильтров для субполосного разложения кратности 3*3 //

Электросвязь. 2009. № 2. С. 25-28.

3. Приоров А.Л., Волохов В.А., Мочалов И.С. Синтез двумерных неразделимых вейвлет-фильтров для субполосного разложения произвольной кратности // Радиотехника. 2010. № 1. С. 74-81.

Статьи в рецензируемых журналах

4. Приоров А.Л., Волохов В.А., Мочалов И.С. Синтез двумерных неразделимых вейвлет-фильтров для субполосного разложения нечетной кратности // Вестн. Яросл. гос. ун-та. Сер. Физика. Радиотехника. Связь. 2008. № 1.С. 144-147.

Доклады на российских и международных конференциях

5. Мочалов И.С. Статистический алгоритм контроля битовой скорости в стандарте видеокодирования Н.264 // Докл. междунар. конф. «Проблемы автоматизации и управления в технических системах». Пенза, 2008. С. 55-59.

6. Мочалов И.С., Приоров АЛ., Волохов В.А. Усовершенствование алгоритма SPIHT на основе адаптивного изменения фильтров синтеза // Докл. 11-й междунар. конф. «Цифровая обработка сигналов и ее применение». М., 2009. Т. 2. С. 494-497.

7. Волохов В.А., Мочалов И.С., Приоров А.Л. Разработка алгоритма фильтрации цифровых изображений на основе трехполосной схемы разложения сигнала // Докл. 11-й междунар. конф. «Цифровая обработка сигналов и ее применение». М., 2009. Т. 2. С. 467-469.

8. Волохов В.А., Мочалов И.С., Приоров А.Л. Применение динамической пороговой обработки в задачах фильтрации цифровых изображений // Тр. LXIV науч. сессии, посвященной Дню Радио. М., 2009. С. 240-241.

9. Приоров А.Л., Мочалов И.С., Волохов В.А. Сжатие изображений на основе адаптивного изменения вейвлет-фильтров синтеза в алгоритмах SPIHT и JPEG2000 II Тр. LXIV науч. сессии, посвященной Дню Радио. М., 2009. С. 241-244.

10. Мочалов И.С., Приоров А.Л., Цветкова К.Н., Новожилова Т.В. Сжатие изображений на основе модифицированной схемы вейвлет-преобразования // Докл. 12-й междунар. конф. «Цифровая обработка сигналов и ее применение». М., 2010. Т. 2. С. 136-139. '

Свидетельства о государственной регистрации программ для ЭВМ

11. Мочалов И.С., Жуков A.A., Приоров А.Л. YarVc - программа для сжатия и воспроизведения видеоданных. Свидетельство о государственной регистрации программы для ЭВМ № 2010610724 от 21.01.2010.

Подписано в печать 19.03.2012 Формат 60x84 1/16. Усл. печ. л. 1. Тираж 100 экз. Заказ 10/12.0гаечатано на ризографе Ярославский государственный университет 150000 Ярославль, ул. Советская, 14.

61 12-5/2477

Ярославский государственный университет им. П.Г. Демидова

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

Мочалов Иван Сергеевич

МЕТОДЫ И УСТРОЙСТВА ПРЕОБРАЗОВАНИЯ И КВАНТОВАНИЯ ВЕЙВЛЕТ-СПЕКТРОВ ПРИ ВНУТРИКАДРОВОМ СЖАТИИ ЦИФРОВЫХ ТЕЛЕВИЗИОННЫХ СИГНАЛОВ

Специальность 05.12.04 Радиотехника, в том числе системы и устройства телевидения

Диссертация на соискание ученой степени кандидата технических наук

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

Ярославль - 2012

ОГЛАВЛЕНИЕ

Список сокращений 5

ВВЕДЕНИЕ 6

1. МЕТОДЫ СЖАТИЯ ИЗОБРАЖЕНИЙ 11

1.1. Преобразования 14

1.1.1. Блочные преобразования 15

1.1.2. Вейвлет-преобразования 17

1.1.3. Направленные преобразования 23

1.2. Развитие методов энтропийного кодирования коэффициентов 27 преобразований

1.3. Алгоритмы сжатия изображений, основанные на вейвлет- 28 преобразовании.

1.3.1. Алгоритмы Льюиса и Ноулеса 28

1.3.2. Алгоритм Шапиро 31

1.3.3. Алгоритм SPIHT 36

1.3.4. Алгоритмы блочного иерархического кодирования 38

1.3.5. Алгоритм квантования деревьев 42

1.3.6. Алгоритм SFQ 43

1.3.7. Стандарт JPEG-2000 44

1.4. Алгоритмы сжатия изображений, основанные на блочных 46 преобразованиях

1.4.1. Стандарт JPEG 46

1.4.2. Алгоритм EZW DCT 50

1.4.3. Сжатие I-кадров в стандарте Н.264 51

1.4.4. Алгоритм ADCTC 57

1.5. Алгоритмы сжатия изображений, основанные на фрактальной 59 модели изображения

1.6. Выводы 61

2. КВАНТОВАНИЕ ВЕЙВЛЕТ-КОЭФФИЦИЕНТОВ В 63 СИСТЕМАХ СЖАТИЯ

2.1. Равномерное квантование 64

2.2. Равномерное квантование с расширенной нулевой зоной 65

2.3. Квантование Ллойда-Макса 67

2.4. Адаптивное квантование, основанное на энтропии 68

2.5. Алгоритм оптимального квантования для фиксированной 71 кодовой книги и энтропийного кодера

2.5.1. Общие положения разработанного алгоритма 73

2.5.2. Расчет числа бит на первом уровне вейвлет- 74 преобразования

2.5.3. Расчет числа бит в общем случае 75

2.5.4. Общие положения квантователя 76

2.6. Выводы 81

3. РАЗРАБОТКА ПРЕОБРАЗОВАНИЯ ВЕЙВ ЛЕТ-СПЕКТР А 82 ДЛЯ КОМПРЕССИИ ИЗОБРАЖЕНИЙ

3.1. Общие требования к преобразованию 83

3.2. Нелокальная обработка 85

3.3. Разработка преобразования для сжатия изображений на 86 основе нелокальной обработки

3.3.1. Форма окрестности 92

3.3.2. Общий принцип декодирования 93

3.3.3. Сжатие с потерями 94

3.3.4. Кодер 95

3.4. Квантование 97

3.6. Результаты первичного тестирования 98

3.7. Выводы 99

4. РАЗРАБОТКА УСТРОЙСТВ ПРЕОБРАЗОВАНИЯ И 100 КВАНТОВАНИЯ ВЕЙВ ЛЕТ-СПЕКТРОВ ЦИФРОВЫХ ИЗОБРАЖЕНИЙ

4.1. Оценка параметров шума 101

4.2. Результаты тестирования субоптимального квантования 105

4.3. Практическая реализация предложенного нелокального 109 преобразования вейвлет-спектров

4.3.1. Принцип вычисления разностей окрестностей 111

4.3.2. Устройства прямого и обратного преобразования 113

4.4. Особенности выбора оценки качества восстановленного 115 изображения

4.5 Результаты тестирования 119

4.6. Выводы 124

ЗАКЛЮЧЕНИЕ 126

Литература 128

Список сокращений

БФ - банк фильтров ВФ - вейвлет-фильтр ВЧ - высокочастотный НЧ - низкочастотеый

ДВП - дискретное вейвлет-преобразование

ДИКМ - дифференциальная импульсно-кодовая модуляция

ДКП - дискретное косинус-преобразование

ИСФ - итеративная система функций

ИХ - импульсная характеристика

ММ ОСП - многомасштабная оценка структурного подобия

НЧ - низкочастотный

ОСП - оценка структурного подобия

ОСШ - отношение сигнал/шум

СЗК - список значимых коэффициентов

СНК - список незначимых коэффициентов

СНМ - список незначимых множеств

СКО - среднеквадратическая ошибка

ТВС - точное восстановление сигнала

ВВЕДЕНИЕ

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

При этом известно, что в видеопотоке основное место занимают, так называемые, I-кадры, сжимаемые без использования дополнительной информации, как статические изображения, поэтому рассмотрение проблем сжатия статических изображений является важной задачей в рамках разработки систем видеосжатия. В частности, мировой стандарт MPEG-2 использует стандарт сжатия изображений JPEG для I-кадров. Стандарт MPEG-4 part 10 (AVC) использует уже более сложную схему сжатия I-кадров.

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

Степень разработанности проблемы.

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

Наиболее известными в данной области являются работы Вудса Р., Гонсалеса Р., Зубарева Ю.Б., Прэтта У., Сойфера В.А., Ярославского Л.П.

Большую роль в современных алгоритмах кодирования с преобразованием играют вейвлет-преобразования, которые обеспечивают частотную и временную локализацию, а так же возможность обрабатывать сигнал на разных масштабах. В этой области широко используются работы Ваттерли М., Добеши И., Ковачевич Д., Малла С., Стренга Г., Чуй К.

Непосредственно алгоритмам сжатия изображений и видео посвящены работы российских ученых: ЧобануМ.К., Умняшкина C.B., Бехтина Ю.С.,

Радченко Ю.С., а также зарубежных авторов: Pearlman W.A., Said A., Shapiro J.M., Taubman D., Wheeler F.W., Xiong Z., Ramchandran K.

Наряду с вейвлет-преобразованием кратности разложения 2 используется кратность М выше, чем 2. В развитии теории М-полосных банков вейвлет-фильтров большую роль сыграли работы таких авторов, как Дворкович В.П., Дворкович A.B., Приоров А.Л., Burns C.S., Gopinath R.A., Tewfik А.Н., Vetterli M., Zou H.

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

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

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

- анализ выбранного энтропийного кодера SPIHT (STW) в контексте современных алгоритмов кодирования;

- разработка алгоритма квантования вейвлет-коэффициентов, позволяющего повысить качество изображений по метрике Пик ОСШ при фиксированном числе бит по сравнению со скалярным квантованием;

- разработка преобразования, более эффективного для решаемой задачи, чем вейвлет-преобразование.

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

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

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

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

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

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

3) Разработка преобразования для сжатия с потерями, основанного на нелокальном кодировании с предсказанием и квантованием в вейвлет-области.

Практическая значимость

Разработан и реализован алгоритм оценки параметров аддитивного и мультипликативного шумов. Разработанный алгоритм был внедрен в организации ООО «Гипроприбор-Инвест» для оптимизации параметров алгоритмов сжатия видеоданных с камер наружного наблюдения с учетом действия шумов.

Разработан и внедрен в организации ООО «Информационные системы Криста» алгоритм двумерного нелокального предсказания для предсказания значений двумерных индикаторов на прогнозный период.

Разработанные методы носят исключительную практическую направленность и применимы для использования в системах сжатия изображений. Их совместное применение позволяет добиться выигрыша до 3 дБ по метрике Пик ОСШ по сравнению со стандартной схемой кодека БРШТ.

Личный вклад автора. Выносимые на защиту положения предложены и реализованы лично автором в ходе выполнения научно-исследовательских работ на кафедре динамики электронных систем Ярославского государственного университета им. П.Г. Демидова. Практическая реализация алгоритмов выполнялась лично автором с привлечением для проверки коллектива исследователей.

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

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

ЬУ1-ЬХУ научные сессии, посвященные Дню радио, Москва; международные научно-практические конференции «Перспективные технологии в средствах передачи информации», Владимир-Суздаль, 2007, 2011; 9-13 международные конференции и выставки «Цифровая обработка сигналов и ее применение», Москва, 2007-2011.

Публикации. Основное содержание диссертации отражено в 23 печатных работах, из них 3 статьи в журналах из перечня ВАК.

Структура и объем работы. Диссертация состоит из введения, 4-х глав, заключения, списка литературы, содержащего 107 наименований, и 2-х приложений. Основная текстовая часть изложена на 154 страницах (59 рис., 5 табл.). В приложении Б приведены копии документов, подтверждающие внедрение результатов работы.

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

2) Преобразование, основанное на нелокальной обработке области вейвлет-коэффициентов.

3) Результаты тестирования разработанной системы сжатия для объективных метрик Пик ОСШ и кратномасштабной оценки структурного подобия.

Благодарности. Автор выражает глубокую благодарность своему научному руководителю Приорову Андрею Леонидовичу за помощь и поддержку на всех этапах проведения работы.

Отдельную благодарность своим друзьям и коллегам с кафедры динамики электронных систем: Волохову В.А., Сергееву Е.В., Новоселову С.А. за еженедельные советы, обсуждения и проверки результатов.

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

1. МЕТОДЫ СЖАТИЯ ИЗОБРАЖЕНИЙ

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

Сегодня во всем мире успешно внедряются системы цифрового телевидения. Россия, как крупная мировая держава, очень осторожно подходит к этому вопросу. Так в 2005 году было принято решении о внедрении до 2015 года европейского стандарта DVB. Были проведены испытания цифрового телевизионного вещания в Нижнем Новгороде, Москве, Санкт-Петербурге и других городах.

Согласно постановлению правительства РФ от 3 декабря 2009 г. №985 О федеральной целевой программе «Развитие телерадиовещания в Российской Федерации на 2009 - 2015 годы» состояние телерадиовещания как важнейшего средства массовой информации, направления и темпы его развития имеют первостепенное значение для социальной стабильности общества, информационной безопасности государства, экономической активности и духовного развития населения.

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

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

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

Существенным фактором, определяющим сроки реализации Программы, является решение Международного союза электросвязи, принятое на конференции по планированию наземного цифрового вещания «Женева-06», устанавливающее срок окончания переходного периода на цифровое наземное эфирное вещание - 2015 год.

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

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

Международный успех цифрового телевидения связан с успехами в двух областях науки. Разработки в области эффективных методов защиты от шумов, помех и многолучевости привели к созданию ряда международных стандартов передачи видео: ATSC, DVB, DVB-2, ISDB, DMBT. Успех же цифровых телевизионных систем был вызван тем, что они способны обеспечить лучшее визуальное качество изображения на принимающей стороне при той же полосе частот. А это - уже результат разработок в области сжатия видео. Известно, что один несжатый цифровой видеопоток требует для передачи скорость в 270 Мбит/сек, что соответствует полосе частот в 60 МГц. При этом для одного аналогового канала выделяется полоса

частот 8 МГц. Совершенствование алгоритмов сжатия видео и звука позволило передавать более 8 каналов в полосе частот одного аналогового канала. Это и энергетический выигрыш, и возможность передачи большего числа каналов, и возможность передавать видео высокого разрешения.

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

В частности мировой стандарт видеосжатия MPEG-2 использовал стандарт сжатия статических изображений JPEG для сжатия 1-кадров. Стандарт MPEG-4 part 10 (AVC) использовал уже более сложную схему сжатия I-кадров. Его основной разработчик Гари Дж. Суливан не захотел оформлять в отдельный стандарт эту схему, что привело к тому, что она долгое время не использовалась как отдельный алгоритм сжатия изображений, несмотря на ее высокую эффективность по сравнению с JPEG.

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

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

Наиболее типичная схема такого алгоритма представлена на рис. 1.1.

Рис. 1.1. Блок-схема алгоритма кодирования с преобразование

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