PatchMatch

Квіти у нижньому правому куті видалені за допомогою алгоритму PatсhMatсh

PatchMatch - це алгоритм швидкого знаходження відповідностей між невеликими квадратними ділянками зображення (або патчами) . Алгоритм може бути використано у різних додатках, таких як видалення об’єктів із зображень, перестановка або переміщення вмісту зображень, перенацілювання або зміна співвідношення сторін зображень, оцінка оптичного потоку або стерео відповідність .

Алгоритм

Метою алгоритму є знаходження поля найближчих сусідів(nearest-neighbor field, $NNF$) що є картою зсувів - кожній точці одного зображення відповідає точка іншого зображення зсунута на значення відповідної точки у $NNF$. Для ділянки зображення із певними координатами неважко знайти відповідну ділянку на іншому зображенні шляхом перевірки усіх можливих зсувів. Однак, якщо необхідно знайти відповідність для всіх ділянок задача стає дуже складною обчислювально. Тому алгоритм виконується у рандомізований підхід для прискорення швидкості обчислень. Алгоритм має три основні складові. Спочатку поле найближчого сусіда заповнюється або випадковими зміщеннями, або деякою попередньою інформацією. Далі до NNF застосовується ітеративний процес оновлення, в якому хороші зсуви патчів розповсюджуються на сусідні пікселі, після чого винокується випадковий пошук в околицях найкращого зміщення.

Функція відповідності

У якості критерію відповідності D двох патчей f та g можна використати різні функції. Найбільш вживаними є:

Сума квадратів різниць (Sum of Squared Differences, SSD).

$D=\sum _{i,j\in R}(f(i,j)-g(i,j))^{2}$

Сума модулей різниць (Sum of Absolute Differences, SAD).

$D=\sum _{i,j\in R}|(f(i,j)-g(i,j))|$

Сума квадратів різниць або сума модулей різниць із нульовим середнім (ZSSD, ZSAD) - для кожного патча визначається та видаляється середнє значення.

$D=\sum _{i,j\in R}((f(i,j)-{\hat {f}})-(g(i,j)-{\hat {g}}))^{2}$

Нормалізована взаємна кореляція (Normalized Cross Correlation, NCC)

$D={\frac {\sum _{i,j\in R}f(i,j)*g(i,j)}{{\hat {f}}*{\hat {g}}}}$

Ініціалізація

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

Ітерація

Після ініціалізації алгоритм ітеративно виконує покращєння поля найближчих сусідів. Кожна ітерація послідовно опрацьовує пікселі зображення в фіксованому порядку (зліва направо, згори до долу) і включає дві фази - поширення та випадкового пошуку.

Поширення

На цій фазі ми намагаємось вдосконалити $f(x,y)$ в точці (х, у) використовуючи відомі зсуви сусідів $f(x-1,y)$ та $f(x,y-1)$, припускаючи, що зсуви патчів, ймовірно, будуть однаковими. Тобто алгоритм приймає в якості нового значення $f(x,y)$ таке, що мінімізує $\arg \min \limits _{(x,y)}{D(f(x,y)),D(f(x-1,y)),D(f(x,y-1))}$ . Тож якщо $f(x,y)$ має правильне значення зсуву і знаходиться у когерентній області $R$, то всі пікселі з $R$ знизу та праворуч від $f(x,y)$ будуть заповнені правильним значенням зсуву. Крім того, часто для парних ітерації напрямок поширення інвертується і шукаются нові значення як$\arg \min \limits _{(x,y)}\{D(f(x,y)),D(f(x+1,y)),D(f(x,y+1))\}$ .

Випадковий пошук

Позначимо через $v_{0}=f(x,y)$ поточне значення сзуву. Для кожної точки ми намагаємось покращити $f(x,y)$ шляхом тестування декількох кандидатів, зсув від яких до $v_{0}$ між кроками пошуку експоненційно спадає:

$u_{i}=v_{0}+w\alpha ^{i}R_{i}$

де $R_{i}$ є рівномірно розподіленим випадковим числом із діапазону $[-1,1]\times [-1,1]$, $w$ - початковий радіус вікна пошуку кандидата, що дорівнює розміру зображення (якщо відсутня додаткова інформація, що обмежує діапазон пошуку) і $\alpha$ є фіксованим коефіцієнтом зменшення вікна пошуку між ітераціями, значення якого часто береться як 1/2. Ця частина алгоритму дозволяє $f(x,y)$ вистрибнути з локального мінімуму шляхом випадкового процесу.

Критерії зупинки

Часто у якості критерію зупинки задаєтся максимальне число ітерацій, як правило 4 ~ 5. Навіть при невеликій кількості ітерацій алгоритм працює дуже добре. Також у якості критерію можна встановити максимальне значення похибки.

Посилання

• Connelly Barnes, Eli Shechtman, Adam Finkelstein, Dan B Goldman(2009), PatchMatch: A Randomized Correspondence Algorithm for Structural Image Editing [Архівовано 21 вересня 2021 у Wayback Machine.]