Диссертация (1149346), страница 9
Текст из файла (страница 9)
Будем считать, что числа M и N достаточновелики. В области D построим целочисленную сетку узлов. Положимrij = (i, j),i ∈ {−M, −M + 1,..., M − 1, M },j ∈ {−N, −N + 1,..., N − 1, N }.Нетрудно видеть, что рассматриваемая прямоугольная сетка узлов имеет размер(2M + 1) × (2N + 1).Определим множество D0 следующим образом:D0 = {(x, y) | ϕ(x, y) ≤ 0, (x, y) ∈ D}для некоторой измеримой функции ϕ(x, y), заданной на D.73ПустьT (i, j) = (2i, 2j)(2i + 2, 2j)(2i + 1, 2j + 1)(2i + 2, 2j)(2i + 2, 2j + 2) (2i + 1, 2j + 1)(2i + 2, 2j + 2) (2i, 2j + 2)(2i + 1, 2j + 1)(2i, 2j + 2)(2i + 1, 2j + 1)(2i, 2j) (2i, 2j)(2i + 2, 2j) (2i, 2j + 2)T l(i, j) = (2i + 2, 2j + 2) (2i + 2, 2j) (2i, 2j + 2) (2i, 2j) (2i + 2, 2j + 2) (2i + 2, 2j)T r(i, j) = (2i, 2j) (2i + 2, 2j + 2) (2i, 2j + 2),,.В случае, если все элементы матрицы T (i, j) содержатся в области D0 , заменяемв таблице инциденций строки, описанные в матрице T (i, j) на строки из матрицы Tl (i, j) или Tr (i, j).
Выбор между Tl (i, j) и Tr (i, j) делается таким образом,что бы структура укрупненной триангуляции совпадала со структурой исходнойтриангуляции.Для удобства читателя покажем, как будут выглядеть треугольники, объединенные с помощью отображений εl2,2 и εr2,4 :Рис. 3.1 – Результат работы отображений εl1,1 и εr1,2Результатом работы алгоритма является триангуляция области D, укрупненная в области D0 . Полученная триангуляция описывается таблицей инциденций,которую обозначим Trez .74Ниже приводится псевдокод рассматриваемого алгоритма:mцикл e i = (−M + 1) от (M − 1) выполнятьmцикл e j = (−N + 1) от (N − 1) выполнятьmесли e All items of T (i, j) are inside of D0 тогдаmесли e (i + j) mod 2 = 0 тогдаAdd T l(i, j) to Tresконец условияиначеAdd T r(i, j) to Tresконец условияконец условияиначеAdd T (i, j) to table Tresконец условияконец циклаконец циклаВходными данными этой программы являются числа M и N , а также множествозначений аппроксимируемой функции на сетке узлов.Продемонстрируем, как будут изменяться таблицы инциденций при проведенииукрупнения.
Исходная триангуляция выглядит следующим образом:75Рис. 3.2 – Исходная триангуляцияСерым цветом обозначены индексы треугольников. На таблице 3.1 показано, каквыглядит таблица инциденций вершин данной трангуляции; в ней первый столбец— индекс вершины, 2-й и 3-й — ее координаты.index012.........118119120x000y01210 810 910 10Таблица 3.1 – Таблица инциденций вершин исходной триангуляции76На таблице 3.2 показана таблица инциденций треугольников; в ней первая колонка — индекс треугольника, далее идут индексы вершин, составляющих треугольник.index012.........979899vertice 0 vertice 1 vertice 20212224122422129812011812011896108108108Таблица 3.2 – Таблица инциденций треугольников исходной триангуляцииПолностью таблица приведена в приложении 14.77Напомним преобразование, определяющее первое укрупнение:r2i+2,2jr2i+1,2j+1 r2i,2j r rrrr2i+2,2j r2i,2j+22i+2,2j+22i+1,2j+1 2i,2j 2i+2,2jlεij : → r2i+2,2j+2 r2i,2j+2 r2i+2,2j+2 r2i+2,2j r2i,2j+2r2i+1,2j+1 r2i,2j+2 r2i,2jr2i+1,2j+1 εrij : r2i+2,2jr 2i+2,2j+2 r2i,2j+2 r2i,2j∀(i, j) ∈ Z2 (i + j) mod 2 ≡ 0,r2i+2,2j+2 r2i+1,2j+1 rr2i,2j+2r2i+1,2j+1 2i,2j r2i+2,2j+2 r2i+2,2j→ r2i,2j r2i+2,2j+2 r2i,2j+2r2i,2jr2i+1,2j+1 r2i+2,2jr2i+1,2j+1 ∀(i, j) ∈ Z2 (i + j + 1) mod 2 ≡ 0Укрупненная тримнгуляция будет выглядеть следующим образом:Рис.
3.3 – Триангуляция после укрупнения78,,Таблица инциденций треугольников укрупненной триангуляции выглядит следующим образом:index012.........474849vertice 0 vertice 1 vertice 2022222224242694969811898118116118120Таблица 3.3 – Таблица инциденций треугольников укрупненной триангуляцииПолностью таблица инциденций треугольников укрупненной триангуляции приведена в приложении 15.3.5.Програмная реализация алгоритмаДля демонстрации работы алгоритма был реализован комплекс компьютерныхпрограмм, выполняющий рекурсивное локальное адаптивное укрупнение триангуляции; полученная триангуляция далее используется для построения модели (наоснове курантовской аппроксимации) исходного потока данных. В качестве языкапрограммирования была выбрана Java; выбор обусловлен возможностями распараллеливания и переносимостью на различные аппаратные платформы.Для удобства тестирования предусмотрено использование графических файловв качестве исходных данных; это позволяет генерировать множество различныхпримеров для тестирования, а также наглядно продемонстрировать качество получающихся математических моделей исходных данных.
При этом данные интерпретируются как курантовская аппроксимация; ее график представляет собой кусочно-линейную поверхность. При укрупнении каждой группы треугольников проводится сравнение значений курантовских аппроксимаций на исходной и79укрупненной триангуляциях; укрупнения проводятся при условии, что максимумуклонения упомянутых аппроксимаций друг от друга не превосходит априори заданного числа ε > 0. Этим условием определяется критерий остановки процессаукрупнения.Было проведено распараллеливание алгоритма, однако оно не дало существенного прироста производительности.
Для эффективного использования возможностей современных вычислительных систем необходимо выполнить дополнительноеисследование.Для запуска программы необходимо использовать командную строку вида1t r _ e n l . j a v a <\ v a r e p s i l o n > <i n p u t > <o u t p u t >Программа имеет следующие обязательные параметры:1. верхняя граница погрешности аппроксимации ε; целое число типа integer;2. путь к директории в файловой системе (полный или относительный) input,в которой хранятся входные файлы; будут обработаны все файлы, имеющиерасширения bmp, jpg, jpeg, tiff и png;3. путь к директории в файловой системе (полный или относительный) output,в которую будут записаны полученны результаты.Пример запуска программы из коммандной строки:1java −j a rt r _ e n l .
j a r 10 "C : \ t r _ e n l a r g e \ i n p u t " "C : \ t r _ e n l a r g e \ o u t p u t "Каждый набор входных данных (графический файл) раскладывается затем натри независимых набора: для красной, зеленой и синей компонент цвета исходного изображения; разложение осуществляется с помощью встроеных средств языкаJava. Каждый из трех полученных таким образом наборов данных интерпретируется как множество вершин стандартной триангуляции. Далее для каждой триангуляции выполняются адаптивные рекуррентные укрупнения.3.6.Структура алгоритма укрупнения триангуляцииДадим краткое описание последовательности действий, выполняемых при укрпнении триангуляции.80Рис.
3.4 – Этапы работы метода processEnlargement, выполняющего укрупнения триангуляции.Шаг 1: ввод данныхВходные данные представлены в виде графического изображения, ассоциируемого с равномерной прямоугольной сеткой. В качестве значений в узлах сетки берутся уровни яркости красной, зеленой или синей компонент цветов соответствующих пикселей; таким образом, рассматриваются три экземпляра сеток. Далееузлы сетки автоматически интерпретируются как вершины триангуляции, имеющей рассмотренную в предыдущих главах топологию; триангуляция определяетсятаблицами инциденций треугольник-вершина и вершина-координаты. Значениямив узлах сетки являются целые числа в диапазоне [0, 255].81Рис.
3.5 – Ввод данныхШаги 2 и 3 выполняются независимо для каждой построенной на этапе вводаданных триангуляции.Шаг 2: преобразование данныхНа втором шаге выполняется преобразование полученных данных. Как уже говорилось выше, триангуляция задается таблицами инциденций треугольник →вершины Tv и вершина → координаты Vc .
Множество вершин триангуляции разобьем на два класса: к первому классу отнесем вершины, инцидентные четыремтреугольникам, а ко второму классу — вершины, инцидентные восьми треугольникам. Телом барицентрической звезды назовем замыкание объединения ее треугольников.Будем рассматривать барицентрические звезды, тело которых состоит из четырех треугольников триангуляции; следовательно, вершина каждой рассматриваемой барицентрической звезды — вершина первого класса, а ее граничные вершины— вершины второго класса.
Составим таблицу инциденций вершина → барицен82трические звезды, позволяющую по данной вершине найти множество всех барицентрических звезд, для которых эта вершина является граничной. Обозначимэту таблицу Vs .Нарисунке3.6приведенодинэлементтаблицыинциденцийVs .Вершину (второго класса), являющуюся граничной для выделенных барицентрических звезд, обозначим Λ; сами звезды обозначим символами Υ, Φ,Ψ и Ω.
Множество барицентрических звезд, инцидентных граничной вершине, назовем единицейукрупнения (триангуляции).Общую граничную вершину назовем центральнойдля данной единицы укруп-Рис. 3.6 – Единица укрупнения триангуляции.нения. Каждая единицаукрупнения имеет общие барицентрические звезды с другими единицами укрупнения; единицы укрупнения, имеющие общие барицентрические звезды, будем называть соседними.
Назовем угловыми те вершины, которые являются граничными только для одной барицентрической звезды из составляющих данную единицуукрупнения. Очевидно, что каждая угловая вершина является текже центральнойдля некоторой соседней единицы укрупнения.83Шаг 3: укрупнение триангуляцииУкрупнение триангуляции осуществляется в соответствии со следующими этапами:1. выборка из построенной на предыдущем шаге таблицы инциденций Vs первой еденицы укрупнения (случайным образом) и постановка ее в очередь наукрупнение Q;2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
