Банк фильтров анализа (Analysis Filter Bank).

Банк фильтров синтеза (Synthesis Filter Bank):

Система анализа-синтеза (А-С) – совокупность банка фильтров анализа и банка фильтров синтеза. Сигнал вначале декомпозируется на субполосы, в каждой из них выполняется некоторая его обработка и, затем, выполняется синтез сигнала (реконструкция). Надо отметить, что иногда нужен обратный порядок операций: сначала синтез, потом анализ. Такая последовательность действий встречается при использовании банков фильтров в связи. При этом НЧ сигналы от разных источников интерполируются, фильтруются, объединяются и передаются по каналу связи. На приеме групповой сигнал подается на схему анализа для выделения сигналов отдельных абонентов. Такая схема, называется трансмультиплексором.

Lazy («ленивый») банк фильтров – система А-С без фильтров. Применяется при доказательстве теорем в банках фильтров.

Элайзинг (Aliasing) – наложение спектра, то есть два сигнала накладываются один на другой.

Устранение элайзинга (Alias Cancellation). Выходной будет свободен от элайзинговой составляющей.

ВЕЙВЛЕТЫ И ВЕЙВЛЕТ-ПРЕОБРАЗОВАНИЕ.

Вейвлеты - это математические функции, обладающие некоторыми свойствами. В научном сообществе до сих пор не решен вопрос, какие функции относить к вейвлетам. В узком смысле это семейство функций, получающихся путем масштабирования и сдвигов одной, материнской функции. Именно за счет изменения масштабов вейвлеты способны выявить особенности сигнала на разных шкалах, а за счет сдвигов они способны пронализировать сигнал во всех точках. В широком смысле вейвлеты - это функции, обладающие хорошей частотно-временной локализацией, чье среднее значение равно нулю. При этом они могут вовсе не иметь функции-прототипа (например, вейвлеты второго поколения, названные так В.Свелденсом). В математических кругах вейвлеты назывались одно время всплесками, но сейчас этот термин встречается редко. В приложениях чаще всего используют дискретные вейвлеты, так как непрерывные вейвлеты не образуют ортонормированного базиса и бесконечно протяжены (имеют экспоненциальный спад). С другой стороны, применение непрерывного вейвлет-анализа позволяет лучше визуализовать результаты анализа (получить более «красивые картинки») и, возможно, выявить какие-то скрытые от других видов анализа свойства сигнала. Хотя я бы лично рекомендовал использовать для анализа сигналов частотно-временные разложения Вигнера и им подобные - там, где скорость анализа не имеет первостепенной важности. Рассмотрим основные термины, использующиеся в этой области. При этом надо учесть, что если англоязычные термины являются устоявшимися, то этого нельзя сказать о русских терминах. Даже перевод и издание «библии вейвлетов» - книги И.Добеши «Десять лекций по вейвлетам» - не исправил до конца положения. Так, по мнению одного из авторитетов в этой области - Л.Левковича-Маслюка - перевод терминологии (в редакции проф. А.Петухова) выполнен неудачно. Что ж, сколько людей - столько мнений.

Непрерывное (Continuos) вейвлет-преобразование (CWT). Под CWT функции понимается разложение по всем возможным сдвигам и сжатиям некоторой функции (порождающего вейвлета).

Вейвлет-ряды (Ортогональное дискретное (диадное) вейвлет- преобразование). В этом случае рассматриваются не все сдвиги и растяжения базисной функции, но только взятые на некоторой дискретной сетке (обычно логарифмической). Заметьте, что если сигнал остается непрерывным, то называть это преобразование дискретным неверно и приводит к путанице. Иногда его называют диадным. Мне кажется (и не только мне), что лучше называть это преобразование рядами вейвлетов непрерывного времени (CTWS) по аналогии с рядами Фурье. Если же сигнал - дискретный, то аналогичное преобразование правильно называть дискретным вейвлет-преобразованием. Формулами вычисления прямого ДВП является, по сути, масштабирующее уравнение (см. ниже) для вейвлет- функции и для масштабирующей функции. Обратное ДВП всегда существует.

Кратномасштабный (многомасштабный) анализ (КМА) - Multiresolution Analysis (MRA) - математическая конструкция, схема представления сигналов. Эта конструкция позволяет «с другой стороны» зайти к построению вейвлет-рядов и заключается в представлении пространства в виде бесконечной последовательности вложенных подпространств, являющихся отмасштабированными версиями друг друга и связанных определенными свойствами. Различают ортогональный и биортогональный КМА. Значение КМА заключается также и в том, что при его помощи мы можем дать более точные определения масштабирующей и вейвлет функциям, а также найти связь между ними.

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

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

Быстрое вейвлет-преобразование (Fast Wavelet Transform) - пирамида Малла (Mallat). Входной сигнал подается на пару фильтров- дециматоров. Выход ВЧ фильтра-дециматора считается коэффициентами, а выход НЧ фильтра поступает на точно такую же схему (то есть в алгоритме выполняется итерация по НЧ каналу). Сложность - не более 2LN, где L - длина фильтра, N - длина сигнала. В самом деле, на первом уровне сложность выполнения фильтрации LN, на втором - LN/2 и т.д.; сумма последовательности 1+1/2+1/4+... сходится к 2.

Маска (Mask) - в литературе по аппроксимации так называется вектор, в ЦОС называющийся вектором коэффициентов фильтра.

Масштабограмма (Scalogram) - квадрат амплитуды коэффициентов непрерывного вейвлет-преобразования. Изображается обычно на плоскости. По оси абсцисс откладывается, например, время, а по оси ординат - масштабы, на которых сигнал анализировался. Масштабограмма аналогична спектрограмме, построенной при спектральном анализе с постоянной относительной полосой (constant-Q). Под спекттрограммой понимается квадрат амплитуды коэффициентов оконного преобразования Фурье.

Гладкость (Smoothness) - параметр, ограничивающий сверху число производных функции. Различные вейвлет-фильтры обладают различной гладкостью (то есть, конечно, гладкостью обладают функции, получаемые в пределе при бесконечном числе итераций пирамиды Малла) Например, считается что сигнал изображения имеет гладкость 1,5-2. Поэтому, для его анализа, сжатия можно применять вейвлет-фильтры соответствующей или большей гладкости. Как правило, чем больше коэффициентов у вейвлет-фильтра, тем больше гладкость соответствующей ему функции.

Симметрия (антисимметрия) базисных функций - симметрия означает, что если перенести центр функции в начало координат, то функция будет четной. Антисимметрия означает, что функция после переноса будет нечетной.

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

Вейвлет-пакеты (Wavelet Packet). Если в пирамиде Малла выполнять разложения не только по НЧ, но и по ВЧ каналу, то в конечном счете мы получим дерево базисов, аналогичное получаемому при выполнении быстрого преобразования Фурье. Это множество базисов и называется вейвлет-пакетами. Функции вейвлет-пакетов ортогональны между собой на каждом уровне, а также и между уровнями.

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

Лифтинговая (Lifting) схема вычисления вейвлет-преобразования. Альтернативный пирамиде Малла способ быстрого вычисления ВП. По некоторым оценкам снижает вычислительную стоимость в два раза, позволяет экономить память и конструировать вейвлеты, которые другим способом не построить (вейвлеты второго поколения). Лифтинговая схема состоит из трех звеньев: разбиения, предсказания и обновления.

Целочисленное (Integer) вейвлет -преобразование - применяется в двух смыслах: 1)использование целочисленных фильтров; 2)получение целых значений коэффициентов преобразования целочисленного сигнала. В первом случае повышается скорость вычислений, во втором случае появляется возможность выполнения преобразования без потерь.

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

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

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

СТЕГАНОГРАФИЯ

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

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

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

Стегосообщение – скрываемое сообщение.

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

СЖАТИЕ ИЗОБРАЖЕНИЙ

Сжатие изображений (Image compression) – сокращение объема их цифрового представления. Под изображением понимается прямоугольная матрица, элементы которой обычно принимают значения (0..28-1) (полутоновые изображения), (0..224-1) (цветные изображения), (0,1) (бинарные изображения). Цветные изображения могут быть в RGB-формате (по 8 бит на канал), YCH- формате (яркостная и две цветоразностные составляющие), а также и в других форматах. Как правило, большинство алгоритмов сжатия разрабатываются для полутоновых изображений (256 градаций серого). Это связано с тем, что такие алгоритмы легко обобщить на случай цветного изображения. Различают сжатие без потерь и с потерями.

Сжатие без потерь (lossless compression) – восстановленное после сжатия изображение полностью идентично исходному («бит в бит»). То есть при сжатии используется только статистическая избыточность, имеющаяся в изображении. Ее используют так называемые энтропийные кодеры (Хаффмана, арифметический). Понятно, что таким образом большого коэффициента сжатия достичь нельзя (обычно, коэффициент сжатия не более 1.5-2). Сжатие без потерь находит ограниченное применение в некоторых областях, например, медицине или астрономии. Алгоритмы сжатия JPEG, JPEG2000 имеют режимы работы без потерь. Иногда рассматривается сжатие «почти без потерь», то есть с незаметными для человека потерями. При этом достигаются коэффициенты сжатия порядка (6..10). Для сжатия изображений без потерь находит применение целочисленное вейвлет-преобразование. Его преимуществом является то, что коэффициенты преобразования - целые числа, поэтому после обратного преобразования можно восстановить изображение «бит в бит». Целочисленное вейвлет-преобразование выполняется для перераспределения энергии исходного изображения, так как в этом случе можно построить более эффективные энтропийные кодеры

Сжатие с потерями (Lossy Compression) - восстановленное изображение визуально мало отличается от исходного. Это различие называется искажением. Говорят, что сжатие с потерями вносит искажение. Мерой искажения может быть визуальное отличие двух изображений. Однако, эта характеристика плохо описывается на языке формул. Поэтому, на практике в качестве меры искажения используется среднеквадратическая ошибка. В среде исследователей не прекращаются споры об адекватности этой меры, однако ничего лучшего по сей день не придумано. Сжатие с потерями выполняется, как правило, в три этапа: линейное преобразование (ДКП, вейвлет), квантование, энтропийное кодирование. Целей первого этапа несколько: перераспределение энергии между отсчетами, декорреляция отсчетов и придание коэффициентам удобной для квантования структуры (например, нульдерева). Квантование бывает скалярное (каждый отсчет в отдельности)и векторное. В качестве энтропийного кодера обычно используется арифметический (более эффективный, но и более вычислительно сложный) или кодер Хаффмана.

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

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

Нульдерев о – одна из наиболее эффективных структур, упорядочивающих множество вейвлет-коэффициентов изображения для целей их сжатия. Заключается в следующем: вейвлет-коэффициенты более НЧ областей «отвечают» за четыре коэффициента более ВЧ областей. Тем, в свою очередь, соответствуют 16 коэффициентов еще более ВЧ областей и т.д. Таким образом, получаем дерево коэффициентов с вершиной в самой НЧ области. Выберем некоторый порог и назовем меньшие этого порога (по абсолютной величине) коэффициенты незначащими. Начиная с самой НЧ области проверяем значимость коэффициентов относительно текущего порога. Если коэффициент незначащий, проверяем его потомков по дереву. Если все потомки незначащие, то на месте коэффициента ставится признак нульдерева. Таким образом одним символом обозначаем большое множество коэффициентов. После «обхода» всех коэффициентов порог уменьшается в два раза, и процесс повторяется. Сжатие на основе нульдерева была впервые предложена Льюисом и Ноулесом (1992) и улучшено в дальнейшем Шапиро (1993) и Саидом-Перельманом (1995).

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

логарифмическое квантование, оптимальное квантование. Оптимальные интервалы квантования находятся с применением процедуры Ллойда-Макса (квантователь Макса).

Векторное квантование – квантуется сразу некоторое множество отсчетов (вектор). Если скалярное квантование одномерный процесс, то векторное - многомерный, то есть гораздо более сложный. Построение оптимального векторного квантователя основано также на применение алгоритма Ллойда- Макса. Сложность кодирования и декодирования намного выше, чем при скалярном квантовании. Поэтому, обычно применяются структурированные методы векторного квантования (то есть кодовой книге придается структура): древовидное, решетчатое, пирамидальное ВК. Древовидный векторный квантователь – кодовые слова упорядочены в виде дерева. Таким образом. сложность поиска по дереву высотой N будет NlogN вместо N^N, как было бы при не структурированной кодовой книге. Проигрыш заключается в неоптимальности найденных кодовых слов. Разновидностью является усеченный древовидный векторный квантователь (PTSVQ), суть которого заключается в следующем. Вначале строится полное дерево, затем оно усекается (аналогично, как в алгоритме вейвлет-пакетов). Таким образом получается адаптивный квантователь.

Решетчатый квантователь – кодовые слова книги расположены в узлах решетки. Каких-то преимуществ по сравнению с древовидным я не знаю. По поводу теории решеток смотрите замечательную книгу Конвэя и Слоэна.

Стандарты на сжатие изображений – сжатие бинарных изображений - JBIG, сжатие полутоновых и цветных - JPEG, JPEG2000. В стандарте JPEG в качестве линейного преобразования используется ДКП, в JPEG2000 - вейвлет- преобразование. На роль стандарта де-факто для сжатия смешанных тексто- графических изображений претендует алгоритм DjVu («дежавю»), основанный на распознавании образов и последующем применении различных алгоритмов к различным типам изображений.

Стандарты на сжатие видео – MPEG-2, MPEG-4 (ДКП и вейвлеты, соответственно), рекомендация МСЭ H.263, H263+ и др. Сжатие видео состоит из двух частей: сжатие неподвижного кадра (во многом аналогично сжатию изображений) и межкадровое кодирование (в основном применяют что-то типа ДИКМ).

 

Рекомендуемая литература

1. Яглом А.М. Корреляционная теория стационарных случайных процессов. Ленинград гидрометеоиздат, 1981 г. – 280 с.

2. Марпл-мл С.Л. Цифровой спектральный анализ и его приложения. М.:Мир, 1990 г., – 584 с., ил.

3. Блейхут Р. Быстрые алгоритмы цифровой обработки сигналов. М.:Мир, 1989 г., – 448 с., ил.

4. Введение в цифровую фильтрацию. Под ред. Р.Богнера, А.Константинидиса. М.:Мир, 1976

5. Отнес Р., Эноксон Л. Прикладной анализ временных рядов. М.:Мир, 1982 г. – 428 с., ил.

6. Бендат Дж., Пирсол А. Прикладной анализ случайных данных М.:Мир, 1989. –540 с.

7. Л.В. Новиков Основы вейвлет–анализа сигналов. Санкт-Петербург, 1999г. – 152 с.

8. Д.У.Тафтс, Р.Кумаресан. Оценка частот суммы нескольких синусоид: Модификация метода линейного предсказания, сравнимая по эффективности с методом максимального правдоподобия.//ТИИЭР, т.70, №9, 1982.С.77-94.

9. Х.Л. Никиас, М.Р.Рагувер Биспектральное оценивание применительно к цифровой обработке сигналов//ТИИР, т.75,N7,1987. С.5-30.

10. С.Н.Кей, С.Л.Марпл Современные методы спектрального анализа. Обзор. //ТИИЭР, т.69, №11, 1981. С.5-51.

11. М.И.Миллер, Д.Л.Снайдер. Роль правдоподобия и энтропии в задачах с неполными данными: Приложения к задачам оценивания интенсивности точечных процессов и условных теплецевых ковариаций.//ТИИЭР, т.75, №7. 1987г. С.31-50.

12. Э.Т.Джейнс. О логическом обосновании методов максимальной энтропиию.//ТИИЭР, т.70, №9. 1982. С.33-51.

13. Д.Дж.Томсон. Спектральное оценивание и гармонический анализ.//ТИИЭР, т.70, №9. 1982г., С.171–219.

14. Д.Дж.Чайлдерс, Д.П.Скиннер, Р.Ч.Кемерейт Кепстр и его применение при обработке данных. Обзор.//ТИИЭР, т.65, №10, 1977. С.5-21.

15. Макс Ж Методы и техника обработки сигналов при физических измерениях. М.:Мир, 1983. Т.1. –312 с.

16. Грибунин В.Г. Глоссарий по цифровой обработке сигналов (предварительная версия) / http://d.theupload.info/down/ yx94bmuhf2ffnek6pg3mnporw9h2p8if/gribunin_v_g__glossarii_po_cifrovoi_obrabotke_signalov.pdf –28с.

 

Примечание: Учебным планом по курсу «Современные методы спектрального оценивания» такие виды работы как подготовка рефератов и курсовых работ, выполнение лабораторных работ, прохождение практики не предусмотрены.