Студопедия

Главная страница Случайная страница

Разделы сайта

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






Алгоритмы архивации изображений без потери информации. Классический алгоритм Хаффмана. LZ и LZW компрессия.






Алгоритм RLE

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

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

1 1 1 1 2 2 3 4 4 4

В алгоритме RLE предлагается заменить её следующей структурой: 1 4 2 2 3 1 4 3, где первое число каждой пары чисел - это код данных, а второе - коэффициент повторения. Если для хранения каждого элемента данных входной последовательности отводится 1 байт, то вся последовательность будет занимать 10 байт памяти, тогда как выходная последовательность (сжатый вариант) будет занимать 8 байт памяти. Понятно, что алгоритм RLE будет давать лучший эффект сжатия при большей длине повторяющейся последовательности данных. В случае рассмотренного выше примера, если входная последовательность будет иметь такой вид: 1 1 1 1 1 1 3 4 4 4, то коэффициент сжатия будет равен выше. В связи с этим большая эффективность алгоритма RLE достигается при сжатии графических однотонных изображений.

 

Если отсканировать текст или чертеж и построчно развернуть изо­бражение в одну длинную линию, то можно обнаружить, что на ней будет много длинных участков одного и того же цвета. Именно это обстоятельство и использует алгоритм RLE. Если встречается последовательность из N одинаковых чисел, например: т,..., т, то она заменяется двумя числами: N, т.

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

Впрочем, RLE не требователен к памяти и производительности ПК. Он нашёл широкое применение в факсимильных аппаратах. В начале 80-х, когда вычислительные возможности персональных компьютеров были еще очень скромными, большой популярностью пользовался графический формат PCX, также основанный на RLE.Усовершенствованный алгоритм RLE, в худшем случае увеличивающий размер файла только на 0, 8%, используется в одном из вариантов формата TIFF и в формате TGA.

 

Алгоритмы группы LZ(LZW)

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

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

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

Алгоритмы сжатия этой группы наиболее эффективны для текстовых данных больших объёмов и малоэффективны для файлов маленьких размеров (за счёт необходимости сохранение словаря).

 

Потоки информации, с которыми приходится иметь дело компьютеру, как правило, содержат повторяющиеся цепочки символов. Самый яркий пример — текст, в котором неоднократно употребляются те или иные слова. Если развернуть изображение по строкам, как в алгоритме RLE, то можно увидеть не только цепочки одинаковых чисел, но и повторяющиеся последовательности, просто RLE не умеет с ними работать. Напрашивается мысль: заменить подобные цепочки одним символом, а в начале файла по­местить таблицу замен, по которой можно восстановить информацию. Но если наш мозг позволяет быстро извлечь из текста слова, даже если они не разделены пробелами, то для компьютера эта задача является довольно сложной. И только в 1977 г. два израильских математика, А. Лемпел и Я. Зив, разработали новый класс алгоритмов сжатия без потерь, получивший название метод Лемпела—Зива. Одновременно с публикацией общих идей исследователи обнародовали и основанный на этих идеях алгоритм LZ77. Через год алгоритм был усовершенствован, новый вариант стал известен как LZ78. На основе этих разработок впоследствии было создано множество методов сжатия информации, получивших по первым буквам фамилий создателей общее название LZ-алгоритмы. Примерами реализации LZ-алгоритмов являются Zip-архиваторы и протокол V.42bis.

Недостатком классического варианта алгоритма LZ является то, что он эффективен лишь для повторяющихся цепочек длиной не менее 5 байт. При сжатии текстов это приемлемо, но при сжатии изображений глубиной цвета 8 бит классический LZ становится неэффективным. В 1983 г. сотрудник компании Unisys Т. Уэлч нашел способ усовершенствовать классический LZ таким образом, что становится выгодным работать с повторяющимися цепочками начиная с 2 байт — этот вариант алгоритма получил название Лемпела—Зива—Уэлча (LZW). Представим, что найдена цепочка символов А, которая содержит уже найденную цепочку В и больше её всего на один символ С. В классическом алгоритме LZ цепочки А и В будут записаны и обрабатываться отдельно или же будет взята большая из них, т.е. А. В алгоритме LZW последовательность А будет записана как «С, ссылка на В». Таким образом, не только уменьшается объём сохраняемой в файле информации, но и значительно повышается быстродействие. В отличие от классического LZ, который стал общедоступен, алгоритм LZW был запатентован компанией Unysys.

Алгоритм LZW появился очень своевременно и сразу же стал приме­няться в самых разнообразных целях, но особенно удачным оказалось его использование для сжатия изображений, передаваемых по компьютерным сетям. На основе LZW в компании CompuServe, которая владела одной из крупнейших компьютерных сетей США, в 1987 г. был создан графический формат Graphics Interchange Format (GIF), позволяющий эффективно сжимать изображения с огромной по тем временам глубиной цвета 8 бит несжатой информации на каждую точку изображения, причём палитра 256 цветов изображения может быть выбрана из набора в 16 млн. цветов. Среди преимуществ GIF — поддержка т.н. чересстрочной развёртки, благодаря чему в процессе загрузки можно увидеть изображение в полном размере, но с пониженной чёткостью и принять решение, стоит ли загружать его дальше. По мере загрузки новых данных чёткость изображения повышается.

Формат GIF быстро завоевал популярность среди пользователей Com­puServe, в 1989 г. была принята его новая версия. Однако на протяжении нескольких лет существование GIF без лицензионных отчислений владельцу патента на LZW не вызывало серьезных протестов со стороны Unisys. Лишь когда в 1993 г. появилась и начала стремительно развиваться Всемирная паутина, а на горизонте замаячили большие прибыли от нового бизнеса, в Unisys наконец спохватились. Был инициирован судебный процесс против CompuServe, который был проигран этим провайдером. Судебное решение от 28 декабря 1994 г. обязывало разработчиков программного обеспечения, в котором используется формат GIF, платить фирме Unisys лицензионные отчисления. Дальнейшие события, которые повлекло это решение, вполне достойны того, чтобы про них был написан детективный роман.

 

За разработку нового формата, который был бы не хуже, чем GIF, но при этом не требовал лицензионных отчислений, интернетовская обще­ственность взялась, так сказать, всем миром. Точкой отсчёта истории PNG можно считать 4 января 1995 г., когда Т. Боутелл послал в ряд конференций Usenet свои предложения о графическом формате Portable Bitmap Format (PBF). Первый вариант нового формата был, как и GIF, 256-цветным и ещё не был привязан к определённому методу сжатия, но уже содержал некоторые черты современного PNG. Буквально в течение недели предложение Боутелла получило множество откликов в Usenet, и была создана группа разработчиков нового формата, которые общались друг с другом по Интерне­ту. События развивались стремительно. 23 января 1995 г. новый формат получил современное название Portable Network Graphics (PNG), что в переводе на русский язык означает «переносимый графический формат». Темпы, которыми шла разработка формата, иллюстрирует следующий факт, к моменту переименования, т.е. менее чем через три недели после размещения описания алгоритма в Usenet, было разработано уже четыре его версии. 2 февраля 1995 г. была предложена схема чересстрочной развёртки, а уже 11 марта была выпущена первая программа, которая позволяла просмат­ривать записанные изображения в виде PNG-файлов.

 

Несмотря на то, что лежащий в основе GIF алгоритм стандартизован, коэффициент сжатия зависит от его конкретной реализации. Обычно в графических редакторах используются не самые лучшие реализации, что объясняется стремлением повысить быстродействие и сократить расходы на разработку программы. Поэтому перед тем как размещать на Web-странице, файлы в формате GIF обрабатывают специальной утилитой (например, AGO), уменьшающей их размер (иногда даже в два-три раза!) за счёт оптимальной реализации алгоритма сжатия.

Важной особенностью PNG, позволяющей достичь при прочих равных условиях более высокого коэффициента сжатия по сравнению с GIF, является т.н. предварительная фильтрация сжимаемой информации. Многие пользователи программ-архиваторов не раз замечали эффект, когда сжатие файла давало один результат, а после внесения небольшого исправления в сжимаемый файл — уже совершенно другой, т.е. размеры сжатых файлов могут различаться намного сильнее, чем различаются размеры исходных файлов. Дело в том, что при разработке алгоритма сжатия вначале строится некая модель сжимаемой информации, и уже исходя из неё, создается алгоритм. Чем ближе структура сжимаемой информации к той модели, которую имели в виду разработчики метода сжатия, тем сильнее сжимается информация. Но может получиться и так, что изменение всего нескольких бит информации может настолько изменить её структуру, что алгоритм будет работать невероятно хорошо или, наоборот, очень плохо. Кстати, именно это обстоятельство используют всевозможные «оптимизаторы GIF». Чтобы высокий коэффициент сжатия достигался практически для любых изображений, в PNG используется преобразование информации перед её сжатием, причём это преобразование также происходит без потерь. В результате предварительных преобразований информация приводится к виду, наиболее удобному для сжатия.

 

8 декабря 1995 г. была выпущена спецификация PNG 0.92, которая яв­лялась уже рабочим документом консорциума W3C. Таким образом, открылась перспектива широкого применения PNG в Интернете. Начиная с 1 октября 1996 г., когда вышла спецификация PNG 1.0 в виде рекомендации консорциума W3C, формат PNG существует в качестве полноправного члена сообщества популярных графических форматов для глобальной компьютерной сети.

В основе PNG лежит LZ-алгоритм, который, обладая преимуществами LZW, является лицензионно чистым. Графический формат, PNG поддер­живает глубину цвета до 48 бит, но в отличие от большинства графических форматов в PNG нет чёткого деления между типами изображений по глубине цвета. В графический файл формата PNG записывается описание всей палитры цветов, используемой в изображении, что позволяет гибко подстраиваться под реальное число цветов в изображении и обеспечивает более высокую степень сжатия, чем GIF. Как и GIF, формат PNG поддерживает возможность чересстрочной развёртки, причём в PNG она является двумерной. Среди других приятных особенностей формата PNG — возможность выбора компрессии либо по критерию быстроты распаковки изображения, либо по максимально высокому коэффициенту сжатия.

Формат PNG поддерживается Netscape Communicator начиная с версии 4.0, Microsoft Internet Explorer на­чиная с версии 4.01 — всеми версиями браузера Opera, а также почти всеми современными графическими редакторами. Однако встретить изображения в формате PNG на Web-страницах до сих пор практически невозможно. Причина в том, что формат GIF со сжатием без потерь используется на Web-страницах главным образом для мелких элементов навигации и управления. В формате PNG размер файла не может быть меньше 1 Кбайт, поскольку именно столько занимает описание палитры. Таким образом, для ма­леньких изображений размер файла в формате PNG может быть больше, чем у GIF, а иногда больше, чем у BMP.

 

 

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

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

Основная идея состоит в следующем: чем чаще встречается символ, тем меньшим количеством бит он кодируется. Результат кодирования заносится в словарь, необходимый для декодирования.

Для построения алгоритма сжатия изображения можно использовать неравномерность вероятности появления тех или иных цветовых оттенков в изображении. Например, на фотографии природного пейзажа, сделанной зимой, вероятность появления оттенков зелёного цвета очень мала, в то же время оттенки серого встречаются часто. Идея заключается в том, чтобы часто встречающиеся оттенки обозначать более короткой комбинацией бит, чем редко встречающиеся. Алгоритм такого сжатия информации называется алгоритмом Хаффмана, в результате его применения получается т.н. код Фано. Сжатие по Хаффману используется в архиваторах, формате TIFF, а также в факсимильной связи. Применение алгоритма Хаффмана не для отдельных символов, а для их последовательностей называется Q-кодированием. IBM разработала на основе Q-кодирования алгоритм JBIG, эффективно сжимающий без по­терь черно-белые изображения, а также изображения, имеющие два или че­тыре оттенка серого. Алгоритм JBIG нашел применение в факсимильной связи и системах автоматизации документооборота. Кодирование по Хаффману вместе с RLE используется как составная часть алгоритма JPEG, дополнительно сжимая информацию после обработки преобразованием Фурье.

 

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

 

JPEG (Joint Photographic Experts Group)

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

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

Таким образом, чем выше уровень компрессии, тем больше данных отбрасывается, тем ниже качество. Используя JPEG можно получить файл в 1-500 раз меньше, чем ВМР!

 

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

 

Методы сжатия с потерями применяются для изображений с глубиной цвета 24 бита. Возможен вариант их использования для изображения с 256 оттенками серого. С одной стороны, именно для полноцветных изображений нужны эффективные методы сжатия: изображение 800x600 точек с глубиной цвета 24 бита в формате BMP занимает 1, 4 Мбайт! С другой стороны, при глубине 8 бит изменение цвета хотя бы на один бит в младшем разряде хорошо заметно глазу, а ведь при сжатии с потерями искажения непременно возникают. Если глубина цвета 24 бита, то ошибка в одном-двух младших битах будет малозаметна.

Формат JPEG (Joint Photographic Expert Group) был разработан в 1991 г. одноименным подразделением в рамках ISO — международной организации по стандартизации. Суть его в следующем. Изображение делится на участки размером 8x8 точек. В пределах каждого участка над массивом точек осуществляется дискретное преобразование Фурье. В полученном спектре более высоким частотам будут соответствовать более мелкие детали. Как правило, чем выше частота, тем меньше амплитуда (частота и амплитуда, которые в быту обычно ассоциируются только со звуком, на самом деле яв­ляются более общими понятиями, применимыми и к изображению). В зависимости от требуемой степени сжатия записываются коэффициенты для частот от нуля до определенного значения. Интересно отметить, что по своему принципу работы JPEG отдаленно напоминает алгоритм сжатия звуковой информации МР3, что еще раз свидетельствует о единстве законов природы.

Искажения изображения при использовании алгоритма JPEG прояв­ляются в размывании резких цветовых границ и исчезновении мелких деталей. При очень сильном сжатии изображение начинает выглядеть, как мозаика, каждый элемент которой имеет размер 8x8 точек. При сжатии задаётся показатель качества, выраженный в процентах, — чем он больше, тем меньше степень сжатия. Качество выше 90% можно охарактеризовать оценкой «отлично», 75-90% - «хорошо», 50-75%- «удовлетворительно», менее 50%- «неудовлетворительно».

Для хорошего качества сжатие фотографического изображения по сравнению с BMP составляет 10—20 раз.

Поскольку алгоритм JPEG появился точно тогда, когда в нём возникла необходимость, и изначально создавался не какой-либо фирмой, а меж­дународной некоммерческой организацией, его судьба сложилась на редкость счастливо. Вот уже более 20 лет он используется как основной алгоритм сжатия графической информации с потерями. Появились первые графические браузеры, и JPEG стал главным методом сжатия для Интернета. Появились цифровые фотокамеры, и JPEG широко используется в них, хотя преимущество данного алгоритма для цифровой фотографии весьма спорно; но если сейчас начать замену JPEG на другой формат, владельцы цифровых фотоаппаратов сразу же столкнутся с проблемой совместимости. Алгоритм JPEG положен в основу одноименного формата, поддерживающего прогрессивную развертку (в отличие от телевидения и компьютерных мониторов, где термины «чересстрочная развёртка» и «прогрессивная раз­вёртка» имеют прямо противоположное значение, в данном случае они близки по смыслу; прогрессивная развёртка, так же как и чересстрочная, обеспечивает постепенную прорисовку изображения. — Прим, ред.), а также используется в форматах TIFF и QuickTime.

 

3. Понятие фрактала. Основные идеи фрактальных алгоритмов сжатия.

 

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

В 70-е гг. XX в. математики стали проявлять интерес к новому классу геометрических фигур, т.н. фракталам. Уже первые исследования показали, что фракталы удивительно похожи на природные объекты: листья, соцветия, капли и т.п. В 1977 г. бельгийский математик Б. Мандельброт высказал смелое предположение, что это не просто совпадение, а действительно, те очертания природных объектов, которые мы привыкли называть нечёткими или расплывчатыми, на самом деле представляют собой фракталы. Пока что биология не подтвердила эту гипотезу, однако су­ществуют результаты вычислительных экспериментов, подтверждающие це­лесообразность использования данной идеи в практических целях. Фрак­тальное преобразование описывает обработку форм различных размеров, похожих между собой по структуре (пример таких объектов — чипсы). При этом изображение можно масштабировать в широких пределах —

ведь картинка рисуется кривыми, только более сложными, чем в век­торной графике. Теоретически это позволяет сжимать графическую ин­формацию до 10 тыс. раз, причём появляющиеся при этом искажения будут гораздо менее заметны человеческому глазу по сравнению с результатами применения алгоритма JPEG.

В 1981 г. Д. Хатчинсон предложил метод системы итерируемых функций (IPS, Iterated Function System) для фрактального сжатия изображений. В 1987 г. американец М. Барнсли основал компанию Iterated Systems, основной деятельностью которой является создание новых алгоритмов и ПО с использованием фракталов. Первая практическая реализация метода IFS в виде компьютерного алгоритма появилась только в 1990 г. Фрактал представляется в виде набора рекурсивных преобразований, коэффициенты в которых и являются описанием изображения. В процессе сжатия информации происходит определение этих коэффициентов.

 

Существующее деление графических форматов по наличию потерь при сжатии информации довольно условное. Некоторые графические редакторы допускают сохранение изображения с 24-битным цветом в формате GIF. Происходит это следующим образом: определяются наиболее часто встречающиеся цвета, и из них составляется 8-битная палитра. Редко встречающиеся цвета в палитру не включаются, а заменяются близкими оттенками. В этом случае GIF выступает как формат, сжимающий с потерями. С другой стороны, есть вариант формата JPEG, предусматривающий сжатие без потерь.

 

Практическим результатом работы компании Iterated Systems стал графический формат FIF, использующий принцип фрактального сжатия. Для создания FIF-файлов существуют специальная программа, а также plug-in к редактору Adobe Photoshop, которые можно найти на сайте компании-производителя Altamira Group (https://206.63.152.155). Там же находятся созданный Iterated Systems plug-in к популярным Web-браузерам для просмотра FIF-файлов и галерея изображений, выполненных в этом формате, которая наглядно демонстрирует преимущества фрактальных методов сжатия. Однако, несмотря на всю свою привлекательность, FIF пока что не стал таким же общеупотребительным форматом для Web, как GIF или JPEG.

Фрактальное сжатие изображений является сейчас важной темой для многих серьезных исследований. Конечно, 10000-кратной компрессии фрактальными методами пока еще достичь не удалось, но сжатие изображения в 50 раз так, что искажения практически не заметны, — уже реальный результат.

 

Что такое фрактал?

Топологической размерностью множества в линейном пространстве называют число линейно независимых координат, которыми описываются его точки. Например, окружность имеет топологическую размерность 1, круг (т.е. часть плоскости, лежащая внутри окружности), сфера — 2, а шар (как часть объёма, ограниченная сферой) — 3. Фрактальной размерностью множества называется размерность пространства, которое полностью заполняется множеством. Фракталом называют множество, для которого фрактальная размерность не совпадает с топологической. Например, фракталом может быть линия бесконечной длины, ограничивающая конечную по площади часть плоскости.

 

4. Сжатие движущихся изображений

Устаревший стандарт сжатия движущихся изображений AVI (Audio Visual Interleave) позволяет формировать упрощенное видеоизображение, но не на полном экране и со скоростью лишь 15 кадров в секунду. При этом используется всего 160 х 120 пикселей и 256 цветов.

Наибольшее распространение для сжатия движущихся изображений получил стандарт MPEG.

С помощью стандарта MPEG обрабатывается и каждый кадр по от­дельности, и анализируется динамика изменения изображения. Этим удается уменьшить избыточные данные, так как в большинстве фрагментов фон изо­бражения остаётся достаточно стабильным, а изменения происходят в ос­новном на переднем плане. MPEG начинает сжатие с создания исходного (ключевого) кадра, называемого Intra (внутренний) кадр. I-кадры играют роль опорных при восстановлении остального видеоизображения и размещаются последовательно через каждые 10—15 кадров. I-кадры формируют с помощью методов, разработанных стандартом JPEG для сжатия неподвиж­ных изображений.

Фрагменты изображений, которые претерпевают изменения, сохра­няются при помощи Predicted (расчётных, предсказуемых) кадров. Р-кадры, содержат различия текущего изображения с предыдущим или последующим I-кадром. Р-кадры располагаются между опорными I-кадрами.

Кроме перечисленных кадров, используются В-кадры, название кото­рых происходит от английских слов Bi-directional Interpolated. В переводе с английского языка этот термин означает «кадры двунаправленной интерпо­ляции (предсказания)». В-кадры содержат усредненную информацию отно­сительно двух ближайших (предыдущего и последующего) I-кадров или Р-кадров. Это позволяет предположительно восстанавливать (реконструиро­вать) отсутствующие кадры.

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

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

При сжатии изображений (как и при сжатии звуков) используются физиологические особенности человека.

Установлено, что ошибки в изображении заметны глазом (визуально), если они превышают некоторый порог заметности. Различают пространст­венную и временную заметность искажений изображений.

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

Что касается временного восприятия цвета, то известно, что вариации цветности менее заметны, чем вариация яркости. Наиболее заметны измене­ния зеленого цвета, затем красного, и наименее заметны изменения синего цвета.

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

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

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

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

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

Качество сжатия варьируется в довольно широких пределах; обычными для современных видеосистем являются коэффициенты сжатия от 1: 4 до 1: 100.

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

Некоторые сложные алгоритмы кодирования, например алгоритм сжатия видеосигнала MPEG, не могут выполняться в реальном времени (при записи), поэтому кодек MPEG называется асимметричным.

 






© 2023 :: MyLektsii.ru :: Мои Лекции
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
Копирование текстов разрешено только с указанием индексируемой ссылки на источник.