В этой статье хочу поделиться интересной историей, о необычном решении одной интересной задачи, которая попалась мне год назад. Всё описанное в статье делалось, прежде всего, «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:ImageMagickconvert.exe E:Articleimgtest1.jpg -resize 16x16! -colorspace gray E:Articleimg_test1.jpg
E:ImageMagickconvert.exe E:Articleimgtest2.jpg -resize 16x16! -colorspace gray E:Articleimg_test2.jpg
E:ImageMagickconvert.exe E:Articleimgtest3.jpg -resize 16x16! -colorspace gray E:Articleimg_test3.jpg
Получаем:
Далее считаем сам хеш:
<?
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:Denwer3homeimagecomparer.locwwwArticleimg_test1.jpg").'<br>';
echo '_test2.jpg '.getPerceptHash("E:Denwer3homeimagecomparer.locwwwArticleimg_test2.jpg").'<br>';
echo '_test3.jpg '.getPerceptHash("E:Denwer3homeimagecomparer.locwwwArticleimg_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:ArticlepHashConsole.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!
Автор: galichmark
