Главная
Блог разработчиков phpBB
 
+ 17 предустановленных модов
+ SEO-оптимизация форума
+ авторизация через соц. сети
+ защита от спама

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

Anna | 29.05.2014 | нет комментариев
В этой статье хочу поделиться увлекательной историей, о странном решении одной увлекательной задачи, которая попалась мне год назад. Всё описанное в статье делалось, раньше каждого, «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-х подрядчиков, а если номенклатура в сумме насчитывает десятки тысяч позиций, а подрядчиков десятки?
Казалось бы, в чём задача — задача элементарная, но требует много несложных вычислений, руками объём не подъёмный, значит её необходимо стремительно переложить на плечи ПК и пожинать плоды? Всё было бы так, если бы была одна цельная база со каждой номенклатурой и ценами. Но увы, это утопия… база была в обыкновенном, страшном состоянии помойки, в котором могли кое-как разобраться только те кто всякий день и сваливал эту кучу мусора. С ценами всё ещё дрянней, они вообще размазаны по различным каталогам, прайсам, сайтам. При попытке как-нибудь это каталогизировать и собрать вместе, становится видимо, что это весьма сложно без ручного вмешательства. Один подрядчик использует артикул изготовителя, иной ставит свой, а 3-й вообще не указывает их в прайсах. Наименования фактически нигде не совпадают, скажем один и тот же товар может именоваться: «Ваза с рисунком ‘узор треугольный’», «Ваза А-563», «Ваза с рисунком», наконец, легко «Ваза» :)
Значит, по наименованиям соединять было тоже безусловно напрасно.

2. Безрассудная идея

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

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

Для того Дабы сделать стремительно прототип было решено применять ImageMagick для обработки картинок, а в качестве скриптового языка был выбран php.
В качестве материала для тестов я взял изображение «Хризантема.jpg», из стандартного комплекта Windows. 1-й файл я назвал 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

Получаем:

Изображения 16×16 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

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

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!

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

Вот такая комичная история…

Каждому большое спасибо за внимание! The End!

 Источник: programmingmaster.ru
Оставить комментарий
Форум phpBB, русская поддержка форума phpBB
Рейтинг@Mail.ru 2008 - 2017 © BB3x.ru - русская поддержка форума phpBB