Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 64
Круто!
не полностью вникал в вычисление ключа, но при проверке схожести у вас проверяется сколько значений из первого ключа входят во второй, но не наоборот.
Для примера:
[1 1]&[0 1]=1
[0 1]&[1 1]=0.5
Как вариант могу предложить использовать функцию array_intersect
Для примера:
[1 1]&[0 1]=1
[0 1]&[1 1]=0.5
Как вариант могу предложить использовать функцию array_intersect
причём применять функцию дважды с разным порядком элементов. а результат уже брать либо как среднее, либо как минимальное, это уже нужно на конкретных примерах выбирать.
Объясните подробнее, а то не понял, какая разница что с чем сравнивать.
алгоритм интересен, но вот реализация хромает, имхо.
использование @ неоправдано, можно было обойтись такой инициализацией:
$average=array('red' => 0, 'blue' => 0, 'green' => 0);
не нравится изменения типов переменных: то average у вас массив, то уже число.
алгоритм можно упростить до такого:
использование @ неоправдано, можно было обойтись такой инициализацией:
$average=array('red' => 0, 'blue' => 0, 'green' => 0);
не нравится изменения типов переменных: то average у вас массив, то уже число.
алгоритм можно упростить до такого:
//Заполняем маску и вычисляем базовый цвет
for($x=0;$x<20;$x++)
for($y=0;$y<20;$y++)
{
$color=imagecolorat($zone,$x,$y);
$color=imagecolorsforindex($zone,$color);
//Вычисление яркости было подсказано хабраюзером Ryotsuke
$colormap[$x][$y]= 0.212671 * $color['red'] + 0.715160 * $color['green'] + 0.072169 * $color['blue'];
$average += $colormap[$x][$y];
}
//Базовый цвет
$average /= 400;
В первом примере нет ничего удивительного. Сжимая изображение, вы получаете цветовое пятно. Вычисление «среднего цвета» напрямую зависит от того, какие цвета преобладают на картинке. Так как первое изображение без полутонов (я насчитал 7 цветов), то и вероятность, что уменьшение размера даст очень похожее цветовое пятно весьма высока.
В качестве примера предлагаю сжать два первых изображения, а потом отойти от монитора на большое расстояние (близоруким можно и не отходить) — изображения практически сольются.
Думаю, что автор мог бы значительно улучшить эффективность алгоритма, если бы не уменьшал изображение, а делил бы его на сетку и считал бы средние цвета для ячеек, а потом сравнивал бы. Можно также добавить туда приоритеты. Чтобы разделять, что схожесть в центре изображения важнее, чем по краям (хорошо для фотографий)
В качестве примера предлагаю сжать два первых изображения, а потом отойти от монитора на большое расстояние (близоруким можно и не отходить) — изображения практически сольются.
Думаю, что автор мог бы значительно улучшить эффективность алгоритма, если бы не уменьшал изображение, а делил бы его на сетку и считал бы средние цвета для ячеек, а потом сравнивал бы. Можно также добавить туда приоритеты. Чтобы разделять, что схожесть в центре изображения важнее, чем по краям (хорошо для фотографий)
Дело в том, что данное решение скорее расчитано на быстрое сравнение двух изображений — т.е. заказчик хотел получать изображения похожие на загружаемое — сами понимаете, что уже при 1000+ картинок результат будет не впечатляющим, а посмотреть лишние два-три изображения совсем не проблема.
Думаю если найдется специфическая задача — можно будет и модернизировать.
Думаю если найдется специфическая задача — можно будет и модернизировать.
Я предлагал в расчете на следующее применение: картинки загружаются пользователем. При загрузке вычисляется некий хэш, сохраняется в базу. Затем можно выбирать из базы изображения похожие на заданное при помощи Stored Function из Mysql.
Если нужно сравнивать при загрузке с большим количеством, тогда да…
Если нужно сравнивать при загрузке с большим количеством, тогда да…
Я делаю точно так же, через некоторое время после загрузки крон вычисляет кеш, а затем уже ищет подобные.
В принципе мастабирование и выполняет роль «сетки», едиснтвенное отличие в том что я вычисляю не средний цвет, а среднюю яркость — это сделало возможным проверить пример номер 4.
P.S. Первоначально не понял замечания про разбиение, прошу прощения.
В принципе мастабирование и выполняет роль «сетки», едиснтвенное отличие в том что я вычисляю не средний цвет, а среднюю яркость — это сделало возможным проверить пример номер 4.
P.S. Первоначально не понял замечания про разбиение, прошу прощения.
В этом случае, наилучшим результатом (быстрое сравнение) было написание алгоритма обработки на C (с использованием той-же GD).
Варианта 2:
1) Запуск как демона. (сканирование на предмет новых изображений) И автоматическое сравнение.
2) Запуск как отдельное приложение из PHP.
Варианта 2:
1) Запуск как демона. (сканирование на предмет новых изображений) И автоматическое сравнение.
2) Запуск как отдельное приложение из PHP.
уменьшать изображение и находить средние цвета по регулярным ячейкам это по сути одно и то же, так что улучшения не будет
а чтобы увеличить вес центральной области — надо просто сжимать меньше а по краям брать для анализа не все пиксели
а чтобы увеличить вес центральной области — надо просто сжимать меньше а по краям брать для анализа не все пиксели
Просто, лаконично.
в избранное!
Наверное, похожий алгоритм работы у tineye.com
очень хорошая статья! взял на заметку!
но все же, кОрреляция!
но все же, кОрреляция!
в мемориз. авось пригодится=)))
foreach($image as $bit)
if(in_array($bit,$desc))
$result++;
Я может не совсем врубился, но вроде у Вас в строках лежат тройки [координата X, координата Y, производное яркости], т.е. тройки уникальны и лежат по порядку. Имхо достаточно писать в строки яркости через пробел и просто сравнивать их потом.
ИМХО для усовершенствования распознавания слегка модифицированных изображений, можно сигнатурить не так жестко (матрицей), а генерируя для изображения массив шинглов (по яркости, оттенку или контрастам, тут уж надо смотреть как эффективнее). По аналогии с алгоритмами нахождения плагиата в тексте. Таким образом можно быстро получать совпадения не только на целую картинку, но и частично повторяющую объект (например кроп или коллаж).
я бы попробовал вычислить несколько ступеней дискретного вейвлет преобразования простейшего ( /2 ), фактически линейная интерполяция между соседними пикселями на каждом шаге, и сравнивал поэтапно начиная с матриц 2x2 потом 4x4 потом 8x8 впринципе тут все уже зависит от того, какая точность требуется
для моего сервиса, я использую похожий алгоритм, правда только 3х3 точки, что вполне хватает, тем более что при большом количестве фоток, там сейчас около 200 тыс., скорость поиска дубликатов очень важна
Сразу подумалось о видео: снимаем среднюю яркость каждого кадра из оригинала, строим зависимость этого показателя во времени и кладем распределение в индекс поиска. Ищем копии, снимая с изучаемого объекта аналогичное распределение и сравнивая с индексом.
очепятка: карелляции -> корреляции
А дайте ссылки на полноразмерные картинки. Особенно на ту, что с эльфами :3 А вообще интересная тема — поиск похожих изображений.
Спасибо. Как раз искал правда на Delphi :), ну ничего переведу.
А если например на сайте проверять — лицензионное или пиратское видео загружает пользователь или есть такое видео на сайте или нет, то алгоритм почти не изменится:
1. Раскладываем все имеющиеся видео на кадры по каждому кадру строим ключ и пишем его в базу данных.
2. Из нового загружаемого видео — выдёргиваем несколько случайных кадров и строим их ключи.
3. Ключи из п.1 и п.2 проверяем по базе — есть ключ (видео имеется или пиратское(если изначальные ключи — лицензионного видео)), нет ключа — уникальное видео.
А если например на сайте проверять — лицензионное или пиратское видео загружает пользователь или есть такое видео на сайте или нет, то алгоритм почти не изменится:
1. Раскладываем все имеющиеся видео на кадры по каждому кадру строим ключ и пишем его в базу данных.
2. Из нового загружаемого видео — выдёргиваем несколько случайных кадров и строим их ключи.
3. Ключи из п.1 и п.2 проверяем по базе — есть ключ (видео имеется или пиратское(если изначальные ключи — лицензионного видео)), нет ключа — уникальное видео.
На 1-м курсе универа такое преподают
Написал класс из всего этого:
<?php
// ini_set('memory_limit', '256M');
class imagediff
{
private $image1;
private $image2;
function __construct($img1, $img2)
{
$this->image1['path'] = realpath($img1);
$this->image2['path'] = realpath($img2);
if($this->image1['path'] === false || $this->image2['path'] === false)
{
throw new Exception('Image "'.htmlspecialchars( $this->image1 ? $img2 : $img1 ).'" not found!');
}
else
{
$this->image1['type'] = $this->imagetyte($this->image1['path']);
$this->image2['type'] = $this->imagetyte($this->image2['path']);
}
}
private function imagetyte($imgname)
{
$file_info = pathinfo($imgname);
if(!empty ($file_info['extension']))
{
$filetype = strtolower($file_info['extension']);
$filetype = $filetype == 'jpg' ? 'jpeg' : $filetype;
$func = 'imagecreatefrom' . $filetype;
if(function_exists($func))
{
return $filetype;
}
else
{
throw new Exception('File type "'.htmlspecialchars( $filetype ).'" not supported!');
}
}
else
{
throw new Exception('File type not supported!');
}
}
private function imagehex($image)
{
$size = getimagesize($image['path']);
$func = 'imagecreatefrom'.$image['type'];
$imageres = $func($image['path']);
$zone = imagecreate(20, 20);
imagecopyresized($zone, $imageres, 0, 0, 0, 0, 20, 20, $size[0], $size[1]);
$colormap = array();
$average = 0;
$result = array();
for($x=0; $x<20; $x++)
{
for($y=0; $y<20; $y++)
{
$color = imagecolorat($zone, $x, $y);
$color = imagecolorsforindex($zone, $color);
$colormap[$x][$y]= 0.212671 * $color['red'] + 0.715160 * $color['green'] + 0.072169 * $color['blue'];
$average += $colormap[$x][$y];
}
}
$average /= 400;
for($x=0; $x<20; $x++)
{
for($y=0; $y<20; $y++)
{
$result[]=($x<10?$x:chr($x+97)) . ($y<10?$y:chr($y+97)) . round(2*$colormap[$x][$y]/$average);
}
}
return $result;
}
public function diff()
{
$hex1 = $this->imagehex($this->image1);
$hex2 = $this->imagehex($this->image2);
$result = 0;
foreach($hex1 as $bit)
{
if(in_array($bit, $hex2))
{
$result++;
}
}
return $result / ( ( count($hex1) + count($hex2) ) / 2 );
}
}
$diff = new imagediff('/opt/www/test/www/3.png', '/opt/www/test/www/3.jpeg');
print ($diff->diff() * 100 ).'%';
?>
у вас ошибка, как и у автора, в функции diff. Если поменять порядок изображений — изменится результат, а это не правильно. я писал об этом выше во втором комментарии.
у вас ошибка, как и у автора, в функции diff. Если поменять порядок изображений — изменится результат, а это не правильно. я писал об этом выше во втором комментарии.
round(2*$colormap[$x][$y]/$average); рекомендую сделать как в upd-2, сравнение получается более точное.
Спасибо!
Тут исправленная версия:
http://webiteam.ru/2009/03/sravnenie-izobrazhenij-s-pomoshhyu-php/
Тут исправленная версия:
http://webiteam.ru/2009/03/sravnenie-izobrazhenij-s-pomoshhyu-php/
Очень интересная реализация. Подойдет для фотохостинга — например говорить пользователю, что у него уже есть такая похожая фотография (но всё-таки разрешать загружать).
В букмарки!
В букмарки!
а как оптимальнее провести поиск схожих изображений средствами mysql к примеру?
А может перевести в LAB цвет, оставить только освещённость, и ксорить… :)
Меня, конечно, запинают… Но я осмелюсь спросить… А как с помощью SQL выбрать максимально схожие изображения основываясь на этом алгоритме?
Попробовал через MATCH(`hash`) AGAINST("$HASH") Ничего не выбрало… Точнее выбрало много но релевантность везде была равна нулю.
Спасибо, помогли.
Кстати, если в конце долгий in_array заменить на быстрый isset (для этого надо класть в ключи, а не в значения), то можно оптимизировать по быстродействию почти на порядок.
Кстати, если в конце долгий in_array заменить на быстрый isset (для этого надо класть в ключи, а не в значения), то можно оптимизировать по быстродействию почти на порядок.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Простое сравнение изображений с помощью php