Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 32
Я конечно не вижу всей картины в целом, но похоже лупят из пушек по воробьям…
Задача решена, автору плюсы повсюду, но правильнее иметь одну точку заведения товаров в базу и строго карать если не так.
Я за вертикаль власти. Должен быть один начальник у всех этих княжеств, а иначе такая свистопляска с наименованиями будет продолжаться. Рублём только можно супер-босса убедить, на сравнении «до» и «после», хотя чаще и к сожалению, нет полёта фантазии и планов — «и так же работает, чо нормально, мне хватает...»
Автор — скажите, как быстро работает ваш алгоритм поиска похожего изображения по одному образцу на ваших 3млн.?
Я за вертикаль власти. Должен быть один начальник у всех этих княжеств, а иначе такая свистопляска с наименованиями будет продолжаться. Рублём только можно супер-босса убедить, на сравнении «до» и «после», хотя чаще и к сожалению, нет полёта фантазии и планов — «и так же работает, чо нормально, мне хватает...»
Автор — скажите, как быстро работает ваш алгоритм поиска похожего изображения по одному образцу на ваших 3млн.?
но правильнее иметь одну точку заведения товаров в базу и строго карать если не так.
Как я понимаю, софт написан как раз для такой точки, где заводятся в базу товары из разных источников.
Вы не представляете насколько я с вами согласен!
Для мня вообще, криво заполненные базы — это одна из постоянных проблем, с которыми приходится сталкиваться. Но увы, обычно базы начинают заполнятся криво с самого начала и спустя X лет очень сложно исправить положение. В такой ситуации обычно необходимо тотально перебирать базу, но под это как правило нет человекочасов. Куда лучше было бы заполнять всё правильно сразу, но увы…
По поводу скорости — точных цифр сейчас не назову, т.к. дело было год назад и разумеется всего не сохранилось, там вся работа по поиску перекладывается на плечи MySQL, и во многом зависит уже от настроек самой MySQL. Результаты был в пределах секунды, но это явно не верх совершенства.
Для мня вообще, криво заполненные базы — это одна из постоянных проблем, с которыми приходится сталкиваться. Но увы, обычно базы начинают заполнятся криво с самого начала и спустя X лет очень сложно исправить положение. В такой ситуации обычно необходимо тотально перебирать базу, но под это как правило нет человекочасов. Куда лучше было бы заполнять всё правильно сразу, но увы…
По поводу скорости — точных цифр сейчас не назову, т.к. дело было год назад и разумеется всего не сохранилось, там вся работа по поиску перекладывается на плечи MySQL, и во многом зависит уже от настроек самой MySQL. Результаты был в пределах секунды, но это явно не верх совершенства.
Секунда — это очень неплохо, спасибо за ответ.
В данном случае секунда это неплохо.
Но проверил на своей базе с 700 тыс хешами:
Простая оптимизация запроса дает неплохой прирост.
Один хеш на изображение решает задачу полного либо совсем частичного совпадения. Но при задаче кластеризации дубликатов из базы, оказывается, что решения через SQL запросы не годятся.
Например, имеется 1000 изображений, которые надо найти в базе.
Реализация через запросы будет отрабатывать ~3-5 минут (если запрос за запросом). Если одним большим запросом, то это примерно ~20 секунд.
А если просто сделать линейный поиск в С++ и руками подсчитать, то это ~8 секунд.
Но и это как-то сильно туго. Поэтому дальше идет уже тяжелая артиллерия. Но это уже совсем другая история.
Но проверил на своей базе с 700 тыс хешами:
mysql> SELECT * FROM ( SELECT *, BIT_COUNT( 5175267106820201044 ^ hash ) as d FROM image_hash ORDER BY d LIMIT 0, 100 ) AS s WHERE d <= 7;
1 row in set (0.54 sec)
mysql> SELECT *, BIT_COUNT( 5175267106820201044 ^ hash ) as d FROM image_hash ORDER BY d LIMIT 0, 100;
100 rows in set (0.49 sec)
mysql> SELECT * FROM image_hash WHERE BIT_COUNT( 5175267106820201044 ^ hash ) <= 7;
1 row in set (0.35 sec)
Простая оптимизация запроса дает неплохой прирост.
Один хеш на изображение решает задачу полного либо совсем частичного совпадения. Но при задаче кластеризации дубликатов из базы, оказывается, что решения через SQL запросы не годятся.
Например, имеется 1000 изображений, которые надо найти в базе.
Реализация через запросы будет отрабатывать ~3-5 минут (если запрос за запросом). Если одним большим запросом, то это примерно ~20 секунд.
А если просто сделать линейный поиск в С++ и руками подсчитать, то это ~8 секунд.
Но и это как-то сильно туго. Поэтому дальше идет уже тяжелая артиллерия. Но это уже совсем другая история.
Так и есть! Но этого никто и не скрывал. Прочитайте вступление, пожалуйста. Именно из пушки, именно по воробьям, и притом ещё на рукотворном велосипеде с квадратными колёсами… было просто интересно попробовать.
Ой, ну пожалуйста, ну используете C или C++, ну нужны типы с фиксированной длинной, ну уже всё сделано за вас (http://en.cppreference.com/w/c/types/integer или en.cppreference.com/w/cpp/types/integer)… Ну или если это Windows-only, так там тоже уже всё есть… Ну не нужно typedef-ить всё подряд.
P.S. Просто наболело уже: сейчас правлю проект мультиплатформенный (требование, заложенное изначально), так в нём чувак напереопределял всяких #define WORD и #define DWORD и кучу ещё всяких костылей через #define и typedef, чтобы как в Windows, наверное потому что в Linux этих типов нет…
P.S. Просто наболело уже: сейчас правлю проект мультиплатформенный (требование, заложенное изначально), так в нём чувак напереопределял всяких #define WORD и #define DWORD и кучу ещё всяких костылей через #define и typedef, чтобы как в Windows, наверное потому что в Linux этих типов нет…
А есть идеи, когда ситуация точь такая же, только даже картинок нет?
Кластеризация. И, главное, интерфейсы и процессы, позволяющие легко распутать ошибки первого (ложное отнесение сущности к кластеру) и второго (ложное неотнесение) рода без необходимости откатывать транзакции (скажем, перепечатывать и заменять накладные на всех точках).
Однажды решал аналогичную задачу, только без картинок. Данные были в БД Oracle. Написал небольшой скрипт, который разбивает каждое название на части по словам («Ваза с рисунком 'узор треугольный'» -> «ваза», «с», «рисунком», «узор», «треугольный»), далее сравнивает отдельные части-слова. Вычисляет коэффициент совпадения по принципу, чем больше составляющих совпало, тем лучше. В результате каждому элементу из списка 1 сопоставлялось несколько наиболее подходящих элементов из списка 2. Финальное сопоставление делалось вручную, к сожалению:(
В моем случае я мог рассчитывать, что один и тот же предмет в разных списках назван одними и теми же словами. Это, конечно, не всегда сработает. На примере из статьи:
1 «Ваза с рисунком 'узор треугольный'»,
2 «Ваза А-563»,
3 «Ваза с рисунком»,
4 просто «Ваза»
Мой алгоритм позволит сопоставить 1 и 3, а вот с пунктами 2 и 4 — без картинки не обойтись. Хотя зависит от того, на сколько широк ассортимент «ваз».
В моем случае я мог рассчитывать, что один и тот же предмет в разных списках назван одними и теми же словами. Это, конечно, не всегда сработает. На примере из статьи:
1 «Ваза с рисунком 'узор треугольный'»,
2 «Ваза А-563»,
3 «Ваза с рисунком»,
4 просто «Ваза»
Мой алгоритм позволит сопоставить 1 и 3, а вот с пунктами 2 и 4 — без картинки не обойтись. Хотя зависит от того, на сколько широк ассортимент «ваз».
Да, тоже интересный подход. Спасибо за совет!
Я у себя еще сверху юзал Левенштейна, а если пыха, то similar_text. А потом уже на ручное сопоставление.
Пару месяцев в 2005 работал на проекте по поддержке бэкенда одного швейцарского сайта, агрегирующего данные по отелям из нескольких систем про резервированию мест в отелях, там тоже была похожая система, вроде с некоторыми элементами «самообучения». Из 250000 отелей после их матчера 15-20 тысяч приходилось «доматчивать» вручную. Это я к оценке релеватности подобных методик…
А мне понравилось! Хорошее решение смело звучащей задачи. Встречал очень мудрёные решения подобных задач, без использования хешей. Тут же всё просто
Типовая задача дедуб(п)ликации неструктурированных каталогов.
На объеме в 10Кзаписей еще применим такой или подобный подход, а дальше (от 100к уникальных записей) задачи Data Quality и MDM систем.
Задачу поддержки решения смотрели?
Замена картинки поставщиком? записи разъедутся обратно или как то будет поддерживаться связка «Ваза с рисунком 'узор треугольный'» =«Ваза А-563»?
Точность объединения?
Возможности ошибочных объединений? когда «Пила двуручная Дружба = Забор из досок обрезный
Записи формируются динамически по новым прайсам или статикой?
На объеме в 10Кзаписей еще применим такой или подобный подход, а дальше (от 100к уникальных записей) задачи Data Quality и MDM систем.
Задачу поддержки решения смотрели?
Замена картинки поставщиком? записи разъедутся обратно или как то будет поддерживаться связка «Ваза с рисунком 'узор треугольный'» =«Ваза А-563»?
Точность объединения?
Возможности ошибочных объединений? когда «Пила двуручная Дружба = Забор из досок обрезный
Записи формируются динамически по новым прайсам или статикой?
Месье знает толк в программировании.)
Так в итоге pHash оказался намного лучше обычного хэша? Ложные срабатывания пропали совсем?
Интересно, сколько денег удалось сэкономить?
на всякий случай pHash имеет сгенереный php Extension
github.com/sdepold/pHash/tree/master/bindings/php
github.com/sdepold/pHash/tree/master/bindings/php
Отличное решение практического вопроса и отличная статья. Я бы добавил в статью еще ссылку на расширение для пхп, ссылка на него есть в комментариях.
Интересно, какие алгоритмы для сравнения изображений используют крупные поисковые системы.
Интересно, какие алгоритмы для сравнения изображений используют крупные поисковые системы.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Нестандартное применение IT в быту: парсинг, перцептивный хеш, сравнение изображений = оптимизация расходов