Диссертация (1150572), страница 8
Текст из файла (страница 8)
Тем не менее, для расчетов агрегатов, составленных48из большого количества частиц, как и в плоском случае, требуется значительноевремя работы вычислителя.Рисунок 2.6. – Пример результата моделирования DLA на триангуляционной сетке намодели поверхности кости, представленного в работе [20].2.6Оптимизация модели DLA для поверхностиПостроим на выделенной области поверхности триангуляционную сетку.Как и в [20], треугольники в ней могут иметь разные размеры. Пусть общеечисло треугольников равно M .Каждому треугольнику ставим в соответствие вершину некоторого графаG.
В этом графе между вершинами i и j есть дуга тогда и только тогда, когдасоответствующие им треугольники Mi и Mj имеют общую сторону. На дугахрасставим веса, равные вероятности перехода из i в j согласно приведеннойвыше формуле.2.6.1Априорная оценка коэффициентов присоединенияРассмотрим всевозможные пути на графе длины не более чем некоторое N .Для любого пути между двумя произвольными вершинами i и j вероятностьюэтого пути назовем произведение вероятностей (весов) всех входящих в путь49дуг.
Вычислим некоторый коэффициент выбора для вершин i и j, равный суммевероятностей всевозможных путей из i в j длины не более чем N . Из всехкоэффициентов выбора составим матрицу G размера M × M .Вычисления организуем следующим образом. Изначально нам даны вероятности всех путей, состоящих ровно из одной дуги (это веса на соответствующих дугах). Будем последовательно вычислять матрицы Gk . В матрицу G1на позицию (i, j) при наличии на графе дуги (i, j) запишем значение веса этойдуги. На каждом шаге будем из матрицы Gk составлять матрицу Gk+1 следующим образом. Пусть элемент (i, j) матрицы Gk равен y. Рассмотрим все дугина графе, начало которых — j (таких дуг не более 3, по числу возможных соседей). Пусть для некоторой из этих дуг ее конец — x. Тогда в матрицу Gk+1 напозицию (i, x) добавим число, равное y, умноженному на веc дуги (j, x).
Матрицей G назовем сумму всех матриц Gk , где k ∈ {1...N }. Несложно заметить, чтоматрица G содержит значения всех коэффициентов выбора для путей длиныне более чем N .2.6.2Определение точки присоединения новой частицыМоделирование бросания частицы на триангуляционную сетку будем производить как и в плоском случае — в соответствии с коэффициентами выборастроить функцию неравномерного распределения, случайным образом выбирать точку из ее области значений и по прообразу определять, к какой точкеагрегата присоединится частица.Можно сказать, что построенная матрица G, как в плоском случае, так ив случае моделирования на поверхности, содержит в себе информацию о геометрии исходной поверхности.Геометрия плоской поверхности проста, поэтому матрица G для нее имееточень простой вид.
В случае моделирования на нерегулярной триангуляциооной сетке матрица G неизбыточна и не может быть без потерь информации50сохранена в структуре данных меньшей размерности.Безусловно, подсчет матрицы G для больших M трудоемок и в случае однократного вычисления агрегата на конкретной поверхности время вычисленийможет быть сравнимым с временем вычислений по классическому алгоритму.Но обычно задачу построения агрегатов решают для того, чтобы оценить динамику протекающих на поверхности процессов.
Это означает, что для конкретной поверхности для сбора статистики необходимо построить достаточное число(сотни) агрегатов. И в этом случае важно то, что для каждой поверхности матрицу G можно подсчитать 1 раз, после чего переиспользовать без измененийдля каждого нового вычисления. Это позволяет существенно экономить времявычислений при многократной операции построения агрегата на поверхности.2.6.3Оценка вычислительной сложностиСформулируем оценки вычислительной слоности алгоритма в виде следющего утверждения.Утверждение 2.2. Пусть число треугольников в рассматриваемой триангуляции равно M , максимальная из рассматриваемых длин путей равна N ,а число бросаемых частиц равно T .
Тогда вычислительная сложность алгоритма построения матрицы G равна O(N M 2 ), а вычислительная сложность этапабросания частиц, как и в плоском случае, пропорциональна T 2 . При этом размер используемой памяти на этапе построения матрицы G пропорционален M 2 ,а на этапе бросания частиц, как и в плоском случае, константен.Доказательство. Для определения априорных коэффициентов необходимо вычислить N матриц размером M × M , алгоритмическая сложность этихопераций составляет O(N M 2 ). В каждый момент времени в памяти необходимодержать матрицы G1 , Gk и матрицу G (вследствие того, что наш процесс марковский [33], не нужно держать в памяти промежуточные Gk ), поэтому размериспользуемой памяти пропорционален M 2 .51При бросании T частиц, как и в плоском случае, алгоритмическая сложность вычислений O(T 2 ), размер используемой памяти константен.
2.6.4Численный экспериментРеализованы два алгоритма построения агрегата на нерегулярной триангуляционной сетке. Один из них соответствует алгоритму, описанному в статье[20], второй — алгоритму с вычислением априорной вероятности.Проведены две серии экспериментов по построению агрегатов на триангуляционной сетке, построенной на поверхностяхx2 y 2+− z2 = 144(2.7)иx2+ y 2 = 2z.4(2.8)Серии состояли из вычислений 10 агрегатов для N = 300, M = 5000,T = 1000. Время, затраченное на вычисления, показано в таблицах 2.2 и 2.3.Таблица 2.2. – Сравнение алгоритмов моделирования на поверхности 1. Время вычислений.Классический алгоритм Оптимизированный алгоритм2.71 агрегат26 мин. 12 сек.29 мин. 43 сек.10 агрегатов4 ч.
47 мин. 33 сек.31 мин. 58 сек.РезультатыВ результате исследований предложена модификация диффузионной мо-дели DLA, дающая в результате агрегаты, близкие по математическим харак-52Таблица 2.3. – Сравнение алгоритмов моделирования на поверхности 2. Время вычислений.Классический алгоритм Оптимизированный алгоритм1 агрегат24 мин.
59 сек.28 мин. 11 сек.10 агрегатов4 ч. 11 мин. 37 сек.32 мин. 4 сек.теристикам к построенным с помощью традиционной модели, что продемонстрировано путем вычисления емкостной размерности агрегатов и дивергенции Кульбака–Лейблера между представляющими изображения вероятностными мерами. Основными преимуществами модифицированной модели являютсянизкая алгоритмическая сложность и возможность переиспользования данныхпри решении задачи многократного построения агрегатов. Показано, что предложенная модификация может быть использована для решения задачи моделирования агрегата на поверхности. Предложенный для моделирования агрегата на поверхности алгоритм обладает теми же преимуществами, что и егоплоскостный аналог.
Все предложенные алгоритмы были реализованы в рамках разрабатываемого комплекса программ; результаты практических исследований хорошо согласуются с теорией.Идея априорной оценки вероятности, использованная в предложенных алгоритмах, после некоторой переработки может быть в дальнейшем использована для модификации других диффузионных моделей распространения вещества, таких как CCA и RLCA.53Глава 3. Метод построения модели сиспользованием стационарного потока на графе3.1Основные определенияБудем рассматривать изображения, связанные с процессами распростране-ния вещества.
Для таких изображений оказывается удобным рассматривать иллюстрируемый ими процесс как движение по ориентированному графу [68, 81].При этом каждому пикселю изображения ставится в соответствие вершина графа. Каждой вершине приписывается вес (мера), равная интенсивности соответствующего пикселя. Каждая дуга графа выражает отношение соседства двухвершин, при этом для каждых двух соседних вершин существует две дуги, ведущие из одной в другую.
Количество соседей определяется выбором окрестности,как правило рассматривают окрестность из четырех ближайших вершин. Каждой дуге приписывается вес, определяемый как мера являющейся его началомвершины, деленная на число выходящих из нее ребер. Дуги с приписанными имвесами можно рассматривать как поток [24]. Этот поток нормируется, так чтобы сумма весов на дугах была равна 1. Можно считать, что полученный такимобразом граф описывает начальное состояние некоторого процесса с помощьюмарковской цепи на нем [28].Интерес при этом представляют стационарные состояния этого процесса,а именно такие, когда построенная цепь является стационарной.
Стационарной называют марковскую цепь, для каждой вершины которой сумма весов навходящих в нее ребрах равна сумме весов на исходящих.54Стационарное состояние может быть охарактеризовано с помощью энтропии стационарного процесса [74]. Для нас более интересной оказывается величина, которая характеризует скорость сходимости процесса к такому стационарному состоянию — так называемая взвешенная энтропия. Известно [3, 4], чтовзвешенная энтропия может использоваться как классификационный признакпри анализе изображений.Построение стационарных процессов на графе — хорошо изученная область математики.
К ним могут быть сведены задачи из разных областей математики, таких как линейное программирование (так называемые транспортныезадачи) или теория динамических систем (построение инвариантной меры награфе символического образа). Решение этой задачи существует, если на графеесть замкнутые циклы. Один из методов решения таких задач был предложенленинградским архитектором Г.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
