PatchMatch — це алгоритм швидкого знаходження відповідностей між невеликими квадратними ділянками зображення (або патчами).. Алгоритм може бути використано у різних додатках, таких як видалення об’єктів із зображень, перестановка або переміщення вмісту зображень, перенацілювання або зміна співвідношення сторін зображень, оцінка оптичного потоку або стерео відповідність .
Алгоритм Метою алгоритму є знаходження поля найближчих сусідів(nearest-neighbor field, ) що є картою зсувів - кожній точці одного зображення відповідає точка іншого зображення зсунута на значення відповідної точки у . Для ділянки зображення із певними координатами неважко знайти відповідну ділянку на іншому зображенні шляхом перевірки усіх можливих зсувів. Однак, якщо необхідно знайти відповідність для всіх ділянок задача стає дуже обчислювальноскладною . Тому алгоритм виконується у рандомізований підхід для прискорення швидкості обчислень. Алгоритм має три основні складові. Спочатку поле найближчого сусіда заповнюється або випадковими зміщеннями, або деякою попередньою інформацією. Далі до NNF застосовується ітеративний процес оновлення, в якому хороші зсуви патчів розповсюджуються на сусідні пікселі, після чого винокується випадковий пошук в околицях найкращого зміщення.
Функція відповідності Як критерій відповідності D двох патчей f та g можна використати різні функції. Найбільш вживаними є:
Сума квадратів різниць (Sum of Squared Differences, SSD).
Сума модулей різниць (Sum of Absolute Differences, SAD).
Сума квадратів різниць або сума модулей різниць із нульовим середнім (ZSSD, ZSAD) - для кожного патча визначається та видаляється середнє значення.
Нормалізована взаємна кореляція (Normalized Cross Correlation, NCC)
Ініціалізація При ініціалізації з випадковими зсувом використовуються незалежні однорідні вибірки по всьому діапазону зображення . Цей алгоритм дозволяє обійтися без початкового припущення щодо відповідностей на зображеннях, а також має властивість уникати потрапляння у локальні мінімуми.
Ітерація Після ініціалізації алгоритм ітеративно виконує поліпшення поля найближчих сусідів. Кожна ітерація послідовно опрацьовує пікселі зображення в фіксованому порядку (зліва направо, згори до долу) і включає дві фази - поширення та випадкового пошуку.
Поширення На цій фазі ми намагаємось вдосконалити в точці (х, у) використовуючи відомі зсуви сусідів та , припускаючи, що зсуви патчів, ймовірно, будуть однаковими. Тобто алгоритм приймає новим значенням таке, що мінімізує . Тож якщо має правильне значення зсуву і знаходиться у когерентній області , то всі пікселі з знизу та праворуч від будуть заповнені правильним значенням зсуву. Крім того, часто для парних ітерації напрямок поширення інвертується і вишукуються нові значення як .
Випадковий пошук Позначимо через поточне значення зсуву. Для кожної точки ми намагаємось покращити шляхом тестування декількох кандидатів, зсув від яких до між кроками пошуку експоненційно спадає:
де є рівномірно розподіленим випадковим числом із діапазону , - початковий радіус вікна пошуку кандидата, що дорівнює розміру зображення (якщо відсутня додаткова інформація, що обмежує діапазон пошуку) і є фіксованим коефіцієнтом зменшення вікна пошуку між ітераціями, значення якого часто береться як 1/2. Ця частина алгоритму дозволяє вистрибнути з локального мінімуму шляхом випадкового процесу.
Критерії зупинки Часто критерієм зупинки закладається максимальне число ітерацій, як правило 4 ~ 5. Навіть при невеликій кількості ітерацій алгоритм працює дуже добре. Також як критерій можна встановити максимальне значення похибки.
Посилання
Connelly Barnes, Eli Shechtman, Adam Finkelstein, Dan B Goldman(2009), PatchMatch: A Randomized Correspondence Algorithm for Structural Image Editing