Алгоритм розмиття зображення
В рамках проходження курсу «Розподілене програмування» на Coursera зустрівся з цікавим завданням, яке мені сподобалося простотою і лаконічністю його рішення, яким я і вирішив поділитися.
Отже, завдання: реалізувати алгоритм розмиття зображення, обчислення повинні распараллелівать. Завдання не штучно-навчальна: функцію розмиття зараз можна знайти в кожному першому додатку, призначеному для роботи з графікою.
Схема RGBA - класичний варіант представлення кольору. Піксель представляється чотирма значеннями (від 0 до 255): red, green, blue - відповідні кольори, alpha - прозорість. Відповідно, нам потрібен тип для подання пікселя і функції, які б дозволяли отримувати кожну складову з RGBA-типу. Не забуваємо і про «упаковці» всіх складових в одне RGBA-значення.
Піксель представимо типом RGBA, який, в свою чергу, є 32-бітовим числом.
Далі нам потрібна реалізація зображення. Зображення складається з пікселів типу RGBA. Потрібно реалізувати навігацію по зображенню за допомогою системи координат. По суті, все, що нам потрібно - це дані про ширину і висоту зображення, а також функції оновлення та отримання окремого пікселя.
Отже, ми підібралися до найголовнішого - до розмиття. Розумієте будемо виконувати самим нехитрим способом: обчисленням середніх значень всіх каналів кольорів всіх сусідніх пікселів. Ступінь розмиття контролюється значенням радіусу. Радіус - це кількість пікселів, яке ми «захоплюємо» з кожного боку цільового пікселя для розрахунку середніх значень.
Тобто при одиничному радіусі будуть розраховуватися середні значення десяти пікселів (9 сусідніх + цільової). При реалізації методу потрібно не забути, що не можна допустити виходу за межі зображення. Приступимо до реалізації.
Почнемо з сигнатури методу. Метод повинен приймати зображення, координати точки, яку потрібно розмити, і радіус. Повертаємо новий піксель типу RGBA.
Для лаконічності заведемо тип для зберігання координат пікселя.
Далі нам потрібно обчислити координати прямокутника, всі пікселі всередині якого будуть використовуватися для обчислення середнього значення. З одного боку верхня ліва точка цього прямокутника обмежується кордонами зображення, з іншого - нашої цільової точкою. Нижня права точка також обмежується спочатку цільової точкою і потім межами зображень, відповідно. Для «обрізання» значень реалізуємо метод clamp.
З урахуванням вищевказаних обмежень тепер ми можемо знайти координати прямокутника.
Заведемо 4 лічильника-акумулятора для компонентів кольору і один загальний лічильник для того, щоб знати, скільки, власне, пікселів ми обійшли.
Залишилось зовсім небагато. Через підрядник ітеріруемся по обчисленому прямокутника, оновлюючи акумулятори та лічильник.
Об'єднуємо все воєдино, повертаючи новий RGBA-піксель.
Тепер трохи роздумів про можливість распараллелить завдання.
Обчислення розмиття окремого пікселя - дуже легке завдання, тому ідею про її вирішенні в окремому потоці можна відкинути відразу. Потрібно бити зображення на сектора. Але на скільки і яким чином? На перше питання можна відповісти виходячи з того, що навіть дуже крутий суперкомп'ютер не має нескінченного числа обчислювальних ядер. Тобто потрібно виходити з можливостей наявних ресурсів. Якщо у нас восьмиядерна машина - можна справедливо припустити, що, в загальному випадку, завдання, що не несе в собі великих накладних витрат на суміщення результатів обчислення подзадач, обчислення якої відбуваються в 8 потоках, вирішиться швидше, ніж рішення її в одному потоці. Робимо висновок, що для користувача важливо надати можливість самому вибирати кількість потоків відповідно до наявних у нього ресурсами. Таким чином, нам потрібно розбити зображення на N приблизно однакових секторів, де N - кількість потоків для вирішення, і потім паралельно розмити всі ці сектора.
Як розбивати зображення? Залежить від реалізації самого зображення. У нас реалізований найпримітивніший варіант: одновимірний масив пікселів. Таким чином, навіть якщо в підзадача будуть перераховуватися окремі випадкові пікселі, продуктивність від цього майже ніяк не постраждає. Можна сфокусувати на лаконічності коду. Найнаївніший і просто реалізований варіант - це розмиття в одній подзадаче певного діапазону стовпців або рядків. Приступимо.
Метод blur приймає два зображення (вихідне і цільове), радіус розмиття, а також діапазон стовпців (from і to). Ітеріруемся спочатку по стовпчиках, потім по окремим пікселям, оновлюючи цільове зображення отриманими розмитими пікселями.
Залишилося запустити завдання на виконання. Я опустив реалізацію генерації діапазонів для подзадач з огляду на її тривіальності. Так само не буду демонструвати код, який реалізує диспетчеризацію завдань, так як це жодним чином не відноситься до сьогоднішньої теми. Для кожного діапазону стовпців запускаємо нову задачу (task). Потім же просто очікуємо закінчення всіх обчислень.
На цьому реалізація алгоритму закінчена. Можна поекспериментувати з кількістю потоків. В цьому випадку дуже добре себе показав hyper-threading від Intel (кожне ядро підтримує 2 логічних потоку). У моєму випадку (у процесора 4 фізичних ядра) 8 потоків обробляли завдання на 40-50% швидше, ніж 4. А ось подальше збільшення числа потоків відчутного прискорення не дали.
Спасибі, що дочитали.