ДонНТУ   Портал магистров

Исследование применения вейвлет-преобразований для обработки мультимедийного трафика

Cодержание

ВВЕДЕНИЕ

В современном мире человек большое количество времени проводит за компьютером. Данные разного рода становятся неотъемлемой частью не только успешной работы, но и домашнего отдыха. Большую часть этих данных составляют различные графические изображения, начиная от рабочих графиков и гистограмм и заканчивая личными фотографиями. И задача современной техники обеспечить сохранность этой информации и предоставить быстрый доступ к ней пользователю. Возьмем для примера следующие данные: скромная, не очень качественная иллюстрация на обложке книги размером 500x800 пикселей, займет 1.2 Мб, а несжатое полноцветное изображение размером 2000 * 1000 пикселей имеет размер около 6 мегабайт. Размер изображений, получаемых от профессиональных камер или сканеров высокого разрешения может быть еще больше. Но далеко не размеры изображения, хранящиеся на носителях, повлияли на разработку методов сжатия изображения, а необходимость постоянной работы с ними и, главное, передача по телекоммуникационным каналам. Сжатие изображений также имеет преимущества для каждой существующей на сегодняшний день индустрии. Сначала техника сжатия изображений наиболее часто использовалась в индустрии, которая занимается печатью, сохранением данных и телекоммуникациями. Но в настоящее время цифровая форма сжатия изображений применяется также в таких областях, как передача факса, спутниковый дистанционный сбор данных, телевидении повышенной четкости и т.д. Кроме того, сжатие изображений также полезно для любой организации, которая требует, чтобы просмотр и сохранение изображений было стандартизировано. К таким организациям можно отнести государственные правительственные органы, музеи, галереи, библиотеки, архивы и т.п.. Таким образом, задача поиска оптимального метода сжатия изображений является очень актуальной в наше время, ведь это позволит существенно снизить требования к пропускной способности сетей и каналов связи и увеличит возможности обычного пользователя, в условиях ограниченной пропускной способности, в быту.

ОБЗОР ЛИТЕРАТУРНЫХ ИСТОЧНИКОВ

Статья«Использование вейвлет-преобразований для обработки цветных цифровых изображений» [1] Родионова И.В. посвящена использованию вейвлет-преобразований для обработки изображений в системах с ограниченными ресурсами. Книга«Основы теории вейвлетов. Вейвлеты в MATLAB.» [2] автора Смоленцева Н.К. знакомит нас с различными математическими аппаратами анализа процессов, сосредоточивает внимание на теории вейвлетов и их реализации в MatLab. В статье«Применение новых критериев оценки качества изображений после их сжатия.» [3] авторы Илюшкина Н., Чобану М., знакомят нас с различными критериями оценки изображений после их сжатия и анализируют преимущества различных алгоритмов оценки изображений. Методическое пособие«Алгоритмы сжатия изображений.» [4] автора Ватолина Д.С. знакомит с основными алгоритмами сжатия, базовыми алгоритмами и направлениями развития теории сжатия. Книга«Система инженерных и научных расчетов MATLAB 5.x.» [5]предоставляет полную информацию для ведения инженерных расчетов и визуализации результатов. Книга«Обработка сигналов и изображений.» [6] посвящена мощным средствам обработки сигналов и изображений, которые предоставляет MatLab. В книге«Теория и практика вейвлет-преобразования.» [7] авторов Воробьева В.И. и Грибунина В.Г. излагаются основные принципы вейвлет-преобразований, рассмотриваются принципы построения вейвлет-фильтров. В книге«Десять лекций по вейвлетам.» [8] Ингрид Добеши знакомит нас с этим математическим аппаратом и использованием его для решения различных задач. Это одна из лучших книг для начала знакомства с этим математическим аппаратом.

1 ОБЗОР АЛГОРИТМОВ СЖАТИЯ

Основными особенностями, которые позволяют сжимать изображения является то, что человеческое зрение при анализе изображения оперирует контурами, общим переходом цветов и сравнительно не чувствительно к малым изменениям в изображении. Таким образом, мы можем создать эффективные алгоритмы архивации изображений, в которых декомпрессированное изображение не будет совпадать с оригиналом, однако человек этого не заметит. Данная особенность человеческого зрения позволила создать специальные алгоритмы сжатия, ориентированные только на изображения. Также легко заметить, что изображение, в отличие, например, от текста, имеет избыточность в 2-х измерениях. То есть, как правило, соседние точки, как по горизонтали, так и по вертикали, в изображении близки по цвету. Кроме того, мы можем использовать сходство между слоями цветной интенсивности (зеленой, красной и голубой) в наших исследованиях, что позволяет создать еще более эффективные алгоритмы. Различают 2 принципиальных подхода к построению алгоритмов сжатия: алгоритмы сжатия без потерь и алгоритмы сжатия с потерями. Сжатие без потерь (англ. Lossless data compression) - метод сжатия: видео, аудио, графики, документов, представленных в цифровом виде, при использовании которого закодированные данные могут быть восстановлены с точностью до бита. При этом оригинальные данные полностью восстанавливаются из сжатого состояния. Для каждого из типов цифровой информации, как правило, существуют свои оптимальные алгоритмы сжатия без потерь. Сжатие без потерь используется, когда важна идентичность сжатых данных оригиналу. Сжатие с потерями - метод сжатия (компрессии) данных, при использовании которого распакованные данные отличаются от исходных, но степень отличия не является существенной с точки зрения их дальнейшего использования. Этот тип компрессии часто применяется для сжатия аудио- и видеоданных, статических изображений, в Интернете, особенно, в потоковой передаче данных и цифровой телефонии.

Структурная схема принадлежности формата к алгоритму

Рисунок 1.1 – Структурная схема принадлежности формата к алгоритму.

При воспроизведении сжатых изображений возникает вопрос, как сравнить восстановленное изображение и оригинал. Ведь известно, что человеческое зрение и машинное видение кардинально отличаются друг от друга. Высокое качество машинной обработки вовсе не означают высокое качество изображения для человека, потому что зрение человека обладает нелинейной поведением и субъективностью. Именно поэтому существует большое количество метрик, анализирующих изображение. Для анализа были выбраны следующие метрики: PSNR, SSIM, MSE, Сorr, экспертная оценка человеческого зрения.

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

2 РАЗРАБОТКА АЛГОРИТМА СЖАТИЯ ИЗОБРАЖЕНИЯ С ИСПОЛЬЗОВАНИЕМ ВЕЙВЛЕТ - ПРЕОБРАЗОВАНИЙ

Как показано в пункте 1, изображение имеет избыточную информацию, для сжатия её можно удалить из него так, что восстановленное изображение не будет отличаться ничем для зрения человека. Поэтому разрабатываемый алгоритм, будет ориентирован на статические изображения (цветные изображения, которые содержат много полутонов), как наиболее используемые в телекоммуникационных сетях. Любое изображение может быть представлено тремя двумерными матрицами, содержащими исходные данные для каждого слоя цвета (R , G, B). Тогда общую схему работы кодера возможно отобразить так:

Общая схема кодера

Рисунок 2.1 – Общая схема кодера.

2.1 Выбор вейвлета для разложения

Сейчас выбор вейвлетов достаточно велик. Только в пакете Wavelet Toolbox 2.0/2.1 представлены полтора десятка базовых типов вейвлетов и множество вариантов для ряда базовых типов вейвлетов. Однако, необоснованное применение того или иного типа вейвлета может привести к ошибкам. Такой выбор следует рассматривать как первое приближение. Разумеется, при решении серьезных задач в области обработки сигналов и изображений желательно применение хотя бы нескольких типов вейвлетов с последующим сравнением результатов и выбора лучшего из них. Алгоритм, который был описан выше, может работать на любых вейвлета, поддерживающих дискретный двумерный анализ. Приведем графический пример разложения некоторого изображения.

Пример разложения изображения до четвертого уровня вейвлетом Добеши. Анимация: 4 кадра, 0.8 сек задержка, размер 118 Кб,неограниченное число повтров, программа: Easy GIF Animator

Рисунок 2.2 – Пример разложения изображения до четвертого уровня вейвлетом Добеши.
(Анимация: 4 кадра, 0.8 сек задержка, размер 118 Кб, неограниченное число повтров, программа – Easy GIF Animator)

Оценку отображения будем осуществлять по критериям которые воспроизведения были описаны пункте 1 нашей работы и по параметрам Nzero и Ereg. Где Nzero-количество нулей в матрицах коэффициентов изображения, а Ereg - значение восстановленной энергии при значении порога обработки - "Remove near 0" - порога удаления значения, близкого к 0. Данные исследования сведем в таблицу 2.1

Таблиця 2.1 – Результаты общего анализа вейвлетов.

– Результаты общего анализа вейвлетов

Исходя из результатов таблицы 2.1 остановим свой выбор на вейвлет Добеши и рассмотрим их более подробно. Данные исследования сведем в таблицу 2.2

Таблиця 2.2 – Результаты анализа вейвлетов Добеши .

– Результаты анализа вейвлетов Добеши

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

Таблиця 2.3 – Результаты анализа уровня разложения вейвлетов Добеши.

– Результаты анализа уровня разложения вейвлетов Добеши

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

Таблиця 2.4 – Результаты анализа обработки для вейвлета Добеши4 .

– Результаты анализа обработки для вейвлета Добеши4

Исходя из данных исследования, можно выбрать метод извлечения значения близкого к 0 (Rem. n0), как наиболее качественного из всех методов..

3 АНАЛИЗ РЕЗУЛЬТАТОВ РАБОТЫ КОДЕРА

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

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

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

– График зависимости метрики от коэффициента сжатия

Рисунок 3.1 – График зависимости метрики от коэффициента сжатия.

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

3.2 Анализ размеров сжатого изображения

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

Таблиця 3.1– Статистические сравнения.

– Статистические сравнения

На данном этапе собственный алгоритм проигрывает формату JPG так, как в нем не были реализованы некоторые важные алгоритмы, такие как учет корреляции цветных слоев и соседних пикселей в слое. Чтобы сделать окончательные выводы относительно работы алгоритма необходимо взять несколько изображений, которые будут отличаться цветовой палитрой, количеством объектов, иметь одинаковые размеры и много цветных переходов. Результаты их сжатия сравнить между собой. Тогда средний коэффициент сжатия для кодера будет: 8,4. Такой коэффициент выше коэффициента сжатия алгоритмов сжатия без потерь, но не очень большой.

ВЫВОДЫ

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

СПИСОК ЛИТЕРАТУРЫ

  1. Родионов И.В. «Использование вейвлет-преобразований для обработки цветных цифровых изображений.» 58-ма НТК СП6ГУТ. 2005 р. –14с.
  2. Смоленцев Н.К. «Основы теории вейвлетов. Вейвлеты в MATLAB».М.ДМК Прес 2005 р.–304 с.
  3. Илюшкина Н. , Чобану М.«Применение новых критериев оценки качества изображений после их сжатия.» Современная электроника. №3 2007г. –4с.
  4. Ватолин Д.С. «Алгоритмы сжатия изображений.» М. Методическое пособие. 1999г. -150с.
  5. Потемкин В.Г. «Система инженерных и научных расчетов MATLAB 5.x.» – В 2-х т. Том 2. – М.: ДИАЛОГ-МИФИ, 1999 –336 с.
  6. Дьяконов В. MATLAB. «Обработка сигналов и изображений. Специальный справочник.» – С-Пб.: Питер, 2002. –608 с.
  7. Воробьев В.И., Грибунин В.Г. «Теория и практика вейвлет-преобразования.» – СПб.: Изд-во ВУС, 1999 –204 с.
  8. Добеши И. «Десять лекций по вейвлетам.» – М.: Ижевск: РХД, 2001 –189 с.