Содержание к диссертации
Введение
Глава 1. Стандартный алгоритм фрактального сжатия изображений 19
1.1. Изображение - неподвижная точка сжимающего оператора 19
1.2. \Р - сходимость модели изображения 24
1.3. Вычисление параметров кодирования 30
1.4. Дискретное представление изображения 33
1.5. Алгоритм кодирования Хатчинсона 39
1.6. Программная реализация алгоритма кодирования Хатчинсона 45
1.7. Результаты экспериментов 52
Глава 2. Классификация площадок изображения. Построение фрактальных баз 61
2.1. Классификация архетипов 62
2.2. Основные требования, предъявляемые к фрактальньм базам . 65
2.3. Кодирование, раскодирование изображений 67
2.4. Сферическая классификация полутоновых площадок (S-классификация) 70
2.5. Обучение фрактальной базы. Процесс построения искусственной и естественной фрактальных баз 75
2.6. Результаты экспериментов 78
Глава 3. Улучшение качества изображений за счет введения дисперсионных классификаций 83
3.1. Приближение изображения тремя базисными площадками 83
3.2. Дисперсионные классификации полутоновых площадок 86
3.3. SVO-классификация в условиях задачи приближения тремя базисными функциями 89
3.4. SW-классификация в условиях задачи приближения тремя базисными функциями 92
3.5. Описание комплекса программ для сжатия полноцветных (truecolor) изображений. Результаты вычислительных экспериментов 95
Заключение 105
Литература 107
- \Р - сходимость модели изображения
- Программная реализация алгоритма кодирования Хатчинсона
- Основные требования, предъявляемые к фрактальньм базам
- SVO-классификация в условиях задачи приближения тремя базисными функциями
Введение к работе
Актуальность темы. Новейшие технологии, возникшие на стыке электросвязи и компьютерной техники, стали в технически передовых странах источником и основой исследований и разработок в области создания принципиально новых цифровых телекоммуникационных систем, способных при необходимости, предоставить пользователю практически любые информационные услуги.
Преимущество цифровой передачи сигналов с точки зрения ее помехоустойчивости и качества воспроизведения информации общеизвестно.
Однако для передачи цифровой информации без использования специальных процедур ее сжатия требуется существенное увеличение пропускной способности каналов связи, что влечет за собой разрушение действующих частотных стандартов, принятых для различных систем передачи информации.
Фундаментальной проблемой создания цифровых систем является сокращение избыточности информации. Разработка эффективных способов и устройств сжатия и рациональной упаковки видео- и звуковой информации является предпосылкой более эффективного использования каналов связи, обеспечивая не только сохранение действующих частотных стандартов, но и высвобождение значительной части частотного пространства для передачи потребителям дополнительных видов услуг — многопрограммного телевидения, телевидения высокой четкости, многопрограммного звукового вещания, организацию интерактивных систем связи, более качественную передачу графической информации при видеотелефонной связи, видеоконференциях и др.
Цифровая обработка изображений важна тем, что является по сути основой создания нового поколения телевизионной техники.
В настоящее время разработаны эффективные методы архивации данных. Эти алгоритмы кодируют данные без потери информации. Их принцип основан на замене часто повторяющихся последовательностей короткими кодами (кодирование по алгоритму Хаффмана или Лемпеля-Зива) [39]. Алгоритмы архивации эффективны при сжатии текстов (наиболее часто повторяющиеся слова и буквы кодируются короткими кодами). Их можно использовать для сжатия монохромных изображений в формате РІСТ [44], так как зачастую они обладают избыточной информацией и содержат фон. Полутоновые и цветные изображения также архивируют с помощью этих алгоритмов, хотя и с меньшим успехом. Наконец, данные алгоритмы совсем не эффективны, если необходимо сжимать вещественные данные (упаковка вещественных таблиц, сжатие экспериментальных данных).
Поэтому для сжатия экспериментальных зависимостей, полутоновых и цветных изображений используются вычислительные алгоритмы, в которых допускается определенный уровень потери информации. Вычислительные алгоритмы такого типа условно разбивают на пять групп [32]: алгоритмы интерполирования и экстраполяции, алгоритмы импульсно-кодовой модуляции (ИКМ), алгоритмы с предсказанием (ДИКМ), алгоритмы посредством преобразований (Корунена-Лоэва, Фурье, вейвлет-технологии), гибридные схемы (JPEG). Алгоритмы интерполяционного, экстраполяционного кодирования используются для кодирования экспериментальных данных или изображений. При интерполяционном кодировании передаются лишь некоторые отсчеты или элементы изображений, а остальные вычисляются при помощи интерполяции, экстраполяции. Развернутый анализ методов интерполяционного кодирования изложен в работах [б, 25]. Возможно кодирование сигналов и изображений при помощи импульсно-кодовой модуляции. Впервые для телевизионных сигналов этот метод был использован Гудоллом [28] в 1951 году. Принцип ИКМ заключается в дискретизации сигнала (обычно с частотой Найквиста [2]) и АГ-уровневом квантовании каждого отсчета. Каждый уровень представляется двоичным словом, содержащим М бит (N=2M) . При раскодировании эти слова преобразуются в дискретные значения амплитуды, и полученная последовательность значений подвергается фильтрации нижних частот. Для изображений широко распространен метод сжатия данных в пространственной области — метод дифференциальной импульсно-кодовой модуляции (ДИКМ) [21, 32]. Этот подход связан с методами теории предсказания. Вначале формируется оценка яркости точки в виде линейной комбинации яркостей предшествующих точек (сверху вниз, слева направо) с соответствующими коэффициентами предсказания: ОС (к-і), п = 3. Кодируется квантованная разность между реальным значением яркости и ее оценкой. Выбор оптимальных коэффициентов предсказания а, в данном методе является достаточно сложной и трудоемкой задачей, так как оптимальные коэффициенты зависят от взаимосвязей точек в изображении описываемых автокорреляционной функцией. При использовании этого метода могут появляться ошибки на границах изображаемых предметов, где процесс нестационарен. Возникает необходимость аппроксимировать нестационарные статистические характеристики изображений стационарными функциями. Этот метод сжатия эффективен для изображений [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 таблиц и 25 рисунков. Краткое содержание работы
Во введении дается обзор литературы по основным направлениям сжатия изображений, описаны тенденции развития алгоритмов сжатия статистических растровых изображений, сформулирована основная цель работы и краткое содержание диссертации по главам. Первая глава посвящена основам фрактального сжатия изображений. Пусть для некоторых a,beR
/) =( = ( , х2)є R :0 x{ a, 0 x2 b }, тогда под пространством всех изображений будем понимать / (D-) . Идея задачи фрактального сжатия заключается в нахождении для заданного изображения /є/, (0 ) сжимающего оператора т :/ (/) ) / (/) такого, что / является его неподвижной точкой, то есть т (/) = /. Будем искать приближенное решение задачи (оператор т=т ) .
Согласно принципу сжимающих отображений в полном метрическом пространстве последовательность итераций сходится к /цЄІ Фх): r(fN) = fN.
Если для заданного изображения /е [ (D ) построен оператор т такой, что Р(т(/), /) , то для последовательности итераций восстановления изображений имеем.
В разделе 1.5 приведен алгоритм кодирования Хатчинсона, вычислена трудоемкость этого алгоритма, описана модификация алгоритма.
В разделе 1. б рассматривается программная реализация модифицированного алгоритма кодирования Хатчинсона. В разделе 1.7 приведены результаты апробации комплекса на конкретных изображениях.
Во второй главе для кодирования (аппроксимации) дискретного изображения f(x)e L i Dj) предлагается использовать площадки, взятые с других изображений (хранимые отдельно в виде фрактальных баз). Восстановление изображения в этом случае представляет собой мозаику элементов фрактальной базы. Для построения фрактальных баз предложена сферическая классификация полутоновых площадок изображений, которая заключается в следующем. Пусть R = \r(i, j)\. ., - произвольная площадка изображения, N = 2t,t 2, (r(i, j) - интенсивность пиксела), комбинация площадок одного класса порождает площадку того же самого класса. На этом свойстве построен процесс обучения фрактальных баз, описанный в разделе 2.5. Кроме того, фрактальную базу можно строить искусственной, взяв в качестве фрактала класса Кц
проинтерполированные значения пикселов, соответствующие геометрическим центрам площадок, полученных в результате разбиения сферы.
В разделе 2.б описаны эксперименты применения разработанного алгоритма сферической классификации и построения искусственных и естественных фрактальных баз.
В третьей главе с целью улучшения качества кодирования изображения предложено кодируемую площадку изображения приближать двумя фракталами из разных баз, один из которых имеет заданные средние интенсивности квадрантов (определяется по сферической классификации), другой имеет нулевые средние интенсивности квадрантов и заданные дисперсии, либо заданные отношения дисперсии квадрантов площадки.
Кроме того, представлены экспериментальные графические данные: фотография исходного цветного изображения, его три полутоновые составляющие, результат JPEG кодирования, восстановленное изображение и результат восстановления полутоновых компонент этого изображения. В разделе 3.1 для вычисления параметров кодирования (J,(Pi,0),(p:,h площадки R в условиях уже построенных двух фрактальных баз минимизируется расстояние.
Задаваемые дисперсии квадрантов в первом случае выбираются по уже созданным фракталам сферической базы, во-втором, выбираются из условий ограниченности дисперсий квадрантов, посредством введения сетки по переменным dlt d2, d$, dA .
В разделе описаны проведенные эксперименты применения для кодирования разработанных фрактальных баз, в результате которых получен коэффициент сжатия в полтора-два раза лучше, чем у JPEG при одинаковом качестве кодирования 30dB.
Пользуясь случаем, автор выражает искреннюю благодарность научным руководителям:
д.ф.-м.н. В.А. Василенко, д.ф.-м.н. A.M. Мацокину за постоянное внимание, предложенную тему диссертации, полезные обсуждения в процессе работы и руководство работой, к.ф.-м.н. А.Ю. Бежаеву за полезные замечания в программной реализации работы.
Список работ по теме диссертации
1. Ваганова Н.А., Василенко В.А. Алгоритм
формирования фрактальных баз для сжатия изображений.
Четвертый сибирский конгресс по прикладной и индустриальной математике, посвященный памяти М.А. Лаврентьева (1900-1980): Тез. докл., ч.ІІ. Новосибирск: Изд-во Ин-та математики, 2000.
Ваганова Н.А. Классификации блоков изображений при фрактальном сжатии. Тезисы докладов конференции молодых ученых по математике, математическому моделированию и информатике, Новосибирск, Институт вычислительных технологий, 2001, стр. 4 4-46
Ваганова Н.А. Описание программного комплекса по фрактальному сжатию изображений. Труды XXXVIII Международной научной студенческой конференции «Студент и научно-технический прогресс»: Новосиб. ун-т, Новосибирск, 2000.
Ваганова Н.А. Построение дисперсионной и сферической фрактальных баз для задачи кодирования изображений. Вестник Новосибирского Государственного Университета, серия: математика, механика, информатика, N1,2001
Ваганова Н.А. Построение дисперсионной и сферической фрактальных баз для задачи кодирования изображений. Сибирская конференция «Методы сплайн-функций», посвященной памяти Ю.С. Завьялова. Тез. докл. Новосибирск: Изд-во Института математики, 2001, стр. 26-27
Ваганова Н.А. Сплайн-интерполяция по локальным средним в задачах обработки медицинских изображений. Тезисы докладов II объединенной научной сессии СО РАН и СО РАМН, Новые технологии в медицине, 18-19 июня 2002, Новосибирск, 2002. 7. Ваганова Н.А. Улучшение качества фрактального сжатия изображений за счет введения дисперсионных баз. Труды конференции молодых ученых ИВМиМГ, 2001, стр.1-11.
8. Ваганова Н.А. Фрактальное сжатие изображений. Материалы XXXVII Международной научной студенческой конференции «Студент и научно-технический прогресс»: Информационные технологии/Новосиб. ун-т, Новосибирск, 1999.
9. Vaganova N.A., Vasilenko V.A. 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.
10. Vaganova N.A. The image postprocessing by local average integrals for fractal image compression. Proceedings of the International Conference on Computational Mathematics, Novosibirsk, 2002.
11. 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. Khabarovsk, 2001.
Апробация работы. Основные результаты диссертации докладывались на
• XXXVII Международной научной студенческой конференции «Студент и научно-технический прогресс», Новосибирск, 1999. • XXXVIII Международной научной студенческой конференции «Студент и научно-технический прогресс», Новосибирск, 2000;
• конференции молодых ученых ИВМ и МГ СОРАН, Новосибирск, 2001.
• Сибирской конференции «Методы сплайн-функций», Новосибирск, 2001;
• Четвертом сибирском конгрессе по прикладной и индустриальной математике (ИНПРИМ-2000), посвященном памяти М.А. Лаврентьева, Новосибирск, 2000;
• Дальневосточной школе по математическому моделированию и численному анализу, Находка, 2001.
• Конференции молодых ученых СОРАН по математике, математическому моделированию и информатике, Новосибирск, 4-7 декабря, 2001.
• Конкурсе молодых ученых, организованном компанией САМСУНГ при поддержке Сибирского отделения Российской Академии Наук, Новосибирск, 13-14 июня 2002 года.
• 11-ой объединенной научной сессии Сибирского отделения Российской академии наук и Сибирского отделения Российской академии медицинских наук «НОВЫЕ ТЕХНОЛОГИИ В МЕДИЦИНЕ», Новосибирск, 18-19 июня 2002 года
• Международной конференции по вычислительной математике (ICCM-2002), Новосибирск, 24-28 июня 2002
\Р - сходимость модели изображения
Отличным [11] считается качество, при котором невозможно на глаз различить первоначальное и разархивированное изображение (уровень PSNR свыше 35 dB) , хорошим - когда определить, которое из изображений подвергалось архивации, можно только сравнивая две находящиеся рядом картинки (30-35 dB).
В целом отметим, что алгоритмы архивации с потерями не рекомендуется использовать при сжатии изображений, которые в дальнейшем собираются либо печатать с высоким качеством, либо обрабатывать программами распознавания образов. Неприятные эффекты могут возникнуть даже при простом масштабировании изображения. В дальнейшем все цифровые характеристики качества изображений, полученных в вычислительных экспериментах, будут даны в шкале PSNR.
Для проверки эффективности разработанной сферической классификации полутоновых площадок был модифицирован комплекс программ по фрактальному сжатию. Алгоритм тестировался на рентгенограммах (полутоновые изображения с 65536 градациями серого цвета) и полутоновых изображениях с 256 градациями серого. Эксперимент 2.1. Сжатие рентгенографического изображения при помощи естественной сферической базы, построенной на рентгенограммах, отличных от сжимаемого изображения. Размер фрактальной базы был выбран 256 фракталов, с учетом образования приблизительно одинаковых по размеру площадок на сфере. Кодируемое изображение разбивалось на квадратные площадки размера 8x8 пикселов. Фрактальная база была обучена на рентгенограммах и применена для сжатия рентгенограмм, не участвующих в обучении фрактальной базы. Средний коэффициент сжатия составил 2:1 по отношению к JPEG алгоритму, т.е. в 2 раза лучше. Время кодирования одного изображения оказалось равным 1 секунде, вместо 90 секунд по стандартному алгоритму сжатия Хатчинсона. Эксперимент 2.2. Применение искусственной фрактальной базы. Параметры разбиения изображения и сжимаемые изображения были взяты из эксперимента 1. Для кодирования изображений была построена искусственная сферическая база, содержащая 256 фракталов. Разбиение сферы площадками для чистоты эксперимента было сохранено. Центры площадок интерполировались до размеров блоков фрактальной базы при помощи кусочно-постоянной и билинейной интерполяции. Эксперименты показали, что кусочно-постоянная интерполяция не подходит для построения, так как увеличивает клетчатость восстанавливаемых изображений. Время кодирования и коэффициент сжатия остались прежними. Проведенные эксперименты (см. табл. 2.2) показали, что для сжатия изображения можно применять как искусственные, так и естественные фрактальные базы, при этом качество восстанавливаемых после сжатия изображений практически не страдает (в смысле отношения сигнал-шум). По сравнению со стандартным алгоритмом фрактального сжатия это отношение даже увеличивается с 21 до 2 6 dB.
Программная реализация алгоритма кодирования Хатчинсона
За дисперсионные характеристики фрактала класса Кіітп возьмем средние точки соответствующих интервалов. И, наконец, строим аналогично п. 3.3. фрактал с заданными дисперсиями и нулевыми средними в квадрантах.
Количество классов в дисперсионной базе равно М[ М2-Л/з М4 и может варьироваться в зависимости от нужд пользователя. Для улучшения качества кодирования, конечно, нужно строить базу как можно шире. Но в тоже время необходимо помнить, что с расширением базы, увеличивается число бит, необходимых для хранения номера фрактала, и может случиться так, что коэффициент сжатия резко пострадает. Теперь рассмотрим подробно кодирование блока изображения R . Будем считать, что сферическая и дисперсионная (WB) базы уже построены. В результате сферической классификации блоку сопоставляются номер отображения т{, номер сферического фрактала Skl . Затем вычисляются дисперсионные характеристики d{(R), d2(R), d3(R), d4(R). В результате упорядочения этих величин выявляется номер преобразования т2, а по самим значениям дисперсий блоку ставится в соответствие дисперсионный фрактал Vk2 . Рассмотренную процедуру сопоставления площадки изображения двух фракталов будем называть SVV-классификацией. Дальнейшая работа по кодированию и раскодированию в условиях SW-классификации аналогична одноименным процессам в условиях SVO-классификации, разница лишь в том, что дисперсионный блок во время раскодирования потребуется дополнительно повернуть или зеркально отразить.
Для проверки работоспособности и применения разработанных алгоритмов был написан комплекс программ для Unix-платформы на языке программирования Си. В этот комплекс вошли следующие программы: Bit3raw - разбивает цветное изображение на три полутоновых компоненты стандарта PAL; Quadroenc - кодирует одну из компонент; Quadropackcolor - упаковывает три закодированных компоненты; Quadrodepackcolor - распаковывает три компоненты; Quadrodecoder - декодирует одну из компонент в стандарт raw (PPM); Unbit3raw - производит сборку декодированных полутоновых компонент в цветное изображение; Run - скрипт, осуществляющий полный алгоритм кодирования/раскодирования цветного изображения; Quadropartition - вспомогательная программа отрисовки разбиения изображения; SbaseConstruct - строит сферическую базу; Vbaseconstruct - строит дисперсионную базу. Эксперимент 3.1. Сжатие рентгенографического изображения при помощи естественной сферической базы, построенной на рентгенограммах, отличных от сжимаемого изображения и искусственной дисперсионной базы (VOB). Размер сферической фрактальной базы был выбран 20 фракталов, с учетом образования приблизительно одинаковых по размеру площадок на сфере. Кодируемое изображение разбивалось на квадратные площадки размера 8x8 пикселов. Фрактальная база была обучена на рентгенограммах и применена для сжатия рентгенограмм, не участвующих в обучении фрактальной базы. Средний коэффициент сжатия составил 59:28 по отношению к JPEG алгоритму, т.е. почти в 2 раза лучше. Время кодирования одного изображения оказалось равным 1 секунде, вместо 90 секунд по стандартному алгоритму сжатия Хатчинсона. Качество восстанавливаемого изображения увеличилось с 2 бсІВ до 2 8dB, по отношению к применению для кодирования только естественной сферической фрактальной базы (см эксперимент 2.1), при этом немного пострадал коэффициент сжатия, и увеличилось время кодирования изображения до 1сек. (См. табл. 3.1.)
Основные требования, предъявляемые к фрактальньм базам
В описанных (см. п.2.1) способах построения фрактальных баз существенным недостатком является большое количество переборов (сравнений) площадок. Кроме того, при кодировании изображения придется сравнивать кодируемые площадки со всем множеством фракталов. Для изменения фракталов (обучения базы на изображениях, не участвующих ранее в формировании базы) потребуется знать площадки, на основе которых была получена эта база. Формально также неясно, на каких изображениях строить базу, и нет гарантии, что последующее обучение базы при помощи других изображений не ухудшит в дальнейшем качество раскодируемых изображений.
Сформулируем основные требования, предъявляемые к базам площадок. Очевидно, что классификация должна быть построена так, чтобы, во-первых, в процессе кодирования исключить или уменьшить количество переборных операций. Во-вторых, должна существовать возможность построения универсальной базы, чтобы не передавать вместе с изображением применяемую базу, в противном случае, мы только увеличим объем передаваемых данных. В-третьих, необходимо так построить процесс обучения (построения) базы, чтобы он также не вызывал переборных операций с площадками. Для этого достаточно потребовать от базы, чтобы ее классы обладали свойством выпуклости, то есть выпуклая линейная комбинация любых двух площадок заданного класса должна порождать площадку того же самого класса.
Отметим основные трудности появляющиеся при построении алгоритма создания фрактальных баз. 1)Есть ли возможность создания универсальной базы для эффективного кодирования всех изображений, полученных в различных приложениях. Под словом эффективное кодирование здесь следует понимать не только сокращение объема информации, но и, по возможности, наилучшее визуальное сохранение изображения. Может быть более разумным будет создание баз, ориентированных на конкретные приложения. 2)Самой главной на этапе построения базы является задача классификации площадок. Ведь вместе с быстрым и разумным формированием классов нам необходимо организовать быстрый поиск фракталов (центральных точек) этих классов, а значит, мы должны исключить варианты решения, связанные с переборами. Ниже предлагается подход к нахождению фрактала как средней точки класса [5,8,40]. Пусть для сжатия дано некоторое изображение F . Предварительно будем считать, что фрактальная база \С,-_=1 уже построена и, кроме того, предположим, что мы умеем классифицировать любую площадку изображения (т.е. определять фрактал из базы ей «подобный»), причем эта классификация сразу позволяет выявить геометрическое преобразование фрактала. Тогда задача кодирования состоит в следующем. Изображение F разбиваем на неперекрывающиеся блоки R:, 7 = 1, ..., М , размер которых совпадает с размером фракталов в базе. При помощи алгоритма классификации определяем класс к, к которому принадлежит конкретная площадка Rj и преобразование 0)j . Далее посредством оптимального контрастирования и подсветки фрактала к того класса Ск приблизим кодируемую площадку изображения Rj, то есть мы будем минимизировать сеточную L2 - норму функционала / :
SVO-классификация в условиях задачи приближения тремя базисными функциями
Примером обучающих площадок могут служить блоки одного размера взятые с одного или нескольких изображений. Эти площадки затем поочередно классифицируем. В каждом порождаемом классе к, фрактал Д +{ заново пересчитывается для вновь поступившей площадки R по рекуррентной формуле
После чего для того чтобы фрактал снова попал на единичную сферу его необходимо отнормировать. Так как сферическая классификация является выпуклой, то построенный таким образом фрактал будет принадлежать тому же классу, к которому принадлежали обучающие его площадки.
Заметим, что процесс обучения созданной когда-либо базы и процесс построения естественной базы тесно связаны. Для построения нужно в формуле (2.14) положить / =0. А для обучения уже существующей фрактальной базы необходимо знать статистику осреднения блоков в каждом классе к до процесса обучения, то есть значение п(к), на котором был закончен процесс построения естественной базы. Здесь фрактальную базу мы назвали естественной потому, что ее построение и обучение зависит от изображений, при помощи которых она была создана.
Очевидно, что для каждого приложения можно создать свою естественную базу, которая будет наиболее качественно приближать кодируемое изображение.
Основным недостатком естественной фрактальной базы является необходимость хранения ее в памяти компьютера. Но этот недостаток не является существенным, так как сжатие большого количества изображений компенсирует расходы на хранение не только одной фрактальной базы. Перейдем теперь к описанию процесса создания искусственной базы, который порождается сферической классификацией. Допустим, что мы уже разбили одну шестнадцатую часть (где лежат сферические характеристики) сферы на площадки одинакового размера (см. рис. 2.6).
Тогда за направляющие косинусы фрактала каждого класса можно взять центральную точку соответствующей площадки на сфере Sif пусть, например, это будет точка с координатами ( [ (к), 2 (к), з ( )) Положив 4( ) = 0 и решая систему (3.9) относительно переменных /1,/2./3 /4/ получаем
Теперь для каждого искусственного фрактала Ск мы знаем его средние значения в квадрантах. Интерполируя эти значения на весь блок, получим требуемые искусственные фракталы. Основным преимуществом искусственной фрактальной базы является то, что ее не требуется хранить, а нужно лишь быстро вычислить в момент кодирования/восстановления изображений.
Искусственная фрактальная база является универсальной для всех изображений, но ее можно также подвергнуть процессу обучения и переориентировать для работы конкретного приложения.
Сначала несколько слов о количественных характеристиках сравнения изображений. К сожалению, многие популярные способы сравнения не соответствуют ситуации. Например, если f,g - дискретные изображения разрешения MxN (/ - исходное изображение, g - восстановленное), тогда среднеквадратичное отклонение значений пикселов (-мера или root mean square - RMS) страдает при понижении яркости на 5% (глаз этого не заметит - у разных мониторов настройка яркости изменяется гораздо сильнее). В то же время изображение со "снегом" - резким изменением цвета отдельных точек, слабыми полосами или "муаром" будут признаны "почти не изменившимися". Нормакрайнє чувствительна к изменению значения лишь одного пиксела (что практически не заметно для глаза). Мера, которую сейчас используют на практике, называют мерой отношения сигнала к шуму (peako-peak signalo-noise ratio или PSNR)
Похожие диссертации на Построение и оптимизация фрактальных баз для сжатия изображений
