Распознавание типа нарисованной двумерной фигуры (Figure Recognition)

...какие библиотеки...

Не факт, что они вообще были.

Навеяло, как я однажды выполнял реверс одной программы. Едва ли не впервые в жизни. 😗

Не нужны там никакие библиотеки, местами просто математика, местами просто смекалка. Скорее всего, программа сама по себе.

Надо записать на потом, идея прикольная, можно запилить, поэкспериментировав.

Часто логика работы программы, и идеи лежащие в основе транзита ввод->результат видно буквально глазами или по косвенным признакам. Конкретно эту программу отреверсить можно буквально по скриншоту.

Скорее всего, на холсте одновременно рисуется два слоя, первый произвольный корявый, а второй из прямых/кривых линий (в зависимости от динамики рисования) первый мы видим, а по второму программа определяет фигуру. Например если рисуя линию я резко меняю направление движения «карандаша» это легко заметить и сформировать в этом месте точку от которой идёт другая невидимая линия. А далее просто игнорируем маленькие ломанные линии, и смотрим на углы пересечения и их количество с учётом некой погрешности + отношения углов друг к другу, по итоговому результату можно просто из таблички брать имя фигуры =)

Всё, я отреверсил. Теперь осталась нудятина, записать эти мысли в код, попутно додумывая детали.

Для полноты картины можно ещё сломать алгоритм, чтобы программа не смогла определить фигуру, если посмотреть на это в картинке, то это будет тоже самое что прочитать исходники, через строчку.

Причем тут linux?

Может определить трапецию или овал, повёрнутые на 15% градусов?

Не точно. Этот нарисованый ромб еще и квадрат. Ну еще конечно прямоугольник, четырехугольник, и, в зависимости от того, как определить, трапеция.

Если он определяет только в одной позиции, то можно взять простейший алгоритм заливки с дырами, заливать и смотреть по соотношению залитой площади и общей.
Вполне возможно что эвристика вообще без заливки работает, просто отношение линии к площади прямоугольника параллельного осям в который вписана фигура.

Надо переводить пространство x,y в пространство целевой фигуры. Для окружностей всё очевидно - Hough transform, который в opengl есть. Для остальных должно быть тоже из этой категории. Или можно тупо искать углы каким-нибудь Харрисом, и потом определять по изображению, какие углы соединены. Дальше просто проходишься по всем множествам соединённых углов, и считаешь, кто из них кто (треугольник, квадрат и проч.)

Странные, в заголовке окна «demo for reuniongalaxy.com» указано а в about затёрто.

Нет там никаких библиотек, конечно. А алгоритм скорее всего сначала попытка распознать прямые линии (можно на основе МНК, проходят на 1 курсе если ты не гуманитарий), а потом по их координатам уже совсем элементарно.

а в about затёрто.

Видимо не уместилось, char buff[размер] выделили меньше чем для заголовка окна

Вы же мышкой прямо в окне программы водите?

Тогда это 99% т.н. online-распознавание по вектору, который вы ведёте. Это совсем простенькая задача в сравнении с обработкой растра (offline-распознавание). Никакие особенные библиотеки для этого не нужны.

Вопрос: как узнать какие библиотеки использовались (opencv?). Или с пом. какого алгоритма это было сделано?

геометрия за 6-8 класс, скорее всего.

еще можно деревья или таблицы решений задействовать для примитивной экспертной системы. читай Лео Броуди «Thinking Forth» про структурное программирование (да, на форте) и таблицы решений либо Таунсенда и Фогхта, например.

рисуешь примерно фигуру и она определяет ее тип

единственные сложности кажутся в слове «примерно».

ну что ж, вот тебе пример с нечеткой логикой:

1. посчитай попиксельно площади нарисованных фигур

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

3. да, возможны неоднозначности которые как-то надо устранять. или проблема k-средних. проще всего спросить у пользователя что именно он нарисовал и дообучать базу знаний если сильно большие отличия.

Вопрос: как узнать какие библиотеки использовались (opencv?).

современная молодежь что, без готовых фреймворков, библиотек и ч0рных ящиков типа того же opencv совсем не в состоянии самостоятельно придумать никакой адекватный поисковый эвристический алгоритм? или более-менее точный строгий аналитический?

а чему же вы тогда там учились?

Раскопал у себя на старом компьютере давно скачанный exe-шник

лучше бы ты исходники раскопал.

попробуй натравить декомпиляторы чтобы понять каким конпелятором это конпелировалось, еще посмотри зависимости стандартных рантаймов чтобы определить язык и средства разработки. или IDA/Ghydra. но надо знать ассемблер, да.
вряд ли там дельфи, скорее всего, MFC.

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

2. перебирай все известные формулы площадей этих фигур в деревьях решений и смотри какая с максимальной точностью подойдет

Threshold похоже настраивает приблизительную точность, погрешность в вычислениях площадей по разным методам: 1)подсчет внутри фигуры или методу монте-карло, но не стоит заморачиваться 2) по известной формуле

то есть, может использоваться как %погрешности для классификатора k-means.

как узнать какие библиотеки использовались

определи динамическая или статическая линковка.

натрави strings и ищи по сигнатурам известных функций этой библиотеки.

тоже касаемо рантаймов известных конпеляторов.

ntldd опять же. или утилиты руссиновича.

ну и декомпиляторы и IDA/Ghydra или хотя бы HIEW/BIEW, посмотри ими.

Вы же мышкой прямо в окне программы водите?

Да. Рисую пока не отпущена клавиша мыши. После того как отпускаю клавишу мыши, появл. красный контур и MessageBox

Найди граничные случаи. Насколько надо исказить фигуру, чтобы человек ещё считывал её, а прога уже нет.

Ещё можно попытаться постепенно превращать одну фигуру в другую и смотреть когда программа переключится.

Так будет больше пищи для размышлений.

Скорее всего там какое-то упрощение типа «считаем отклонение меньше какого-то порога прямой линией». А уже из прямых линий определяем фигуру.

посчитай попиксельно площади нарисованных фигур

А там не обязательно контур замкнутый м б.: может распознаться как окружность, но контур с разрывом.

Потом попиксельно считать - это медленно. В программе мгновенно определяется.

Если рисовать много, то из всех возможных фигур самое частое выпадает Polygon или Polyline

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

Еще скрины:

Дуга

Окружность с завиточком

Дуга почти окружность

Дуга почти прямая

Линия

что, без готовых фреймворков, библиотек и ч0рных ящиков типа того же opencv совсем не в состоянии самостоятельно придумать никакой адекватный поисковый эвристический алгоритм?

почему бы и не использовать opencv?

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

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

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

Вот такие попробуй https://i.ibb.co/5gjr2fJg/1.png иетересно что скажет

Еще скрины:

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

PS/ На 90% современный «ИИ» так и работает. Добавляет шум к входу, шум к выходу. При незначительной привеси получается «ух-ты...»

кривые Безье, сплайнами Catmull-Rom и другими интерполирующими кривыми.

Короче я придумал

0. нарисовать произвольную фигуру точками
1. описать прямоугольник над фигурой
2. вписать шаблон в прямоугольник (проверяемая фигура)
3. вращать шаблон внутри прямоугольника, вписывая шаблон в прямоугольник
   • 3.1 при вписывании шаблон будет пропорционально искажаться
4. проверять вхождение точек фигуры в грани вписанного шаблона
   • 4.1 толщина граней шаблона при этом определяет точность
5. если достаточный процент точек фигуры пересекает/(входит в) грани шаблона фиксируем совпадение
   • 5.1 процентная величина при этом тоже определяет точность

Таким образом можно с некотором приближением выявлять не только примитивные фигуры описанные выше, через всякие матан хаки с узким спектром применения, но и сложные выпуклые, впуклые, фигурные, ломанные, звёздочки, пентаграммы, можно титьки детектировать или человечка (выпуклого) =)

Начал было делать

• https://i.ibb.co/mCGR8WWK/2025-04-15-21-35-27.png

Но запнулся на вращении вписанного в прямоугольник шаблона по центру прямоугольника, аж голова разболелась.
Может завтра, а может никогда.

Или с пом. какого алгоритма это было сделано?

https://en.wikipedia.org/wiki/Dynamic_time_warping

Короче, выложил на гитхабе:

FigureDetection

Можете скачивать, экспериментировать и анализировать.

Потом попиксельно считать - это медленно. В программе мгновенно определяется.

Ты там на 386 считаешь? На современных процессорах, рассчитать попиксельно один кадр, это о-о-очень быстро. Даже с 60-100к\с считать по заливке думаю не проблема на современных процах.

А там не обязательно контур замкнутый м б.: может распознаться как окружность, но контур с разрывом.

Это ещё легче, замыкать последнюю точку на первую. А если разрывов много(такое вообще там может быть?), то последнюю до разрыва и первую после, а последнюю опять на первую.

Если рисовать много, то из всех возможных фигур самое частое выпадает Polygon или Polyline

А это скорее всего fallback, когда не может определить ничего путного. polygon - замкнутая неопределенная фигота, polyline - разомкнутая неопределенная фигота.

Короче я придумал

Херню, я придумал. Пришёл покаяться, ничего я не отреверсил. Реализовал свою задумку, получилась бредятина, где надо 100500 вариантов фигур шаблонов впихивать чтобы сходилось.

В частных случаях работает, в общих нет. Сначала делаем, потом думаем :D

Не делайте так :)

Некоторые методы распознавания геометрических фигур в компьютерном зрении:

Пакет объектов с дискриминационным модулем (BoF-DM). 1 Метод сочетает ключевые точки и кольцевые графики для изучения локальных и глобальных объектов, позволяя лучше различать важные части формы. 1

Функции распределения разности наклонов (SDD). 1 Метод фокусируется на объектах формы в виде разреженных представлений, обеспечивая надёжное распознавание, даже когда части объекта скрыты. 1

Многоуровневые элементы комбинирования контуров. 1 Метод решает проблемы, связанные с внутриклассовыми вариациями и нелинейными деформациями. 1 Локальные бинарные шаблоны (LBP). 1 Метод извлекает важные особенности контура и использует их для эффективного поиска формы. 1

Метод отношения внутренних расстояний (SIDR). 1 Предлагает быстрый и эффективный способ распознавания фигур на основе их отношения к правильным геометрическим формам, таким как ограничивающие прямоугольники или круги. 1

Преобразование Хафа. 23 Метод выделяет признаки для обнаружения простых форм, таких как круги, линии и т. д., на изображении. 3

Не делайте так :)

• Суть https://rutube.ru/video/aade732da9ed6a6e2ffb19eb0371754d/
• Результат https://gitflic.ru/project/blogdron/figuvam

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

HoughLines, HoughCircles. findContours

Да, это очень сильный хинт. Записанный жест суть готовый контур

Компьютерную графику открой для себя, opencvшное ламерьё.

Обобщенное Преобразование Хафа - Generalized Hough Transform, GHT