У своєму виступі Олександр Крайнов розповів яким способом Яндекс.Зображення кластерізіровалі дублікати зображень. Іншими словами, виділяли і фільтрували дублі картинок. Де основна ідея була в тому, щоб виділити контури зображення за допомогою фільтра DoG. після чого знайти ключові точки і отримати їх дескриптори.
Кластеризація дублікатів зводиться до пошуку збігів дескрипторів. Це і є «цифровий формат» ключових точок зі статті Кластеризация дублікатів в пошуку по картинках.
Але хотілося б трохи докладніше дізнатися, що це за дескриптори і як робити по ним пошук.
Дескриптори
Ключові точки - це точки, які в ідеалі не повинні змінюватися при зміні або модифікації зображення.
Дескриптори - це, в загальному вигляді, згортка характеристик і уявлення ключових точок у форматі доступному для перевірки на збіг.
Пошук ефективного виділення ключових точок, їх дескрипторів, а також методів перевірки на збіги, все ще залишається на порядку денному.
Але треба з чогось починати, тому звернемося на допомогу до бібліотеки OpenCV.
Перше на що кидається погляд - це дескриптори SURF.
Які обіцяють надзвичайну точність. Що і підтверджується після тестів.
Але є кілька нюансів.
Дескриптори SURF - це вектора з 128 (або 64) чисел на одну ключову точку. Перевірка на збіг виконується пошуком найближчої точки (або навіть двох). І чим ближче точка, тим краще.
Виходить що на зображення з 1 000 ключових точок, буде потрібно 128 000 чисел з плаваючою точкою.
Крім того, саме виявлення точок досить складна операція і вимагає чимало часу. Що не дозволяє ефективно використовувати даний алгоритм на невеликих пристроях. До того ж сам алгоритм закритий і запатентований (в США).
Після ознайомлення з SIFT і SURF, захотілося чогось простого в реалізації з можливістю застосувати на невеликому сервері або пристрої.
перцептивні хеші
І були знайдені перцептуальние або перцептивні хеші.
Завдання яких в тому, що б при невеликій зміні зображення хеш також незначно змінювався.
Перевірка на збіг проводиться підрахунком кількості відрізняються позицій між двома хешамі. Тобто підрахунок відстані Хеммінга. І чим менше воно, чим менше різняться елементів, тим більше збіг.
Даний метод розрахований на пошук повних або часткових дублікатів зображення. Тобто при значній зміні формату зображення яке втручання в контент призводить до неможливості перевірки на збіг, так як хеш-кодування будуть помітно відрізнятися.
Іншими словами перцептивні хеши не годяться для пошуку полудублікатов.
Виходячи з цього була зроблена спроба об'єднати SURF дескриптори і перцептивні хеші з метою вирішити проблему пошуку нечітких полудублікатов.
Метод грунтується на кластеризації ключових точок таким чином, щоб центри кластерів збігалися на оригінальному і кропнутих зображенні. А далі вироблялося виділення фрагмента зображення навколо ключової точки і отримання перцептивного хешу. В результаті одне зображення давало близько 200 кроп нарізки і їх хешів.
У даного методу є два з половиною значні недоліки:
1. низька швидкість перевірки на збіг на великому наборі хешів. Пошук по 1 млн хешів займало 20 секунд
2. низька швидкість отримання ключових точок
3. низька точність, безліч помилкових спрацьовувань, високі вимогу до цільової базі, годиться не для всіх картинок, вимагає премодерації і т.д
Сама ідея про те, що б з зображення виділялося кілька відбитків (fingerprint), які можна було б просто зіставити один з одним, заворожувала.
Тому було вирішено спробувати знайти рішення цих проблем.
Низька швидкість вибірки
Складність пошуку і підрахунку відстані Хеммінга на великому наборі даних є самостійною проблемою і вимагає незалежного підходу.
Після деяких досліджень тематики виявилося, що існує безліч варіантів розв'язання проблеми.
Був обраний і реалізований найбільш ефективний з наявних алгоритм названий HEngine. який дозволив в
60 раз прискорити вибірку з бази даних.
SURF і ключові точки
Так як ми працюємо вже з бінарними хешамі, або відбитками, а збіг вважаємо відстанню Хеммінга, то дивно використовувати таку махину як SURF і варто було б розглянути інші методи отримання ключових точок і дескрипторів.
У загальному вигляді OpenCV надає два типи дескрипторів:
- Дескриптори з плаваючою точкою
- І бінарні дескриптори
Ось бінарні дескриптори як ніякі інші підходять для нашого завдання, тому що також використовують відстань Хеммінга для перевірки на збіги.
ORB: an efficient alternative to SIFT or SURF
OpenCV вже має у себе відмінну альтернативу SURF, яка мало того, що відкрита і без ліцензійних обмежень, так ще легше і працює швидше [1].
ORB - це Oriented FAST and Rotated BRIEF - поліпшена версія і комбінація детектора ключових точок FAST і бінарних дескрипторів BRIEF.
ORB має один істотний нюанс для нас - розмір дескрипторів 32 байта на одну точку.
Перевірка на збіг - це сума відстаней Хеммінга для кожного байта дескриптора (перший порівнюється з першим, другий з другим і тд).
У нашій задачі мається на увазі, що одна точка дає одне значення, а тут виходить 32, які треба ще й підсумувати з відповідними за індексом (перший з першим, другий з другим і тд) в цільової базі даних.
Так як наш хеш це 64бітние число, то потрібно 32 байта дескриптора стиснути в 8 байт і при цьому не сильно втратити в точності.
Після деяких тестів було вирішено спробувати ці 32 байта представити у вигляді матриці 16 × 16 біт. А потім цю матрицю пропустити через перцептивний хеш PHash. Результатом мало бути якраз 64 бітове число.
Тепер ми підійшли до інформації про продукт концепту.
Як працює індексація
1. Отримуємо ключові точки і дескриптори ORB, вибираємо кількість необхідних точок на зображенні.
2. Отримані дескриптори по 32 байта представляємо у вигляді бітової матриці 16 × 16.
3. Конвертуємо матрицю в 64бітние число за допомогою PHash.
4. Зберігаємо 64бітние відбитки в MySQL.
5. Вибираємо необхідну відстань Хеммінга і запускаємо демон HEngine, який буде виконувати пошук.
Як працює пошук
Виконуємо ідентичні кроки 1 - 3 з індексації, але тільки на запитуваній зображенні.
4. Робимо запит демону HEngine, який повертає всі хеші в заданому межі.
5. Якщо потрібно, відфільтрувати неактуальні результати.
Рис 1. Межа відстані Хеммінга 7. Сірі точки - це знайдені ключові точки. Зелені - збігаються точки. Червоні - збігаються стандартним ORB повним перебором.
А що в результаті?
В результаті вдалося вирішити кількох проблем:
- знайти спосіб швидкого підрахунку відстані Хеммінга на великому наборі даних
- позбутися від великого і незручного SURF
- збільшити швидкість виділення ключових точок і їх відбитків
- а також не втратити сильно в точності.
Що дозволило знаходити зображення по їх фрагменту, а також нечіткі полудублікати без великих обчислювальних ресурсів.
З огляду на те, що в залежності від налаштувань, описаний алгоритм через бінарні дескриптори ORB видає близько 1 000 хешів на картинку.
На базу в 1 000 зображень виходить 1 000 000 хешів в базі. І повний перебір всіх зображень в базі займає півтори хвилини.
Для порівняння, в своїй доповіді krainov Олександр Крайнов пояснює, що пошук дублікатів з 1 млн зображень у них займає близько двох хвилин.