Содержание к диссертации
Введение
Глава 1. Матрицы выбора для дискретных ортогональных преобразований 9
1.1. Постановка задачи 9
1.2. Определение матриц выбора для преобразования Фурье и дискретных тригонометрических преобразований 14
1.3. Матрицы выбора для преобразования Уолша-Адамара, Уолша-Пэли и Уолша 25
1.4. Выводы 35
Глава 2. Регуляризация дискретных ортогональных преобразований 36
2.1. Введение и постановка задачи 36
2.2. Регуляризация дискретного преобразования Фурье с приближенными коэффициентами 38
2.3. Регуляризация дискретного преобразования Уолша 43
2.4. Выводы 48
Глава 3. Оценки погрешностей при сжатии сигналов с регуляризацией 49
3.1. Постановка задачи 49
3.2. Оценка погрешностей для ДПФ и преобразования Хартли .51
3.3. Оценка погрешностей для ДКП, ДСП и ДПУА 58
3.4. Выводы 66
Литература 67
- Определение матриц выбора для преобразования Фурье и дискретных тригонометрических преобразований
- Матрицы выбора для преобразования Уолша-Адамара, Уолша-Пэли и Уолша
- Регуляризация дискретного преобразования Фурье с приближенными коэффициентами
- Оценка погрешностей для ДПФ и преобразования Хартли
Введение к работе
В различных задачах, возникающих в радиометрии, аэрокосмических исследованиях, а также в медицине, биологии и других областях сталкиваются с проблемой сокращения избыточности и эффективного кодирования (сжатия данных), возникающей в связи с переработкой, хранением и передачей огромных потоков информации, представленной в форме цифровых сигналов. Проблемы построения и использования систем сжатия данных тесно связаны с задачами автоматизации научных исследований (АСНИ) [18,19]. При разработке АСНИ сталкиваются с рядом трудностей, как например, требования оперативной обработки данных при ограниченном быстродействии вычислительных устройств или быстрой передачи данных по каналам связи при ограниченной пропускной способности последних. В связи с этим задача сжатия данных, являясь основным средством повышения эффективности АСНИ, приобретает большое практическое значение.
В настоящее время разработано большое количество разнообразных систем сжатия данных. Одними из основных используемых математических методов являются спектральные методы, основанные на вычислении дискретных ортогональных преобразований (ДОП) [1,3,20-24]. Интерес к изучению ДОП в последние годы значительно возрос, что обусловлено, в основном, следующими причинами:
- идея перехода к новым отсчетам достаточно универсальна и может быть применена к широкому кругу как теоретических, так и прикладных задач, например, к обработке речевых сигналов, спектроско-
пий и т.д.;
ортогональные преобразования обладают полезным свойством сохранения энергия, они линейны и легко обратимы;
разработано уже большое количество эффективных алгоритмов вычислений для широкого класса ортогональных преобразований;
имеются значительные достижения в области применения быстродействующих ЭВМ, в технологии цифровых схем и разработке специализированных процессоров.
Сжатие посредством ДОП (или кодирование с преобразованием) было предложено в конце 60-х, начале 70-х годов как эффективный метод сокращения избыточности изображений и базировалось на преобразованиях Фурье, Адамара и Карунена-Лоэва [25-29]. В дальнейшем ортогональные преобразования использовались не только для анализа изображений, отбора признаков при распознавании образов, обобщенной винеровской фильтрации, но и для обработки различной информации, такой как данные биомедицинских исследований, сейсмические, акустические данные и т.п. [1,5,30-34].
Кодирование сигнала с преобразованием существенно отличается от других методов кодирования [5,3,5], которые применяются непосредственно к сигналу. Кодирование с преобразованием - косвенный метод. Сигнал подвергается унитарному преобразованию с дальнейшим отбором спектральных коэффициентов, используемых при решении данной конкретной задачи (процедуры сжатия, фильтрации, выделения признаков производятся в спектральной области).
Выделяются два основных способа отбора спектральных компонент: зональный и пороговый. Зональный отбор состоит в выделении совокупности компонент, занимающих некоторые фиксированные области спектра, а пороговый метод сжатия сохраняет только те спектральные компоненты, величина которых превышает установленный порог. Отметим, что пороговые системы кодирования обеспечивают более правильный выбор передаваемых отсчетов (с точки зрения величины искажений), но они обладают многими недостатками [36], в частности, необходимостью кодирования дополнительной информации об адресах передаваемых отсчетов.
В настоящее время класс ДОП, используемых в цифровой обработке сигналов достаточно широк [1,21,24,37-42]. Однако большинство исследований касается непосредственно алгоритмов преобразования, а не того, что необходимо сделать после преобразования. В [36] отмечено, что наиболее перспективным способом повышения эффективности сжатия является не разработка новых быстрых алгоритмов преобразования, а разработка процедур, следующих за преобразованием. Наряду с преобразованием Фурье все более широкое применение на практике получают вещественные тригонометрические преобразования, преобразования Уолша, Хаара и др. [18,38,39,41,43,44]. В этой связи становится важной также задача отыскания (для заданного класса сигналов) для указанных ДОП эффективных методов зонного кодирования.
Приведем постановку задачи сжатия информации посредством дискретных ортогональных преобразований. Пусть х = (ж0, i, , хп-\)-
исходный вектор данных, F - ортогональная матрица, S - матрица выбора спектральных компонент размерности т х п, 1 < т < п, W -матрица восстановления размерности п х т.
Задача сжатия состоит в выборе F, S и W так, чтобы
p{x,F~lWSFx) -> тгп (1)
где р - некоторая метрика.
Содержательно, задача (1) сводится к следующему. Исходный вектор х размерности п подвергается ортогональному преобразованию F. Затем посредством матрицы выбора S выбираются т отсчетов сигнала в новой системе координат. (Отметим, что эти выбранные отсчеты и предназначены для передачи, хранения и т.д.). Далее производится "экстраполяция" этих отсчетов посредством матрицы W и при помощи обратного преобразования F~l восстанавливается исходный вектор. Величина к = — называется коэффициентом сжатия.
С другой стороны, задача восстановления сжатого сигнала можно рассматриваться как обратная (некорректно поставленная) задача. На самом деле, если даже считать входной сигнал х заданным точно, то вектор у = SFx, подлежащий передаче, является искаженным. Отсюда, естественным образом, возникает задача использования метода регуляризации перед "экстраполяцией" вектора у.
Таким образом, задача сжатия и восстановления сигнала с регуляризацией состоим в выборе операторов /, 5, W и регуляризирующего оператора jR так, чтобы
р(х, f-WRSFx) -> тгп (2)
где р - некоторая метрика. .
Диссертационная работа посвящена исследованию задач (1) и (2).
Работа состоит из трех глав.
Первая глава посвящена задаче определения матриц выбора для дискретных ортогональных преобразований.
В параграфе 1.2 приводятся постановка задачи сжатия и восстановления сигнала, обосновывается важность задачи определения матрицы выбора для различных типов дискретных ортогональных преобразований.
В параграфах 1.2 и 1.3 определены матрицы выбора для дискретного преобразования Фурье, дискретных тригонометрических преобразований (преобразование Хартли, косинусное и синусное преобразование), дискретных преобразований Уолша-Адамара, Уолша-Пэли и Уолша.
Результат первой главы можно сформулировать в виде общего утверждения.
Утверждение 1. При сжатии сигнала необходимо заменять нулями:
центральные компоненты спектра для преобразований Фурье и Хартли;
последние компоненты спектра для ДКП, ДСП, ДПУП, ДПУ;
компонента спектра с номерами 2г-1(2г — 1), г = 1, 2,... , к, і = 1,2,... ,2n_r, для ДПУА, где 2П - длина сигнала, 2к - коэффициент сжатия.
Вторая глава посвящена задаче регуляризации дискретных ортогональных преобразовании с исходными приближенными коэффициентами. Показано, что для ДПФ и дискретного преобразования Уолша, регуляризация спектра коэффициентом вида
т-гЛл+7' 0<а< 1, є>0, к =1,2,... ,п-1.
позволяет произвести устойчивое суммирование рядов Фурье и Уолша.
Третья глава посвящена оценке погрешностей при сжатии сигналов с регуляризацией. Получены оценки погрешностей для ДПФ, преобразований Хартли, ДКП, ДСП и ДПУА с регуляризацией и без регуляризации. Проведено сравнение соответствующих оценок и определены значения регуляризирующего параметра а улучшающего восстановленный сигнал.
Каждая из трех глав завершается параграфом, в котором приводятся основные выводы.
Определение матриц выбора для преобразования Фурье и дискретных тригонометрических преобразований
Проблема сжатия данных в настоящее время приобретает все большую актуальность в связи с необходимостью передачи или хранения огромных и все возрастающих потоков информации при решении ряда прикладных задач. При этом благодаря растущим возможностям современных ЭВМ все более широкое применение в задаче сжатия (а также фильтрации, распознавания образов и др.) находят дискретные ортогональные преобразования [1].
Приведем постановку задачи сжатия информации посредством дискретных ортогональных преобразований исходный вектор данных, рассматриваемый как реализация некоторого случайного процесса, F = (/г,і)Г7=о - ортогональное преобразование, F l - обратное преобразование, S -матрица выбора размерности т х п ранга т, 1 т п, W - матрица восстановления размерности п х т.
Задача сжатия состоит в выборе F, S, W так, чтобы где р - некоторая метрика. Матрицы FQ, So, и WQ, доставляющие указанный минимум, называются соответственно матрицами оптимального базиса, оптимального выбора и оптимального восстановления. Содержательно задача (1.1.1) сводится к следующему. Исходный вектор х размерности п подвергается ортогональному преобразованию F, которое приводит к новой, более удобной системе координат. Затем посредством матрицы выбора S выбираются т отсчетов сигнала в новой системе координат. Отметим, что эти отсчеты и предназначены для передачи, хранения, распознавания и т.д. При необходимости производится "экстраполяция" (восстановление размерности) этих отсчетов посредством матрицы W. Затем посредством обратного ортогонального преобразования восстанавливается исходный сигнал. Отметим, что число к = — называется коэффициентом сжатия. Таким образом задача заключается в отыскании ортогонального дискретного преобразования F, матриц S и W, минимизирующих ошибку восстановления при заданном коэффициенте сжатия к. Замечание 1.1.1. При решении прикладных задач, как правило, рассматривают более простую задачу. А именно, фиксируется преобразование F и берут W = ST. Тогда в (1.1.1) минимизация производится только по 5. В такой постановке задача (1.1.1) известна как задача отыскания оптимального метода зонного кодирования при сжатии данных посредством преобразования F[2.,3,4j. Замечание 1.1.2. Величина р(х, F 1WQSQFQX) называется уровнем ошибки восстановления. Замечание 1.1.3. Пусть S - матрица вида (Д : 0), W = 5Т, р - среднеквадратичный критерий, тогда в выражении (1.1.1) оптимизация производится только по F. В этом случае оптимальным базисом будет базис Карунена-Лоэва [3,5]. Отметим, что базис Карунена-Лоэва приводит к некоррелированным компонентам [6,7], однако требует выполнения большого объема операций - 0(гг3). Алгоритм зонного кодирования при сжатии данных описывается в следующем виде. Пусть х = (XQ,XI,... ,zn_i) - исходный вектор данных из некоторого метрического пространства (X, р), F - ортогональная матрица порядка п. Алгоритм реализуется в три шага. 1. Вектор х подвергается преобразованию F: \Уп-і/ 2. Вектор у заменяется посредством оператора выбора S на меньший по размерности вектор у: который и необходимо передать по каналу связи или хранения и т.д. Отметим, что матрица S размерности v X п имеет вид Величина к = - называется коэффициентом сжатия. 3. На приемном конце полученный вектор у дополняется до размерности п посредством операции 4. Вектор у подвергается обратному преобразованию F 1, т.е. определяется вектор х = F ly которое восстанавливает исходный вектор данных с погрешностью є = р(х}х). Задача состоит в определении оптимального способа зонного кодирования, т.е. такого выбора заменяемых нулями спектральных компонент, который обеспечивает минимум погрешности при заданном /с, т.е. обеспечивает погрешность. Понятно, что целесообразно заменять нулями те компоненты вектора у, которые малы по абсолютной величине и, поэтому вносят меньший вклад при восстановлении исходного вектора. Отметим также, что при разработке алгоритмов быстрого ортогонального преобразования используется внутренняя структура ортогональной матрицы. Именно, ортогональная матрица F разбивается на однотипные блоки, что позволяет организовать параллельные вычисления. По этой причине целесообразно заменять нулями те спектральные компоненты, которые соответствуют целиком блоку или нескольким блокам матрицы F. Более детально остановимся на процессе кодирования и декодирования двумерных сигналов (изображений) посредством ортогональных преобразований.
Матрицы выбора для преобразования Уолша-Адамара, Уолша-Пэли и Уолша
Большое число практических задач можно описать моделью вида где D[-] - искажающий оператор, действующий на входную последовательность х и дающий выходную последовательность у. Эта задача может выглядеть поразному в зависимости от того, что известно и что необходимо определить.
Так, если входной сигнал и искажающий оператор известны, а выходной сигнал необходимо определить, то задача относится к классу задач реализации системы. Если известны вход и выход и необходимо определить искажающий оператор, то задача относится к классу задача идентификации системы. И, наконец, задача, в которой необходимо определить входной сигнал по известному искаженному выходному, известна как обратная задача.
Нетрудно заметить, что задача восстановления сигнала входит в класс обратных задач. На самом деле, если даже считать входной сигнал х заданным точно, то вектор у — SFx подлежащему к передаче является искаженным, т.к. Fx преобразовался посредством матрицы выбора S. На приемном конце переданный сигнал у подвергается "экстраполяции" посредством оператора W. И, рассматривая сигнал WSFx как выходной искаженный сигнал системы типа (2.1.1), заключаем, что действительно задача восстановления сжатого сигнала является обратной задачей.
В цифровой обработке сигналов приходится иметь дело с приближенными данными, и это часто делает невозможным применение традиционных методов решения этих задач. Так, если в качестве приближенного значения суммы ряда Фурье с неточными коэффициентами брать сумму конечного числа его первых членов, то увеличение числа членов может не только не улучшить оценку, но и сильно испортить ее. Такие задачи называются некорректно поставленными.
Примером некорректной задачи является численное суммирование рядов Фурье с приближенными коэффициентами [15]. Из формул (2.1.3) и (2.1.5) следует, что подобающим выбором числа є величину Е\ можно сделать сколь угодно малой, между тем разница \у] —уі\ может быть сколь годно большой. Т.е. небольшая погрешность в исходных данных делает задачу суммирования частичных сумм рядов Фурье неустойчивой.
Сначала исследуем задачу суммирования рядов Фурье с приближенными коэффициентами. Пусть {VA;(0}fcLr полная ортогональная система и пусть непрерывная на отрезке [а, Ь] функция f(t) представлена своим рядом Фурье по этой системе, т.е. Нашей целью является нахождение в классе непрерывных на [а, Ь] функций функции /(), аппроксимирующей функцию f(t) по последовательности {ck} j L1 так чтобы при 6 — 0 pc(f, /) — 0. Заметим, что в качестве f(t) нельзя брать сумму S(t) ряда (2.2.2) п так как такое суммирование, как было показано в предыдущем параграфе, не является устойчивым к малым изменениям коэффициентов. В работе [15] показано, что регуляризацию суммирования ряда Фурье функции с приближенными коэффициентами можно произвести при помощи регуляризирующих множителей вида Следовательно, искомое приближение функции f(t) можно записать в виде Таким образом сумма ряда устойчива к малым, в смысле метрики пространства І2-, изменениям коэффициентов Cfc и при значении а. = У(6) согласованном с погрешностью коэффициентов с , равномерно аппроксимирует функцию f(t). Перейдем теперь к оптимальному выбору регуляризирующего множителя. Из общего вида этого множителя, т.е. из вида видно, что с изменением параметров.о; и А получаем достаточно обширный класс множителей. Естественно, при наличии дополнительной информации о коэффициентах {cfc}, и надлежащем выборе параметров а и А можно решать задачу в определенном смысле оптимального выбора регуляризирующего множителя. Так, пусть {7/с} — {ск ак] являются случайными числами, удовлетворяющими требованиям: - { Ук} есть последовательность попарно некоррелированных случайных чисел; - математические ожидания этих чисел для всех значений к равны нулю. В этих условиях приближенные значения {с&} также являются случайными числами.
Регуляризация дискретного преобразования Фурье с приближенными коэффициентами
Пусть х = (ха,х\,... ,жп_і)- исходный вектор (дискретный сигнал), F - ортогональная матрица, S - матрица выбора спектральных компонент размерности т х п, 1 m тг, W - матрица восстановления размерности п X т.
Сжатие сигналов посредством дискретных ортогональных преобразований производится по следующей схеме:
Исходный вектор х подвергается ортогональному преобразованию. Затем посредством матрицы выбора S выбираются т спектральных компонент вектора у = Fx (получается вектор уст компонентами). Далее, вектор у передается по каналу связи, (рассматриваем бесшумный канал связи) и посредством матрицы W на приемном конце канала производится "экстраполяция" вектора у, т.е. вместо выброшенных компонент вектора у подставляются компоненты с нулевыми значениями и при помощи обратного преобразования F-1 восстанавливается исходный вектор х с точностью p(x,F 1WSFx).
Пусть F - матрица дискретного преобразования Фурье, хг,х2 -исходные сигналы. Тогда в силу равенства Парсеваля и линейности преобразования Фурье, имеем. Теперь если x - исходный сигнал, ах- восстановленный после сжатия сигнал, то имеет место равенство Следовательно, для оценки погрешности при сжатии сигналов достаточно иметь оценку вида Как уже отмечалось в предыдущей главе, если спектр сигнала рассмотреть как исходный сигнал у — Fx, то после сжатия, передачи и экстраполяции этот сигнал отличается от исходного сигнала (спектра), и это отличие можно с некоторой точностью устранить при помощи регуляризации исходного сигнала. Ошибка восстановления с регуляризацией имеет вид где к - коэффициент сжатия, уг- исходный регуляризированный сигнал, уг - соответствующий сжатый сигнал, а - параметр регуляризации. Естественным образом возникает задача нахождения оценки погрешности восстановления исходного сигнала х без регуляризации и с регуляризацией, т.е. сравнение (3.1.3) с где хг - восстановленный сигнал, что согласно (3.1.1) эквивалентно задаче определения р(у,уг). Последующие параграфы этой главы посвящены получению оценок вида (3.1.3)—(3.1.5) для различных дискретных ортогональных преобразований и их сравнению. Пусть х = (жо, !,... ,п_і)- исходный вектор, F - матрица ДПФ порядка п. Через у обозначим вектор, который , получается из вектора у = Fx заменой нулями 2т центральных компонент (т ), т.е. коеффициент сжатия имеет вид к = — —. Подставляя в (3.2.8) и (3.2.9) значения m, m = n%kn , при больших n окончательно находим В этих условиях выше показано, что ошибка восстановления имеет вид (3.2.1) где к = — косффициент сжатия. Как было показано в параграфе 2.3, регуляризацию суммирования ряда Фурье функции с приближенными коэффициентами можно произвести при помощи регуляризирующих множителей вида.
Оценка погрешностей для ДПФ и преобразования Хартли
Сжатие посредством ДОП (или кодирование с преобразованием) было предложено в конце 60-х, начале 70-х годов как эффективный метод сокращения избыточности изображений и базировалось на преобразованиях Фурье, Адамара и Карунена-Лоэва [25-29]. В дальнейшем ортогональные преобразования использовались не только для анализа изображений, отбора признаков при распознавании образов, обобщенной винеровской фильтрации, но и для обработки различной информации, такой как данные биомедицинских исследований, сейсмические, акустические данные и т.п. [1,5,30-34].
Кодирование сигнала с преобразованием существенно отличается от других методов кодирования [5,3,5], которые применяются непосредственно к сигналу. Кодирование с преобразованием - косвенный метод. Сигнал подвергается унитарному преобразованию с дальнейшим отбором спектральных коэффициентов, используемых при решении данной конкретной задачи (процедуры сжатия, фильтрации, выделения признаков производятся в спектральной области). Выделяются два основных способа отбора спектральных компонент: зональный и пороговый. Зональный отбор состоит в выделении совокупности компонент, занимающих некоторые фиксированные области спектра, а пороговый метод сжатия сохраняет только те спектральные компоненты, величина которых превышает установленный порог. Отметим, что пороговые системы кодирования обеспечивают более правильный выбор передаваемых отсчетов (с точки зрения величины искажений), но они обладают многими недостатками [36], в частности, необходимостью кодирования дополнительной информации об адресах передаваемых отсчетов.
В настоящее время класс ДОП, используемых в цифровой обработке сигналов достаточно широк [1,21,24,37-42]. Однако большинство исследований касается непосредственно алгоритмов преобразования, а не того, что необходимо сделать после преобразования. В [36] отмечено, что наиболее перспективным способом повышения эффективности сжатия является не разработка новых быстрых алгоритмов преобразования, а разработка процедур, следующих за преобразованием. Наряду с преобразованием Фурье все более широкое применение на практике получают вещественные тригонометрические преобразования, преобразования Уолша, Хаара и др. [18,38,39,41,43,44]. В этой связи становится важной также задача отыскания (для заданного класса сигналов) для указанных ДОП эффективных методов зонного кодирования.
Приведем постановку задачи сжатия информации посредством дискретных ортогональных преобразований. Пусть х = (ж0, i, , хп-\)- исходный вектор данных, F - ортогональная матрица, S - матрица выбора спектральных компонент размерности т х п, 1 т п, W -матрица восстановления размерности п х т. Задача сжатия состоит в выборе F, S и W так, чтобы где р - некоторая метрика. Содержательно, задача (1) сводится к следующему. Исходный вектор х размерности п подвергается ортогональному преобразованию F. Затем посредством матрицы выбора S выбираются т отсчетов сигнала в новой системе координат. (Отметим, что эти выбранные отсчеты и предназначены для передачи, хранения и т.д.). Далее производится "экстраполяция" этих отсчетов посредством матрицы W и при помощи обратного преобразования F l восстанавливается исходный вектор. Величина к = — называется коэффициентом сжатия. С другой стороны, задача восстановления сжатого сигнала можно рассматриваться как обратная (некорректно поставленная) задача. На самом деле, если даже считать входной сигнал х заданным точно, то вектор у = SFx, подлежащий передаче, является искаженным. Отсюда, естественным образом, возникает задача использования метода регуляризации перед "экстраполяцией" вектора у. Таким образом, задача сжатия и восстановления сигнала с регуляризацией состоим в выборе операторов /, 5, W и регуляризирующего оператора JR так, чтобы где р - некоторая метрика. . Диссертационная работа посвящена исследованию задач (1) и (2). Работа состоит из трех глав. Первая глава посвящена задаче определения матриц выбора для дискретных ортогональных преобразований. В параграфе 1.2 приводятся постановка задачи сжатия и восстановления сигнала, обосновывается важность задачи определения матрицы выбора для различных типов дискретных ортогональных преобразований. В параграфах 1.2 и 1.3 определены матрицы выбора для дискретного преобразования Фурье, дискретных тригонометрических преобразований (преобразование Хартли, косинусное и синусное преобразование), дискретных преобразований Уолша-Адамара, Уолша-Пэли и Уолша.
Похожие диссертации на Сжатие сигналов посредством дискретных ортогональных преобразований с регуляризацией
