Median Filter for Image Processing

Умова

Реалізація медіанного фільтра для обробки фотографій трьома методами - послідовне опрацювання, розпаралелене за OpenMP, розпаралелене за MPI.

Послідовна програма

У спрощеній реалізації (без використання паралельних обчислень) процедура median_filter_manual() проходить по кожному пікселю зображення (враховуючи RGB-канали, якщо зображення кольорове) і рахує медіанне значення для "вікна" kernel_size * kernel_size навколо відповідного пікселя.

Для обробки пікселів по краях зображення використовується "padding", який додає по краях кілька пустих пікселів, щоб уникнути виходу за межі масиву під час циклу.

---

OpenMP (Cython)

Теорія

Cython

Cython — це мова програмування та компілятор, який дозволяє прискорювати Python-код шляхом перетворення його в C та подальшої компіляції в машинний код.

Основні можливості:

• Компільований Python: код пишеться як на Python, але транслюється в C, після чого компілюється в dll, з якого вже імпортуються потрібні функції. Даний підхід значно прискорює виконання.
• Оптимізація типів даних: використання статичних типів (int, double, float) для підвищення швидкості обчислень.
• Вимкнення GIL (Global Interpreter Lock): дозволяє використовувати багатопотокове виконання.
• Інтеграція з C/C++: можливість виклику C-функцій через cimport.
• Сумісність із NumPy: підтримка cimport numpy для ефективної роботи з масивами.

OpenMP

OpenMP (Open Multi-Processing) — API для багатопотокового програмування в C, C++ і Fortran.

Основні можливості:

• Прискорення обчислень на багатоядерних процесорах.
• Використання моделі поділюваної пам'яті.
• Мінімальні зміни в коді через використання директив компілятора.
• Підтримується компіляторами GCC, Clang, MSVC тощо.

Основні директиви OpenMP:

#pragma omp parallel
{
    printf("Привіт від потоку %d\n", omp_get_thread_num());
}

#pragma omp parallel for
for (int i = 0; i < 10; i++) {
    printf("Ітерація %d виконується потоком %d\n", i, omp_get_thread_num());
}

#pragma omp critical
{
    sum += i; // Запобігає конфліктам при доступі до sum
}

Практична реалізація

Для прискорення обчислень медіанного фільтра використано комбінацію Cython та OpenMP:

• Використання cdef для визначення типів змінних у стилі C++.
• Використання prange (замість range) для автоматичного розподілу ітерацій між потоками.
• Вимкнення GIL (with nogil) для забезпечення справжньої багатопотоковості.

Компіляція Cython-коду

Потрібно створити setup.py та виконати:

python setup.py build_ext --inplace

cythonize("median_filter.pyx", annotate=True, language_level=3)

Опис параметрів:

Аргумент	Опис
median_filter.pyx	Вихідний Cython-файл
annotate=True	Генерує HTML-аналіз коду
language_level=3	Вказує сумісність з Python 3
include_dirs=[numpy.get_include()]	Додає підтримку NumPy

---

MPI (MS MPI)

Теорія

MPI (Message Passing Interface) — стандартний інтерфейс для розподілених обчислень.

Основні можливості:

• Обмін даними між процесами.
• Підтримка точкової (point-to-point) і колективної (collective) передачі даних.
• Працює як на локальних машинах, так і в кластерах.
• Найпопулярніші реалізації: MPICH, OpenMPI, Intel MPI.

Практика

Для розпаралелювання медіанного фільтра використовується mpi4py.

Запуск коду:

mpiexec -n 4 python script.py

Де -n 4 вказує кількість процесів.

Після запуску:

• Створюються 4 процеси Python.
• Кожен процес отримує унікальний номер rank у MPI.COMM_WORLD.
• Головний процес (rank = 0) розбиває зображення на горизонтальні смуги та розсилає іншим процесам через comm.send().
• Інші процеси (rank > 0) отримують смуги через comm.recv(), обробляють їх та повертають результат головному процесу.

Ця реалізація дозволяє ефективно обробляти великі зображення, використовуючи розподілені обчислення.

---

Висновки

• Послідовна реалізація проста у розумінні, але повільна.
• Cython + OpenMP дає значний приріст швидкості завдяки багатопоточності.
• MPI дозволяє розподіляти обчислення між декількома машинами, що ідеально для кластерних обчислень.

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