PatchMatch: латки, знайдені навмання
У серпні 2009 року на SIGGRAPH Коннеллі Барнс, Елі Шехтман, Адам Фінкельштейн і Ден Голдман (Принстон, Adobe) описали PatchMatch — пошук схожих латок у зображенні, у 20–100 разів швидший за kd-дерева: спершу випадкові збіги, тоді добрі передаються сусідам і уточнюються випадковим пошуком.
Чому це важливо
Латкові методи редагування давали добрі результати, але рахували хвилинами, і користуватися ними інтерактивно було неможливо. PatchMatch зробив їх справою секунд: заповнення діри, зміну пропорцій і перенесення частин зображення можна стало виконувати й поправляти просто під час роботи, чого не було доти.
ACM Transactions on Graphics 28(3). Прискорення 20–100 разів — проти kd-дерев із PCA на латках 7 × 7, при приблизно вдвадцятеро меншій пам’яті; версія для відеокарти ще приблизно в 7 разів швидша за процесорну. Збіжність перевірено на зображеннях до 2 мегапікселів. Інструменти статті — ретаргетинг, завершення й перетасування з обмеженнями, які задає користувач (лінії, що мають лишитися прямими). Photoshop у статті не згаданий; що метод став заливкою з урахуванням вмісту в Photoshop CS5, автори скажуть у Communications of the ACM 2011 року.