Содержание к диссертации
Введение
1. Обзор методов кодирования спектральных коэффициентов для систем сжатия аудио сигналов 7
1.1. Кодирование аудио сигнала 7
1.1.1. Блок фильтров 9
1.1.2. Модель субъективного восприятия 10
1.1.3. Распределение бит 13
1.1.4. Сжатие информации без потерь 15
1.1.5. Формирование битового потока 16
1.2. Сжатие информации с потерями 17
1.2.1. Теоретико-информационные пределы эффективности кодирования при сжатии с потерями 17
1.2.2. Классификация методов квантования 19
1.2.3. Ограничения на выбор метода квантования 23
1.2.4. Оптимальные методы скалярного квантования 24
1.2.5. Избыточность скалярного квантования 28
1.2.6. Сравнение методов скалярного квантования 29
1.3. Постановка задачи построения адаптивного скалярного квантования для системы кодирования аудио сигналов 32
1.4. Результаты и выводы 33
2. Информационные характеристики потока аудио данных 35
2.1. Методы вычисления функции скорость-искажение источника данных 35
2.2. Предварительная обработка спектральных коэффициентов для вычисления информационных характеристик 42
2.3. Построение модели одномерного распределения 50
2.4. Вычисление информационных характеристик реального сигнала 55
2.5. Результаты и выводы 65
3. Скалярное квантование 67
3.1. Характеристики скалярного квантования 67
3.2. Границы эффективности скалярного квантования 70
3.3. Оптимальное скалярное квантование 71
3.4. Скалярное квантование с расширенной нулевой зоной 75
3.5. Адаптивное скалярное квантование с расширенной нулевой зоной 81
3.6. Результаты и выводы 85
4. Перцептуальная энтропия и управление квантованием 87
4.1. Вычисление допустимого уровня шума квантования 87
4.2. Перцептуальная энтропия 94
4.3. Управление квантованием 96
4.4. Определение параметров скалярного квантования с расширенной нулевой зоной 101
4.5. Вычисление перцептуальной энтропии для квантования с расширенной нулевой зоной 106
4.6. Результаты и выводы 113
5. Эффективность применения квантования с расширенной нулевой зоной в аудио кодеке 115
5.1. Передача аудио данных 115
5.2. Спектральная обработка аудио данных и сжатие информации без потерь 121
5.3. Результаты применения квантования с расширенной нулевой зоной в аудио кодеке 123
5.4. Результаты и выводы 127
Заключение 129
Список литературы 132
- Классификация методов квантования
- Методы вычисления функции скорость-искажение источника данных
- Скалярное квантование с расширенной нулевой зоной
- Определение параметров скалярного квантования с расширенной нулевой зоной
Введение к работе
Актуальность. Алгоритмы сжатия аудио информации используются для получения компактного представления аудио сигналов. Эффективность сжатия важна с точки зрения уменьшения затрат на передачу информации по каналам связи или хранения информации на цифровом носителе. Целью кодирования аудио сигнала является представление сигнала наименьшим числом бит при условии, что последующее его воспроизведение удовлетворительно с точки зрения субъективного восприятия. Разработка устройства кодирования опирается на особенности восприятия аудио сигналов человеком. Эти особенности в большей степени зависят от спектрального состава сигнала, совместного влияния спектральных коэффициентов друг на друга и частотного диапазона. Квантование является одной из основных составляющих алгоритмов кодирования аудио информации.
Так как в реальных системах сжатия аудио информации качество передачи зависит от выбранного способа квантования, то актуальной является задача разработки алгоритмов квантования спектральных коэффициентов, обеспечивающих необходимое качество передачи сигнала и большую эффективность сжатия. Актуальным является также определение характеристик способов квантования, позволяющих предварительно оценить эффективность сжатия и выбрать наилучшие параметры передачи аудио информации.
Цели и задачи исследования. Целью диссертационной работы является разработка способов квантования спектральных коэффициентов аудио сигнала.
Для достижения цели исследования необходимо решить следующие задачи:
Построение математической модели квантуемых данных.
Идентификация модели по выборке данных малого объема.
Адаптивный выбор параметров квантователя в зависимости от кодируемого сигнала и параметров распределения.
Адаптивное квантование спектральных коэффициентов в зависимости от требуемой ошибки квантования.
Предметом исследования является разработка и анализ алгоритмов квантования, учитывающих особенности субъективного восприятия аудио сигналов. Взаимосвязь квантования и субъективного восприятия в области аудио кодирования на сегодняшний день настолько тесная, что рассматривать их в отдельности практически невозможно.
Научная новизна. На основе анализа информационных характеристик модели и источника показано, что в качестве модели источника аудио данных может быть использовано одномерное обобщенное гауссово распределение. В работе показано, что анализ оценки параметров распределения данных позволяет более эффективно выбирать параметры скалярного квантователя. Характеристики предложенного метода квантования значительно превосходят характеристики наиболее часто применяемых алгоритмов скалярного квантования (Макса-Ллойда, равномерного) и близки к оптимальному скалярному квантованию в области низких скоростей кодирования.
Положения, выносимые на защиту:
Алгоритм квантования с расширенной нулевой зоной, оптимизированный по скорости и ошибке кодирования.
Алгоритм субоптимального квантования с расширенной нулевой зоной, позволяющий получить характеристики, близкие к предельно достижимым при всех распределениях вероятностей рассматриваемого класса.
Алгоритм адаптивного скалярного квантования с расширенной нулевой зоной на основе модели распределения спектральных коэффициентов.
Метод вычисления перцептуальной энтропии для квантования с расширенной нулевой зоной при заданных параметрах модели распределения спектральных коэффициентов.
Теоретическая значимость полученных результатов в ходе диссертационной работы заключается в следующем:
Построена вероятностная модель для коэффициентов преобразования аудио сигналов ортогональными фильтрами.
Исследована зависимость потенциальных характеристик эффективности квантования от параметров модели.
Предложен алгоритм адаптации квантования к изменениям модели входных данных.
Дан вывод новой формулы перцептуальной энтропии на основе аппроксимации функции скорость-искажение.
Практическая значимость полученных результатов в ходе диссертационной работы:
Разработан алгоритм субоптимального квантования с расширенной нулевой зоной, обеспечивающий выигрыш порядка 0.5 дБ по сравнению с обычным равномерным квантованием при скорости порядка 1 бит на отсчет. Потери энергетической эффективности лежат в пределах 0.05 дБ от теоретически достижимого предела для скалярного квантования.
Разработан метод вычисления оценки перцептуальной энтропии, позволяющий эффективно реализовать на практике адаптацию параметров квантования к изменению параметров сигнала.
Применение на практике нового метода вычисления перцептуальной энтропии позволяет более эффективно осуществлять распределение бит между полосами спектра сигнала. Как следствие этого, уменьшается число итераций при управлении ошибкой квантования или скоростью кодирования.
На основе проведенных экспериментов по интеграции квантования с расширенной нулевой зоной в аудио кодек показано, что достигается значительный выигрыш по скорости и увеличение качества (в среднем на 8.71 кбит/с и 0.44 дБ, что соответствует 14.44% и 2.25%, измеренной в дБ).
Экспертные оценки слепого тестирования при фиксированной целевой скорости показали: при внедрении квантования с расширенной нулевой зоной в кодек субъективное качество существенно возросло (в среднем на 15.03 балла).
Апробация результатов. Основные положения и результаты диссертации докладывались на 8, 9 конференции аспирантов ГУАП, на 8 международной конференции «Цифровая обработка сигналов», публиковались в журнале «Цифровая обработка сигналов», оформлено 7 заявок на патенты США и докладывались на научных семинарах института прогрессивных технологий Самсунг и кафедре информационных систем ИТМО.
Структура диссертации. Диссертационная работа состоит из введения, пяти глав, списка использованных источников (59 наименований). Основная часть работы изложена на 136 страницах машинописного текста, содержит 54 рисунка и 6 таблиц. В первой главе диссертационной работы приведен обзор методов обработки и кодирования аудио сигналов. Особое внимание уделено методам квантования и сформулирована постановка задачи построения адаптивного скалярного квантователя в системе кодирования аудио сигналов. Вторая глава посвящена информационным характеристикам квантования и построению модели спектральных коэффициентов аудио данных. Третья глава посвящена анализу предлагаемого метода квантования и сравнению его информационных характеристик с другими известными методами квантования. В четвертой главе рассматриваются вопросы управления квантованием, построения оценки перцептуальной энтропии и приведены алгоритмы для нахождения необходимых параметров. Пятая глава демонстрирует результаты применения предлагаемого метода квантования в аудио кодеке.
1. Обзор методов кодирования спектральных коэффициентов для
систем сжатия аудио сигналов
1.1. Кодирование аудио сигнала
Источником данных системы сжатия аудио информации является дискретизированный по времени сигнал с частотой дискретизации fd. Дискретизированный сигнал получается из аналогового сигнала с использованием импульсно кодовой модуляции при разрешении b бит на отсчет как показано на рис. 1.1. Битовая скорость этого потока данных составляет R = bfd
бит/с или R =bfd /1000 Кбит/с. В основных приложениях битовая скорость равна R = 705,6
или 768 Кбит/с для одного канала (моно сигнала) что соответствует R — \,A\ или 1,54
Мбит/с для двух каналов (стерео сигнала) при частотах дискретизации fd = 44,1 или 48,0
кГц и разрешением = 16 бит на отсчет. Это наиболее распространенный формат, хотя, в принципе, можно рассматривать любую частоту дискретизации.
Разрешение b бит на отсчет
Частота дискретизации /а Требуемая скорость Rt бит в секунду
Рис. 1.1. Получение аудио сигнала с фиксированной битовой скоростью
Битовые скорости /? = 1,41 и 1,54 Мбит/с допустимы для приложений, которые не являются критичными к скорости, например запись аудио дисков. Для многих мультимедиа приложений и беспроводных систем часто требуются более низкие скорости из-за наличия ограничений на пропускную способность каналов связи. Как показано на рис. 1.1, понижение битовой скорости до требуемой происходит за счет сжатия информации, которое выполняется с потерями в качестве звука. Ошибка восстановления должна удовлетворять ограничениям, накладываемыми условиями применения.
В качестве блока, сжимающего информацию, может выступать любая система, позволяющая контролировать битовую скорость потока данных. К настоящему времени существует целый класс аудио кодеков, основанных на кодировании коэффициентов ортогонального преобразования. Каждая из этих систем содержит стандартные модули, такие как блок фильтров, модель субъективного восприятия, квантование, модуль распределения бит, модуль сжатия информации без потерь, формирователь битового потока. Типовая структурная схема устройства, сжимающего аудио информацию методом кодирования спектральных коэффициентов (/) на выходе блока фильтров, показана на рис. 1.2. Различия между кодеками заключаются в том, как реализованы отдельные модули этой структурной схемы.
Рис. 1.2. Структурная схема устройства сжимающего аудио информацию
Типичный аудио кодек обрабатывает входной сигнал, разбивая его на кадры. Временная длительность кадра может составлять от 2 до 50 миллисекунд. Считается, что на этом интервале времени сигнал является квазистационарным. Изменение длины кадра вызвано наличием коротких временных событий в аудио сигнале, которые нельзя приближать кадрами большой длительности, поскольку это приведет к потере четкости звука. Также, изменение длины кадра является одним из способов борьбы с «эхо» эффектом, который возникает при наличии сигнала с сильным перепадом энергии во времени.
Отметим, что выделенного количества бит может не хватить на представление сигнала в частотной области. Большому числу спектральных коэффициентов при кодировании могут быть сопоставлены нулевые значения. В результате синтезированный сигнал приобретает «металлическое» звучание либо появляется так называемый «музыкальный шум». Для подавления этих эффектов в низкоскоростных системах сжатия используют подстановку шума, амплитуда которого оценивается кодирующим устройством как корень средней энергии с некоторыми поправками, учитывающими особенности звукового восприятия.
1.1.1. Блок фильтров
На блок фильтров возлагаются задачи получения спектра 5(/) сигнала з(п), определения параметров сигнала, оценивания временных и частотных характеристик сигнала [7]. Структурная схема блока фильтров приведена на рис. 1.3. В зависимости от конкретной реализации кодека блок фильтров может выполнять следующие действия для каждого кадра звукового сигнала:
Модифицированное дискретное косинусное преобразование (МДКП), модифицированное дискретное синусное преобразование (МДСП).
Получение амплитудного спектра сигнала.
Рис. 1.3. Структурная схема блока фильтров
Согласно рис. 1.2, на вход модуля квантования поступает спектр сигнала .ч(п).
Обозначим через N количество отсчетов спектра сигнала. Для получения спектра сигнала обычно используют модифицированное дискретное косинусное преобразование сигнала взвешенное с окном Л(г), г = 0,...,2Ы-1 [1,3,4]:
ад= ^/г(1>(1)со8[яг(1 + (Л^ + 1)/2)(А: + 1/2)/Л^], к =0,...,Ы-I (1.1)
-о
Основными критериями для выбора окна /г служат возможность точного восстановления сигнала и степень локализации энергии при преобразовании с перекрытиями. В частности, можно использовать синусное окно
/г(0 = 8пфг(1 + 1/2)/2М].
Амплитудный спектр используется в тех модулях аудио кодека, где валено оценивать характеристики сигнала по устойчивому спектру от кадра к кадру. Поскольку коэффициенты МДКП зависят от фазы входного сигнала, МДКП спектр не дает удовлетворительной оценки энергетического спектра сигнала. Поскольку энергетический спектр необходим для корректной работы модели субъективного восприятия, дополнительно вычисляется МДСП преобразование. Модифицированное дискретное синусное преобразование вычисляется аналогично МДКП, в формуле (1.1) достаточно заменить косинус синусом:
2ЛГ-1
3\к)= А(1>(08т[яХ1 + (^ + 1)/2)№ + 1/2)/^1 к = 0,...,Ы-1 (1.2)
/=о
Амплитудный спектр сигнала при известных коэффициентах преобразований МДКП (1.1) и МДСП (1.2) вычисляется как:
Л =
2(АГ -1) , (1.3)
А(Л) = ^(Л)2+5'(Л)2
где (/*) - коэффициенты косинусного преобразования, 5 (/к) - коэффициенты синусного преобразования, к - номер отсчета в спектре. В дальнейшем индекс к в обозначениях дискретных значений частоты будем опускать / = /к.
1.1.2. Модель субъективного восприятия
Повышение качества передачи аудио информации требует повышения скорости передачи данных. Также эффективность кодирования аудио сигналов можно повысить, используя обобщенную модель восприятия аудио информации человеческим ухом. В дальнейшем эта модель будет назваться моделью субъективного восприятия (МСВ). За основу МСВ принят ряд свойств, связанных с восприятием звука человеком. Наиболее важными из них являются свойство маскирования одних компонент звука другими и восприятие силы звука по логарифмической шкале. Применение модели субъективного восприятия к кодированию аудио сигналов - не новая идея [58], большинство современных аудио-кодеров достигают необходимого уровня сжатия за счет ухудшения качества передачи набора компонент сигнала, который является незначимым для данного уровня сжатия, даже если эти компоненты и слышны хорошо тренированным слушателям. Незначимые компоненты обычно идентифицируются на этапе анализа входного сигнала с помощью таких факторов субъективного восприятия, как:
абсолютный порог слышимости,
частотный состав по полосам Барка, определение которых дано ниже,
взаимное маскирование компонент спектра,
распространение влияния компоненты спектра на ее окружение в частотной области.
Комбинирование факторов восприятия и квантования сигнала является ключевым моментом при оценке перцептуальной энтропии [35], используемой для первоначального определения битовых затрат при сжатии аудио сигналов.
В этом разделе будет рассмотрено только два основных принципа, на основе которых строится модель субъективного восприятия. Более детальное описание модели
субъективного восприятия и перцептуальной энтропии будет приведено в четвертой главе.
(1.4)
Отметим, что основой для любой модели субъективного восприятия служит разбиение полосы звуковых сигналов на спектральные подполосы по определенному закону. Формально, закон разбиения может быть любым, но желательно учитывающим субъективное восприятие. Для построения оптимального разбиения спектра на полосы необходимо определиться с тем, как человеческое ухо выполняет спектральный анализ. На данный момент установлено, что частотно-пространственный анализ выполняется в ушной раковине, на базилярной мембране [32,57,66]. Каждый из участков базилярной мембраны можно рассматривать как множество нейронных рецепторов, которые реагируют на определенный частотный диапазон. Таким образом, базилярная мембрана может быть рассмотрена как банк фильтров с высокой степенью перекрытия полос пропускания. Реакция на амплитуду сигнала ассиметрична и нелинейна (зависит от уровня сигнала). Более того, полосы пропускания фильтров, представляющих базилярную мембрану, имеют неравную ширину, и известно, что ширина полосы пропускания возрастает при увеличении частоты. Некоторые зависимости ширины полосы пропускания фильтров были выявлены в практических работах [32,57,66] по исследованию реакции человеческого уха на различные сигналы. На сегодняшний день существует множество различных функций аппроксимации для ширины полос пропускания фильтров. Большая часть из них дает похожие результаты. Наиболее часто используемая аппроксимация приведена в работе [65].
г(/) = 13агс^(0.00076/) + 3.5а/-с^((//7500)2), Барк,
где / - значение частоты в Гц, г(/) - значение частоты в единицах шкалы Барка.
Ширина полосы пропускания полосового фильтра равна одному Барку. Формула (1.4) показывает соотношение частоты в герцах с единицами в Барках. Зависимость ширины полосы пропускания фильтра от частоты приведена на рис. 1.4.
Частота, Гц
Рис. 1.4. Шкала Барка
Как показано на рис. 1.4, количество полос Барка для спектра кадра длиной 1024 отчета (частота дискретизации 44100 отсчетов в секунду) равно 25. Отметим, что при длине кадра 128 отсчетов количество полос Барка будет несколько меньше. Факт уменьшения количества полос с уменьшением длины спектра позволяет сделать вывод о том, что количество полос определяется разрешающей способностью спектральной обработки.
Далее рассмотрим одно из основополагающих понятий теории субъективного восприятия - абсолютный порог слышимости.
(1.5)
Абсолютный порог слышимости характеризует количество энергии необходимой для того, чтобы тональный сигнал был слышен. Абсолютный порог обычно выражается в единицах уровня звукового давления (Sound Pressure level, dB). Зависимость данного порога от частоты спектра была исследована Флетчером, опубликовавшим результаты в отчете организации NIH (National Institutes of Health) [29]. В работе [60] было показано, что для абсолютного порога слышимости существует хорошая аппроксимация нелинейной функцией следующего вида:
Тд(/) = 3.64(/ /1000)8 _6.5e--6(//1000-3-3)I +10~3(//1000)4, дБ
где / — частота в герцах.
Физический смысл абсолютного порога слышимости достаточно прост. В области сжатия аудио сигналов Т (/) может интерпретироваться как уровень максимально
допустимой энергии ошибки, вносимой в частотную область за счет кодирования коэффициентов преобразования. Также абсолютный порог слышимости можно использовать как детектор слышимости спектральных коэффициентов. В частности, если энергия спектрального коэффициента (в БРЬ единицах) превышает значение порога, то можно однозначно утверждать, что данный спектральный коэффициент слышен человеческим ухом. Зависимость абсолютного порога слышимости от частоты, соответствующей спектральному коэффициенту, приведена на рис. 1.5.
О 2.5 5.0 7.5 10.0 12.5 15.0 17.5 20.0 22.5
Рис. 1.5. Абсолютный порог слышимости
Частота, кГц
Энергия, SPL дБ
Энергия спектрального коэффициента в единицах звукового давления определяется формулой:
Р(/) = 90.302 + Ю^10(А(/)/2ь-1/^)2 (с1В) (1.6)
где А(/) - амплитудный спектр сигнала, Ь - разрешение импульсно кодовой модуляции, N
- длина спектра.
Важно отметить, что абсолютный порог слышимости подразумевает слышимость тона в бесшумной среде. Таким образом, данный порог в полной мере является абсолютной характеристикой слышимости тонов сигнала.
Следующий принцип, используемый моделью субъективного восприятия, заключается в маскировании одного тона другим. Маскирование возникает из-за того, что при наличии сильно тонального звука, человеческое ухо может не слышать более слабые тональные звуки, имеющие близкие частоты по отношению к рассматриваемому звуку. На основе этой информации строится так называемый маскирующий порог слышимости.
Маскирующий порог, как правило, используется для определения факта маскирования шумовых компонент спектра тональными частотами, а также маскирования тональных частот шумовыми компонентами спектра. Отметим, что маскирующий порог находится всегда выше абсолютного порога слышимости (см. рис. 1.6). Более детальное пояснение относительно построения и последующего использования маскирующего порога слышимости будет дано в главе 4.
1.1.3. Распределение бит
Устройство сжатия аудио информации с заданной битовой скоростью содержит модуль распределения бит, который управляет битовыми затратами на кодируемый кадр. Обычно
целевая битовая скорость Я задана. Существует несколько подходов, обеспечивающих кодирование с целевой скоростью Я :
Кодирование каждого кадра сигнала с фиксированной скоростью И .
Кодирование кадров сигнала со случайной скоростью и средним значением по всем кадрам /?.
Кодирование кадров со случайной скоростью
Скорость на кадре:
= 50 Кбит/секунду = 2 Кбит/секунду — 44 Кбит/сскунду
Целевая скорость: д = V д. / и = 32 Кбит / секунду * Я,, V*
Рис. 1.6. Управление битовой скоростью
Способ кодирования кадров с фиксированной скоростью является самым простым подходом к обеспечению требуемой скорости. В этом случае никак не учитываются свойства сжимаемой информации. Даже тогда, когда кодируемый кадр является тишиной или шумом, битовые затраты составляют величину равную целевой скорости. Таким образом, в случае тишины или шума вносится избыточность в схему сжатия информации (см. рис. 1.6). Помимо недостатка в виде избыточности, данный подход обладает очень важным свойством: результат кодирования аудио сигнала будет более стабильным, но менее качественным, чем для случая случайной скорости кодирования.
Сигнал Шум Сигнал
Методы контроля битовой.скоддсти
' Кодирование кадров с фиксированной скоростью
Скорость на кадре:
Л. , =32 Кбит/секунду Я; = 32 Кбит/секунду /?;+1 = 32 Кбит/секунду
Целевая скорость: я = 32 Кбит / секунду = Я,., V/
Кодирование кадров сигнала со случайной скоростью основано на том, что в аудио сигнале присутствуют участки, которые требуют гораздо меньшего числа бит, чем целевая скорость кодирования. Например, к таким участкам относится тишина или шумовые фрагменты звука. Как показано на рис. 1.6., кадры, состоящие из тишины или шума, могут быть закодированы со скоростью меньшей целевой, при этом разница в битовых затратах будет существенной (например, — =30 Кбит/с).
В случае кодирования со случайной скоростью разница в битовых затратах
помещается в так называемый битовый мешок. Следует отметить, что величина /?(/ может
быть как положительна, так и отрицательна. Отрицательность величины свидетельствует
о том, что кадр был закодирован со скоростью большей, чем целевая. Такая ситуация связана с наличием участков звука, на которые желательно потратить больше бит для повышения качества их передачи. Обычно этими участками являются сложные кадры для кодирования, такие как быстро меняющиеся звуки. Потери бит, связанные с более качественной передачей звука, компенсируются из битового мешка.
Таким образом, рассматриваемый подход дает целевую битовую скорость в среднем, но допускает ее отклонение от целевой скорости на отдельных кадрах (см. рис. 1.6). Данный способ распределения битовых затрат более эффективен по причине нестационарности аудио сигнала. Более того, эффективность кодирования со случайной скоростью подтверждается тем, что перцептуальная энтропия, отражающая битовые затраты, изменяется во времени.
1.1.4. Сжатие информации без потерь
Сжатие без потерь - это передача информации с затратами меньшего числа бит, но при точном последующем восстановлении [2]. Уменьшение битовых затрат достигается за счет неравномерного распределения вероятности передаваемых данных. Как известно, пределом сжатия информации является оценка на основе энтропии. Энтропия дискретного источника без памяти определяется формулой:
# = х 1о Р'' Р* е (1.7)
где р1 - вероятности появления символов источника.
Известно много алгоритмов сжатия информации. Например, кодирование по Хаффману [25], арифметическое кодирование [62], алгоритмы универсального кодирования [61,64]. Для источника без памяти скорость кодирования К близка к энтропии Н (1.7), при использовании арифметического кодирования с известной моделью источника.
Следует отметить, что модель источника данных определяется областью применения. На практике, как правило, модель источника не известна, поэтому используют различные способы адаптации принятой модели. Адаптация производится с помощью оценивания вероятностей р[ в формуле (1.7). Как правило, для адаптации кодирования используется некоторая дополнительная информация. Например, параметры модели распределения данных или уже переданная и восстановленная часть информации. Если в качестве дополнительной информации выступают параметры модели, то, возможно, потребуется их
передача в битовый поток. Если же используется часть переданной информации, то никаких дополнительных битовых затрат не требуется.
1.1.5. Формирование битового потока
Модуль формирования битового потока выполняет упаковку передаваемой информации в соответствии с заданной структурой данных. Формат структуры потока обычно определяется стандартом, для которого разрабатывается кодирующее устройство. Передаваемая информация подразделяется на два типа: служебная и основная.
Битовый поток
Служебная информация
Основная информация
Основная информации
Шкалы квантования
Закодированные кванты
Информация о шуме
Заголовок кадра
Длина кадра Алгоритмы сжатия
Параметры алгоритмов
Рис. 1.7. Пример структуры битового потока
Синхрослово
Заголовок клипа
Под основной информацией понимаются данные, порождаемые работой алгоритмов сжатия аудио сигнала. Этот вид информации, так же как и заголовок кадра, состоит из данных специфичного типа, обусловленных схемой сжатия и стандартом. В частности, общая информация может включать в себя шкалы квантования, закодированные кванты, информацию о шуме и т.п. (см. рисунок 1.7).
Поток данных состоит из отдельных кадров. Служебная информация кадра содержит синхрослово, заголовок и дополнительные параметры. Синхрослово необходимо для организации возможности проигрывания звукового файла с произвольного момента времени (см. рисунок 1.7). Заголовок кадра служит для указания типа последующей информации, идентификации длины кадра, а также информацию о выбранных алгоритмах сжатия данных, параметры алгоритмов и т.п. (см. рисунок 1.7).
Служебная инДтпмяния
1.2. Сжатие информации с потерями
В сжатии информации с потерями основополагающую роль играет квантование. Процесс квантования является дискретизацией сигнала по амплитуде [18,19,20]. Дискретизация по амплитуде - это необратимое преобразование. Следствием этого является появление ошибки квантования. Величина ошибки зависит от метода квантования.
В общем случае процесс квантования описывается моделью, показанной на рис. 1.8.
Оригинальный сигнал Квантованный сигнал
SAf)
R, кбит / с
Rq, кбит / с
Модуль квантования
Параметры
Рис. 1.8. Квантование сигнала
Чем меньше бит отводится на представление квантованного сигнала, тем больше ожидаемая ошибка квантования. Таким образом, существует зависимость между количеством бит, представляющих квантованный сигнал, и ошибкой квантования. Зависимость наименьшего достижимого количества бит при заданной ошибке кодирования определяется функцией скорость-искажение источника.
1.2.1. Теоретико-информационные пределы эффективности кодирования при
сжатии с потерями
Как установлено в работе Шеннона [22], теоретико-информационным пределом эффективности кодирования при сжатии с потерями является функция скорость-искажение источника (эпсилон-энтропия). Эта функция отражает наименьшую скорость кодирования источника при заданной ошибке кодирования.
Пусть имеется непрерывный стационарный источник, выбирающий сообщения из непрерывного множества X. Предположим, что У — аппроксимирующее дискретное множество и d(x,y) — неотрицательная функция, задающая величину ошибки аппроксимации хе X величиной уеУ. Функция d(x,y) называется критерием качества. Для каждого целого п, п = 1,2,..., определен ансамбль {1",/(х)} и {У",/(у)} последовательностей сообщений длины п, распределение вероятностей на которых задается посредством функций плотности вероятности (ф.п.в.) /(х) и /(у), x = (jc,,...,jcJeJf" и
у = (у,,..., Э>л ) е У ". Тогда критерий качества для последовательности длины п :
(х»У) = У,-). (1.8)
П /=1
Операция квантования представляет собой операцию замены вектора х = (x,,...,jcn) из множества X" аппроксимирующим вектором у = (yj,...,^) из множества У". Для
выполнения квантования строится кодовая книга В z У", содержащая M аппроксимирующих последовательностей {Ух,.-->УмЬ Скоростью создания информации источником X относительно критерия качества d(x,y) называется наименьшее число H(D) такое, что для любой R > H(D) возможна аппроксимация со скоростью R и средней ошибкой ~d~n — M[dn(х,у)] , Tn
Для того, чтобы установить, что некоторое число H(D) является скоростью создания информации относительно критерия качества d(x,y), необходимо доказать справедливость двух следующих утверждений:
Для любого R>H(D) найдется п и аппроксимация сообщений х = (jc,,...,jrn) длины п со скоростью R, для которой средняя ошибка относительно критерия качества d(x,y) не превосходит D (прямая теорема кодирования).
Для любого R < H{D), для всех п и возможных аппроксимаций со скоростью R средняя ошибка относительно критерия качества d(x,y) превышает D (обратная теорема кодирования).
Для анализа эффективности методов квантования необходимо оценить величину скорости создания информации для различных источников [10].
(1.9)
Пусть /(ylx), хе X", - произвольное семейство условных функций плотности вероятности на множестве У" . Эти функции плотности вероятности совместно с функциями /(х) задают ансамбль {Х"У",/(х,у)}, где /(х,у) = /(х)/(у I х) и
Л У)= \f(x)f(y\x)dx.
X"
Пусть X" =Х1...Хп и У'!=У!...Уп, где Х1 и - ансамбль сообщений и аппроксимирующих сообщений в момент времени . В общем случае ф.п.в. /(.х^у^, задающая распределение вероятностей на ансамбле Х1У1, зависит от номера /.
Для ансамбля {X"У",/(х,у)}определены две величины. Одна из них - средняя взаимная информация /(Х";У) между ансамблями X" и У":
(1.10)
Другая - средняя ошибка аппроксимации:
где
di = \d(xl,yl)f(xi)f{yi\xi)dxldyl. (1 л2)
X.r,
Пусть Фл(0) есть класс всех функций плотности вероятности /(ylx) такой, что для каждой функции из этого класса средняя ошибка не превосходит D :
Ф„(>) = {/(у1х):^
Пусть
Hn(D) = mm-I(Xn-Yn), (1.14)
Ф„(0) п
где минимум разыскивается по всем функциям /(у 1л) из класса функций Ф„(Д). Тогда функция от D
H{D) = MHn{D), (1Л5)
где точная нижняя грань берется по всем п, п = 1,2,..., называется функцией скорость- искажение источника H(D) относительно критерия качества d(x,y).
1.2.2. Классификация методов квантования
Рассмотрим понятие скорости кодирования. Постоянная скорость кодирования представляет собой число бит, требующихся для представления данных в двоичной форме. Постоянная скорость кодирования определена, когда мощность алфавита кодируемого источника данных конечна. Случайная скорость кодирования получается в результате использования методов сжатия без потерь, например, арифметического кодирования. При достаточно большом объеме выборки случайная скорость кодирования стремится к энтропии кодируемого источника данных. В дальнейшем случайная скорость будет называться скоростью кодирования, а постоянная скорость - скоростью квантования. Методы квантования классифицируются по размерности п вектора х (вектор х является сообщением). Если длина вектора х равна единице (и = 1), тогда квантование называется скалярным. Скалярное квантование - это замена значения х величины X ближайшим значением у из некоторого дискретного множества значений Y = {>*!,..., ;yw } В этом случае, скорость квантования равна R = log2 M бит на отсчет. Если размерность вектора х отлична от единицы (п > 1), квантование принято называть векторным. Векторное квантование — это замена вектора величин х = из множества X" ближайшим вектором величин
у = (у1г..., уп) из множества векторов у1,...,ум. Тогда скорость квантования выражается \о%2 М
через к = -— бит на отсчет.
Равномерное скалярное квантование. Скалярное квантование предполагает, что на числовой оси определен непрерывный вероятностный ансамбль Х = (—о,о), заданный плотностью распределения /(х), хе X . В данном случае квантованием называется отображение множества X на дискретное аппроксимирующее множество У с X .
Такое отображение можно задать, разбив множество X на прилегающие друг к другу непересекающиеся отрезки одинаковой длины (= X , =0 при } ^ _/') и
выбрав по одной точке каждого отрезка в качестве одного из элементов у е У. Отрезки называют квантами, границы отрезков - границами квантов, элементы множества У - аппроксимирующими значениями, длина отрезка - шагом квантования.
Для простоты предположим, что У - конечное множество, число его элементов |К| = М представляет собой число квантов или объем аппроксимирующего алфавита. Обозначим через у1,...,ум аппроксимирующие значения, а через Ь0,Ь],...,Ьм границы квантов.
Подразумевается, что у1 е = ,6,0 и у} е 11, = . Если функция плотности
вероятности /(х) определена на всей числовой оси, то Ь0 =-о, Ъм — .
Если все параметры квантователя (числа уп г = 1 ,...,М , Ьг У = 0,...,М) заданы, тем самым определена дискретная случайная величина У = {yj,j = 1,...,М}, вероятности значений которой вычисляются по формуле
(1.16)
Алгоритмически квантование выполняется как сравнение входной величины х с границами квантов 7 = 0,...,М и определение номера кванта У содержащего л:. Номер
7 , записанный в двоичной форме, хранится или передается по каналу связи. Наиболее часто используемый на практике равномерный квантователь такого типа выполняет простую операцию арифметического округления частного х!8:
(1.17)
где 3 — шаг квантования.
К последовательности номеров квантов на выходе квантователя может быть применено неравномерное кодирование, в частности, арифметическое кодирование, скорость которого Я будет сколь угодно близка к энтропии, т.е.:
к = (1Л8)
]
При восстановлении по кодовому слову (двоичной записи номера выбирается аппроксимирующее значение у]. В большинстве реализаций равномерного скалярного квантования у. выбирается в середине аппроксимирующего отрезка:
У ^ — н , у = 1 (1.19)
В качестве меры искажения на практике применяется среднеквадратическая ошибка, определяемая как
0 = м[(х-у(х))2]=^1(х-у^/(х)с1х. (1 20)
Характеристики равномерного квантователя можно достаточно легко вычислить в предположении, что точность квантования велика, что соответствует малому значению шага квантования 8. В этих условиях плотность распределения можно принять постоянной в пределах одного кванта. Тогда равенства (1.14) и (1.18) переписываются следующим образом:
^»/ВД. (1.21)
У ,+81 2 „2
D = I (х-- уjУlf{x)dx - X^ (x-yj)2dx = — . (,_22)
j I) J у,-812
То есть, ошибка кодирования зависит только от шага квантования. Скорость квантования, выражаемую формулой (1.18), можно оценить по формуле:
Я = logр, log( j j j ij ~"S J/W(*)>& = - J/(*)log( j Ij X Через функцию H0(X) обозначена дифференциальная энтропия случайной величины с плотностью распределения f(x). Из (1.22) и зависимости скорости от шага квантования следует, что функция скорость-искажение скалярного равномерного квантователя при малых шагах 8 задается соотношением: tf(D)~tf0(X)-|log(12D). (1.23) Неравномерное скалярное квантование. В случае неравномерного квантования длины квантов могут быть различными. Возможно два подхода к построению оптимального квантования: Минимизация среднеквадратической ошибки при заданной скорости кодирования. Минимизация скорости кодирования (энтропии квантованных значений) при заданной ошибке. Векторное квантование. Векторное квантование предполагает, что на вход квантователя поступает случайный вектор х = (хг,...,хп). Этот вектор заменяется ближайшим (в смысле выбранного критерия качества) вектором у = (у^,..., уп) из аппроксимирующего множества Y = {у,,...,уЛ/}. Аппроксимирующее множество Y часто называют кодовой книгой. Если функция плотности вероятности не известна, тогда для построения кодовой книги используется алгоритм Линде-Бузо-Грея (ЛБГ). Этот алгоритм представляет собой обобщение процедуры Ллойда-Макса и состоит из 4 шагов: Инициализация. Известно множество реализаций вектора х: х, = (д:п,...,л-1л), х2 =(jc21,...,jc2J, ..., xk = (xkl,...,xu). Задан размер кодовой книги, которую необходимо построить М «k, М = 2й", где R - требуемая скорость кодирования. Построение начальной кодовой книги. Выбор М произвольных векторов из множества х ., j = 1,... ,к в качестве аппроксимирующих у;, i = 1,..., М . Для всех векторов х., j = \,...,k устанавливается Sj =0, numi =0, i = l,...,M . Вычисление ошибки по формуле е = min (х. -уг)(х, -у,)Г, где Т обозначает операцию транспонирования. Вычисление индекса вектора в книге, при котором достигается минимум ошибки для вектора х, по формуле iopt =arg( min (х . -y;)(x . - у,)7-). Вычисление покомпонентной суммы векторов S, = S + х . 1 'api opl J Вычисление количества векторов Xj, ближайших к каждому из аппроксимирующих значений y : num = num +1. Для всех 1 = 1 вычисляются новые аппроксимирующие значения по формуле у; = Si /пит,.. 4. Если условие останова алгоритма не выполнено, тогда возвращение к шагу 3. Условием останова алгоритма служит одно из следующих событий: Аппроксимирующие значения, полученные на текущем шаге отличаются от аппроксимирующих значений, полученных на предыдущем шаге менее, чем на заданную величину. Число итераций превысило допустимое количество. Среднеквадратическая ошибка квантования оказалась меньше заданной. Результатом применения процедуры Линде-Бузо-Грея является кодовая книга аппроксимирующих значений для вектора х. При этом в процессе выполнения процедуры п -мерные аппроксимирующие значения смещаются в высоковероятные области. Структурная схема алгоритма Линде-Бузо-Грея приведена на рис. 1.9. _ _ Алп>1)»1М-ЛБГ Выбор М векторов в кодовую книгу : * Взвешенная сумма ближайших векторов к векторам из кодовой книги Множество реализаций вектора х Нахождение ближайшего вектота в книге Кодовая книга для векторов х М векторов к» М Рис. 1.9. Алгоритма Линде-Бузо-Грея Процедура квантования состоит в выборе для входного вектора х одного из векторов у,., i = 1 ,...,М , минимизирующего среднеквадратическую ошибку е — min (х —у;)(х —у;)г . Следует отметить, что на практике кодовая книга изменяется, адаптируясь к входному потоку данных. В некоторых приложениях адаптация кодовой книги необходима из-за наличия во входном потоке векторов, которые в отсутствие адаптации будут квантоваться с большими ошибками. к векторов 1.2.3. Ограничения на выбор метода квантования Модификация кодовой книги Условие останова Основной недостаток векторного квантования, в сравнении со скалярным квантованием, состоит в его высокой сложности. Процедура кодирования предполагает перебор по всем кодовым словам из кодовой книги. Например, при Л = 0.5 бит/отсчет и п = 32 размер кодовой книги составляет М = 216. Уменьшение сложности векторного квантования возможно за счет использования кодовых книг заданной структуры, например, решетчатых кодов. В этом случае для нахождения ближайшего вектора в кодовой книге может быть использован алгоритм декодирования решетчатых кодов, известный как алгоритм Витерби [28]. Тем не менее, сложность остается значительно выше сложности скалярного квантования. Поэтому практически во всех стандартных аудио кодеках используется скалярное квантование. В зависимости от стандарта сжатия аудио информации применяется равномерное или неравномерное скалярное квантование. Например, в стандарте МРЕв1 использовано равномерное скалярное квантования, а в стандартах МРЕС2 и МРЕС4 - скалярное неравномерное. В дальнейшем мы будем рассматривать исключительно скалярное квантование, и уделять большее внимание его оптимизации. 1.2.4. Оптимальные методы скалярного квантования Оптимизация выполняется за счет неравномерности расположения границ квантов. Для построения оптимальных методов скалярного квантования используются критерий минимума средней ошибки квантования при заданной скорости или минимума скорости кодирования при заданной ошибке. Границы подбираются так, чтобы минимизировать один из параметров при ограничении на другой параметр. Оптимальное квантование по минимуму средней ошибки. Существенные шаги в направлении повышения эффективности скалярного квантования были сделаны Ллойдом (1957) и Максом (1960) [40,44]. Независимо друг от друга они решали задачу нахождения квантователя, который минимизирует среднеквадратическую ошибку при заданном числе квантов и предложили описанный ниже способ построения оптимального квантователя по заданной плотности распределения /(х). При известном числе квантов М среднеквадратическая ошибка квантователя с границами квантов 6,, / = 0,...,М, и аппроксимирующими значениями уп г = 1,...,М, может быть вычислена по формуле: 0 = М[(х-у(х))2] = (х-У;)2/(х)с1х. (1.24) М ьм Приравнивая производные правой части уравнения по переменным bj и yj к нулю, после простых вычислений определяются аппроксимирующие значения и границы квантов: ' p jf(x)dx (1.25) (1.26) где использованы следующие обозначения: pj= ^f(x)dx, rrij = ^xf(x)dx. Принимая во внимание (1.25) и (1.26), ошибка квантования (1.24) приводится к виду: (1.27) где Е представляет собой среднюю энергию одного значения случайной величины. Из формул (1.25) и (1.26) следует, что границы квантов оптимального квантователя делят пополам интервалы между аппроксимирующими значениями, а аппроксимирующие значения являются «центрами тяжести» квантов. В общем виде найти совместное решение (1.25) и (1.26) невозможно, но следующая итеративная процедура решает эту проблему. Итерационная процедура носит название алгоритм Ллойда-Макса (алгоритм JIM). Ниже приведено формальное описание алгоритма: Инициализация. Выбираем произвольным образом начальное положение границ квантов ЬХ,...,ЬМ_\ (границы Ь0 и Ъм соответствуют нижней и верхней границе области значений величины *). В качестве текущего значения ошибки принимается Ц. = Е. Выбирается некоторая малая величина (точность приближения к минимальному значению ошибки) и фиксируется максимальное количество итераций Л^. По формулам (1.25) и (1.26) находим аппроксимирующие значения уу,...,ум и границы квантов Ь1,...,ЬМ_ 1. По формуле (1.27) вычисляем новое значение ошибки И. Если Д. - В > и максимальное допустимое число итераций ЛгП1ах не превышено, то полагаем = ) и возвращаемся к шагу 2. В противном случае работа алгоритма закончена. При решении практических задач плотность f(x) бывает неизвестной. Вместо нее имеется некоторая реализация случайной последовательности хх,..., xN на выходе источника. В этом случае оптимальный квантователь по минимуму среднеквадратической ошибки, также может быть построен с помощью алгоритма JIM с той разницей, что числа rrij и Pj в этом случае вычисляются по формулам: 2 п т}=— Pj=--/г,-=|{* .)}|. n Mbj-Lbj) Схема алгоритма Ллойда-Макса приведена на рис. 1.10. Границы квантов b, j = I,..., М -1 Рис. 1.10. Структурная схема алгоритма Ллойда-Макса На первый взгляд, ЛМ квантователь должен быть заметно лучше равномерного, поскольку принимает в расчет неравномерность распределения квантуемых значений вдоль числовой оси. Он уделяет «больше внимания» той области, вероятность появления значений которой больше. Напротив, широкие кванты и, соответственно, большая ошибка будет допущена для редко встречающихся значений случайной величины. Однако, как мы увидим ниже при сравнении характеристик способов квантования, с учетом неравномерного кодирования на выходе квантователя, выигрыш не так велик и зачастую не оправдывает увеличения сложности квантования. Оптимальное квантование с ограничением на скорость кодирования. Здесь задача состоит в нахождении аппроксимирующих значений ух,...,ум и границ квантов b0,...,bM, при которых достигается минимальная ошибка при заданной скорости кодирования. Теперь накладывается ограничение не на число квантов М, а на величину энтропии последовательности квантованных значений. Решение данной задачи было представлено в работе Т. Бергера [21]. При заданных аппроксимирующих значениях у = (ух,-..,ум) и границах квантов b = (bQ,...,bM) ошибка и скорость вычисляются по формулам: /VI 1 Я(Ь,У) = \(х-у^2/(х)с1х, (1.28) ^(Ь, у) = Р] р], (1.29) Р] = /(х)(1х, ) =1,...,М . (1.30) Задача состоит в нахождении пары (Ь,у), которая дает минимальную ошибку при заданной скорости ^ . Иными словами, требуется найти /)(/?0) = шах )(Ь,у). (Ь,у):й(Ь,у)<й0 Таким образом, необходимо решить задачу нахождения условного экстремума функции и стандартный способ ее решения - метод множителей Лагранжа. Идея метода состоит в том, что вводится вспомогательный параметр Л, и вместо условного минимума функции )(Ь,у) выполняется поиск безусловного минимума функции: <р(Ъ,у,Л) = >(Ь,у) + Л(Л(Ь,у) - Д0). (1.31) Случай Л — 0 соответствует поиску оптимального квантователя без ограничения на скорость и решением является алгоритм квантования Ллойда-Макса. Ограничение на скорость проявляется когда Л> 0. При скорости /?(Ь,у)>/?0 второе слагаемое вносит положительный вклад в функцию (1.31). Тогда, правильный выбор параметра Л приведет к тому, что в качестве оптимальной пары (Ь,у) будет выбрана именно та, для которой второе слагаемое в функции р(Ъ,у,Л) равно нулю, т.е. Д(Ь,у) = Предположим, что пара (Ь0,у0) оптимальна для некоторой скорости /?. Тогда выражение р(Ь0,у0,Л) = В(Ь0,у0) +ЛИ(Ь0,у0) —АЛ0 = О(И) + АЛ —АЛ0 представляет собой линейную функцию скорости Я0. Больше того, совершенно очевидно, что эта функция - касательная к графику >(/?) в точке К = Яа. Это означает, что Л нужно выбирать из условия л= Э>(/?) Трудность состоит в том, что функция неизвестна, ее отыскание как раз и является задачей, которую нужно решить. Поэтому значения Л находят перебором, либо задача решается в некотором диапазоне значений Л и тем самым строится график функции искажение-скорость в некотором диапазоне И . При фиксированном Л, дифференцируя (1.31) по каждой компоненте Ь] вектора Ь, приходим к следующим условиям минимума функции ф(Ь,у,Л): (1.32) Ф, -У,)2- Ф, - У ^ )2 - = 0, ]=1,... ,М -1. При этом аппроксимирующие значения должны удовлетворять уравнениям (1.25) (1.33) К сожалению, найти совместное решение уравнений (1.32) и (1.33) непросто. Один из путей к численному решению задачи - следующий. Значение Ь0 известно. Выбирается какое- либо значение Ъх. Тем самым мы определяются величины рх и . После этого можно выбрать Ь2 так, чтобы зависящие от этой величины р2 и у2 удовлетворяли уравнению (1.32). Продолжая рекурсию, находятся все параметры квантователя, но при этом может оказаться, что последняя граница кванта Ьм не совпадает с верхней границей области значений х. Чтобы исправить ситуацию, нужно скорректировать начальный выбор параметра >, и повторить вычисления. И так до тех пор, пока не будут найдены подходящие значения всех параметров квантователя. Этот алгоритм - один из двух алгоритмов построения оптимальных моделей квантования в работе Н. Фарвардина и Дж. Модестино [27]. 1.2.5. Избыточность скалярного квантования Как было показано, минимальная скорость кодирования с заданной ошибкой описывается функцией скорость-искажение источника Л()). Отметим, что в действительности скорость, даваемая этой функцией, не может быть достигнута при скалярном квантовании. Рассмотрим асимптотическую границу на избыточность скалярного квантования. В случае, когда рассматривается равномерное скалярное квантование с очень маленьким шагом квантования 8 —> 0 и среднеквадратической мерой искажения, установлено, что избыточность при квантовании составляет приблизительно 0.2546 бит. Этот факт был установлен сначала в работе Кошелева [11], затем в работе Гиша и Пирса [30]. Таким образом, при большой скорости кодирования, имеется теоретически доказанный факт о наличии подобной асимптоты. Если же рассматривать малые скорости кодирования (большие шаги квантования и ошибки), то теоретическая оценка не известна. На практике было установлено, что в случае малых скоростей, меньших одного бита на отсчет, избыточность составляет меньшую величину. Причем, чем меньше скорость кодирования, тем меньше избыточность. Оценка избыточности указывает максимальную величину выигрыша, который может быть получен за счет перехода от скалярного к векторному квантованию. Потенциальный выигрыш относительно невелик, если на передачу каждого числа отводится, скажем, 16 бит. Однако, во многих приложениях допустимые затраты не превышают одного бита на отсчет. В таких условиях задача повышения эффективности скалярного квантования по сравнению с равномерным скалярным квантованием остается достаточно важной. 1.2.6. Сравнение методов скалярного квантования Сравнительный анализ методов скалярного квантования приведен в работе Н. Фаравардина и Дж. Модестино, описывающей алгоритмы построения оптимального скалярного квантования [27]. Были построены графики функции скорость-искажение для некоторых типов случайных величин, а также показана асимптотическая граница Кошелева (Гиша-Пирса) на избыточность скалярного квантования. Равномерное распределение случайной величины описывается функцией плотности вероятности: (1.34) хе [а,Ь] - а где а и Ь - параметры распределения. На рис. 1.11 приведены графики функции скорость-искажение оптимального скалярного квантования для равномерного распределения при различном числе квантов N . Там же показаны функция скорость-искажение источника и асимптотическая граница Кошелева (Гиша-Пирса). .. % Асимптота Кошелева М» 0.1 I 1)1(7 О, Рис. 1.11. Функция скорость искажение оптимального квантования для равномерного распределения Обобщенное гауссово распределение случайной величины описывается функцией плотности вероятностей: осп {а, or) 2Г(1/дг) (1.35) ехр{-[^(а,сг)|л|]аг}, 1/2 7j(a,cr) = a 1 Г(1/ог) и а - параметр, характеризующий скорость экспоненциального убывания распределения, а - среднеквадратическое отклонение, Г(-) - гамма функция. Т{Ъ la) (1.36) Если параметр а = 2, то из обобщенного гауссова распределения получается нормальное распределение: гехр^ 1 f „2 ] (1-37) пит V 2сг ] Если задать параметр а — 1, то обобщенное гауссово распределение сводится к распределению Лапласа: /(*) = (1.38) На рис. 1.12 приведены графики функции плотности вероятности обобщенных гауссовых распределений с различными параметрами а и дисперсией <т2 = 1. fix) Рис. 1.12. Функция плотности вероятности обобщенного гауссова распределения На рис. 1.13-1.14 приведены графики функции скорость-искажение оптимального скалярного квантования для обобщенного гауссова распределения с различными параметрами при различном числе квантов N. Там же показаны функция скорость- искажение источника и асимптотическая граница Кошелева (Гиша-Пирса). обобщенного гауссовского распределения с параметром (X = 0.5 Рис. 1.14. Функция скорость искажение оптимального квантования для обобщенного гауссовского распределения с параметром а = 1.0 и а = 2.0 Как видно из рисунков 1.13-1.14 потери квантования на больших скоростях составляют 0.2546 (асимптота Кошелева), а при малых скоростях (< 1 бита на отсчет) потери составляют меньшую величину. В дальнейшем понадобится формула для вычисления дифференциальной энтропии источника: Я0(Х) = - |/(х)1оё2/(*)<&. (1.39) Для обобщенного гауссова распределения, энтропия Н0(Х) может быть выражена через параметры источника: Н0(Х) = - 1оё2 Приведенный выше обзор текущего положения в области квантования аудио данных позволяет сделать следующие выводы. Выбор способа квантования определяется соотношением между скоростью и ошибкой кодирования и вычислительной сложностью. Рассмотрим специфику области применения (сжатие аудио данных). Практически во всех стандартных аудио кодеках присутствует модель субъективного восприятия, которая определяет допустимый уровень ошибки для разных участков спектра. В связи с этим появляется задача распределения битовых ресурсов между полосами спектра для улучшения субъективного качества. Распределение битовых ресурсов требует возможности и управления квантованием. Управление квантованием выражается в нахождение таких параметров квантователя, чтобы ошибка или скорость кодирования были приблизительно равны заданным. Далее рассмотрим сравнительную оценку приведенных выше способов квантования. Равномерное скалярное квантование обеспечивает возможность управления качеством квантования за счет изменения шага квантования. По вычислительной сложности равномерное скалярное квантование также лучше других методов. Однако, равномерное скалярное квантование проигрывает при сравнении информационной характеристики скорость-искажение с другими методами, что делает его применение непривлекательным на практике. Векторное квантование является с точки зрения функции лучшим вариантом по сравнению со скалярным квантованием, но обладает существенно большей вычислительной сложностью. Управление векторным квантованием также затруднено. Оптимальное равномерное скалярное квантование дает лучше результат, чем равномерное скалярное, согласно кривой -/?( ), но не применимо на практике из-за наличия бесконечного числа параметров требующих передачи. Процедура оптимизации Макса-Ллойда, основанная на анализе распределения данных не учитывает скорость кодирования, поэтому является оптимальной только с точки зрения ошибки. По этой причине, характеристики этого квантователя оказываются хуже, чем равномерного скалярного квантования (при некоторых распределениях входных данных). Неравномерное скалярное квантование, предложенное в работе Фарвардина, обладает достаточно большой вычислительной сложностью и не позволяет добиться управления квантованием. Из изложенного материала явно проявляется необходимость в разработке нового способа квантования, требования к которому приведены ниже. Итак, сформулируем задачу построения адаптивного скалярного квантования для системы кодирования аудио сигналов. Необходимо разработать способ квантования для кодирования спектральных коэффициентов аудио данных, который удовлетворяет следующим требованиям: Вычислительная сложность должна быть соизмерима со сложностью равномерного скалярного квантования. Необходима возможность адаптивного выбора параметров в зависимости от свойств кодируемого сигнала. Функция скорость-искажение квантователя должна быть как можно ближе к функции скорость-искажение источника при любых входных данных. Должна обеспечиваться возможность адаптивного квантования спектральных коэффициентов в зависимости от требуемой ошибки квантования. Для разрабатываемого метода квантования должна быть определена достаточно точная аппроксимация функции скорость-искажение /?()) с целью ее последующего использования в качестве перцептуальной энтропии. 1.4. Результаты и выводы В данной главе приведен обзор методов кодирования спектральных коэффициентов в системах сжатия аудио информации. В качестве результатов главы отметим следующие: Показано, что эффективность системы сжатия аудио сигналов существенно зависит от выбранного способа квантования. На основе сравнительного анализа способов квантования и вычислительной сложности показано, что применяемые в настоящее время способы квантования не обладают некоторыми необходимыми характеристиками, такими как адаптивность, невысокая вычислительная сложность, эффективность. Сформулирована задача разработки способа адаптивного скалярного квантования на основе принятой модели распределения спектральных коэффициентов при заданных ограничениях на вычислительную сложность. Описанные в этой главе результаты экспериментов и вычислений позволяют сделать следующие выводы: Функция скорость-искажение квантования ограничена снизу функцией скорость- искажение источника, а сверху - асимптотой Кошелева-Гиша-Пирса. Сформулированным требованиям к способу квантования не удовлетворяет в полной мере ни один из предложенных в литературе квантователей. Для построения адаптивного скалярного квантования необходимо построить адекватную математическую модель спектральных коэффициентов. 2. Информационные характеристики потока аудио данных 2.1. Методы вычисления функции скорость-искажение источника данных В разделе 1.2.1 было дано формальное определение функции скорость-искажение источника H(D), как наименьшего числа бит, которое необходимо для передачи сигнала с ошибкой не выше D. Рассмотрим два возможных способа приближенного вычисления функции H(D). Первый подход основан на применении аналитического выражения для нижней границы на функцию H(D). Для непрерывного источника данных известна нижняя граница Шеннона [22] на функцию скорость-искажение источника, вычисляемая по формуле: дифференциальная энтропия источника (1.39). При известной функции плотности распределения f(x) источника, пользуясь формулами (1.40) и (2.1), можно найти выражение для вычисления функции скорость- искажение источника через параметры функции f{x). Например, для обобщенного гауссова распределения (1.35-1.36) нижняя граница Шеннона выражается через параметры а и сг: Аналогичным образом находится выражение нижней границы на функцию скорость- искажение Н{П) для любого процесса, если возможно аналитически вычислить дифференциальную энтропию источника. Точность оценки Шеннона для функции скорость- искажение источника будет приведена ниже. Если закон распределения /(х) неизвестен, тогда воспользоваться методикой описанной выше невозможно. В этом случае используется второй подход, основанный на применении численных методов вычисления Я(О). Формулы (1.13-1.15) показывают, что вычисление Н(О) является задачей поиска условного экстремума функции. Большую роль в этом направлении сыграла работа Р. Блейхута [23], где приведен алгоритм расчета функции скорость-искажение источника по экспериментальным данным. Этот метод получил название алгоритма Блейхута. Дальнейшее изложение материала связано с описанием алгоритма Блейхута из работы [23] и анализом результатов, получаемых при его использовании. Предварительная обработка спектральных коэффициентов необходима для корректного определения информационных характеристик сигнала и основана на том, что анализируемый сигнал можно разложить на составляющие компоненты, разбить на полосы частотных диапазонов и учесть особенности субъективного восприятия. Предварительная обработка спектральных коэффициентов состоит из нескольких этапов: Разбиение спектра на полосы. Использование принципов субъективного восприятия. Классификация полос по признаку тональности. Разбиение спектра на полосы. Разбиение исходного спектра на полосы помогает повысить эффективность кодирования аудио сигнала. Эффективность кодирования может быть оценена функцией скорость-искажение источника. Повышение эффективности кодирования спектра сигнала основано на том, что функция H{D) некоторого процесса в исходном диапазоне частот больше, чем средняя Н(И) по полосам частот. Этот факт следует из выпуклости средней взаимной информации /(Х;У) [5,10]. Если на множестве сообщений X задано несколько распределений вероятностей р, г = 1,...,л, то линейная комбинация р этих распределений также является распределением вероятностей на множестве X : где р, - вектор распределения вероятностей с номером г, а1 - коэффициент соответствующий г -му распределению вероятностей. Итак, имеется несколько распределений вероятности р; / = 1 ,...,п на множестве X. Для дальнейшего изложения материала необходимо ввести множество Z = {,...,n}, элементами которого являются номера распределений с вероятностями появления р, (г) = а1. Линейная комбинация р, задаваемая выражением (2.15), является распределением вероятностей, учитывающим вероятности появления элементов множества X. Тогда, процесс выбора величины из множества X с множеством распределений вероятности р; соответствует следующему правилу. Сначала в соответствии с вероятностью р(г) выбирается один из элементов множества Т . Затем, в соответствии с выбранным элементом г выбирается одно из распределений р(. на множестве X. В соответствии с полученным распределением порождается величина х из множества X. Тогда для полученного распределения вероятностей средняя взаимная информация должна учитывать, что элемент из множества X порождается при условии множества X : Средняя взаимная информация при распределении вероятностей р, получаемом линейной комбинацией (2.15), на множестве X , является безусловной величиной 1(Х\У). В действительности, распределение вероятности р является усредненным распределением на множестве X. Для выявления связи между величинами 1(Х;У и ЦХ\У) нужно рассмотреть взаимную информацию /(У;Х2): Приравнивая правые части уравнений (2.17) и (2.18) , а так же учитывая, что В силу условной независимости X и У величина взаимной информации \ X) = 0. (2.20) Принимая во внимание, что взаимная информация 1{У\2) неотрицательна, от равенства (2.19) можно перейти к неравенству: Учитывая, что функция скорость-искажение источника Н(И) есть минимум средней взаимной информации по всем функциям плотности вероятности /(у I л) из класса функция Фп(1)) (1.14) и взаимная информация 1(Х,У — средняя взаимная информация по всем распределениям р; на множестве X (2.16), выражение (2.20) можно записать как: где #. (ТУ) - функция скорость-искажение источника для г -го распределения на множестве X, #( ) - функция скорость-искажение источника усредненного распределения на множестве X . Применительно к разбиению спектра на полосы, выражение (2.15) можно интерпретировать следующим образом. Если спектр имеет некоторое усредненное распределение вероятностей р, тогда это распределение можно рассматривать как линейную комбинацию распределений р, , заданных на полосах спектра. В этом случае выражение (2.21) показывает, что функция скорость-искажение источника для спектра с усредненным распределением вероятности р больше или равна среднему значению функции скорость- искажение источника по полосам спектра. Таким образом, разбиение спектра на частотные диапазоны является эффективной техникой при кодировании сигнала. Способ разбиения спектра на полосы может быть произвольным, при этом закономерность (2.21) не изменит своего характера. В некоторых аудио кодеках принимается равномерное распределение полос, при этом все полосы имеют одинаковую длину, но этот вид разбиения не учитывает субъективного восприятия звука. Учет субъективного восприятия звука является существенным инструментом при кодировании сигнала. В предварительной обработке спектральных коэффициентов целесообразно учесть субъективное восприятие звука, используя так называемый абсолютный порог слышимости и шкалу Барка. Шкала Барка - неравномерный закон распределения длин полос. Выражение (1.4) определяет соотношение между частотой в Герцах и частотой в Барках. Самым важным достоинством полос Барка, по сравнению с полосами равной длины, является согласованность между субъективным восприятием частотных диапазонов и длинами полос шкалы. Разбиение частотного спектра на полосы с использованием шкалы Барка позволяет выделить диапазоны частот, в пределах которых звучание частоты заданной амплитуды воспринимается субъективно одинаково при изменении ее положения от левой до правой границы полосы. Как отмечалось в первой главе, ширина спектра выбирается из условия стационарности сигнала по времени. Отметим, по частоте кодируемый сигнал нельзя рассматривать как стационарный. Поскольку цель шкалы Барка - выделить диапазоны частот, на которых звучание сигнала субъективно одинаково, разбиение спектра на полосы с использованием шкалы Барка можно рассматривать как разбиение одного нестационарного источника на несколько кусочно-стационарных источников. Использование принципов субъективного восприятия. Абсолютный порог слышимости позволяет выделить коэффициенты спектра, которые не важны с точки зрения субъективного восприятия. Важность или неважность отдельной частоты спектра определяется по соотношению энергии коэффициента спектра и абсолютного порога. Энергия отдельного коэффициента спектра вычисляется по формуле (1.6), а значение абсолютного порога слышимости на этой частоте определяется выражением (1.5). Если энергия коэффициента спектра оказалась меньше значения абсолютного порога, то коэффициент считается не важным с точки зрения субъективного восприятия. Следует отметить, что выделение отдельных коэффициентов спектра, с помощью абсолютного порога слышимости, является не очень эффективной техникой кодирования, поскольку для этого требуется высокая разрешающая способность анализируемого кадра по частоте. В том случае, если высокая разрешающая способность не гарантирована, то используется приближение абсолютного порога по полосам. Таким образом, для каждой полосы имеется одно значение порога, в качестве которого выступает минимальное значение абсолютного порога (1.5) слышимости в рассматриваемой полосе: Описанные в этом разделе результаты экспериментов и кривые, отраженные на рис. 2.19, позволяют сделать следующие выводы: При одном и том же виде разбиения спектра на полосы и постоянной длине кадра во времени, выгоднее использовать кадры как можно большей длины. Адаптивное изменение длины кадра показывает уменьшение средних битовых затрат на скоростях от 0,5 бита на отсчет и выше. На скоростях меньших 0,5 изменение длины кадра дает несущественные выигрыш по битам, как видно на рис. 2.19. Использование полос Барка вместо полос равной длины уместно при скорости кодирования не менее 1 бит на отсчет, в противном случае средние битовые затраты совпадают с равномерным распределением полос при той же длине кадра. Использование абсолютного порога слышимости оказалось эффективной техникой для уменьшения битовых затрат за счет более грубой передачи частотных диапазонов, которые считаются неслышными с субъективной точки зрения. Эффективность использования абсолютного порога слышимости уменьшается на низких скоростях кодирования. Применение анализа на шумность для диапазонов частот позволяет уменьшить битовые затраты за счет более грубой передачи диапазонов частот, которые являются шумовыми. Эффективность использования анализа на шумность убывает с уменьшением скорости кодирования. Считается, что при сжатии исходного звукового фрагмента с частотой дискретизации 48000 приблизительно до 64 кбит/с (1,33 бита на отсчет) качество звука можно считать удовлетворительным. После применения всех этапов предварительно обработки спектральных коэффициентов (см. рис. 2.19) и кодировании с качеством в 30 дБ (удовлетворительное качество) необходимо менее 1 бит на отсчет, что свидетельствует о существенном повышении эффективности кодирования при применении предварительной спектральной обработки. 2.5. Результаты и выводы В качестве основных результатов главы отметим следующие: Разработана методика оценивания функции скорость-искажение и ее применения в качестве информационной характеристики потока. Показано влияние предварительной обработки спектральных коэффициентов на информационную характеристику потока аудио данных. Показано, что в качестве модели одномерного распределения может быть выбрано обобщенное гауссово распределение с параметрами а и т. На основе предложенной модели сигнала показана возможность эффективного кодирования спектральных коэффициентов со скоростью менее 1 бит на отсчет. Описанные в этой главе результаты расчетов и моделирования позволяют сделать следующие выводы: Предварительная обработка спектральных коэффициентов позволяет уменьшить битовые затраты на представление кодируемого сигнала, с помощью разбиения спектр сигнала на полосы. Наибольший эффект вносит обработка, учитывающая абсолютный порог слышимости. Использование абсолютного порога слышимости позволяет исключить из рассмотрения полосы спектра с малым уровнем звукового давления. Шкала Барка позволяет задать закон разбиения спектра на полосы с учетом особенностей субъективного восприятия. Использования шкалы Барка оправдано при скоростях выше 1 бит на отсчет. Построение модели одномерного распределения заключается в оценке параметров распределения. Если моделью является обобщенное гауссово распределение, то в качестве определяемых параметров выступают а и а. Адаптивное изменение длины кадра обеспечивает уменьшение средних битовых затрат при скоростях от 0,5 бита на отсчет и выше. Известно, что равномерное скалярное квантование не является оптимальным. Существует несколько подходов к построению неравномерного квантования. Минимальная ошибка при заданном количестве квантов обеспечивается при использовании процедуры оптимизации Ллойда-Макса [40,44]. Минимальная ошибка при заданной энтропии достигается с помощью квантователя ECSQ (Entropy Constrained Scalar Quantization) [21,27,45]. Основной недостаток ECSQ - высокая сложность построения шкалы квантования и самой операции квантования, поэтому этот вид квантования не будет рассматриваться. Подробный обзор результатов в области скалярного квантования приведен в работах [22,31]. В данной главе рассматривается еще один подход к построению неравномерного скалярного квантования [12]. Его важным преимуществом является то, что номера квантов и аппроксимирующие значения вычисляются практически с той же сложностью, что и для равномерного скалярного квантования. Важной особенностью рассматриваемого класса квантователей является малое число параметров, требуемых для их описания. Это свойство имеет большое значение в тех случаях, когда требуется подстройка квантования к изменениям статистических свойств источника. В этом разделе будет дано формальное определение информационной характеристики скалярного квантования, позволяющей сравнивать различные способы скалярного квантования. В разделе 1.2.2 приводилось определение скалярного квантования, как замены значения х величины X ближайшим значением у из некоторого дискретного множества значений У = {у1,...,ум }, мощность которого определяется числом квантов М . Скорость квантования может быть выражена через количество квантов как 7? = М бит на отсчет. Зависимость скорости от числа квантов не позволяет дать объективную оценку способа квантования, потому что не учитывает неравномерность распределения вероятностей квантов. Из теории кодирования источников без потерь известно, что при использовании кодов переменной длины (например, при использовании арифметического кодирования) скорость кода источника с вероятностями символов {р(} )} может быть сделана сколь угодно близкой к Н{У). Следовательно, для того, чтобы учесть распределение вероятностей квантов необходимо оценить энтропию способа квантования: Детальное рассмотрение описанного подхода к вычислению перцептуальной энтропии позволяет сделать несколько выводов. Выражение (4.12) определяет зависимость шага квантования от величины минимального значения маскирующего порога в полосе исключительно для равномерного скалярного квантования. Это означает, что перцептуальная энтропия, подсчитанная с помощью формулы (4.16), также определена исключительно для равномерного скалярного квантования. Отметим, что формула (4.12) и для равномерного скалярного квантования не точна. Она дает некоторое приближение, основанное на равномерности распределения величин, попадающих в квант. Это предположение позволяет получить хорошее приближение только на высокой скорости кодирования. На сегодняшний день актуальна проблема передачи аудио сигнала на низкой скорости при хорошем качестве звука. Описанный выше подход не учитывает неравномерность распределения входных данных, что может привести к существенным промахам на экспоненциальных распределениях для низких скоростей. Результаты моделирования, приведенные во второй главе, показывают, что обобщенное гауссово распределение с достаточно маленькими параметрами а 1.0 может выступать в качестве модели распределения входных данных. Напомним, для небольших значений параметров осе [0.1,0.5] распределения характеризуются большей вероятностью «хвостов» (значений, далеких от математического ожидания), чем для экспоненциального распределения. В третьей главе было предложено адаптивное скалярное квантование данных на основе анализа распределения входных данных, эффективность которого гораздо выше эффективности равномерного скалярного для диапазона низких скоростей (менее 2 бит на отчет). Процесс квантования сопровождается внесением ошибки, величина которой зависит от параметров квантователя. В мультимедиа приложениях очень часто можно видеть ситуацию, когда данные квантуются с разной ошибкой. Например, в аудио кодеке сигнал разделяется на полосы, для которых используется разный уровень качества квантования. Как правило, ошибка квантования определяется моделью субъективного восприятия. На сегодняшний день большая часть приложений сжатия информации использует фиксированную целевую скорость кодирования, что накладывает ограничение на количество бит, отведенных для представления сигнала в заданном промежутке времени (обычно информация кодируется блоками или кадрами). Таким образом, при фиксированной целевой скорости кодирования актуальна задача распределения бит между полосами спектра. В аудио кодеках перцептуальная энтропия выполняет распределение бит между участками спектра сигнала на основе модели субъективного восприятия и функции скорость-искажение. Информационная характеристика R(D) зависит от выбранного способа квантования и на сегодня не имеет точного аналитического выражения. Для расчета перцептуальной энтропии в стандарте MPEG используется аппроксимация R(D). Отметим, что управление ошибкой квантования косвенно решает задачу распределения бит, поскольку уровень качества определяет количество бит, необходимых для представления сигнала. Под управлением квантованием будем понимать определение параметров квантователя, которые позволяют обеспечить заданный уровень ошибки D. В этом разделе рассматривается аппроксимация функции скорость-искажение и способ определения параметров квантования для заданной ошибки D в общем случае. Общий подход к оценке скорости кодирования и вычислению параметров квантования заключается в анализе информации о функции скорость-искажение, полученной моделированием. Рассмотрим возможные способы оценки скорости кодирования R по заданной ошибке D. Одной из возможностей является хранение функции по точкам. Конечно, невозможно сохранить все точки кривой R(D) для всех возможных вариантов ошибки, даже если рассматривать только нормированные выборки данных с нулевым математическим ожиданием и единичной дисперсией. Поэтому требуется интерполяция значений функции. Функция скорость-искажение на рис. 4.6 построена для тестовой выборки с обобщенным гауссовым распределением при параметре а = 0.25. Функцию скорость- искажение, показанную на рис. 4.6, возможно аппроксимировать двумя способами. Первый способ заключается в определении оценки /?(/)) для всего диапазона скоростей. Этот подход предполагает проведение регрессионного анализа на предмет выявления полиномиальной зависимости скорости от ошибки. Практические результаты показывают необходимость построения полиномов высокой степени, что достаточно затруднительно.
Классификация методов квантования
Методы вычисления функции скорость-искажение источника данных
Скалярное квантование с расширенной нулевой зоной
Определение параметров скалярного квантования с расширенной нулевой зоной
Похожие диссертации на Адаптивное скалярное квантование спектральных коэффициентов для систем сжатия аудио сигналов
