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

• Малыгин, Ярослав Владимирович
• кандидат физико-математических наук
• 2004

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

1 Введение

2 Фракталы

2.1 Основные понятия и определения.

2.2 Аппроксимация множеств.

2.3 Фрактальное представление монохромных изображений.

2.4 Численный алгоритм фрактального сжатия монохромного изображения.

3 Методы повышения быстродействия фрактального сжатия

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

3.2 Использование преобразования Мерсенна.

3.3 Использование многопроцессорной вычислительной техники.

4 Применение всплесков в задаче фрактального сжатия

4.1 Кратномасштабный анализ

4.2 Всплеск-фрактальное преобразование.

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

5 Поиск параметров IFS для бинарных изображений

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

Актуальность темы

Современные информационные технологии предполагают передачу и хранение больших объемов данных. Значительную часть передаваемых данных составляют графические изображения и видеоинформация. В связи с этим важную роль играют методы сжатия (т.е. компактного описания) графических изображений. Под монохромным графическим изображением будем понимать матрицу целых чисел X = о"-1, Xij = 0,2Ь — 1. Каждый элемент матрицы X определяет интенсивность свечения графического элемента (пиксела). Нулевое значение элемента соответствует чёрному цвету, а значение (2Ь — 1) — белому. Параметр 6 называется глубиной цвета и определяет количество информации, необходимое для хранения значения одного элемента. Таким образом, для хранения всего изображения X необходимо т • п • Ь бит памяти.

Если 6 = 1, такое изображение называется бинарным, т.е. в нём могут быть графические элементы только чёрного и белого цвета. Бинарное изображение также можно представить как характеристическую функцию компактного множества из R2.

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

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

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

Как видно из названия, сжатие с потерями предполагает потерю части информации при сжатии и последующем восстановлении. Использование методов сжатия с потерями ограничивается объектами, где такие потери допустимы (обработка графической, звуковой информации и т.д.). Для оценки качества восстановления используют величину PSNR (peak signal-to-noise ratio, предельное отношение сигнал-шум), измеряемую в дБ: п—1,171 — 1

Е (хч - va)2 kpsnr(x,y) = -ioig [ДВ], (i.i) где X и Y - соответственно исходное и восстановленное изображения. Качество восстановления, как правило, находится в обратной зависимости от коэффициента сжатия. Т.е. коэффициент сжатия ограничен требуемым качеством восстановления, и его значение может достигать сотни и более. В данной работе рассматриваются лишь методы сжатия с потерями.

В настоящее время для сжатия численной информации используют методы аппроксимации функций полиномами [37], рациональными дробями [5], экспонентами [32], сплайнами [26], всплесками. Одним из самых распространенных алгоритмов сжатия с потерями фотогорафических изображений является JPEG (Joint Photographie Expert Group - объединенная группа экспертов по фотографии). Этот алгоритм [31] основан на разбиении исходного изображения на фрагменты размером 8x8 пикселов. Для каждого фрагмента выполняется двумерное дискретное косинус-преобразование (ДКП) [1]. Далее происходит квантование по уровню спектра ДКП, что и определяет потери при сжатии. Коэффициенты квантования определяют, какое количество данных теряется и, следовательно, коэффициент сжатия и качество восстановленного изображения. Для получения окончательного результата выходные данные квантования без потерь упаковываются с использованием какого-либо статистического метода кодирования. Таким методом может быть арифметическое кодирования, либо кодирования по методу Хаффмана [8], [20].

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

Самое общее понятие фрактала можно дать следующим образом: это такой объект, который при сколь угодно большом увеличении (рассмотрении все меньших фрагментов) сохраняет неизменной степень своей детализации (визуальной сложности). Классический пример фрактала — береговая линия. Если выбрать некоторый участок берегового контура, например, на карте с мелким масштабом, а затем увеличивать этот участок (использовать карты со все более крупным масштабом), то можно увидеть, как появляются все новые и новые детали. При больших увеличениях географических карт будет недостаточно, и придется воспользоваться фотографиями. Камни и песок, составляющие береговую линию, издали кажутся гладкими, но пр дальнейшем увеличении и они будут состоять из различных "шероховатостей". Ни при каком увеличении не будет наблюдаться тенденции к сглаживанию береговой линии. Фрактальные методы сжатия основаны на предположении Б. Мандельброта о глобальной "самопохожести" (масштабной инвариантности) многих естественных объектов [17]. Это означает, что различные части объекта оказываются похожими друг на друга или на весь объект в целом.

Цель работы

Целью представленной диссертационной работы является:

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

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

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

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

Научная новизна работы

В данной работе впервые предложено использовать:

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

• преобразование Мерсенна для ускорения процесса фрактального сжатия.

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

Апробация работы Основные результаты диссертации докладывались на:

Молодежной конференции "Проблемы теоретической и прикладной математики". Екатеринбург: УрО РАН, 1997, 1999, 2000г.

Школе-конференции им. С.Б.Стечкина по теории приближения функции, Миасс, 1998, 1999, 2000, 2003г.

Сессиях молодых ученых ИММ УрО РАН.

Расширенном семинаре "Параллельные вычисления"ИММ УрО

Исследования, проведенные по теме диссертации, поддержаны грантами РФФИ №96-01-00121, №99-01-00460 и №02-01-00782, а также грантом "Ведущие научные школы РФФИ" №00-15-96035.

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

Диссертация состоит из введения, четырех глав основного текста и заключения, в котором перечислены основные полученные результаты. Объем диссертации составляет 73 страницы. Библиография включает 38 наименований. Диссертация содержит 23 рисунка и 3 таблицы.

Заключение диссертации по теме «Вычислительная математика», Малыгин, Ярослав Владимирович

6 Заключение

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

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

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

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

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

5. Предложен метод предварительного нахождения параметров IFS для описания бинарных изображений.

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

1. Ahmed N., Natarajan T., Rao K. Discrete Cosine Transform // IEEE, Trans. Computers. 1974. Vol. C-23. P.90-93.

2. Barnsley M. Fractals Everywhere. Boston: Acad. Press, 1988. 396p.

3. Beaumont J.M. Advanced in Block Based Fractal Coding of still Pictures // Proc. of IEEE Colloquium: The Application of Fractal Techniques in Image Processing, 1990 , P. 3.1-3.6.

4. On compression and modelling of images /V.I. Berdyshev, S.V. Berdyshev, V.P. Rondrat'ev, V.B. Kostousov, Ya.V. Malygin// Russ. J. Numer. Anal, and Math. Modelling. 1996. Vol. 11, N 4, P. 275-285.

5. Cheney E.W. Introduction to approximation theory. New York: McGraw-Hill, 1966. 259p.

6. Fisher Y., Jacobs B., Boss R. Iterated Transform Image Compression// NOSC Techn. Report 1408. San Diego: Naval Ocean Systems Center (CA). April 1991. P. 1-27.

7. Fisher Y. A discussion of fractal image compression // Chaos and Fractals: New Frontiers of Science /H.-O. Peitgen, H. Jurgens, and D. Saupe, eds. New York: Springer-Verlag, 1992, P. 903-919.

8. Gersho A., Gray R. Vector Quantization and Signal Compression. Boston, MA.: Kluwer, 1992.

9. Hutchinson J. Fractals and Self-Similarity // Indiana Univ. Math. J. 1981. Vol. 30, N 5. P. 713-747.

10. Jacobs B., Boss R., Fisher Y. Image Compression: A Study of the Iterated Transform Method// Signal Processing. 1992. Vol. 29. p. 251263.

11. Jacquin A. Image Coding Based on a Fractal Theory of Iterated Contractive Image Transformations // IEEE Trans. Image Processing. 1992. Vol. 1, N 1. P. 18-30.

12. Kominek J. Convergence of fractal encoded images. Proc. DCC'95 Data Compression Conf.// IEEE Computer Society Press, March 1995.

13. Krupnik H., Malah D., Karnin E. Fractal representation of image via the discrete wavelet transform // IEEE 18-th Convention of Electrical Engineering in Israel, Tel-Aviv, March 1995.

14. Mallat S.G. A Theory for Multiresolution Signal Decomposition: The Wavelet Representation // IEEE Trans. PAMI. 1989. Vol. 5. P. 565-568.

15. Mallat S.G. Multifrequency channel decompositions of images and wavelet models // IEEE Trns. Acoust., Speech, Signal Processing. 1989. Vol. 33, Dec. P. 2099-2110,

16. Malygin Ya.V. Two Methods for Fast Fractal Compression of Images // Pattern Recognition and Image Anal. 1999. Vol. 9, N. 3, P. 448452.

17. Mandelbrot B. The Fractal Geometry of Nature. San Francisco (Calif.) :W.H. Freemam and Co, 1982. 460p.

18. Saupe D., Hamzaoui R. Complexity reduction methods for fractal image compression // Conf. Proc. on Image Processing: Math. Methods and Appl. Sept. 1994. Oxford: Oxford Univ. Press, 1994,

19. Stein M. Fractal image models and objects detection // SPIE Vol. 845. VCIP II. 1987, P. 293-300.

20. Nelson M., Gailly J. The Data Compression Book. New York: MAT Books, 1995.

21. Sweldens W. The Lifting Scheme: a Custom-design Construction of Biorthogonal Wavelets // Appl. Comput. Harmon. Anal. 1996. Vol. 3 N 2. p. 186-200.

22. Tricot C. Curves and Fractal Dimension. New York: SpringerVerlag, 1995.

23. Sweldens W. Bilding your own wavelts at home: Techn. Report 1995:5: Industrial Math. Initiative / Dep. of Math., Univ. South California, 1995.

24. Vrscay E. A Generalized Class of Fractal-Wavelet Transforms for Image Representation and Compression // Canadian J. Electrical and Computer Eng. 1998.

25. Бердышев В.И., Петрак JI.B. Аппроксимация функций, сжатие численной информации, приложения. Екатеринбург: УрО РАН, 1999. 297с.

26. Бердышев В.И., Субботин Ю.Н. Численные методы приближения функций. Свердловск: Ср.-Урал. кн. изд-во, 1979. 120с.

27. Бродин В.Б., Шагурин И.И. Микропроцессор i486. Архитектура, программирование, интерфейс. М.: Диалог-МИФИ, 1993. 240с.

28. Васильев Ф.П. Численные методы решения экстремальных заг дач: Учеб. пособие для вузов. М.: Наука, 1988. 549с.

29. Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. СПб.: БХВ-Петербург, 2002. 608с.

30. Добеши И. Десять лекций по вейвелетам. Ижевск: НИЦ "Регу-ляр. и хаотич. динамика", 2001. 164с.

31. Климов A.C. Форматы графических файлов: Киев: НИПФ "ДиаСофт Лтд." 1995. 480с.

32. Ланцош К. Практические методы прикладного анализа. М.: Физматгиз, 1961. 524с.

33. Малыгин Я.В. Поиск параметров IFS для бинарного изображения // Проблемы теорет. и прикл. математики: Тр. 33-й Регион, молодеж. конф. Екатеринбург: УрО РАН, 2002. С. 71-73.

34. Малыгин Я.В. Параллельный алгоритм фрактального сжатия графических изображений большого размера // Проблемы теорет. и прикл. математики: Тр. 34-й Регион, молодеж. конф. Екатеринбург: УрО РАН, 2003. С. 276-278.

35. Нуссбаумер Г. Быстрое преобразование Фурье и алгоритмы вычисления сверток. М.: Радио и связь, 1985. 248с.

36. Препарата Ф., Шеймос М. Вычислительная геометрия: Введение: Пер. с англ. М.: Мир, 1989. 478с.

37. Ремез. Е.Я. Основы численных методов чебышевского приближения. Киев: Наук, думка, 1969. 624с.

38. Чуй К. Введение в вэйвлеты: Пер. с англ. М.: Мир, 2001. 413с.