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

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

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

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

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

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

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

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

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

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

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

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

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

Далее, исходное изображение с помощью функции библиотеки 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);
    }
}

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

//Цветов на один пиксел (число от 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->compare($hash1, $hash2, 0.05);
echo "Хэши изображений равны?:" . ($isEqual ? "Да" : "Нет");
echo "Хэши изображений равны с точностью до 5%?:" . ($isNearEqual ? "Да" : "Нет");

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

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

2 комментария

Оставить комментарий