Алгоритмы: совпадение эллипсов

У меня много изображений, похожих на следующие (только белые и черные):

введите описание изображения здесь

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

Моя идея – найти «точки останова». Я отмечаю их на следующем рисунке:

введите описание изображения здесь

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

введите описание изображения здесь

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

большое спасибо

    1. Образец точек окружности

      Просто сканируйте свое изображение и выберите «Все черные пиксели» с любым белым соседом. Вы можете сделать это, перекрасив оставшиеся черные пиксели в любой неиспользованный цвет (синий).

      После того, как будет сделано целое изображение, вы можете перекрасить внутреннюю спину из неиспользуемого цвета (синий) в белый.

    2. сформировать список упорядоченных точек окружности на кластер / эллипс

      Просто сканируйте свое изображение и найдите первый черный пиксель. Затем используйте A * для заказа точек окружности и сохраните путь в каком-либо массиве или в списке pnt[] и обработайте его как круглый массив.

    3. Найдите «точки останова»

      Они могут быть обнаружены пиком по углу между соседями найденных точек. что-то вроде

       float a0=atan2(pnt[i].y-pnt[i-1].y,pnt[i].x-pnt[i-1].x); float a1=atan2(pnt[i+1].y-pnt[i].y,pnt[i+1].x-pnt[i].x); float da=fabs(a0-a1); if (da>M_PI) da=2.0*M_PI-da; if (da>treshold) pnt[i] is break point; 

      или использовать тот факт, что в точке останова знак отклонения угла наклона:

       float a1=atan2(pnt[i-1].y-pnt[i-2].y,pnt[i-1].x-pnt[i-2].x); float a1=atan2(pnt[i ].y-pnt[i-1].y,pnt[i ].x-pnt[i-1].x); float a2=atan2(pnt[i+1].y-pnt[i ].y,pnt[i+1].x-pnt[i ].x); float da0=a1-a0; if (da0>M_PI) da0=2.0*M_PI-da0; if (da0<-M_PI) da0=2.0*M_PI+da0; float da1=a2-a1; if (da1>M_PI) da1=2.0*M_PI-da1; if (da1<-M_PI) da1=2.0*M_PI+da1; if (da0*da1<0.0) pnt[i] is break point; 
    4. подходящие эллипсы

      поэтому, если не найдено точек останова, вы можете поместить весь pnt [] в виде одиночного эллипса. Например, найдите ограничительную рамку. Это центр центра эллипса, и его размер дает вам полуоси.

      Если обнаружены точки останова, сначала найдите ограничительную рамку для целого pnt[] чтобы получить пределы для полуоси и поиска области центра. Затем разделите pnt[] на части между точками разрыва. Обрабатывайте каждую часть как отдельную часть эллипса и подгонка.

      После того, как все части pnt[] установлены, проверьте, не являются ли некоторые эллипсы одними и теми же, если они перекрываются другим эллипсом, они будут разделены ... Таким образом, слияние идентичных (или среднее значение для повышения точности). Затем перекрасьте все точки pnt pnt[i] на белый, очистите список pnt[] и цикл # 2, пока не будет найдено больше черного пикселя.

    5. как подобрать эллипс от выбора очков?

      1. алгебраически

        используйте уравнение эллипса с «равномерно» распределенными известными точками, чтобы сформировать систему уравнений для вычисления параметров эллипса ( x0,y0,rx,ry,angle ).

      2. геометрически

        например, если вы обнаружите наклон 0,90,180 или 270 gradleусов, то вы находитесь на пересечении с осью по оси. Поэтому, если у вас есть две такие точки (по одной для каждой полуоси), это все, что вам нужно для подгонки (если это эллипс, ориентированный по оси).

        для эллипсов, не ориентированных по оси, вам нужно иметь достаточно большую часть окружности. Вы можете использовать тот факт, что центр ограничивающей frameworks также является центром эллипса. Итак, если вы получили весь эллипс, вы знаете также центр. Полуосные пересечения с окружностью могут быть обнаружены с самым большим и наименьшим касательным изменением. Если у вас есть центр и две точки - все, что вам нужно. Если у вас есть только частичный центр (только координата x или y), вы можете комбинировать с большим количеством осевых точек (найти 3 или 4) ... или приблизиться к отсутствующей информации.

        Также половина оси H, V линий пересекает центр эллипса, поэтому его можно использовать для обнаружения, если не весь эллипс в списке pnt[] .

        выравнивание по эллипсу без оси

      3. поиск приближений

        Вы можете выполнить «все» возможную комбинацию параметров эллипса в пределах, найденных в # 4, и выбрать тот, который ближе всего к вашим точкам. Это было бы безумно медленным грубым, поэтому используйте бинарный поиск, например, подход, похожий на мой class . Также см

        • Фиксация кривой с точками y на повторяющихся положениях x (галактические спиральные armва)

        о том, как он используется для аналогичного соответствия вашему.

      4. гибридный

        Вы можете комбинировать геометрический и приближенный подход. Сначала вычислите, что вы можете по геометрическому подходу. А затем вычислить остальные с помощью аппроксимационного поиска. вы также можете повысить точность найденных значений.

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

    Вот что я имею в виду:

    обзор

    Вам, вероятно, нужно что-то вроде этого:

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

    Ваши граничные точки – это просто черные пиксели с по крайней мере одним белым 4-соседом.

    К сожалению, вы говорите, что ваши эллипсы могут быть «наклонены». Общие эллипсы описываются квадратичными уравнениями типа

     x² + Ay² + Bxy + Cx + Dy + E = 0 

    с B² <4A (⇒ A> 0). Это означает, что, по сравнению с проблемой окружности, у вас нет 3 измерений, но 5. Это приводит к тому, что преобразование Хафа будет значительно сложнее. К счастью, ваш пример подсказывает, что вам не нужно высокое разрешение.


    См. Также: алгоритм обнаружения круга в изображении


    РЕДАКТИРОВАТЬ

    Вышеупомянутая идея алгоритма была слишком оптимистичной , по крайней мере, если ее применяли простым способом. Хорошей новостью является то, что два умных парня (Yonghong Xie и Qiang Ji) уже сделали домашнее задание для нас:

    https://www.ecse.rpi.edu/~cvrl/Publication/pdf/Xie2002.pdf

    Я не уверен, что создам свой собственный алгоритм. Почему бы не повлиять на работу, которую другие команды сделали, чтобы выяснить, какая кривая подходит для растровых изображений?

    INKSCAPE (ссылка на приложение)

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

    Вот ссылка на отправную точку для API Inkscape:

    http://wiki.inkscape.org/wiki/index.php/Script_extensions

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

    Вы также можете сделать что-то с нулевым скриптом из интерфейса командной строки inkscape:

    http://wiki.inkscape.org/wiki/index.php/Frequently_asked_questions#Can_Inkscape_be_used_from_the_command_line.3F

    COREL DRAW (приложение Link)

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

    Вот ссылка на их API:

    https://community.coreldraw.com/sdk/api

    Вот ссылка на пакетную обработку Corel Draw (решение без скрипта):

    http://howto.corel.com/en/c/Automating_tasks_and_batch-processing_images_in_Corel_PHOTO-PAINT

    Interesting Posts

    Что это за странное поведение двоеточия Python?

    Как установить прокси-сервер по умолчанию для использования учетных данных по умолчанию?

    Создание документов Word (в Excel VBA) из серии шаблонов документов

    Как использовать class в Java?

    Какие файлы можно удалить при использовании Dropbox на внешнем жестком диске?

    Запуск нескольких экземпляров любого приложения Windows

    Странное поведение в функции PowerShell, возвращающее DataSet / DataTable

    Как выполнять команды в другой папке, не повторяя путь к папке?

    Почему это происходит в бесконечном цикле?

    Слишком длинное имя файла – НЕВОЗМОЖНО удалить / переместить / переименовать

    Internet Explorer 10, похоже, не работает с Sysinternals Despops

    Первичный ключ Rails и идентификатор объекта

    Как создать сертификат для моего Android Market APK?

    Firefox 32: загрузка не удалась; Не может читать из источника

    Как выравнивать представления в нижней части экрана?

    Давайте будем гением компьютера.