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

Введение.

Глава 1. Стандартный алгоритм фрактального сжатия изображений.

1.1. Изображение - неподвижная точка сжимающего оператора

1.2. if - сходимость модели изображения

1.3. Вычисление параметров кодирования.

1.4. Дискретное представление изображения . зз

1.5. Алгоритм кодирования Хатчинсона

1.6. Программная реализация алгоритма кодирования Хатчинсона

1.7. Результаты экспериментов

Глава 2. Классификация площадок изображения. Построение фрактальных баз.

2.1. Классификация архетипов.

2.2. Основные требования, предъявляемые к фрактальным базам.

2.3. Кодирование, раскодирование изображений.

2.4. Сферическая классификация полутоновых площадок (S-классификация)

2.5. Обучение фрактальной базы. Процесс построения искусственной и естественной фрактальных баз

2.6. Результаты экспериментов

Глава 3. Улучшение качества изображений за счет введения дисперсионных классификаций.

3.1. Приближение изображения тремя базисными площадками

3.2. Дисперсионные классификации полутоновых площадок.

3.3. SVO-классификация в условиях задачи приближения тремя базисными функциями

3.4. SW-классификация в условиях задачи приближения тремя базисными функциями

3.5. Описание комплекса программ для сжатия полноцветных (truecolor) изображений. Результаты вычислительных экспериментов

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

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

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

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

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

В настоящее время разработаны эффективные методы архивации данных. Эти алгоритмы кодируют данные без потери информации. Их принцип основан на замене часто повторяющихся последовательностей короткими кодами (кодирование по алгоритму Хаффмана или Лемпеля-Зива) [39] . Алгоритмы архивации эффективны при сжатии текстов (наиболее часто повторяющиеся слова и буквы кодируются короткими кодами). Их можно использовать для сжатия монохромных изображений в формате PICT [44], так как зачастую они обладают избыточной информацией и содержат фон. Полутоновые и цветные изображения также архивируют с помощью этих алгоритмов, хотя и с меньшим успехом. Наконец, данные алгоритмы совсем не эффективны, если необходимо сжимать вещественные данные (упаковка вещественных таблиц, сжатие экспериментальных данных).

Поэтому для сжатия экспериментальных зависимостей, полутоновых и цветных изображений используются вычислительные алгоритмы, в которых допускается определенный уровень потери информации. Вычислительные алгоритмы такого типа условно разбивают на пять групп [32]: алгоритмы интерполирования и экстраполяции, алгоритмы импульсно-кодовой модуляции (ИКМ), алгоритмы с предсказанием (ДИКМ), алгоритмы посредством преобразований (Корунена-Лоэва, Фурье, вейвлет-технологии), гибридные схемы (JPEG).

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

Возможно кодирование сигналов и изображений при помощи импульсно-кодовой модуляции. Впервые для телевизионных сигналов этот метод был использован Гудоллом [28] в 1951 году. Принцип ИКМ заключается в дискретизации сигнала (обычно с частотой Найквиста [2]) и АГ-уровневом квантовании каждого отсчета. Каждый уровень представляется двоичным словом, содержащим М бит (Ы=2М) . При раскодировании эти слова преобразуются в дискретные значения амплитуды, и полученная последовательность значений подвергается фильтрации нижних частот.

Для изображений широко распространен метод сжатия данных в пространственной области — метод дифференциальной импульсно-кодовой модуляции (ДИКМ) [21, 32]. Этот подход связан с методами теории предсказания. Вначале формируется оценка яркости точки в виде линейной комбинации яркостей предшествующих точек (сверху вниз, слева направо) с соответствующими коэффициентами предсказания: г), п = 3. Кодируется 1 квантованная разность между реальным значением яркости и ее оценкой. Выбор оптимальных коэффициентов предсказания а, в данном методе является достаточно сложной и трудоемкой задачей, так как оптимальные коэффициенты зависят от взаимосвязей точек в изображении описываемых автокорреляционной функцией. При использовании этого метода могут появляться ошибки на границах изображаемых предметов, где процесс нестационарен. Возникает необходимость аппроксимировать нестационарные статистические характеристики изображений стационарными функциями. Этот метод сжатия эффективен для изображений [43] с небольшим количеством деталей, у которого не слишком часто происходит резкое изменение яркостей изображения.

Разновидностью сжатия данных является цифровая фильтрация (низкочастотная, полосовая), поскольку она приводит к выделению ограниченной части спектра [2, 16, 26] . Фильтрация может применяться для предварительной обработки до применения специальных алгоритмов сжатия данных [17, 28] . Некоторые алгоритмы фильтрации (обратные фильтры) позволяют восстанавливать искаженные данные [19, 24] .

К группе алгоритмов, выполняющих сжатие в области преобразований, можно отнести алгоритмы на основе быстрых преобразований Фурье, Адамара, Хаара и др. [1, 5, 9] . Методы сжатия в этих алгоритмах основаны на частотном анализе данных. Так, например, для изображений известно, что обычно их структура носит низкочастотный характер. Сохраняя низкочастотные составляющие, на которые приходится обычно практически вся энергия изображения и достаточно много высокочастотных компонент, чтобы резкость изображения была приемлема для человеческого глаза, можно добиться существенного уменьшения объема избыточной информации.

Но, к сожалению, сжатие в частотной области может приводить к резкому перепаду частот и появлению осцилляций в частотной характеристике. Возникают, так называемые эффекты Гиббса [2], которые, в свою очередь, приводят к заметным ошибкам при восстановлении данных. Использование периодических функций при разложении непериодической приводит к искажению данных на границах. Было [42] проведено сравнение алгоритмов типа БПФ с другими алгоритмами (преобразованием Карунена-Лоэвы, слэнт-преобразованием). Оказалось, что алгоритмы типа БПФ проигрывают и в оптимальности сжатия и по критериям качества (для оценки была взята среднеквадратическая ошибка). К этой же группе относится алгоритм на основе преобразования Карунена-Лоэва [42] . Для сжатия переходят в новые системы координат, основанные на собственных значениях и собственных векторах ковариационной матрицы обрабатываемого изображения. Это позволяет использовать массив данных с более удобными свойствами. Метод сжатия достаточно эффективен, но, к сожалению, объем вычислений весьма велик.

Оригинальный метод сжатия изображений, не относящийся ни к одной из описанных выше групп, но успешно применяющийся в последнее время является метод фрактального сжатия изображений [34]. Этот метод сжатия основан на том, что по Мандельброту [31] можно имитировать структуры, из которых состоит изображение, и с помощью рекурсивных процедур создавать из них изображения. По Мандельброту, термин фрактал обозначает структуру, обладающую схожими формами разных размеров. Используя фракталы (масштабируемые картинки, созданные с помощью компьютерной программы), а также аффинные преобразования, которые выполняют вращение, сжатие, расширение объектов изображения, можно создать фрактальную версию изображения. Эта процедура сейчас полностью формализована и запатентована фирмой Iterated Systems в 19 91 году. Главным недостатком этой процедуры является высокая вычислительная трудоемкость процесса кодирования изображения, например время кодирования цветных полноцветных (24-бит на пиксел) изображений может достигать более 12 часов. Ясно, что в режиме реального времени этот алгоритм применять для кодирования изображений невозможно. В связи с этим неоднократно стали разрабатываться некоторые модификации этого алгоритма.

Эффективный алгоритм сжатия JPEG [44] в 1990 году был разработан Объединенной группой экспертов в области фотографии (США, Израиль, Франция, Германия, Япония). Практически с первых дней своего существования он завоевал всеобщее признание как стандарт сжатия для неподвижных изображений [10, 11]. В основе этого алгоритма лежит зонная обработка блоков 8x8 пикселов. Вся обработка выполняется в частотной области, для перехода в которую выполняется дискретное косинус-преобразование (ДКП). В зависимости от коэффициента сжатия устанавливается степень потери информации. Данный алгоритм позволяет сжимать как полутоновые, так и цветные изображения, но их реализация усложняется изза наличия трех цветовых сигналов в изображениях. Каждый элемент изображения (пиксел) представляет собой вектор состоящий из трех компонент RED, GREEN, BLUE. Объем информации возрастает при этом в три раза. К сожалению, цветовая модель RGB не очень эффективна для сжатия, так как ее компоненты не отражают степень важности при воспроизведении изображения.

Поэтому в алгоритме JPEG для сжатия цветных изображений переходят к другой цветовой модели YUV телевизионного стандарта PAL [27]. Эта цветовая модель, также как и другие (SECAM [27], NTSC[27, 30]) были разработаны специалистами в области телевидения для передачи цветных изображений. В этих цветовых моделях выделяется главная компонента Y, отвечающая за яркость изображения, она и изображается на экране черно-белого телевизора. Во всех трех моделях эта компонента одинакова и меньше всего подвергается сжатию, так как несет основную информацию. В телевидении для ее передачи выделяется более широкая полоса частот. Две другие компоненты содержат информацию о цвете, то есть тон и насыщенность. В разных моделях они выделяются по-разному. Эти компоненты сильнее подвергаются сжатию, чем компонента Y. В телевидении для их передачи используют более узкую полосу частот. В этих цветовых моделях используется свойство человеческого зрения, которое более чувствительно к изменениям яркости, чем переменам цветового тона и насыщенности. Цель данной работы — Разработать быстрые алгоритмы классификации площадок изображений, на основе которых создать прикладные фрактальные базы для кодирования изображений. Сравнить полученные характеристики сжатия (время кодирования, качество, степень компрессии) с JPEG - стандартом.

Научная новизна. В диссертационной работе впервые разработаны алгоритмы выпуклой классификации площадок изображений и построения фрактальных баз, позволяющие с приемлемым уровнем качества (выше 30 dB) сжимать полноцветные и полутоновые изображения в 1.5-2 раза лучше JPEG - стандарта кодирования в режиме реального времени.

Структура и объем диссертации. Диссертация состоит из введения, трех глав, содержащих 17 разделов, заключения, и списка литературы из 42 наименований. Объем работы 112 машинописных страниц, включая 11

Заключение

Перечислим основные результаты диссертационной работы.

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

2. Разработана сферическая классификация полутоновых площадок изображений, позволяющая создавать фрактальные базы на конкретных изображениях (естественные фрактальные базы), и также строить искусственные фрактальные базы. Проведены численные эксперименты по сравнению качества кодирования искусственными фрактальными базами и естественными. Эксперимент показал, что применение искусственных сферических фрактальных баз не ухудшает восстанавливаемое изображение. Проведены численные эксперименты по сравнению разработанного алгоритма сферической классификации с алгоритмом Хатчинсона., в результате которых получено ускорение кодирования в 90 раз, увеличение качества изображения с 21dB до 2 6dB. Эксперименты показали, что кодирование с применением сферических фрактальных баз дает коэффициент компрессии в два раза лучший, чем JPEG - стандарт.

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

1. Бакланова O.E. Пакет программ для обработки изображения быстрым преобразованием свертки на многопроцессорном вычислительном комплексе. — В сб. Комплексы программ мат. физики. Красноярск, 1989, с.51-60.

2. Бакланова O.E., Зюзин М.В., Люляков A.B. О реализации параллельных алгоритмов цифровой фильтрации. Автометрия, 1988, N6, с.3-9.

3. Бакланова O.E., Зюзин М.В. О зависимости скорости реализации фильтров от вида частотных характеристик. В сб. Вариационно-разностные методы в задачах численного анализа. Новосибирск,1988, с.37-43 .

4. Бакланова O.E., Зюзин М.В. Численные методы решения уравнений типа свертки на параллельных системах. Тез. докл. Зшк. семинара по численным методам для высокопроизводительных систем. Фрунзе, 1988, с.14.

5. Ваганова H.A. Описание программного комплекса по фрактальному сжатию изображений. Труды XXXVIII Международной научной студенческой конференции «Студент и научно-технический прогресс»: Новосиб.ун-т, Новосибирск, 2000.

6. H.A. Ваганова Построение дисперсионной и сферической фрактальных баз для задачи кодирования изображений. Вестник Новосибирского Государственного Университета, серия: математика, механика, информатика, N1,2001

7. Ваганова H.A. Фрактальное сжатие изображений. Материалы XXXVII Международной научной студенческой конференции «Студент и научно-технический прогресс»: Информационные технологии / Новосиб. ун-т, Новосибирск, 1999.

8. В.А. Василенко. Тензорные сплайн-аппроксимации в задачах подавления артефактов на восстановленных изображениях, Новосибирск, ИМСОРАН, (2001) , Тезисы докладов сибирской конференции "Методы сплайн-функций", стр. 28.

9. Д.И. Ватолин. Тенденции развития алгоритмов сжатия статистических растровых изображений.// Открытые системы, Open Systems Publishing House, Москва, 4(12), 1995.

10. Ф.Р. Гантмахер. Теория матриц, М:Наука, 1967, стр.354-355

11. Даджион Д., Мерсеро Р. Цифровая обработка многомерных сигналов. М.:Мир, 1988.-487с.

12. Каппелини В., Константенидис А.Дж., Эмилиани П. Цифровые фильтры и их применение.— М.,Энергоатомиздат, 1983, — 360с.

13. А.Н. Колмогоров, C.B. Фомин, Элементы теории функций и функционального анализа. М.: Наука, 1981, стр. 74-78.

14. Кортман. Сокращение избыточности как практический метод сжатия. ТИИЭР, 1967, т.55, N3, с 8-20.

15. Кривошеев М.И. Основы телевизионных измерений. М.: Радио и связь, 1989. 608с.

16. Макхол Ж. Линейное предсказание. Обзор. ТИИЭР, 1975, т.63, N4, с.20-45.

17. Нетравали А.Н., Лимб Дж. О. Кодирование изображений: Обзор. ТИИЭР, Март 1980, т. 68, N3, стр. 76-124.

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

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

20. Прэтт В. Цифровая обработка изображений. М.:Мир, 1978.-848с.

21. Рабинер Л., Голд Б. Теория и применение цифровой обработки сигналов. М.:Мир, 1978.-478с.

22. Сейтер Ч. Сжатие данных. Мир ПК, 1991, N2, с.46-59 .

23. Харкевич A.A. Спектры и анализ. М.:Физматгиз, 1982.-236с.

24. Хочман, Кацман, Вебер. Сжатие полосы телевизионныхсигналов за счет сокращения избыточности. — ТИИЭР, 1967, т.55, N3, с.21-25.

25. Эндрюс Г. Применение вычислительных машин для обработки изображений. М.:Энергия,1987 .

26. Michael Barnsley, Fractals Everywhere, Academic Press, Boston, 1988.

27. R. D. Boss and E. W. Jacobs. Archetype classification in an iterated transformation image compression algorithm. In Y. Fisher, editor, Fractal Image Compression: Theory and Application, chapter 4, pages 79-90. Springer-Verlag, New York, NY, USA, 1995.

28. Y. Fisher. A discussion of fractal image compression. In H.-O. Peitgen, H. Jiirgens, and D. Saupe, editors, Chaos and Fractals: New Frontiers of Science, appendix A, pages 903-919. Springer-Verlag, New York, NY, USA, 1992.

29. Y. Fisher, E. W. Jacobs, and R. D. Boss. Fractal image compression using iterated transforms. In J. A. Storer, editor, Image and Text Compression, chapter~2, pages 35-61. Kluwer Academic Publishers, Norwell, MA, USA, 1992.

30. Yuval Fisher. Fractal Image Compression. Springer Verlag, New York, 1994

31. Goodall Television by pulse code modulation. — Bell Syst. Tech. J., Jan. 1951, vol.30, p. 33-49.

32. John E. Hutchinson, Fractals and Self Similarity, Indiana University Mathematics Journal, Vol. 30, No. 5, 1981, pp. 713-747.

33. A. E. Jacquin. Image coding based on a fractal theory of iterated contractive image transformations. IEEE Transactions on Image Processing, 1(1):18-30, January 1992.

34. Y. Linde, A. Buzo, and R.M. Gray. An algorithm for vector quantizer design, IEEE Trans. On Communications, COM-28(1):84-85, January 1980.

35. S. P. Lloyd. Least squares quantization in PCM, IEEE Trans. Information Theory, IT-28:127-135, March 1982.

36. Mandelbrot B. The fractal geometry of nature. -W.H. Freeman and Co., NY,1977.

37. Pritchard D.H. U.S. Color Television Fundamentals

38. A Review, IEEE Transactions on Consumer Electronics, CE-23 (4), Nov. 1977, p.467-478.

39. N. A. Vaganova, V.A. Vasilenko Fast coding-decoding algorithm in fractal image compression via spherical range classification. Bulletin of the Novosibirsk Computing Center, series: Numerical Analysis, issue: 9(2000), NCC Publisher.

40. Vasilenko V.A., Vaganova N. A. Fractal base construction for image compression. Proceeding and Abstracts of 2001 Far-Eastern School-Seminar on Mathematical Modeling and Numerical Analysis (FESS-MMNA'01). Edited by Victor Rukavishnikov. Pp. 207-209.

41. Wallace G.K. Overview of the JPEG (ISO/CCITT) still image compression standard. Image Processing Algorithms and Techniques. Proceeding of the SPIE,

42. Feb. 1990, vol. 1244, p.220-233.

43. Wallage G.K. The JPEG still picture compression standard. Communication of ACM, April, 1991, vol.34, No 4, p.30-44.

44. Мюррей Д., Райпер У. Энциклопедия форматов графических файлов. Пер. с англ. К. ¡Издательская группа BHV, 1977.