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

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

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

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

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

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

p.s. ну и конечно - готовиться параллелить задачу :-)
Ответ написан
riky
@riky
Symfony / Laravel
взять N серверов и сделать шардирование, главное чтобы на каждом памяти хватало.

тем более насколько я понимаю каждый вектор нужно проверять отдельно (индексы не катят) сложность O(1), то тем более при увеличеннии колич картинок в одной базе начнет расти время только для поиска, не считая загрузку с диска. при шардированиии время не будет расти, так как поиск будет параллельный.
Ответ написан
2ord
@2ord
продвинутый чайник
Для сравнения изображений использую перцептивный хэш, используя привязку к библиотеке 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 .
Ответ написан
ThunderCat
@ThunderCat
{PHP, MySql, HTML, JS, CSS} developer
Как вариант - делать копии изображения в небольшом разрешении, и по ним производить сличение. Например, делаем фотки в ширину 50 пикселей, и сравнивать уже их.
Ответ написан
@kgbplus
Сократите хоть немного пространство признаков и у вас все поместится в память. Дисперсию при этом, я думаю, вы не потеряете почти нисколько.
Ответ написан
@pfg21
ex-турист
Поставить сервер с 64-94 ГБ памяти ?? это будет серьезное вложение, но в дальнейшем окупится скоростью и т.д.
Вариант2: взять такой сервер в облаке: стартовых затрат меньше, покрайне мере можно пару месяц погонять и уточниться в своих потребностях и уже думать о локальной железяке.
Ответ написан
MetaAbstract
@MetaAbstract
Разработка интерактивных функциональных прототипов
Наверно Вам поможет распределенное хранение и параллельная обработка данных
Ответ написан
@potapm
Насколько я понимаю, просто прогоняется вся сеть и потом храниться предпоследний слой для каждого изображения. Размер предпоследнего слоя можете задать любого размера в зависимости от необходимой точности.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы