Быстрое сравнение изображений на PHP через hash изображения |

Иногда возникает потребность определить, являются ли два файла изображений одинаковыми, или очень похожими (когда одно из них было сильнее сжато, сохранено в другом формате файла, или размер его был изменён).
Это может понадобиться в следующих случаях:

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

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

Долгие поиски в Интернете, не дали мне подходящего алгоритма, поэтому я создал свой.

Принцип действия

Хэш изображения — это строка, составляемая из байт, полученных из цветов упрощённого исходного изображения.

Вот как она генерируется:

Выбор параметров:

Для хэша нужно задать 2 параметра: размер и детализация.

Размер ($hashSizeRoot) — это сторона квадрата упрощённого изображения, или квадратный корень из длины хэша, скажем, если размер = 10, то длина хэша будет 100 байт. Размер может быть от 4 и до бесконечности, хотя слишком большим его делать не стоит.

Детализация ($hashDetalization) — это степень упрощения цветов изображения, равняется числу градаций каждого из каналов цвета, красного, синего и зелёного. Значение детализации может варьироваться так, чтобы цветность одного пиксела укладывалась в 1 байт. Таким образом, детализация может меняться от 2 до 6, где 2 — означает что у каждого байта будет всего 8 значений (2³), 6 — что значений будет 216 (6³).

Уменьшение изображения до квадратного «упрощённого»

Далее, исходное изображение с помощью функции библиотеки gd2 imagecopyresampled уменьшается до квадратного изображения со стороной $hashSizeRoot. Неважно, какие пропорции у исходного изображения, в результате всё равно получится квадрат.

Например, из такого вот изображения:
src

Получается вот такое:

dest

(увеличено в 15 раз для наглядности)

Упрощение информации о цветности

Необходимо снизить количество цветов так, чтобы каждый пиксел уменьшенного изображения укладывался в 1 байт.
Изначально заданным является параметр $hashDetalization, он, как это уже упоминалось, определяет максимальное количество значений на каждый цветовой канал.

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

$littleSize = $hashSizeRoot;
for($i=0;$i<$littleSize; $i++)
{
    for ($j=0;$j<$littleSize;$j++)
    {
        $color = imagecolorat($littleImg, $i, $j);
        $simpleColor = $colorSimplify($color);
        $hash .= chr($simpleColor);
    }
}

Как работает функция $colorSimplify:

//Цветов на один пиксел (число от 8 до 216)
$colorsPerPixel = pow($hashDetalization, 3);
//Цветов на один канал
$colorsPerChannel = $hashDetalization;
//Отрезок цветового канала, пропорциональный единице из упрощённого цветового канала
$channelDivision = 256 / $colorsPerChannel;
 
//Функция упрощающая цвет:
$colorSimplify = function($color) use($colorsPerPixel, $colorsPerChannel, $channelDivision) {
    //Разбиваем цвет на красный, синий и зелёный
    $r = ($color >> 16) & 0xFF;
    $g = ($color >> 8) & 0xFF;
    $b = $color & 0xFF;
    //Получаем упрощённые значения цветовых каналов
    $simpleR = floor($r / $channelDivision);
    $simpleG = floor($g / $channelDivision);
    $simpleB = floor($b / $channelDivision);
    //Упрощённый цвет
    $simpleColor = ($simpleR + $simpleG * $colorsPerChannel + $simpleB * $colorsPerChannel * $colorsPerChannel);
    //На всякий случай ограничиваем сверху
    if ($simpleColor >= $colorsPerPixel) $simpleColor = $colorsPerPixel - 1;
    //Возвращаем результат - байт упрощённого цвета
    return (int)$simpleColor;
};

Сохранение хэша

Полученная строка в переменной $hash — и есть готовый хэш, который можно использовать для сравнения изображений.

Сравнение хэша

Сравнивать хэши можно на точное равенство (то есть просто $hash1 == $hash2), а можно на приблизительное, которое несколько медленнее, но позволяет определять в качестве схожих более изменённые изображения.

При сравнивании на приблизительное равенство выбирается процент соответствия, различия менее которого считаются несущественными.

Приблизительное сравнение

Приблизительное сравнение выполняется только для хэшей одинаковой длины (то есть для тех, у которых одинаковы $hashSizeRoot).
При сравнении строки хэша при помощи функции unpack превращаются в массив целых чисел — значений байт, далее, эти байты разбиваются на составляющие — красную, синюю и зелёную. Эти составляющие и сравниваются, каждое различие добавляет некоторый процент ошибки. Если суммарный процент ошибки выше заданного, то проверка прекращается, и функция возвращает false.

/**
 * Сравнить два хэша изображений
 * @param string $hash1 хэш первого изображения в формате base64
 * @param string $hash2 хэш второго изображения в таком же формате
 * @param float $epsilon Максимальная относительная ошибка. 1 это 100%, 0.5 это 50% и так далее.
 * @param boolean $error Ссылка на переменную, в которую будет записана величина ошибки (число от 0 до 1)
 * @param boolean $alreadyDecoded Флаг, указывающий, что переданные хэши уже декодированы из base64
 * @return boolean возвращает true/false в зависимости от того, соответствуют ли друг другу хэши
 */
function compareImageHashes($hash1, $hash2, $epsilon = 0.01, &$error = 0, $alreadyDecoded = false)
{
    $error = 1;
    if ($epsilon == 0)
    {
        return $hash1 == $hash2;
    }
    else
    {
        if ($hash1 == $hash2) return true;
	if (!$alreadyDecoded)
	{
            $h1 = base64_decode($hash1);
            $h2 = base64_decode($hash2);
        }
	else
	{
            $h1 = $hash1;
            $h2 = $hash2;
	}
 
        if (strlen($h1) != strlen($h2)) return false;
 
	$l = strlen($h1);
	$error = 0;
	$bytes1 = unpack("C*", $h1);
	$bytes2 = unpack("C*", $h2);
 
	for ($i=0;$i<$l;$i++)
	{
            $b1 = $bytes1[$i+1];
            $b2 = $bytes2[$i+1];
            if ($b1 != $b2)
            {
                $delta = abs($b1 - $b2);
                $mid = ($b1 + $b2) / 2;
                if ($delta > 0)
                {
                    $e = $delta / $mid;
                    $error += $e / $l;
                    if ($error > $epsilon) return false;
                }
            }
        }
        return $error <= $epsilon;
    }
}

Где взять и как пользоваться

Класс для работы с хэшами изображений можно скачать в репозитории:
https://github.com/MihanEntalpo/php_helpers/tree/master/imagehash
(Когда-нибудь дойдут руки, я освою composer и сделаю нормальный пакет)

Вычислим хэш изображения, лежащего в файле:

<?php
require_once "ImageHash.php";
$ih = new ImageHash();
$hash = $ih->createHashFromFile("./test.jpg");

Вычислим хэш двух изображений и сравним их:

<?php
require_once "ImageHash.php";
$ih = new ImageHash();
$hash1 = $ih->createHashFromFile("./test1.jpg");
$hash2 = $ih->createHashFromFile("./test2.jpg");
$isEqual = ($hash1 == $hash2)
$isNearEqual = $ih->compareImageHashes($hash1, $hash2, 0.05);
echo "Хэши изображений равны?:" . ($isEqual ? "Да" : "Нет");
echo "Хэши изображений равны с точностью до 5%?:" . ($isNearEqual ? "Да" : "Нет");

Вычислим хэш изображения из объекта image, с большей детализацией

$ih = new ImageHash();
$image = imagefromjpeg("./file.jpeg");
$hash = $ih->createHash($image, 10, 6);

Ответить mihanentalpo | Ноябрь 27th, 2020

Предположим, что $colorsPerChannel = 4.
Тогда переменные $simpleR, $simpleG, $simpleB — могут принимать значения от 0 до 3.
Все цвета у нас укладываются в один байт, представленный в виде 8 бит.
Если все цвета = 0, тогда байт имеет вид 00000000
Если у нас ярко-красный, то $simpleR = 3, а байт выглядит так 00000011
Если у нас ярко-зеленый, то $simpleG = 3, и байт будет иметь вид 00001100
Для ярко-синего байт будет 00110000
Таком образом видно, что каждой из составляющих цветов находится в своей «части» байта и не мешает другим. Например, фиолетовый будет выглядеть так: 00110011, к голубой так: 00111000.
Добиваемся мы этого «сдвигом регистра», то есть умножением на размерность системы счисления, в данном случае это как раз $colorsPerChannel.
То есть красный должен стоять в начале байта — поэтому он не домножается ни на что. Зелёный должен стоять дальше красного в байте, не смешиваясь с ним, поэтому он домножается на величину, которая как раз на 1 больше максимального значения красного, а это и есть $colorsPerChannel. Аналогично для синего, который должен стоять третьим в байте, а потому домножается на основание системы счисления 2 раза.
Тоже самое происходит когда цвет храниться не в 1 байте а в 3х, каждая составляющая цвета хранится в одном байте не мешая другим составляющим, но в сумме из них должно получиться одно большое число, которое можно найти по формуле R + G * 256 + B * 256 * 256.
Если же попробовать сделать по предложенному тобой методу, то все цвета будут в одной куче где-то посередине нашего байта, и будет математически влиять друг на друга.
А например, ярко красный, ярко зелёный и ярко синий по твоему методу будут в байте записываться одинаково: 00001100
Очевидно что это не то что нам надо, всё-таки это три разных цвета.

9 комментариев

Ответить Дмитрий | Ноябрь 3rd, 2016

Огромное человеческое спасибо!
- Ответить mihanentalpo | Ноябрь 4th, 2016
  
  Огромное человеческое пожалуйста
Ответить Александр | Октябрь 22nd, 2020

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

Также нашёл ошибку, выше в примере указано:

$isNearEqual = $ih->compare($hash1, $hash2, 0.05);

В файле imagehash написана функция compareImageHashes:

$isNearEqual = $ih->compareImageHashes($hash1, $hash2, 0.10);
- Ответить mihanentalpo | Октябрь 22nd, 2020
  
  Спасибо за комментарий, действительно похоже на ошибку
Ответить Keker | Ноябрь 26th, 2020

Мне кажется, что в методе упрощения тоже есть ошибка.
В этой строчке:
$simpleColor = ($simpleR + $simpleG * $colorsPerChannel + $simpleB * $colorsPerChannel * $colorsPerChannel);
Разве не должно быть так:
$simpleColor = ($simpleR * $colorsPerChannel + $simpleG * $colorsPerChannel + $simpleB * $colorsPerChannel );
Ответить mihanentalpo | Ноябрь 27th, 2020

Предположим, что $colorsPerChannel = 4.
Тогда переменные $simpleR, $simpleG, $simpleB — могут принимать значения от 0 до 3.
Все цвета у нас укладываются в один байт, представленный в виде 8 бит.
Если все цвета = 0, тогда байт имеет вид 00000000
Если у нас ярко-красный, то $simpleR = 3, а байт выглядит так 00000011
Если у нас ярко-зеленый, то $simpleG = 3, и байт будет иметь вид 00001100
Для ярко-синего байт будет 00110000
Таком образом видно, что каждой из составляющих цветов находится в своей «части» байта и не мешает другим. Например, фиолетовый будет выглядеть так: 00110011, к голубой так: 00111000.
Добиваемся мы этого «сдвигом регистра», то есть умножением на размерность системы счисления, в данном случае это как раз $colorsPerChannel.
То есть красный должен стоять в начале байта — поэтому он не домножается ни на что. Зелёный должен стоять дальше красного в байте, не смешиваясь с ним, поэтому он домножается на величину, которая как раз на 1 больше максимального значения красного, а это и есть $colorsPerChannel. Аналогично для синего, который должен стоять третьим в байте, а потому домножается на основание системы счисления 2 раза.
Тоже самое происходит когда цвет храниться не в 1 байте а в 3х, каждая составляющая цвета хранится в одном байте не мешая другим составляющим, но в сумме из них должно получиться одно большое число, которое можно найти по формуле R + G * 256 + B * 256 * 256.
Если же попробовать сделать по предложенному тобой методу, то все цвета будут в одной куче где-то посередине нашего байта, и будет математически влиять друг на друга.
А например, ярко красный, ярко зелёный и ярко синий по твоему методу будут в байте записываться одинаково: 00001100
Очевидно что это не то что нам надо, всё-таки это три разных цвета.
- Ответить Keker | Ноябрь 27th, 2020
  
  Спасибо за столь подробное обьяснение, думаю теперь я понял)
Ответить Юрий Йосифович | Ноябрь 28th, 2020

Спасибо за отличную публикацию.
Скажите пожалуйста функция gd2 imagecopyresampled это стандартное масштабирование без сохранения пропорций, или это какое-то специфическое масштабирование?

Также если есть время/возможность набросать пример как на вход подавать не с файла, а например POST запросом, передавая картинку в base64.

Пытаюсь переписать на C#, не особо получается.
Возможно проще подавать POST запросом с C# одну картинку в base64, и в ответ получать есть ли в базе такой хеш уже или нет…
Но, познаний в PHP не достаточно, чтобы понять как это сделать…
Ответить mihanentalpo | Ноябрь 28th, 2020

imagecopyresamples — копирует изображение с масштабированием и «ресемплингом», то есть если картинка была 128х128 а должна стать 64х64, то каждый пиксел результирующего изображения будет получен путем усреднения 4х пикселей исходного (4 потому что 2 по горизонтали и 2 по вертикали). В C# должна быть подобная функциональность.
Подробнее: https://www.php.net/manual/ru/function.imagecopyresampled.php

Что касается передачи файла на вход пост-запросом, это делается легко.

$file_b64 = $_POST[‘file_b64’];
$file = base64_decode($file_b64);
$image = imagecreatefromstring($file);

Дальше с image можно работать как будто оно было загружено из файла.
Но вообще не советую этого делать. На C# тот же код будет работать в 100 раз быстрее чем на Php

MihanEntalpo blog Php, javascript, jquery, yii, webasyst, nginx, Python и все-все-все