МИНИСТЕРСТВО  ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

Московский  государственный  университет печати имени Ивана Фёдорова

Факультет полиграфической  техники и технологии

Специальность 261202.65 «Технология полиграфического производства»

КУРСОВАЯ  РАБОТА

Москва, 2001

МИНИСТЕРСТВО  ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

Московский  государственный  университет печати

Факультет полиграфической  техники и технологии

Специальность 261202.65 «Технология полиграфического производства»

ЗАДАНИЕ НА ВЫПОЛНЕНИЕ КУРСОВОЙ РАБОТЫ

РЕФЕРАТ

Цель  работы: разработка технологии изготовления гибкой упаковки для конфет из композитного материала.

Работа  содержит: 24 страницы, 7 схем, 5 таблиц.

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

Сокращения:     ДКП - дискретное косинусное преобразование                          

  Техническая характеристика  изделия

     Содержание 

Введение           3

  1. Показатель степени сжатия файлов      4

  2. Алгоритм RLE          5

  3. Алгоритм LZW          5

  4. Алгоритм  ДИКМ и JPEG-LS       6

  5. Стандарт сжатия JPEG        7

  5. Другие виды сжатия информации       9

Заключение          17

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

     Введение 

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

Поскольку каждый пиксел принято интерпретировать в  виде 24-битового числа, в котором  компоненты красного, зеленого и голубого цветов занимают по 8 бит каждый. Такой 24-битовый пиксел может отображать   миллионов цветов. Тогда изображение с разрешением 512х512 пикселов будет занимать 786432 байта. А изображению размером 1024х1024 пиксела потребуется 3145728 байт для его хранения. Все это объясняет важность сжатия изображений.

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

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

1. Показатель  степени сжатия файлов

Чтобы говорить о сжатии информации, необходимо сначала  понять, за счет чего в принципе возможно сжатие конечных цифровых последовательностей? Чтобы показать принцип кодирования (сжатия) информации, который положен  в основу всех современных кодеров  сжатия без потерь, рассмотрим такой  простой пример:  000011112222333555566666. Теперь подряд идущие цифры заменим парой <значение, количество>, получим: 041424335465 и получаем сокращение исходной последовательности в 2 раза (24/12). Если обобщить эту идею, то можно заключить, что кодер находит статистические закономерности в цифровой последовательности и за счет этого осуществляет сжатие (кодирование).

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

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

Степень сжатия принято определять либо как коэффициент  сжатия, равный

,

где   - размер закодированного (сжатого) изображения;   - размер исходного изображения, либо как фактор сжатия:

.

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

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

3. Типы изображений

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

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

2. Полутоновое  изображение. Каждый пиксел такого  изображения может иметь   значений от 0 до  , обозначающих одну из   градаций серого (или иного) цвета. Число   обычно сравнимо с размером байта, то есть, оно равно 4, 8, 12, 16, 24 или другое кратное 4 или 8. Множество самых значимых битов всех пикселов образуют самую значимую битовую плоскость или слой изображения. Итак, полутоновое изображение со шкалой из   уровней составлено из   битовых слоев.

3. Цветное изображение.  Существует несколько методов  задания цвета, но в каждом  из них участвуют три параметра.  Следовательно, цветной пиксел  состоит из трех частей. Обычно, цветной пиксел состоит из  трех байтов. Типичными цветовыми  моделями являются RGB, HLS и CMYK.

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

5. Дискретно-тоновое  изображение (оно еще называется  синтетическим). Обычно, это изображение  получается искусственным путем.  В нем может быть всего несколько  цветов или много цветов, но  в нем нет шумов и пятен  естественного изображения. Примерами  таких изображений могут служить  фотографии искусственных объектов, машин или механизмов, страницы  текста, карты, рисунки или изображения  на дисплее компьютера. (Не каждое  искусственное изображение будет  обязательно дискретно-тоновым.  Сгенерированное компьютером изображение,  которое должно выглядеть натуральным,  будет иметь непрерывные тона, несмотря на свое искусственное  происхождение.) Искусственные объекты,  тексты, нарисованные линии имеют  форму, хорошо определяемые границы.  Они сильно контрастируют на  фоне остальной части изображения  (фона). Прилегающие пикселы дискретно-тонового  образа часто бывают одиночными  или сильно меняют свои значения. Такие изображения плохо сжимаются  методами с потерей данных, поскольку  искажение всего нескольких пикселов  буквы делает ее неразборчивой,  преобразует привычное начертание  в совершенно неразличимое. Методы  сжатия изображений с непрерывными  тонами плохо обращаются с  четкими краями дискретно-тоновых  образов, для которых следует  разрабатывать особые методы  компрессии. Отметим, что дискретно-тоновые  изображения, обычно, несут в себе  большую избыточность. Многие ее  фрагменты повторяются много  раз в разных местах изображения.

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

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

На настоящий  момент известны два наиболее широко распространенных алгоритма сжатия с потерей информации: JPEG и JPEG2000. Алгоритм JPEG имеет в своей основе дискретное косинусное преобразование (ДКП), которое применяется к неперекрывающимся  блокам изображения размером 8х8 пикселов. Данный метод сжатия изображений  был исследован в большом числе  работ [1-3]. К основным недостаткам  данного метода относятся: распад кодируемого  изображения на отдельные блоки  по 8х8 пикселов при больших коэффициентах  сжатия; появление ложных контуров; плохое описание нестационарного во времени сигнала коэффициентами Фурье-преобразования. Для преодоления  указанных недостатков был предложен  новый стандарт сжатия изображений JPEG2000, основу которого составляет вейвлет-преобразование. В этом случае все изображение  раскладывается по базисным вейвлет-функциям, локализованным как во временной, так  и в частотной областях. Это  дает возможность создавать алгоритмы  быстрого вейвлет-преобразования, а  также не разбивать изображение  на отдельные независимые блоки. Благодаря такому подходу в вейвлет-коэффициентах  образуются длинные цепочки подряд идущих нулей, которые эффективно сжимаются  энтропийными кодерами. 
 

2. Алгоритм RLE.

Алгоритм необычайно прост в реализации. Групповое  кодирование — от английского Run Length Encoding (RLE) — один из самых старых и самых простых алгоритмов архивации  графики. Изображение в нем вытягивается в цепочку байт по строкам растра. Сжатие в RLE происходит за счет того, что в исходном изображении встречаются цепочки одинаковых байт. Замена их на пары <счетчик повторений, значение> уменьшает избыточность данных.

В первом алгоритме  признаком счетчика служат единицы  в двух верхних битах считанного файла:

Соответственно  оставшиеся 6 бит расходуются на счетчик, который может принимать  значения от 1 до 64. Строку из 64 повторяющихся  байтов мы превращаем в два байта, т.е. сожмем в 32 раза.

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

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

Признаком повтора  в данном алгоритме является единица  в старшем разряде соответствующего байта:

Как можно легко  подсчитать, в лучшем случае этот алгоритм сжимает файл в 64 раза (а не в 32 раза, как в предыдущем варианте), в  худшем увеличивает на 1/128. Средние  показатели степени компрессии данного  алгоритма находятся на уровне показателей  первого варианта. Похожие схемы компрессии использованы в качестве одного из алгоритмов, поддерживаемых форматом TIFF, а также в формате TGA.  

3. Алгоритм LZW

Название алгоритм получил по первым буквам фамилий  его разработчиков — Lempel, Ziv и Welch. Сжатие в нем осуществляется за счет одинаковых цепочек байт.  Процесс  сжатия выглядит достаточно просто. Мы считываем последовательно символы  входного потока и проверяем, есть ли в созданной нами таблице строк  такая строка. Если строка есть, то мы считываем следующий символ, а  если строки нет, то мы заносим в  поток код для предыдущей найденной  строки, заносим строку в таблицу  и начинаем поиск снова. LZW реализован в форматах GIF и TIFF.

Алгоритм LZW имеет  несколько особенностей своей реализации в формате сжатия изображений gif. Первая особенность – это переменный размер кода таблицы цепочек, который  не может превышать 12 бит, т.е. не превышать  числа 4095. Вторая особенность состоит  в использовании двух специальных  кодов – это код обновления (реинициализации) таблицы цепочек, и код завершения потока символов .

В самом начале своей работы алгоритм определяет количество цветов, используемых в изображении. В случае GIF их максимум может быть 256, т.к. любое изображение, даже с  большим набором цветов преобразуется  в 256 цветовое пространство. Минимум  может быть 2 цвета. Если используется только два цвета, то начальный размер кодов в таблице равен 3 битам. Причем коду 0 ставится цвет 0, а коду 1 – цвет 1. Коды 4 и 5 соответствуют  коду очистки таблицы и коду. При большем количестве цветов размер кода таблицы равен числу бит N, приходящихся на один пиксел. При этом специальные коды равны. Начальный размер кодов в таблице записывается в заголовок GIF файла.

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

Разработчики  формата GIF ограничили максимальный размер кодов в таблице 12 битами. Это  значит, что когда код достигает  значения, то размер увеличивать уже  нельзя. Но в то же время и размер кодов становится больше 12 бит. Как  разрешить данную ситуацию? Простым  решением является выполнить перегенерирование  таблицы последовательностей, после  чего она будет содержать только цепочки длины, равной 1, т.е. значения пикселей и плюс специальные коды. Таким образом, она перейдет в  то же состояние, в котором была на момент начала кодирования изображения. А для того, чтобы декодировщик знал, что в определенный момент произошло перегенерирование таблицы, кодировщик в выходной поток записывает код управляющего символа.  

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

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

4. Алгоритм  ДИКМ и JPEG-LS

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

В общем случае оценка элемента строится на основе линейной комбинации нескольких предыдущих отсчетов:

,

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

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

Полученная ошибка подвергается равномерному квантованию  с шагом   согласно следующей формуле:

.

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

Алгоритм ДИКМ применяется в стандарте JPEG при  сжатии изображений без потерь. В  начале отсчеты исходного изображения  заменяются на целочисленные разности между истинным значением яркости пиксела и его целочисленным (округленным) прогнозом. При этом прогноз текущего пиксела   строится по трем ближайшим соседям.

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

5. Стандарт сжатия JPEG

Алгоритм разработан группой экспертов в области  фотографии (Joint Photographic Expert Group) специально для сжатия 24-битных и полутоновых  изображений в 1991 году. Этот алгоритм не очень хорошо сжимает двухуровневые  изображения, но он прекрасно обрабатывает изображения с непрерывными тонами, в которых близкие пикселы обычно имеют схожие цвета. Обычно глаз не в состоянии заметить какой-либо разницы при сжатии этим методом в 10 или 20 раз.

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