Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Алгоритмы сжатия




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

Растровый файл устроен проще (для понимания, по крайней мере). Он представляет из себя прямоугольную матрицу (bitmap), разделенную на маленькие квадратики - пикселы (pixel - picture element). Растровые файлы можно разделить на два типа: предназначенные для вывода на экран и для печати.

Растровые файлы, предназначенные для допечатной подготовки изданий имеют, подобно большинству векторных форматов, параметр Print Size - печатный размер. С ним связано понятие печатного разрешения, которое представляет из себя соотношение количества пикселов на один квадратный дюйм страницы (ppi, pixels per inch или dpi - dots per inch, - термин не совсем верный, но часто употребимый). Печатное разрешение может быть от 130 dpi (для газеты) до 300 (высококачественная печать), больше почти никогда не нужно.

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

4.2.1 GIF (CompuServe Graphics Interchange Format)

Независящий от аппаратного обеспечения формат GIF был разработан в 1987 году (GIF87a) фирмой CompuServe для передачи растровых изображений по сетям. В 1989-м формат был модифицирован (GIF89a), были добавлены поддержка прозрачности и анимации. GIF использует LZW-компрессию, что позволяет неплохо сжимать файлы, в которых много однородных заливок (логотипы, надписи, схемы).

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

Это достигается за счет записи, а затем подгрузки, сначала 1, 5, 10 и т.д. строчек пикселов и растягивания данных между ними, вторым проходом следуют 2, 6, 11 строчки, разрешение изображения в интернетовском браузере увеличивается. Таким образом, задолго до окончания загрузки файла пользователь может понять, что внутри и решить, стоит ли ждать, когда файл поднимется весь. Черезстрочная запись незначительно увеличивает размер файла, но это, как правило, оправдывается приобретаемым свойством.

В GIF’e можно назначить один или более цветов прозрачными, они станут невидимыми в интернетовских браузерах и некоторых других программах. Прозрачность обеспечивается за счет дополнительного Alpha-канала, сохраняемого вместе с файлом. Кроме того файл GIF может содержать не одну, а несколько растровых картинок, которые браузеры могут подгружать одну за другой с указанной в файле частотой. Так достигается иллюзия движения (GIF-анимация).

Основное ограничение формата GIF состоит в том, что цветное изображение может быть записано только в режиме 256 цветов. Для полиграфии этого явно недостаточно.

4.2.2 LZW

Метод сжатия LZW (Lempel-Ziv-Welch) разработан в 1978 году израильтянами Лемпелом и Зивом и доработан позднее в США. Сжимает данные путем поиска одинаковых последовательностей (они называются фразы) во всем файле. Выявленные последовательности сохраняются в таблице, им присваиваются более короткие маркеры (ключи). Так, если в изображении имеются наборы из розового, оранжевого и зеленого пикселов, повторяющиеся 50 раз, LZW выявляет это, присваивает данному набору отдельное число (например, 7) и затем сохраняет эти данные 50 раз в виде числа 7. Метод LZW, так же, как и RLE, лучше действует на участках однородных, свободных от шума цветов, он действует гораздо лучше, чем RLE, при сжатии произвольных графических данных, но процесс кодирования и распаковки происходит медленнее.

4.2.3 JPEG

Строго говоря JPEG’ом называется не формат, а алгоритм сжатия, основанный не на поиске одинаковых элементов, как в RLE и LZW, а на разнице между пикселами. Кодирование данных происходит в несколько этапов. Сначала графические данные конвертируются в цветовое пространство типа LAB, затем отбрасывается половина или три четверти информации о цвете (в зависимости от реализации алгоритма). Далее анализируются блоки 8х8 пикселов. Для каждого блока формируется набор чисел. Первые несколько чисел представляют цвет блока в целом, в то время, как последующие числа отражают тонкие делали. Спектр деталей базируется на зрительном восприятии человека, поэтому крупные детали более заметны.

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

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

Таким образом, чем выше уровень компрессии, тем больше данных отбрасывается, тем ниже качество. Используя JPEG можно получить файл в 1-500 раз меньше, чем ВМР! Формат аппаратно независим, полностью поддерживается на РС и Macintosh, однако он относительно нов и не понимается старыми программами (до 1995 года). JPEG не поддерживает индексированные палитры цветов. Первоначально в спецификациях формата не было и CMYK, Adobe добавила поддержку цветоделения, однако CMYK JPEG во многих программах делает проблемы. Лучшим решением является использование JPEG-сжатия в Photoshop EPS-файлах, которое описывается ниже.

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

Из сказанного можно сделать следующие выводы. JPEG’ом лучше сжимаются растровые картинки фотографического качества, чем логотипы или схемы - в них больше полутоновых переходов, среди однотонных заливок же появляются нежелательные помехи. Лучше сжимаются и с меньшими потерями большие изображения для web или с высокой печатной резолюцией (200-300 и боее dpi), чем с низкой (72-150 dpi), т.к. в каждом квадрате 8х8 пикселов переходы получаются более мягкие, за счет того, что их (квадратов) в таких файлах больше. Нежелательно сохранять с JPEG-сжатием любые изображения, где важны все нюансы цветопередачи (репродукции), так как во время сжатия происходит отбрасывание цветовой информации. В JPEG’е следует сохранять только конечный вариант работы, потому что каждое пересохранение приводит ко все новым потерям (отбрасыванию) данных и превращении исходного изображения с кашу.

 

4.2.4 LAB

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

Существует похожая цветовая модель YCC, используемая в форматах Kodak Photo CD и FlashPix, здесь не описываемых

 

4.2.5 Метод Хаффмана

Метод сжатия Хаффмана (Huffman) разработан в 1952 году и используется как составная часть в ряде других схем сжатия, таких как LZW, Дефляция, JPEG.

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

 

4.2.6 PNG (Portable Network Graphics)

PNG - разработанный относительно недавно формат для Сети, призванный заменить собой устаревший GIF. Использует сжатие без потерь Deflate, сходное с LZW (именно из-за патентования в 1995-м году алгоритма LZW возник PNG). Сжатые индексированные файлы PNG, как правило, меньше аналогичных GIF'ов, RGB PNG меньше соответствующего файла в формате TIFF.

Глубина цвета файлах PNG может быть любой, вплоть до 48 бит. Используется двумерный interlacing (не только строк, но и столбцов), который, так же, как и в GIF'е, слегка увеличивает размер файла.

В отличие от GIF'а, где прозрачность как мед - либо есть, либо нет, PNG поддерживает также полупрозрачные пикселы (то есть в диапазоне прозрачности от 0 до 99%) за счет Альфа-канала с 256 градациями серого.

В файл формата PNG записывается информация о гамма-коррекции. Гамма представляет собой некое число, характеризующее зависимость яркости свечения экрана вашего монитора от напряжения на электродах кинескопа. Это число, считанное из файла, позволяет ввести поправку яркости при отображении. Нужно оно для того, чтобы картинка, созданная на Мас’е, выглядела одинаково и на РС и на Silicon Graphics. Таким образом эта особенность помогает реализации основной идеи WWW - одинакового отображения информации независимо от аппаратуры пользователя.

PNG поддерживается в Microsoft Internet Explorer начиная с версии 4 для Windows и с версии 4.5 на Макинтош. Netscape добавила поддержку PNG для своего браузера в версиях, начиная с 4.0.4 для обеих платформ. Тем не менее до сих пор не реализована поддержка таких важных функций формата, как плавно переходящая прозрачность и гамма-коррекция.

 

4.2.7 TIFF (Tagged Image File Format)

Аппаратно независимый формат TIFF, на сегодняшний день, является одним из самых распространенных и надежных, его поддерживают практически все программы на РС и Macintosh так или иначе связанные с графикой. TIFF является лучшим выбором при импорте растровой графики в векторные программы и издательские системы. Ему доступен весь диапазон цветовых моделей от монохромной до RGB, CMYK и дополнительных цветов Pantone. TIFF может сохранять обтравочные контуры, Альфа-каналы, другие дополнительные данные.

TIFF имеет две разновидности: для Macintosh и РС.

Это связано с тем, что процессоры Motorola читают и записывают числа слева направо, а процессоры Intel - наоборот. Современные программы могут без проблем использовать оба варианта формата.

В формате TIFF может быть использована LZW-компрессия. Ряд старых программ (например, QuarkXPress 3.x, Adobe Streamline, многие программы-распознаватели текста) не умеют читать сжатые файлы TIFF, однако, если вы пользуетесь новым программным обеспечением, нет причины не использовать компрессию.

 

4.2.8 PDF (Portable Document Format)

PDF предложен фирмой Adobe как независимый от платформы формат для создания электронной документации, презентаций, передачи верстки и графики через сети.

PDF-файлы создаются путем конвертации из PostScript-файлов или функцией экспорта ряда программ. Photoshop и Illustrator могут создавать одностраничные файлы PDF. Illustrator 8, как это ни странно для программы Adobe, имеет проблему со встраиванием шрифтов. Photoshop же выпускает PDF отличного качества. Многостраничные PDF могут создавать InDesign, FreeHand 7-9, PDFWriter и Acrobat Distiller некоторые другие программы.

PDFWriter работает как виртуальный принтер. Он не основан на PostScript и не может корректно обрабатывать графику, PDFWriter предназначен для быстрого изготовления простых текстовых документов. У него наблюдается та же проблема со встраиванием шрифтов, что и у Illustrator'а. FreeHand, так же, не может внедрять шрифты. Самые надежные и максимально близкие к оригиналу PDF создает из PostScript и EPS-файлов программа Acrobat Distiller, поставляемая в пакете Adobe Acrobat и вместе и PageMaker'ом.

PDF первоначально проектировался как компактный формат электронной документации. Поэтому все данные в нем могут сжиматься, причем к разного типа информации применяются разные, наиболее подходящие для них типы сжатия: JPEG, RLE, CCITT, ZIP (похожее на LZW и известное еще как Deflate). Программа Acrobat Exchange 3 (которая в 4-й версии стала называться просто Acrobat 4.0) позволяет расставлять гиперссылки, заполняемые поля, включать в файл PDF видео и звук, другие действия.

 

4.2.9 Adobe Photoshop Document

Внутренний формат популярного растрового редактора Photoshop в последнее время стал поддерживаться все большим количеством программ. Он позволяет записывать изображение со многими слоями, их масками, дополнительными Альфа-каналами и каналами простых (spot) цветов (начиная с версии 5), контурами и другой информацией - все, что может сделать Photoshop. В версии 3.0 появляются слои, контуры и RLE-компрессия, в 4-й версии алгоритм улучшается, файлы становятся еще меньше. В версии 5 реализован принципиально иной подход к управлению цветом. В программу была внедрена архитектура управления цветом, основанная на профилях для сканеров, мониторов и принтеров Международного консорциума по цвету (International Color Consortium, ICC).

Несмотря на то, что в 5-й версии появились новые эффекты со слоями, текстом, а так же возможность создавть дополнительные каналы для простых цветов, профили, формат Photoshop'a имеет полную совместимость от 5-й до 3-й версии. В Photoshop'e 2.5 не было слоев и контуров, поэтому он выступает, как отдельный подформат.

Однослойный Photoshop Document понимают ряд программ, многослойные могут импортировать Illustrator и InDesidn. Fractal Design Painter и Corel PHOTO-PAINT открывают на редакцию многослойные документы Photoshop, причем лишь PHOTO-PAINT 8 открывает файл Photoshop'а 100-процентно корректно.

Одной из простейших форм сжатия является метод RLE (Run Length Encoding - кодирование с переменной длиной строки). Действие метода RLE заключается в поиске одинаковых пикселов в одной строке. Если в строке, допустим, имеется 3 пиксела белого цвета, 21 - черного, затем 14 - белого, то применение RLE дает возможность не запоминать каждый из них (38 пикселов), а записать как 3 белых, 21 черный и 14 белых в первой строке.

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

 

4.2.10 CorelDRAW Document

Формат известен в прошлом низкой устойчивостью, плохой совместимостью файлов, искажением цветовых характеристик внедряемых битовых карт, тем не менее пользоваться CorelDRAW чрезвычайно удобно, он имеет неоспоримое лидерство на платформе РС. Многие программы на РС (FreeHand, Illustrator, PageMaker - среди них) могут импортировать файлы CorelDRAW.

В седьмой версии многие основные проблемы были решены. Ее, 8-ю и 9-ю версии CorelDRAW можно без натяжек назвать профессиональными. В файлах этих версий применяется компрессия для векторов и растра отдельно, могут внедряться шрифты, файлы CorelDRAW имеют огромное рабочее поле 45х45 метров (этот параметр важен для наружней рекламы); начиная с 4-й версии поддерживается многостраничность, начиная с 7-й - технология OPI.

 

 

Сказанное означает, что файлы формата CorelDRAW можно применять для переноса/передачи работ на PC, но нежелательно импортировать в программы верстки. На Макинтош файлы CorelDRAW for Windows открывают версия CorelDRAW для Макинтош и Adobe Illustrator 8.

 

4.2.11 WMF (Windows Metafile)

Векторный формат WMF использует графический язык Windows и, можно сказать, является ее родным форматом. Служит для передачи векторов через буфер обмена (Clipboard). Понимается практически всеми программами Windows, так или иначе связанными с векторной графикой. Однако, несмотря на кажущуюся простоту и универсальность, пользоваться форматом WMF стоит только в крайних случаях для передачи "голых" векторов.

WMF искажает цвет, не может сохранять ряд параметров, которые могут быть присвоены объектам в различных векторных редакторах, не может содержать растровые объекты, не понимается очень многими программами на Macintosh.

4.2.12 BMP (Windows Device Independent Bitmap)

Еще один родной формат Windows. Он поддерживается всеми графическими редакторами, работающими под управлением этой операционной системы. Применяется для хранения растровых изображений, предназначенных для использования в Windows и, по сути, больше ни на что не пригоден. Способен хранить как индексированный (до 256 цветов), так и RGB-цвет (16.700.000 оттенков). Возможно применение сжатия по принципу RLE, но делать это не рекомендуется, так как очень многие программы таких файлов (они могут иметь расширение .rle) не понимают. Существует разновидность формата ВМР для операционной системы OS/2.

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

 

4.2.13 RTF (Microsoft Rich Text Format)

Текстовый формат RTF попал сюда за свои неординарные способности к переносу текстов из одной программы в другую. Он позволяет переносить форматированный текст из программ оптического распознавания символов или текстовых редакторов в графические программы или в любых других направлениях. RTF может оказаться хорошим решением (а, иногда, и единственным выходом) при переброске из программы в программу нелатинского, например, ивритского текста или русского в Windows 95/98 Hebrew Edition.

Секрет совместимости заключается в использовании специальных тегов форматирования RTF и Unicode. Именно Unicode, кстати (использованный как основа формата Microsoft Word 97/98 для Макинтош и PC), позволяет легко переносить русские тексты с PC на Мак и обратно в файлах MS Word 97/98.

На Макинтош RTF менее применим, так как у программ, работающих под управлением Mac OS, не наблюдается таких проблем с совместимостью и переносом текста, как у Windows-приложений.

4.3 Вейвлет-преобразования

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

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

Слово “wavelet”, являющееся переводом французского “ondelette”, означает небольшие волны, следующие друг за другом. Можно без преувеличения сказать, что вейвлеты произвели революцию в области теории и практики обработки нестационарных сигналов. В настоящее время вейвлеты широко применяются для распознавания образов; при обработке и синтезе различных сигналов, например речевых, медицинских; для изучения свойств турбулентных полей и во многих других случаях.

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

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

 

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

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

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

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

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

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

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

 







Дата добавления: 2015-09-04; просмотров: 132. Нарушение авторских прав

Studopedia.info - Студопедия - 2014-2018 год . (0.006 сек.) русская версия | украинская версия