Еще одна версия алгоритма сравнения изображений

    Эта статья с месяц висела у меня в черновиках, пока кто-то мне наконец не привел карму к тонусу. Не знаю кто, но спасибо тебе

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

    Возможно такой метод уже существует давно и кем-то давно описан, ну, в таком случае, у меня по крайней мере есть готовый код.

    Алгоритм заключается в том, что нам нужно записать в массив разницу между каждыми i-м и (i + 1)-м пикселем. Таким образом этот массив и есть хэш для нашего изображения (при необходимости можно привести его в строковый вид). То есть, основываясь на этом, мы полагаем, что наше изображение — это не набор пикселей определенного цвета, а скорее совокупность разностей между этими пикселями.

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

    Теперь разберем этот алгоритм на коде.
    Я написал простенький класс, который может сравнивать любое количество изображений, отдавая разность между каждым из них.
    Вот сам класс, если хотите, можете на нем и остановится, или Вы можете почитать дальше что тут и к чему.
    
    class ImagesComparer
    {
        
        const
            BAD_ARGS = 1,
            UNSUPPORTED_FILETYPE = 2,
            ERROR_OPEN = 3;
        
        public $Images = array();
        
        private
            $_types = array('', 'gif', 'jpeg', 'png', '', '', 'wbmp', '', '', '', '', '');
        
        public $CompareWithFirst = false;
        
        public function __construct($Image1, $Image2 = null)
        {
            if (func_num_args() > 2)
                $Images = func_get_args();
            else if (is_array($Image1))
                $Images = $Image1;
            else
                $Images = array($Image1, $Image2);
            
            foreach ($Images as $Image)
            {
                if (is_string($Image))
                    $this->_openImage($Image);
                else if (is_resource($Image))
                    $this->Images[] = array($this->_getPixelsDiff($Image), array());
                else
                    throw new Exception('Bad arguments.', self::BAD_ARGS);
            }
        }
    
        private function _getImageType($Image)
        {
            $Type = getimagesize($Image);
            if (!$Type = $this->_types[$Type[2]])
                throw new Exception('Image have an unsupported file type.', self::UNSUPPORTED_FILETYPE);
            
            return 'imagecreatefrom' . $Type;
        }
    
        private function _openImage($Image)
        {
            $Type = $this->_getImageType($Image);
            $Image = $Type($Image);
            if (!$Image)
                throw new Exception('Error opening image.', self::ERROR_OPEN);
            
            $this->Images[] = array($this->_getPixelsDiff($Image), array());
            imagedestroy($Image);
        }
        
        private function _getPixelsDiff($Image)
        {
            $Sample = imagecreatetruecolor(8, 8);
            imagecopyresampled($Sample, $Image, 0, 0, 0, 0, 8, 8, imagesx($Image), imagesy($Image));
            
            $Pixels = array();
            $Color = array(0, 0, 0);
            for ($y = 0; $y < 8; $y++)
            {
                for ($x = 0; $x < 8; $x++)
                {
                    $Color1 = imagecolorat($Sample, $x, $y);
                    $Color1 = $this->_scale255To9(array(
                        ($Color1 >> 16) & 0xFF,
                        ($Color1 >> 8) & 0xFF,
                        $Color & 0xFF
                    ));
                    
                    if ($x != 0 || $y != 0)
                    {
                        $Pixels[] = array(
                            $Color1[0] - $Color[0],
                            $Color1[1] - $Color[1],
                            $Color1[2] - $Color[2]
                        );
                    }
                    
                    $Color = $Color1;
                }
            }
            imagedestroy($Sample);
            
            return $Pixels;
        }
        
        private function _scale255To9($NumArr)
        {
            return array(
                round($NumArr[0] / 28.3),
                round($NumArr[1] / 28.3),
                round($NumArr[2] / 28.3)
            );
        }
        
        private function _getDiff($Img1, $Img2)
        {
            $Diff = 0;
            for ($i = 0; $i < 63; $i++)
            {
                $Diff += abs($this->Images[$Img1][0][$i][0] - $this->Images[$Img2][0][$i][0]);
                $Diff += abs($this->Images[$Img1][0][$i][1] - $this->Images[$Img2][0][$i][1]);
                $Diff += abs($this->Images[$Img1][0][$i][2] - $this->Images[$Img2][0][$i][2]);
            }
            
            return $Diff;
        }
        
        public function Compare()
        {
            $count = count($this->Images);
            
            if ($this->CompareWithFirst)
            {
                for ($i = 1; $i < $count; $i++)
                {
                    $this->Images[0][1][$i] = $this->_getDiff(0, $i);
                }
            }
            else
            {
                for ($i = 0; $i < $count; $i++)
                {
                    for ($k = $i + 1; $k < $count; $k++)
                    {
                        //echo "\r\n<br />" .
                        $this->Images[$k][1][$i] =
                            $this->Images[$i][1][$k] = $this->_getDiff($i, $k);
                    }
                }
            }
        }
        
    }


    В конструкторе на каждое изображение вызывается метод _getPixelsDiff(), и его результат кладется в массив Images. Этот метод производит такие манипуляции:
    1. Уменьшает изображение до размеров 8x8.
    2. Создает массив для цветов.
    3. Проходится по каждому пикселю изображения:
      1. Берет его цвет в RGB.
      2. Каждый канал делит на 28.3 и округляет, чтобы максимальное значение канала было равно 9-ти.
      3. Вычитает из каждого канала значение предыдущего пикселя.
      4. Результат кладется в массив и возвращается.
    Ну, далее в Compare() вызывается метод _getDiff(), который находит разницу между массивами.
    Кстати, исходя из этого кода, самая большая разность у изображений может составлять 1701 (63 * 3 * 9, поправьте если это не так).

    А теперь тесты.

    Первая пара картинок: раз и два. Первая картинка — логотип Air Jordan. Вторая — пародия на первую в исполнении Бендера. Согласитесь, на глаз довольно похожие картинки. И наша программа выдает на них 68 баллов разности из 1701. То есть вероятность их идентичности примерно 96.1%.

    Вторая пара картинок: раз и два. Выдает разность, равную 266, хотя цветовая гамма у них довольно похожая. Кстати, получается, что эти рисунки с вероятностью 85% идентичны. Так что планку (извините, порог) надо ставить довольно высокую.

    Вот еще пара: раз и два. Разность 52.

    В общем я не считаю, что этот метод идеален, но, по крайней мере, думаю он имеет право на жизнь.

    UPD. Сравнение этого изображения и этого. Контрастность второго была сильно изменена как видим. Разность — 70 попугаев из 1701.
    Share post

    Similar posts

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

    More
    Ads

    Comments 23

      +1
      А какие результаты выдаются для одинаковых изображений разной контрастности?
        +2
        Написал в конце
        +2
        А почему бы не вынести примеры прямо в топик? Нагляднее было бы, если их рядом поместить
          0
          Чтобы не шло много трафика, а миниатюры сейчас не могу сделать, хабрасторейдж глючит.
          0
          Грубовато, но я думаю найти применение можно. Только тут, мне кажется, нужно очень четко представлять какими методами должна уменьшаться картинка.
          Согласитесь, что выкидывание 9 из 10 рядов для уменьшения или взятие среднего арифметического(в простейшем случае) для 10 рядов для уменьшения в 10 раз будут совершенно по разному влиять на результат. В первом случае пиксель будет нести информацию только о себе и получается тестовая выборка очень маленького размера. Во втором пиксель будет нести информацию обо всех уничтоженных. А способов уменьшения можно много придумать.
            –4
            Отправляйте в Google inc.)
              +1
              Текст особо не мешает

              А вы попробуйте его перенести вниз(на полосу шириной 1/8) и чтоб он от этой полосы отъедал ~60%. Что-то мне подсказывает, что мешать он будет сильно.
                0
                «чтобы он кушал изображения, у которых сильно различается, например, яркость „

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

                Как на счёт примера одинаковых изображений одно из которых сильно просветлено или затемено.
                  0
                  Тоже самое делал с этой собакой, второму изображению сильно увеличивал яркость, разность была около 120. Извините, не выложу изображение
                  0
                  Замечание по коду. Это не очень красиво и чрезмерно запутанно выглядит:
                  for ($i = 0; $i < $count; $i++)
                  {
                  for ($k = $i + 1; $k < $count; $k++)
                  {
                  //echo "\r\n
                  " .
                  $this->Images[$k][1][$i] =
                  $this->Images[$i][1][$k] = $this->_getDiff($i, $k);
                  }
                  }
                    0
                    А как еще можно пройтись по элементам выше главной диагонали?
                      +1
                      Мои замечания касаются удобночитаемости кода и рефаторинга. Поэтому немного оффтоп.
                      Дело субъективное. Я руководсовался книгой Макконелла делая следующие замечания.

                      применять в многомерных массивах для обозанчения коэффициетов переменных $i $j $k — которые не несут смысловой нагрузки на мой взгляд ухудшает читаемость кода и легко запутаться что есть $i и что есть $k,

                      в инициализации цикла встречается $k = $i + 1; — о смысле единицы тут можно догодаться, а вот тут Images[$i][1][$k] — чтоб догадаться что это за единица сразу можно и не разобрать.

                      кусок кода
                      $this->Images[$k][1][$i] =
                      $this->Images[$i][1][$k] = $this->_getDiff($i, $k);

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

                        >применять в многомерных массивах для обозанчения коэффициетов переменных $i $j $k
                        <offtop>Ненавижу называть переменные $j, т.к. постоянно путаю с $i</offtop>
                        Но вот как придать смысл этим переменным, если это просто счетчики и смысла в нет, я не знаю
                      +1
                      Код уникален тем, что практически не одна из переменных не названа удобоварима и без анализа кода не понятно ее значение.
                      Например, если мне нужно понять что такое $count, я должен найти в начале строчку:
                      $count = count($this->Images);
                      А можно было бы по другому: $images_count = count($this->Images);

                      За $i, $j, и $k нужно, увы, рвать яйца даже не кодерам, а авторам большинства учебников, которые в свою очередь свистнули эти индексы из математики, которой глубоко посрать на какие то конкретные привязки переменных.

                      Вот у меня на экране код метода:

                      for ($i = 0; $i < $count; $i++)
                      {
                      for ($k = $i + 1; $k < $count; $k++)
                      {
                      //echo "\r\n
                      " .
                      $this->Images[$k][1][$i] =
                      $this->Images[$i][1][$k] = $this->_getDiff($i, $k);
                      }
                      }



                      Кто ни будь, не роясь в остальном коде, может сказать, что такое $i, что такое $k, чему соответствует $this->Images[$k][1][$i], и количеством чего является $count?

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

                      Сорри, за все это занудство, просто, пардон, все эти «глупые мелочи», как раз то, что превращает работу программиста (и его колег) из интеллектуальной поэзии в ад, и наоборот.

                      Про общие вещи — описание алгоритма содержит чуть ли не больше информации как он закодирован в итоге, нежели о том, как это работает, откуда взялись подобные коэффициенты и размерности, почему именно 9 (породив тем самым кучу дорогих операций с плавающей точкой), а не 8 или тогда уж 42. Почему именно 63, а не 64? Многое из этого не понять ни с первого ни со второго захода.

                      Зачем уменьшать именно до 8х8, а при 4х4 сильно хуже сравнивает, а при 16х16 сильно медленнее? А если делать шашечками через один сегмент? А насколько при этом точнее? А может хватило бы 4-х цветов?
                      Когда люди тестируют алгоритмы, они в первую очередь после их создания пытаются ответить именно на эти вопросы, что отражено в любой публикации на схожие темы. Иначе просто непонятно, имеет ли их разработка право на жизнь, это прорыв (допустим в быстрых алгоритмах сопоставления) или наоборот, тормоз-франкельштейн? Без апробации и тестирования это просто неизвестно. И она составляет вторую половину работы — создать методику тестирования или применить чужую, набрать тестовый материал, или разные группы для него.

                      Писать алгоритм на PHP тоже не учень удобно, единственное оправдание — язык хорошо знаком. А так есть Matlab с целым ворохом инструментов для подобной работы, есть языки для быстрого прототипирования, где получится в три раза меньше строк и можно сосредоточиться на непосредственно логике.
                      +1
                      после феерического
                      for ($i = 0; $i < 63; $i++)
                      {
                      	$Diff += abs($this->Images[$Img1][0][$i][0] - $this->Images[$Img2][0][$i][0]);
                      	$Diff += abs($this->Images[$Img1][0][$i][1] - $this->Images[$Img2][0][$i][1]);
                      	$Diff += abs($this->Images[$Img1][0][$i][2] - $this->Images[$Img2][0][$i][2]);
                      }

                      остальное не читал

                      неужто так сложно реализовать один из более годных методов?
                      Image Quality Assessment: From Error Visibility to Structural Similarity
                      и вообще погуглить на тему, включив мозг
                        –2
                        рад за тебя
                          0
                          Вообще обзор по методикам создания fingerprint-ов изображений был бы полезен.

                          То, что предлагает автор достаточно известная штука с известными недостатками. Куда интереснее методики поиска частичных совпадений в вейвлет представлениях или анализирующие пропорции расстояний между различными артефактами на изображениях (крайне упрощенно — находим 10 углов или прочих характерных перепадов градиента, записываем расстояния между центрами зон присутствия таких артефактов, потом сравниваем по такому отпечатку), особенно часто такие штуки встречаются в системах распознавания лиц.

                          Более конкретные методики уже касаются непосредственно детекторов этих уникальных особенностей изображений, например «потомки» Viola-jones много где используются.

                          Пока самое чахлое из направлений в прикладном плане — это нейросетки, но оно же и самое перспективное, так как потенциально обещает резкий переход количества в качество по мере роста аппаратных мощностей.
                            0
                            Fingerprint'ов с какой целью? Если сравнения 1-к-1, то они как таковые не особенно и нужны, лишь бы алгоритм мог выдать на выходе степень схожести, если с целью последующего поиска одного из множества — это уже CBIR, и там свои особенности в зависимости от метода.

                            анализирующие пропорции расстояний между различными артефактами на изображениях

                            Мне кажется это черезчур сложно для такой, в общем-то, несложной задачи. Если задумываться о производительности, то, наверное, всё печально совсем будет.
                              0
                              Для 1:1 изложенного выше алгоритма хватит за глаза, тут уже давно узким местом стала скорость чтения изображения с диска или из памяти :)

                              > Мне кажется это черезчур сложно для такой, в общем-то, несложной задачи. Если задумываться о производительности, то, наверное, всё печально совсем будет.

                              Если говорить о готовых решениях на щщах, то подобные штуки с различными анализаторами уже лет 10 как работают с realtime видеопотоком в куче систем слежения, видеонаблюдения и т.д.

                              Даже нейросетки, и те подтянулись к этому пределу.
                              А задачи вариативного выделения и классификации объектов, они посложнее, чем сравнение изображений будут, хотя «идеальные» в плане точности алгоритмы сравнения, наверное, должны подразумевать и это.
                                0
                                Подскажете какие-то реально существующие системы поиска в видеоколлекции по кадру?
                                  0
                                  Вряд ли кто-то ставил перед собой такую задачу :)
                                    0
                                    ну это я порядке оффтопика уже спросил о вашем возможном личном опыте…
                                      0
                                      Если делать, то скорее всего индексация видео целиком, даже через 5 кадров — это полный ад в плане количества изображений в базе. Наверное, разумно экстрагировать отдельные планы, и потрошить по паре кадров из них на фурье-спектр и потом искать уже по совпадениям с ними, для точности можно доиндексировать подходящие планы на лету уже по более часто идущим ключевым кадрам.

                                      В основу можно положить что-то вроде такого:
                                      research.microsoft.com/pubs/68785/video_scene_extraction_grouping.pdf

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

                                      Но можно придумать и что-то попроще, методика описанная топикстартером с сегментацией вполне подойдет.

                                      Ау, MS, я хочу такую хрень в локальном поиске! :)

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