Методологія пошуку зображень на базі бінарного розбиття простору та перцептивного хешування

Анотація

Стаття розглядає питання щодо побудови систем пошуку зображень на основі зображення-зразка. Розглянуто основні
виклики, які стоїть на шляху вчених та інженерів при побудові подібних систем, розглянуто складові частини подібних систем і дано короткий огляд основних методів і технік, які використовувалися в цій галузі для реалізації основних складових
частин систем пошуку зображень. У якості одного з варіантів розв'язання подібного завдання запропоновано методологію
пошуку зображень на основі методу бінарного розбиття простору та методу перцептивного хешування. Дерева бінарного
розбиття простору являють собою структуру даних, отриману наступним чином: простір розбивається гіперплощиною на
два напівпростори, потім кожен напівпростір рекурсивно розбивається до тих пір, поки кожен вузол не буде містити тільки
тривіальну частину вхідних об'єктів. Алгоритми перцептивного хешування дозволяють отримати уявлення зображення у
вигляді хеш-значення довжиною 64 біта, при чому схожі зображення будуть представлені схожими хеш-значеннями. У якості метрики визначення відстані між хеш-значеннями використовується відстань Геммінга, яка підраховує кількість різних
біт. Для організації бази хеш-значень використовується vp-дерево, що є реалізацією структури бінарного розбиття простору.
Для експериментального дослідження методики був використаний набір даних Caltech-256, який містить 30607 зображень,
розбитих на 256 категорій, у якості алгоритмів перцептивного хешування були використані алгоритми Difference Hash, PHash та Wavelet Hash, дослідження проводилося в середовищі Google Colab. В рамках експериментального дослідження
було розглянуто стійкість алгоритмів хешування до модифікації, стиснення, розмиття, зашумлення та повороту зображення.
Крім того, було проведено дослідження процесу побудови vp-дерева та процесу пошуку зображень у дереві. В результаті
експериментів було встановлено, що кожен з алгоритмів хешування має свої переваги та недоліки. Так, алгоритм хешування, заснований на різниці значень пікселів на зображенні, виявився найшвидшим, але був не надто стійким до модифікації
та повороту зображень. Алгоритм P-Hash, заснований на використанні дискретного косинусного перетворення, показав
кращу стійкість до розмиття зображень, але виявився чутливим до стиснення. Алгоритм W-Hash, заснований на вейвлетперетворенні Гаара, дозволив побудувати найбільш ефективну структуру дерева і виявився стійким до модифікації та стиснення зображення. Запропонована методика не рекомендується для використання в системах пошуку зображень загального
призначення, однак, може бути корисна для пошуку зображень у спеціалізованих базах. В якості подальших шляхів покращення методики можна відзначити удосконалення структури vp-дерева, а також пошук більш ефективного методу представлення зображення, ніж перцептивне хешування.