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

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

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

Получил широкое распространение на страницах интернет ресурсов.

Формат TIFF (Tagged Image File Format) создавался специально для хранения сканированных изображений. Исключительная гибкость формата сделала его действительно универсальным. В нем можно хранить графику в любом режиме: от битового и индексированных цветов до изображений в цветовых представлениях Lab, CMYK и RGB (кроме дуплексов и многоканальных документов).

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

• PackBits (RLE);

• Lempel-Ziv-Welch (LZW);

• LZ77;

• ZIP;

• JBIG;

• JPEG;

• CCITT Group 3, CCITT Group 4.

Формат TIFF позволяет хранить изображения, сжатые по стандарту JPEG, без потерь данных (JPEG-LS), что является преимуществом по сравнению с использованием алгоритма JPEG для формата JPEG.

Алгоритмы CCITT Group 3 и 4 предназначены для кодирования бинарных растровых изображений. Первоначально они были разработаны для сетей факсимильной связи и поэтому их еще называют Fax 3, Fax 4. В настоящий момент они также используются в полиграфии, системах цифровой картографии и географических информационных системах. Алгоритм Group 3 напоминает RLE, так как кодирует линейные последовательности пикселей, а Group 4 ­- двумерные поля пикселей.

1. Алгоритм Deflate

Алгоритм Deflate относится к группе алгоритмов сжатия без потерь и использует совместно алгоритмы LZ77 и Хаффмана[34].

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

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

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

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

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

Рисунок 7 – Результат работы алгоритма Deflate

PNG (portable network graphics) представляет собой растровый формат хранения графической информации, использующий сжатие без потерь по алгоритму Deflate. Он был разработан как формат данных для замены GIF. Создавался специально для использования в сети Интернет. Позволяет выбирать палитру сохранения, включающую серые полутона, 256 цветов, true color. Позволяет использовать прозрачность. В отличие от GIF сжатие производится и по горизонтали и по вертикали.

Существует три разновидности формата: PNG8, PNG24, PNG48, где цифры означают максимальную глубину цвета, возможную в цветовой палитре.

Формат PNG обладает более высокой степенью сжатия для файлов с большим количеством цветов, чем GIF. Разница составляет около 5-25%, что является недостаточным для абсолютного преобладания формата, так как небольшие 2-16-цветные файлы формат GIF сжимает с не меньшей эффективностью.

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

1. Алгоритм JPEG

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

• .jpg;

• .jfit;

• .jpe;

• .jpeg.

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

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

Первым этапом кодирования является перевод изображения из цветовой палитры RGB (R – Red, G – Green, B – Blue) в палитру YCbCr (иногда ее еще именуют YUV), где Y – компонента яркости, а Cr, Cb — каналы изображения, отвечающие за цвет (хроматический красный и хроматический синий).

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

Рисунок 8 – Иллюстрация перевода изображения пространства RGB в YCbCr

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

(1)

Для того, чтобы выполнить обратное преобразование к цветовому пространству RGB, необходимо умножить вектор YUV на обратную матрицу в соответствии с (2):

(2)

Затем к полученному цветовому пространству YCbCr применяется операция «прореживания». Преобразование заключается в том, что блоку пикселей (2x2) канала Y присваивается усредненное значение каналов Cb и Cr. При этом используется 4 значения Y канала и всего по одному – Cb и Cr.

Далее, яркостный компонент Y и отвечающие за цвет компоненты Cb и Cr, разбиваются на блоки 8х8 пикселей. Каждый из блоков подвергается дискретному косинусному преобразованию (ДКП). Данные коэффициенты умножаются на матрицу квантования и затем кодируются, используя коды Хаффмана. Именно этот шаг отвечает за степень сжатия. Если матрица квантования с большими коэффициентами, в результате получится большее число нулей, а также большая степень сжатия.

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

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

В результате получится4 матрицы HH0, HL0, LH0, LL0, соответствующие фильтрации фильтром h1(n) по строкам и столбцам, фильтром h1(n) по строками фильтром h0(n) по столбцам, фильтром h0(n) по строкам и фильтром h1(n) по столбцам, и фильтром h0(n) по строкам и столбцам.

Далее подвергается вейвлет разложению матрица LL0. На выходе получатся матрицы HH1, HL1, LH1, LL1. Такое разложение будет повторяться r количество раз, и результатом будет являться набор из 3r+1 матриц уменьшающейся размерности. Затем каждая матрица подвергается скалярному или векторному квантованию и последующему кодированию. Выбор числа уровней квантования или шага квантования производится в соответствии с требуемым сжатием и распределением битов между матрицами. Данное разложение представлено на рисунке 9.

Рисунок 9 – Трехуровневое вейвлет-преобразование

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

Главным преимуществом данного преобразования является то, что оно не вносит дополнительной избыточности в исходные данные, что позволяет восстановить изображение с использованием тех же самых фильтров. Также если выбирается параметр сжатия с потерями то можно сжать изображение от 3 до 10 раз без особых потерь информации и с допустимыми потерями – до 300 раз.

Дискретное вейвлет-преобразование (DWT) - реализация вейвлет-преобразования с использованием дискретного набора масштабов и переносов вейвлета, подчиняющихся некоторым определённым правилам. Другими словами, это преобразование раскладывает сигнал на взаимно ортогональный набор вейвлетов, что является основным отличием от непрерывного вейвлет-преобразования (CWT), или его реализации для дискретных временных рядов, иногда называемой непрерывным вейвлет-преобразованием дискретного времени (DT-CWT)[30].

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

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

После введения некоторых дополнительных условий можно получить результат всех этих уравнений, т.е. конечный набор коэффициентов a_k которые определяют функцию масштабирования, а также вейвлет. Вейвлет получается из масштабирующей функции как N где N - чётное целое. набор вейвлетов затем формирует ортонормированный базис, который мы используем для разложения сигнала. Следует отметить, что обычно только несколько коэффициентов a_k будут ненулевыми, что упрощает расчёты [28].

На рисунках 10 и 11 показаны некоторые масштабирующие функции и вейвлеты. Наиболее известным среди семейства ортонормированных вейвлетов является семейство Добеши. Её вейвлеты обычно обозначаются числом ненулевых коэффициентов a_k, таким образом, обычно упоминаются вейвлеты Добеши 4, Добеши 6, и т.п. Другой из упомянутых вейвлетов – простейший вейвлет Хаара, который использует прямоугольный импульс как масштабирующую функцию.

Рисунок 10 – Функция масштабирования Хаара и вейвлет

Рисунок 11 – Функция масштабирования Добеши и вейвлет

Существует несколько видов реализации алгоритма дискретного вейвлет-преобразования. Самый старый и наиболее известный – алгоритм Малла (пирамидальный). В этом алгоритме два фильтра – сглаживающий и несглаживающий составляются из коэффициентов вейвлета и эти фильтры рекуррентно применяются для получения данных для всех доступных масштабов. Если используется полный набор данных D = 2^N и длина сигнала равна L, сначала рассчитываются данные D/2 для масштаба L/2^{N - 1}, затем данные (D/2)/2 для масштаба L/2^{N - 2}, … пока в конце не получится 2 элемента данных для масштаба L/2. результатом работы этого алгоритма будет массив той же длины, что и входной, где данные обычно сортируются от наиболее крупных масштабов к наиболее мелким.

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

1. Алгоритм фрактального сжатия

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

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

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