2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Найти похожие фрагменты в картинках
Сообщение20.07.2018, 21:19 


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

Например:

Изображение

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

(Оффтоп)

Изображение


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

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

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

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

(Оффтоп)

Изображение


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

Изображение

 Профиль  
                  
 
 Re: Найти похожие фрагменты в картинках
Сообщение20.07.2018, 21:31 


05/09/16
11625

(Оффтоп)

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

 Профиль  
                  
 
 Re: Найти похожие фрагменты в картинках
Сообщение20.07.2018, 21:31 
Заслуженный участник


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

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

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

 Профиль  
                  
 
 Re: Найти похожие фрагменты в картинках
Сообщение20.07.2018, 21:43 


15/11/15
971
Dmitriy40 в сообщении #1327953 писал(а):
Дык вырежьте руками область лишь с картинками, а там останется лишь два варианта: горизонтальное или вертикальное деление примерно пополам, что уже нетрудно обработать автоматически.

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

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

 Профиль  
                  
 
 Re: Найти похожие фрагменты в картинках
Сообщение20.07.2018, 21:51 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Найти похожие фрагменты в картинках
Сообщение20.07.2018, 22:00 
Заслуженный участник
Аватара пользователя


09/09/14
6328
Dmitriy40 в сообщении #1327953 писал(а):
Интересно почему я на приведённых картинках нашёл 6-8 отличий?
Меньше 7 ни на одной нет :D

-- 20.07.2018, 22:17 --

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

 Профиль  
                  
 
 Re: Найти похожие фрагменты в картинках
Сообщение22.07.2018, 12:14 
Аватара пользователя


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

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

Dmitriy40 в сообщении #1327958 писал(а):
пространственным частотам

По моему тут у вас ошибка. Часто путают гистограммы со спектром. От куда у вас и возникли простоанмвенные частоты. Если говорить про корреляционные методы то они плохо работают.
Dmitriy40 в сообщении #1327953 писал(а):
Хитрый какой, а если у одной из картинки чуть поправят цветовую насыщенность, контраст или гамма-коррекцию? Не совпадут все пиксели.

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

 Профиль  
                  
 
 Re: Найти похожие фрагменты в картинках
Сообщение22.07.2018, 15:42 
Заслуженный участник


20/08/14
11353
Россия, Москва
Pavia в сообщении #1328175 писал(а):
По моему тут у вас ошибка. Часто путают гистограммы со спектром.
Возможно. Я имел в виду именно преобразование Фурье, примерно как в JPEG. Но возможно HOG в данном случае правильней.
Pavia в сообщении #1328175 писал(а):
Просто о нём редко упоминают, а так он есть в любом методе распознования.
Ага, упомянул именно чтобы показать что задача сравнения даже найденных областей не так проста как кажется ТС.

(Оффтоп)

grizzly в сообщении #1327961 писал(а):
Меньше 7 ни на одной нет :D
Ну, я долго не замечал карандаш у девушки. :facepalm: А так да, нашёл 8,7,8 отличий.

 Профиль  
                  
 
 Re: Найти похожие фрагменты в картинках
Сообщение24.07.2018, 14:46 


15/11/15
971
Dmitriy40 в сообщении #1327953 писал(а):
Дык вырежьте руками область лишь с картинками, а там останется лишь два варианта: горизонтальное или вертикальное деление примерно пополам, что уже нетрудно обработать автоматически.

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

(Оффтоп)

Изображение

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

(Оффтоп)

Изображение


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

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

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

 Профиль  
                  
 
 Re: Найти похожие фрагменты в картинках
Сообщение24.07.2018, 15:09 
Заслуженный участник


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

-- 24.07.2018, 15:14 --

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

 Профиль  
                  
 
 Re: Найти похожие фрагменты в картинках
Сообщение24.07.2018, 20:37 
Аватара пользователя


31/10/08
1244
Dmitriy40 в сообщении #1328519 писал(а):
Насчёт автоопределения ориентации, подсчитайте два числа, количество совпадений для горизонтальной и вертикальной ориентации. Они должны сильно различаться и большее укажет на правильную ориентацию.

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

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

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

 Профиль  
                  
 
 Re: Найти похожие фрагменты в картинках
Сообщение24.07.2018, 20:47 


05/09/16
11625
gevaraweb в сообщении #1328515 писал(а):
РЖБ сильно скачет, составляющие почти совпадают

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

 Профиль  
                  
 
 Re: Найти похожие фрагменты в картинках
Сообщение24.07.2018, 21:02 
Заслуженный участник


20/08/14
11353
Россия, Москва
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%.
Считаю во всех случаях вполне реально отличить ориентацию.
Время счёта полсекунды.

 Профиль  
                  
 
 Re: Найти похожие фрагменты в картинках
Сообщение25.07.2018, 19:51 
Аватара пользователя


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

Во-вторых напоминаю что изначально задача
gevaraweb в сообщении #1327951 писал(а):
1) Определить координаты вершин прямоугольников, которые ограничивают похожие картинки.

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

 Профиль  
                  
 
 Re: Найти похожие фрагменты в картинках
Сообщение25.07.2018, 20:42 
Заслуженный участник


20/08/14
11353
Россия, Москва
Pavia
Вы проглядели контекст, я говорил исключительно об автоопределении ориентации:
Dmitriy40 в сообщении #1328519 писал(а):
Насчёт автоопределения ориентации, подсчитайте два числа,
С величиной чисел ошибся, скорее всего шум из-за разного сжатия JPEG половинок общей картинки, т.к. исходные данные с потерями, то и не стал разбираться, благо отношение чисел достаточно велико.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 16 ]  На страницу 1, 2  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group