Applying GPU parallel programming for image processing and clustering

Full Text

1. ВВЕДЕНИЕ

Современные достижения в области технологий изображения произвели революцию в получении структурных данных высокого разрешения, что повысило спрос на надежные и эффективные алгоритмы, способные обрабатывать и анализировать сложные наборы данных изображений [1]. В ответ на эту растущую потребность были разработаны передовые алгоритмы для обработки изображений, идентификации объектов, кластеризации и структурного анализа с большим акцентом на оптимизацию производительности для параллельных вычислений и ускорения GPU [1; 2]. Эти алгоритмы были включены в удобные программные инструменты, которые способствуют комплексному и эффективному анализу данных.

Интеграция методов параллельного программирования и GPU-ускорения в алгоритмический каркас позволяет значительно повысить эффективность вычислений, особенно при работе с большими массивами данных и выполнении операций, требующих больших вычислительных затрат [3; 4]. Повышение производительности критически важно для таких чувствительных ко времени научных дисциплин, как материаловедение, биология и астрономия, где детальный анализ микроструктурной и пространственной организации необходим для развития теоретических представлений и практического применения.

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

2. РАЗРАБОТКА АЛГОРИТМОВ ОБРАБОТКИ ИЗОБРАЖЕНИЙ

Разработанные алгоритмы включают в себя ключевые этапы предварительной обработки, идентификации объектов и кластеризации. Методы шумоподавления, такие как гауссова и медианная фильтрация, повышают четкость изображения, а методы повышения контрастности, такие как выравнивание гистограммы, улучшают видимость объектов. Обнаружение объектов осуществляется с помощью обнаружения блобов (лапласиан Гаусса) и обнаружения краев (Canny) для нахождения и определения границ объектов. Сегментация водоразделов разделяет перекрывающиеся объекты. Для кластеризации используется K-means для однородных наборов данных, а DBSCAN обрабатывает сложные неоднородные данные. Для повышения скорости алгоритмы используют параллельные вычисления на базе GPU, что позволяет выполнять обработку в режиме реального времени [4]. Адаптируемые параметры обеспечивают широкую применимость – от электронной микроскопии до астрономических изображений. Модульная природа алгоритмов обеспечивает масштабируемость при различных разрешениях и размерах изображений, что было проверено в различных научных приложениях. Аналогичные подходы включают Mean-Shift для адаптивной кластеризации на основе пиков плотности, Agglomerative Clustering для иерархических структур и OPTICS для выявления вложенных кластеров в больших наборах данных. Каждый из них дополняет кластеризацию объектов на основе пространственной близости и распределения данных.

Алгоритм «Параллельная кластеризация объектов»

Input

D: Dataset of atomic coordinates {p_1, p_2, …, p_n}

r_min, r_max: Distance range for clustering (e.g., 9nm ≤ r ≤ 13nm)

minPts: Minimum points to form a cluster (default: 2)

numThreads: Number of threads for parallel execution

Output

C: List of clusters

Cluster statistics (point distribution, angles)

Cluster visualization

Step 1: Parallel Distance Matrix Calculation

Compute distance d(p_i, p_j) for each pair of points (p_i, p_j ∈ D) in parallel.

Distribute calculations across numThreads.

Result: A distance matrix storing distances between all points.

Step 2: Cluster Initialization

Initialize empty clusters C = {}.

Mark all points as unvisited (thread-safe).

Create a lock to ensure thread-safe cluster updates.

Step 3: Parallel Cluster Formation (Distance Range)

For each point p_k ∈ D (in parallel):

If unvisited, mark as visited.

Find neighbors N_k = {p_j | r_min ≤ d(p_k, p_j) ≤ r_max}.

If |N_k| ≥ minPts, form and expand a cluster by adding N_k points.

Use locks for thread-safe cluster expansion.

Step 4: Parallel Cluster Statistics Calculation

For each cluster c ∈ C (in parallel):

Calculate point distribution.

Compute angles between points in triplets.

Determine angle distribution.

Step 5: Cluster Visualization

Visualize each cluster in parallel (e.g., plots, charts, graphs).

Step 6: Parallel Execution Flow

Load dataset D.

Set radius range r_min and r_max, and minPts.

Define numThreads for parallelism.

Perform parallel distance matrix calculation, clustering (based on distance range), statistics, and visualization.

Output

Clusters C with detailed statistics and visual representation.

3. РАЗРАБОТКА ПРОГРАММНОГО ИНСТРУМЕНТА

Успешное внедрение алгоритмов обработки изображений зависит от надежных программных средств, которые интегрируют эти алгоритмы, обеспечивая удобный интерфейс и оптимизированную производительность. Программное обеспечение имеет модульную архитектуру, что позволяет легко обновлять алгоритмы, не нарушая работу системы. Для математических вычислений и обработки изображений используются библиотеки NumPy, SciPy и OpenCV, поддерживающие различные форматы и обеспечивающие бесшовный ввод/вывод файлов для удобного экспорта данных [5]. Интуитивно понятный пользовательский интерфейс упрощает такие задачи, как загрузка изображений, настройка параметров и конфигурация кластеризации, благодаря понятным макетам и динамическим визуализациям, обеспечивая доступность и возможность настройки этапов анализа. Оптимизация производительности достигается за счет параллельных вычислений, использования GPU и CUDA для ускоренной обработки данных, а также стратегий управления памятью, таких как «ленивая» загрузка и «куски» для работы с большими наборами данных. Обширные бенчмарки обеспечивают эффективную работу программного обеспечения даже при работе с большими объемами данных. На рис. 1 иллюстрирует модульную архитектуру анализа данных, демонстрируя основные архитектурные модули и поток данных от исходных данных до визуализации, подчеркивая гибкость и модульность данного программного инструмента.

 

Рис. 1. Модульная архитектура анализа данных: основные архитектурные модули, иллюстрирующие поток данных от исходных данных до визуализации

Fig. 1. Modular data analysis architecture: main architectural modules illustrating the data flow from raw data to visualization

 

4. ОБРАБОТКА ИЗОБРАЖЕНИЙ И ИДЕНТИФИКАЦИЯ ОБЪЕКТОВ

Эффективная обработка изображений и идентификация объектов – ключевой момент в извлечении ценных сведений из сложных наборов данных. Программное обеспечение применяет методы шумоподавления, повышения контрастности и нормализации для предварительной обработки изображений, обеспечивая точность последующего анализа [1; 6]. Гауссова и медианная фильтрация удаляют шум, сохраняя края, а повышение контрастности с помощью выравнивания гистограммы и адаптивного растяжения улучшает видимость объектов [7].

После предварительной обработки применяются такие методы идентификации объектов, как обнаружение блобов (лапласиан Гаусса), обнаружение контуров (обнаружение краев Canny) и сегментация водоразделов [8; 9]. Эти методы позволяют точно обнаружить, сегментировать и очертить объекты даже в сложных или перекрывающихся областях. Программное обеспечение выдает координаты, центроиды и границы объектов, сохраняя их в доступных форматах, таких как CSV или базы данных, для дальнейшего анализа, обеспечивая совместимость и масштабируемость в различных исследовательских контекстах.

5. АЛГОРИТМЫ КЛАСТЕРИЗАЦИИ В ПРОГРАММНЫХ ИНСТРУМЕНТАХ

Кластеризация необходима для анализа пространственных моделей объектов на изображениях. Программное обеспечение объединяет различные методы кластеризации для решения различных типов данных и исследовательских задач [10]. Кластеризация K-means разбивает данные на заданное пользователем количество кластеров путем минимизации расстояния между точками и центроидами. DBSCAN определяет кластеры различной формы, даже в зашумленных наборах данных, с задаваемыми пользователем параметрами, такими как эпсилон (ϵ) и минимальное количество точек (minPts), что делает его адаптируемым к сложным наборам данных. Иерархическая кластеризация также позволяет пользователям исследовать вложенные кластерные отношения с помощью дендрограмм, обеспечивая понимание данных на разных уровнях детализации.

Программное обеспечение предлагает простой интерфейс для настройки этих алгоритмов. Пользователи могут легко задать параметры, такие как количество кластеров для K-means или epsilon и minPts для DBSCAN, с помощью интуитивно понятной панели настроек. Настройка в реальном времени и визуализация результатов кластеризации помогают быстро оптимизировать анализ. Предопределенные предустановки упрощают настройку для общих исследовательских задач, снижая сложность и обеспечивая гибкость.

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

6. СТРУКТУРНЫЙ АНАЛИЗ КЛАСТЕРОВ

Структурный анализ кластеров в программе нацелен на количественную оценку пространственного расположения точек кластера и их геометрических связей. Ключевые метрики включают распределение точек, формирование углов между соединенными точками и геометрические параметры, описывающие формы, образованные этими соединениями. Анализ распределения точек дает представление о плотности и организации объектов в кластере, а углы между соединенными точками выявляют пространственные отношения и общую структурную целостность кластера [11; 12]. Изучая распределение углов, исследователи могут оценить однородность или изменчивость расположения объектов.

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

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

7. ПРИМЕНЕНИЕ В РАЗЛИЧНЫХ ОБЛАСТЯХ НАУКИ

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

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

В биологических исследованиях программное обеспечение играет важную роль в анализе клеточных структур и организации тканей. Оно помогает идентифицировать и группировать клетки по размеру, форме и близости друг к другу, облегчая оценку нормального и аномального расположения тканей [7; 14; 15]. В исследованиях рака программное обеспечение помогает изучать образцы тканей для выявления неупорядоченных моделей роста, которые указывают на раковые ткани, что позволяет проводить раннее обнаружение и своевременное вмешательство. Кроме того, в регенеративной медицине программное обеспечение поддерживает разработку строительных лесов, способствующих упорядоченному росту клеток, имитирующих естественные структуры тканей, необходимые для эффективного восстановления и регенерации тканей.

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

8. ТЕМАТИЧЕСКИЕ ИССЛЕДОВАНИЯ И РЕЗУЛЬТАТЫ

Тематическое исследование: анализ атомной структуры аморфных сплавов

Этот пример посвящен анализу аморфных сплавов, в частности CoP, CoNiP, NiW, FeNiSiB и CoNiFeSiB, которые были выбраны из-за их структурной сложности. В аморфных сплавах отсутствует дальний атомный порядок, что делает анализ атомной структуры сложной задачей. Алгоритмы обработки и кластеризации изображений были применены к реальным электронно-микроскопическим изображениям этих материалов, что значительно повысило скорость и точность обнаружения атомных особенностей. Цель данного исследования заключалась в изучении закономерностей распределения атомов, размеров кластеров и взаимосвязи между размером кластера и упорядоченностью, а также в моделировании структур аморфных сплавов для подтверждения экспериментальных результатов.

Исследование началось с анализа данных, в ходе которого изображения просвечивающей электронной микроскопии высокого разрешения (HRTEM) были обработаны с помощью пользовательского алгоритма кластеризации K-means. Алгоритм, оптимизированный для параллельной обработки с использованием ускорения GPU с помощью библиотек CUDA и CuPy, эффективно обрабатывал большие наборы данных. Перед анализом изображения были предварительно обработаны для повышения контрастности и уменьшения шума, чтобы убедиться, что обнаруженные на изображениях атомные позиции отражают реальное расположение атомов. Специальный алгоритм обнаружения частиц успешно идентифицировал 6881 атом, рассеянный по образцам. Затем эти атомы были сгруппированы в кластеры на основе пространственной близости, в результате чего было выявлено 1659 отдельных кластеров. Эти кластеры различались по размеру: от небольших групп из 2–3 атомов до крупных конгломератов, содержащих более 10 атомов. Пространственное распределение кластеров было визуализировано с помощью диаграммы рассеяния, где каждому кластеру был присвоен уникальный цвет, чтобы различать их (рис. 2).

 

Рис. 2. Диаграмма рассеяния образца NiW, демонстрирующая идентифицированные кластеры атомных частиц, (HRTEM)

Fig. 2. Scatterplot diagram of the NiW sample, showing the identified atomic particle clusters (HRTEM)

 

Количественный анализ кластеров был направлен на понимание взаимосвязи между размером кластера и упорядоченностью. Использовались две ключевые метрики: линеаризованное расхождение Куллбэка–Лейблера (K-L) и отношение связей к вершинам (B/V). Метрика расхождения K-L выявила четкую тенденцию: с увеличением размера кластера увеличивалась и степень упорядоченности, что говорит о том, что большие кластеры имеют более организованную атомную структуру за счет более сильных межатомных взаимодействий. Эта тенденция наглядно представлена на рис. 3, где показано линеаризованное расхождение K-L для отношения связей к вершинам (B/V) в зависимости от уровня упорядоченности атомных структур.

 

Рис. 3. Линеаризованное расхождение Куллбэка–Лейблера (K-L) для кумулятивной функции распределения (CDF) отношения связей к вершинам (Div (SP(B/V)) (показано на левой оси) и для меры Лебега отношения связей к вершинам (Div (Mu(B/V)) (показано на левой оси) и для меры Лебега отношения связей к вершинам (Div (Mu(B/V)) (показано на правой оси) в зависимости от уровня упорядочения в изображениях атомных структур

Fig. 3. Linearized Kullback–Leibler (K-L) divergence for the CDF (Div (SP(B/V)) and Lebesgue measure (Div (Mu(B/V)) of the bond-to-vertex ratio, as a function of the ordering level in atomic structure images

 

Соотношение B/V еще больше подтвердило это наблюдение, показав, что кластеры с 6–8 атомами демонстрируют более высокую степень внутренней связности и упорядоченности (рис. 4). Эта метрика показала, как специфическое расположение атомов соответствует большей структурной упорядоченности в кластерах.

 

Рис. 4. Анализ соотношения связей и вершин, показывающий кластеры с более высокой степенью упорядоченности по мере увеличения их размера

Fig. 4. Bond and vertex ratio analysis, showing clusters with a higher degree of ordering as their size increases

 

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

 

Рис. 5. Иллюстрация функции радиального распределения (RDF) для аморфных сплавов, демонстрирующая вероятность нахождения частицы на определенном расстоянии от эталонной частицы и выявляющая локальный ближний порядок в материале

Fig. 5. Radial distribution function (RDF) for amorphous alloys, showing particle distance probabilities and revealing local near-order

 

Экспериментальные результаты были подтверждены моделированием аморфных сплавов. Эти модели успешно смоделировали сферические кластеры Fe, Ni и Co с неупорядоченной структурой, содержащей 1000–2500 атомов на моделируемой площади 1,5–3,5 нм. Рассчитанное распределение атомной плотности и значения RDF, полученные в результате моделирования, точно совпали с экспериментальными данными, что подтверждает адекватность моделей для анализа структур аморфных сплавов (рис. 6). Это сравнение моделированных и экспериментальных данных подтвердило способность программного обеспечения точно воспроизводить атомные конфигурации.

 

Рис. 6. Функция распределения атомной плотности (a) и функция радиального распределения (b) для двух реализаций модельного сплава FeB₂₅

Fig. 6. Atomic density distribution (a) and radial distribution function (b) for two simulated realizations of the FeB₂₅ alloy

 

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

 

Рис. 7. Эволюция угловых распределений между связями для различных степеней упорядоченности, от 10 до 90%, в кластерах, состоящих более чем из 3 вершин

Fig. 7. Evolution of the angle distributions between bonds for different degrees of ordering, from 10 to 90%, in clusters consisting of more than 3 vertices

 

Одним из значимых вкладов данного исследования стала демонстрация вычислительной эффективности и масштабируемости параллельных алгоритмов, используемых в кластерном анализе. Благодаря использованию GPU-ускорения было достигнуто 5–20-кратное ускорение обнаружения и анализа кластеров по сравнению с традиционными методами на базе CPU. Эта возможность очень важна для обработки крупномасштабных изображений высокого разрешения в режиме реального времени, что делает программное обеспечение особенно полезным в экспериментальных условиях, где своевременный анализ имеет решающее значение.

Производительность программного обеспечения была дополнительно оценена путем моделирования образцов аморфных сплавов, таких как FeB₂₅. Результаты показали отличное согласие между смоделированными и экспериментальными функциями радиального распределения, подтверждая способность программного обеспечения точно моделировать атомные структуры (рис. 8). Этот рисунок иллюстрирует изменение доли кластеров с определенными углами связей (например, 90°, 180°, 120°, 60°) по мере увеличения степени упорядоченности. Эти результаты позволили установить корреляцию между углами связей и структурной упорядоченностью.

 

Рис. 8. Изменение доли кластеров с определенными углами между связями

Fig. 8. Change in the proportion of clusters with certain angles between bonds

 

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

9. ЗАКЛЮЧЕНИЕ

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

Значение этих инструментов выходит далеко за рамки их непосредственного применения, способствуя более глубокому пониманию сложных структур в различных научных областях. Благодаря параллельному программированию на базе GPU программное обеспечение достигает 5–20-кратного увеличения производительности по сравнению с традиционными последовательными методами, обеспечивая визуализацию в реальном времени и эффективную обработку больших массивов данных высокого разрешения. Это делает программное обеспечение особенно полезным в экспериментальных средах, где анализ в реальном времени имеет решающее значение.

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

В целом, разработанное программное обеспечение показало высокую эффективность как при экспериментальном тестировании, так и при практическом применении, в частности, при анализе упорядоченности атомной структуры в кластерах. Алгоритм объединяет передовые математические модели и статистические методы для измерения структурных вариаций. Кроме того, результаты моделирования показали, что энтропийные и графические метрики практически не чувствительны к изменениям упорядоченности, в то время как углы связей сильно коррелируют со степенью структурной упорядоченности. Примечательно, что более высокая доля определенных углов, таких как 90°,180°, 120° и 60°, указывает на повышенную упорядоченность. Данные экспериментов подтвердили, что более крупные кластеры имеют тенденцию демонстрировать более высокую степень упорядоченности. Дивергенция Куллбэка–Лейблера и угловые распределения были определены как надежные метрики для количественной оценки упорядоченности, в то время как функция радиального распределения дала представление об упорядоченности на коротких расстояниях, но оказалась менее эффективной для оценки общей структурной упорядоченности.

About the authors

Dagim Sileshi Dilla

Far Eastern Federal University

Author for correspondence.
Email: dilla.d@dvfu.ru
ORCID iD: 0000-0002-9100-1257
SPIN-code: 7200-1921

postgraduate student, Institute of Mathematics and Computer Technologies; research engineer, Electron Microscopy and Imaging Laboratory

Russian Federation, Vladivostok

Evgeniy V. Pustovalov

Far Eastern Federal University

Email: pustovalov.ev@dvfu.ru
ORCID iD: 0000-0003-1036-3975
SPIN-code: 6192-2432

Dr. Sci. (Phys.-Math.); Professor, Department of Information and Computer Systems, Institute of Mathematics and Computer Technologies; Head of the educational program 09.03.02 “Information systems and technologies”, profile “Programming of robotic systems”

Russian Federation, Vladivostok

Irina L. Artemeva

Far Eastern Federal University

Email: artemeva.il@dvfu.ru
ORCID iD: 0000-0003-2088-5259
SPIN-code: 8161-1313

Dr. Sci. (Eng.), Professor; deputy Director for Scientific Works, Institute of Mathematics and Computer Technology

Russian Federation, Vladivostok

References

Supplementary files