Методы сжатия данных в графических файлах

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

РЕФЕРАТ

на тему: «Методы сжатия данных в графических файлах»

Введение

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

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

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

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

Целью данной работы является определение методов сжатия данных в графических файлах.

При написании данной работы использовались следующие методы: исторический, логический, описательный, анализ и синтез.

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

1. Понятие сжатия данных

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

В зависимости от того, в каком объекте размещены данные, подлежащие сжатию различают:

Сжатие (архивация) файлов: используется для уменьшения размеров файлов при подготовке их к передаче каналами связи или к транспортированию на внешних носителях маленькой емкости;

Сжатие (архивация) папок: используется как средство уменьшения объема папок перед долгим хранением, например, при резервном копировании;

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

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

Если при сжатии данных происходит изменение их содержимого, то метод сжатия называется необратимым, то есть при восстановлении (разархивировании) данных из архива не происходит полное восстановление информации.

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

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

JPEG - для графических данных.

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

GIF, TIFF - для графических данных.

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

- степень сжатия (compress rating) или отношение (ratio) объемов исходного и результирующего потоков;

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

- качество сжатия - величина, показывающая на сколько сильно упакован выходной поток, при помощи применения к нему повторного сжатия по этому же или иному алгоритму. Ватолин Д. С. Тенденции развития алгоритмов архивации графики // Открытые системы. - Зима 1995. - № 4.

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

алгоритм RLE (Run Length Encoding);

алгоритмы группы KWE (KeyWord Encoding);

алгоритм Хаффмана.

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

2. Некоторые методы сжатия данных в графических данных

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

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

При таком подходе можно восстанавливать нужную информацию без потерь. Компрессия же не гарантирует полного восстановления исходных данных, поэтому ее основная задача - не «убить» что-нибудь очень ценное в погоне за уменьшением объема. Обычно информация, подвергнутая компрессии, занимает значительно меньше объема, чем сохраненная методами архивации. Именно это обстоятельство и оставляет этому методу место под солнцем. Регулирование степени сжатия дает право на выбор: размер выходного файла или сохранение его качества. Рассмотрим несколько алгоритмов сжатия данных, которые не вносят изменений в исходные файлы и гарантируют полное восстановление данных.

RLE (RUN LENGTH ENCODING)

Метод сжатия данных, при котором одинаковые последовательности одних и тех же байтов заменяются однократным упоминанием повторяющегося байта (или целой цепочки байтов) и числа его повторений в исходных данных. Например, строка типа 0100 0100 0100 0100 0100 0100 0100 0100, описывающая некую группу пикселей, будет заменена на запись типа 0100х8 и т.п. Климов А. С. Форматы графических файлов. - С.-Пб.: ДиаСофт. 1995.

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

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

CCITT GROUP 3, CCITT GROUP 4

Эти два похожие метода сжатия графических данных работают с однобитными изображениями, сохраненными в цветовой модели Bitmap. Основаны на поиске и исключении из исходного изображения дублирующихся последовательностей данных (как и в предыдущем типе сжатия - RLE). Оба ориентированы на упаковку именно растровой графической информации, так как работают с отдельными рядами пикселей в изображении. Изначально алгоритм был разработан для сжатия данных, передаваемых через факсимильные системы связи (CCITT Group 3), а более совершенная разновидность этого метода архивации данных (CCITT Group 4) подходит для записи монохромных изображений с более высокой степенью сжатия. Как и предыдущий алгоритм, он в основном подходит для сжатия изображений с большими одноцветными областями. Его достоинство - скорость выполнения, а недостаток - в ограничениях при компрессии графических данных (не все данные удается эффективно сжать таким образом). Этот метод - для файлов формата.PDF, PostScript (в инкапсулированных объектах) и других. Ватолин Д., Ратушняк А., Смирнов М., Юкин. В. Методы сжатия данных. - М., 2003.

LZW (LEMPLE-ZIF-WELCH)

Алгоритм сжатия данных, основанный на поиске и замене в исходном файле одинаковых последовательностей данных для их исключения и уменьшения размера «архива». В отличие от предыдущих рассмотренных методов сжатия, более «интеллектуально» просматривает сжимаемое cодержимое, а все ради большей степени сжатия данных. Данный тип сжатия не вносит искажений в исходный графический файл и подходит для обработки растровых данных любого типа - монохромных, чернобелых или полноцветных. Наилучшие результаты получаются при компрессии изображений с большими областями одинакового цвета или изображений с повторяющимися одинаковыми структурами. Этот метод демонстнрирует самые поразительные результаты степени сжатия (среди других существующих методов сжатия графических данных) при полном отсутствии потерь или искажений в исходных файлах. Используется в файлах формата.TIFF.PDF.GIF, PostScript (в инкапсулированных объектах) и других.

ZIP

Метод сжатия, аналогичный использующемуся в популярном алгоритме архивации PKZip. В основу ZIP положен метод, аналогичный LZW. Как и LZW, не вносит искажений в исходный файл и лучше всего подходит для обработки графических данных с одинаковыми одноцветными или повторяющимися областями. Используется в файлах формата.PDF.TIFF и некоторых других. А теперь рассмотрим алгоритмы и методы конвертирования данных, которые вносят изменения в исходные файлы, показывая при этом более высокую степень качества упаковки графических изображений.

JPEG (JOINT PHOTOGRAPHIC EXPERTS GROUP)

Метод, используемый для хранения полутоновых и полноцветных изображений, позволяющий добиться лучшей степени сжатия и минимального размера выходного файла. Принцип работы основан на особенностях восприятия человеческим глазом различных цветов и достаточно сложен с вычислительной точки зрения, так как занимает много процессорного времени. Кодирует файлы в несколько этапов. Во-первых, изображение условно разбивается на несколько цветовых каналов для дальнейшего анализа. Затем картинка разбивается на группы по 64 пиксела в каждой группе (она же - квадратный участок изображения размером 8х8 пикселей) для последующей обработки. Затем цвет пикселей специальным образом кодируется, исключаются дублирующая и избыточная информация, причем при описании цвета больше внимания уделяется скорее яркостной, чем цветовой составляющей, так как человеческий глаз воспринимает изменения яркости лучше, чем изменения конкретного цветового тона. Ватолин Д. С. Алгоритмы сжатия изображений. - М.: Диалог-МГУ, 1999.

Полученные данные сжимаются по RLE или LZW-алгоритму для достижения еще большей компрессии. В результате на выходе получаем файл иногда в десятки раз меньший, чем его неконвертированный аналог. Однако чем меньше размер выходного файла, тем меньше степень «аккуратности» при работе программы-конвертора и, соответственно, ниже качество выходного изображения. Обычно в программах, позволяющих сохранять растровые данные, есть возможность некоторого компромисса между объемом выходного файла и качеством изображения. При лучшем качестве объем выходного файла в 3-5 раз меньше исходного незапакованного. При качестве похуже - меньше исходника в десятки раз, но, как правило, при этом качество изображения уже не позволяет использовать его где-либо. Данный формат предназначен для хранения в основном фотографических изображений с большим количеством оттенков и цветовых переходов и почти не подходит для хранения однотонных изображений типа кадров из мультфильмов, скриншотов (сжатие будет слишком низким или качество картинки достигнет критической отметки). Этот метод сжатия графических данных используется в файлах формата.PDF, PostScript (для включенных объектов), собственно в.JPEG и других.

НОВЫЙ СТАНДАРТ JPEG 2000

В его разработке приняли участие Международная организация по стандартизации (International Organization for Standardization), Международный союз телекоммуникаций (International Telecommunications Union), компании Agfa, Canon, Fujifilm, Hewlett-Packard, Kodak, LuraTech, Motorola, Ricoh, Sony и другие. Позволяет сжимать изображения в 200 раз без заметной для невооруженного глаза потери качества. Основным отличием JPEG2000 от предыдущей версии этого формата является использование алгоритма волнового преобразования (изображение описывается с помощью математических выражений как непрерывный поток) вместо преобразования Фурье, что и предотвращает появление характерных блоков. Умеет также без ущерба модифицировать (масштабировать, редактировать) рисунок, сохраненный в этом формате. Алгоритм волнового преобразования позволяет просматривать и распечатывать одно и то же изображение при различных (заданных пользователем) значениях разрешения и с требуемой степенью детализации. Шкарин Д. Повышение эффективности алгоритма РРМ // Проблемы передачи информации. - 2001.

Благодаря этой особенности JPEG2000 быстро найдет свое место в Сети, поскольку обеспечит возможность загружать картинки с разными значениями разрешения в зависимости от пропускной способности конкретного канала связи. Да и тот факт, что пользователи интернета смогут получать изображения высокого качества, немаловажен. Еще одно значимое преимущество JPEG2000 - возможность управлять 256-цветовыми каналами, а в результате получать качественные цветные изображения. Специалисты обещают, что в общем случае новый формат будет как минимум на 30% эффективнее, чем JPEG. И еще один плюс - новый стандарт является открытым. Главным недостатком компрессии с частичной потерей качества является то, что эти потери, выражающиеся в искажении цветового тона или появлении характерной кубической структуры в контрастных участках изображения (всплытие так называемых артефактов), возникают каждый раз при сохранении изображения и «накладываются» друг на друга при многократном сохранении файла в этом формате. Поэтому специалисты рекомендуют использовать форматы с частичной потерей качества только для хранения окончательных результатов работы, а не для промежуточных рабочих файлов. Кроме того, вспомогательным средством уменьшения объема файлов в JPEG 2000 можно считать изменение цветовой модели графического файла, изменение разрешения растрового файла и ресемплирование (изменение глубины цвета пикселей).

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

Заключение

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

Наиболее вероятно, что из тройки WinАce-WinRar-7Zip лучше справится WinRar. Однако даже при сжатии файлов одного и того же типа (например, графического формата bmp) часто невозможно заранее определить, какой из архиваторов сожмет файл лучше - наиболее высокая степень сжатия может быть у любого из перечисленных архиваторов.

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

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

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

сжатие графический данные

1. Ватолин Д., Ратушняк А., Смирнов М., Юкин. В. Методы сжатия данных. - М., 2003.

2. Ватолин Д.С. Тенденции развития алгоритмов архивации графики // Открытые системы. - Зима 1995. - №4.

3. Ватолин Д.С. Алгоритмы сжатия изображений. - М.: Диалог-МГУ, 1999.

4. Кадач А.В. Эффективные алгоритмы неискажающего сжатия текстовой информации. // Дис. к. ф.-м. н. - Ин-т систем информатики им. А.П. Ершова. - М., 1997.

5. Климов А.С. Форматы графических файлов. - С.-Пб.: ДиаСофт. 1995.

6. Шкарин Д. Повышение эффективности алгоритма РРМ // Проблемы передачи информации. - 2001.

7. Яншин В.В. Анализ и обработка изображений (принципы и алгоритмы). - М.: Машиностроение, 1995.

Размещено на Allbest.ru