Нестандартное применение IT в быту: парсинг, перцептивный хеш, сравнение изображений = оптимизация расходов

    В этой статье хочу поделиться интересной историей, о необычном решении одной интересной задачи, которая попалась мне год назад. Всё описанное в статье делалось, прежде всего, «just for fun» и из чистого академического интереса…
    Дело было год назад, как раз было свободное время и желание сделать что-нибудь полезное. Явно был некоторый интеллектуальный голод и острая нехватка чего-нибудь нового, какой-нибудь интересной задачи… Отсюда и попытки прилепить велосипед даже туда, куда он вообще не требовался… Собственно, таковым велосипедом и является всё нижеописанное…

    1. Задача


    На одном торгово-закупочном предприятии, достаточно остро стоял вопрос оптимизации закупок. У предприятия было несколько десятков основных поставщиков, но при этом у многих поставщиков пересечение товаров достигало 20-30%, а цены у всех разные. К сожалению, большинство товаров закупалось «по старой памяти», например привыкли, что товары группы A поставляет поставщик X, а товары группы Б поставщик Y, хотя если отбирать товары не группами, а штучно, то можно не слабо экономить. Для наглядности, покажу на примере:

    У поставщика X:
    Товар A1 -  11 руб.
    Товар A2 -  10 руб.
    Товар Б1 -  10 руб.
    Товар Б2 -  11 руб.
    
    У поставщика Y:
    Товар A1 -  10 руб.
    Товар A2 -  11 руб.
    Товар Б1 -  11 руб.
    Товар Б2 -  10.5 руб.
    

    Из таблицы очевидно, что A1 и Б2 выгоднее закупать у «Y», а A2 и Б1 у «X». Но легко и просто это на примере из 4-х позиций номенклатуры и 2-х поставщиков, а если номенклатура в сумме насчитывает десятки тысяч позиций, а поставщиков десятки?
    Казалось бы, в чём проблема — задача элементарная, но требует много несложных вычислений, руками объём не подъёмный, значит её нужно быстро переложить на плечи ПК и пожинать плоды? Всё было бы так, если бы была одна единая база со всей номенклатурой и ценами. Но увы, это утопия… база была в обычном, ужасном состоянии помойки, в котором могли кое-как разобраться только те кто каждый день и сваливал эту кучу мусора. С ценами всё ещё хуже, они вообще размазаны по разным каталогам, прайсам, сайтам. При попытке как-нибудь это каталогизировать и собрать воедино, становится очевидно, что это крайне трудно без ручного вмешательства. Один поставщик использует артикул производителя, другой ставит свой, а третий вообще не указывает их в прайсах. Названия практически нигде не совпадают, например один и тот же товар может называться: «Ваза с рисунком 'узор треугольный'», «Ваза А-563», «Ваза с рисунком», наконец, просто «Ваза» :)
    Значит, по названиям соединять было тоже абсолютно бесполезно.

    2. Безумная идея


    И тут появилась безумная идея. Специфика товара была таковой, что практически везде была картинка, притом, картинки очень часто поставщики брали в одном месте, или вообще друг у друга. Было одно «НО», картинки естественно были разного размера, могли даже отличаться пропорции. Значит сравнение «в лоб» нам не поможет. Но, ведь, Яндекс же как-то находит похожие изображения? А почему бы и нам не попробовать?!? Решено!

    Изучение литературы, чтение гугла, статей, дало представление о том, как работает поиск похожих изображений. Вкратце: строятся хеши изображений, а потом уже хэши между собой и сравниваются. Основные различия именно в хеш-функциях. Самый простой и быстрый, как в реализации, так и в самой сложности расчётов — перцептивный хеш «по среднему значению».
    Вкратце принцип работы: изображение сжимается в квадрат, например 16x16, затем из цветного изображения получаем изображение в градациях серого, затем, по точкам квадрата считаем среднее значение цвета, а потом во второй проход для каждой точки ставим 0 или 1, в зависимости от того, цвет этой точки меньше или больше среднего значения. Полученная последовательность 0-ей и 1-иц и есть искомый нами хеш.

    Для того чтобы сделать быстро прототип было решено использовать ImageMagick для обработки картинок, а в качестве скриптового языка был выбран php.
    В качестве материала для тестов я взял изображение «Хризантема.jpg», из стандартного набора Windows. Первый файл я назвал test1.jpg, потом взял исходный файл и исказил пропорции, сохранив под именем test2.jpg. В качестве 3-его образца я взял «Пустыня.jpg» и назвал его test3.jpg. Вот они:

    Изображения для теста





    Далее вызываем ImageMagick для предварительной обработки:
    E:\ImageMagick\convert.exe E:\Article\img\test1.jpg -resize 16x16! -colorspace gray E:\Article\img\_test1.jpg
    E:\ImageMagick\convert.exe E:\Article\img\test2.jpg -resize 16x16! -colorspace gray E:\Article\img\_test2.jpg
    E:\ImageMagick\convert.exe E:\Article\img\test3.jpg -resize 16x16! -colorspace gray E:\Article\img\_test3.jpg
    


    Получаем:
    Изображения 16x16 grayscale





    Далее считаем сам хеш:
    <?
    function getPerceptHash($imgName) {
    	$im = imagecreatefromjpeg($imgName);
    	
    	//В первом проходе считаем сумму, которую потом делим на 256 (16*16), чтобы получить среднее значение
    	$summ = 0;
    	for($i=0;$i<8;$i++){
    		for($j=0;$j<8;$j++){
    			$summ += imagecolorat($im, $i, $j);
    		}
    	}
    	$sred = $summ/64;
    	
    	//При втором проходе сравниваем значение цвета каждой точки со средним значением и записываем в результат 0 или 1
    	$str='';
    	for($i=0;$i<8;$i++){
    		for($j=0;$j<8;$j++){
    			if(imagecolorat($im, $i, $j)>=$sred){ $str .= '1'; }else{ $str .= '0'; }
    		}
    	}
    	
    	//Переводим в 16-ю систему, для удобства
    	$str = base_convert($str, 2, 16);
    	return $str;
    }
    
    echo '_test1.jpg '.getPerceptHash("E:\Denwer3\home\imagecomparer.loc\www\Article\img\_test1.jpg").'<br>';
    echo '_test2.jpg '.getPerceptHash("E:\Denwer3\home\imagecomparer.loc\www\Article\img\_test2.jpg").'<br>';
    echo '_test3.jpg '.getPerceptHash("E:\Denwer3\home\imagecomparer.loc\www\Article\img\_test3.jpg").'<br>';
    ?>
    


    Получаем результат:
    _test1.jpg f9f6f0f0e0b0f000
    _test2.jpg fbf6f0f0c0b0f000
    _test3.jpg 1e1e3e3e3e3e3c00
    


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

    3. Попытка применения на практике


    Метод сравнения найден, проверен, на тестовых примерах он работал. Пора была проверить его в бою. Несколько дней ушло на написание различных парсеров каталогов/прайсов/сайтов поставщиков, и сам парсинг. Вся информация + хеши складывались в базу, а сами изображения на диск, для дальнейших экспериментов. Всего в базу было собрано порядка 3 млн. записей.
    В начале метод работал, но по мере роста базы, результаты становились хуже и хуже, пока не скатились просто в помойку. Появилась куча ложных срабатываний. Метод хорошо работал на изображениях, у которых просто был изменён размер, но если изображение цветокорректировалось, обрезалось, или ещё хуже на него накладывали watermark (что было очень и очень часто), то результат был плохим.

    4. pHash


    Было очевидно, что используемая хеш-функция нам не подходит, нужно что-то серьёзнее. Решено было использовать pHash, основанный на дискретно косинуснусном преобразовании

    Сам по себе алгоритм тяжёлый и попытки реализовать его на php ничем хорошим не закончились. Выходом было — сделать консольную утилиту на СИ, которая бы на входе получала бы путь к файлу, считала бы хеш и возвращала его. Была найдена библиотека http://www.phash.org/

    Затем быстро написан тестовый образец, использующий эту библиотеку:
    #include "stdafx.h"
    #include <iostream>
    #include <windows.h>
    
    using namespace std;
    
    #ifndef _WIN32
    typedef unsigned _uint64 ulong64;
    typedef signed _int64 long64;
    #else
    typedef unsigned long long ulong64;
    typedef signed long long long64;
    typedef unsigned char uint8_t;
    typedef unsigned int uint32_t;
    #endif
    
    typedef int (*ph_dct_imagehash)(const char* file,ulong64 &hash);
    
    int _tmain(int argc, TCHAR* argv[])
    {
    	if (argc > 1) {
    		char* filename = (char *)malloc( 255 );
    		wcstombs( filename, argv[1], 255 );
    
    		ph_dct_imagehash _ph_dct_imagehash;
    		HINSTANCE hInstLibrary = LoadLibrary(L"pHash.dll");
     
    	   if (hInstLibrary)
    	   {
    
    		  _ph_dct_imagehash = (ph_dct_imagehash)GetProcAddress(hInstLibrary, "ph_dct_imagehash");
    		  int err = 0;
    		  err = GetLastError();
    		  ulong64 myhash=0;
    		  _ph_dct_imagehash(filename, myhash);
    		  std::cout << myhash <<  std::endl;
    
    		  FreeLibrary(hInstLibrary);
    	   }
    	   else
    	   {
    		  return 0;
    	   }
    	}else{
    		return 0;
    	}
       return 0;
    }
    


    Компилируем, на выходе получаем — pHashConcole.exe

    Из php эта конструкция вызывается через обычный exex:
    $pHash=exec('E:\Article\pHashConsole.exe "'.$filename.'"');
    


    Хеши были сложены в таблицу MySQL, а результат поиска можно получить очень простым запросом:
    'SELECT * FROM (SELECT * , BIT_COUNT( hash ^ '.$pHash.') AS distance FROM images ORDER BY distance LIMIT 0 , 100) s1 WHERE distance < '.$precision.';'
    

    Где, $pHash - хеш которому ищем похожие.
    $precision - точность, чем больше, тем больше результатов будет, но тем отдалённее от оригинала они будут. Подбирается эмпирически.
    


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

    5. The End!


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

    Вот такая забавная история…

    Всем огромное спасибо за внимание! The End!

    Similar posts

    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 32

      –3
      Я конечно не вижу всей картины в целом, но похоже лупят из пушек по воробьям…
        +1
        Задача решена, автору плюсы повсюду, но правильнее иметь одну точку заведения товаров в базу и строго карать если не так.
        Я за вертикаль власти. Должен быть один начальник у всех этих княжеств, а иначе такая свистопляска с наименованиями будет продолжаться. Рублём только можно супер-босса убедить, на сравнении «до» и «после», хотя чаще и к сожалению, нет полёта фантазии и планов — «и так же работает, чо нормально, мне хватает...»

        Автор — скажите, как быстро работает ваш алгоритм поиска похожего изображения по одному образцу на ваших 3млн.?
          +1
          но правильнее иметь одну точку заведения товаров в базу и строго карать если не так.

          Как я понимаю, софт написан как раз для такой точки, где заводятся в базу товары из разных источников.
            +1
            Это сложно именно софтом назвать, скорее такая сборка «наколенная».
            +2
            Вы не представляете насколько я с вами согласен!
            Для мня вообще, криво заполненные базы — это одна из постоянных проблем, с которыми приходится сталкиваться. Но увы, обычно базы начинают заполнятся криво с самого начала и спустя X лет очень сложно исправить положение. В такой ситуации обычно необходимо тотально перебирать базу, но под это как правило нет человекочасов. Куда лучше было бы заполнять всё правильно сразу, но увы…

            По поводу скорости — точных цифр сейчас не назову, т.к. дело было год назад и разумеется всего не сохранилось, там вся работа по поиску перекладывается на плечи MySQL, и во многом зависит уже от настроек самой MySQL. Результаты был в пределах секунды, но это явно не верх совершенства.
              0
              Секунда — это очень неплохо, спасибо за ответ.
                0
                В данном случае секунда это неплохо.
                Но проверил на своей базе с 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 секунд.
                Но и это как-то сильно туго. Поэтому дальше идет уже тяжелая артиллерия. Но это уже совсем другая история.
            +2
            Так и есть! Но этого никто и не скрывал. Прочитайте вступление, пожалуйста. Именно из пушки, именно по воробьям, и притом ещё на рукотворном велосипеде с квадратными колёсами… было просто интересно попробовать.
            0
            Ой, ну пожалуйста, ну используете 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 этих типов нет…
              +4
              А есть идеи, когда ситуация точь такая же, только даже картинок нет?
                +3
                Кластеризация. И, главное, интерфейсы и процессы, позволяющие легко распутать ошибки первого (ложное отнесение сущности к кластеру) и второго (ложное неотнесение) рода без необходимости откатывать транзакции (скажем, перепечатывать и заменять накладные на всех точках).
                +2
                Однажды решал аналогичную задачу, только без картинок. Данные были в БД Oracle. Написал небольшой скрипт, который разбивает каждое название на части по словам («Ваза с рисунком 'узор треугольный'» -> «ваза», «с», «рисунком», «узор», «треугольный»), далее сравнивает отдельные части-слова. Вычисляет коэффициент совпадения по принципу, чем больше составляющих совпало, тем лучше. В результате каждому элементу из списка 1 сопоставлялось несколько наиболее подходящих элементов из списка 2. Финальное сопоставление делалось вручную, к сожалению:(

                В моем случае я мог рассчитывать, что один и тот же предмет в разных списках назван одними и теми же словами. Это, конечно, не всегда сработает. На примере из статьи:
                1 «Ваза с рисунком 'узор треугольный'»,
                2 «Ваза А-563»,
                3 «Ваза с рисунком»,
                4 просто «Ваза»

                Мой алгоритм позволит сопоставить 1 и 3, а вот с пунктами 2 и 4 — без картинки не обойтись. Хотя зависит от того, на сколько широк ассортимент «ваз».
                  0
                  Да, тоже интересный подход. Спасибо за совет!
                    0
                    Я у себя еще сверху юзал Левенштейна, а если пыха, то similar_text. А потом уже на ручное сопоставление.
                      0
                      Пару месяцев в 2005 работал на проекте по поддержке бэкенда одного швейцарского сайта, агрегирующего данные по отелям из нескольких систем про резервированию мест в отелях, там тоже была похожая система, вроде с некоторыми элементами «самообучения». Из 250000 отелей после их матчера 15-20 тысяч приходилось «доматчивать» вручную. Это я к оценке релеватности подобных методик…
                        0
                        А куда деваться? Тут два варианта: либо отбрасывать нераспознанную часть (что было допустимо в нашем случае), либо доделывать руками (что необходимо в приведенном вами примере).
                        0
                        Похожий на метод шинглов описанный здесь PHP (rar)
                      +1
                      А мне понравилось! Хорошее решение смело звучащей задачи. Встречал очень мудрёные решения подобных задач, без использования хешей. Тут же всё просто
                        +1
                        Типовая задача дедуб(п)ликации неструктурированных каталогов.
                        На объеме в 10Кзаписей еще применим такой или подобный подход, а дальше (от 100к уникальных записей) задачи Data Quality и MDM систем.

                        Задачу поддержки решения смотрели?
                        Замена картинки поставщиком? записи разъедутся обратно или как то будет поддерживаться связка «Ваза с рисунком 'узор треугольный'» =«Ваза А-563»?
                        Точность объединения?
                        Возможности ошибочных объединений? когда «Пила двуручная Дружба = Забор из досок обрезный
                        Записи формируются динамически по новым прайсам или статикой?
                          0
                          Замена картинки поставщиком?
                          Думаю, первым возражением будет «лень»…
                          +1
                          Месье знает толк в программировании.)
                            0
                            Так в итоге pHash оказался намного лучше обычного хэша? Ложные срабатывания пропали совсем?
                              0
                              pHash лучшая open source библиотека для этих целей. Многие сервисы сравнения изображений построены именно на нем. Очевидно, что pHash оказался лучше :)
                                0
                                Да, вы правы, библиотека действительно отличная. Огромное спасибо авторам!
                                0
                                Да, pHash дал результат на порядки лучше, чем хеш «по среднему». Удалось детектить даже изображения у которых прямо через всю картинку красовалась надпись-watermark.
                                +3
                                Интересно, сколько денег удалось сэкономить?
                                  0
                                  Да, было бы интересно взглянуть на практический выхлоп, хотя бы в процентном отношении. Ну и примеры, ala «покупали раньше ту самую вазу за 1200рэ, а сейчас за 300».
                                  +1
                                  на всякий случай pHash имеет сгенереный php Extension
                                  github.com/sdepold/pHash/tree/master/bindings/php
                                    0
                                    Отличное решение практического вопроса и отличная статья. Я бы добавил в статью еще ссылку на расширение для пхп, ссылка на него есть в комментариях.

                                    Интересно, какие алгоритмы для сравнения изображений используют крупные поисковые системы.

                                    Only users with full accounts can post comments. Log in, please.