×Закрыть

Сравнение изображений

Привет,

Разыскиваю разработчика (или того, кто подскажет как) разработать и реализовать алгоритм сравнения скриншотов веб страниц. Сейчас использую для этих целей imagemagick. И из изображений
ygerasimovvrt.s3.amazonaws.com/.../httpswwwukrnet-797e1.png
и
ygerasimovvrt.s3.amazonaws.com/.../httpswwwukrnet-73acd.png
получаю
ygerasimovvrt.s3.amazonaws.com/...2015/04/23/diff-ad0de.png

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

Если подобные решения уже существуют — буду очень признателен за помощь.

Спасибо!

Юрий

👍НравитсяПонравилось0
В избранноеВ избранном0
LinkedIn
Допустимые теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter
Допустимые теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter

Большое спасибо за наводку. Насколько я понял там используется попиксельное сравнение, что уже imagemagick делает.

Я смотрел
github.com/...mparison/ImageDiffer.java

конкретно приведенный вами пример, идеально будет в 2 этапа решать
1) собственно тоже что вы и сделали (предпологаю что там обычное вычитание/xor)
2) анализировать участки которые оказались различными

Предложенное

Mike Gorchak
выглядит лучше. Разве что размер тайлов подобрать с точки зрения бысродействия.

И чем же оно лучше? :)

Из всего предложеного будет работать максимально быстро и очень просто в реализации.
В его варианте все делается за один проход по картинке. Причем легко распараллеливается.

дальше интересней :))) как же вы это за один проход то сделаете? как вы посчтитали что это максимально быстро?

Бью на тайлы. Затем pdist2 по тайлам. Затем наиболее близкие сопоставить.

если бы было все так просто... этот алгоритм будет работать только если у вас смещение будет кратное размеру тайла... а это возможно только если ваш тайл будет 1×1 что приведет к тому что у вас будет в основном false-positive результаты... а значит 1-м проходом вы не обойдетесь

Проблема в том, что разница изображений в правой колонке только появившийся банер. Изза этого подсвечивается вся колонка, а хотелось бы только выделять банер. Тоесть если произошло смещение, то находить соответствующую совпадающую область и ее не подсвечивать.
Ты невнимательно прочитал задачу. Границу потом можно уточнить. По задаче я получу расстояния 0 на одинаковых тайлах — их много будет.

ну вот и проверь те ваш алгоритм на таких данных:
размер банера 100×8 а вашего тайла 16×16
если вам нравится размер тайла 8×8 проверьте с банером 100×4

И 0 на совпадающих и не 0 на несовпадающих. Потом только выделить границу и уточнить в тайлах по границе. Здесь же нет шумов, смещения картинки или ее поворота.

вы таки попробуйте, потом расскажите...

Что мне за это будет. А то мне сильно лень уже несколько дней вот в этом разобраться даже www.cs.northwestern.edu/~ago820/color2gray — хоть там и код есть и все все все.

А MPEG энкодит разве не таким же образом, есть макроблоки (тайлы) и делается дифф к I-frame с маркировкой motion vector для каждого макроблока. Ну зацепит макроблок кусок не банера, супер точный результат с выравниванием на пиксель на выходе никто не ожидает.

мпег2 делает motion detection в окне
h264 (он же mpeg4 part 10) если активировать то делает даже Quarter-pixel motion

только это далеко не алгоритмы в один проход

У меня по подобному алгоритму работает автоматический тест для графических драйверов, которые сравнивают результат с golden image и пытаются найти куски изображения golden image в результирующей картинке. Пустые тайлы, которые не содержат никаких данных (solid fill) отбрасываются, не пустые ищутся в golden image с 25% толерантностью по каждому цветовому каналу. На выходе имеем дифф двух изображений. Толерантность можно уменьшать, но тут начинают появляться проблемы с точностью дизеринга, альфа блендинга, антиалиазинга, etc.

а зачем по каждому цветовому каналу? для начала достаточно по яркости, потом уже можно и каждый канал. а так конечно без motion detection никуда не деться. но в случае сравнения 2-х предоставленных картинок как по мне лучше сначала сравнить целиком, так меньше вероятность на prefetch miss нарваться

а зачем по каждому цветовому каналу?
Например, при антиалиазинге цвет пикселя состоит из усреднённого 2×2, 3×3 пикселя, etc. Вес каждого пикселя в результирующем может отличаться, вот отсюда и сранение по цвету по принципу «где-то рядом».
выравниванием на пиксель
можно уже уточнить только по тайлам, где различия. Твоим подходом мы сначала находим области кратные шагу тайла, что отличаются, а потом уже только в этих областях уточняем, если нужно. У меня опыта в визуальных немного, но к матрице pdist я бы попробовал еще какой аналог ДП применить, если быстродействия не хватать будет (но, имхо, это сильно лишнее).

в случае же с одним проходом, как утверждает, Виктор. можно пологаться только на удачу, т.е. верить в то что смещения не будет, а иначе как в 1 проход то?

Стоп, не подумал. Да так влоб не выйдет. Был не прав.

спасибо за идею! каким образом стоит анализировать участки которые различаются?

я же не знаю какие у вас требования... если рассмотреть конкретно предоставленный вами пример:

допустим вы определили что есть различия в блоке NxM (в вашем случае вертикальное смещение) у вас таких 2 блока (из первой и второй картинки) двигаете вертикалько (вверх/вниз) любой из блоков на 1 пиксель и сравниваете, но это решение в лоб конкретного примера, а какие у вас входные данные мне неизвестно, вполне вероятно что прийдется разбивать на макроблоки и делать поиск оных в окне

На сколько я знаю OpenCV с таким легко справляется.

а нужно именно скриншоты? текстовый diff страницы работал бы лучше

Может здесь что-нибудь интересное есть
habrahabr.ru/...mpany/yandex/blog/238323

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

есть алгоритм на java
bitbucket.org/apoloz/image-comparison
только большие изображения могут вылетать, надо разбивать на несколько частей

Скормил ему два урла из топика ... ну уже 5 минут думает пока.

Uber якраз створили таку бібліотеку image-diff github.com/uber/image-diff яка є надбудовою imagemagick. А взагалі гугліть OCR або Visual regression.

дякую за наводку. Я подивився проект — це обертка навколо imagemagick і просто визиває його через джаваскрипт.

Можна використовувати SIFT keypoint matching
www.youtube.com/watch?v=HvvCMJjAUUE
Якщо точка знайдена на обох кадрах — то точка і її окіл позначається як біле —
якщо не знайдена відповідність між кадрами — червоне.

В случае задачи ТС — это стрелять из пушки по воробьям, как по мне.

Посмотрите на реализацию сравнения изображений в Galen Framework (galenframework.com/...pec-language-guide/#Image)
Там основная идея заключается в том, что верстка сайта проверятся не через сравнение всего изображения, а через проверку расположения элементов на странице. А затем уже отдельно для каждого элемента реализуется проверка изображения. В вашем случае это сработает, однако потребуется правильно описать верстку страницы.
Как вариант в Galen есть так называемая Page Dump. Она работает таким образом: вы даете только список объектов и их локаторов. Galen открывает сайт, вытягивает все объекты, вырезает изображения для каждого объекта отдельно из скриншота и генерирует отчет. Этот отчет затем позволяет сгенерировать проверки и просмотреть свойства объектов. Вот тут есть подробное видео www.youtube.com/watch?v=bheFQfEGR6U где объясняется как подготовить тестовые изображения, а также применять фильтры при проверке.

Спасибо огромное за идею. Я работаю над сервисом в котором идеально нетехнические люди смогли бы получать сравнения. Другими словами указание селекторов блоков будет слишком сложно для них. Но идея однозначно очень интересная!

Если планируется использовать только такие картинки — скриншоты браузера, то надо бить изображение на тайлы 8×8, 16×16, etc. и искать тайл исходного изображения в сравниваемом. Для облегчения сравнения тайлов можно использовать какой-нибудь perceptual hash (типа такого phash.org ). Хотя если это будут всегда скриншоты, то я не вижу проблем в сравнивании целых тайлов как они есть между собой.

погугли keypoint matching, думаю opencv это то что надо

и чем помогут они для решения его проблемы(в частности кусочка баннера)?

да там выше Evgen Gunya выложил чем
но мне кажется что решение от Mike Gorchak со сравниваем тайлов будет ммм несколько по проще )))

Подписаться на комментарии