Как организовать поиск среди миллиона и более изображений?

Question

[Ринат Бакиев]

Есть задача поиска похожих изображений в базе. Решение сделали на нейронках (keras), выдергиваем фичи из картинок при помощи сетки vvg16 (слой 4096). Работает приемлемо на небольших объемах, используем косинусное расстояние.
Проблема в том что база очень большая... около 1млн картинок и это не предел. Вектора на 100.000 весят примерно 5-7 гб. Соответственно на 1млн картинок векторов на 50-70гб. Поиск медленный и база в ОЗУ уже не помещается, а с диска очень долго. Причем база будет пополняться, меняться и хранить ее в виде одного файла hd5 не удобно.

Пока пошли таким путем. Загоняем все вектора в базу данных (к примеру mariadb, хотим PostgreSQL). Потом загружаются вектора партиями и хешируются решением (https://github.com/pixelogik/NearPy). В памяти остается как бы хеши к базе и айди картинок. Поиск быстрый, весит мало, но не точный (сравниваются уже не косинусы, а похожие находятся по чувствительному хэшу)

Может знает кто еще другие решения?

Comments

[Everything_is_not_so_bad]

Поиск насколько медленный? Хотел бы понять на примерах какие картинки считаются практически идентичными, близко похожими, а какие несхожими. Скажем на одном изображении тарелку на столе сдвинули с места на 5 см. Это будет считаться схожими или разными?

[Рустам Салаватов]

Роман Мирр: если сдвинули будет похожии... даже если повернули немного, и если сняли немного под другим углом, цветом. Это сейчас получается с помощью векторов vgg16 делать, не идеально... но получается.

вот в основе тут описано https://habrahabr.ru/post/314490/

[hOtRush]

не особо в теме, но почему не использовать elasticsearch или подобные?

Answer 1

[Александр Пожарский]

Судя по : https://www.cs.toronto.edu/~frossard/post/vgg16/vg...
Я бы сделал следующее :
Хранил бы :
- изображение (возможно - уменьшенные копии)
- 4096-компонентный вектор
- выходной вектор (который из 1000 компонентов)
Возможно бы снизил размерность ещё слоем, но это уже потребует дообучения сети.

Тогда :
- сперва извлекаем из изображения векторы (на 1000/4096 компонентов)
- считаем косинусное расстояние по меньшему вектору.
- отбрасываем варианты, у которых косинусное расстояние больше определенной границы
- считаем расстояние по большему вектору
- отбрасываем варианты с большим расстоянием
- среди оставшихся - сравниваем изображения (возможно - уменьшенные копии)

По идее отброс тех изображений у которых сильно отличается результат классификации должен снизить количество вычислений. Но по хорошему или экспериментировать нужно, или считать.

p.s. ну и конечно - готовиться параллелить задачу :-)

Comments

[Рустам Салаватов]

спасибо за ответ, да примерно так и думали вначале... но показалось сложно слишком, искали вариант попроще...типа NearPy.
планируются в будущем кластеризовать базу (обувь, футболка и тп) это бы снизило сложность. будем пробовать да, работы с этим похоже будет много)

Answer 2

[Everything_is_not_so_bad]

Для сравнения изображений использую перцептивный хэш, используя привязку к библиотеке libphash0 и расстояние Хэмминга (mysql: bit_count(), postgresql: hamming_distance). Каждый хэш представляет из себя 64-битное число. Вроде как совсем мало занимает.

Ссылки:
https://habrahabr.ru/search/?q=%5Bphash%5D&target_...
https://habrahabr.ru/post/211773/

Выявлять дубликаты можно так:

select s1.name, s2.name from images s1
inner join
(
    select t2.name, t2.phash as dup_phash, hamming_distance((t1.phash), (t2.phash)) as dist from images t1
    inner join images t2 on dist between 1 and 8
    group by dist
    having count(*) > 1
) s2 on dist between 0 and 8

Проиндексировать по images.phash .

Comments

[Рустам Салаватов]

спасибо, интересно. но есть да свои минусы судя по статье... ищет только дубликаты или часть а не похожии. и скорость вроде тоже не очень быстрая. У вас какая скорость?
Надо отклик в не более 1-2 секунд в идеале

[Рустам Салаватов]

и это как раз похоже на работу с хешем, как тут https://github.com/pixelogik/NearPy

[Everything_is_not_so_bad]

Рустам Салаватов: Алгоритм pHash находит различия в изображения, между которыми небольшие отличия в цвете, когда объект немного сдвигается с места, изображение перевёрнуто по вертикали. Отличия выражаются в расстоянии Хэмминга между двумя хэшами, которое можно подобрать экспериментально, в зависимости от нужд, или использовать в запросах каждый раз как пользовательский параметр.

В SQL запросе выше определяются любые дубликаты в коллекции изображений.
Для определения дубликатов у заданного изображения нужен другой запрос:

SELECT hamming_distance('e00e2f5e780fe7c0', phash) as dist, name FROM images
WHERE dist between 1 and 8

Проект мой экспериментальный, он едва начат и ещё не производил замеров скорости отклика. Пока использовал лишь SQLite. Нужно произвести замеры и постараюсь позже написать результаты.

Answer 3

[Юрий]

взять N серверов и сделать шардирование, главное чтобы на каждом памяти хватало.

тем более насколько я понимаю каждый вектор нужно проверять отдельно (индексы не катят) сложность O(1), то тем более при увеличеннии колич картинок в одной базе начнет расти время только для поиска, не считая загрузку с диска. при шардированиии время не будет расти, так как поиск будет параллельный.

Comments

[Рустам Салаватов]

да спасибо, это больше про хранение векторов... а как искать в этой огромной базе потом быстро похожие, близкие по косинусу или еще как?

[Юрий]

Рустам Салаватов: если честно плохо понял ваш способ, т.к. не занимаюсь таким. но при шардировании можете делать также как делали изначально, если при 100к вас устривала скорость то при распределении будет примерно то же, только загрузка на неск серверов.

Answer 4

[Сергей]

https://ru.wikipedia.org/wiki/Locality-sensitive_h... -- может поможет идея.

Answer 5

[ThunderCat]

Как вариант - делать копии изображения в небольшом разрешении, и по ним производить сличение. Например, делаем фотки в ширину 50 пикселей, и сравнивать уже их.

Comments

[Ринат Бакиев]

и что там в итоге сравнивать? ) когда всего 2500 пикселей, а изображений более 1,5 млн

[ThunderCat]

Ринат Бакиев: вы ищете похожие изображения, аппроксимируйте на таком размере (это в разы быстрее и проще), гугл раньше так делал, так что не стесняйтесь ).

Answer 6

[Roman Mindlin]

Сократите хоть немного пространство признаков и у вас все поместится в память. Дисперсию при этом, я думаю, вы не потеряете почти нисколько.

Comments

[Ринат Бакиев]

интересно. действительно стоит попробовать в количестве признаков. у вас может быть уже был такой опыт?

[Roman Mindlin]

Ринат Бакиев: ну начните хотя бы с PCA: https://ru.wikipedia.org/wiki/%D0%9C%D0%B5%D1%82%D...
На питоне это очень просто сделать scikit-learn.org/stable/modules/generated/sklearn....

[Рустам Салаватов]

Roman Mindlin: спасибо, да надо уменьшить пространство а потом похоже отсюда использовать будем какой-нибудь метод https://github.com/DBWangGroupUNSW/nns_benchmark

[Roman Mindlin]

Рустам Салаватов: это будет работать быстрее scikit? На самом деле, еще забыл сказать, что проверьте свои признаки на значимость и на мультиколлинеарность. Может быть их естественным образом станет поменьше

Answer 7

[pfg21]

Поставить сервер с 64-94 ГБ памяти ?? это будет серьезное вложение, но в дальнейшем окупится скоростью и т.д.
Вариант2: взять такой сервер в облаке: стартовых затрат меньше, покрайне мере можно пару месяц погонять и уточниться в своих потребностях и уже думать о локальной железяке.

Comments

[Ринат Бакиев]

увеличение расходов - это самое легкое ))

Answer 8

[Артемий]

Наверно Вам поможет распределенное хранение и параллельная обработка данных

Answer 9

[potapm]

Насколько я понимаю, просто прогоняется вся сеть и потом храниться предпоследний слой для каждого изображения. Размер предпоследнего слоя можете задать любого размера в зависимости от необходимой точности.