Определение принадлежности точки внутренности эллипса

[Omega]

Доброго времени суток, уважаемые форумчане! Появилась такая вот интересная задача.

Есть изображения пузырей. Задача состоит в том, чтобы определить лежит ли точка (на рисунке - это красные квадраты) во внутренней области эллипса, который можно вписать в образ пузыря, - или не лежит. Примеры когда точки вне пузырей:


И внутри:




Текущий вариант решения: выделим квадрат заданного размера (скажем, 80x80 пикселей) с центром в рассматриваемой точке.
Бинаризуем изображение внутри квадрата, тогда - получаем двоичный квадратный массив фиксированного размера, как на изображении ниже.

• Я попытался первым делом использовать алгоритм поиска связанных областей (если область нашлась, закрашиваем её и просто проверяем - есть ли внутри неё центральная точка). Однако этот алгоритм весьма и весьма не просто расширить до возможности использования с неполными периметрами эллипсов (точнее я не придумал пока как).. В общем, - такой подход работает, но далеко не всегда (пузыри редко имеют полностью прочерченный обод).
• Также попробовал преобразование Хафа, чтобы подогнать эллипс и определить его размер. Работает - значительно медленнее, но чуть более успешно (для него также непрочерченный обод большая проблема)

Может у кого есть идеи как это сделать лучше и/или быстрее?
Заранее большое спасибо за Ваши комментарии и советы!

[Pavia]

Постройте выпуклую или частично выпуклую оболочку
http://docs.opencv.org/2.4/doc/tutorial ... /hull.html

[Omega]

Pavia в сообщении #1210042 писал(а):

Постройте выпуклую или частично выпуклую оболочку
http://docs.opencv.org/2.4/doc/tutorial ... /hull.html

Идея хорошая, спасибо!

Но как же быть если у меня есть что-то подобное?

[Munin]

Забить. Ваша задача - это задача распознавания образов. Или вы всерьёз занимаетесь ИИ, или бросаете это дело.

[mihaild]

Omega в сообщении #1210101 писал(а):

Но как же быть если у меня есть что-то подобное?

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

[Omega]

mihaild в сообщении #1210167 писал(а):

Omega в сообщении #1210101 писал(а):

Но как же быть если у меня есть что-то подобное?

...сразу учить сверточную нейросеть.

Это и есть результаты её работы :)
Дело в том, что особенность обучающих данных такова, что появляются такие вот ошибки - и их крайне сложно искоренить..

Munin в сообщении #1210161 писал(а):

Забить. Ваша задача - это задача распознавания образов. Или вы всерьёз занимаетесь ИИ, или бросаете это дело.

Это не наш метод! Нужно завершить начатое.

[mihaild]

Omega в сообщении #1210206 писал(а):

Это и есть результаты её работы :)

В смысле она вот такие картинки рисует?
А почему не хотите учить ее сразу определять, попадает точка внутрь или нет?

[Omega]

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

-- 17.04.2017, 22:38 --

Pavia в сообщении #1210042 писал(а):

Постройте выпуклую или частично выпуклую оболочку
http://docs.opencv.org/2.4/doc/tutorial ... /hull.html

Частично улучшило ситуацию - но часть случаев всё равно плохо обрабатывается.

[amon]

Omega в сообщении #1209985 писал(а):

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

Я бы попробовал что-нибудь такое. Поставим на эллипсе некоторое количество точек, стараясь, что бы среди них была точка, находящаяся на минимальном расстоянии от изучаемой. После этого сосчитаем сумму углов, образованных отрезками, соединяющими изучаемую точку с точками на эллипсе при обходе точек на эллипсе, например, против часовой стрелки с учетом знака угла. Если сумма $2\pi,$ то точка внутри, если ноль - то снаружи.

[Omega]

Спасибо, попробую. А что на счёт идеи собрать из каждого кругового сектора по градусов 15 точки в определённом диапазоне расстояний, как здесь например:

Выбрать из них некоторое число случайных троек точек - и вписывать в каждую по окружности. Затем собрать статистику по полученным центрам этих окружностей, и, если максимум пика где-то в центре кадра - то ответ даём положительный. Иначе - отрицательный.
Это словно поиск колец из следов электронов в детекторе)

[Omega]

Всем спасибо! Проблема решена правильной настройкой параметров тренировочных данных для НС.
А самым эффективным методом удаления точек стал способ предложенный amon.

[bondkim137]

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

[bondkim137]

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

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

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