Сжатие сигналов посредством дискретных ортогональных преобразований с регуляризацией тема диссертации и автореферата по ВАК РФ 01.00.00, кандидат физико-математических наук Казарян, Мариетта Левоновна

• Казарян, Мариетта Левоновна
• кандидат физико-математических наук
• 1995

Оглавление диссертации кандидат физико-математических наук Казарян, Мариетта Левоновна

Введение

Глава 1. Матрицы выбора для дискретных ортогональных преобразований

1.1. Постановка задачи

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

1.3. Матрицы выбора для преобразования Уолша-Адамара, Уолша-Пэли и Уолша.

1.4. Выводы.

Глава 2. Регуляризация дискретных ортогональных преобразований.

2.1. Введение и постановка задачи.

2.2. Регуляризация дискретного преобразования Фурье с приближенными коэффициентами

2.3. Регуляризация дискретного преобразования Уолша.

2.4. Выводы.

Глава 3. Оценки погрешностей при сжатии сигналов с регуляризацией.

3.1. Постановка задачи

3.2. Оценка погрешностей для ДПФ и преобразования Хартли

3.3. Оценка погрешностей для ДКП, ДСП и ДПУА.

3.4. Выводы.

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

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

В настоящее время разработано большое количество разнообразных систем сжатия данных. Одними из основных используемых математических методов являются спектральные методы, основанные на вычислении дискретных ортогональных преобразований (ДОП) [1,3,2024]. Интерес к изучению ДОП в последние годы значительно возрос, что обусловлено, в основном, следующими причинами:

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

- ортогональные преобразования обладают полезным свойством сохранения энергия, они линейны и легко обратимы;

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

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

Сжатие посредством ДОП (или кодирование с преобразованием) было предложено в конце 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, . . . , хп1)исходный вектор данных, F - ортогональная матрица, S - матрица выбора спектральных компонент размерности т х п, 1 < т < п, W -матрица восстановления размерности п х т.

Задача сжатия состоит в выборе F, S и W так, чтобы р(х, F~lW SFx) -> min (1) где р - некоторая метрика.

Содержательно, задача (1) сводится к следующему. Исходный вектор х размерности п подвергается ортогональному преобразованию F. Затем посредством матрицы выбора S выбираются т отсчетов сигнала в новой системе координат. (Отметим, что эти выбранные отсчеты и предназначены для передачи, хранения и т.д.). Далее производится "экстраполяция" этих отсчетов посредством матрицы W и при помощи обратного преобразования F~l восстанавливается исходный вектор. Величина к = ^ называется коэффициентом сжатия.

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

Таким образом, задача сжатия и восстановления сигнала с регуляризацией состоим в выборе операторов /, 5, W и регуляризирующего оператора R так, чтобы р(х, f~WRSFx) тгп (2) где р - некоторая метрика. .

Диссертационная работа посвящена исследованию задач (1) и (2).

Работа состоит из трех глав.

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

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

В параграфах 1.2 и 1.3 определены матрицы выбора для дискретного преобразования Фурье, дискретных тригонометрических преобразований (преобразование Хартли, косинусное и синусное преобразование), дискретных преобразований Уолша-Адамара, Уолша-Пэли и Уолша.

Результат первой главы можно сформулировать в виде общего утверждения.

Утверждение 1. При сжатии сигнала необходимо заменять нулями:

- центральные компоненты спектра для преобразований Фурье и Хартли;

- последние компоненты спектра для ДКП, ДСП, ДПУП, ДПУ;

- компонента спектра с номерами 2г-1(2г — 1), г = 1, 2,. , к, г — 1,2,. ,2ПГ, для ДПУА, где 2п - длина сигнала, 2к - коэффициент сжатия.

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

1 + с^.1+а> 0 < а < 1, О, А= 1,2,. 1. позволяет произвести устойчивое суммирование рядов Фурье и Уолша.

Третья глава посвящена оценке погрешностей при сжатии сигналов с регуляризацией. Получены оценки погрешностей для ДПФ, преобразований Хартли, ДКП, ДСП и ДПУА с регуляризацией и без регуляризации. Проведено сравнение соответствующих оценок и определены значения регуляризирующего параметра а улучшающего восстановленный сигнал.

Каждая из трех глав завершается параграфом, в котором приводятся основные выводы.

Заключение диссертации по теме «Физико-математические науки», Казарян, Мариетта Левоновна

3.4. Выводы.

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

Проведено сравнение оценок погрешностей и найдены значения регуляризирующего параметра а для ДПФ, преобразования Хартли, ДКП, ДСП и ДПУА, при которых восстановленный сигнал ближе к оригиналу чем сигнал восстановленный без применения метода регуляризации.

Список литературы диссертационного исследования кандидат физико-математических наук Казарян, Мариетта Левоновна, 1995 год

1. Ахмед H., Pao K.P. Ортогональные преобразования при обработке цифровых сигналов. М., Связь, 1980.

2. Голубов Б.Н., Ефимов A.B., Скворцова В.А. Ряды и преобразования Уолгца. М., Наука, 1987.

3. Уинтц П. Кодирование изображения посредством преобразований. ТИИЭР, т.60, 1972, с.69-83.

4. Агаян С.С., Петросян A.A. Оптимальные методы зонного кодирования посредством дискретных ортогональных преобразований. Препринт No 89-3, 1989.

5. Прэтт У. Цифровая обработка изображений. М., Мир, 1982, т.1, т.2, -312 е., 480 с.

6. Гонсалес Дж.Ту. Принципы распознавания образов. Мир, 1978, 411с.

7. Ватанабе С. Разложение Карунена-Лоэва и факторнай анализ. Теория и приложения. В кн. Автоматический анализ сложных изображений. М., Мир, 1969, с.254-275.

8. Петросян A.A. Оценки спектров дискретных преобразований Фурье. ДАН Арм-ССР, т.87, No 5, 1988, с.203-206.

9. Р.Беллман, С .Дрейфус. Прикладные задачи динамического программирования. М., Наука, 1965.

10. Z.Wang. Fast Algorithms for the discrete transform and for the discrete Fourier transform. IEEE Tans, on Acombtics, Speech, and Signal Processing, vol. 32, No 4,1984, p.803-816.

11. Гладиштейн И.О., Рыжик И.М. Таблицы интегралов, сумм, рядов и произведений. М., 1962.

12. Логинов В.П. Функции Уолша и области их применения. Зарубежная радиоэлектроника, No 4, 1973, с.73-101.

13. Холл М. Комбинаторика. М., 1970.

14. Wallis J.S. Haclamard matrices. In Combinatorics Room Squares, Sum-Free Sets and Hadamard matrices. Lecture Notes in Mathematics, vol.292,1972.

15. Тихонов A.H., Арсении В.Я. Методы решения некорректных задач. М., Наука, 1979.

16. Агаян С.С., Баядян Г.Л., Геворкян Д.З. Вопросы устойчивости суммирования ортогональных рядов и вычисления линейных преобразований. Кибернетика и вычислительная техника. М., Наука, 1990,с.132-168.

17. Хармут X. Теория секвентного анализа, основы и применения. М., Наука, 1980, с.574.

18. Виттих В.А., Сергеев В.В., Сойфер В.А. Обработка изображений в автоматизированных исследованиях. М., Наука, 1982.

19. Агаян С.С. Оптимальные алгоритмы ортогональных преобразований и их реализация на ЭВМ. Кибернетика и вычислительная техника. Вып. 2,1986, с.231-319.

20. Трахтман A.M., Трахтман В.А. Основы теории дискретных сигналов на конечных интервалах. М., Сов. Радио, 1975.

21. Трахтман В.А. Быстрые преобразования Фурье для широкого класса систем ортогональных функций. Радиотехника и электроника, 1976, No 5, с.1034- 1041.

22. Enomoto Н., Shibata К. Orthogonal transform coding system for television signals. IEEE Trans. Electromgn. Compat., Special Issue on Walsh functions, vol. 19, 1971, p.11-17.

23. Rao K.R.,Narasimhan M.A., Revohivi K. Image data processing by Hadamard- Haar transform. IEEE Trans. Comput., vol. C-23, 1975, p.888-896.

24. ПрэттУ.К., КейнД., ЭндрюсГ. Кодироваппе изображений посредством преобразования Адамара. ТИИЭР, т.57, No 1, 1969, с.66-78.

25. Andrews H.G., Pratt W.K. Fourier transform coding of images. Havaii Int. Conf. Sys. Sci., 1968, p.677-679.

26. Anderson G.B , Huang T.S. Piecewise Fourier transformation for picture Bandwidth compression. IEEE Trans. Commun. Tech., vol. Corn-19, No 4, 1971, p.133-140.

27. Habibi A., Wints P.A. Image coding by linear transformation and block quantization. IEEE Trans. Commun. Tech. vol. Corn-19, No 2,1971, p.50-63.

28. Woods J.W., Huang T.S. Picture bandwidth compression by lineartransformation and block quantisation, hi. Picture bandwidth compression. New York, Gordon and Breach, 1972, p.555-573.

29. Гоулд Б., Рейдер Ч. Цифровая обработка сигналов, М., Сов. Радио, 1973.

30. Оппенхейм А., Шафе Р. Цифровая обработка сигналов. М., Связь, 1979.

31. Рабинер JI.P. Гоулд Б. Теория и применение цифровой обработки сигналов. М., Мир, 1978.

32. Ту Дж., Гонсалес Р. Принципы распознавания образов. М., Мир, 1978.

33. Ярославский Л.П. Цифровая обработка сигналов в оптике и голографии: Введение в цифровую оптику. М., Радио и Связь, 1987.

34. Джайн А.К. Сжатие видеоинформации. Обзор. ТИИЭР, т.69, No 3,1981,с.71- 117.

35. Тесчер А.Г. Кодирование изображений с преобразованием. В кн. Методы передачи изображений. Сокращение избыточности. Под ред. У.К.Прэтта. М., Радио и связь, 19836 с.103-143.

36. Лабунец В.Г. Новые унитарные преобразования со структурами быстрых алгоритмов. В кн. Автоматизация экспериментальных исследований. М., 1982, с.61-69.

37. Логинов В.П. Функции Уолша и области их применения. Зарубежная радиоэлектроника. No 4, 1973, с.73-101.

38. Ahmed N., Natarajan Т. Rao K.R. Discrete cosine transform. IEEE Trans. Comput., vol. C-23, No 1,1974, p.90-93.

39. Egiazarian К.О. Discrete trigonometric transforms. Cybernetics and Systems'88, R.TrappI (ed.), 1988, p.1215-1222.

40. Jain A.K. A sinusoidal family of unitary transforms. IEEE Trans. Pattern Anal. Machine Intel!., vol. PAMI-1, No Щ 1979, p.356-365.

41. Pratt W.K.) Chen W.H., Welch L.R. Staat transform image coding. IEEE Trans. Common., vol Corn-22, No 9, 1974, p.1075-1093.

42. Rao K.R., Devarajan V., Vlasenko V., Narasimhan M.A. Cal-Sal Walsh- Hadamard transform. IEEE! Trans, on ASSP, 1978, vol. 26, No 6, p.605-607. I

43. Shore J.E. On the application of Haar functions. IEEE Trans. Commun. Tech., No 3, 1973, p.209-216. I

44. Казарян M.JI. Задача сжатия сигналов с регуляризующей матри-дей. Деп. в ВИНИТИ 01.04.92г., No 1112-В92, 13 стр.

45. Казарян M.JI. Задачи винеровской фильтрации сигналов с применением метода регуляризации. Деп. в ВИНИТИ 21.10.92г., No 3033-В92, 14 стр.

46. Казарян M.JI. Алгоритм отбора признаков при распознавании образов с регуляризирующей матрицей. Деп. в ВИНИТИ 02.03.93г., No 518-В93, 18 стр.

47. Казарян M.JI. Алгоритм сжатия данных с регуляризацией. Препринт СОГУ, 1995, 13 стр.

48. Казарян M.JI. Общий алгоритм сжатия данных с регуляризирующей матрицей. Проблемы алгебры и анализа. Сб. сообщении конф. математического факультета. Изд. СОГУ, 1995, 12 стр.