Найти похожие фрагменты в картинках

[gevaraweb]

Подсел на игру "Найди 5 отличий" Вконтакте. Суть игры: даны две картинки, надо найти отличия ) Раньше играли в такое в цветных журналах )

Например:



Выигрывать в принципе несложно. Но иногда картинка (вырви глаз):

(Оффтоп)

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

1) Определить координаты вершин прямоугольников, которые ограничивают похожие картинки.
2) Пробежаться и сравнить попиксельно внутри прямоугольников. Где разные пикселы, замазать зеленкой.

Пикселы обычно обыкновенная матрица с целыми значениями.

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

(Оффтоп)

Мое решение (наобум). Взять схему как из чм , вычислить значения в узлах, приписать по некоторому правилу их комбинацию главному узлу.
и так для всех точек.

[wrest]

(Оффтоп)

gevaraweb
Пока учитесь решать программно, дам совет как читерить при помощи глаз.
Располагаете картинки горизонтально, затем левым глазом смотрите на правую а правым на левую (сводите взгляд) и все отличия видны прям сразу.

[Dmitriy40]

Хитрый какой, а если у одной из картинки чуть поправят цветовую насыщенность, контраст или гамма-коррекцию? Не совпадут все пиксели.

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

PS. Интересно почему я на приведённых картинках нашёл 6-8 отличий?

[gevaraweb]

Dmitriy40 в сообщении #1327953 писал(а):

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

PS. Интересно почему я на приведённых картинках нашёл 6-8 отличий?

Видимо, какие-то традиции, в правилах сказано: уровни также отличаются между собой количеством отличий в картинке (от 5 до 10).
Нее, никакой ручной работы )

[Dmitriy40]

Без ручной работы совсем просто не получится, код будет весьма вычурным.
В качестве идеи: перейти от пикселей к пространственным частотам, делить весь скрин на постепенно уменьшающиеся куски и искать более-менее совпадения спектров. Примерно так делается для motion detecting (обнаружении движения - смещения в кадре) при упаковке видео.

[grizzly]

Dmitriy40 в сообщении #1327953 писал(а):

Интересно почему я на приведённых картинках нашёл 6-8 отличий?

Меньше 7 ни на одной нет

-- 20.07.2018, 22:17 --

Нашёл ещё мета-отличие

gevaraweb в сообщении #1327951 писал(а):

[subj] Найти похожие фрагменты

gevaraweb в сообщении #1327951 писал(а):

Суть игры: ... надо найти отличия

[Pavia]

Такое реализовано почти в каждом кодеки - стадия называется "предсказание движения".
А так же в детекторах движения. Методом Histogram of Oriented Gradients, HOG определяется смещение камеры, сцены и отдельных объектов. Далее эти смещения устраняются. Далее вычитание одной картинки из другой или ксорим непомню, что лучше. Далее фильтруем. Далее после ищем кляксы (blobs). Отбрасываем очень маленькие, оставляем крупные и для них выводим очерчивающий прямоугольник.

Фильтрация нужна для того, чтобы устранить разрывы между кляксами восстановить дыры в них. А так же убрать оставшиеся шумы. Я обычно несколько раз накладываю размытие. - можно и математической морфологией добиться такого же, используя операторы открытия и расширения. Или использовать суперпиксели.

Dmitriy40 в сообщении #1327958 писал(а):

пространственным частотам

По моему тут у вас ошибка. Часто путают гистограммы со спектром. От куда у вас и возникли простоанмвенные частоты. Если говорить про корреляционные методы то они плохо работают.

Dmitriy40 в сообщении #1327953 писал(а):

Хитрый какой, а если у одной из картинки чуть поправят цветовую насыщенность, контраст или гамма-коррекцию? Не совпадут все пиксели.

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

[Dmitriy40]

Pavia в сообщении #1328175 писал(а):

По моему тут у вас ошибка. Часто путают гистограммы со спектром.

Возможно. Я имел в виду именно преобразование Фурье, примерно как в JPEG. Но возможно HOG в данном случае правильней.

Pavia в сообщении #1328175 писал(а):

Просто о нём редко упоминают, а так он есть в любом методе распознования.

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

(Оффтоп)

grizzly в сообщении #1327961 писал(а):

Меньше 7 ни на одной нет

Ну, я долго не замечал карандаш у девушки. А так да, нашёл 8,7,8 отличий.

[gevaraweb]

Dmitriy40 в сообщении #1327953 писал(а):

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

Да, в итоге так и сделал.
Использовал уж свой костыль, чтоб найти прямоугольники. Но неудачно начал сравнивать сами ржб, и замучился. Наступил на те же грабли. Как назло, первая картинка была идеальной, все работало. Потом на других тестах - ни в какую. Дошло, стал сравнивать синюю составляющую ржб, этого хватило. РЖБ сильно скачет, составляющие почти совпадают. Прога создает новую серую картинку с закраской:
Вот результат:

(Оффтоп)

Вертикальные картинки переворачивал вручную перед проверкой:

(Оффтоп)

Работает 10-20 сек. Срабатывает в 70 % случаях Плохо работает на картинках, где много однородного фона.

Не смог только сделать, как отличить первый случай от второго, про расположение фрагментов, чтоб руками не переворачивать. Думал будет просто - беру рандомные горизонтальные и вертикальные линии, и считаю кол-во повторений... Не, не прокатило.

Еще бы проверить на фото экрана, а не на скрине.... Правда большие сомнения что будет работать )

[Dmitriy40]

Думаю не будет - как минимум из-за искажений геометрии, т.е. одинаковые пиксели скрина спроецируются в неодинаковые на фото.

-- 24.07.2018, 15:14 --

Насчёт автоопределения ориентации, подсчитайте два числа, количество совпадений для горизонтальной и вертикальной ориентации. Они должны сильно различаться и большее укажет на правильную ориентацию. А чтобы срабатывало не за 20-40 секунд, считайте точки с шагом 3-7 по обеим координатам (сработает в 10-50 раз быстрее).

[Pavia]

Dmitriy40 в сообщении #1328519 писал(а):

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

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

gevaraweb в сообщении #1328515 писал(а):

Еще бы проверить на фото экрана, а не на скрине.... Правда большие сомнения что будет работать )

Если снимать под прямым углом, то там незначительные искажения(после устранения дисторсии). А вот если под произвольным, то надо будет в вести в модель обработки соответствующие искажения. К примеру HoG заменяем на SIFT или SURF.

[wrest]

gevaraweb в сообщении #1328515 писал(а):

РЖБ сильно скачет, составляющие почти совпадают

RGB это конечно не то. Надо в какой-то яркостно-цветовой формат переводить, типа Lab или HSL, а то может и вовсе в ЧБ, для надежности.
А нет, в ЧБ не пойдет, судя по картинке с художницей зеленый и сиреневый лес одной яркости там.

[Dmitriy40]

Pavia в сообщении #1328565 писал(а):

Не факт. Автор темы использует простой алгоритм сравнения. А там в шумах утонет. Что-бы более или менее работало надо использовать особые точки - такие как углы.

Для скринов должно работать, там искажений RGB (разных для двух картинок) и шумов быть не должно. А вот с углами и сторонами всё хуже - туда может попасть отличие картинок и испортить статистику. Я сразу хотел предложить искать границы (стороны или углы), но потом передумал, намного ненадёжнее. Для статистики же по всей картинке одно число даже в худшем случае будет порядка 50% (а реально должно быть сильно меньше), зато второе будет не меньше чем количество совпадающих точек на картинках, а это сильно более 90%. Прореживание картинки конечно сдвинет пороги, но совсем чуть, я ж предложил не по 100 точкам набирать статистику, а по паре процентов всей картинки.

-- 24.07.2018, 21:05 --

wrest
Для получения ориентации можно, но зачем? Сравнить RGB даже проще и быстрее пересчёта и сравнения ЧБ.

-- 24.07.2018, 22:01 --

Подсчитал совпадение картинок с пейзажем и часами по горизонтали и вертикали без прореживания:
1. Пейзаж, 2.2% против 27%, совпадение цветов точное.
2. Часы, для точного совпадения цветов 4.8% и 0.9%; для допустимого несовпадения $|\Delta R|+|\Delta G|+|\Delta B|<18$ (из максимум $255$) получается 18% и 2.6%.
Считаю во всех случаях вполне реально отличить ориентацию.
Время счёта полсекунды.

[Pavia]

Dmitriy40
Вот видите у вас даже 50% не получилось всего 27% и 18%.

Во-вторых напоминаю что изначально задача

gevaraweb в сообщении #1327951 писал(а):

1) Определить координаты вершин прямоугольников, которые ограничивают похожие картинки.

А вы решили совершенно другую.
Если бы вы честно взяли скриншот. Когда у вас вокруг часов ещё и текст с форума. Плюс картинки не точно посередине. То проценты были бы ещё ниже. Но о цифрах я говорить не буду так как чёткого алгоритма не обозначено. А смена алгоритма может их изменить статистику в нужную сторону.

[Dmitriy40]

Pavia
Вы проглядели контекст, я говорил исключительно об автоопределении ориентации:

Dmitriy40 в сообщении #1328519 писал(а):

Насчёт автоопределения ориентации, подсчитайте два числа,

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