Главная » Программирование звука » Сжатие информации без потерь

0

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

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

для компрессии любых данных. Однако, как вы сможете убедиться сами, нет не-

обходимости избегать потерь при сжатии аудиоданных.

Один  из  подходов  к  компрессии,  используемый  в  таких  алгоритмах  сжатия данных,   как   метод   Лемпела-Зива-Уэлча   (Lempel-Ziv-Welch,   LZW),   дефляция и метод Берроуза-Уиллера (Burroughs-Wheeler), заключается в поиске длинных

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

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

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

И  действительно,  у  звуковых  файлов  неравномерное  распределение  возмож-

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

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

B  противоположность   рассмотренным   способам,   большая   часть  алгоритмов компрессии звука, о которых мы поговорим в следующих главах, позволяет производить  компрессию  с  заданным  отношением.  Алгоритм  IMA  ADPCM,  например, всегда сжимает 16-битную запись звука точно в отношении 4:1.

Нелинейная ИКМ

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

объем данных, однако, поскольку значений будет меньше, вам не удастся  добить-

ся большой точности.

Проблема  потери  точности  в  большей  степени  важна  для  слабых  звуков,  чем для  громких.  Если  используется  диапазон  значений  от  -64  до  +63,  то  пропадет любой   звук,   сила   которого   меньше,   чем   1/128   звука   максимально   возможной громкости.

Один   из   способов   сохранения   самых   тихих   звуков   заключается   в   переопределении  уровней.  Стандартная  ИКМ   это  линейная   система  кодирования. Например,  значение  32  показывает,  что  интенсивность  звука  ровно  в  два  раза выше представленного числом 16; а значение 63 определяет звук, ровно в 63 раза более  интенсивный,  чем  представленный  числом  1.  Чтобы  охватить  более  широкий  динамический  диапазон,  вы  можете  воспользоваться  нелинейной  системой кодирования,  в  которой  значение  1  могло  бы  соответствовать  звуку,  интенсивность  которого  гораздо  меньше,  чем  1/63  интенсивности  звука,  представленного числом 63.

Эта простая идея приводит к отличным результатам. Суть данного метода заключается  в  более  эффективном  использовании  того  же  количества  битов:  мы  получаем  возможность  использовать  больше  битов  для  слабых  звуков,  при  записи которых  потеря  данных  более  заметна.  Эту  технологию  можно  также  рассматривать  как  метод  компрессии.  Широко  распространенный  формат,  использующий ?-Law  (мю-функцию),  часто  характеризуют  как  формат,  сжимающий  12-битные отсчеты в 8-битные.

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

Дифференциальная ИКМ

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

Этот    метод    называют    дифференциальной    кодово-импулъсной    модуляцией (ДИКМ),   или   дельта-модуляцией.   Он   редко   используется   в   программах.   Чтобы  приращения  выборок  были  невелики,  приходится  использовать  более  высокие  частоты  дискретизации.  Ho  повышение  частоты  сводит  на  нет  преимущества записи меньших значений.

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

имеют  величины  17,  22  и  23.  Тогда  приращения  последовательных  значений  составят 5 и 1. Если самое большее, что позволяет хранить используемый вами формат, это 3, тогда следует записать 3 и 3. После реконструкции получатся значения 17, 20 и 23.

Ha   практике   методы   ДИКМ   работают   несколько   сложнее.   Подобно   тому, как  в  выборках,  записываемых  с  помощью  ИКМ,  чаще  преобладают  небольшие величины,  записываемые  с  помощью  ДИКМ  приращения  также  часто  оказываются   малы.   Это   обстоятельство   делает   разумным   использование   нелинейного формата   для   ДИКМ,   обеспечивая   высокую   скорость   обработки   и   предельную компрессию. B главе 12 описаны два простых алгоритма ДИКМ-кодирования.

Адаптивная ДИКМ

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

Методы,  использующие  АДИКМ,  получили  широкое  распространение  как  способы  компрессии  звука.  Их  программная  реализация  трудностей  не  вызывает,  эти алгоритмы  быстро  работают  и  позволяют  добиться  компрессии  с  коэффициентом приблизительно  4:1, сохраняя при этом приемлемое качество  звучания. B качестве примера  кодирования  указанного  типа  можно  привести  IMA  ADPCM,  о  котором пойдет рассказ в главе 13.

Источник: Кинтцель Т.  Руководство программиста по работе со звуком = A Programmer’s Guide to Sound: Пер. с англ. М.: ДМК Пресс, 2000. 432 с, ил. (Серия «Для программистов»).

По теме:

  • Комментарии