Diplom_29-06 (1221240), страница 4

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

Текст из файла (страница 4)

Сегодня наиболее распространенным алгоритмом архивации графики является JPEG. Сравнивая алгоритм с JPEG можно заметить некоторые особенности [33].

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

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

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

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

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

Метод подсчёта кубов - напрямую выводится из определения фрактальной размерности подсчётом коробок. Алгоритм основан на следующих шагах: кубическая решетка с постоянной решетки l накладывается на растянутую по z поверхность. Вначале l устанавливается на X/2 (где X – половина стороны поверхности), в результате получается решетка из 2×2×2 = 8 кубов. Тогда N(l) – число кубов, которые содержат хотя бы один пиксель изображения. Постоянная решетки l затем последовательно на каждом шаге уменьшается вдвое и процесс повторяется пока l не станет равным расстоянию между двумя соседними пикселями. Наклон графика log(N(l)) от log(1/l) даёт непосредственно фрактальную размерность D_f.

Метод триангуляции – похож на алгоритм подсчёта кубов и также основан на определении фрактальной размерности, основанном на подсчёте коробок. Метод работает следующим образом: сетка с размером ячейки в одну единицу измерения l помещается на поверхность. Это определяет положения вершин набора треугольников. Когда, например, l = X/4, поверхность покрыта 32 треугольниками различной площади наклонёнными под разными углами по отношению к плоскости xy. Площади всех треугольников рассчитываются и суммируются чтобы получить приближенную площадь поверхности S(l), соответствующую l. размер сетки затем уменьшается последовательно в два раза на каждом шаге, как и раньше, процесс продолжается до тех пор. пока l не станет равным расстоянию между двумя соседними точками. Наклон графика S(l) от log(1/l) при этом соответствует D_f − 2.

Вариационный метод – основан на зависимости от масштаба фракционного броуновского движения. На практике, в вариационном методе делят полную поверхность на равносторонние квадратные коробки, и вариация (степень среднеквадратичного значения высоты) рассчитывается для заданного размера коробок. Фрактальная размерность рассчитывается из наклона β аппроксимированной методом наименьших квадратов линии на графике в двойном логарифмическом масштабе вариации как D_f = 3 − β/2.

Метод спектра мощности – основан на зависимости спектра мощности фракционного броуновского движения. В методе спектра мощности к каждому профилю высоты вдоль линии, из которых состоит изображение применяется преобразование Фурье, рассчитывается спектр мощности и все эти спектры усредняются. Фрактальная размерность определяется из наклона β аппроксимирующей линии, проведённой по методу наименьших квадратов на построенном в двойном логарифмическом масштабе графике спектра мощности, как D_f = 7/2 − β/2.

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

Таблица 1.1 ­– Характеристика алгоритмов сжатия

Продолжение таблицы 1.1

1. Проектирование приложения

   1. Назначение разрабатываемого приложения

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

1. Требования к системе

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

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

• загрузка исходного изображения;

• просмотр изображения, вывод его на экран;

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

• выполнение кодирования в соответствии с выбранным алгоритмом и параметрами;

• вывод преобразованного изображения;

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

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

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

Величины V₁ и V₂ выражаются в байтах. К_сж – величина безразмерная.

Среднеквадратическое отклонение значений яркости или цветности пикселей сжатого изображения от оригинала определяется в соответствии с выражением: Также возможно найти среднеквадратическое отклонение значений пикселей сжатого изображения от оригинала, для этого нужно взять исходное и восстановленное изображение размером MxN, также называемой как среднеквадратичная ошибка(MSE – Mean Square Error):

где M – высота и N – ширина исходного и преобразованного изображений в пикселях соответственно, x,y – координаты пикселя, f(x,y) –значение функции яркости или цвета пикселя (с координатами x,y) в исходном изображении, f ̂(x,y) – значение функции яркости или цвета пикселя (с координатами x, y) в преобразованном изображении.

Другим критерием является максимальное отклонение искаженного изображения от оригинала:

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

На практике используют соотношения сигнал/шум (PSNR – peak signal to noise ratio).

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

Характеристики

Список файлов ВКР