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

Введение.

1. АНАЛИЗ МЕТОДОВ СОКРАЩЕНИЯ ИНФОРМАЦИОННОЙ ИЗБЫТОЧНОСТИ ЦИФРОВЫХ ИЗОБРАЖЕНИЙ.

1.1. Представление цифровых изображений.

1.2. Классификация методов сжатия. Основные характеристики.

1.3. Алгоритмы сжатия изображений без потерь.

1.3.1. Сжатие способом кодирования серий (RLE).

1.3.2. Сжатие по методу Хаффмана.

1.3.3. Алгоритм Лемпеля-Зива (LZ-compression).

1.3.4. Алгоритм Лемпеля-Зива-Велча (Lempel-Ziv-Welch -LZW).

1.3.5. Алгоритм JBIG.

1.3.6. Алгоритм Lossless JPEG.

1.4. Алгоритмы сжатия с потерями.

1.4.1. Метод усеченного блочного кодирования (УБК).

1.4.2. Сжатие по стандарту JPEG.

1.4.3. Сжатие по стандарту MPEG.

1.4.4. Сжатие по методу WIC (Wavelet Image Compression).

1.4.5. Фрактальное сжатие изображений.

Выводы по главе 1.

2. МОДИФИКАЦИЯ АЛГОРИТМОВ СЖАТИЯ /ВОССТАНОВЛЕНИЯ ИЗОБРАЖЕНИЙ ПО МЕТОДУ JPEG.

2.1. Применение преобразования Хартли для пространственночастотной декомпозиции фрагментов.

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

2.2.1. Дискретное преобразование Уолша-Адамара.

2.2.2. Преобразование Хаара.

2.3. Алгоритмы быстрых ортогональных преобразований в базисах знакопеременных диадных функций.

2.4. Модификация процедур сканирования и квантования отсчетов фрагмента.

2.5. Исследование эффективности сжатия/восстановления изображений на основе модифицированного метода JPEG.

Выводы по главе 2.

ГЛАВА 3. СЖАТИЕ ИЗОБРАЖЕНИЙ С АДАПТИВНЫМ ВЫБОРОМ ФРАГМЕНТОВ.

3.1. Адаптивный метод сегментации областей.

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

3.3. Алгоритм сжатия отдельных фрагментов.

3.4. Исследование эффективности сжатия/восстановления изображений с адаптивным выбором областей.

Выводы по главе 3.

ГЛАВА 4. МОДИФИЦИРОВАННЫЙ ФРАКТАЛЬНЫЙ

МЕТОД СЖАТИЯ.

4.1. Аппроксимация локальных областей изображения.

4.2. Определение параметров аппроксимирующей функции.

4.3. Поиск области максимального размера.

4.4. Восстановление изображения.

4.5. Анализ полученных результатов.

Выводы по главе 4.

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

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

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

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

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

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

• совершенствование алгоритмов сжатия изображений по стандарту JPEG за счет:

- применения преобразований Хартли, Уолша - Адамара и Хаара;

- применения новых способов сканирования матрицы спектральных компонент фрагментов;

- дополнительной весовой обработки вектора спектральных компонент перед квантованием;

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

• разработка метода сжатия изображений на основе выделения локальных областей, подлежащих сжатию:

О разработка метода сегментации изображений с адаптивным выбором порога;

О разработка методов сглаживания границ объектов, локализованных в выделенных областях; О исследование влияния размеров сжимаемых фрагментов выбранной области на коэффициент сжатия и качество восстановленного изображения;

• разработка метода сжатия на основе аппроксимации изображения фрагментами гармонических функций:

О построение алгоритмов сжатия и восстановления;

О разработка методики определения параметров аппроксимирующей функции.

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

Научная новизна работы состоит в следующем:

• разработана модификация алгоритма JPEG, основанная на применении ортогонального преобразования Хаара при выполнении спектрального разложения фрагментов изображения;

• предложено применение кодирования по Хаффману с укрупнением при кодировании квантованных спектральных компонент;

• выполнено исследование эффективности преобразований Хаара и Уолша -Адамара для сжатия изображений по стандарту JPEG;

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

• выбраны весовые функции при квантовании отсчетов вектора спектральных компонент фрагментов изображения, позволяющие при приемлемом качестве восстановленного изображения сократить число ненулевых компонент;

• разработан метод сегментации областей изображения;

• разработан метод сжатия изображений на основе выделения локальных областей, подлежащих сжатию и содержащих информативные объекты изображения;

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

Практическая ценность результатов заключается в следующем:

• разработаны программно-алгоритмические средства сжатия и восстановления изображений по JPEG-подобному методу, реализующие предложенные автором подходы;

• разработаны программно-алгоритмические средства сжатия изображений на основе выделения локальных областей с информативными объектами изображения, подлежащих сжатию;

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

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

Основные результаты работы внедрены в СПбГИТМО(ТУ), ЗАО

Петербург Транзит Телеком". Работа поддерживалась грантами Конкурсного центра фундаментального естествознания Министерства образования

Российской федерации в 2001 и 2002 годах.

Основные положения, выносимые на защиту:

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

2. Результаты исследования эффективности применения ортогональных преобразований Хартли, Уолша - Адамара и Хаара для сжатия изображений по стандарту JPEG.

3. Метод сегментации областей изображения и отслеживания границ областей.

4. Метод сжатия изображений на основе выделения локальных подлежащих сжатию областей, содержащих информативные объекты.

5. Метод сжатия на основе сегментации областей изображения и их аппроксимации фрагментами гармонических функций.

Апробация работы. Результаты выполненных исследований докладывались на IV Int. Conf. «Pattern recognition and information processing», 20-22 may 1997, Minsk - Szczecin, Belarus - Poland, XXX научно-технической конференции студентов, аспирантов и молодых ученых Санкт-Петербургской академии гражданской авиации , -СПб, 1998, XIII International conference "Systems for automation of engineering and research" (SAER-99) September 18-19, St.Konstantin, Bulgaria, 1999, XXXII научно-технической конференции студентов, аспирантов и молодых ученых Санкт-Петербургской академии гражданской авиации, -СПб, 2000, VI Санкт-Петербургской ассамблеи молодых ученых и специалистов, СПб, СпбГУ, 2001, III Int.Conf."Advanced Computer Systems ASC-2002", Szczecin, Poland, 23-25 Oct., 2002, Всероссийской научно-технической конференции "Прогрессивные технологии в машино и приборостроении", Нижний Новгород-Арзамас, 2002, XXXIV научно-технической конференции студентов, аспирантов и молодых ученых Санкт-Петербургской академии гражданской авиации, -СПб, 2002, Политехническом Симпозиуме «Молодые ученые - промышленности Северо-Западного Региона, СПб, СПбГПУ, 2002, XXXII (2002) и XXXIII (2003) Научно-технических конференциях профессорско-преподавательского состава СПбГИТМО(ТУ).

По теме диссертации опубликовано 12 работ. Структура и объем диссертации.

Диссертация состоит из введения, четырех глав, заключения и списка литературы. Рукопись содержит 151 страницу текста, 45 рисунков и 10 таблиц. Список литературы включает 69 наименований.

Выводы по главе 4

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

2. Определены требования, предъявляемые как к выделяемым локальным областям, так и к аппроксимирующим функциям.

3. Разработана методика определения параметров аппроксимирующих функций и оценки погрешности , вносимой при аппроксимации.

4. Разработаны программные средства, реализующие предложенный метод сжатия и выполнены эксперименты по сжатию изображений различного информационного смысла.

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

ЗАКЛЮЧЕНИЕ

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

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

1 Определены основные пути модификации стандарта JPEG сжатия многоуровневых изображений, обеспечивающие его усовершенствование за счет:

• применения более простых ортогональных базисов Хартли, Уолша-Адамара и Хаара при спектральном разложении фрагментов исходного изображения;

• дополнительной весовой обработки векторизованных матриц спектральных компонент фрагментов;

• оптимального кодирования по Хаффману с укрупнением квантованных отсчетов векторов спектральных компонент, что обеспечивает сокращение времени сжатия/восстановления, повышение качества восстановленного изображения и увеличение коэффициента сжатия.

2 Получены удобные для программирования алгоритмов БДОП Уолша-Адамара и Хаара рекуррентные соотношения, позволяющие в компактной форме описать как отдельную базовую операцию типа «бабочка» на произвольной итерации, так и весь алгоритм в целом, включая межитерационные перестановки элементов.

3 Разработаны новые алгоритмы сканирования матрицы спектральных компонент - спиральное сканирование для отсчетов двумерного БПХ, учитывающее центрированный характер спектра, и сканирование матрицы спектральных компонент с учетом вероятности появления ненулевых компонент на каждой позиции, рассчитываемой по всем фрагментам сжимаемого изображения, что позволяет повысить коэффициент сжатия

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

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

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

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

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

1. Астафьева Н.М. Вейвлет-анализ: основы теории и примеры применения// Успехи физических наук, т. 166, №11, 1996.

2. Бочарова И.Е., Кудряшов Б.Д., Таубин Ф.А., Алснис И.Л. Алгоритмы кодирования и сжатия изображений в системах мультимедиа. Учебное пособие// -СПб.: СПб. Государственный университет аэрокосмического приборостроения, 1997, -30 с.

3. Брейсуэлл Р. Преобразование Хартли. Теория и приложения. М.: Мир, 1990.- 225 с.

4. Бруин Б. Titan сжимает волной.// Computerlend, № 42, 1997

5. Бутаков Е.А., Островский В.И.,Фадеев И.Л. Обработка изображений на ЭВМ.//- М.: Радио и связь,-1987, -238 с.

6. Васильев В.Н., Гуров И.П. Компьютерная обработка сигналов в приложении к интерферометрическим системам// СПб, bhv, 1998.

7. Востров Г.М., Полякова М.В., Любченко В.В. Фрактальное сжатие временных рядов с использованием нелинейной вейвлет-аппроксимации. Труды Одесского политехнического института. Выпуск 3, -Одесса: Изд-во ОдПИ, 1999, с.87-92 .

8. Вотолин Д.С. Тенденции развития алгоритмов сжатия растровых изображений // Открытые системы, № 4, 1995.

9. Вотолин Д.С. MPEG-стандарт ISO на видео в системах мультимедиа// Открытые системы, № 5, 1995.

10. Ю.Вотолин Д.С. Фрактальное сжатие изображений// Computer World-Россия. №6, 1996.

11. Вотолин Д.С. Алгоритмы сжатия изображений. Учебное пособие.// -М:, МГУ, 1998, -52 с.

12. Глущик Р.В. Процедуры распознавания и локализации объектов на изображении.// В сб. «Современные технологии. Труды молодых ученых ИТМО», СПб,СПбГИТМО, 2001 г., с.106-109.

13. Дагман Э.Е., Кухарев Г. А. Быстрые дискретные ортогональные преобразования. Новосибирск: Наука, -1983, -232 с.

14. Дьяконов В., Абраменкова И. MATLAB обработка сигналов и изображений. Специальный справочник. СПб, "Питер", 2002, - 608 е.

15. Зубарев Ю.Б., Дворкович В.П. Цифровая обработка телевизионных и компьютерных изображений. Москва, 1997.

16. Корриган Дж. Компьютерная графика: Секреты и решения: М.: Энтроп, 1995.

17. Кодирование и обработка изображений,- М.: Наука , -1988. -175 с.

18. Кухарев Г.А., Тропченко А.Ю., Шмерко В.П. Систолические процессоры для обработки сигналов. Минск: Беларусь, -1988, -127 с.

19. Ламброу Н, Линней А., Спеллер Р. Применение вейвлет-преобразования к обработке медицинских сигналов и изображений// Компьютерра №8 1998.

20. Переберин А.В. Вейвлеты в компьютерной графике// Компьютерра №8 1998.

21. Применение цифровой обработки сигналов. //Под ред А.Оппенгейма. -М.:Мир,-1980.-550 с.

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

23. Розенфельд А. Распознавание и обработка изображений с помощью вычислительных машин.// М.: Мир, 1972.

24. Рыдзевский B.JI. Фрактальное сжатие изображений// Труды Петрозаводского государственного университета. Сер. "Прикладная математика и кибернетика". Вып. 5, Петрозаводск: Изд-во ПетрГУ, 1996, с.114-125.

25. Рыдзевский B.JI. Об одном методе увеличения скорости фрактального сжатия изображений// Труды Петрозаводского государственного университета. Сер. "Прикладная математика и кибернетика". Вып. 7, Петрозаводск: Изд-во ПетрГУ, 1998, с.98-106.

26. Сергиенко А.Б. Цифровая обработка сигналов. СПб., "Питер". 2002, -608 с.

27. Солонина А., Улахович Д., Яковлев JI. Алгоритмы и процессоры цифровой обработки сигналов. СПб, БХВ-Петербург, 2001, 464 с.

28. Суворов А.С. Эффективный метод сжатия медицинских изображений без потерь// Материалы VI Международной конференции "проблемы пространства, времени, движения", -СПб, СПбГИТМО(ТУ), 2000, с.34.

29. Темников Ф.Е., Афонин В.А., Дмитриев В.И. Теоретические основы информационной техники. -М.; Энергия, 1980.

30. Тропченко А.А. Вычисление двумерной свертки на основе МДПХ.// Тезисы докладов XXX научно-технической конференции студентов,аспирантов и молодых ученых Санкт-Петербургской академии гражданской авиации, -СПб, 1998, с. 15.

31. Тропченко А.А. Алгоритмические и аппаратные средства для сжатия-восстановления изображений при их передаче по каналам связи.// Тезисы докладов VI Санкт-Петербургской ассамблеи молодых ученых и специалистов, СПб, СпбГУ, 2001, с.79.

32. Тропченко А. А. Сжатие изображений на основе JPEG-подобных алгоритмов с использованием ортогональных диадных базисов. // В сб. «Современные технологии. Труды молодых ученых ИТМО», СПб, 2001 г., с.128-130.

33. Тропченко А.А. Сжатие изображений на основе аппроксимации гладкими функциями. // В сб. «Современные технологии. Труды молодых ученых ИТМО», СПб, 2001 г, с.110-114.

34. Тропченко А.А. Повышение эффективности процедур сжатия цифровых изображений.//Тезисы докладов XXXIV научно-технической конференции студентов, аспирантов и молодых ученых Санкт-Петербургской академии гражданской авиации, -СПб, 2002, с.47-49.

35. Тропченко А.А. Сокращение информационной избыточности цифровых изображений при их передаче по каналам связи// Тезисы докладов

36. Политехнического Симпозиума «Молодые ученые промышленности Северо-Западного Региона, СПб, Изд. СПбГПУ, 2002, с. 72

37. Тропченко А.Ю., Романов Ю.Ф. Алгоритмы быстрого преобразования Хартли при различных основаниях и конвейерные структуры для их реализации // "Известия вузов-Приборостроение", 1993, т.36, N 4, стр.3732.

38. Фор А. Восприятие и распознавание образов. // М.Машиностроение, -1989, -272.

39. Фу. К. Структурные методы в распознавании образов.// -М.: Мир, 1977.

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

41. Antoni М., Barlaud М., Mathieu P. Image coding using Wavelet Transform// IEEE Trans. Image Proc., 1992, N 2, p. 205-220.

42. Barnsley M.F. Fractals Everywhere. London: Academic Press Inc., 1988.

43. Burt P.H. et Adelson A.E. The Laplacian pyramid as a compact image code // IEEE Trans, on Communications, 31, pp. 532-540, 1983.

44. Calderbank G, Daubechies I., Sweldens W., Yeo L. Wavelet transforms that map integers to integers. // Technical report, Department of mathematics, Princeton University, 1996.

45. Cvetcovic Z., Popovic M.V. New fast algorithms for the computation of discrete cosine transforms.// IEEE Trans, on Signal Processing, 1992, v.40, N.8, p.2083 2086.

46. Colella D., Heil C. Characterizations of scaling functions: Continuous Solutions // SIAM J. Matrix Anal. Appl., vol. 15, pp. 496-518, 1994.

47. Daubechies I, Ten lectures on Wavelets, Philadelphia, 1992.

48. Evangelista G. The coding of Multiplexed Wavelet Transforms // IEEE translations on signal processing ., Vol. 44, No 7, 1996.

49. Fisher Y. «Fractal image compression»// Sig-Graf 92., № 4, 1992.

50. Graps A.L. An Introdaction to Wavelets // IEEE Computional Science and Engineering, v.2, N 2, 1995, p.p. 50-61.

51. Jacquin A. «Fractal image coding based on a theory of iterated contractive image transformations «// Open systems, № 5, 1995.

52. Jacquin A. Fractal image coding based on a theory of iterated contractive image transformations // in Proceedings of SPIE Visual.

53. Lewis A., Knowles G. Image compression using the 2-D Wavelet Transform// IEEE Trans. Image Proc., 1992, N 2, p.244-250

54. Mallat S. A Theory for Multiresolution Signal Decomposition: The Wavelet

55. Representation //Proc. IEEE Trans on Pattern Anal, and Math, intel., Vol. 11, No 7, 1989.

56. Mallat S. Wavelet tour of signal processing//Academic Press, N-J, 1997.

57. Mallat S., Falson F. Undestanding image transform codes// Proc. SPIE Aerospace Conf., Orlando, 1997.

58. Malvar H. Fast computation of discrete cosine transform through fast Hartly transform.//Electronics letters, 1986, v.22, N.7, p. 352-353.

59. Qien G.E., Baharav Z., Lepsqy S.,Karnin E. A new improved collage theorem with appplications to multiresolution fractal image coding.// In Proc. ICASSP, 1994.

60. Saupe D., Hamzaoui R., Hartenstein H., Fractal image compression An introductory overview.// in: Fractal Models for Image Synthesis, Compression and Analysis, D. Saupe, J. Hart (eds.), SIGGRAPH'96 Course Notes, ACM, New Orleans, Louisiana, Aug. 1996.

61. Shensa M.J. Discrete Wavelet Transforms: Wedding the a tours and Mallat Algorithms, IEEE Rrans. on Signal Process., Vol. 40, 10, p.p.2464 2482, 1992.

62. Tropchenko A.A., Tropchenko A.U. Modified fractal method of havetone multilevel image compression // Proc. of Int.Conf. "AdvancedComputer SystemsASC-2002" ,Szczecin, 23-25 0ct.2002, Szczecin, Poland, p.p. 399 -405.

63. Wallace G.K. The JPEG still picture compression standart// Communication of ACM, v. 34, №4, 1991.q 6mie