Как найти шаблоны (линии, круги, ...) из списка точек?

Question

У меня есть список точек. Каждая точка является координатой x и y (обе являются целыми числами). Теперь я пытаюсь найти известные шаблоны, такие как линии, дуги или окружности, зная, что точки не идеально расположены на шаблоне.

Какой лучший способ сделать это? У меня не так много подсказок, чтобы начать.

Редактировать: точки упорядочены. Пользователь что-то рисует, и программа должна определить лучшие образцы. Например, если нарисован треугольник, он должен обнаружить три линии.

Answer 1

взгляните на Преобразование Хафа . то, что вы делаете: вы преобразуете свое изображение в "круговое" пространство, и тогда вам нужно только найти светлые пиксели.

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

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

Answer 2

Классическим распознавателем является нейронная сеть. Нейронные сети работают "хорошо" и требуют некоторого обучения.

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

Answer 3

Поскольку вы получаете пиксели, и они располагаются по порядку, вы можете начать с проверки наклона между, скажем, каждым десятым нарисованным пикселем и посмотреть, как меняется наклон. Непрерывности дают вам некоторую информацию.

Answer 4

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

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

Полагаю, вам понадобится нечто иное, чем стандартное отклонение, то, что меньше интересует выбросы и больше интересует комкование.

Кроме того, это не принесет вам пользы для линий.

Answer 5

Пока вы ограничиваете его базовыми фигурами, вы можете рассчитать усредненное «направление» текущего штриха и создать последовательность «штрихов» из них.

Вероятно, легче распознать форму на основе этой информации:

• круг имеет довольно постоянную вторую производную
• «семерка» имеет удар вправо, а затем удар в левом нижнем углу
• ...