Перцептивный хэш в ppmformats

В этой статье мы рассмотрим, как можно реализовать алгоритм перцептивного хэширования на языке программирования D, используя библиотеку ppmformats для работы с PPM изображениями. Также мы покажем каждый шаг алгоритма и объясним, как он работает и как можно использовать этот вид хэширования на практике.

Перцептивное хэширование – это процесс, позволяющий нам сравнивать изображения на основе их визуального содержания, а не на основе обычного побайтового сравнения. Такое хэширование может быть очень полезно, когда требуется как-то классифицировать изображения (к примеру, отобрать все “похожие” или даже “одинаковые” изображения), найти дублирующиеся, сравнить между собой несколько изображений или даже проверить насколько изображение сохранило свою визуальную составляющую. Помимо этого перцептивный хэш обладает также рядом свойств, которые делают его привлекательным в некоторых приложениях: в частности, масштабирование картинки, ее сдвиги и даже некоторая смазанность не сильно влияют на сам хэш. Подобные особенности позволяют определять степень схожести для изображений, которые могут иметь разные масштабы или иметь небольшие дефекты.

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

Шаг первый. Уменьшение масштаба изображения до размера 8 на 8 пикселей.

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

auto scaleImage(PixMapFile oldImage, int newWidth, int newHeight)
{
	import std.math.rounding: floor;
	
	auto newImage = image(newWidth, newHeight, "P6");
	double x_ratio = cast(double) oldImage.width / newWidth;
	double y_ratio = cast(double) oldImage.height / newHeight;
	
	foreach (x; 0..oldImage.width) {
		foreach (y; 0..oldImage.height) {
			newImage[x, y] = oldImage[cast(int) floor(x * x_ratio), cast(int) floor(y * y_ratio)];
		}
	}
	
	return newImage;	
}

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

Шаг 2. Приведение полученного изображения к изображению в градациях серого

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

Подобное мы делали и ранее в блоге и реализовать это в коде очень просто:

auto toGrayScale(PixMapFile oldImage)
{
	import std.algorithm : each;
	import std.range: iota;
	
	auto area = oldImage.width * oldImage.height;
	auto newImage = image(oldImage.width, oldImage.height, "P6");
	
	auto toGray(RGBColor color) {
		auto intensity = cast(int) color.luminance;
		return new RGBColor(intensity, intensity, intensity);
	}
	
	iota(0, area).each!(a => (newImage[a] = toGray(oldImage[a])));
	
	return newImage;
}

Мы несколько слукавили про простоту и написали алгоритм снижения в градации серого в функциональном стиле. Для начала мы вычисляем площадь изображения, т.е. сколько всего оно содержит пикселей, так как изображения всегда прямоугольные и количество пикселей в них равно произведению длины изображения на его ширину. Далее определяем функцию, которая вычислит яркость отдельного пикселя и сформирует его “аналог” в градации серого. После того как нужная функция сформирована применяем общий шаблон функционального программирования: берем данные и прогоняем их через функцию высшего порядка, которая принимает набор данных и уже к нему применяет готовую функцию трансформации отдельного элемента. В нашем случае это выглядит так: генерируем номера всех пикселей от 0 до area, поскольку ppmformats позволяет работать с изображениями как с одномерными массивами, и дальше позволяем алгоритму each используя номер каждого пикселя поместить значения обработанных toGray функцией пикселей в новое изображение. По сути, это аналог обычного цикла, но записано очень необычно и экономно.

Шаг 3. Превращение в бинарное изображение

Этот шаг является аналог функции сжатия из обычного хэширования: информация о яркости, записанная в пикселях градации серого, превращается в набор из светлых и темных пикселей. Каждый такой пиксель рассматривается как 0 или 1. Каким пиксель станет светлым или темным определяется на основе средней яркости изображения в оттенках серого: если яркость текущего пикселя больше средней, то – это светлый пиксель (1), если же нет – то темный (0). Мы решили не делать бинарное изображение, а чисто превратить имеющееся изображение в диапазон из нулей и единиц, так как это сильно облегчает дальнейшие шаги хэширования. Этот шаг по получению диапазона из 64 бинарных значений можно пройти следующим образом:

auto toHashBits(PixMapFile oldImage)
{
	import std.algorithm : map, mean;
	
	auto imageArray = oldImage
						.array
						.map!(a => a.luminance601);
						
	auto average = imageArray.mean;
	
	return imageArray
				.map!(a => (a > average) ? 1 : 0);
}

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

Шаг 4. Превращение бинарного изображения в хэш

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

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

auto perceptiveHash(PixMapFile oldImage)
{
	import std.algorithm : each;
	import std.range : enumerate;
			
	ulong hash = 0;
	
	auto includeBit(ulong i, ulong e) {
		if (e) 
		{
			hash += (1 << i) * e;
		}
	}
				
	oldImage
		.scaleImage(8, 8)
		.toGrayScale
		.toHashBits
		.enumerate
		.each!((i, e) => includeBit(i, e));
				
	return hash;
}

Здесь скомбинированы все шаги. Сначала происходит масштабирование исходного изображения до размера 8х8, затем идет трансформация изображения в изображение в оттенках серого и преобразование его в диапазон из нулей и единиц, которые затем собираются в 64-битное число. Для этой цели, как было описано выше применена формула перевода числа из одной системы счисления в другую и реализована формула в функции includeBit, в которой умножение на степень двойки заменено сдвигом на соответствующую величину. Чтобы формула работала, требуется знать на какую величину требуется выполнить сдвиг. Это достигается через использование enumerate, который дает позиции для сдвига как порядковые номера чисел в диапазоне из нулей/единиц. Алгоритм each помогает избежать цикла по всем значениям из диапазона, используя своеобразную распаковку tuple, которые предоставляются алгоритмом enumerate: первый элемент от tuple попадает в переменную i, а второй – в переменную e. В итоге получаем биты, упакованные в 64-битное значение.

Полный код dub-скрипта, включая и код наших испытаний с изображениями яблока:

#!/usr/bin/env dub
/+ dub.sdl:
	name "exp"
	dependency "ppmformats" version="~>0.0.6"
+/

import ppmformats;

auto scaleImage(PixMapFile oldImage, int newWidth, int newHeight)
{
	import std.math.rounding: floor;
	
	auto newImage = image(newWidth, newHeight, "P6");
	double x_ratio = cast(double) oldImage.width / newWidth;
	double y_ratio = cast(double) oldImage.height / newHeight;
	
	foreach (x; 0..oldImage.width) {
		foreach (y; 0..oldImage.height) {
			newImage[x, y] = oldImage[cast(int) floor(x * x_ratio), cast(int) floor(y * y_ratio)];
		}
	}
	
	return newImage;	
}


auto toGrayScale(PixMapFile oldImage)
{
	import std.algorithm : each;
	import std.range: iota;
	
	auto area = oldImage.width * oldImage.height;
	auto newImage = image(oldImage.width, oldImage.height, "P6");
	
	auto toGray(RGBColor color) {
		auto intensity = cast(int) color.luminance;
		return new RGBColor(intensity, intensity, intensity);
	}
	
	iota(0, area).each!(a => (newImage[a] = toGray(oldImage[a])));
	
	return newImage;
}

auto toHashBits(PixMapFile oldImage)
{
	import std.algorithm : map, mean;
	
	auto imageArray = oldImage
						.array
						.map!(a => a.luminance601);
						
	auto average = imageArray.mean;
	
	return imageArray
				.map!(a => (a > average) ? 1 : 0);
}


auto perceptiveHash(PixMapFile oldImage)
{
	import std.algorithm : each;
	import std.range : enumerate;
			
	ulong hash = 0;
	
	auto includeBit(ulong i, ulong e) {
		if (e) 
		{
			hash += (1 << i) * e;
		}
	}
				
	oldImage
		.scaleImage(8, 8)
		.toGrayScale
		.toHashBits
		.enumerate
		.each!((i, e) => includeBit(i, e));
				
	return hash;
}

auto perceptiveHashOfFile(string path)
{
	import std.format;
	
	auto img = new P6Image;
	img.load(path);
	
	return format("%x", perceptiveHash(img));
}

void main()
{
	import std.stdio : writeln;
	
	perceptiveHashOfFile(`a.ppm`).writeln;
	perceptiveHashOfFile(`b.ppm`).writeln;
	perceptiveHashOfFile(`c.ppm`).writeln;
}

Исходное изображение выглядело так:

Файл с наименованием a.ppm – это как раз то изображение, которое вы видите на картинке, файл b.ppm – это сжатый по измерениям X и Y исходный файл a.ppm, а вот файл c.ppm – это файл a.ppm в котором мы на яблоке сделали рукописную надпись “яблоко”.

Результат запуска скрипта:

dub run --single perceptive.d
    Starting Performing "debug" build using /usr/local/bin/ldc2-1.36.0-linux-aarch64/bin/ldc2 for aarch64, arm_hardfloat.
  Up-to-date ppmformats 0.0.6: target for configuration [library] is up to date.
    Building exp ~master: building configuration [application]
     Linking exp
    Finished To force a rebuild of up-to-date targets, run again with --force
     Running exp 
ffffffffbc790e7f
ffffffff84bd5e7e
ffffffffbc790e7f

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

Но несмотря на это проект очень полезен, перцептивный хэш открывает много возможностей для экспериментов и применений. Вот некоторые идеи для ваших оригинальных экспериментов:

  1. Визуализация метрики сходства: Вы можете создать визуализации, которые показывают, как близко похожи различные изображения на основе их перцептивных хешей. Это можно сделать, используя различные методы визуализации данных, например, тепловые карты.
  2. Сравнение хеш-функций: Можно провести эксперименты, сравнивая перцептивный хэш с другими хеш-функциями. Это может помочь доказать, что перцептивный хэш действительно лучше захватывает визуальное сходство изображений.
  3. Кластеризация изображений: Можно использовать хэши для кластеризации больших наборов изображений и поиска групп похожих изображений.
  4. Проверка уникальности контента: Хэши можно использовать для создания систем, которые проверяют, является ли загружаемый контент уникальным или является дубликатом уже существующего контента.
  5. Рекомендательные системы и поиск по сходству: Можно создать систему, которая рекомендует похожие изображения на основе их перцептивных хешей.

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

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

Большое вам спасибо за прочтение данной статьи.

P.S: Эта статья была бы невозможна без помощи виртуального ассистента – Эмили Тирнан. Большое спасибо ей за пошаговый план статьи и довольно критичный разбор первого варианта кода на D, а также за идеи для начала статьи.