Электронная библиотека диссертаций и авторефератов России
dslib.net
Библиотека диссертаций
Навигация
Каталог диссертаций России
Англоязычные диссертации
Диссертации бесплатно
Предстоящие защиты
Рецензии на автореферат
Отчисления авторам
Мой кабинет
Заказы: забрать, оплатить
Мой личный счет
Мой профиль
Мой авторский профиль
Подписки на рассылки



расширенный поиск

Разработка алгоритмов анализа картин визуализации потоков Савин Алексей Андреевич

Разработка алгоритмов анализа картин визуализации потоков
<
Разработка алгоритмов анализа картин визуализации потоков Разработка алгоритмов анализа картин визуализации потоков Разработка алгоритмов анализа картин визуализации потоков Разработка алгоритмов анализа картин визуализации потоков Разработка алгоритмов анализа картин визуализации потоков Разработка алгоритмов анализа картин визуализации потоков Разработка алгоритмов анализа картин визуализации потоков Разработка алгоритмов анализа картин визуализации потоков Разработка алгоритмов анализа картин визуализации потоков Разработка алгоритмов анализа картин визуализации потоков Разработка алгоритмов анализа картин визуализации потоков Разработка алгоритмов анализа картин визуализации потоков
>

Диссертация - 480 руб., доставка 10 минут, круглосуточно, без выходных и праздников

Автореферат - бесплатно, доставка 10 минут, круглосуточно, без выходных и праздников

Савин Алексей Андреевич. Разработка алгоритмов анализа картин визуализации потоков: диссертация ... кандидата технических наук: 05.12.04 / Савин Алексей Андреевич;[Место защиты: Национальный исследовательский университет "МЭИ"].- Москва, 2014.- 150 с.

Содержание к диссертации

Введение

1 Численное моделирование потоков для испытания алгоритмов их визуализации 15

1.1 Вводные замечания 15

1.2 Математические модели потока 15

1.2.1 Численное решение уравнений гидродинамики 15

1.2.5 Альтернативные модели стационарных потоков 18

1.2.6 Нестационарная модель потока 19

1.3 Моделирование работы цифровой видеокамеры 31

2 Корреляционные алгоритмы обработки картин визуализации потоков 39

2.1 Классические алгоритмы обработки изображений 39

2.1.1 Стандартный кросскорреляционный алгоритм PIV 39

2.1.2 Адаптивный кросскорреляционный алгоритм PIV 46

2.1.3 Методы улучшения качества изображений 49

2.1.4 Методы коррекции ошибок 52

2.1.5 Методы интерполяции векторов 54

2.1.6 Маскирование областей 56

2.2 Цветовое кодирование картин визуализации потоков 57

2.2.1 Вводные замечания 57

2.2.2 Цветовое кодирование изображений для автокорреляционной функции 58

2.2.3 Цветовое кодирование изображений для взаимной корреляционной функции 61

2.3 Точностные характеристики алгоритмов обработки картин визуализации потоков 65

2.3.1 Основные сведения 65

2.3.2 Алгоритм обработки с цветовым кодированием 67

2.3.3 Результаты обработки 69

3 Методы поиска и слежения за положением частиц на картинах визуализации потоков 73

3.1 Алгоритмы поиска частиц на изображениях 73

3.1.1 Основные сведения 73

3.1.2 Стандартные алгоритмы обнаружения частиц 73

3.1.3 Маркерная градиентная сегментация по водоразделу 77

3.1.4 Сравнение работы алгоритмов 81

3.2 Алгоритмы слежения за положением частиц 83

3.2.1 Стандартные алгоритмы 83

3.2.2. Алгоритм релаксации 84

3.2.3 Алгоритм отслеживания частиц на основе математической трактовки многочастичных задач 88

Заключение 119

Список литературы 125

Введение к работе

Актуальность работы

В последние годы в исследованиях аэро- и гидродинамических течений широко используются бесконтактные методы измерения векторного поля скорости, основанные на цифровой видеозаписи траекторий частиц, визуализирующих исследуемый поток, с последующим компьютерным анализом получившихся изображений.

В настоящее время рассматриваемые методы нашли свое применение в исследовании гидро- и аэродинамики лабораторных течений, физическом моделировании технологических процессов в энергетике, химической промышленности и медицине.

При этом экспериментальные изображения представляют собой смесь случайных импульсных сигналов и теплового шума видеокамеры. В то же время в современной радиотехнике широко развиты и используются методы обработки сигналов при наличии помех. Кроме того, при анализе картин визуализации потоков часто возникает задача определения частиц, относящаяся к методам анализа и распознавания изображений, которые также изучаются в радиотехнике.

Таким образом, возникает актуальная задача – применить эти методы к задачам определения векторных полей смещений и скорости потока, что позволит разработать новые алгоритмы, которые повысят точность, надежность и быстродействие процедур извлечения необходимой в этих задачах информации.

Состояние вопроса

В настоящее время при анализе картин визуализации потоков используются следующие методы:

корреляционный анализ фрагментов изображений (метод Particle Image Velocimetry, PIV, представлен в работах R. J. Adrian, M. Raffe, C.E. Willert и др.). Метод основан на поиске максимума взаимной корреляционной функции (ВКФ), по которому оценивается вектор смещения частиц во фрагменте;

методы отслеживания отдельных частиц (методы Particle Tracking Velocimetry, PTV, развитые в работах O. Kazuo, L. Hang-Yu, T. Wei-Hsin, D. Dabiri и др.).

Методы PIV позволяют получать мгновенные пространственные распределения векторных полей, даже для сложных турбулентных потоков. Однако при анализе методом PIV получается, что векторное поле скорости усреднено по группе частиц. Предполагается, что

частицы внутри области анализа движутся параллельно, однако это не так. Также никак не используется возможность управления формой корреляционных функций, которая широко используется в радиотехнике. Кроме того, для возможности вычисления ВКФ используются скоростные видеокамеры, обладающие более высокой стоимостью и меньшим разрешением, чем обычные камеры.

Методы PTV устраняют недостаток, связанный с усреднением векторного поля по группе частиц. Однако определение смещения отдельных частиц является достаточно сложной задачей. Существующие подходы чаще всего основаны на предположении, о квазипараллельном движении соседних частиц. Такой подход не позволяет учитывать эффект ухода частиц из кадра (потери пары). Отсюда вытекают цели и задачи диссертации.

Цель и задачи диссертации

Целью настоящей работы является разработка методов реконструкции векторного поля смещения частиц по последовательным изображениям, зарегистрированным с помощью цифровой видеокамеры. Для достижения этой цели необходимо:

1. провести анализ существующих методов обработки картин
визуализации потоков;

2. разработать новые принципы обработки, повышающие качество и
надежность извлечения информации о характеристиках потоков;

  1. разработать компьютерную модель системы для визуализации потоков, состоящую из двух частей – моделирование движения жидкости и моделирование работы цифровой видеокамеры;

  2. разработать новые алгоритмы анализа методом PIV и PTV;

  3. реализовать стандартные алгоритмы анализа методом PIV и PTV;

6. провести сравнения результатов работы стандартных и новых
алгоритмов на экспериментальных и модельных изображениях;

7. дать рекомендации по использованию и дальнейшему
совершенствованию предложенных методов.

Методы исследования

В работе использовались математический аппарат дифференциальных уравнений в частных производных и методы математического моделирования.

Достоверность разработанных алгоритмов проверялась решением уравнений Навье-Стокса методом конечных элементов, а также методом моделирования движения нестационарных потоков.

При определении смещения частиц использовались методы нелинейной оптимизации для целевых функций нескольких переменных.

Научная новизна работы заключается

1. в разработке рациональной модели картины визуализации
турбулентного потока;

  1. в использовании для расчета векторного поля скорости корреляционного анализа с применением цветового кодирования изображений;

  2. в использовании для поиска частиц на изображениях алгоритма сегментации, основанного на преобразовании водораздела и поиске маркерных областей;

  3. в разработке метода определения смещения частиц на изображениях, основанного на введении функции, описывающей совокупность частиц, и расстояния между кадрами.

Практическая значимость работы состоит в том, что:

  1. доказана возможность практического использования для реконструкции векторного поля скорости потоков корреляционного анализа с применением цветового кодирования;

  2. доказана возможность практического использования для определения координат частиц алгоритма сегментации, основанного на преобразовании водораздела и поиске маркерных областей;

  3. предложен алгоритм моделирования системы для визуализации потоков, позволяющий быстро получать модельные изображения с заданными параметрами и известным векторным полем;

  4. предложен алгоритм цветового кодирования изображений для метода PIV, позволяющий повысить точность анализа при наличии шума на изображении;

  1. предложен алгоритм поиска частиц на изображении, позволяющий быстро и эффективно получать координаты частиц для дальнейшего анализа;

  2. предложен алгоритм определения смещения частиц, позволяющий увеличить надежность анализа при исследовании вихревых потоков.

Основные научные положения работы, выносимые на защиту: 1. компьютерная модель экспериментальных изображений картин визуализации потоков и модель нестационарного потока;

  1. использование корреляционного анализа с применением цветового кодирования для повышения точности измерений при работе с зашумленными изображениями;

  2. алгоритм анализа методом PIV на основе цветового кодирования изображений;

4. использование алгоритма сегментации с применением преобразования
водораздела и поиска маркерных областей для эффективного обнаружения
частиц на изображениях;

5. алгоритм поиска частиц на изображении с применением преобразования водораздела;

  1. принцип и алгоритм отслеживания частиц на основе математической трактовки многочастичных задач;

  2. результаты тестирования разработанного программного обеспечения на экспериментальных и модельных изображениях.

Апробация результатов

Основные результаты работы были представлены на конференциях «Международная научно-техническая конференция студентов и аспирантов» (г. Москва, «НИУ «МЭИ», 2010-2014 гг.), «Международная конференция Оптические методы исследования потоков» (г. Москва, «НИУ «МЭИ», 2011, 2013 гг.), «The 15th International Symposium on Flow Visualization» (Белоруссия, г. Минск, «Институт тепло- и массообмена имени А.В. Лыкова», 2012).

Реализация основных результатов

Разработанный алгоритм отслеживания частиц использовался на кафедре физики им. В.А. Фабриканта «НИУ «МЭИ» для определения смещения сетки лазерных маркеров при деформации объекта.

Публикации

В процессе подготовки диссертации опубликовано 11 работ, среди которых 1 статья в приложении «Метрология» к журналу «Измерительная техника» и 2 статьи в журнале «Журнал радиоэлектроники», определенных в перечне ВАК РФ в качестве одних из ведущих рецензируемых научных журналов; опубликовано 5 тезисов докладов и 3 статьи в трудах конференций.

Структура и объем диссертации

Диссертация состоит из введения, трех глав, заключения, списка литературы и одного приложения. Работа содержит 150 страниц, включая приложение (20 стр.), 69 рисунков (13 в приложении) и список литературы из 63 наименований (включая труды автора).

Численное решение уравнений гидродинамики

Таким образом, возникает актуальная задача – применить эти методы к задачам определения векторных полей смещений и скорости потока, что позволит разработать новые алгоритмы, которые повысят точность, надежность и быстродействие процедур извлечения необходимой в этих задачах информации.

Обзор существующих методов исследования В настоящее время под термином PIV понимается количественное измерение скорости потока при большом числе опорных точек [7]. Строго говоря, первые исследователи, которые провели такое измерение в 1977 году, использовали метод спеклов (Laser Speckle Velocimetry – LSV) и показали, что этот метод можно применять для определения скорости потоков [8].

В 1984 г. выходит работа [1], в которой говорится о том, что при лазерной подсветке частиц в плоскости изображения редко будут формироваться спеклы. Чаще всего в ней будут наблюдаться изображения отдельных частиц. Термин PIV вводится для того, чтобы отличить такой режим от режима спеклов. В статье [1] также вводится простой критерий, основанный на концентрации частиц в исследуемом объеме, который позволяет легко определить, какой из двух режимов будет иметь место. Этот критерий устанавливает, когда из-за перекры 8 тия изображений отдельных частиц их допустимая концентрация оказывается недостаточной для формирования спеклов. Дальнейшее увеличение концентрации оказывается либо недостижимым, либо нежелательным с точки зрения динамики потока. Таким образом, на картинах визуализации потоков чаще всего наблюдаются изображения отдельных частиц.

Суть метода PIV заключается в разбиении изображения на фрагменты, называемые областью опроса. В этом методе предполагается, что частицы внутри области опроса движутся в одном направлении. Затем вычисляется взаимная корреляционная функция (ВКФ) между фрагментами соседних кадров. По положению максимума корреляционной функции определяется вектор смещения каждого фрагмента, а, следовательно, и всех частиц внутри него.

Для повышения пространственного разрешения применяются адаптивные алгоритмы, в которых вектора, полученные при больших окнах опроса, используются для коррекции положения меньших окон [9].

Предположение о коллинеарном движении частиц внутри фрагмента чаще всего не выполняется и приводит к возникновению погрешности. Кроме того, для определения одного вектора в корреляционном методе используется порядка 6-10 меток, что снижает пространственное разрешение [10]. Поэтому более предпочтительным выглядит идея отслеживать каждую частицу в отдельности. Однако такая задача является достаточно сложной, из-за чего изначально алгоритмы отслеживания отдельных частиц, получившие названия Particle Tracking Velocimetry (PTV), применялись лишь при небольшой концентрации меток [11]. Только в последние годы аппаратная часть систем визуализации потоков достигла того уровня, когда можно говорить об отслеживании частиц при их высокой концентрации, поэтому методам PTV уделяется большое внимание.

Для анализа картин визуализации потоков методом PTV необходимо решить две задачи: определение координат частиц на изображении и определение смещения частиц на двух последовательных кадрах. Долгое время первой задаче уделялось мало внимания. Чаще всего использовалось преобразование изображения в двоичную форму (бинаризация) с определенным порогом яркости. После этого на двоичном изображении ищутся области, в которых находятся логические единицы, и вычисляется центры этих областей [12, 13]. Более сложные подходы учитывают распределение яркости изображения частиц [14], либо применяется бинаризация с адаптивным для каждой частицы порогом [15].

Решение второй задачи сопряжено со значительными трудностями, особенно в турбулентных потоках при наличии вихрей и большого разброса скоростей. Наиболее простой подход состоит в интерполяции результатов анализа методом PIV в точки, соответствующие координатам частиц. Затем на следующем кадре выполняется поиск ближайшей к концу вектора частицы [11].

В настоящее время наиболее простыми алгоритмами можно считать четырех-кадровый алгоритм поиска [16], использующий четыре последовательных изображения, и кросскорреляционный алгоритм обработки бинарных изображений [17], использующий только два кадра. В четырех-кадровом методе движение частиц отслеживается от кадра к кадру с учетом геометрической согласованности каждого из возможных путей. Наиболее подходящий путь частицы выбирается с помощью последовательной интерполяции смещения частицы и поиска ближайших соседей. Преимуществом этого метода является простота алгоритма и возможность его использования для исследования вихревых структур в потоке. Недостатками является ограничения на количество частиц и низкая скорость работы алгоритма.

Кросскорреляционный алгоритм обработки бинарных изображений является вариацией обычно алгоритма PIV, в котором кросскорреляционная функция (взаимная корреляционная функция) вычисляется для каждой области опроса, центрированной относительно частиц первого кадра с использованием методов смещения областей опроса, описанных выше. Расчет происходит очень быстро, так как входными данными являются двоичные числа, а число смещений ограничено числом возможных кандидатов для частицы на втором кадре. Преимущества и недостатки этого метода противоположны предыдущему: высокая скорость работы и возможность работы с большим количеством частиц является преимуществом, а усложнение алгоритма и сложность работы с вихревыми потоками являются недостатком.

Не так давно появились двух-кадровые алгоритмы отслеживания частиц, использующие концепцию кластеров. При таком подходе частицы на первом и втором кадре образуют кластеры вместе со своими ближайшими соседями, а выбор пар частиц основан на деформации кластера на первом и втором кадрах. В качестве меры деформации можно использоваться, например, градиент скорости по отношению к центральной частице [18]. Такой подход хорош тем, что позволяет работать с вихревыми потоками. Тем не менее, такие кластеры требуют фиксированное число соседних точек для каждого кластера, следовательно, необходимо изменять размер области опроса от кластера к кластеру, что приводит к проблемам с локализацией вектора скорости. Кроме того, эти алгоритмы никак не учитывают возможную потерю частиц на двух кадрах.

Еще одной идеей стало использование генетических алгоритмов [19] и алгоритмов на основе нейронных сетей [20]. Такие алгоритмы дают хорошие результаты, однако также не позволяют учитывать эффект потери пар и применяются в основном к изображениям с низкой концентрации частиц. Одним из наиболее распространенных на сегодняшний день является метод, основанный на алгоритме релаксации [21].

Адаптивный кросскорреляционный алгоритм PIV

Прибавив к координатам частицы смещение, задаваемое локальным вектором скорости (рисунок 1.8б), мы получим новое положение плотности. При таком подходе сложность заключается в преобразовании получившихся нецелых координат в ячейки сетки. Удобнее вычислить, из какой точки пространства (x0, y0) на следующем шаге частица попадет точно в центр ячейки (рисунок 1.8в). Тогда останется интерполировать значение плотности из ближайших ячеек в точку (x0, y0), чтобы получить смещенное значение плотности. Распространение скалярного поля плотности дыма вдоль статического векторного поля скорости показано на рисунке 1.9.

Распространение плотности дыма вдоль статического векторного поля Благодаря указанному выше сходству систем (1) и (2) разработанные для плотности алгоритмы можно использовать для расчета изменения во времени векторного поля скорости потока. Однако необходимо еще обеспечить выполнение второго уравнения системы (1)

.После выполнения процедуры адвекции по используемому алгоритму результирующее поле скорости часто массу не сохраняет. Это общая проблема для всех сеточных методов. Ключевая идея алгоритма состоит в том, чтобы на последнем шаге добавить в поток учет закона сохранения массы. Это выполняется с помощью математического метода, называемого декомпозицией Ходжа [36]: любое векторное поле скорости представляет собой сумму градиентного поля и поля, сохраняющего массу. Это иллюстрируется на рисунке 1.10.

Заметим, что вычисление декомпозиции Ходжа приводит к системе линейных уравнений, с разряженной матрицей, и решение можно искать с помощью уже используемого алгоритма на основании метода покоординатного спуска. В исходной статье [33] уделяется мало внимания граничным условиям. В ней предполагалось, что по периметру сетки располагаются твердые стенки, и поток не может покинуть их пределы. Одна из частых задач для траекторных методов визуализации потоков – исследование обтекания неподвижных объектов различной формы. Поэтому автор принял решение добавить в алгоритм учет объектов произвольной формы.

Будем использовать самые простейшие граничные условия – гладкие твердые неподвижные стенки. На границе таких стен нормальная составляющая векторного поля скорости должна равняться нулю (поток не может проникнуть внутрь объекта). Поэтому в алгоритм необходимо добавить определение границы объекта и построение вектора нормали к границе. Затем вычисляется проекция вектора на нормаль и добавление обратного вектора, направленного от границы.

Для добавления объектов в модель потока на сетке вводится дополнительная логическая разметка. Элементы сетки, занятые объектом, обозначаются логической единицей, а свободные – нулем. Для того чтобы найти элементы границы, воспользуемся некоторыми сведениями из цифровой обработки изображений.

Цифровое изображение задается массивом: двухмерным в случае черно-белого изображения и трехмерным для цветных изображений. Элемент массива называется пикселем. Для того чтобы извлечь определенные компоненты изображения, такие, как границы объектов, Два пикселя;? и q называются 4-смежными, если q eN4(p) и 8-смежными, если q eN8(p). Путем между пикселями р1 и рп называется последовательность пикселейр1,р2, … Рп-1,Рп, такая, что pk является смежным длярк+1 при к= 1, 2, … /1-1. Путь может быть 4-связным или 8-связным в зависимости от используемой смежности пикселей. Два пикселя р и q называют 4-связными (8-связными), если между ними существует 4-связный (8-связный) путь. Для любого пикселя множество всех связанных с ним пикселей называется компонентной связности. На рисунке 1.12 показано, как выбор смежности пикселей влияет на количество компонент связности на изображении. Рис. 1.12 – Определение компонент связности для 4-смежных пикселей (слева) и 8-смежых пикселей (справа)

Из рисунка 1.12 хорошо видно, что компоненты связности в нашем случае позволяют выделить отдельные объекты на бинарном изображении. Границы объектов затем легко выделить по перепаду между 0 и 1. В результате работы такого алгоритма мы имеем координаты пикселей границ всех объектов на изображении, и координаты пикселей, занимаемых объектами. При использовании 4-связных пикселей у автора возникли проблемы с взаимодействием векторов у соприкасающихся объектов. Поэтому было принято решение использовать 8-смежные пиксели для того, чтобы расстояние между объектами было не меньше одного пикселя.

После добавления объектов и определения их границ, необходимо для каждого пикселя границы построить вектор нормали. Для этого мы разобьем границу на элементарные участки, состоящие из текущего пикселя границы и 8-смежных с ним пикселей границы. Кроме того, необходимо найти 8-смежные с текущим пиксели свободного пространства. После этого достаточно будет рассмотреть все возможные комбинации пикселей и для каждой построить вектор.

Движение частицы в векторном поле скорости моделируется также как и для стационарных потоков – движение с небольшим шагом вдоль линий тока. Однако необходимо еще учитывать наличие границ, которые частицы не могут пересекать. Так как на каждом конкретном шаге движение частиц остается прямолинейным, то может возникнуть ситуация, изображенная на рисунке 1.13.

Если наша кусочно-линейная траектория частицы пересекает пиксели границы (чего не может быть при движении по линиям тока, которые огибают границы), то движение частицы необходимо скорректировать. Это можно сделать, еще больше уменьшив шаг по времени, либо рассчитав криволинейную траекторию движения частицы. Как уже отмечалось, движение легких частиц происходит вдоль линий тока потока. Существуют алгоритмы, позволяющие построить силовые линии векторного поля. Таким образом, для каждой частицы можно построить ее траекторию движения. Однако, скорость работы таких алгоритмов достаточно низкая, а количество частиц в методах PIV исчисляется десятками тысяч. Более того, если для стационарных потоков траектория движения не изменяется во времени, то для нестационарных процедуру расчета си зо ловых линий придется повторять на каждом шаге моделирования, что значительно снизит скорость работы алгоритма. Поэтому в нашей работе мы использовали уже описанный выше менее точный, но намного более быстрый подход, а криволинейные траектории вычисляются только для тех частиц, траектории которых при прямолинейном движении пересекают границу объекта. Примеры работы алгоритма моделирования нестационарных потоков показаны на рисунке 1.14. 733474 Рис. 1.14 – Примеры работы алгоритма моделирования нестационарных потоков Разработанный алгоритм работает в режиме реального времени, позволяет вводить в поток объекты произвольной формы и интерактивно взаимодействовать с потокам, создавая начальные условия для модели. Получающиеся векторные поля скорости отображают основные особенности турбулентных потоков, что позволяет использовать их для анализа работы методов PTV. 1.3 Моделирование работы цифровой видеокамеры

При исследовании характеристик систем PIV методами математического моделирования важную роль играет адекватность выбранной модели совокупности изображений частиц, находящихся в области сечения потока световой плоскостью. В зависимости от параметров оптико-электронной системы регистрации и характеристик исследуемого потока изображения частиц имеют свои размеры, форму, динамический диапазон яркостей, пространственное распределение и др. Моделирование изображений, полученных методом PIV, обычно включает в себя следующие этапы: - расчет трехмерного распределения интенсивности зондирующего светового поля в исследуемой области; - генерация пространственных координат центров рассеивающих частиц и размеров частиц в соответствии с заданными вероятностными характеристиками размера и концентрации частиц; - построение отображения полученного объемного распределения сово купности частиц на поверхность фоточувствительной приемной матрицы с уче том характеристик оптической схемы фотоприемника, пространственного рас пределения интенсивности зондирующего светового поля и выбранной модели образа одиночной частицы. В большинстве случаев используется гауссова модель распределения яркости изображения одиночной частицы [12], параметрами которой являются координаты центра изображения, эффективный радиус и максимальная интенсивность светового пятна. Интенсивность изображения частицы является, в свою очередь, функцией ее пространственного положения внутри зондирующей световой плоскости. Обычно предполагается, что диаметр частицы существенно меньше толщины световой плоскости

Цветовое кодирование изображений для взаимной корреляционной функции

Геометрическая интерпретация алгоритма наискорейшего спуска: траектория x(k) ортогональна линиям равного уровня минимизируемой функции. Поскольку шаг движения к экстремуму имеет конечную длину, по мере перемещения к точке x(k+1) ортогональность нарушается. В точке x(k+1) направление корректируется и снова становится ортогональным к линиям равного уровня.

Как видно из (48), алгоритмы наискорейшего спуска могут различаться по способу определения шага (k) (остальные элементы формулы (48) для всех модификаций алгоритма наискорейшего спуска одинаковы). Величина шага может зависеть, а может и не зависеть от формы минимизируемой функции. Если величина шага не зависит от формы, минимизируемой функции, алгоритмы подразделяются на алгоритмы с постоянным и переменным шагом. Если величина шага зависит от формы минимизируемой функции, то алгоритмы подразделяются по способу учета этой формы.

Использование алгоритмов с постоянным шагом не позволило получить удовлетворительные результаты при расчете экстремума введенной функции. Поэтому автору необходимо было реализовать алгоритм учитывающие форму минимизируемой функции, называемый метода Ньютона. Он основан на квад-ратической аппроксимации минимизируемой функции в окрестности точки x(k). Минимум квадратической функции легко найти, приравнивая ее градиент нулю. Можно сразу же вычислить положение экстремума и выбрать его в качестве следующего приближения к точке минимума.

Вычисляя точку нового приближения по формуле: x(k+1)=x(k)+x(k) и разлагая f(x(k+1)) в ряд Тейлора, получим формулу квадратической аппроксимации fкв(x(k+1)): закончить итерационный процесс, используя следующее условие: - так как по постановке задачи нас интересует именно значение аргумента (а не функции), то следует прекратить вычисления, если, начиная с -той итерации \/к к абсолютное значение нормированной разности между значениями аргумента в «соседних» точках не превышает наперед заданного малого числа 5 0: хк Сложность реализации метода Ньютона связаны с необходимостью вычислений и обращения матриц вторых производных, однако при таком подходе получается гораздо более высокая скорость сходимости, чем при использовании других модификаций метода наискорейшего спуска

Большинство численных алгоритмов работают лучше и быстрее, если точка начального приближения находиться как можно более близко к истинному значению экстремума. Предлагается в качестве первого приближения интерполировать в координаты частиц (X1, Y1) векторное поле, полученное в результате предварительного анализа методом PIV исходных изображений.

Время вычисления при большом числе точек на персональном компьютере достаточно велико. Чтобы получить хоть какие-то результаты для реального числа точек, все пространство разбивалось на квадратные непересекающиеся подобласти, причем на втором кадре подобласть увеличивалась с целью предотвращения потери точек, и метод применялся к каждой подобласти независимо. Это иллюстрируется на рисунке 3.5. Сравнение алгоритмов отслеживания частиц принято проводить с помощью различных модельных изображений. Существуют стандартные синтетические изображения, полученные сообществом по визуализации Японии. Они доступны в сети Интернет (http://www.vsj.or.jp/piv). Такие изображения более подробно описаны в [62]. Так же тестирование будет проводиться на изображениях, полученных с помощью разработанной модели. Изображения будут отличаться количеством завихрений, т. е. в некотором роде степенью турбулентности. Основным показателем качества работы алгоритмов является число корректных совпадений.

Сравниваются три алгоритма: алгоритм релаксации (АР), метрический алгоритм с весовыми коэффициентами, выбранными по двухмерной кривой гаусса (рисунок 3.7 сверху, МАГ) и метрический алгоритм с весовыми коэффициентами, выбранными по двухмерному окну Ханна (рисунок 3.7 снизу, МАХ).

Так как по большей части сохраняется локальная параллельность движения частиц, то все алгоритмы еще хорошо справляются со своей задачей. На следующем рисунке представлены результаты обработки на более сложных потоках, полученных с помощью разработанной нестационарной модели. Результаты представлены на рисунках 3.11-3.13 Алгоритм АР, процент совпадений 85%

Результат обработки модельного изображения с шестью вихрями

Видно, чем больше вихрей в потоке, чем сильнее локальные неоднородности в скорости, тем хуже работает алгоритм релаксации. Так как в его основе лежит предположение о схожем движении соседних частиц, в тех местах, где частиц мало, или где резкие перепады скорости наблюдается повышенное число ошибочных векторов.

Стандартные алгоритмы обнаружения частиц

Вверху располагается панель с параметрами частиц. Можно выбирать их количество, размер (в пикселах), разброс размера (в пикселах), а также каким образом будет распределена яркость, одинаковая, случайная по равномерному закону или случайная по выведенному в пункте 2.2 закону.

Ниже располагается панель параметров кадра, где можно выбрать их число, ширину и высоту. Отметим, что выбор большого количества кадров может привести к переполнению памяти компьютера. Для формирования длинных последовательностей кадров предназначена специальная панель. Далее идет панель цветового кодирования. При ее активации, изображения становятся цветными, и появляется возможность задать цветовой код. После идет панель выбора числа уровней квантования яркости, панель усреднения с выбором области усреднения и кнопка, которая передает координаты последнего кадра в первый и заново запускает процесс моделирования. Это необходимо, чтобы изначально равномерное распределение частиц по кадру оказалось промодулировано скоростью потока.

Панель «Параметры шума» Эта панель предлагает активировать любой из четырех представленных шумов и задать их параметры. Отметим, что периодический шум может моделировать отсветы от стекла на изображениях.

Панель «Параметры движения» Сверху располагается панель основных параметров, где можно вводить время между кадрами, угол наклона движения (для прямолинейных движений) и центр вихря (для вихревых движений). Кроме того, можно выводить векторное поле скорости и линии тока выбранного типа движения, указывать их размер и цвет, задавать сетку для них вручную либо загрузить из файла. Так же можно сохранять векторное поле. Это требуется для расчета погрешности методов анализа.

Панель «Параметры модели Jos Stam а» Сверху располагается панель основных параметров алгоритма: размер расчетной сетки, вязкость и шаг по времени. Ниже располагается переключатель выбора между стационарным и нестационарным потоком, выбор одного из алгоритмов (исходный алгоритм и улучшенный алгоритм, позволяющий учитывать объекты произвольной формы). Ниже располагается переключатель, позволяющий использовать сидеры (бесконечные источники частиц), сформированные для модели нестационарного потока, в любых других потоках моде 138

ли. Это полезно, например, если одна из границ кадра является источником частиц. Это позволяет моделировать текущий с одной стороны поток. Далее идет слайдер выбора прозрачности отображаемых на изображении границ (показаны красным цветом) введенных в поток объектов. Внизу располагаются две кнопки, предназначенные для создания начальных условий модели (для этого используется специальная программа, описанная в пункте А.3) и для загрузки заранее созданных начальных условий.

Панель «Параметры серии кадров» Вверху располагается область, позволяющая задать путь к папке, в которой будут сохраняться сформированные кадры. Ниже находится поле ввода общего названия всех кадров (в программе будет добавляться инкрементируе-мый номер). Под ним расположено поле ввода числа кадров. Далее находится переключатель выбора случайных координат. В таком случае вместо координат, рассчитанных по модели потока, в каждом кадре координаты частиц будут выбираться случайно по равновероятному закону. Это требуется для исследования методов поиска частиц на изображении. Внизу располагается выпадающий список, позволяющий выбрать формат изображений (jpg, bmp и tiff), и кнопка, запускающая процесс записи серии кадров. Процент выполнения отображается под кнопкой.

Основное назначение этой программы – подготовка начальных условий для программы моделирования эксперимента по визуализации потоков. В программе можно в реальном времени наблюдать изменений векторного поля, вносить с помощью мыши дополнительные воздействия в поток и визуализировать поле скорости с помощью дыма. Интерфейс построен на базе двух переключающихся панелей.

В центре располагаются основные оси, в которые выводится результат моделирования. Внизу справа располагаются кнопки, позволяющий запускать бесконечный процесс симуляции, ставить его на паузу и останавливать. Во время симуляции можно добавлять с помощью мыши в поток дым, частицы,

Около пунктов меню показаны «горячие» клавиши, позволяющие быстро их вызывать с клавиатуры. Пункт меню «Файл…» позволяют сбросить все параметры алгоритма, сохранить параметры алгоритма, загрузить параметры алгоритма, загрузить границы, созданные во внешнем редакторе (в формате изображений) и выйти из программы. Пункт меню «Параметры…» позволяет переключаться между панелями «Базовые параметры» и «Параметры визуализации». Пункт меню «Алгоритм…» позволяет переключаться между исходными алгоритмом Джоса Стема и модифицированным алгоритмом, учитывающим объекты произвольной формы.

Пункт меню «Очистка…» позволяет выборочно удалять из модели существующий дым, вектора, бесконечные источника дыма, сидеры и сбрасывать 141 координаты точек в исходное положение (распределены по кадру случайным образом по равновероятному закону).

Пункт меню «Ветер…» и «Сидеры…» управляют формой добавляемых бесконечных источников: будут ли они сконцентрированы в ограниченной области или располагаться вдоль все границы кадра.

Пункт меню «Граничные условия…» Позволяет добавить объекты в виде многоугольника, начерченного мышью, к существующим граничным условиям, добавить границы по краям кадра, удалить все объекты и произвести расчет границ. Перед тем, как границы объектов будут учитываться в алгоритме, нужно сначала рассчитать их рассчитать (определить объекты, вычислить их границы и построить нормали к ним). Это можно сделать только при отключенной симуляции.

В верхней части панели располагаются поля ввода основных параметров алгоритма: размера сетки, параметров диффузии и вязкости и шаг по времени. Ниже расположены параметры визуализации: размеры кадра (могут не соответствовать размерам сетки, в таком случае недостающие значения интерполируются), а также добавление в алгоритм сил плавучести (дым будет подниматься к верху кадра).

Далее идет выбор между стационарным и нестационарным векторным полем. В самом низу панели расположены поля, позволяющие управлять положением и параметрами бесконечных источников дыма, векторов и частиц.

Панель «Параметры визуализации»

В верхней части панели располагаются элементы, управляющие числом, цветом и размером частиц, визуализирующих поток. Можно также изменить скорость движения частиц по потоку (1 – совпадает с шагом по времени. Если значение не равно шагу по времени, то алгоритм без визуализации просчитывает промежуточные шаги и отображает конечный результат).

Далее следуют параметры, управляющие визуализацией векторов, их размером, цветом и числом (если число векторов не соответствуют шагу сетки, пропущенные значения интерполируются). Также можно включить отображение векторов на границах объектов (всегда отображаются красным цветом).

Ниже располагаются параметры, управляющие визуализацией дымом. За ним следует блок, позволяющий с помощью мыши добавлять в поток дым (в виде гауссово или прямоугольного пятна с заданными размерами и плотностью), причем левая клавиша мыши добавляет одно пятно, а правая позволяет вести непрерывную линию

Похожие диссертации на Разработка алгоритмов анализа картин визуализации потоков