1 added
1 removed
Original
2026-01-01
Modified
2026-02-26
1
<p><strong>В этой статье я расскажу об одном своем интересном проекте, который решал проблему, решение которой до сих пор не найдено.</strong></p>
1
<p><strong>В этой статье я расскажу об одном своем интересном проекте, который решал проблему, решение которой до сих пор не найдено.</strong></p>
2
<p>Однажды по воле случая мне пришлось написать проект, который бы по фотографируемым предметам на столе и белому листу, на котором начерчен многоугольник, выдавал ответ на вопрос о том, можно ли уместить эти предметы в нарисованный многоугольник.</p>
2
<p>Однажды по воле случая мне пришлось написать проект, который бы по фотографируемым предметам на столе и белому листу, на котором начерчен многоугольник, выдавал ответ на вопрос о том, можно ли уместить эти предметы в нарисованный многоугольник.</p>
3
-
<p>Для решения данной проблемы мной выбран был язык Python, как наиболее удобный и гибкий, по моему мнению, для данной области (компьютерное зрение).</p>
3
+
<p>Для решения данной проблемы мной выбран был язык Python, как наиболее удобны�� и гибкий, по моему мнению, для данной области (компьютерное зрение).</p>
4
<p>Самый первый модуль был "preprocessing.py", в нем я делал предобработку изображения, чтобы в дальнейшем можно было выделить контуры предметов и многоугольника, чем и будет заниматься "recognizing.py". Подробно на этих модулях останавливаться не буду, поскольку в большей степени в рассказе были бы термины из области компьютерного зрения, что не привносило бы красоты в статью. В общих чертах - использовалась библиотека OpenCV, с помощью которой и выполнялась основная работа в этих двух модулях: убирались шумы и применялись различные фильтры.</p>
4
<p>Самый первый модуль был "preprocessing.py", в нем я делал предобработку изображения, чтобы в дальнейшем можно было выделить контуры предметов и многоугольника, чем и будет заниматься "recognizing.py". Подробно на этих модулях останавливаться не буду, поскольку в большей степени в рассказе были бы термины из области компьютерного зрения, что не привносило бы красоты в статью. В общих чертах - использовалась библиотека OpenCV, с помощью которой и выполнялась основная работа в этих двух модулях: убирались шумы и применялись различные фильтры.</p>
5
<p>Главный механизм этой работы - это каким же образом понять, можно ли разместить предметы в многоугольник? Самая первая идея, которая мне пришла - это банальный перебор всех возможных углов и положений на листе, что было отброшено почти сразу, ибо это неоптимизированно, и любые сервера крупных компаний отказались бы высчитывать такие данные. Поэтому была придумана идея, основанная на минимизации некоторой функции, которая позволяла бы не только сказать, можно ли разместить предметы, но и показала бы, каким образом. И была придумана такая "штуковина":</p>
5
<p>Главный механизм этой работы - это каким же образом понять, можно ли разместить предметы в многоугольник? Самая первая идея, которая мне пришла - это банальный перебор всех возможных углов и положений на листе, что было отброшено почти сразу, ибо это неоптимизированно, и любые сервера крупных компаний отказались бы высчитывать такие данные. Поэтому была придумана идея, основанная на минимизации некоторой функции, которая позволяла бы не только сказать, можно ли разместить предметы, но и показала бы, каким образом. И была придумана такая "штуковина":</p>
6
<p>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</p>
6
<p>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</p>
7
<p>Разберем подробно. На вход функции поступают два аргумента: многоугольник и предмет в виде контуров, что, в свою очередь, является просто набором координат. Для минимизации этой функции использовался алгоритм дифференциальной эволюции. Почему не какой-нибудь стандартный, типа градиентного и других? Потому что на тот момент сложно было судить о характере функции, но точно было известно, что существует много локальных минимумов и не всегда один глобальный минимум. Кроме того, функция недифференцируема. Очень кратко про метод дифференциальной эволюции - он использует различные идеи генетических алгоритмов, но со своими усовершенствованиями.</p>
7
<p>Разберем подробно. На вход функции поступают два аргумента: многоугольник и предмет в виде контуров, что, в свою очередь, является просто набором координат. Для минимизации этой функции использовался алгоритм дифференциальной эволюции. Почему не какой-нибудь стандартный, типа градиентного и других? Потому что на тот момент сложно было судить о характере функции, но точно было известно, что существует много локальных минимумов и не всегда один глобальный минимум. Кроме того, функция недифференцируема. Очень кратко про метод дифференциальной эволюции - он использует различные идеи генетических алгоритмов, но со своими усовершенствованиями.</p>
8
<p>Вернемся к функции. Для алгоритма необходимо указать границы, в пределах которых мы ищем оптимальную позицию. Я особо думать не стал и взял просто границы многоугольника (замечу, что перед поиском оптимальных позиций я совмещал центры предмета и многоугольника). Теперь непосредственно о том, что минимизировалось. А минимизировалось три слагаемых:</p>
8
<p>Вернемся к функции. Для алгоритма необходимо указать границы, в пределах которых мы ищем оптимальную позицию. Я особо думать не стал и взял просто границы многоугольника (замечу, что перед поиском оптимальных позиций я совмещал центры предмета и многоугольника). Теперь непосредственно о том, что минимизировалось. А минимизировалось три слагаемых:</p>
9
<ol><li>Число точек, находящихся на расстоянии меньше MAX_DISTANCE. Чем больше, тем плотнее к границе</li>
9
<ol><li>Число точек, находящихся на расстоянии меньше MAX_DISTANCE. Чем больше, тем плотнее к границе</li>
10
<li>Площадь пересечения многоугольника и предмета. Сделано, чтобы в результате преобразований оставались внутри многоугольника или хотя бы не отдалялись от него</li>
10
<li>Площадь пересечения многоугольника и предмета. Сделано, чтобы в результате преобразований оставались внутри многоугольника или хотя бы не отдалялись от него</li>
11
<li>Расстояние между центрами многоугольника и предмета. Так я пытался дополнительно усилить уплотнение к границе и заполнять пропуски в многоугольнике</li>
11
<li>Расстояние между центрами многоугольника и предмета. Так я пытался дополнительно усилить уплотнение к границе и заполнять пропуски в многоугольнике</li>
12
</ol><p>Однако метод дифференциальной эволюции использовал эвристику, поэтому приходилось запускать поиск оптимальной позиции несколько раз и из всех уже выбрать наилучшую.</p>
12
</ol><p>Однако метод дифференциальной эволюции использовал эвристику, поэтому приходилось запускать поиск оптимальной позиции несколько раз и из всех уже выбрать наилучшую.</p>
13
<p>Вот примерно так решалась задача. Все исходники можно посмотреть в<a>репозитории</a>.</p>
13
<p>Вот примерно так решалась задача. Все исходники можно посмотреть в<a>репозитории</a>.</p>