Пошук картинок за контентом на PHP (CBIR), Red Spirit

Блог Олексія Таянчина

Пошук картинок за контентом на PHP (CBIR)

Є завдання – як за допомогою PHP на серверіперевірити на схожість два зображення. Потрібно це для того, щобзнаходити дублікати завантажених на сайт картинок. Основна проблема в тому, що потрібен такий алгоритм порівняння зображень, щоб він коректно сприймав однакові картинки з різною яскравістю, з шумами, з рамкою, з різним масштабом і зміщенням убік, та й з різними форматами, роздільною здатністю і глибиною кольору.

Є велика кількість алгоритмів, від простих, що базуються на порівнянні яскравості двох зображень, до наворочених, заснованих на “точках опори”, що сприймаються людським оком (як у tineye.com). Раніше я використав простецький скрипт, який був повністю реалізований на php і використав принцип різниці яскравостей. Але насправді цей метод виявився повною нісенітницею, який часом не міг розпізнати навіть два візуально абсолютно ідентичні зображення. Та й до того ж швидкість роботи залишала бажати кращого (з використанням хешів – близько 1.5 сік на 1000 порівнянь).

ImageMagick

Почав шукати більш прийнятних рішень. Виявив, що уImageMagick є цікавий метод Imagick::compareImages він самепорівняє два зображення (заздалегідь наведених до однієї висоти і ширини) і видає результат з урахуванням обраної метрики (див. приклад). Як результат повертається масив з двома значеннями: різниця картинок у візуальному вигляді (новий об'єкт картинкиimagick ) і числове значення, яке обумовлюєрізницю між зображеннями, чим воно менше, тим менша різниця. Якщо воно дорівнює нулю, то картинки 100% ідентичні.

Я провів експерименти з кількома сотнями різних зображень длятого, щоб достовірно визначити, який коефіцієнт різниці виставити, щоб картинки вважалися ідентичними. З прикладу нижче видно, що значення$d я перетворив за формулою$d = round($d/1000) для того, щоб можна було зручно підбирати граничні значення. Для себе я визначив його так:

• від 0 до 20 -однакові
• від 21 до 50 –подібні
• >50 -різні

У першому прикладі до вихідного зображення було застосовано зменшену яскравість та збільшену контрастність, а також додано жовту рамку та напис чорним кольором. Як видно, ці зображення були визнані "схожими". У другому прикладі була взята зовсім інша картинка, і видно, що результат набагато більший50, це означає, що картинки ніяким боком не схожі (хоча персонаж і один).

Щодоякості розпізнавання цим інструментом мені все сподобалося, але є мінус – швидкість. Сама собою швидкість завантаження зображення та його порівняння невелика (близько 1 сек на 1000 порівнянь). Але крім цього, треба ще привести зображення до загального розміру і перетворити до одного формату, все це значно впливає на швидкість. Особливі проблеми можуть виникнути зGIF, ImageMagick не завжди коректно читає гіфки з анімацією, тому доводиться додатково витягувати перший кадр анімації і працювати вже з ним (покадрово ImageMagick читає анімацію нормально). При цьому немає ніякої можливості витягти із зображення якийсь хеш або сигнатуру, яка характеризувала вже оброблене зображення і яку можна було б зберегти в базі даних для швидкого доступу. Максимум, що можна зробити, це зберігати в базі зменшені зображення (наприклад 30х30 png) і працювати з ним без зайвих перетворень. Але це по-перших зменшує якість розпізнавання, по-друге значно напружує БД, і по-третє негаразд сильно збільшується швидкість. Я вже робив у такий спосіб, швидкість була все ті ж 900-1000 порівнянь за сік.

Puzzle library

Потім не без допомоги товариша ConstXife я дізнався про бібліотечку Libpuzzle. Ця штука робить саме те, що мені треба. Програма поставляється вихідниками, окремо сама програма та окремо PHP-модуль до неї. Скомпілювалося і встановилося без проблем і запрацювало з першого разу.

Puzzle library мені відразу сподобалася своєю швидкістю та можливістю зберігати дуже компактні сигнатури зображень уMySQL. Тобто, щоб ефективно використовувати цю бібліотеку, потрібно заздалегідь індексувати всі зображення, які будуть задіяні в пошуку та зберегти індекс (сигнатури) у БД від куди і робити вибірку. Ось простий приклад використання Libpuzzle:

---