Учебник Фамилия, имя, отчество




НазваниеУчебник Фамилия, имя, отчество
страница6/12
Дата18.04.2013
Размер1.59 Mb.
ТипУчебник
1   2   3   4   5   6   7   8   9   ...   12

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

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

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

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

· сжатие без потерь;

· сжатие с потерями.


2.5.1. Сжатие без потерь

Большинство схем сжатия без потерь основано на поиске в растровом изображе­нии повторяющихся пиксельных узоров. Такой узор можно запомнить один раз и впоследствии повторить его необходимое количество раз. Подобные схемы сжа­тия полностью – пиксел за пикселом – восстанавливают исходное изображение. При этом в исходных данных ничего не отбрасывается и не теряется. Метод сжа­тия без потерь (например, используемый в форматах GIF или TIF) очень эффек­тивен для растровых рисунков, содержащих большие области однотонной закрас­ки, или повторяющихся растровых узоров. В таких случаях чаще всего достигается коэффициент сжатия 10:1.

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

Групповое кодирование (RLE)

Групповое кодирование RLE – алгоритм сжатия данных, поддерживаемый большинством растровых файловых форматов, таких как TIFF, BMP и PCX. RLE – простой метод сжатия групп одинаковых байтовых значений в код, занимающий всего несколько байт. Алгоритм RLE позволяет сжимать данные любых типов, невзирая на содержащуюся в них информацию. Однако сама информация влияет на полноту сжатия. Хотя большинство алгоритмов RLE не могут достигать высокой степени сжатия, характерной для наиболее совершенных алгоритмов сжатия, но групповое кодирование легко и быстро выполняется, являясь хорошей альтернативой применению сложных алгоритмов сжатия или отказу от использования таковых вообще.

RLE уменьшает физический размер повторяющихся строк символов. Такие повторяющиеся строки, называемые группами, обычно кодируются в двух байтах. Первый байт определяет количество символов в группе и называется счетчиком группы. На практике закодированная группа может содержать от 1 до 128 или 256 символов, что часто записывается в счетчик группы в виде: количество символов минус единица (значения в диапазоне от 0 до 127 или 255). Второй байт содержит значение символа в группе, которое находится в диапазоне от 0 до 255 и называется значением группы.

Несжатая символьная группа из 15 символов А обычно занимает 15 байтов:

ААААААААААААААА

После RLE-кодирования та же строка займет всего два байта:

15А

Код 15А, сгенерированный для представления символьной строки, называется RLE-пакетом. Первый байт данного пакета (15) является счетчиком группы и содержит количество повторений. Второй байт (А) служит значением группы и хранит повторяемое значение.

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

AAAAAAbbbXXXXXt

Применив групповое кодирование, мы сможем сжать ее в четыре 2-байтовых пакета.

6A3b5X1t

Таким образом, в результате группового кодирования 15-байтовая строка станет занимать только 8 байтов. В данном случае групповое кодирование позволило получить степень сжатия, примерно равную 2:1.

В определенных типах данных длинные группы встречаются крайне редко. Например, текст в формате ASCII редко включает длинные группы. В предыдущем примере последняя группа (содержащая символ “t”) имеет единичную длину, тем не менее это все же группа, следовательно, счетчик группы и значение группы будут записаны в два байта. Для кодирования группы в RLE требуется как минимум два байта, поэтому группы из одиночных символов займут больше памяти. Исходя из этих соображений, можно утверждать, что данные, содержащие двухсимвольные группы, имеют после RLE-кодирования тот же размер, что и до него.

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

LZW-сжатие

Схема сжатия Лемпела-Зива-Велча (LZW) является одной из наиболее распространенных в компьютерной графике. Этот метод сжатия данных без потерь применяется в различных форматах файлов изображений, в частности в GIF и TIFF, и включен в стандарт сжатия для модемов V.42bis и PostScript Level 2.

В 1977 году Абрахамом Лемпелом и Джекобом Зивом был создан первый компрессор из широко известного сегодня семейства компрессоров LZ. Алгоритмы сжатия LZ77 широко использовались для сжатия текста, а также стали основой таких архивирующих программ, как lha, pkzip и arj.

В 1984 году, являясь сотрудником Unisys, Терри Велч модифицировал компрессор с учетом применения высокоскоростных дисковых контроллеров. Полученный в результате алгоритм LZW широко используется и сегодня.

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

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

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

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

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

Ряд файловых форматов, в том числе и TIFF, применяют подобный метод кодирования для графических файлов. В TIFF пиксельные данные пакуются в байты до того, как поступают на вход LZW. Следовательно, исходный байт LZW может быть пиксельным значением, частью пиксельного значения или несколькими пиксельными значениями. GIF требует, чтобы каждый входной символ LZW был пиксельным значением.

Подход, примененный в TIFF, не очень хорошо “работает” с пикселями нечетного размера, поскольку упаковка приводит к последовательностям байтов, не совпадающим с оригинальными последовательностями пикселей, отчего все образцы в пикселях “прячутся”. Если границы пикселя совпадают с границами байта (например, два 4-байтовых пикселя в байте или один 16-битовый пиксель в 2 байтах), то метод, примененный в TIFF, достаточно удачен.

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


2.5.2. Сжатие с потерями

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

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

Ключевым моментом в применении сжатия с потерями является определение “приемлемого уровня” потерь. Уровень этот субъективен и зависит от изображения-оригинала и от того, как он будет использоваться. Если ваше оригинальное изоб­ражение – фотография музейного качества, предназначенная для публикации в высокохудожественном издании, то ни о каких “приемлемых потерях” не может быть и речи. Рисунок должен быть воспроизведен как можно точнее. Другое дело электронная публикация на web-странице, где одним из главных критериев явля­ется малый размер файла.

Формат JPEG

JPEG – стандарт формата файлов для растровых изображений с эффективным сжатием информации.

На сегодняшний день формат JPEG (Joint Photographic Experts Group) является одним из наиболее распространенных графических форматов для сжатия файлов. В нем реализован алгоритм сжатия с потерями. Это означает, что в процессе сжатия изображения происходит частичная потеря хранящейся в файле информации. Поэтому в процессе применения этой процедуры сжатия при­ходится искать компромисс между степенью сжатия и качеством сохраняемого изображения. Чем больше сжатие, тем ниже качество, и наоборот.

Строго говоря, JPEG не формат, а алгоритм сжатия, в основе которого лежит не поиск одинаковых элементов, как в случае RLE и LZW, а поиск разницы между пикселами.

Кодирование данных с помощью используемого в JPEG алгоритма сжатия осуще­ствляется в несколько этапов.

1. Сначала графические данные конвертируются в цветовое пространство Lab-модели (Lab-модель используется графическими редакторами в качестве внутренней модели для взаимного преобразования RGB- и CMYK-моделей).

2. Затем отбрасывается половина или три четверти информации о цвете (в зави­симости от реализации алгоритма).

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

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

5. На последнем этапе используется кодирование методом Хаффмана для более эффективного сжатия конечных данных.

Алгоритм сжатия Хаффмана (Huffman) разработан еще в 1952 году. В нем осущест­вляется последовательный перебор наборов символов, которые анализируются с целью определения частоты появления каждого символа. Затем наиболее часто встречающиеся символы кодируются с помощью минимально возможного коли­чества битов. Например, в английских текстах чаще всего встречается буква “е”. Используя кодировку Хаффмана, можно представить “е” всего лишь двумя битами (1 и 0) вместо восьми битов, необходимых для представления буквы “е” в кодировке ASCII.

Восстановление данных происходит в обратном порядке. Таким образом, чем выше уровень компрессии, тем больше данных отбрасывается и тем ниже качество. Ис­пользуя JPEG, можно получить файл в 1–500 раз меньше, чем BMP. Этот формат аппаратно независим, полностью поддерживается и PC и Macintosh, однако он относительно новый и не понимается старыми программами (до 1995 года).

Наряду со стандартным вариантом существуют еще два подтипа формата JPEG, ориентированных на применение в Интернете:

· Baseline Optimized – файлы этого подтипа формата несколько лучше сжимают­ся, но не читаются некоторыми программами. Однако все основные браузеры его поддерживают.

· Progressive JPEG также разработан специально для сети, его файлы меньше стандартных, но чуть больше подтипа формата Baseline Optimized. Главная осо­бенность Progressive JPEG состоит в поддержке чересстрочного вывода изоб­ражения (использование этого свойства намного сокращает время передачи и вывода на экран насыщенных графикой Web-страниц).

При сохранении графических изображений в формате JPEG следует учитывать следующее.

· JPEG лучше подходит для сжатия растровых картинок фотографического ка­чества, чем для логотипов или схем. Это связано с тем, что в них больше полу­тоновых переходов, в то время как при сжатии однотонных заливок появляют­ся нежелательные помехи.

· Лучше сжимаются (и с меньшими потерями) большие изображения для web и изображения с высоким разрешением для печати (200–300 dpi и более), так как в каждом квадрате (8х8 пикселов) переходы получаются более мягкими за счет большего числа квадратов в таких файлах.

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

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


3. Инструментарий для написания графических приложений


3.1. Стандарты в области разработки графических систем

Компьютерная графика в настоящее время уже вполне сформировалась как наука. Существует аппаратное и программное обеспечение для получения разнообразных изображений – от простых чертежей до реалистичных обра­зов естественных объектов.

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

Использование программистами графических возможностей видеосистемы может осуществляться различно. Во-первых, простейшие операции, такие как определение графического видеорежима, вывод пиксела на экран и неко­торые другие, поддерживаются BIOS. Во-вторых, можно использовать функ­ции операционной системы. Различные операционные системы могут пре­доставлять различные возможности. Например, в MS-DOS графических функций почти не было, однако программисту был разрешен свободный дос­туп ко всем аппаратным ресурсам компьютера. В быстродействующих гра­фических программах часто использовался непосредственный доступ к ви­деопамяти. В отличие от этого, операционная система Windows запрещает прикладным программам непосредственный доступ к аппаратным ресурсам, однако можно применять несколько сотен графических функций операцион­ной системы – интерфейс API (Application Program Interface – прикладной программный интерфейс) – интерфейс для разработки прикладных программ. В-третьих, можно использовать специализи­рованные графические интерфейсы, которые поддерживают аппаратные воз­можности современных графических процессоров.

Одним из наиболее известных графических стандартов является OpenGL. OpenGL – это стандартная графическая библиотека для всех 32-разрядных операционных систем, в том числе и для операционной системы Windows. Стандарт OpenGL был разработан и утвержден в 1992 г. девятью ведущими фирмами, среди которых Digital Equipment Corparation, Evans & Sutherland, Hewlett Packard Co, IBM Corp, Intel Corp, Intergraph Corp, Silicon Graphics Inc, Sun Microsystems и Microsoft. В основу стандарта была положена библиотека IRIS GL, разработанная фирмой Silicon Graphics Inc. Этот интерфейс поддерживается многими операционными системами, а также производителями видеоадаптеров.

Существенным достоинством OpenGL является его широкая распространенность – он является стандартом в мире графических рабочих станций типа Sun, Silicon Graphics и др.

Вот только некоторые из достоинств OpenGL:

· Стабильность. OpenGL – устоявшийся стандарт, действующий уже 5 лет. Все вносимые в него изменения предварительно анонсируются и реали­зуются таким образом, чтобы гарантировать нормальную работу уже на­писанного программного обеспечения.

· Надежность. Все приложения, использующие OpenGL, гарантируют оди­наковый визуальный результат вне зависимости от используемого обору­дования и операционной системы.

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

· Простота использования.

Другим известным графическим стандартом является интерфейс DirectX с подсисте­мой трехмерной графики Direct3D, а также подсистемой Direct Draw, которая обеспечивает, в частности, непосредственный доступ к видеопамяти. Этот интерфейс разработан Microsoft и предназначен только для Windows. Direct3D – специализированная прикладная программная библиотека трехмерной графики, являющаяся частью программного интерфейса Microsoft DirectX и поддерживаемая всеми современными графическими ускорителями.

Известны также другие разработки графических интерфейсов для видеоадап­теров. Например, интерфейс Glide, разработанный 3Dfx для графических видеоадаптеров семейства Voodoo (впрочем, это уже история, поскольку фирма 3Dfx недавно прекратила свое существование как изготовитель видео­адаптеров).

1   2   3   4   5   6   7   8   9   ...   12

Похожие:

Учебник Фамилия, имя, отчество iconФамилия Имя Отчество Занимаемая

Учебник Фамилия, имя, отчество iconФамилия, имя, отчество члена летного экипажа

Учебник Фамилия, имя, отчество iconФамилия, имя отчество члена летного экипажа

Учебник Фамилия, имя, отчество iconКурс Вакантные места Фамилия, имя и отчество заявителя Основание

Учебник Фамилия, имя, отчество iconРезюме фамилия Имя Отчество
Образование: Высшее: Рудненский индустриальный институт. Специальность: Автоматизация и
Учебник Фамилия, имя, отчество iconОбщеобразовательная школа
Фамилия, имя, отчество контактного лица по вопросам инновационной деятельности в образовательном учреждении
Учебник Фамилия, имя, отчество iconФамилия, имя, отчество
Заместитель начальника корпусно-сварочного цеха ОАО «ссрз имени 111 Интернационала»
Учебник Фамилия, имя, отчество iconФамилия Имя Отчество
Необходимое техническое оборудование: презентация осенних пейзажей,запись "Времен года" Чайковского
Учебник Фамилия, имя, отчество iconАнкета Ваши Фамилия Имя Отчество
Комплекс товарного выращивания осетровых в системе замкнутого водообеспечения (узв)
Учебник Фамилия, имя, отчество iconРезюме Фамилия Имя Отчество
Личными качествами считаю: добросовестность, ответственность, исполнительна, целеустремленная, хорошая работоспособность
Разместите кнопку на своём сайте:
Библиотека


База данных защищена авторским правом ©lib.znate.ru 2014
обратиться к администрации
Библиотека
Главная страница