Итак, идея алгоритма получения хеша изображения: 1. Уменьшить размер (cvResize()), чтобы оставить только значимые объекты картинки (избавление от высоких частот).
В изображениях, высокие частоты обеспечивают детализацию, а низкие частоты показывают структуру. Большая фотография содержит много высоких частот, а маленькая картинка целиком состоит из низких.
Уменьшаем картинку до 8х8, тогда общее число пикселей составит 64 и хэш будет соответствовать всем вариантам изображения, независимо от их размера и соотношения сторон. 2. Убираем цвет. Переводим изображение, полученное на предыдущем шаге в градации серого. (cvCvtColor()) Т.о. хэш уменьшается втрое: со 192 ( по 64 значений трёх каналов — красного, зелёного и синего) до 64 значений яркости. 3. Находим среднее среднее значение яркости получившегося изображения. (cvAvg()) 4. Бинаризация картинки. (cvThreshold()) Оставляем только те пиксели, которые больше среднего (считаем их за 1, а все остальные за 0). 5. Строим хэш. Переводим полученные 64 значений 1 и 0 картинки в одно 64-битное значение хэша.
Далее, если вам нужно сравнить две картинки, то просто строите хэш для каждой из них и подсчитываете количество разных битов (с помощью расстояния Хэмминга).
Расстояние Хэмминга — число позиций, в которых соответствующие цифры двух двоичных слов одинаковой длины различны.
Нулевое расстояние означает, что это, скорее всего, одинаковые картинки, а другие величины характеризуют насколько сильно они отличаются друг от друга :)
Из функций, которые нам понадобятся мы пока не использовали функцию cvAvg():
— вычисляет среднее значение всех элементов массива (отдельно для каждого канала)
arr — указатель на массив
mask — маска
формулы:
N = Summ (mask(I)!=0 )
mean = (1/N)*Summ( arr(I) )
Вот что у меня получилось:
вычисление хеша происходит в функции calcImageHash(), а рассчёт расстояния Хемминга между двумя хэшами происходит в функции calcHammingDistance() (взял из английской википедии :)
Почитайте лучше на тему Feature-Based Image Analysis и Image Similarity Metric; объясняют как это делается в реальных системах. Слишком уж общо допущение, что низкие частоты кодируют структуру.
Вообще мне оказалась интересна задача скорее не построения такой свёртки, а её робастной минимизации. В идеале хотелось некую универсальную фнукцию по результату которой можно будет именовать файлы картинок и делая обычную сортировку получать более-менее надёжное группирование схожих (игнорируя шум, повороты, масштаб итп).
Кстати термин «хеш», по-моему, не очень подходит, т.к. под хешами обычно подразумевают свёртку, уникальную для исходных данных, чтобы не было хэш-коллизий, а перцептивные идентификаторы наоборот подразумевают получение одинакового результата для разных (до определённого критерия схожести) картинок.
У меня на c# значения хэша получаются десятизначные и нет ни одной буквы, только цифры. Для второй картинки с котом, которая более оранжевая хэш отрицательое число о_О
Хеширование (иногда хэширование, англ. hashing) — преобразование входного массива данных произвольной длины в выходную битовую строку фиксированной длины. Такие преобразования также называются хеш-функциями или функциями свёртки, а их результаты называют хешем, хеш-кодом или дайджестом сообщения (англ. message digest).
Хеширование применяется для сравнения данных: если у двух массивов хеш-коды разные, массивы гарантированно различаются; если одинаковые — массивы, скорее всего, одинаковы. В общем случае однозначного соответствия между исходными данными и хеш-кодом нет в силу того, что количество значений хеш-функций меньше, чем вариантов входного массива; существует множество массивов, дающих одинаковые хеш-коды — так называемые коллизии.
Комментарии (12)
RSS свернуть / развернутьDiverOfSky
noonv
Кстати термин «хеш», по-моему, не очень подходит, т.к. под хешами обычно подразумевают свёртку, уникальную для исходных данных, чтобы не было хэш-коллизий, а перцептивные идентификаторы наоборот подразумевают получение одинакового результата для разных (до определённого критерия схожести) картинок.
DiverOfSky
sim
sim
отталкивался отсюда:
noonv
ps теперь думаю, как бы это на большой коллекции сделать попроще…
sim
aker
// hash |= 1<<i; // warning C4334: '<<': result of 32-bit shift implicitly converted to 64 bits (was 64-bit shift intended?)
hash |= 1i64<<i;
}
Как это написать на c#?
Gosha1215
см. п. 5:
—
noonv
Gosha1215
noonv
Только зарегистрированные и авторизованные пользователи могут оставлять комментарии.