Методы сжатия информации в полиграфии

Рассмотрим работу алгоритма подробнее. Предположим, что сжимается полноцветное 24-битное изображение. В этом случае получаем следующие этапы работы.

Шаг 1. Переводим изображение из пространства RGB в пространство YCbCr с помощью следующего выражения:

.

Отметим сразу, что обратное преобразование легко  получается путем умножения обратной матрицы на вектор  , который по существу является пространством YUV:

.

Шаг 2. Разбиваем исходное изображение на матрицы 8х8. Формируем из каждой три рабочие матрицы ДКП – по 8 бит отдельно для каждой компоненты. При больших степенях сжатия блок 8х8 раскладывается на компоненты YCbCr в формате 4:2:0, т.е. компоненты для Cb и Cr берутся через точку по строкам и столбцам.

Шаг 3. Применение ДКП к блокам изображения 8х8 пикселей. Формально прямое ДКП для блока 8х8 можно записать в виде

,

где  . Так как ДКП является «сердцем» алгоритма JPEG, то желательно на практике вычислять его как можно быстрее. Простым подходом для ускорения вычислений является заблаговременное вычисление функций косинуса и сведения результатов вычисления в таблицу. Мало того, учитывая ортогональность функций косинусов с разными частотами, вышеприведенную формулу можно записать в виде

.

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

.

Здесь   - результат ДКП, для вычисления которого требуется   операций умножения и почти столько же сложений, что существенно меньше прямых вычислений по формуле выше. Например, для преобразования изображения размером 512х512 пикселей потребуется   арифметических операций. Учитывая 3 яркостных компоненты, получаем значение 12 582 912 арифметических операций. Количество умножений и сложений можно еще больше сократить, если воспользоваться алгоритмом быстрого преобразования Фурье. В результате для преобразования одного блока 8х8 нужно будет сделать 54 умножений, 468 сложений и битовых сдвигов.

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

Шаг 4. Квантование. На этом шаге происходит отбрасывание части информации. Здесь каждое число из матрицы   делится на специальное число из «таблицы квантования», а результат округляется до ближайшего целого:

.

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

          

светимость                                                                   цветность

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

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

Шаг 5. Переводим матрицу 8х8 в 64-элементный вектор при помощи «зигзаг»-сканирования (рис. 2).

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

Шаг 6. Преобразовываем вектор с помощью модифицированного алгоритма RLE, на выходе которого получаем пары типа (пропустить, число), где «пропустить» является счетчиком пропускаемых нулей, а «число» - значение, которое необходимо поставить в следующую ячейку. Например, вектор 1118 3 0 0 0 -2 0 0 0 0 1 … будет свернут в пары (0, 1118) (0,3) (3,-2) (4,1) … .

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

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

Схема упорядочения DC коэффициентов

Рис. 4. Структурная схема алгоритма JPEG

Процесс восстановления изображения в этом алгоритме  полностью симметричен. Метод позволяет  сжимать изображения в 10-15 раз  без заметных визуальных потерь.

При разработке данного стандарта руководствовались  тем, что данный алгоритм должен был  сжимать изображения довольно быстро – не более минуты на среднем  изображении. Это в 1991 году! А его  аппаратная реализация должна быть относительно простой и дешевой. При этом алгоритм должен был быть симметричным по времени  работы. Выполнение последнего требования сделало возможным появление  цифровых фотоаппаратов, снимающие 24 битные изображения. Если бы алгоритм был несимметричен, было бы неприятно долго ждать, пока аппарат «перезарядится» - сожмет изображение.

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

     Заключение 

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

Принято различать  архивацию и упаковку (компрессию, сжатие) данных. В первом случае речь идет о слиянии нескольких файлов и даже каталогов в единый файл — архив (примером использования  такой технологии в чистом виде может  служить формат TAR). Во втором — о  сокращении объема исходных файлов путем  устранения избыточности (в данной работе рассматривается упаковка без  потерь информации, т. е. с возможностью точного восстановления исходных файлов). Как правило, современные архиваторы обеспечивают также сжатие данных, являясь, таким образом, еще и  упаковщиками, однако существуют и  чисто «упаковочные» утилиты  типа Gzip, сжимающие отдельные файлы.

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

Для хранения файлов я взял за основу метод сжатия JPEG 2000. По сравнению с JPEG он имеет:

Бо́льшую степень сжатия: на высоких битрейтах, где артефакты незначительны, JPEG 2000 имеет степень сжатия в среднем на 20 %[источник не указан 360 дней], больше, чем JPEG. На низких битрейтах JPEG 2000 также имеет преимущество над основными режимами JPEG. Большая степень сжатия достигается благодаря использованиюдискретного вейвлет-преобразования и более сложного энтропийного кодирования.

Масштабируемость  фрагментов изображений: JPEG 2000 обеспечивает бесшовное сжатие разных компонентов  изображения, с каждым компонентом  хранится от 1 до 16 бит на семпл. Благодаря разбиению на блоки можно хранить изображения разных разрешений в одном кодовом потоке.

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

Гибкий формат файла: форматы файлов JP2 и JPX обеспечивают хранение информации о цветовых пространствах, метаданных и информации для согласованного доступа в сетевых приложениях, взаимодействующих с помощью  протокола JPEG Part 9 JPIP.

К недостаткам  сжатия по стандарту JPEG следует отнести  появление на восстановленных изображениях при высоких степенях сжатия характерных  артефактов: изображение рассыпается  на блоки размером 8x8 пикселов (этот эффект особенно заметен на областях изображения с плавными изменениями  яркости), в областях с высокой  пространственной частотой (например, на контрастных контурах и границах изображения) возникают артефакты в виде шумовых ореолов. Следует отметить, что стандарт JPEG (ISO/IEC 10918-1, Annex K, п. K.8) предусматривает использование специальных фильтров для подавления блоковых артефактов, но на практике подобные фильтры, несмотря на их высокую эффективность, практически не используются. Однако, несмотря на недостатки, JPEG получил очень широкое распространение из-за достаточно высокой (относительно существовавших во время его появления альтернатив) степени сжатия, поддержке сжатия полноцветных изображений и относительно невысокой вычислительной сложности. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

     Список  использованных источников 

     1. Кузнецов Ю.В.Технология обработки изобразительной информации.СПб: Изд-во "Петербургский институт печати", 2002.  312 с.

     2. 1. Ю.Н. Самарин, Н.Л.Сапожников, М.А. Синяк. Допечатное оборудование. М.: МГУП, 2000г.

     3. Г. Кипхан. Энциклопедия по печатным средствам информации. М.: МГУП, 2003 г.

     4. Стефанов С.И. Путеводитель в мире полиграфии. М. Унисерв, 1998

     5. Воробьев В.И., Грибунин В.Г. Теория и практика вейвлет-преобразования., ВУС, 1999. С. 1-204.

     6. Зелов С. Стандарт JPEG-кодирование неподвижных изображений Компьютер Пресс №5, 1997 с. 82-84.

     7. Д.С. Ватолин. Алгоритмы сжатия изображений www.useic.ru\~dv\ fractal\index.htm.

     8. Уидроу Б., Стирнз С. Адаптивная обработка сигналов: Пер. с англ. – М.: Радио и связь, 1989. – 440 с.: ил.

     9. Прикладная теория случайных процессов и полей / Васильев К.К., П 75 Драган Я.П., Казаков В.А. и др.; Под ред. Васильева К.К., Омельченко В.А. Ульяновск: УлГТУ, 1995. 256 с.

     10. Д.Сэломон. Сжатие данных, изображений и звука - Москва: Техносфера, 2004. - 368с.