• ,

Тестовое задание "Image Comparison"

Привет всем, дорогие читатели и форумчане!

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

Image Comparison Requirements
Write a program in Java that compares any 2 images and shows the differences visually. Remember that Working Software is the main value, so something simple that works is generally better than a complex unfinished solution.

Must have
  • Implementation should use only standard core language and platform features, no 3rd party libraries and plagiarized code is permitted.
  • Pixels (with the same coordinates in two images) can be visually similar, but have different values of RGB. We should only consider 2 pixels to be «different» if the difference between them is more than 10%.
  • The output of the comparison should be a copy of one of the images image with differences outlined with red rectangles as shown below.
  • We need to see your own code. No third party libraries and borrowed code is allowed.
  • Target completion time is 2 hours, but you may choose to use up to 4 hours. Submissions sent after 4 hours will be disqualified. Note that in addition to quality, time is also factored into scoring the task. The closer you get to 2 hours the higher is the score.



Nice to have
  • It should be possible to exclude certain parts of the image from comparison, for example a clock or dynamically generated number. They will be provided by the caller as a list of rectangles to exclude.
  • Provide some sort of UI either as a web page or GUI that allows the user to select the images and view differences as an overlay on either of the images.
Expected Deliverables
  • Source code.
  • Binary version of the algorithm that runs and produces output of comparison. No build should be required.
  • Output image showing the result of comparison.
Tips and Hints
  • Use javax.imageio.ImageIO to read/write images.
  • Consider java.awt.image.BufferedImage#createGraphics() to draw on in-memory images.


От себя хочу добавить, что хорошим тоном будет еще написать JUnit тесты для всего этого добра. Для этого нужно будет использовать какую-то систему сборки проектов Ant/Maven/Gradle чтобы подтянуть либу для JUnit.

Ставим "+" на статье, если была полезна. Решаем ее, прокачиваем свои скиллы. Она попадалась у меня в двух компаниях!

См. также мои другие статьи:
Тестовое задание: «Написать Интерпретатор на язык BrainFuck»
Тестовое задание «Image Comparison»
Java — быстрее, сильнее и выше! Зарплаты украинских программистов.
История успеха спустя 1.5 года от начала обучения
Технические вопросы на собеседовании.
Как найти работу? Рассылка резюме
Профессиональное выгорание. Как устоять?
Английский для IT и для собеседования
Паттерн Command своими словами.
Паттерн Singleton своими словами.
Как создать исполняемый jar в Intellij IDEA / how to create jar in IDEA
Помогите, нужна мотивация!

Подписывайтесь на мой блог Паттерны Проектирования пишите в нем статьи!">

29 комментариев

Himeg
  • Himeg
  • 0
  • Комментарий отредактирован 2017-02-03 00:05:52 пользователем Himeg
… создать массив[][], в который записать результат соответствия/несоответствия пикселей двух источников. Получится что-то типа поля игры морской бой с расставленными «кораблями»-несоответствиями. Далее в массиве вписать каждый «корабль» в прямоугольник (меняя значения в массиве соответствующим образом). Далее искать в массиве все значения, относящиеся к прямоугольникам, и вносить соответствующие изменения в image (на этом мой 14 уровень на Javarush падает без чувств)
Himeg
Хотя можно проще: при первичном заполнении вычислять координаты диагоналей прямоугольников, а потом по этим данным рисовать их на результирующем изображении.
Roman_kh
выбрать массив несоответствия не составляет труда.
а что дальше?
1. более 10% отличии
2. обрисовка разниц.
Himeg
Ну вот тут уже надо код писать, чтобы прокомментировать конкретнее реализацию 10% разницы и вписывания отличающихся областей в прямоугольники. Если будет возможность вникнуть, не на что не отвлекаясь, попробую.
Joysi
  • Joysi
  • +3
  • Комментарий отредактирован 2017-02-03 13:13:23 пользователем Joysi
Можете использовать как болванку…

Когда то ради интереса пробовал работать с картинками в консоли (грузить изображение, модифицировать и записывать) без использования 3rd libraries, если кому интересно:
info.javarush.ru/Joysi/2016/02/20/World-of-Bytes-1-%D0%A0%D0%B0%D0%B1%D0%BE%D1%82%D0%B0-%D1%81-%D0%B8%D0%B7%D0%BE%D0%B1%D1%80%D0%B0%D0%B6%D0%B5%D0%BD%D0%B8%D1%8F%D0%BC%D0%B8-.html
Fry
  • Fry
  • 0
оо, делал когдато такое. суть решения маркировать области где не совпадают пиксели (дистанция больше 10%) а потом уже по областях рисовать квадратики. Помню на решение потратил около 2- ух часов. Не оптимально было, но работает. Области искал рекурсивным обходом писклей от первого найденного. Кому интересно, могу дать решение.
JuriMik
Интересно, т.к. с квадратиками так и не разобрался
Cargeh
Тоже прошу скинуть.
Roman_kh
Не давай решение… Это ведмежья услуга
Fry
  • Fry
  • 0
  • Комментарий отредактирован 2017-02-04 16:38:36 пользователем Fry
Сюда выкладывать не буду, в личку напишите скину. Но думаю что такое задание ближе уже к мидлу.
JuriMik
да, я делал как раз на позицию миддла
JuriMik
  • JuriMik
  • 0
  • Комментарий отредактирован 2017-02-03 21:19:47 пользователем JuriMik
Делал такое. Правда время ограничено было двумя часами, я не уложился, поэтому с рисованием квадратиков не срослось и я просто подсвечивал область, где были отличия, красным.
Fry
просто выделить область не самое хорошее решение, и довольно простое. С квадратиками там самая сила
Torin
У меня просьба ко всем не выкладывать пока решение, а договориться и выкатить в один день всем вместе. Просто у меня не всегда есть 3-4 часа сосредоточенно кодинга
alexeyfrei
мде… я справился за 4 часа и 8 минут :/ без всяких гуи и юнит тестов, правда. но это от того, что я еще понятия не имею про гуи и юнит тесты, так что на это у меня неделя бы ушла.
с 10% отклонением — просто, а вот обведение области прямоугольником я даже не думал, что будут сложности, пока не попробовал реализовать.
по итогу, загнал все отличающиеся пиксели в список и потом перебирал его, попутно создавая новый список в который уже помещались области и ними же сравнивал пиксели.
Himeg
  • Himeg
  • +2
  • Комментарий отредактирован 2017-02-05 22:21:45 пользователем Himeg
Заняло более четырех часов, но, тем не менее, получилось.
Некоторые комментарии:
1. Вопреки тому, что я предположил в первом сообщении, массив соответствия можно не создавать.
2. Разница в 10% между пикселями действительно реализуется просто.
3. Обведение прямоугольником: при сравнении изображений создается список координат всех отличающихся пикселей. Рекурсивный метод находит координаты диагоналей всех прямоугольников, которыми нужно обводить отличающиеся области, и рисует их в файл. Если я хоть слово напишу дальше, то будет жёсткий спойлер))

А, да, чуть не забыл про JUnit тесты))))))))))
Roman_kh
  • Roman_kh
  • 0
  • Комментарий отредактирован 2017-02-06 00:05:50 пользователем Roman_kh
А случай, когла разрывная картинка, но близко друг к другу.(буквы рядом а обволится целиком слово)?
Himeg
Задается минимальное расстояние, в пределах которого различия считаются одним множеством различий. Если взять исходные изображения из задания, то вывод соответствует тому, что должно быть:
Javin
А не поможет ли решение этой более простой задачи в создании одного из алгоритмов для тестового задания от «Image Comparison»?

Задание: Вписать три случайные клетки в решётке в один минимальный по размерам прямоугольник. Вывести на консоль координаты вершин одной из его диагонали.
Примечание: Координаты клетки 1: (2; 4), клетки 2: (4; 5), клетки 3: (3; 1).

P.S.
Искренне радуюсь за Himegа и остальных, кто быстро и верно находит нужные алгоритмы и реализует их программно. Молодцы!
Himeg
  • Himeg
  • 0
  • Комментарий отредактирован 2017-02-06 23:13:04 пользователем Himeg
Javin, спасибо за искренность, это редкое качество)
Что касается примера простой задачи: да, может помочь. A cell is a pixel =) Главное — понять, каким образом определить отдельные скопления отличий.
FarRenGate
Добил-таки задание, ушло явно больше 4 часов, но вроде работает как положено. Хорошая задачка, решал с интересом. Поиск различных пикселей занял совсем немного усилий, вот над квадратиками чуть мозги не вскипели
Joysi
Интересная задачка, тоже решил поалгоритмичать :)
Собственно кодирование «в лоб» заняло 1.5 часа(правда я до этого умел работать с изображениями и не тратил времени на эту часть). Далее не понравился выход:

Хотелось следующего:


Дополнительные штрихи с выделениями областей + «макияж» кода (вынес из функций все захардкоженные цифры/строки в блок констант, ввел начальную валидацию, сделал небольшую обработку ошибок, комментарии и JavaDoc описание функций) довели общее время до почти двух с половиной часов.

UI не делал, сделал консольную утилиту, где в параметрах командной строки задаются имена 2х выходных файлов и выходного с выделенными областями. JUnit тоже не стал прикручивать (с ним добавился бы час-полтора, так как придется для тестов генерировать различные массивы с областями, создавать моки для анализа вывода в консоль и т.п.).

Общая схема была такая:
1. Валидация
2. Ищем пиксели, отличные в 2х картинках (вынес в отдельный массив, в отличии Himeg так как при работе было удобно маркировать элемент массива a значениями трех категорий:
a=0 — точки в двух изображениях не отличаются в рамках допущения
a=-1 — точка отличается, но в данный момент не приписана никакой области
a>0 — точка приписана области a (где a=1,2....) )
3. Строим области
4. Раздвигаем границы областей
5. Схлопываем пересеченные области
6. Рисуем рамки областей и сохраняем итоговый файл.
Joysi
  • Joysi
  • 0
  • Комментарий отредактирован 2017-02-08 10:32:57 пользователем Joysi
Может немного усложним задачу?
Необходимо найти в изображении последовательности из трех цифр и вывести их:
P.S. Понятно, что за 4 часа не получится уложиться, но решать возможно будет интересно.
Javin
  • Javin
  • 0
  • Комментарий отредактирован 2017-02-11 12:24:49 пользователем Javin
Просьба к тем, кто решил тестовое задание разбить свои решения на этапы и сформулировать промежуточные задачи, которые привели бы и остальных к пониманию алгоритмов и их реализации. Просто выложить решение, конечно, — проще, но учитывая специфику сайта и взаимопомощь участников форума, хотелось бы не просто ознакомиться с решениями…
Мои попытки разбить задание на этапы и прийти к решению оказались безуспешными. Задачу-то, что сам сформулировал решил, а дальше куда идти не понимаю.
Joysi
Ну если бы я был учителем, то по данной задаче сформулировал бы так:

1) Техника: Учимся считывать файл изображения с диска, менять его (допустим нарисовать в его центре рамку) и записать на диск под другим именем. Ссылку на пример кода можно найти в моем ответе выше в данном топике.

2) Поиск пикселов, отличающихся друг от друга на 10%.
Дано: Изображение 1 формата NxM, Изображение 2 формата NxM
Задача: сформировать двумерный массив NxM элементов типа int, каждый элемент (i,j):
— Равен 0, если все Red/Green/Blue составляющие пикселя (i,j) изображения 1, не отличаются от Red/Green/Blue составляющих элемента по тем же координатам изображения2.
— Равен -1, в противном случае

3) Поиск областей. 2 точки (x1,y1) и (x2,y2) считаем соседними, если: |x1-x2|<=1 и |y1-y2|<=1 (то есть вокруг каждой точки может быть максимум 8 соседних (у граничных точек изображения меньше). Собственно задача:
Пробежаться по сформированному на шаге 2 двумерному массиву и для всех его элементов = -1, выставить номер области >0 по принципу, что все точки одной области должны быть соседними. Как вариант, можно использовать рекурсию, то есть сделать функцию маркирующую область и для каждой соседней точки вызывать ее из самой себя.
Область проще задать как класс с полями: номер области, координаты верхнего левого угла, координаты нижнего правого угла.

Самое трудное этап — 3. Если до этого не сталкивались с рекурсией — начните с простого (например, алгоритм поиска чисел Фибоначчи или подсчет факториала).
dollarali
Спасибо! По этому алгоритму решил задачу!
FutureSenior
друзья!
Помогите, не понимаю как это сделать… Может кто-то объяснить? В лс, если никто не хочет видеть.
Artem_Novikov
2 часа? да у меня бы 2 недели заняло
Gnoemes
Ура!
Смог реализовать, правда на это ушло около 10 часов (пока даже не джуниор).
Больше всего времени потратил на рекурсивный алгоритм расширения областей (около 5-6 часов).
Остальное же время ушло создание более менее не убого GUI и ввод/вывод. Оставлю ссылку на репозиторий, а результат вот:
Только зарегистрированные и авторизованные пользователи могут оставлять комментарии.