Требуется создать “Intelligent Placer”: по поданной на вход фотографии нескольких предметов на светлой горизонтальной поверхности и многоугольнику понимать, можно ли расположить одновременно все эти предметы на плоскости так, чтобы они влезли в этот многоугольник. Предметы и горизонтальная поверхность, которые могут оказаться на фотографии, заранее известны. Также известна сторона с которой фотографируется предмет (например, флешка располагается логатипом наверх, автокарандаш зажимом слева при пишущей части вверх на фотографии). Многоугольник задается фигурой, нарисованной темным маркером на белом листе бумаги, сфотографированной вместе с предметами. “Intelligent Placer” должен быть оформлен в виде python-библиотеки intelligent_placer_lib, которая поставляется каталогом intelligent_placer_lib с файлом intelligent_placer.py, содержащим функцию - точку входа

def check_image(<path_to_png_jpg_image_on_local_computer>[, <poligon_coordinates>])

которая возвращает True если предметы могут влезть в многоугольник, иначе False. То есть так, чтобы работал код:

from intelligent_placer_lib import intelligent_placer
def test_intelligent_placer():
	assert intelligent_placer.check_image(“/path/to/my/image.png”)

Также требуется воспроизводимый intelligent_placer.ipynb, содержащий репрезентативные примеры работы алгоритма с оценками качества его работы и их визуализацией.

• Допустимое разрешение входных фотографий: не менее 2048х1536*;
• Соотношение сторон фотографии 4х3, ориентация - документ*;
• Высота съемки: не менее 40 см (в общем случае - достаточная для размещения листа А4 и некоторого количества предметов);
• Расположение источника света и камеры: так чтобы добиться минимальных теней от предметов при съемке сверху (с отклонением камеры не более, чем на 15 градусов от вертикали) и при этом избежать тени от самой камеры;
• Степень размытости фотографии: фотография должна быть максимально чёткой для беззатруднительного зрительного определения границ предметов
• Допустимые форматы фотографий: png, jpg;
• Размещение листа с многоугольником: ориентация - документ, самая длинная сторона - приблизительно вертикально относительно фотографии;
• Размещение предметов: вне листа с многоугольником, без перекрытия, с интервалом ~ 2см между предметами;
• Параметры многоугольника: нарисован тёмным маркером на белом листе формата А4 (толщина линии 2-3мм), количество вершин - не более 10;
• Параметры фона: предмет (покрытие) сплошного светлого (близкого к белому) цвета;
• Дополнительно:
  • Несколько экземпляров одного предмета не допускаются;
  • Во избежание возникновения теней рекомендуется воспользоваться несколькими источниками света;

*Эти требование могут изменится в дальнейшем на более мягкие

True если предметы могут быть размещены в многоугольнике без наложений, иначе False

1. Задача определения многоугольника
2. Задача определения предмета
3. Задача укладки (иными словами, наиболее эффективное с точки зрения постановки задачи расположение предметов в многоугольнике)

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

True

3 предмета, помещающихся в заданный невыпуклый многоугольник

False

2 предмета, непомещающийся в заданный многоугольник

True

2 предмета, помещающихся в заданный невыпуклый многоугольник

True

Тривиальный пример, 1 предмет, помещающийся в область

True

4 предмета, помещающихся в область

True

Крайний случай 10 предметов

True

Крайний случай 10-угольник

False

Крайний случай - 0 предметов

True

Вариант "стыковки" предметов

True

Крайний случай - треугольник

Работа над проектом разделена на следующие этапы:

• Выделение структурных элементов - многоугольника и объектов
  • Выделение элементов происходит с помощью алгоритма Кэни.
  • На этом этапе не ясно, какой из элементов является многоугольником, а какой - объектом.
• Разделение объектов и многоугольника в соответсвтующие контейнеры;
  • Разделение происходит по следующему принципу - черно-белый фрагмент фотографии, доминирующий цвет которого наиболее близок к белому, является многоугольником, остальные - объекты.
• Представление объектов и прямоугольника в виде бинарной маски:
• Применение алгоритма бинаризации триангуляции
• Применение морфологических операций для избавления от лишних фрагментов
• Выделение фрагмента с наибольшей площадью как объекта
• Уточнение границ многоугольника (например, с помощью морфологических операций);
• Размещение объектов внутри многоугольника:
  • На вход функции размещения поступают отсортированные по пллощади маски объектов и маска многоугольника;
  • Объекты добавляются в порядке убывания площадей стараясь добиться максимально плотного замощения. Т.е. объекты распределяются вдоль границ области - оптимальным считается вариант оставляющий максимальную по площади связную область. После чего занятая область "вырезается" из многоугольника и процесс повторяется.
  • Далее проводится проверка:
    • Если удалось разместить все предметы, то сохраняется и выводится соответсвтующее изображение;
    • Иначе - запоминается площадь покрытия, переход к другому порядку объектов;
    • В случае невозможности размещения никакого из объктов возвращается пустая маска многоугольника.
  • Для оптимизации перебора производится предварительное сжатие масок как объектов, так и многоугольника. Также рассматривается перебор углов с шагом 5 градусов.
• Вывод результатов;
  • Вывод производится в фигуру, поставляемую matplotlib, так как с ее помощью возможна удобная работа с получившимся изображением и последующее его сохранение.