Привет всем, дорогие читатели и форумчане!
Отличная идея начать выставлять тестовые задания для тех, кто хочет себя попробовать перед собеседованием. Начал эту темуЗдесь я выставлю только условие задания, в комментариях можно обсуждать алгоритм решения. Задание, как и водится, будет на английском.
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
Помогите, нужна мотивация!
Подписывайтесь на мой блог Паттерны Проектирования пишите в нем статьи!">
Мои попытки разбить задание на этапы и прийти к решению оказались безуспешными. Задачу-то, что сам сформулировал решил, а дальше куда идти не понимаю.
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. Если до этого не сталкивались с рекурсией — начните с простого (например, алгоритм поиска чисел Фибоначчи или подсчет факториала).
Необходимо найти в изображении последовательности из трех цифр и вывести их:
P.S. Понятно, что за 4 часа не получится уложиться, но решать возможно будет интересно.
Собственно кодирование «в лоб» заняло 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. Рисуем рамки областей и сохраняем итоговый файл.
Задание: Вписать три случайные клетки в решётке в один минимальный по размерам прямоугольник. Вывести на консоль координаты вершин одной из его диагонали.
Примечание: Координаты клетки 1: (2; 4), клетки 2: (4; 5), клетки 3: (3; 1).
P.S.
Искренне радуюсь за Himegа и остальных, кто быстро и верно находит нужные алгоритмы и реализует их программно. Молодцы!
Что касается примера простой задачи: да, может помочь. A cell is a pixel =) Главное — понять, каким образом определить отдельные скопления отличий.
Некоторые комментарии:
1. Вопреки тому, что я предположил в первом сообщении, массив соответствия можно не создавать.
2. Разница в 10% между пикселями действительно реализуется просто.
3. Обведение прямоугольником: при сравнении изображений создается список координат всех отличающихся пикселей. Рекурсивный метод находит координаты диагоналей всех прямоугольников, которыми нужно обводить отличающиеся области, и рисует их в файл. Если я хоть слово напишу дальше, то будет жёсткий спойлер))
А, да, чуть не забыл про JUnit тесты))))))))))
с 10% отклонением — просто, а вот обведение области прямоугольником я даже не думал, что будут сложности, пока не попробовал реализовать.
по итогу, загнал все отличающиеся пиксели в список и потом перебирал его, попутно создавая новый список в который уже помещались области и ними же сравнивал пиксели.