Эта статья с месяц висела у меня в черновиках, пока кто-то мне наконец не привел карму к тонусу. Не знаю кто, но спасибо тебе
Сегодня, зайдя в очередной раз на хабр, наткнулся на вот эту интересную статью. Там описывается алгоритм хэширования изображений. Когда я читал эту статью, мне пришла в голову мысль, как можно изменить этот алгоритм, чтобы он кушал изображения, у которых сильно различается, например, яркость (но сами изображения при этом идентичны).
Возможно такой метод уже существует давно и кем-то давно описан, ну, в таком случае, у меня по крайней мере есть готовый код.
Алгоритм заключается в том, что нам нужно записать в массив разницу между каждыми i-м и (i + 1)-м пикселем. Таким образом этот массив и есть хэш для нашего изображения (при необходимости можно привести его в строковый вид). То есть, основываясь на этом, мы полагаем, что наше изображение — это не набор пикселей определенного цвета, а скорее совокупность разностей между этими пикселями.
Результаты тестирования такого алгоритма оказались довольно занятными, но они будут ниже, после разбора кода.
Теперь разберем этот алгоритм на коде.
Я написал простенький класс, который может сравнивать любое количество изображений, отдавая разность между каждым из них.
Вот сам класс, если хотите, можете на нем и остановится, или Вы можете почитать дальше что тут и к чему.
В конструкторе на каждое изображение вызывается метод _getPixelsDiff(), и его результат кладется в массив Images. Этот метод производит такие манипуляции:
Кстати, исходя из этого кода, самая большая разность у изображений может составлять 1701 (63 * 3 * 9, поправьте если это не так).
А теперь тесты.
Первая пара картинок: раз и два. Первая картинка — логотип Air Jordan. Вторая — пародия на первую в исполнении Бендера. Согласитесь, на глаз довольно похожие картинки. И наша программа выдает на них 68 баллов разности из 1701. То есть вероятность их идентичности примерно 96.1%.
Вторая пара картинок: раз и два. Выдает разность, равную 266, хотя цветовая гамма у них довольно похожая. Кстати, получается, что эти рисунки с вероятностью 85% идентичны. Так что планку (извините, порог) надо ставить довольно высокую.
Вот еще пара: раз и два. Разность 52.
В общем я не считаю, что этот метод идеален, но, по крайней мере, думаю он имеет право на жизнь.
UPD. Сравнение этого изображения и этого. Контрастность второго была сильно изменена как видим. Разность — 70 попугаев из 1701.
Сегодня, зайдя в очередной раз на хабр, наткнулся на вот эту интересную статью. Там описывается алгоритм хэширования изображений. Когда я читал эту статью, мне пришла в голову мысль, как можно изменить этот алгоритм, чтобы он кушал изображения, у которых сильно различается, например, яркость (но сами изображения при этом идентичны).
Возможно такой метод уже существует давно и кем-то давно описан, ну, в таком случае, у меня по крайней мере есть готовый код.
Алгоритм заключается в том, что нам нужно записать в массив разницу между каждыми 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. Этот метод производит такие манипуляции:
- Уменьшает изображение до размеров 8x8.
- Создает массив для цветов.
- Проходится по каждому пикселю изображения:
- Берет его цвет в RGB.
- Каждый канал делит на 28.3 и округляет, чтобы максимальное значение канала было равно 9-ти.
- Вычитает из каждого канала значение предыдущего пикселя.
- Результат кладется в массив и возвращается.
Кстати, исходя из этого кода, самая большая разность у изображений может составлять 1701 (63 * 3 * 9, поправьте если это не так).
А теперь тесты.
Первая пара картинок: раз и два. Первая картинка — логотип Air Jordan. Вторая — пародия на первую в исполнении Бендера. Согласитесь, на глаз довольно похожие картинки. И наша программа выдает на них 68 баллов разности из 1701. То есть вероятность их идентичности примерно 96.1%.
Вторая пара картинок: раз и два. Выдает разность, равную 266, хотя цветовая гамма у них довольно похожая. Кстати, получается, что эти рисунки с вероятностью 85% идентичны. Так что планку (извините, порог) надо ставить довольно высокую.
Вот еще пара: раз и два. Разность 52.
В общем я не считаю, что этот метод идеален, но, по крайней мере, думаю он имеет право на жизнь.
UPD. Сравнение этого изображения и этого. Контрастность второго была сильно изменена как видим. Разность — 70 попугаев из 1701.