Национальный исследовательский университет
«Московский энергетический институт»
Методы сегментации частиц для обработки картин визуализации потоков
А.А. Савин
Введение
Одним из распространенных методов измерения полей скоростей потоков жидкости и газа, в том числе, жидкостей в организме человека, в настоящее время является трассерный метод, основанный на цифровой видеозаписи траекторий частиц (трассеров), визуализирующих исследуемый поток, с последующим компьютерным анализом получившихся изображений [1]. Структурная схема метода приведена на Рис. 1 [2].
Рис.1. Структурная схема метода трассерной визуализации потоков.
При выборе метода анализа определяющую роль играет параметр, называемый оптической плотностью (ImageDensity) [2]. Он определяется средним числом частиц в области анализа. Различают три основных значения оптической плотности. При малых значениях отдельные частицы хорошо различимы и можно легко сопоставить пары частиц на двух последовательных кадрах (Рис. 2а). В данном случае применяются так называемые траекторные методы анализа (ParticleTrackingVelocimetry - PTV). При средних значениях оптической плотности отдельные частицы еще можно различить, но сопоставить пары частиц на двух последовательных кадрах уже намного сложнее (Рис. 2б). В данном случае обычно применяется корреляционная обработка фрагментов изображения (ParticleImageVelocimetry - PIV). При больших значениях оптической плотности отдельные частицы на изображениях различить уже не удается (Рис. 2в). В данном случае анализируются картины лазерных спеклов (LaserSpeckleVelocimetry - LSV).
Рис. 2. Три типа оптической плотности
Основным недостатком метода PTV является слишком малая плотность частиц, которая не позволяет отследить небольшие формирования в потоке. В методе LSV, напротив, плотность частиц слишком велика, что часто нежелательно с точки зрения динамики потока. Поэтому самое большое распространение на сегодняшний день получил метод PIV.
Основным достоинством метода PIV является его высокая надежность и повторяемость, особенно при низких отношениях сигнал/шум. Это достигается благодаря статистической обработке изображений посредством корреляционного анализа. К тому же в результате получается регулярная сетка векторов, что облегчает последующую обработку векторного поля. Однако у данного метода есть свои недостатки.
Во-первых, для получения одного вектора скорости необходимо 6-10 частиц, что снижает пространственное разрешение метода [3].
Во-вторых, корреляционный анализ очень чувствителен к различным оптическим искажениям.
Современное развитие техники и методов обработки позволяет с высокой точностью определять положение отдельных частиц на изображении, а так же их центр. И, хотя плотность частиц в методах траекторного анализа выбирается меньше, чтобы избежать перекрытия частиц, итоговое разрешение может оказаться даже выше, чем у метода PIV, так как в данном случае для определения одного вектора скорости нужна только одна частица.
Поэтому развитие методов выделения частиц для картин визуализации потоков, особенно в случае перекрытия изображения частиц, сегодня является очень актуальной задачей. Одному из таких методов посвящена данная статья.
Модель картины визуализации потоков
Для исследования алгоритмов обработки картин визуализации потоков необходима модель цифрового изображения. Хорошее описание подобной модели можно найти в [4]. Основная идея заключается в том, что сначала исходное непрерывное изображение сглаживается из-за усреднения по элементам матрицы фотоприемника, затем происходит дискретизация и квантование.
Исходное изображение в случае картин визуализации потоков представляет собой сумму частиц гауссовой формы с равновероятным положением частиц, равновероятной яркостью частиц и с небольшим разбросом размеров по нормальному закону [5].
Поэтому можно использовать следующую модель изображения:
- формат кадра NxґNy пикселов;
- каждая частица представляет собой двухмерную гауссову кривую; размер частиц был одинаковым по всему кадру и варьировался;
- яркость частиц была одинаковой;
- число частиц Np;
- координаты частиц на первом кадре выбирали также по равномерному закону от 1 до Nx и до Ny по координатам x и у;
- к изображению добавлялся аддитивный нормальный шум с нулевым средним и различной дисперсией s2.
Одинаковые размер и яркость частиц использовались для того, чтобы можно было использовать статистическую обработку результатов измерения.
Выделение частиц на основе поиска локальных максимумов
Данный метод заключается в сравнивание каждого пикселя изображения, который выше некоторого порога, с его ближайшими соседями и в случае максимума вычисляется его координата с подпиксельной точностью по следующей формуле [2]:
В данной формуле dx и dy-координаты максимума с точностью до пикселя, RI-яркость изображения. Итоговые координаты максимума есть (dx+Дx, dy+Дy).
На Рис. 3 показан пример работы данного алгоритма.
Рис. 3. Фрагмент бинаризированного изображения без шума (слева) и с шумом (справа) с нанесенными координатами, полученными с помощью метода локальных максимумов
Как видно из Рис. 3, при наличии шумов на изображении появляются ложные шумовые частицы. Так как шум на изображениях нестационарный, на последовательных кадрах координаты и количество данных шумовых частиц будет случайным, что полностью нарушит работу алгоритмов отслеживания частиц. Поэтому для того, чтобы избавиться от шумов, используют пороговую обработку изображения. У данного подхода есть один недостаток: из-за пороговой обработки пропадают не только шумы, но также и частицы, яркость которых меньше порога. Это приводит к снижению пространственного разрешения PTV-метода.
Маркерная градиентная сегментация по водоразделам
Конечной целью задачи сегментации является разбиение изображения на области. Понятие водораздела основано на представлении изображения как трехмерной поверхности, заданной двумя пространственными координатами и уровнем яркости в качестве высоты поверхности (рельефа).
В такой интерпретации рассматриваются точки трех видов: (а) точки локального минимума; (б) точки, находящиеся на склоне, т.е. с которых вода скатывается в один и тот же локальный минимум; и (в) точки, находящиеся на гребни, т.е. с которых вода с равной вероятностью скатывается в более чем один локальный минимум.
Множество точек, удовлетворяющих условию (б) называют водосборным бассейном локального минимума. Множество точек, удовлетворяющих условию (в) называют линиями водораздела [6].
Основная идея метода выглядит просто. Предположим, что в каждом локальном минимум проколото отверстие, после чего весь рельеф заполняется водой, равномерно поступающей снизу через эти отверстия, так что уровень воды всюду одинаков.
Когда поднимающаяся вода в двух соседних бассейнах близка к тому, чтобы слиться вместе, в этом месте ставится перегородка, препятствующая слиянию. В конце концов, достигается фаза, когда над водой остаются видны только верхушки перегородок. Эти перегородки, соответствующие линиям водораздела, и образуют непрерывные границы, выделенные с помощью алгоритма сегментации по водоразделам [6].
Перед математическим описанием алгоритма сегментации сначала введем несколько определений. Пусть S - некоторое подмножество элементов изображения. Два его элемента, pи q называются связными в S, если между ними существует путь, целиком состоящий из элементов подмножества S. Для любого элемента p из S множество всех пикселей, связных с ним в S, называется компонентой связности (связной компонентой). визуализация фотоприемник векторный матрица
Переходим к описанию алгоритма. Пусть M1, M2,…,MR - множества точек координатной плоскости, соответствующие локальным минимумам поверхности g(x, y). Обозначим через C(Mi) множество точек бассейна, отвечающего локальному минимуму Mi. Обозначения min и max будем использовать для указания наименьшего и наибольшего значения изображения g(x, y). Наконец, запись T[n] означает множество точек (s, t), для которых g(s, t) < n. С геометрической точки зрения, T[n] есть множество точек, в которых поверхность g(x,y) лежит ниже плоскости g(x, y) = n.
При заполнении рельефа водой уровень поднимается в виде целочисленных приращений от n = min+1 до n = max + 1. В процессе подъема воды на любом шаге n алгоритму необходимо знать число точек, лежащих ниже уровня воды. Будем считать, что все точки множества T[n] отмечены черным цветом, а остальные - белым. Тогда при произвольном шаге подъема уровня воды, рассматриваемая трехмерная поверхность в проекции на плоскость xy может быть представлена двоичным изображением.
Пусть Cn(Mi) обозначает множество точек бассейна с локальным минимум Mi, которые оказались залиты на шаге n. Тогда Cn(Mi) можно рассматривать как двоичное изображение, задаваемое соотношением:
Пусть теперь C[n] - объединение залитых водой частей всех бассейнов на шаге n:
Тогда C[max+1] есть объединение всех имеющихся бассейнов. Можно показать [6], что при работе алгоритма никогда не происходит удаления элементов из множеств Cn(Mi) и T[n].
Таким образом, при увеличении n число элементов этих множеств либо возрастает, либо остается неизменным. Следовательно, C[n-1] является подмножеством C[n].
Согласно равенствам и , C[n] является подмножеством T[n], а значит и C[n-1] также есть подмножество T[n].
Алгоритм нахождения линий водораздела начинается с инициализации C[min+1] = T[min+1].
После этого алгоритм выполняется рекуррентно, предполагая на n-ом шаге множество C[n-1] уже построенным. Для получения множества C[n] из множества C[n-1] применяется следующая процедура.
Пусть Q[n] - множество компонент связности множества T[n]. Тогда для каждой связной компоненты есть три возможности:
а) - пустое множество;
б) содержит единственную компоненту связности множества C[n-1];
в) содержит более одной компоненты связности множества C[n - 1].
Способ построения C[n] по C[n-1] зависит от того, какое этих из трех условий имеет место.
Условие (а) означает, что встретился новый локальный минимум (начинается наполнение нового бассейна); в этом случае для построения множества C[n] компонента q добавляется к C[n-1].
Условие (б) имеет место, когда q лежит внутри бассейна некоторого локального минимума; в этом случае для построения множества C[n] компонента q также добавляется к C[n-1].
Условие (в) возникает, когда встретились точки гребня, разделяющего два или более бассейна.
В этом случае дальнейший подъем воды привел бы к слиянию этих бассейнов, поэтому внутри связной компоненты q должна быть построена перегородка (или перегородки, если объединяются более двух бассейнов), не позволяющая бассейнам слиться вместе. После завершения работы алгоритма данные перегородки образуют лини водораздела.
Модуль градиента часто используется при предварительной обработке полутоновых изображений перед сегментацией по водоразделам. Пикселы изображения градиента с большими значениями располагаются вблизи границ объектов, а остальным участкам соответствуют нулевые значения пикселов.
В идеале, выполняя преобразование водораздела, можно получить линии водоразделов вдоль границ объектов [6].
Однако непосредственное применение алгоритма сегментации по водоразделам градиента изображения обычно приводит к избыточной сегментации, вызванной шумом или другими локальными неоднородностями на градиентном изображении.
Избыточная сегментация может быть настолько значительной, что сделает результат обработки практически бесполезным. Пример избыточной сегментации приведен на Рис. 4.
Рис. 4 Фрагмент картины визуализации потоков с нанесенными границами областей при избыточной сегментации (слева) и при нормальной сегментации (справа)
Практическое решение данной проблемы состоит в том, чтобы ограничить допустимое число областей путем включения в состав процедуры шага предварительной обработки, служащего для привнесения добавочной информации в процедуру сегментации.
Подход, применяемый для устранения избыточной сегментации, основан на идее маркеров. Маркер представляет собой связную компоненту, принадлежащую изображению.