by bolshakova anna, group 5030102/90401

Требуется создать “Intelligent Placer”:

Подается фотография, на который отчетливо видно:

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

Необходимо : узнать, можно ли расположить одновременно все эти предметы на плоскости так, чтобы они влезли в этот многоугольник, при этом не пересекаясь (предполагается, что программа сможет создавать бинарные маски-контуры предметов, которые при размещении в многоугольники не будут накладываться друг на друга)

“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”) 

Входные данные: строка - путь к фотографии - фото допустимого формата (см. требования)

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

1. допустимые форматы - png / jpg / jpeg
2. камера как можно более параллельна плоскости листа, чтобы минимизировать искажение перспективы
3. освещение непосредственно над плоскостью съемки
4. четкие фото, тень от объектов минимальна
5. на входных фотографиях предметы отличимы от поверхности. (предметы темнее поверхности, на которой находятся)
6. на эталонных фотографиях предметы находятся на белом листе А4.

1. объекты не пересекаются (видно некотую область с текстурой поверхности между ними)
2. объекты не выходят за границы кадра
3. объекты сложной формы фотографируются с единственного ракурса
4. лист располагается слева, предметы справа
5. На фото 1 объект присутсвует 1 раз

1. многоугольник, имеющий от 3 до 15 вершин
2. нарисован черным маркером / ручкой

1. адаптер
2. карта
3. перо
4. ножницы
5. гильза
6. маркер
7. заколка
8. когтерезка
9. монета
10. кейс

поверхность

1. 1 помещаемый объект -> true
2. 2 объекта, помещается 1 -> false
3. 2 объекта, помещается 2 -> true
4. 2 объкта, оба одновременно не помещаются -> false
5. 1 непомещаемый объект -> false
6. несколько помещаемых объектов -> true
7. еще несколько помещаемых объектов -> true
8. ни один из обхектов не поместился -> false
9. нет многоугольника -> false
10. пример со всеми 10 предметами, все помещаются -> true

1. Этап предобработки.
   • Перевод изображения в ч/б
   • Предобработка изображения:
     • Применение Алгоритма Кэнни
     • Последовательное использование морфологических операций:
       • binary closing с последующей коррекцией краев получившейся маски
       • запосление пустот в полученной маске
   • Теперь, когда есть бинарная маска изображения, можно приступить к выделению многоугольника и объектов:
     • Сначала удалим объекты, площадь которой считается незначительной относительно площади объектов и многоугольника, используя морфологическую операцию remove_small_objects
     • Выделим компоненты связности из получившейся маски с помощью label из skimage.measure
     • Находим многоугольник как самый левый компонент связности (из постановки), удаляем его из списка компонент
     • Оставшиеся компоненты связности возвращаются как объекты
     • Объекты сортируются по убыванию площади
   • Создание бинарных масок предметов
     • Первым делом, имеет смысл уменьшить все изображения получившихся бинарных масок. Информация о форме и о соотношении размеров объектов/многоугольника не потеряется, но потенциально уменьшится время последующих вычислений за счет уменьшения размера матриц.
     • Для изображений предметов применим морфогоческую операцию - эрозию - с малой квадратной матрицей 5x5, поскольку из-за теней на входящем изображении возможна ситуация, что распознанные границы предметов немного больше действительных.
2. Размещение
   • Если суммарная площадь объектов больше площади многоугольника, выход с результатом False
   • Если существует объект, расстояние между 2мя крайними точками которого больше расстояния между 2мя крайними точками многоугольника, выход с результатом False
   • Для каждого объекта:
     • Если площадь объекта больше площади свободной области (для первого объекта свободной областью считается сам многоугольник), то выход с результатом False
     • Итерации размещения:
       • Для каждой конфигурации поворота вычисленной с определенным шагом:
         • Добавление подложки размера, равным размеру свободной области, таким образом, что объект расположен слева-снизу
         • Начиная с нижнего левого угла, 'протаскиваем' с заданным шагом объект. Этот сдвиг реализован с помощью геометрической трансформации (наиболее быстрый способ). Сдвиг изображения происходит в направлении вектора. Изменения размера изображения не происходит. Пустота заполняется черным фоном (значением False). Если при сдвиге объект начал выходить на пределы подложки, выходим из цикла и рассматриваем следующее размещение.
           • Проверяем конфигурацию на то, можно ли разместить объект в свободной пространстве с следующим образом: Если ЛОГИЧЕСКОЕ_"И"(объект, НЕсвободное_пространство) содержит в себе True, то объект не вложен в свободное пространство, а следовательно, текущее размещение некорректно; иначе текущее размещение подходит и считается корректным.
           • Если найдено корректное расположение объекта, то 'вырезаем' из свободного пространства место, занятое объектом с помощью операции "XOR"(объект, свободное_пространство). Возврат с текущей итерации размещения с результатом True.
       • Если не было найдено размещение, возврат с результатом False.