В этой статье я расскажу об одном своем интересном проекте, который решал проблему, решение которой до сих пор не найдено.
Однажды по воле случая мне пришлось написать проект, который бы по фотографируемым предметам на столе и белому листу, на котором начерчен многоугольник, выдавал ответ на вопрос о том, можно ли уместить эти предметы в нарисованный многоугольник.
Для решения данной проблемы мной выбран был язык Python, как наиболее удобный и гибкий, по моему мнению, для данной области (компьютерное зрение).
Самый первый модуль был «preprocessing.py», в нем я делал предобработку изображения, чтобы в дальнейшем можно было выделить контуры предметов и многоугольника, чем и будет заниматься «recognizing.py». Подробно на этих модулях останавливаться не буду, поскольку в большей степени в рассказе были бы термины из области компьютерного зрения, что не привносило бы красоты в статью. В общих чертах — использовалась библиотека OpenCV, с помощью которой и выполнялась основная работа в этих двух модулях: убирались шумы и применялись различные фильтры.
Главный механизм этой работы — это каким же образом понять, можно ли разместить предметы в многоугольник? Самая первая идея, которая мне пришла — это банальный перебор всех возможных углов и положений на листе, что было отброшено почти сразу, ибо это неоптимизированно, и любые сервера крупных компаний отказались бы высчитывать такие данные. Поэтому была придумана идея, основанная на минимизации некоторой функции, которая позволяла бы не только сказать, можно ли разместить предметы, но и показала бы, каким образом. И была придумана такая «штуковина»:
def get_optimal_position(polygon : Polygon, thing: Polygon) -> tuple[float, float, float, float]:
def f(args):
rot, xoff, yoff = args
transformed_thing = rotate(translate(thing, xoff=xoff, yoff=yoff), rot)
distances = distance_between_contours(polygon, transformed_thing)
thing_xc, thing_yc = transformed_thing.centroid.coords.xy
poly_xc, poly_yc = polygon.centroid.coords.xy
return -count_points(distances, MAX_DISTANCE_TO_BORDER) - polygon.intersection(transformed_thing).area - euclidean((poly_xc[0], poly_yc[0]), (thing_xc[0], thing_yc[0]))
minx, miny, maxx, maxy = map(int, polygon.bounds)
w = maxx - minx
h = maxy - miny
result = scipy.optimize.differential_evolution(f, bounds=((0, 360), (-w, w), (-h, h)))
rot, xoff, yoff = result.x
fopt = result.fun
return rot, xoff, yoff, fopt
Разберем подробно. На вход функции поступают два аргумента: многоугольник и предмет в виде контуров, что, в свою очередь, является просто набором координат. Для минимизации этой функции использовался алгоритм дифференциальной эволюции. Почему не какой-нибудь стандартный, типа градиентного и других? Потому что на тот момент сложно было судить о характере функции, но точно было известно, что существует много локальных минимумов и не всегда один глобальный минимум. Кроме того, функция недифференцируема. Очень кратко про метод дифференциальной эволюции — он использует различные идеи генетических алгоритмов, но со своими усовершенствованиями.
Вернемся к функции. Для алгоритма необходимо указать границы, в пределах которых мы ищем оптимальную позицию. Я особо думать не стал и взял просто границы многоугольника (замечу, что перед поиском оптимальных позиций я совмещал центры предмета и многоугольника). Теперь непосредственно о том, что минимизировалось. А минимизировалось три слагаемых:
- Число точек, находящихся на расстоянии меньше MAX_DISTANCE. Чем больше, тем плотнее к границе
- Площадь пересечения многоугольника и предмета. Сделано, чтобы в результате преобразований оставались внутри многоугольника или хотя бы не отдалялись от него
- Расстояние между центрами многоугольника и предмета. Так я пытался дополнительно усилить уплотнение к границе и заполнять пропуски в многоугольнике
Однако метод дифференциальной эволюции использовал эвристику, поэтому приходилось запускать поиск оптимальной позиции несколько раз и из всех уже выбрать наилучшую.
Вот примерно так решалась задача. Все исходники можно посмотреть в репозитории.
