WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


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

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

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

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

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

Москва – 2012

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

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

Официальные оппоненты: доктор технических наук Бехтин Юрий Станиславович кандидат технических наук Салтыков Константин Евгеньевич

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

Защита состоится « 10 » мая 2012 г. (в аудитории А-448) в ___ час. ___ мин.

на заседании Совета по защите докторских и кандидатских диссертаций Д219.001.01 при Московском техническом университете связи и информатики по адресу: Москва, Авиамоторная, д. 8а.

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

Отзывы на автореферат в двух экземплярах, заверенные печатью, просим направлять по адресу: 111024, Москва, ул. Авиамоторная, 8а.

Совет по защите докторских и кандидатских диссертаций Д219.001.01 при ФГОБУ ВПО МТУСИ.

Автореферат разослан «___» __________ 2012 г.

Ученый секретарь диссертационного совета кандидат технических наук, доцент Р.Ю. Иванюшкин

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



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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

LVI–LХV научные сессии, посвященные Дню радио, Москва;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

~ PSNR 10log10N max Pi, j/ Pi, j Pi, j, (1) i j ~ где N – число пикселей, Pi, j – пиксели изображения оригинала, Pi, j – пиксели восстановленного изображения.

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

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





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

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

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

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

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

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

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

Если потомков не существует (первый уровень вейвлет-преобразования), то число бит, требуемых для передачи 4 коэффициентов ( si ), при условии того, что известно максимальное число разрядов m проквантованных коэффициентов, равно 41 m 0), m max(si ). (2) (si i iКак следует из формулы (2), число бит зависит только от числа нулевых коэффициентов (для которых не нужно передавать знак) и числа разрядов максимального по модулю элемента.

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

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

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

Основной структурной единицей этой иерархической структуры является блок 2х2, имеющий одного общего предка с более высокого уровня. Когда у каждого из коэффициентов блока 2х2 имеются потомки, число бит уже определяется не только 4-мя родительскими коэффициентами. Пусть число разрядов 4-х родительских коэффициентов – si, i 1,..,4, и пусть для каждого из 4-х семейств потомков (и прямых, и косвенных) максимальное число разрядов равно сi, i 1,..,4. Для определения числа бит N получена следующая формула 4 i N ) 2 1 m max(si,ci ) ci (si s i1 i. (3) i si ci 0,ci ) ci , m maxmax(si ),max(ci ) min(si s i i iПервое слагаемое формулы (3) соответствует уточняющим битам (с учетом знака). Второе слагаемое отвечает за переходы из состояния незначимый родитель/незначимые потомки в другие состояния (2 бита на переход соответствуют множителю 2). Третье слагаемое отвечает за передачу разницы между числом разрядов родителей и потомков с учетом ситуации нуля разрядов у тех или других.

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

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

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

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

Шаг 1. Для каждого блока si (2х2), имеющего общего родителя, на первом уровне вейвлет-преобразования вычисляется m max(si ).

i Для n 0,..,m Максимальное число разрядов устанавливается в n. Те разряды, что больше n, уменьшаются до n. Таким образом определяется зависимость j функции J (n) для j -го блока.

Переход на уровень 2.

Шаг 2. Для каждого блока si 2х2, имеющего общего родителя, на данном уровне вейвлет-преобразования вычисляется m maxmax(si ),max(ci ).

i i Для n 0,..,m Максимальное число разрядов устанавливается в n. Разряды si блока выбираются так, чтобы максимальный из них был равен n. Среди потомков ci ci перебираются все возможные варианты J (k), k n, где k – максимальный разряд потомков, такие, что для данного блока функция Лагранжа была минимальна среди всех возможных выборов k ci J (n) argminD(n) N(n,ki ) J (ki ).

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

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

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

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

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

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

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

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

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

При коэффициентах сжатия, не превышающих 0.5 бит/пиксель, особо эффективным становится преобразование cdf9/7, реализованное через лифтинг схему, так как на таких коэффициентах сжатия проквантованные коэффициенты практически не коррелируют друг с другом. Кроме того, преобразования, требующие передачи дополнительных данных, начинают занимать большую долю в битовом потоке.

На особо низких коэффициентах сжатия (менее 0.1 бит/пиксель), когда остаются только визуальные очертания, детали стираются, а шум квантования становится сравним по мощности с полезным сигналом, превзойти вейвлеты могут только фрактальные методы. Но, так как рассматривается система преобразование–квантование–энтропийный кодер SPIHT, то применение фрактального компрессора выходит за рамки обозначенной задачи. Отсюда следует не совсем очевидный вывод, что разрабатываемое преобразование должно при больших шагах квантования сходиться к вейвлетам. Таким образом, преобразование F должно зависеть от шага квантования F(QS), и при QS–>52 (в соответствии со стандартом H.264, 52 – максимальный шаг квантования для 8-ми битного изображения) должно переходить в cdf 9/7 или другое эффективное вейвлет-преобразование.

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

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

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

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

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

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

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

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

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

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

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

Основная идея нелокальной обработки изображений заключается в том, что чем ближе окрестности пикселей с точки зрения некоторой нормы, тем ближе значение этих пикселей. С математической точки зрения это записывается следующим образом. Пиксель может быть оценен, если известна его окрестность, как средневзвешенная сумма окружающих пикселей Xi X Xi X j j h h хi e /, (4) x j e j j где h – это параметр, регулирующий скорость спадания весов в зависимости от нормы разницы окрестностей. При этом оценка яркости пикселя перестает зависеть от его положения на изображения и зависит только от его окрестности.

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

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

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

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

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

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

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

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

i 1 ixi i xj /, (5) i, j i, j j 1 j где i – декодированный из битового потока i-й коэффициент, xi – преобразованный вейвлет-коэффициент, i, j – веса, определяющиеся на основе похожести окрестностей i-го и j-го коэффициентов, и окрестностей соответствующих коэффициентов в НЧ-области. Пусть Xi и X – вектора j окрестностей i-го и j-го коэффициентов, а Yi и Yj – вектора окрестностей соответствующих коэффициентов в НЧ области, тогда Xi X (1) Yi Yj j h i, j e. (6) Параметр h определяет спадание веса при увеличении расстояния между окрестностями.

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

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

а) б) Рис. 3. Принцип взаимосвязи НЧ и ВЧ частей: а) области поиска; б) форма окрестностей Форма окрестности может иметь и более сложную форму, кроме того, поиск блоков окрестностей может быть выполнен с учетом поворотов.

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

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

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

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

Рис. 4. Принцип перехода между уровнями Сжатие с потерями отличается от сжатия без потерь введением квантования.

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

i1 i~ ~ xi Q1(i ) x /, (7) i, j j i, j j 1 j ~ здесь i – уже проквантованные значения, а xi – восстановленные значения вейвлет-коэффициентов, которые в силу ошибок квантования отличаются от истинных значений xi. Веса вычисляются по тем же формулам, но уже по искаженным значениям. Вейвлет-уровни обрабатываются в обратном порядке.

~ Как только для N-го уровня на основе i получены xi, сразу выполняется обратное вейвлет-преобразование, которое будет НЧ областью для (N-1)-го уровня.

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

Результаты приведены в табл. 1.

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

Таблица 1. Пик ОСШ в зависимости от шага квантования Изображение ДВП Предложенное ДВП Предложенное «Барбара» участок 1 преобразование участок 2 преобразование участок 1 участок бит/пиксель 4,64 4,63 6,20 5,без потерь QS=4 41,28 41,74 40,51 43,QS=8 38,05 38,23 34,33 37,QS=16 34,40 34,55 28,60 31,Стоит отметить, что выбор преобразования можно выполнять не только в пространственной области, но и в области разрядов. Так, часть старших разрядов может быть передана на основе нелокального преобразования, а оставшиеся младшие разряды – на основе алгоритма субоптимального квантования. Если же требуется точное соответствие битового потока заданному значению, то младший разряд для всех вейвлет-коэффициентов может быть передан не полностью.

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

Алгоритм субоптимального квантования реализован в среде компьютерного моделирования MatLab. Реализация алгоритма SPIHT (STW), используемая в исследованиях в качестве энтропийного кодера, была выполнена доктором Сакалли и доктором Пирлманом (автором этого алгоритма) и приведена на официальном сайте MatLab. При исследовании проводилось сравнение разработанного субоптимального и скалярного алгоритмов квантования при одном и том же вейвлет-преобразовании (cdf9/7) и энтропийном кодере без арифметического кодирования, инициализировался по правилу 3QS /8.

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

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

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

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

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

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

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

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

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

Таблица 2. Результаты тестирования предложенного алгоритма (раз) QS=4 QS=8 QS=Пик ОСШ ММ ОСП Пик ОСШ ММ ОСП Пик ОСШ ММ ОСП Изобр.

1,14 1,09 1,16 1,12 1,22 1,Барбара 1,07 1,05 1,08 1,05 1,14 1,Мост 1,16 1,08 1,13 1,05 1,18 1,Лена 1,06 1,05 1,10 1,08 1,16 1,Сан Диего 1,15 1,11 1,13 1,05 1,15 1,Лодка В целом, результаты показывают, что предложенные преобразование и алгоритм квантования позволяют в среднем на 14% сократить размер битового потока при фиксированном значении Пик ОСШ, и на 7,5% – при фиксированном значении ММ ОСП.

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ В диссертационной работе поставлены и решены ряд важных научнопрактических задач, связанных с построением системы сжатия цифровых изображений с фиксированным энтропийным кодером SPIHT (STW).

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

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

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

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

8. Волохов В.А., Мочалов И.С., Приоров А.Л. Применение динамической пороговой обработки в задачах фильтрации цифровых изображений // Тр.

LХIV науч. сессии, посвященной Дню Радио. М., 2009. С. 240...29. Приоров А.Л., Мочалов И.С., Волохов В.А. Сжатие изображений на основе адаптивного изменения вейвлет-фильтров синтеза в алгоритмах SPIHT и JPEG2000 // Тр. LХIV науч. сессии, посвященной Дню Радио. Москва, 2009.

С. 241–244.

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

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

Подписано в печать 30.01.20Формат 6084 1/16. Усл. печ. л. 1. Тираж 100 экз.

Отпечатано на ризографе Ярославский государственный университет 150000 Ярославль, ул. Советская,






© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.