Pull to refresh

Comments 64

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

Для примера:
[1 1]&[0 1]=1
[0 1]&[1 1]=0.5

Как вариант могу предложить использовать функцию array_intersect
причём применять функцию дважды с разным порядком элементов. а результат уже брать либо как среднее, либо как минимальное, это уже нужно на конкретных примерах выбирать.
Я набросал эту функцию только для примера, в основном использую средства MySQL для сравнения двух строк — гораздо быстрее и удобнее. )

P.S. Как это перенести в php?
Не понял вопроса.

array_intersect — это функция php.
а как вы используете эти самы средства? Честно говоря, не совсем представляю как это можно сделать с помощью sql.
Например FULLTEXT в MySQL, значения немного не такие, но вполне основательные.
С FULLTEXT не работал, поэтому ничем не могу помочь.
Объясните подробнее, а то не понял, какая разница что с чем сравнивать.
Разница в том, что если сравнивать image1 и image2, то получим один результат, а если сравнивать image2 и image1, то результат может оказаться другим.
алгоритм интересен, но вот реализация хромает, имхо.
использование @ неоправдано, можно было обойтись такой инициализацией:
$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. Первоначально не понял замечания про разбиение, прошу прощения.
В этом случае, наилучшим результатом (быстрое сравнение) было написание алгоритма обработки на C (с использованием той-же GD).

Варианта 2:
1) Запуск как демона. (сканирование на предмет новых изображений) И автоматическое сравнение.
2) Запуск как отдельное приложение из PHP.
уменьшать изображение и находить средние цвета по регулярным ячейкам это по сути одно и то же, так что улучшения не будет

а чтобы увеличить вес центральной области — надо просто сжимать меньше а по краям брать для анализа не все пиксели
Наверное, похожий алгоритм работы у tineye.com
очень хорошая статья! взял на заметку!
но все же, кОрреляция!
я вот тоже подумал, только пока не представляю для чего :)
foreach($image as $bit)
if(in_array($bit,$desc))
$result++;

Я может не совсем врубился, но вроде у Вас в строках лежат тройки [координата X, координата Y, производное яркости], т.е. тройки уникальны и лежат по порядку. Имхо достаточно писать в строки яркости через пробел и просто сравнивать их потом.
Проблематично будет использовать ресурсы базы, но в «чистом» php так будет быстрее.
ИМХО для усовершенствования распознавания слегка модифицированных изображений, можно сигнатурить не так жестко (матрицей), а генерируя для изображения массив шинглов (по яркости, оттенку или контрастам, тут уж надо смотреть как эффективнее). По аналогии с алгоритмами нахождения плагиата в тексте. Таким образом можно быстро получать совпадения не только на целую картинку, но и частично повторяющую объект (например кроп или коллаж).
я бы попробовал вычислить несколько ступеней дискретного вейвлет преобразования простейшего ( /2 ), фактически линейная интерполяция между соседними пикселями на каждом шаге, и сравнивал поэтапно начиная с матриц 2x2 потом 4x4 потом 8x8 впринципе тут все уже зависит от того, какая точность требуется
для моего сервиса, я использую похожий алгоритм, правда только 3х3 точки, что вполне хватает, тем более что при большом количестве фоток, там сейчас около 200 тыс., скорость поиска дубликатов очень важна
а как вы ищете дубликаты?
При 3*3 можно просто искать совпадения.
В посте реализовано 20*20… тут точность выше но работать с результатом сложнее.
studentpm, честно говоря с 20 на 20 я переборщил, 10x10 должно хватить выше крыши.
Сразу подумалось о видео: снимаем среднюю яркость каждого кадра из оригинала, строим зависимость этого показателя во времени и кладем распределение в индекс поиска. Ищем копии, снимая с изучаемого объекта аналогичное распределение и сравнивая с индексом.
очепятка: карелляции -> корреляции
А дайте ссылки на полноразмерные картинки. Особенно на ту, что с эльфами :3 А вообще интересная тема — поиск похожих изображений.
Спасибо. Как раз искал правда на Delphi :), ну ничего переведу.

А если например на сайте проверять — лицензионное или пиратское видео загружает пользователь или есть такое видео на сайте или нет, то алгоритм почти не изменится:
1. Раскладываем все имеющиеся видео на кадры по каждому кадру строим ключ и пишем его в базу данных.
2. Из нового загружаемого видео — выдёргиваем несколько случайных кадров и строим их ключи.
3. Ключи из п.1 и п.2 проверяем по базе — есть ключ (видео имеется или пиратское(если изначальные ключи — лицензионного видео)), нет ключа — уникальное видео.
Написал класс из всего этого:

<?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. Если поменять порядок изображений — изменится результат, а это не правильно. я писал об этом выше во втором комментарии.
Не меняется… проверял. Но все равно сменил на функцию array_intersect().
я не учёл, что в хэше используются координаты точки.
но тогда можно просто поэлементно сравнить массивы, а не использывать поиск каждого элемента в другом массиве.
у вас ошибка, как и у автора, в функции diff. Если поменять порядок изображений — изменится результат, а это не правильно. я писал об этом выше во втором комментарии.
round(2*$colormap[$x][$y]/$average); рекомендую сделать как в upd-2, сравнение получается более точное.
Да, я археолог, но мне кажется ссылочку лучше либо удалить, либо исправить на правильную. При переходе открывается совсем другая ссылка
image
Очень интересная реализация. Подойдет для фотохостинга — например говорить пользователю, что у него уже есть такая похожая фотография (но всё-таки разрешать загружать).

В букмарки!
Мне кажетяс кнопочка «найти похожие» тоже пригодится.
а как оптимальнее провести поиск схожих изображений средствами mysql к примеру?
т.е. когда ключи уже есть в базе
Думаю мускуль тут слабый помощник =\
Хотя если через лайк запрос выбрать поля хотя бы с 50% содержанием элементов ключа, а дальше уже средствами того же php уточнить результат… но это ни разу не оптимально =((
но и перебирать каждый раз все ключи не выход.
Еще можно попробовать псевдосемантикой. Т.е. разбить ключ на элементы и сравнивать и искать с наибольшим процентов вхождения.
Был как-то на хабре пост про организацию поиска аля яндекс. Там описано как сделать можно.
Понятно. Звучит как-то сильно тяжело (в плане нагрузки) для такой задачи…
А может перевести в LAB цвет, оставить только освещённость, и ксорить… :)
Меня, конечно, запинают… Но я осмелюсь спросить… А как с помощью SQL выбрать максимально схожие изображения основываясь на этом алгоритме?
Попробовал через MATCH(`hash`) AGAINST("$HASH") Ничего не выбрало… Точнее выбрало много но релевантность везде была равна нулю.
Для начала нужно уменьнишь минимальное слово для индексирования (по умолчанию стоит 4, а нужно 3). А дальше точно так же, я постараюсь в ближайшем времени представить кое-какие дополнения для работы в MySQL с этой фиговиной.
Следует вопрос… А как это сделать? В конфигах или можно прямо SQL запросом?
Я делал в конфигурации, наверняка можно временно установить запросом.
Спасибо, помогли.
Кстати, если в конце долгий in_array заменить на быстрый isset (для этого надо класть в ключи, а не в значения), то можно оптимизировать по быстродействию почти на порядок.
Only those users with full accounts are able to leave comments. Log in, please.