Фрактальное сжатие изображений.
Задание
Тема курсового проекта: Реализация в MATLAB алгоритмов построения фрактальных объектов.
Исходные данные: Журнал Exponenta Pro. Математика в приложениях. №3, 2003 г.
Основные вопросы, подлежащие исследованию:
.Применение рекурсивного алгоритма.
.Применение L-системы и терл - графики.
.Применение системы итерированных функций.
К защите представить: ·пояснительную записку объемом не менее 40 листов:
·теоретическое обоснование;
·листинг программы;
·результаты расчетов.
·электронную версию всех материалов курсового проекта;
·слайды плакатов в Ms Off PowerPoint 2003:
·тема и цель курсового проекта;
·алгоритм решения задачи;
·результаты решения задачи в виде графиков и таблиц;
·экранный вид интерфейса задачи.
Введение 1.1 Ковёр Серпинского 1.1.1 Код программы "Serpinsky.m" 1.1.2 Изображения ковра Серпинского 1.2 Квадратный ковёр Серпинского 1.2.1 Код программы "Serpinsky2.m" 2.2 Изображения ковра Серпинского 3 Кривая Коха 3.1 Код программы "Koch.m" 3.2 Изображения кривой Коха L - системы и терл - графика 1 Снежинка Коха 1.1 Код программы "RuleKoch.m" (возвращает функцию) 1.2 Код программы "Snowflake.m" (вывод изображения) 1.3 Изображение снежинки Коха 2 Дракон Хартера-Хайтвея 2.1 Код программы "Dracon.m" 2.2 Изображение дракона Хартера-Хайтвея 2.3 Изображение кривой Гильберта 2.4 Изображение кривой Госпера 2.5 Изображение кривой Серпинского 3 Ветвление 3.1 Код программы "Flower.m" 3.2 Изображение цветка 3.3 Изображение куста 3.4 Изображение Снежинки Системы итерированных функций 1 Построение ковра Серпинского с помощью ДСИФ 3.1.1 Код программы "SerpDSIF.m" 1.2 Изображение ковра Серпинского построенного при помощи ДСИФ 2 Кристалл построенный по алгоритму РСИФ 2.1 Код программы "Cristal.m" 2.2 Изображение кристалла 2.3 Код программы "Maple.m" 2.4 Изображение Листа 2.5 Код программы "Paporotnic.m" 2.6 Изображение папоротника Заключение Список использованных источников
Введение
Фракталы - математические объекты дробной размерности, название которых было введено в математику Б. Мандельбротом, являются в настоящее время, как предметом самостоятельных математических исследований, так и инструментарием, используемым в целом ряде прикладных задач нелинейной динамики, теории хаоса, обработки сигналов. Однако только относительно недавно появилось первое полноценное учебное пособие по новой быстро развивающейся математической дисциплине, основой которого стал учебный курс, преподававшийся автором книги в течение ряда лет в университете Миссури Колумбия. Так как при изучении фракталов и хаоса большую роль играет компьютерное моделирование, в курсе предусмотрено параллельное изучение теоретических вопросов и проведение компьютерных экспериментов. Это отличает его структуру от традиционной структуры большинства математических курсов: теорема-доказательство-пример-задача. В обобщенном виде подробно описаны известные алгоритмы построения фрактальных объектов (L-системы и терл-графика, аффинные преобразования, системы итерированных функций, случайные системы итерированных функций). Однако соответствующих программ, созданных на каком-либо языке программирования или в математическом пакете, не приводится. В то же время опыт практической реализации алгоритмов построения фрактальных объектов, описанных в каком-либо из современных математических пакетов (MATLAB, Mathcad, Maple, Matematica и т. д.), широко используемых в настоящее время в преподавании целого ряда физико-математических дисциплин, показывает, что существует необходимость внесения в них определенных корректировок, учитывающих особенности выбранного пакета (в первую очередь графические). В курсовой работе отражены алгоритмы построения классических фракталов и их программные реализации в пакете MATLAB. 1. Рекурсивный алгоритм
1 Ковёр Серпинского
Рассматривается алгоритм, основанный на использовании рекурсивной функции. Приведён пример построения простого самоподобного фрактала - ковра Серпинского. В рассматриваемом в данном разделе алгоритме используется способ построения, основанный на последовательном удалении из начальной области внутренних подобластей в соответствии с заданными правилами. Выберем в качестве начального множества S0 равносторонний треугольник вместе с областью, которую он замыкает. Удалим внутренность центральной треугольной области и назовем оставшееся множество S1. Затем повторим описанный процесс для каждого из трех оставшихся треугольников и получим приближение S2. Продолжая, таким образом, получим последовательность вложенных множеств, Sn пересечение которых и образует ковер Серпинского S (рис. 1). Из построения видно, что ковер является объединением N=3 непересекающихся уменьшенных в два раза копий (коэффициенты подобия по горизонтали и вертикали в данном случае оказываются одинаковыми, r = 1/2). Фрактальная размерность ковра Серпинского d равна:
Для построения рассматриваемого фрактала, очевидно, можно использовать следующий алгоритм. Задать порядок ковра N. Задать координаты вершин исходного треугольника ABC: (XA, YA), (XB, YB), (XC, YC).
Построить равносторонний треугольник ABC и залить его синим цветом. 5. Построить треугольник A′B′C′ и залить его красным цветом. Повторить N раз действия, описанные в пп. 4, 5, для треугольников AA′C′, A′BB′, C′B′C, соответственно. Наиболее просто описанный выше алгоритм можно реализовать при использовании рекурсивной процедуры, выполняющей последовательность действий, описанных в пп. 4, 5. Для реализации алгоритма в пакете MATLAB создана специальная функция, возвращающая изображение ковра Серпинского. Для этого использовался встроенный текстовый редактор MATLAB. Код программы приведён ниже. Изображение ковра Серпинского на рисунках 1 - 6.
1.1 Код программы "Serpinsky.m"
% Листинг файла Serpinsky.mz = Serpinsky(Lmax) % функциЯ, возвращающая изображение ковра Серпинского % Lmax - порядок ковра % задание координат вершин равнобедренного треугольника x1=0; y1=0; x2=1; y2=0; x3=0.5; y3=sin(pi/3); h=figure(1); % инициализациЯ графического окнаon; % включение режима рисования фигур в одном графическом окне fill(,,"b"); % прорисовка равностороннего треугольника(gca,"xtick",,"ytick",); % отключение режима оцифровки осей(gca,"XColor","w","YColor","w"); % установка цвета рисования осей Simplex(x1,y1,x2,y2,x3,y3,0,Lmax); % обращение к функции, прорисовывающей равносторонние треугольники % белого цветаoff % отключение режима рисования фигур в одном графическом окне function z=Simplex(x1,y1,x2,y2,x3,y3,n,Lmax) % рекурсивная функция, прорисовывающая равносторонние треугольники % белого цветаn % задание координат вершин текущего равностороннего треугольника dx=(x2-x1)/2; dy=(y3-y1)/2; x1n=x1+dx; y1n=y1; x2n=x1+dx+dx/2;n=y1+dy;x3n=x1+dx/2; y3n=y1+dy;(,,"r");=n+1; % рекурсия(x1,y1,x1n,y1n,x3n,y3n,n,Lmax); Simplex(x1n,y1n,x2,y2,x2n,y2n,n,Lmax);(x3n,y3n,x2n,y2n,x3,y3,n,Lmax); end
1.1.2 Изображения ковра Серпинского
Рисунок 1 - Ковёр Серпинского 0 порядка
Рисунок 2 - Ковёр Серпинского 1 порядка
Рисунок 3 - Ковёр Серпинского 2 порядка
Рисунок 4 - Ковёр Серпинского 3 порядка
Рисунок 5 - Ковёр Серпинского 4 порядка
Рисунок 6 - Ковёр Серпинского 5 порядка
2 Квадратный ковёр Серпинского
Алгоритм визуализации фрактального объекта, основные этапы построения которого представлены на рисунках 7 - 12, реализуется следующей последовательностью действий. .Задать порядок ковра N.
.Задать координаты вершин исходного квадрата ABCD: (XA,YA), (XB, YB) (XC, YC),(XD, YD).
3.Построить квадрат ABCD и залить его синим цветом.
.Вычислить координаты точек, делящих стороны квадрата ABCD на три равные части: dx=(XB-XA)/3, dy=(YB-YA)/3, XA=XA+dx, YA=YA+dy, XB=XA+dx+dx, YB=YA+dy, XC=XA+dx+dx, YC=YA+dy+dy, XD=XA+dx, YD=YA+dy+dy.
.Построить квадрат A′B′C′D′ и залить его белым цветом.
.Повторить N раз действия, описанные в пп. 4, 5, для квадратов с вершинами, имеющими следующие координаты:
(XA,YA), (XA,YA), (XA,YA), (XA,YA),
(XA,YA), (XB,YA), (XB,YB), (XA,YB),
(XB,YA), (XB,YB), (XB,YB), (XB,YB),
(XB,YB), (XB,YB), (XB,YC), (XC,YC),
(XC,YC), (XB,YC), (XC,YC), (XC,YC),
(XD,YD), (XC,YC), (XC,YC), (XD,YC),
(XA,YD), (XD,YD), (XD,YC), (XD,YD),
(XA,YA), (XA,YD), (XD