Простое сравнение изображений с помощью php

    Алгоритм возможно не новый, и не является идеалом, но, на удивление, работает. Никаких графов и корелляции.

    Для начала, стоит отметить, что сравнение очень приблизительно (по крайней мере, на данном этапе), временами две совершенно разные фотографии оказываются похожими процентов на 60%, так же не учитываются жесткие модификации (повороты, инверсия, обрезка) – для этого нужно доводить и доводить. Лично для меня самым главным оказались два параметра: скорость, независимость от разрешения изображения и возможность сравнивать «изображения» прямо в базе данных.

    Принцип

    • Открываем исходное изображение
    • Масштабируем его до размера маски (в моем случае это 20 на 20, большие размеры мне ни к чему – сравнение приблизительное, вполне возможно сделать маску и 10 на 10).
    • Вычисляем основной цвет маски.
    • Создаем массив, где значением является ключ типа af2 (1,2 — координты, как в морском бою. 2 — расхождение с основной яркостью).
    • Генерируем строку – ключ.
    • Сравниваем две строки по релевантности.

    Код


    В данном случае представлена версия, работающая через GD c PNG изображениями.
    //Генерация ключа-изображения
    function getimageid($image)
    {
      //Размеры исходного изображения
      $size=getimagesize($image);

      //Исходное изображение
      $image=imagecreatefrompng($image);

      //Маска
      $zone=imagecreate(20,20);

      //Копируем изображение в маску
      imagecopyresized($zone,$image,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);

          //Вычисление яркости было подсказано хабраюзером Ryotsuke
          $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 join(' ',$result);
    }


    * This source code was highlighted with Source Code Highlighter.

    //Вычисление "похожести" двух изображений
    function imagediff($image,$desc)
    {
      $image=explode(' ',$image);
      $desc=explode(' ',$desc);

      $result=0;

      foreach($image as $bit)
        if(in_array($bit,$desc))
          $result++;

       return $result/((count($image)+count($desc))/2);
    }


    * This source code was highlighted with Source Code Highlighter.

    *функция подсчета схожести примерная — лучше данное действие выполнять на стороне базы.

    Примеры


    image
    На удивление, 95% 87% схожести (с добавлением UPD-2)

    image
    52% схожести

    image
    28% схожести

    image
    100% схожести

    Постскриптум


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

    P.S. Замечания и советы принимаются.
    UPD Спасибо MiniM — код упростился.
    UPD-2 Небольшое дополнение:
     //Генерируем ключ строку
      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)).($colormap[$x][$y]==0?'0':round(2*($colormap[$x][$y]>$average?$colormap[$x][$y]/$average:-1*$average/$colormap[$x][$y])));

    * This source code was highlighted with Source Code Highlighter.

    После этого будет учитываться уменьшение яркости в точке. Таким образом схожесть в первом примере составит 87%.
    UPD-3 Перенесено в php.
    Share post

    Similar posts

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

    More
    Ads

    Comments 64

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

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

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

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

              array_intersect — это функция php.
                0
                Я про imagediff.
                  –1
                  а как вы используете эти самы средства? Честно говоря, не совсем представляю как это можно сделать с помощью sql.
                    +1
                    Например FULLTEXT в MySQL, значения немного не такие, но вполне основательные.
                      0
                      С FULLTEXT не работал, поэтому ничем не могу помочь.
            0
            Объясните подробнее, а то не понял, какая разница что с чем сравнивать.
              0
              Разница в том, что если сравнивать image1 и image2, то получим один результат, а если сравнивать image2 и image1, то результат может оказаться другим.
            +4
            алгоритм интересен, но вот реализация хромает, имхо.
            использование @ неоправдано, можно было обойтись такой инициализацией:
            $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;
            
              +2
              Увы, писалось всё очень поздним вечером. За замечания спасибо, я подправлю с вашего разрешения.
                +6
                конечно, я не против — мы тут для того, что бы делиться решениями и опытом.
              +2
              В первом примере нет ничего удивительного. Сжимая изображение, вы получаете цветовое пятно. Вычисление «среднего цвета» напрямую зависит от того, какие цвета преобладают на картинке. Так как первое изображение без полутонов (я насчитал 7 цветов), то и вероятность, что уменьшение размера даст очень похожее цветовое пятно весьма высока.

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

              Думаю, что автор мог бы значительно улучшить эффективность алгоритма, если бы не уменьшал изображение, а делил бы его на сетку и считал бы средние цвета для ячеек, а потом сравнивал бы. Можно также добавить туда приоритеты. Чтобы разделять, что схожесть в центре изображения важнее, чем по краям (хорошо для фотографий)
                +2
                Дело в том, что данное решение скорее расчитано на быстрое сравнение двух изображений — т.е. заказчик хотел получать изображения похожие на загружаемое — сами понимаете, что уже при 1000+ картинок результат будет не впечатляющим, а посмотреть лишние два-три изображения совсем не проблема.
                Думаю если найдется специфическая задача — можно будет и модернизировать.
                  0
                  Я предлагал в расчете на следующее применение: картинки загружаются пользователем. При загрузке вычисляется некий хэш, сохраняется в базу. Затем можно выбирать из базы изображения похожие на заданное при помощи Stored Function из Mysql.
                  Если нужно сравнивать при загрузке с большим количеством, тогда да…
                    0
                    Я делаю точно так же, через некоторое время после загрузки крон вычисляет кеш, а затем уже ищет подобные.
                    В принципе мастабирование и выполняет роль «сетки», едиснтвенное отличие в том что я вычисляю не средний цвет, а среднюю яркость — это сделало возможным проверить пример номер 4.

                    P.S. Первоначально не понял замечания про разбиение, прошу прощения.
                    0
                    В этом случае, наилучшим результатом (быстрое сравнение) было написание алгоритма обработки на C (с использованием той-же GD).

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

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

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

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

                                                <?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 ).'%';

                                                ?>

                                                  0
                                                  у вас ошибка, как и у автора, в функции diff. Если поменять порядок изображений — изменится результат, а это не правильно. я писал об этом выше во втором комментарии.
                                                    0
                                                    Не меняется… проверял. Но все равно сменил на функцию array_intersect().
                                                      0
                                                      я не учёл, что в хэше используются координаты точки.
                                                      но тогда можно просто поэлементно сравнить массивы, а не использывать поиск каждого элемента в другом массиве.
                                                    0
                                                    у вас ошибка, как и у автора, в функции diff. Если поменять порядок изображений — изменится результат, а это не правильно. я писал об этом выше во втором комментарии.
                                                      0
                                                      round(2*$colormap[$x][$y]/$average); рекомендую сделать как в upd-2, сравнение получается более точное.
                                                        +1
                                                        Спасибо!
                                                        Тут исправленная версия:
                                                        http://webiteam.ru/2009/03/sravnenie-izobrazhenij-s-pomoshhyu-php/
                                                          –1
                                                          Да, я археолог, но мне кажется ссылочку лучше либо удалить, либо исправить на правильную. При переходе открывается совсем другая ссылка
                                                          image
                                                        +1
                                                        Очень интересная реализация. Подойдет для фотохостинга — например говорить пользователю, что у него уже есть такая похожая фотография (но всё-таки разрешать загружать).

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

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