Современные методы хранения информации в сжатом виде

      Министерство  транспорта Российской Федерации

      Федеральное агентство железнодорожного транспорта

      Омский  государственный университет путей  сообщения 
 
 

      Кафедра: «Автоматика и система управления» 
 
 
 
 
 
 

      Реферат по дисциплине «ИСВВТ» на тему: 

      «Современные методы хранения информации в сжатом виде» 
 
 
 
 
 
 
 
 
 

       Выполнил: студент гр. 28 з

         ____________ С.А. Нюхтилин

   «__»____________2011г.

       Проверил: ст. преподаватель кафедры

   ________«АиСУ» Афоничев Н.Ю.

  «__»____________2011г. 
 
 
 
 
 
 
 
 
 
 

      Омск 2011

       Содержание

       Введение……………………………………………………………………………......3.

1.Хранение  видеоизображения в сжатом виде……………………………………….4

       2.Хранение  изображения в сжатом виде…………………………………………….13

              3.Хранение данных в сжатом  виде на примере архиватора  WinRar……………….20

       Библиографический список…………………………………………………………..23 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

       Введение

       Хранение  информации осуществляется с помощью  её переноса на некоторые материальные носители. Семантическая информация, зафиксированная на материальном носителе для хранения называется документом.

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

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

1. Хранение  видеоизображения в сжатом виде.

               Существует множество технологий сжатия цифрового видео. Некоторые из рассматриваемых компрессоров используют не одну технологию сжатия, а некоторую их совокупность. Например, и Indeo 3.2, и Cinepak используют векторную квантизацию. Международные стандарты MPEG-1, MPEG-2, MPEG-4, H.261 и H.263 используют комбинированную технологию БДКП и компенсацию движения. Некоторые современные алгоритмы используют технологию ДВП (Discrete Wavelet Transform, или DWT). Другие технологии включают Фрактальное сжатие изображений (Fractal Image Compression).

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

       Сжатие  может происходить с потерями качества, если в процессе сжатия информация была потеряна. Однако с точки зрения человеческого восприятия сжатием  с потерями следует считать лишь такое сжатие, при котором возможно на глаз отличить результат сжатия от оригинала. Таким образом, несмотря на то что два изображения - оригинал и результат сжатия с использованием того или иного компрессора - побитно могут не совпадать, тем не менее разница между ними может быть совсем незаметной. Примером может служить алгоритм JPEG для сжатия статической графики и алгоритм M-JPEG для сжатия видео.

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

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

       Низкое  качество сжатия, в значительной степени  искажающее изображение и вносящее в него искусственные (не существующие в оригинале) детали сцены, называется неестественным сжатием с потерей качества. Примером тому может служить некоторая «блочность» в сильно сжатом MPEG-е и в других компрессорах, использующих технологию БДКП. Неестественность заключается в первую очередь в нарушении самых важных с точки зрения восприятия человеком характеристик изображения - контуров. Опыт показывает, что именно контуры позволяют воспринимающему аппарату человека правильно идентифицировать тот или иной визуальный объект.

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

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

       Для сжатия видео используют различные  кодеки

       Рисунок 1 – видеокодек Select video compression 

       Технологии и алгоритмы сжатия видео

       Run Length Encoding

       Компрессорами, использующими технологию RLE, являются:

       Microsoft RLE (MRLE) RLE используется также для  кодирования коэффициентов в  БДКП, применяющемся в MPEG-1234, H.261, H.263 и JPEG.

       Достоинства и недостатки

       1.  Работает исключительно с 8-битовыми изображениями.

       2.  Не подходит для сжатия полноцветного видео.

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

       Компрессорами, использующими технологию VQ, являются Indeo 3.2 и Cinepak. Оба они применяют  цветовую схему YUV (а не RGB).

       Достоинства и недостатки

       1.  Процесс кодирования очень трудоемок и практически неосуществим без специального дополнительного оборудования.

       2.  Процесс декодирования очень быстр.

       3.  Блоковые искажения при высоких коэффициентах сжатия.

       4.  Технологии, использующие алгоритмы БДКП, ДВП могут достигать более высоких уровней сжатия.

       Основная  идея векторной квантизации заключается  в разбиении изображения на блоки (размером 4x4 пиксела в цветовой схеме YUV для компрессоров Indeo и Cinepak). Как  правило, некоторые блоки оказываются  похожими друг на друга. В этом случае компрессор идентифицирует класс похожих блоков и заменяет их одним общим блоком. Кроме того, генерируется двоичная таблица (карта) таких общих блоков из самых коротких кодовых слов. VQ-декодер затем, используя таблицу, собирает изображение поблочно из общих блоков. Ясно, что данный способ кодирования с потерями качества, так как, строго говоря, схожесть блоков весьма относительна. Здесь допускается аппроксимация реальных блоков изображения к общему, их объединяющему. Процесс кодирования длителен и трудоемок, так как кодеру необходимо выявлять принадлежность каждого блока изображения к какому-нибудь общему блоку. Однако задача декодирования в этом случае сводится к задаче построения изображения по заданной карте из общих блоков и не занимает много аппаратных и временных ресурсов. Таблицу или карту также называют еще и кодовой книгой, а двоичные коды, входящие в нее, - кодовыми словами, соответственно. Наибольшее сжатие с использованием алгоритма VQ достигается путем уменьшения числа классов общих блоков, то есть предположением о схожести относительно большего числа блоков изображения, и, как следствие, уменьшением кодовой книги. По мере уменьшения размеров кодовой книги качество воспроизводимого видео ухудшается. В результате на изображении появляется искусственная «блочность».

       Простой пример: сравним три следующих  блока 4 x 4. 

       Эти три блока для человеческого  глаза неотличимы. Таким образом, 2-ой и 3-ий блоки можно спокойно заменить первым. Тогда кодовая книга будет  иметь следующий вид:

       Кодовая Книга[1] = 128 128 128 128

       128 128 128 128

       128 128 128 128

       128 128 128 128

       Важной  особенностью технологии VQ является то, что при сжатии видео одна и  та же кодовая книга может использоваться для нескольких кадров изображения.

       Дискретное  Косинусное Преобразование (ДКП)

       Компрессоры, использующие ДКП: Motion JPEG; Editable MPEG; MPEG-1; MPEG-2; MPEG-4.

       Достоинства и недостатки

       1.  «Блочность» при высокой компрессии.

       2.  Закругление острых углов изображения. Случайное «размывание» острых краев изображений.

       3.  Кодирование очень трудоемко. Только в последнее время удалось осуществить процесс кодирования программно, а не аппаратно.

       Обзор

       ДКП является широко используемым при сжатии изображений преобразованием. Стандарт сжатия статической графики JPEG, используемый в видеоконференциях стандарт H.263, цифровые видеостандарты MPEG (MPEG-1, MPEG-2 и MPEG-4) — все они используют ДКП. В этих стандартах используется, в частности, 2-мерное ДКП, применяемое последовательно к блокам изображения размерностью 8 x 8 пикселов. ДКП вычисляет 64 (8x8 = 64) коэффициента, которые затем квантизуются, обеспечивая тем самым реально сжатие. В большинстве изображений большинство ДКП-коэффициентов в силу своей малости после квантизации обнуляется. Это свойство ДКП и лежит в основе множества алгоритмов сжатия, использующих ДКП.

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

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

       ДКП(m,n) = sqrt( (1 - delta(m,1) ) / N ) * cos( (pi/N) * (n - 1/2) * (m-1) )

       , где

       ДКП (m,n) есть одномерная матрица ДКП 

       m, n = 1,...,N 

       pi = 3.14159267... 

       N = число выборок в блоке 

       delta(m,1) = 1 если m = 1 и 0 в противном случае  

       cos(x) = косинус x, измеряемый в радианах.

       Естественно, применение ДКП на блоке из N выборок  потребует N*N операций умножения и  суммирования. Однако благодаря рекурсивной  структуре матрицы ДКП реально потребуется гораздо меньшее количество математических операций, а именно N log(N). Это свойство делает ДКП реально применимым на современных математических процессорах персональных ЭВМ.

       Дискретное Wavelet-преобразование (DWT)

       Компрессоры, использующие DWT (Discrete Wavelet Transform): Intel Indeo 5.x; Intel Indeo 4.x

       Достоинства и недостатки

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

       2.  Относительное качество изображений, сжатых с использованием DWT, превосходит качество изображений, сжатых при помощи ДКП, при тех же коэффициентах сжатия.

       3.  DWT несколько размазывает, закругляет острые контуры изображения. Так называемый контурный шум или эффект Гиббса.

       Обзор

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

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

       Простым примером DWT является DWT Хара:

       Входной сигнал x[n] есть множество выборок с индексом n. Низкочастотный фильтр Хара (Haar Low Pass Filter) есть арифметическое среднее двух удачных выборок:

       g[n] = 1/2 * ( x[n] + x[n+1] )

       Высокочастотный фильтр Хара (Haar High Pass Filter) есть средняя  разность двух удачных выборок:

       h[n] = 1/2 * ( x[n+1] - x[n] )

       Заметьте, что:

       x[n] = g[n] - h[n] x[n+1] = g[n] + h[n]

       Выходные  последовательности g[n] и h[n] содержат избыточную информацию. Таким образом, ясно, что  для воспроизведения исходного  сигнала x[n] достаточно взять только четные или только нечетные его выборки. Как правило, берутся четные выборки. Таким образом, исходный сигнал x[n] получается только из: g[0], g[2], g[4], .... h[0], h[2], h[4], .....

       x[0] = g[0] - h[0]

       x[1] = g[0] + h[0] x[2] = g[2] - h[2] x[3] = g[2] + h[2] и так далее...

       Выход низкочастотного фильтра представляет собой грубую аналогию исходного  сигнала. Если исходным сигналом является изображение, то на выходе низкочастотного  фильтра получится расплывчатое, размытое изображение с низким разрешением. Выход высокочастотного сигнала добавляет детали к изображению. В сочетании с выходом низкочастотного фильтра может быть воспроизведено, таким образом, исходное изображение. Грубая форма исходного сигнала (сигнал на выходе низкочастотного фильтра) иногда называют основным уровнем (base layer), а дополнительный сигнал детализации - уровнем улучшения (enhancement layer). Сигнал на выходе высокочастотного фильтра h[n] может быть пропущен снова через пару фильтров, и процесс, таким образом, может быть повторен, пока не будет достигнута достаточная степень детализации исходного сигнала x[n]. Однако ясно, что никакого сжатия здесь не достигается. Преобразование попросту воспроизводит то же количество битов, которое было в исходном сигнале. Выходные значения называются коэффициентами преобразования, или коэффициентами wavelet-преобразования.

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

       Допустим, что в приведенном выше примере  входной сигнал x[n] представляет собой последовательность 8-битных выборок растра полутонового изображения. Для выхода низкочастотного фильтра g[n] теперь можно использовать те же 8 бит, а для высокочастотного h[n] — уже меньше, например 4. Это, по сути, скалярная квантизация. Далее выход высокочастотного фильтра будет стремиться к нулю, так как коэффициенты преобразования будут убывать по мере применения алгоритма. Таким образом, возможно применить вероятностное кодирование к сигналу детализации h[n].

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

       Компрессорами, использующими технологию разницы  кадров, являются: Cinepak

       Достоинства и недостатки

       1.  В целом может обеспечивать сжатие, лучшее, чем независимое сжатие отдельных кадров.

       2.  Возникающие в ходе кодирования ошибки накапливаясь, требуют наличия дополнительного ключевого кадра.

       Обзор

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

       Компенсация движения

       Компрессорами, использующими технологию компенсации  движения, являются: MPEG-1,2 и 4.

       Достоинства и недостатки

       1.  По сравнению с механизмом разницы кадров механизм компенсации движения позволяет достигать большей степени сжатия.

       2.  Кодирование весьма трудоемко и требует специальной аппаратуры.

       3.  Технология компенсации движения используется в таких международных стандартах сжатия цифрового видео, как: MPEG, H.261 и H.263.

       4.  Наибольшее сжатие достигается в сценах с пониженным движением.

       Компенсация движения основана на использовании  ряда сложных алгоритмов. Сфера, где  данная технология сжатия эффективна, как правило, сводится к видеоряду, в котором объект изменяет свое местоположение относительно неподвижного фона. Объекты, изменяющиеся по форме, приближающиеся или удаляющиеся (движущаяся камера), не подлежат эффективному сжатию посредством алгоритма компенсации движения. Сжатие возможно заданием вектора смешения элементов изображения вместо хранения больших значений новых координат данных элементов изображения. Основным блоком (относительно которого задается вектор смещения остальных блоков) может являться любой блок изображения размером 16x16 пикселов, максимально похожий на кодируемый (предсказываемый) блок. Ясно, что кадр, на который ссылаются таким образом другие кадры, должен быть декодирован ранее. Однако совсем не обязательно, чтобы опорный кадр предшествовал предсказываемому кадру. MPEG позволяет производить предсказание в обоих направлениях путем введения так называемых B- (bi-directionally predicted) кадров.

       MPEG - это аббревиатура от Moving Picture Experts Group. Эта экспертная группа работает под совместным руководством двух организаций - ISO (Организация по международным стандартам) и IEC (Международная электротехническая комиссия). Официальное название группы - ISO/IEC JTC1 SC29 WG11. Ее задача - разработка единых норм кодирования аудио- и видеосигналов. Стандарты MPEG используются в технологиях CD-i и CD-Video, являются частью стандарта DVD, активно применяются в цифровом радиовещании, в кабельном и спутниковом ТВ, Интернет-радио, мультимедийных компьютерных продуктах, в коммуникациях по каналам ISDN и многих других электронных информационных системах.

       MPEG-1

       Очень популярный формат во всём мире, с основой, взятой от кодека JPG. Сжатие в нем  производится сериями по три кадра. Это один из самых старых кодеков, так что, практически на любых, даже самых «слабых» машинах можно  просмотреть видео со стереозвуком в этом формате. Однако и качество изображения невысокое: оно сравнимо с привычным аналоговым форматом VHS. Картинка имеет разрешение 352х288 точек, да и качество ее оставляет желать лучшего. И хотя MPEG-1 не требователен к ресурсам, его судьба предрешена: с развитием ёмкости и скорости передачи данных в компьютерах и интернете формат будет постепенно забываться.

       Как происходит сжатие информации в этом формате? Предположим, что у нас  есть следующая сцена: автомобиль движется из пункта "А" в пункт "Б". Перемещение машины можно описать двумя параметрами: вектором перемещения из точки "А" в точку "Б" и углом поворота вокруг своей оси. Задний план при этом остается неизменным или почти неизменным - зритель вряд ли обратит внимание на колебания мелких веток у дальних деревьев. Следовательно, можно разбить кадр на две составные части - задний план, который сохраняется один раз, а затем подставляется при воспроизведении всех кадров, и область, где движется машина, - ее придется записывать отдельно для каждого кадра.

       В формате MPEG-1 все кадры видеоролика  подразделяются на три типа: I-, P- и B-кадры. К первому типу (I-кадры, Intra Frames) относятся  опорные кадры. Их изображения сохраняются  в полном объеме в формате JPEG. Для P-кадров (Predicted Frames) записываются только отличия от предыдущего i-кадра, что требует намного меньше дискового пространства. Для B-кадров (Bi-DirectiOnally Interpolated Frames) сохраняются отличия от предыдущего и следующего I- или P-кадра.

Рисунок 2 – кадры в mpeg1 

       В итоге размер сжатого файла составляет примерно 1/35 от исходного. Это значит, что полуторачасовой фильм с  качеством, эквивалентным аналоговой записи на кассете VHS, в формате MPEG-1 поместится на два компакт-диска. Для передачи через Internet или в сетях спутникового вещания этот стандарт, конечно же, не подходит.

       MPEG-2

       MPEG-2 представляет собой дальнейшее  расширение MPEG-1. В нем увеличен  рекомендуемый размер кадра - теперь он составляет 1920 x 1080 точек, добавлена поддержка шестиканального звука. Однако для воспроизведения видео в этом формате требуется более высокая вычислительная мощность компьютера.

       Следует отметить, что велась работа над  созданием стандарта MPEG-3 (не нужно  путать с популярным форматом сжатия звука - MPEG-1 Audio Layer 3). Он должен был стать базовым для систем цифрового телевидения высокой четкости HDTV. Но работа над ним была прервана, поскольку нужные для HDTV требования удалось реализовать в виде небольших расширений к MPEG-2.

       Доминирующий  формат на сегодня это MPEG-2 с разрешением 720х576 точек. Все DVD-video диски работают в формате MPEG-2. Трансляции со спутников  в несколько каналов на одной  частоте, эфирная трансляция, в том  числе ТВ высокой четкости, разнообразные плееры DVD, microMV-видеокамеры используют этот формат сжатия. И это не удивительно. После триумфального успеха MPEG-1, новый формат, обеспечивающий практически профессиональное качество картинки, утверждался довольно долго, и получился очень удачным. MPEG-2 подходит для записи полуторачасового фильма отличного качества на стандартный диск DVD (4,7 Гб). Кроме того, в этом формате можно записывать на двойные DVD (9 Гб) фильмы повышенного качества с использованием нескольких разных дорожек звука (дубляж), разных форматов многоканального звучания, субтитров, разных углов обзора видеоматериала (несколько синхронных дорожек видео) и других цифровых новшеств. Среди них, например, присутствует произвольный мгновенный доступ к любой части видеоматериала на диске и отсутствие перемотки при достижении конца видеоматериала, что раньше являлось довольно большой проблемой.