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

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

Само ДКП выглядит следующим образом:

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

В результате имеем:

Начальное изображение поддается смещению уровня яркости так, чтобы значения яркости были симметричны относительно 0. Для изображений, содержащих 256 цветов, данная процедура совершается путем отнимания от значений яркости пикселей 128.

Например, нам нужно сжать следующий фрагмент изображения:

Вот формула, по которой приводится ДКП: RES * IMG * DCT

Для начала надо рассчитать промежуточную матрицу: TMP = IMG * DCT

Потом умножаем ее на ДКП матрицу: RES = TMP * DCT

Этап квантования

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

for i:=0 to 8 do

for j:=0 to 8 do 

Q[i,j] = 1+((1+i+j)*q);

Где q – коэффициент качества, от него зависит степень потери качества сжатого изображения. Для q = 2 имеем матрицу квантования:

Теперь надо каждое число в матрице квантования разделить на число в соответствующей позиции в матрице RES, в результате получим:

Как видим, тут достаточно много нулей, мы получаем наиболее длинную последовательность нулей, если будем использовать алгоритм зигзагообразного обхода блока:

Таблица 13. Зигзагообразный обход блока

Итак, мы получили последовательность:

30 0 -7 -11 8 0 0 1 6 -5 -7 -3 0 1 0 0 0 1 0 -3 -4 -1 4 2 0 0 0 0 0 0 0 0 0 0 0 -3 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Этап вторичного сжатия

Наиболее распространенным методом вторичного сжатия является метод Хаффмана и его разновидности.

Восстановление изображения, сжатого с помощью алгоритма JPEG.

При распаковке изображения выполняется обратная последовательность шагов:

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

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

3. Выполняется обратное дискретное косинусное преобразование, которое восстанавливает первоначальный массив пикселей.

JPEG без потерь

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

сжатия около 2:1, что значительно меньше, чем коэффициенты, которые могут быть достигнуты в методах, основанных на ДКП.

Одно из отличий: обрабатывается все изображение, а не блок размера 8х8. При сканировании изображения каждое значение пикселя заменяется значением: Результат = Пиксель - Прогноз

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

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

рис. 13 Размещение пикселей

Возможны следующие режимы кодирования:

табл. 14 Режимы кодирования

              Как видно из рисунка и таблицы, алгоритм сжатия без потерь может быть настроен для любой комбинации предыдущих точек. В режимах с 1 по 3 используются одномерные прогнозы. В режимах с 4 по 7 – двумерные. Какие из них задействуются, зависит от реализации и положения пикселя, что кодируется.

              В любом случае задействуются следующие правила:

              1. Значение прогноза для левого верхнего пикселя равно 2^(P - 1), где P – глубина цвета исходного изображения.

              2. Для других точек верхнего ряда прогноз основывается на значении левого соседа (режим 1).

              3. Для других точек левого столбца прогноз основывается на значении соседа сверху (режим 3).

Основы сжатия изображений

Основные задачи, решаемые при цифровой обработке изображений: Пример кодирования JPEG

DCT-матрица для блока 8х8 пикселей

Начальное изображение:

Изображение после смещения яркости:

Матрица IMG * DCT

Результирующая матрица ДКП:

Матрица квантования для q = 2:

Результат квантования:

Результат обхода:

30 0 -7 -11 8 0 0 1 6 -5 -7 -3 0 1 0 0 0 1 0 -3 -4 -1 4 2 0 0 0 0 0 0 0 0 0 0 0 -3 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Обратное ДКП:

Принцип превращения матрицы изображения в JPEGбез потерь:

Результат = Пиксель – Прогноз

ОБРАБОТКА ЗВУКОВЫХ СИГНАЛОВ

Звуковая информация представляется в цифровом виде в двух принципиально разных формах – WAVE и MIDI.

WAVE – форма используется для цифровых аудиодисков, а MIDI - в электронных музыкальных инструментах.

WAVE-форма звука

WAVE-форма звука получается при оцифровке, или дискретизации, непрерывной звуковой волны (англ. wave – волна), точнее, аналогового аудиосигнала. При оцифровке специальное устройство – аналого-цифровой преобразователь (АЦП) – измеряет амплитуду волны через равные промежутки времени со скоростью несколько тысяч измерений в секунду и запоминает в Wave-файл измеренные значения. Они называются выборками (по англ. sample, откуда еще одно название дискретизации – сэмплинг). Обратное преобразование WAVE-формы звука в аналоговый сигнал осуществляется цифро-аналоговым преобразователем (ЦАП).

На рис. 14 представлена фонограмма первых 10 секунд 40-й симфонии Моцарта, содержащий 2 205 000 выборок. Если на вашем компьютере установлена звуковая плата, вы сможете ее прослушать, щелкнув мышью на картинке. На рис. 15 показан фрагмент записи, содержащий только 50 выборок, начиная с места, отмеченного на рис. 14 вертикальной чертой.

рис. 14 Фонограмма первых 10 секунд 40-ой симфонии Моцарта

рис. 14 Фонограмма симфонии Моцарта

WAVE-форма цифрового звука характеризуется пятью параметрами:

· Частотой дискретизации,

· Разрядностью выборок,

· Количеством каналов или звуковых дорожек,

· Алгоритмом компрессии/декомпрессии – кодеком,

· Форматом хранения.

Чистота дискретизации

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

Под квантованием понимают преобразование непрерывной по значениям величины в величину с дискретной шкалой значений из конечного множества разрешенных, которые называют уровнями квантования. Сущность квантования состоит в округлении мгновенных значений входной функции до ближайших значений уровней квантования. Если уровни квантования нумерованы, то результатом преобразования является число, которое может быть выражено в любой числовой системе. Количество выборок в секунду называется частотой дискретизации и измеряется в герцах и килогерцах (1 кГц=1000 выборок в сек.). При определении количества выборок следует учитывать, что чем меньше интервал между отсчетами (выборками) dt, тем больше будет частота дискретизации и сигнал будет описан точнее. С другой стороны, для обработки такого сигнала будет нужен больший объем памяти, большие ресурсы процессора, больше времени. Поэтому для определения оптимальной частоты дискретизации пользуются теоремой Котельникова (Котельникова - Найквиста).

Теорема гласит: Если непрерывный сигнал x(t), который существует на всей числовой оси и имеет ограниченный спектр [- w, w] заменить отсчетами с минимальным шагом dt=pi/Wm=1/2Fm, то по этой множественном числе отсчетов возможно безошибочное восстановление сигнала x(t).

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

рис. 16 Определение оптимальной частоты дискретизации

Таким образом, для качественного воспроизведения самого звука 20 кГц, что возможно услышать, нужна частота дискретизации не менее 40 кГц. Стандарт CD - DA цифровых аудиодисков требует частоты дискретизации 44,1 кГц (так называемое CD-качество). Используются также частоты 22,05 (радио - качество) и 11,025 и 8 кГц (телефонное качество), что во многих случаях дают удовлетворительные результаты (например, для записи речи). Звук является сложным сигналом, но, как и любой другой сигнал, он может быть представлен с помощью ряда Фурье в виде суммы постоянных составляющих, а также синусов и косинусов, то есть гармонических сигналов (или гармоник).

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

рис. 17 Появление низкочастотных помех

Поэтому для получения качественного цифрового звука процесс дискретизации строится по следующей схеме:

• частичное подавление высокочастотных помех в аналоговом сигнале с помощью аналогового фильтра;

• оверсэмплинг – дискретизация с частотой, что значительно превышает требуемую (при этом шум, что образуется, все еще лежит в нечутному диапазоне);

• подавление высокочастотного шума в цифровом звуке с помощью цифрового фильтра;

• преобразование до требуемой частоты дискретизации.

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

Разрядность выборки

Измеренная амплитуда (выборка) превратится в целое число с некоторой погрешностью, которая определяется разрядностью этого числа. Это преобразование в числа с заданной разрядностью называется квантованием. Погрешность при квантовании вносит шум тем больше, чем меньше разрядность. Теоретически, при n-разрядном квантовании отношение сигнал/шум (динамический диапазон) будет 6n дБ. Таким образом, при 8-разрядном оцифровке динамический диапазон 48 дБ (качество УКВ-радио, достаточная для языка), а при 16-разрядной оцифровке он равен 96 дБ и практически покрывает весь нормально слышимый диапазон. Другими словами, при 8-разрядном кодировании различаются 256 уровней громкости, а при 16-разрядном – 65536, что дает более точную запись. На CD-DA применяется 16-разрядное квантование. Звуковые платы компьютеров обычно используют 8 и 16-разрядное квантование. Применение оверсэмплинга в АЦП и ЦАП позволяет значительно уменьшить шум, который добавляется при квантовании.

Каналы

Обычные звуковые платы позволяют использовать 1 или 2 звуковых канала (дорожки) WAVE-звука – "моно" и "стерео". Оба канала обрабатываются отдельно по одним и тем же алгоритмам, хоть и одновременно. Поэтому нет принципиальных ограничений на число каналов. Увеличение количества каналов ведет к пропорциональному увеличению объема памяти, которую занимает звуковая информация.

Основные методы обработки звука: сжатие, аналоговая фильтрация, цифровая фильтрация.

Компрессия звука

Обозначим

• W – объем памяти в байтах для хранения 1 секунды звука в WAVE-форме,

• w – скорость потока звуковых данных в WAVE-форме в бит/сек,

• H – частоту дискретизации (число выборок в секунду),

• B– разрядность квантования (число разрядов на выборку),

• C – количество каналов.

Тогда очевидно, что w = H*B*C, если B кратно 8, W = w/8. Итак,

• скорость потока данных CD-качества (H=44100, B=16, C=2) составляет 1 411 200 бит/сек или 1378,125 Кбит/сек (такая скорость обеспечивается только CD

-дисководом с не менее, чем 2-кратной скоростью),

• 1 час звука с качеством CD-DA нуждается 605,6 Мбайт (поэтому на аудиодиске помещается около 70 минут несжатого звука),

• скорость потока данных телефонного качества (H=8000, B=8, C=1) составляет 64000 бит/сек или 62,5 Кбит/сек (такая скорость обеспечивается далеко не каждым модемом, поэтому такой звук не может использоваться в Интернет - телефонии).

С целью уменьшения объема и потока звуковых данных в WAVE-форме используются различные специальные алгоритмы компрессии/декомпрессии (кодеки), поскольку обычные алгоритмы сжатия информации здесь не дают эффекта. Сжатие аудиоданных возможно лишь с некоторой потерей информации, но учет психофизиологических особенностей восприятия звука (например, не все частоты в слышимом диапазоне существенные для восприятия), позволяет в ряде случаев сделать эти потери практически незаметны. Однако следует учитывать очень высокую чувствительность человеческого слухового аппарата, особенно временных характеристик звука. Наиболее известными являются следующие кодеки, которые используются в мультимедиа под Windows:

• PCM (PulseCodeModulation) – импульсно-кодовая модуляция (ИКМ) – сжатие может достигаться только за счет выбора меньших значений величин H, B и C (фактически, это несжатая звук); квантование происходит по равномерной шкале из 2B значений;

• DPCM (DifferentialPCM) – дифференциальная ИКМ (ДИКМ) – выборка представляет разницу от предыдущей, что требует меньше B битов; сжимает в несколько раз;

• ADPCM (AdaptiveDPCM) – адаптивная ДИКМ (АДИКМ) – то же, что ДИКМ, только квантование происходит не по равномерной шкале, а с учетом динамики изменений амплитуды; сжимает в несколько раз;

• MPEG (MotionPictureExpertsGroup) – стандарты Группы экспертов в области кино; для сжатия звуковой информации используются стандарты MP2 и MP3; применяется психоакустическая компрессия, при которой удаляются звуки, не воспринимаемые человеческим ухом; сжимает в несколько десятков раз при достаточно высоком качестве;

• RealAudio – метод, разработанный фирмой RealNetworks, сжимает в несколько десятков раз, но с невысоким качеством; используется в Интернете для проигрывания звуковых файлов в реальном времени.

Для цифровой телефонии используются, как правило, другие кодеки.

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

Периодичность гармонических колебаний исследовал еще в VI веке до нашей эры Пифагор и даже распространил ее на описание гармонического движения небесных тел. Термин «spectrum» («спектр») впервые применил И. Ньютон в 1571 году при описании разложения солнечного света, пропущенного через стеклянную призму, на многоцветную полосу. Он же дал и первое математическое трактовку периодичности волновых движений. В 18-м веке решениями волновых уравнений (в приложении к струнам) занимались Даниил Бернулли и Леонард Эйлер. По сути, уже Бернулли и Эйлера показали, что произвольные периодические функции представляют собой суммы простейших гармонических функций – синусов и косинусов кратных частот. Эти суммы получили название рядов Фурье, после того, как в 1807 году французский инженер Жан Батист Фурье обосновал метод вычисления коэффициентов тригонометрического ряда, которым можно показать с абсолютной точностью (при бесконечном количестве членов ряда) или аппроксимировать с заданной точностью (при ограниченном количестве членов ряда) любую периодическую функцию, определенную на интервале одного периода T = b - a, и что удовлетворяет условиям Дирехле (ограниченная, кусочно-непрерывная, с конечным числом разрывов 1-го рода).

А если быть точнее:

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

В качестве базисных функций разложения сигналов, в общем случае, принимаются комплексные экспоненциальные функции exp(jft), от которых с использованием формул Эйлера можно перейти к вещественным синус – косинусных функций. Термин «частотная» обязан происхождением обратная переменной f = 1/|t| временного представления сигналов и функций. Понятие частотного преобразования не следует связывать только с временными аргументами, поскольку математический аппарат преобразования не зависит от физического смысла независимых переменных. Так, например, при переменной "х", как единице длины, значение f будет пространственной частотой с размерностью 1/|х – число периодических изменений сигнала на единице длины.

В математическом аппарате частотного анализа удобно использовать угловую частоту ω = 2πf. Для процессов с другими независимыми переменными в технической литературе вместо индекса частоты f часто используется индекс v, а для угловой частоты индекс k = 2πv, который называют волновым числом.

РАЗЛОЖЕНИЕ СИГНАЛОВ ПО ГАРМОНИЧЕСКИМ ФУНКЦИЯМ