Алгоритм быстрого нахождения похожих изображений

[nightflash]

На самом деле сравнение по яркости не самый лучший вариант, ибо будет пропущено большое кол-во одинаковых изображений имеющих разную яркость, даже более грубый порог не даст достаточно хорошего результата.
Имеет смысл нормировать яркость (приводить ее к общему знаменателю) и затем уже сравнивать изображения. Если задача стоит именно в \поиске одинаковых по содержанию изображений.

[dab512]

Думаю, что это само собой разумеется.

[ErmIg]

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

[Petrify]

Все-таки одинаковые изображения разной контрастности будут определятся как разные. Например можно провести эквализацию гистограммы(пример)

[xiWera]

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

[Kindman]

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

[ErmIg]

Многие форматы изображений, тоже поддерживают миниатюры (для JPEG это изображение уменьшенное в 8 раз). Для получения уменьшенного изображения в Gdiplus даже есть специальная функция, вроде называется GetThumbnail(), ее я и использовал для формирования уменьшенного изображения.

[dom1n1k]

На практике, большинство изображений в одной коллекции, как правило, имеет одинаковое соотношение сторон (например — 3:4), но имеет разную ориентацию (вертикальную или горизонтальную). Таким образом, мы получаем два изолированных класса изображений, которые не обязательно сравнивать друг с другом.

Мой фотоаппарат нередко и непредсказуемо (для меня) сохраняет фотографию в другой ориентации, но прописывает правильную в EXIF. А дальше зависит от софта: Фотошоп понимает этот флаг, а например мой привычный просмотрщик — нет.

[pxx]

Пост про сравнение картинок без картинок.

[ErmIg]

Верное замечание. В следующий раз напишу с картинками.

[Kindman]

Соотношение сторон — плохой помощник для отсеивания похожих изображений.
Во-первых, БОЛЬШИНСТВО цифровых изображений имеют соотношение близкое к 3х4 (или 4х3).
Во вторых, многие фотографы (и дизайнеры) после того как закачают фотки на комп, начинают вручную массово поворачивать половину изображений на ± 90 градусов. (при этом содержимое не меняется, а соотношение сторон — меняется)

[ErmIg]

Для этого у меня в программе есть поиск повернутых и отраженных дубликатов.

[Levsha100]

На сколько я понял алгоритм не инвареантен к сдвигу/повороту, т.е. мы не сможем найти откадрированную копию, например. Есть ли какие-то алгоритмы, которые учитывают сдвиг/поворот?

[dosyas]

Согласно некоторым статьям, успешные реализации поиска похожих картинок работает на основе так называемого «мешка слов». Т.е. из изображений выделяются особые точки, кластеризуются и формируется словарь особых точек. После этого все картинки раскладываются по данному словарю. Дальше поиск ничем не отличается от обычного текстового поиска с ранжированием по метрикам схожести документов.

Дабы не быть голословным, вот.

[UksusoFF]

Кстати, спасибо за программу, давно пользую :)

[edeldm]

После пункта «Приведение всех изображений к одному размеру» читать не стал.

Значительно актуальнее и интереснее вопрос поиска похожих изображений разного размера, причем не обязательно просто масштабированного. Например поиск кружки базируясь по ее фото на фото стола с приборами и этой кружкой.

*Но за старания и статью — автору ↑

[ErmIg]

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

[zen]

Неинтересный пост и алгоритм, ибо решает проблему поиска почтидупликатов, а это не очень интересно.

[Adiost]

Извините за столь дилетантский вопрос, но все же.
Вот есть у нас изображение, допустим, 100х100:



Берем и сжимаем его до 10х10, скажем, бикубически:



А теперь вопрос: почему нельзя вот так вот сжимать изображения и просто попиксельно их сравнивать?

[ErmIg]

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