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

• Гришин, Михаил Викторович
• кандидат технических наук
• 2005

Оглавление диссертации кандидат технических наук Гришин, Михаил Викторович

Введение

1. Анализ методов сжатия и маркирования изображений

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

1.2. Кодирование и декодирование изображения

1.3. Классификация алгоритмов сжатия

1.4. Методы обхода плоскости

1.4.1. ZigZag сканирование

1.4.2. Обход строками

1.4.3. Обход полосами

1.4.4. Контурный обход

1.4.5. Обход по спирали

1.5. Методы сжатия изображений без потерь

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

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

1.5.3. Алгоритм Лемпеля-Зива

1.5.4. Алгоритм JBIG

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

1.6. Сжатие изображений с потерями

1.6.1. Метод сжатия JPEG

1.6.2. Рекурсивно волновой алгоритм

1.6.3. Фрактальные методы сжатия

1.7. Оценка качества восстановленного изображения

1.8. Методы защиты авторского права на основе цифровых 37 водяных знаков

1.8.1. Технологии маркирования

1.8.2. Введение в алгоритмы маркирования 41 Выводы f» 2. Определение базисов вейвлет функций оптимальных для сжатия изображений

2.1.Вейвлеты

2.1.1. Непрерывные вейвлет преобразования

2.1.2. Частотное описание вейвлет преобразований

2.1.3. Дискретное вейвлет преобразование

2.1.3.1. Матричное описание ДВП

2.1.3.2. Описание ДВП посредством блоков фильтров

2.1.4. Пакеты вейвлетов

2.1.5. Целочисленные вейвлет преобразования

2.1.5.1. Целочисленное вычисление вейвлет преобразования 5g (2,2)

2.1.5.2. Вейвлет преобразование лэйзи

2.1.5.3. Целочисленное вычисление вейвлет преобразования (1,3)

2.1.5.4. Целочисленное вычисление вейвлет преобразования gQ (2,6)

2.1.5.5. Целочисленное вычисление вейвлет преобразования gl ^ (5,3)

2.2. Определение целочисленного вейвлет преобразования оптимального для сжатия изображений

Выводы

3. Развитие методов сжатия изображений на основе вейвлет 70 преобразований

3.1. Используемые обратимые дискретные ортогональные 70 преобразования

3.2. Квантование вейвлет коэффициентов 72 t' 3.3. Развитие методов обхода плоскости вейвлет коэффициентов

3.3.1. Древовидный обход вейвлет коэффициентов

3.3.2. Псевдо ZigZag сканирование плоскости вейвлет 74 коэффициентов

3.4. Методы сжатия изображений на основе вейвлет преобразований ^

3.4.1. Метод нульдерева

3.4.2. Использование кодовой книги для кодирования вейвлет коэффициентов

3.4.3. Метод шаблонно-блочного кодирования

3.4.4. Методы кодирования вейвлет коэффициентов, 35 упорядоченных в ZigZag порядке

3.4.4.1. Адаптивное кодирование

3.4.4.3. Разрядно срезовый алгоритм кодирования

3.4.5. Метод сжатия на основе выделения локальных однородных 92 областей

3.4.6. Разрядное кодирование вейвлет деревьев

3.5. Вычислительная сложность алгоритмов сжатия изображений на Ю основе вейвлет преобразования

Выводы

4. Внедрение технологии цифрового маркирования в методы сжатия \ ю изображений

4.1. Маркирование компонент детализации

4.2. Технология слияния логотипа с маркируемым изображением 1 ^

4.3. Модифицированный метод маркирования Сот

4.4. Исследование устойчивости методов маркирования изображений к ¡21 алгоритмам цифровой обработки сигнала

Выводы

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

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

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

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

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

Помимо JPEG, MPEG к спектральным методам сжатия относятся методы, основанные на вейвлет преобразовании. Данные вейвлет преобразования могут быть представлены в виде поддерева, которое может быть эффективно закодировано.

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

Однако существующие методы имеют следующие недостатки: невысокий коэффициент сжатия и, как правило, отсутствие механизмов защиты авторских прав в сохранённом изображении, а так же отсутствие возможности «постепенной» загрузки сжатого изображения из сети.

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

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

Задачами исследования являются:

• Совершенствование алгоритмов сжатия изображений на основе дискретного ортогонального вейвлет преобразования, а именно:

- определение оптимального дискретного ортогонального вейвлет преобразования различных базисов, например Хаара, базис (5,3);

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

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

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

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

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

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

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

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

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

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

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

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

2. Метод сжатия изображений на основе словарного кодирования вейвлет коэффициентов.

3. Метод сжатия изображения на основе кодирования локальных однородных областей.

4. Метод сжатия изображения на основе разрядно-срезового кодирования вейвлет коэффициентов.

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

Апробация работы. Результаты выполненных исследований докладывались на XXXIV научно-технической конференции студентов, аспирантов и молодых учёных: академии гражданской авиации; XXXII научно-технической конференции профессорско-преподавательского состава ИТМО;

XXXIV научно-технической конференции студентов, аспирантов и молодых учёных, 2002г.: Министерства транспорта российской федерации государственной службы гражданской авиации академии гражданской авиации;

XXXV научно-технической конференций студентов, аспирантов и молодых учёных, 2003г.: Министерства транспорта российской федерации государственной службы гражданской авиации академии гражданской авиации; Санкт-Петербургского государственного института точной механики и оптики - «Научно-технический вестник», 2003г.; XXXIV научной и учёбно-методической конференции СПбГУИТМО, 2005г.

По теме диссертации опубликовано 8 работ (из них 3 работы без соавторов), в том числе 4 статьи.

Структура и объем диссертации.

Диссертация состоит из введения, четырёх глав, заключения, списка литературы и трёх приложений. Рукопись содержит 157 страниц текста, 59 рисунков и 15 таблиц. Список литературы включает 82 наименований.

Заключение диссертации по теме «Телекоммуникационные системы и компьютерные сети», Гришин, Михаил Викторович

Выводы

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

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

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

Список литературы диссертационного исследования кандидат технических наук Гришин, Михаил Викторович, 2005 год

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

2. Ватолин Д., Ратушняк А., Смирнов М., . Юкин В. «Методы сжатия данных»; Диалог-Мифи, М. 2002.

3. Воробьёв В.И., Грибунин В.Г. «Теория и практика вейвлет преобразований»; Военный университет связи; СПБ.; 2000.

4. Востриков A.C., Пустовой Н.В. "Цифровая обработка изображений в информационных системах"; Учебник НГТУ, Новосибирск 2002.

5. Гришин М.В. «Использование дискретных вейвлет преобразований для сжатия полутоновых изображений». Вестник конференции молодых учёных СПбГУ ИТМО. Сборник научных трудов. Под ред. B.JI. Ткалич. Т. 1, СПбГУ ИТМО, 2004, стр. 254-261.

6. Гришин М.В. Сжатие изображений на основе шаблонно-блочного кодирования// Тезисы докладов XXXV Юбилейной научно-технической конференции студентов, аспирантов и молодых ученых Санкт-Петербургской академии гражданской авиации, -СПб, 2003.

7. Гришин М.В., Кухта E.H. Проблемы авторизации и идентификации маркированных изображений// Тезисы докладов XXXIV научно-технической конференции студентов, аспирантов и молодых ученых Санкт-Петербургской академии гражданской авиации, -СПб, 2002.

8. Ю.Гришин М.В., Ожиганов A.A., Тропченко А.Ю. Сжатие изображений на основе выделения локальных однородных областей// В сб. «Информация и управление в технических системах. Научно-технический вестник СпбГУ ИТМО» Вып. 10, СПб., 2003, с.50-54.

9. Джоунз Г. «Программирование на языке Оккам»; М.,Мир,1989

10. Дремин И.М., Иванов О.В., Нечитайло В.А. «Вейвлеты и их использование»// «Успехи физических наук» Том 171 №5 Май 2001г.

11. Дьяконов В.П. «От теории к практике Вейвлеты»; Солон-Р, М., 2002.

12. Журавель И.М. "Краткий курс теории обработки изображений"// Консультационный центр MATLAB.

13. Леонид Левкович-Маслюк, Антон Переберин «Два курса по ВЕИВЛЕТ-АНАЛИЗУ»// Учебная программа 8-й международной конференции по компьютерной графике и визуализации ГрафиКон'98

14. Лукин А. «Введение в цифровую обработку сигналов (математические основы)»; Лаборатория компьютерной графики и мультимедиа, МГУ 2002.

15. Мастрюков Д.- «Алгоритмы сжатия информации» // «Монитор»; 7-8, 1993.

16. Новиков Л.В. «Основы вейвлет-анализа сигналов» // Учебное пособие, СПб. 1999.

17. Переберин A.B. «О системе вейвлет преобразований»// «Вычислительные методы и программы» Т.2. 2001.

18. Переберин A.B. «О систематизации вейвлет преобразований»// «Вычислительные методы и программирование», Т.2. 2001.

19. Потапов В.Н. «Обзор методов неискажающего кодирования дискретных источников»// УДК 519.72

20. Солонина А., Улахович Д., Яковлев JI. «Алгоритмы и процессоры цифровой обработки сигналов»; «БЧВ-Петербург», СПб., 2002.

21. Тропченко А.Ю. «Цифровая обработка изображений методы сжатия и вторичной обработки изображений. Распознавание объектов на изображении» // Учебно-методическое пособие по дисциплине "Методы обработки сигналов и изображений"; СПб., 1999.

22. Тропченко А.Ю. «Цифровая обработка сигналов. Методы предварительной обработки» // Учебно-методическое пособие по дисциплине "Методы обработки сигналов и изображений"; СПб., 1999

23. Тропченко A.A., Тропченко А.Ю. Modified fractal method of halftone multilevel image compression // Proc. of Int.Conf. "Advanced Computer SystemsASC-2002", Szczecin, 23-25 0ct.2002, Szczecin, Poland, p.p. 399 405.

24. Тропченко A.A., Ожиганов A.A., Повышение эффективности сжатия полутоновых изображений по стандарту JPEG// Изв. Вузов. Приборостроение, т.45, №5, 2002, с.22-26.

25. Тропченко A.A., Тропченко А.Ю., Ожиганов A.A., Модифицированный фрактальный метод сжатия многоуровневых изображений// Информационные технологии, 2003, № 3 , т., с.

26. Семенюк В.В. Экономное кодирование дискретной информации. -СПб., СПБ ГИТМО (ТУ), 2001.

27. Умняшкин Сергей Владимирович «Применение дискретного преобразования Крестенсона-Леви в цифровой обработке изображений»//УДК 621.391.24 : 681.3.01; Москва 1997

28. Уэлстид С., «Фракталы и вейвлеты для сжатия изображений в действии»; Триумф, М., 2003

29. Фомин А. А. «Основы сжатия информации»//Санкт-Петербургский государственный технический университет; 1998

30. Crever S. "Zero knowledge watermark detection"// Department of electrical engineering.

31. Deepa Kundur and Dimitrios Hatzinakos. "Digital watermarking using multiresolution wavelet decomposition."// In Proceedings of IEEE ICASSP *98, volume 5, pages 2969-2972, Seattle, WA, USA, May 1998.

32. Еего P. Simoncelli, Robert W. Buccigrossi "EmbeddedWavelet Image Compression Based on a Joint Probability Model"// 4th IEEE International Conference on Image Processing, Santa Barbara, CA. October 26-29, 1997.

33. Eric Durant "Wavelet-Based Image Compression Considerations"// Electrical Engineering and Computer Science Department University of Michigan, Monday 14 December 1998

34. Georey Davis "Implicit Image Models in Fractal Image Compression" // 6211 Sudiko Laboratory, Dartmouth College, Hanover, NH 03755, August 5, 1996.

35. George Voyatzis and Ioannis Pitas "The use of watermarks in the protection of digital multimedia products."// Proceedings of the IEEE, Special Issue on Identication and Protection of Multimedia Information, 87(7): 1197(1207, July 1999.

36. George Voyatzis and Ioannis Pitas. "Digital image watermarking using mixing systems."// Computer & Graphics, 22(4):405-416, August 1998.

37. Gopinath R.A. and Burrus C.S. "Wavelet and filter banks'V/Department of Electrical and Computer Engineering, Rice University, Houston, TX-77251 CML TR-91-20 September '91

38. Gustavo Garrigcos "Wavelet methods in image compression"// Mathematical Subject Classification: 42A16, 42C40, 41A15, 2000.

39. Ian H. Witten, Radford M. Neal, And John G. Cleary "Arithmetic coding for data compression" // Communications of the ACM; June 1987 Volume 30 Number 6

40. IEEE Standard EIA-189-A, "Encoded color bar Signal"; Jul 1976,

41. Jacues Lewalle, Syracuse University «Введение в анализ данных с применением непрерывного вейвлет преобразования»// перевод Грибунин В.Г.; 51. Robi Polikar, Iowa State University «Введение в вейвлет преобразование»// перевод Грибунин В.Г.; Автэкс СПб.

42. Joseph J. K. O'Ruanaidh and Thierry Pun. "Rotation, scale and translation invariant spread spectrum digital image watermarking"// Signal Processing, 66(3):303-317, May 1998.

43. Keissarian F.; Daem M.F.- "Block pattern coding of HVS-based on wavelets for image compression"// SPEE volume 4472.

44. Manfred Kopp "Lossless Wavelet Based Image Compression with Adaptive 2D Decomposition"// Technical University of Vienna Institute of Computer Graphics

45. Mark R. Bolin and Gary W. Meyer "A Visual Di^erence Metric for Realistic Image Synthesis"// Department of Computer and Information Science University of Oregon Eugene, OR 97403.

46. Mary L. Comer "Multiresolution image processing techniques with applications in texture segmentation and nonlinear filtering"// Purdue University; December 1995.

47. Max Fomitchev-"An introduction to wavelets and wavelet transforms'7/1998.

48. Michael B. Martin "Applications of Multiwavelets to Image Compression"// June, 1999 Blacksburg, Virginia

49. Michael David Adams "Reversible Wavelet Transforms and Their Application to Embedded Image Compression"// University of Victoria 1998

50. Michael David Adams "Reversible Wavelet Transforms and Their Application to Embedded Image Compression"// B.A.Sc., University ofWaterloo; 1993

51. Michael Seul, Lawrence O'Gorman, Michael J. Sammon "Practical algorithms for image analysis"; Cambridge university press 2001.

52. Michael Wakin, Justin Romberg, Hyeokho Choi, Richard Baraniuk "Geometric methods for wavelet-based image compression"// Dept. of Electrical and Computer Engineering, Rice University 6100 Main St., Houston, TX 77005

53. Mladen Victor Wickerhauser "Lectures on wavelet packet algorithms"// Department of Mathematics Washington University St. Louis, Missouri 63130 November 18,1991

54. Mohamed Ali Ben Ayed, Mourad Loulou, Mohamed Salim Bouhlel, Nouri Masmoudi, Lotfi Kamoun "5/3 Wavelet Transforms for Image Compression: Integration and Evaluation"//JTEA2002 21-22-23 Mars 2002 Sousse Nord Tunisie

55. Peter Meerwald "Digital image watermarking in the wavelet transform domain"// Salzburg, am 11. Janner 2001.

56. Po-Chyi Su, C.-C. Jay Kuo "An Image watermarking scheme to resist generalized geometrical transformation"// Integrated Media System Center and Department of electrical engineering System.

57. Ronald A. DeVore, Bradly J. Lucier "Image compression trough wavelet transform" // IEEE Transaction of information theory Vol. 38, No.2, March 1992.

58. Sara Brooks and Mohammad Tabbara "Wavelet Image Compression : A Heuristic Approach to Space Frequency Quantisation"// Department of Electrical and Electronic Engineering The University of Melbourne

59. Scott Craver, Nasir Memon, Boon-Lock Yeo, and Minerva M. Yeung. "Can invisible watermarks resolve rightful ownerships?"// Technical Report 20509, IBM Research Report, July 1996.

60. Suzanne Bunton "On-Line Stochastic Processes in Data Compression" // University of Washington; 1996

61. Sven Ole Aase "Image subband coding artifacts:analysis and remedies"// The department of electrical and computer engineering of the norwegian institute of technology; March 1993

62. Trac Duy Tran "Linear phase perfect reconstruction filter banks: theory, structure, design, and application in image compression "// university of Wisconsin — madison 1999

63. Valens C., "Embedded Zerotree Wavelet Encoding"// 1999.

64. Vasily Strela M.Sc., Moscow Institute of Physics and Technology -"Multiwavelets: Theory and Applications"// massachusetts institute of technology June 1996

65. Vicius Licks "On digital image watermarking robust to geometric transformation"// THESIS; B.S., Control Engineering, Pontificia University.

66. Vivek K Goyal "Beyond Traditional Transform Coding"// Engineering|Electrical Engineering and Computer Sciences in the graduate division of the university of california, berkeley, 1999.

67. Voloshynovskiy S., Pereira S. "Attacks on digital watermarks: classification, estimation-based attacks and benchmarks"// University of Geneva.

68. Walter Bender, Daniel Gruhl, Norishige Morimoto, and Anthony Lu. "Techniques for data hiding."// IBM Systems Journal, 35:313-336, 1996.

69. Wee Sun Lee "Trees, Windows and Tiles for Wavelet Image Compression"// Department of Computer Science, School of Computing, National University of Singapore, Singapore 117543.

70. Wim Sweldens "The construction and application of wavelets in numerical analysis"//May 18, 1995.