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

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

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

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

Алгоритм заключается в том, что нам нужно записать в массив разницу между каждыми 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.