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 {\mathrm{\backslash 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 {\mathrm{\backslash 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 Шаблон:Webarchive