Обнаружение окружностей (эллипсов) в 2D точечном облаке

14

Учитывая множество точек (2D) т.е. точка помутнения (PC), то речь идет о robust, accurateи computing-friendlyметод , чтобы найти круги (или эллипсов в расширенной версии).

Интуитивно понятная идея заключается в использовании поиска методом грубой силы по всем возможным точкам (в качестве центра) {бесконечно!} И радиусам (опять же бесконечно!). Это ультра-крайне медленно и неэффективно.

Как показано ниже, каждый подобранный круг будет ранжироваться на основе количества точек ( nn), расположенных на окружности окружности на расстоянии, меньшем порога ( t). Так что есть, derrчтобы представить среднее расстояние.

В расширенной форме эллипсы представляют интерес для установки.

Есть идеи, мозговой штурм, опыт, комментарии? введите описание изображения здесь

разработчик
источник
Хороший вопрос. Какую программу вы использовали для создания этой диаграммы?
Джейсон Р
@JasonR Как всегда, Python + MatPlotLib .
Разработчик

Ответы:

14

Лучшие идеи, которые точно пытаются решить эту проблему - это Hough Transform .

В основном, сигнал в жестком пространстве будет r, x, yкоординатами. Здесь r обозначает радиус и x,yобозначает центр. Каждая точка может принадлежать одному или нескольким кругам. Так что в плоскости Хафа пройдите все возможные круги, где эта точка может принадлежать, и просто сделайте +1. Это не поиск, а коллекция.

Теперь, если существует реальный круг, будет добавлено так много очков, и оценка такого r, x, yбудет намного выше, чем у всех остальных. Выбор такой точки позволит вам выбрать правильные круги.

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

  1. ИСПОЛЬЗОВАНИЕ ХАРА ТРАСФОРМАЦИИ ДЛЯ ОБНАРУЖЕНИЯ ЛИНИЙ И ИЗОБРАЖЕНИЙ В КАРТИНАХ Автор: Ричард О. Дуда, Питер Э. Харт. Технический отчет Центра искусственного интеллекта, апрель 1971 года.

Для учебника я бы предложил ссылки ниже:

  1. HIPR2 -Ссылка
  2. Амос Сторкей
  3. Ссылка IDL

В частности, для обнаружения круга, вы можете обратиться к этому ниже:

  1. AI Shack
  2. Технический отчет из Чикаго Univ.
  3. Конспект лекций Рочестерского института

Эти методы очень эффективны и очень дружественны к компьютеру.

Дипан Мехта
источник
1
Я могу поручиться за статьи об AI Shack, они действительно помогают справиться с более строгой математикой, которую вы прочтете в другом месте.
Иво Флипс
1
Хороший ответ. Я уже знаком с Hough Transform (HT). Тот, который я использовал, был для обнаружения линий. Было немного сложно определить отрезки. Поэтому было рекомендовано использовать вероятностное преобразование Хафа (PHT). Я не получил четкое представление о расширении. Я думал, что это может быть настолько сложным для кругов или появиться другие трудности. Что касается моего опыта, ХТ это хорошо, но не идеально. Также меня интересует, как расширить HT на 3D. Я постараюсь просмотреть предоставленные вами ссылки. Ваш ответ довольно хорош, чтобы быть кандидатом в качестве ответа.
Разработчик
Ссылки AI Shack и Tech Report от Chicaco мертвы
Мехди,