Диссертация (1150572), страница 3
Текст из файла (страница 3)
Предполагается, что частицы присоединяются к агрегату последовательно.В главе приведено описание классической модели DLA, а также описаниереализованных автором для ее компьютерного моделирования алгоритмов.Автором предложен метод априорной оценки коэффициентов выбора для14построения агрегата, аналогичного по своим характеристикам агрегату, построенному по классической модели DLA. При бросании частицы на координатнуюсетку вычисляются коэффициенты выбора для каждой из граничных точекагрегата.
Показано, что эти оценки зависят только от суммы покоординатныхрасстояний между бросаемой частицей и граничной точкой агрегата по абсциссе(a) и ординате (b) и могут быть вычислены по формулеP (a, b) =14a+b.(1)После вычисления коэффициентов выбора для каждой из граничных точек агрегата строится функция распределения случайной величины присоединениячастицы к граничным точкам агрегата, из области значений которой случайным образом выбирается значение. Прообраз этого значения и определяет, ккакой точке агрегата присоединится частица.Описаны особенности реализации предлагаемого алгоритма для построения компьютерной модели агрегата.Полученные оценки алгоритмической сложности предлагаемого алгоритмасформулированы в виде следующего доказанного утверждения.Утверждение 1.
Пусть число ячеек в рассматриваемой области M , а число бросаемых частиц T . Тогда вычислительная сложность этапа предподсчетапредлагаемого алгоритма равна O(M ), а вычислительная сложность этапа бросания частиц равна O(T 2 ). Размер используемой памяти пропорционален O(M )на этапе предподсчета и является константой на этапе бросания частиц.Показано, что предлагаемый автором алгоритм позволяет уменьшить время построения агрегатов из 10000 частиц в 40 раз по сравнению с классическойверсией алгоритма.Сравнение емкостных размерностей агрегатов, построенных двумя способами, и вычисление дивергенции Кульбака–Лейблера между определяющимиизображения агрегатов вероятностными мерами позволяют утверждать, что15построенный в результате предложенного автором алгоритма агрегат по своимструктурным особенностям близок к агрегату сопоставимой мощности, построенному по классическому алгоритму.Приведено описание модели DLA для построения агрегатов на нерегулярной триангуляционной сетке, приближающей произвольную поверхность.
Аналогично плоскому случаю, частицы блуждают по треугольникам триангуляциии присоединяются к агрегату последовательно. Основным отличием модели отплоского случая является неравновероятность перехода между треугольниками, зависящая от соотношения сторон. Приведено описание реализованных автором алгоритмов для компьютерного моделирования процесса DLA на триангуляционной сетке.Автором предложена адаптация метода априорной оценки коэффициентов выбора для применения его к моделированию процесса DLA на триангуляционной сетке. Для этого введено понятие матрицы коэффициентов выбораи представлен эффективный алгоритм ее вычисления с помощью построенияпоследовательности матриц Gk , каждая из которых содержит значения всех коэффициентов выбора для путей длины k.
С помощью матрицы G, являющейсячастичной суммой матриц Gk для некоторого N , определяются коэффициентывыбора для всех треугольников, входящих в границу агрегата. Их них аналогично плоскому случаю выбирается тот, к которому будет присоединена частица.Описаны особенности реализации алгоритма для построения компьютерной модели агрегата на поверхности.Полученные оценки вычислительной сложности сформулированы в видеследующего доказанного утверждения.Утверждение 2. Пусть число треугольников в рассматриваемой триангуляции равно M , максимальная из рассматриваемых длин путей равна N , ачисло бросаемых частиц равно T .
Тогда вычислительная сложность алгоритмапостроения матрицы G равна O(N M 2 ), а вычислительная сложность этапа бро-16сания частиц, как и в плоском случае, пропорциональна T 2 . При этом размериспользуемой памяти на этапе построения матрицы G пропорционален M 2 , ана этапе бросания частиц, как и в плоском случае, константен.Показано, что предлагаемый автором алгоритм работает в 10-15 раз быстрее классического при построении последовательности из 10 агрегатов на поверхностяхx2 y 2+− z2 = 144(2)x2+ y 2 = 2z,4(3)ичто позволяет эффективно решать задачу исследования динамики сложныхсистем.Третья глава содержит описание способа классификации биомедицинских изображений с помощью их представления в виде ориентированного графаи построения стационарного потока на нем.Описан способ интерпретации изображения в качестве ориентированного графа, при котором каждому пикселю изображения ставится в соответствиевершина графа.
Вершины, соответствующие соседним в изображении пикселям,соединяются парой разнонаправленных дуг. Каждой дуге ставится в соответствие вес, равный значению интенсивности пикселя, соответствующего вершиненачала дуги, деленному на число исходящих из нее дуг. Полученный таким образом поток pij описывает начальное состояние некоторого процесса с помощьюмарковской цепи [33] на нем.Описан алгоритм построения стационарного потока uij на этом графе.
Поток называется стационарным, если для соответствующей ему марковской цепидля каждой вершины сумма весов на входящих в нее ребрах равна сумме весовна исходящих. Для построения стационарного потока используется алгоритмбалансировки Шелейховского–Брэгмана. Вершины графа перебираются после-17довательно в порядке приоритетной очереди, приоритетом в которой являетсядисбаланс вершины q(n) = |µout (n) − µin (n)|, где µout (n) — сумма мер исходящих из вершины дуг, а µin (n) — сумма мер входящих. На каждом шаге длявершины n с максимальным приоритетом вычисляется коэффициентsµout (n)γ=.µin (n)(4)Меры всех дуг, исходящих из n, делятся на γ, меры всех дуг, входящих в n,умножаются на γ.
После этого производится нормировка потока и пересчетзначений в вершинах. Критерием остановки алгоритма является то, что дисбаланс всех вершин становится меньше некоторого заданного ε. При условии ε= 0 мы получили бы стационарный поток, но вычисления ведутся с некоторойточностью ε > 0, поэтому в результате получится некоторое ε-приближенноерешение.
Соответствующий этому решению поток называют ε-стационарным.Описана реализация алгоритмов построения ε-стационарного потока.Автором предложена модификация классического алгоритма построенияε-стационарного потока на графе для решения задачи анализа изображений путем разбиения изображения на пересекающиеся части, построения ε-стационарного потока на каждой из них и объединения полученных потоков в один общий.Автором доказано следующее утверждение.Утверждение 3.
В результате вычислений по модифицированному алгоритму при объединении ε-стационарных распределений на частях на всем графеполучается не более чем 4ε-стационарное распределение.Сравнительная оценка вычислительной сложности алгоритмов сформулирована в виде следующего доказанного утверждения.Утверждение 4.
При разбиении изображения на K частей сложностьвычислений для модифицированного алгоритма меньше, чем сложность вычислений для базового в K раз.18Показано, что модифицированный алгоритм адаптирован для исполненияна компьютере с несколькими вычислительными ядрами.Проведено исследование границ применимости модифицированного метода для классификации изображений тканей печени. В качестве классифицирующего значения взято вычисленное по построенному стационарному потоку uijзначение взвешенной энтропии v, определяемое как Xpijv=−uij ln.uijij(5)Показано, что для конкретной выборки изображений патологий тканей печенипри K = 4 точность классификации падает незначительно при общем повышении скорости работы в 10 раз. При этом при K = 16 точность вычисленийпадает значительно, на 20%.Четвертая глава содержит в себе описание особенностей реализации комплекса программ для анализа биомедицинских изображений с использованиемпредложенных в главах 1–3 новых алгоритмов.Заключение содержит список основных результатов, полученных в работе.В приложении представлены результаты вычисления статистических характеристик Харалика для полутоновых изображений альбома Бродаца и дляизображений растворов серебра различной концентрации покоординатно дляцветовых палитр RGB и HSV.Публикация результатов.Результаты исследований отражены в работах [6, 7, 8, 9, 10, 11, 12, 13, 43].В статьях [10, 13, 43] соискателю принадлежат формулировки, математическиерассуждения, описания и реализации алгоритмов моделирования агрегации,ограниченной диффузией, на прямоугольной решетке и на триангуляционнойсетке с помощью вычисления коэффициентов выбора, формулировки и доказательства связанных с этими алгоритмами утверждений, а также проведение и19интерпретация результатов численных экспериментов.
Соавтору в этих статьяхпринадлежат общая постановка задачи и методы проверки достоверности полученных результатов. Статьи [6, 10, 11] опубликованы в журналах, входящихв перечень рецензируемых научных журналов и изданий.Автор благодарен своему научному руководителю к.ф.-м.н. доц. Ампиловой Н. Б., а также к.ф.-м.н.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
