Глоссарий

Адаптивное сжатие

Метод сжатия, которые способен изменять (модифицировать) свои операции и/или параметры в зависимости от данных, поступивших из входного потока. Примером является адаптивный метод Хаффмана из § 1.5, а также словарные методы, описанные в главе 2.

 

Алфавит

Множество всех различных символов входного потока данных. При сжатии текстов алфавитом обычно служит множество из 128 кодов ASCII. При компрессии изображений алфавитом является множество различных значений, которые могут принимать пикселы (2, 16, 256 значений или больше). (См. также Символ.)

 

Арифметическое кодирование

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

 

Барк

Единица критической полосы. Названа в честь Г. Баркхозена (Н.Ваrkhausen). Она используется в науке о звуковом восприятии. Шкала величин барк нелинейно соотносится с частотной шкалой. Она подобрана с учетом особенности восприятия разных звуковых частот человеческим ухом.

 

Биграмм

Пара последовательных символов.

 

Бит/Буква

Бит на букву (pbc, bit-per-character). Мера эффективности сжатия текстовой информации. Служит также для измерения энтропии. (См. также Битовая скорость.)

 

Бит/Символ

Бит на символ. Общая характеристика для измерения степени сжатия оцифрованных данных.

 

Битовая скорость

В общем случае термин «Битовая скорость» (по-английски «bitrate») обозначает и bpb (bit-pet-bit, бит набит) и bpc (bit-per-character, бит на букву). Однако при сжатии звука в MPEG, этот термин используется для скорости, с которой сжатый поток считывается декодером. Эта скорость зависит от его источника или носителя (диск, канал связи, оперативная память компьютера и т.п.). Если битовая скорость аудиофайла MPEG определена, скажем, в 128 Кбит/с, то это означает, что кодер конвертирует каждую секунду исходного звукового потока в 128 Кбит сжатых данных, а декодер, соответственно, переводит каждые 128 Кбит сжатого файла в одну секунду звучания. Низкая битовая скорость означает малый размер сжатого файла. Вместе с тем, чем меньше битовая скорость, тем больше кодер должен сжать звуковую информацию, что приводит к значительной потере качества звука. Опытным путем установлено, что для качества звука, сравнимого с качеством записи на CD, битовая скорость должна находиться в интервале от 112 Кбит/с до 160 Кбит/с. (См. также Бит/Буква.)

 

Битовый слой

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

 

Векторное квантование

Это обобщение метода скалярного квантования. Оно применяется при компрессии изображений и звука. На практике векторное квантование осуществляется при сжатии оцифрованных аналоговых данных, таких как звуковые сэмплы, сканированные изображения (рисунки или фотографии). (См. также Скалярное квантование.)

 

Двухуровневое изображение

Изображение, в котором пикселы имеют всего два значения. Эти цвета, обычно, называются «черным» и «белым», «изображение» и «фон», 1 или 0. (См. также Битовый слой).

 

Декодер

Программа или алгоритм декодирования (разжатия) данных.

 

Децибел

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

 

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

Вариант дискретного преобразования Фурье (DFT), которое генерирует вещественные числа. DCT (§§ 3.5.3, 3.7.2) преобразует множество из  чисел, которое рассматривается как вектор -мерного пространства, в повернутый вектор, причем первая координата становится доминирующей. Преобразование DCT и обратное к нему, IDCT, используется в стандарте JPEG (см. § 3.7) для сжатия изображений с приемлемой потерей информации, которая происходит при отбрасывании высокочастотных компонентов образа и квантования низкочастотных составляющих.

 

Дискретно-тоновое изображение

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

 

Дискретное вейвлетное преобразование

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

 

Изображение с градацией серого цвета

Непрерывно тоновое изображение с оттенками одного цвета. (См. также Непрерывно тоновые изображения.)

 

Кодек

Термин для совместного обозначения кодера и декодера.

 

Кодер

Программа или алгоритм кодирования (сжатия) данных.

 

Кодирование длин повторов, RLE

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

 

Кодирование Хаффмана

Популярный метод сжатия данных (см. § 1.4). Присваивает «наилучшие» коды переменной длины множеству символов в зависимости от их вероятностей. Лежит в основе многих известных программ сжатия файлов на персональных компьютерах. Некоторые из них непосредственно применяют метод Хаффмана, а другие используют его как один из шагов многоступенчатого алгоритма компрессии. Метод Хаффмана чем-то похож на метод Шеннона-Фано. В общем случае он производит лучшие коды, и подобно методу Шеннона-Фано эти коды являются наилучшими, когда вероятности символов в точности равны отрицательным степеням числа 2. Основное различие между этими двумя методами состоит в том, что метод Шеннона-Фано строит коды сверху вниз (от самого левого к самому правому биту), а метод Хаффмана выстраивает свои коды с помощью дерева, направляясь вверх (то есть, код выписывается справа налево).

 

Коды

Кодом называется символ, который подставляется на место другого символа. В компьютерных и телекоммуникационных приложениях коды всегда являются двоичными числами. Стандартом де-факто выступает код ASCII. Многие новые приложения поддерживают кодовый стандарт UNICODE, а более старый стандарт EBCDIC все еще применяется в компьютерах IBM.

 

Коды Грея

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

 

Коды переменной длины

Используются в статистических методах сжатия. Эти коды должны удовлетворять свойству префикса (§ 1.2) и они присваиваются входным символам в соответствии с их вероятностями. (См. также Свойство префикса, Статистические методы.)

 

Конференция по сжатию данных (Data Compression Conference, DCC)

Конференция для исследователей и разработчиков в области сжатия данных. DCC происходит ежегодно в городе Сноуберд, штат Юта, США. Она происходит в марте и длится три дня.

 

Корреляция

Статистическая мера линейной зависимости между двумя парными величинами. Эта величина меняется от -1 (совершенная отрицательная зависимость), через 0 (отсутствие зависимости) и до +1 (совершенная положительная зависимость).

 

Коэффициент сжатия

Важная величина, которая постоянно используется для определения эффективности метода сжатия. Она равна частному

.

Коэффициент 0.6 означает, что сжатые данные занимают 60% от исходного размера. Значения большие 1 говорят о том, что выходной файл больше входного (отрицательное сжатие).

Иногда величина равная  используется для определения качества сжатия. Значение, равное 60, означает, что выходной поток занимает 40% от объема исходного потока (то есть, при сжатии освободилось 60% объема). (См. также Фактор сжатия.)

 

Коэффициент усиления сжатия

Это число определяется формулой

,

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

 

Методы LZ

Все словарные методы сжатия основаны на работах Я.Зива (J.Ziv) и А.Лемпэла (A.Lempel), опубликованных в 1977 и 1978 гг. С тех пор эти методы принято подразделять на методы LZ77 и LZ78. Эти замечательные идеи вдохновили многих исследователей, которые обобщали, улучшали и комбинировали их, например, с методом RLE или со статистическими алгоритмами. В результате появилось огромное число известных адаптивных методов сжатия текстов, изображений и звука. (См. Словарное сжатие, Сжатие скользящим окном).

 

Методы LZSS

Это вариант метода LZ77 (см. § 2.2) был разработан Сторером (Storеr) и Сжимански (Szymanski) в 1982 [Storer 82]. Базовый алгоритм был улучшен по трем направлениям: (1) буфер упреждения сохранялся в циклической очереди, (2) буфер поиска (словарь) хранился в виде дерева двоичного поиска и (3) метки имели два поля, а не три. (См. Методы LZ).

 

Методы LZW

Это популярная версия алгоритма LZ78 (см. § 2.4) была разработана Терри Уэлчем (Terry Welch) в 1984. Его главной особенностью является удаление второго поля из метки. Метка LZW состоит только из указателя на место в словаре. В результате такая метка всегда кодирует строку из более чем одного символа.

 

Модель сжатия LZW

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

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

 

Метод SPIHT

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

 

Непрерывно-тоновое изображение

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

 

Отсчеты

Коэффициенты вейвлетного преобразования. (См. также Дискретное вейвлетное преобразование.)

 

Пел

Наименьшая единица факсимильного изображения, точка. (См. также Пиксел.)

 

Пиксел

Наименьшая единица цифрового изображения, точка. (См. также Пел.)

 

Предсказание

Приписывание некоторых вероятностей символам алфавита.

 

Преобразование изображений

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

 

Прогрессирующее сжатие изображений

Метод компрессии изображений, при котором сжатый поток состоит из нескольких «слоев», причем каждый следующий слой несет все более детальную информацию об изображении. Декодер может быстро показать весь образ с грубым разрешением, а затем улучшать качество картинки по мере приема и декодирования следующих слоев. Зритель, наблюдающий на экране декодируемое изображение, сможет получить представление о нем после разжатия всего 5-10% образа. Улучшение качества изображения можно добиться с помощью (1) повышения резкости, (2) добавления цветов или (3) увеличения разрешения.

 

Психоакустическая модель

Математическая модель маскирования звуков близких частот при восприятии органами слуха человека (ухо-мозг).

 

Свойство префикса

Один из принципов построения кодов переменной длины. Если некоторая последовательность битов выбрана в качестве кода определенного символа, то никакой другой код не может начинаться с этой же последовательности битов (не должен быть префиксом другого кода). Например, если строка «1» назначена кодом символа , то никакой другой код не может начинаться с 1 (т.е., все другие коды будут начинаться с 0). Если код «01» присвоен символу , то в начале другого кода не должна стоять последовательность 01 (они могут начинаться с 00). (См. также Коды переменной длины, Статистические методы.)

 

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

Метод сжатия, при котором выход декодера всегда тождественно совпадает с исходными данными, поступившими на вход кодера. (См. также Сжатие с потерями.)

 

Сжатие видео

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

 

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

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

 

Сжатие скользящим окном

Метод LZ77 (§2.1) использует часть ранее полученного потока данных в качестве словаря. Кодер строит окно во входных данных, в которое задвигаются справа налево поступающие символы для кодирования. Этот метод основан на скользящем окне. (См. также Методы LZ.)

 

Символ

Наименьшая единица в сжимаемых данных. Обычно, символом служит один байт, но им может быть один бит, или элемент из множества {0,1,2}, или еще что-то.

 

Скалярное квантование

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

 

Словарное сжатие

Метод компрессии данных (см. главу 2), которые сохраняют некоторые образцы данных в специальной структуре, называемой «словарем» (обычно, это дерево). Если строка новых данных на входе тождественна некоторому образцу из словаря, то в выходной поток или файл записывается указатель на этот образец. (См. также Методы LZ.)

 

Стандарт JFIF

Полное название этого метода (§ 3.7.8) - JPEG File Interchange Format (формат обмена файлами стандарта JPEG). Это формат графических «файлов, который позволяет компьютерам обмениваться сжатыми изображениями стандарта JPEG. Главная особенность этого формата состоит в использовании трехбайтового цветового пространства YCbCr (или однобайтового для образов с градацией серого). Кроме того в файл добавляются некоторые атрибуты, которых нет в формате JPEG, а именно, разрешение изображения, геометрический размер пиксела и некоторые другие параметры, специфические для конкретных приложений.

 

Стандарт JPEG

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

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

Аббревиатура JPEG означает Joint Photographic Experts Group (объединенная группа по фотографии). Проект JPEG был инициирован совместно комитетом CCITT и организацией ISO в июле 1987 года. Этот стандарт был признан во всем мире. Он широко используется в представлении графических образов, особенно на страницах всемирной паутины. (См. также JPEG-LS, MPEG.)

 

Стандарт JPEG-LS

Мода без потерь стандарта JPEG является неэффективной и поэтому ее редко реализуют в конкретных приложениях. Поэтому ISO приняло решение разработать новый стандарт для сжатия без потерь (или почти без потерь) непрерывно тоновых изображений. В результате появился известный стандарт JPEG-LS. Этот метод не является простым расширением или модификацией JPEG. Это новый метод, простой и быстрый. В нем не используется ни DCT, ни арифметическое кодирование, но зато применяется весьма ограниченное квантование (в моде с почти без потерями). JPEG-LS проверяет несколько предыдущих соседей текущего пиксела и использует их в качестве контекста этого пиксела. С помощью контекста делается прогноз текущего пиксела и выбирается некоторое распределение вероятностей из имеющегося семейства распределений. На основе выбранного распределения определяется код ошибки прогноза с помощью специального кода Голомба. Существует также мода кодирования длины повторов, в которой кодируются длины повторяющихся последовательностей одинаковых пикселов.(См. также JPEG.)

 

Статистическая модель

См. Модель компрессии.

 

Статистические методы

Эти методы (глава 1) выполняют присвоение символам из потока данных кодов переменной длины, причем более короткие коды назначаются символам или группам символов, которые чаще встречаются во входном потоке (имеют большую вероятность появления). (См. также Коды переменной длины, Свойство префикса, Кодирование Хаффмана, Арифметическое кодирование.)

 

Теория информации

Математическая теория, которая придает точный количественный смысл понятию информация. Она определяет, как измерить информацию и ответить на вопрос: сколько информации содержится в том или ином массиве данных? Ответом выступает точное число. Теория информация была создана в 1948 в работах Клода Шеннона.

 

Факсимильное сжатие

Передача типичной страницы между двумя факс-машинами по телефонным линиям связи без использования компрессии может занять от 10 до 11 минут. По этой причине комитет ITU разработал несколько стандартов сжатия факсимильных сообщений. Общепринятыми стандартами на сегодняшний день являются (см. § 1.6) Т4 и Т6, которые еще называются Group 3 и Group 4, соответственно.

 

Фактор сжатия

Величина, обратная коэффициенту сжатия. Определяется по формуле

.

Значение, большее 1, означает сжатие, а меньшее 1 расширение. (См. также Коэффициент сжатия.)

 

Энтропийное кодирование

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

Потребность - вот мать сжатия.
 - Эзоп (перефразированное)