Обнаружение нескольких фигур на картинке и вычисление середины

На этот вопрос можно ответить на любом языке программирования, потому что мне нужна помощь с алгоритмами, но я предпочитаю Delphi. У меня есть задача обнаруживать и подсчитывать несколько форм (от 1 до N - в основном круглые или Elipse) случайных изображений, вычислять их середину и возвращать их как координаты изображения. Середина каждой формы может иметь заливку (но это не имеет значения). Фигуры находятся на расстоянии не менее 1 пикселя друг от друга. Ни одна из форм не будет сливаться с другой или уголком изображения. Фон изображения всегда имеет один и тот же цвет фона, что на самом деле не имеет значения, потому что границы / рамки фигур всегда имеют другой цвет по сравнению с фоном. Это упрощает обнаружение форм. Я думал о том, чтобы идти пиксель за пикселем и собирать координаты, а затем рисовать невидимым прямоугольником / квадратом вокруг каждой формы, чтобы вычислить середину. Потом я тоже услышал про scanline, но не думаю, что в этом случае он будет быстрее. Итак, у меня вопрос, как я могу рассчитать:

  1. Сколько фигур на картинке.
  2. Как я могу вычислить (более или менее) точную середину из них.

Несколько картинок для визуализации задачи:

Это изображение со случайными формами (в основном тесными кругами). Как вы можете видеть, они отлично расположены друг от друга.

Фигуры на картинке

Тогда я мог бы легко нарисовать / вычислить воображаемый прямоугольник / квадрат вокруг каждой формы и вычислить его середину следующим образом: Фигуры в  изображение с прямоугольниками / квадратами вокруг них

После того, как у меня есть прямоугольники / квадраты. Я легко могу вычислить середину. Как мне начать?

PS: Я нарисовал несколько кружков в mspaint. Я должен добавить, что все формы ЗАКРЫТЫ, что позволяет без проблем заливать ЛЮБУЮ форму на картинке!

Спасибо за помощь.


person Benjamin Weiss    schedule 11.01.2013    source источник
comment
То, что вы хотите найти, называется центроидом. Вам не нужен ограничивающий прямоугольник для его вычисления, только точки, принадлежащие внешней стороне объекта. Я заметил, что некоторые из ваших нарисованных от руки объектов не закрыты, это намеренно (судя по вашему последнему комментарию, это было чистым совпадением - на самом деле они все закрыты)?   -  person mmgp    schedule 12.01.2013
comment
Мне жаль насчет того. Как я уже сказал - все формы закрыты.   -  person Benjamin Weiss    schedule 12.01.2013
comment
После заливки объектов вы можете сохранить только границы и вычислить центроид каждой формы. Я поместил такой код в stackoverflow.com/questions/14263050/, который не зависит от какой-либо библиотеки для этих задач, я верю, что у вас не возникнет особых проблем с преобразованием Python в язык, подобный Pascal. Если есть какие-либо сомнения относительно этого кода, не стесняйтесь спрашивать.   -  person mmgp    schedule 12.01.2013
comment
Я посмотрю что я могу сделать. Но я думал о том, чтобы просмотреть каждый пиксель, а затем пропустить все, что не является фоном. Как здесь: en.wikipedia.org/wiki/File:Smiley_fill.gif (зеленый цвет означает поиск, а не заполнение! Это приведет к игнорированию того, что находится В фигуре.   -  person Benjamin Weiss    schedule 12.01.2013
comment
Я думаю, что непонятно, хотите ли вы центроид, а не центр форм. Потому что вы пытались связать их прямоугольниками. Кроме того, второе изображение во второй строке не является круглым / эллиптическим. Вам тоже нужно найти центроид этой формы?   -  person EMBarbosa    schedule 12.01.2013
comment
@BenjaminWeiss есть некоторая путаница, потому что ссылка, которую вы упомянули, касается заливки. Неважно, заполняете ли вы каждый пиксель или нет; вы выполняете те же операции, что и заливка заливкой, за исключением того, что, как вы говорите, пиксели не заполняются. Но если на самом деле заполнить заливкой, в смысле устранения внутренних дыр каждого компонента, задача станет проще.   -  person mmgp    schedule 12.01.2013
comment
Пример заливки, который я опубликовал, был просто примером того, как я могу искать пиксели. Я собирался просмотреть каждый пиксель изображения, начиная с 0,0. Какой бы пиксель не был черным (! = Цвет фона), я сохраняю координаты. В конце есть способ вычислить, сколько объектов, форм на картинке, а затем вычислить центроид. Я просмотрел ваш код на Python, но не могу его перевести. Мне нужно больше советов по алгоритму, как начать искать и что.   -  person Benjamin Weiss    schedule 12.01.2013
comment
@BenjaminWeiss в коде прямо под комментарием # Сохраняйте только пограничные точки, он делает то, что вы говорите (я думаю). Он сканирует каждый пиксель изображения, если он находит фоновый пиксель (предполагается, что там 255), то ничего не делается. С другой стороны, если мы находим черный пиксель, мы оглядываемся вокруг четырех соседей. Если один из этих соседей - белый пиксель, то этот черный пиксель находится на границе, и мы оставляем его черным, в противном случае мы устанавливаем его белым. Это должно быть сделано во вспомогательном образе, это не сработает для модификаций на месте.   -  person mmgp    schedule 12.01.2013
comment
И это, конечно, работает только в том случае, если фигура заполнена перед ее применением. Если в ваших фигурах нет ничего внутри (отличного от рисунка выше), вам не нужен шаг в комментарии над этим.   -  person mmgp    schedule 12.01.2013
comment
На i.imgur.com/uyuEb.png вы можете увидеть разницу между центроидом (синий точки) и центр ограничивающей рамки (точки лосося).   -  person mmgp    schedule 12.01.2013
comment
Потрясающие результаты! Это было сделано с вашим кодом? Хотел бы я сделать это с помощью Delphi, но я все еще не понимаю алгоритм. Не могли бы вы привести пример?   -  person Benjamin Weiss    schedule 12.01.2013
comment
@BenjaminWeiss, поскольку я взял именно ваше входное изображение для тестирования, я использовал что-то более надежное, чтобы закрыть компоненты, но все остальное можно было бы сделать с ним. Фактический код для создания этого был сделан в Mathematica, который в полном объеме довольно короткий: ComponentMeasurements[FillingTransform[Closing[Import["http://i.stack.imgur.com/m1pjE.jpg"], DiskMatrix[3]]], {"Centroid", "BoundingBox"}], и самый конечный результат - это просто наложение этих результатов на исходное изображение.   -  person mmgp    schedule 12.01.2013


Ответы (1)


Рассчитайте MSER (максимально устойчивые экстремальные области) для изображения. Я не могу здесь объяснить этот алгоритм. Дополнительную информацию об алгоритме можно найти в статье Максимально стабильные экстремальные области.

Это тоже даст вам центроид.

Этот алгоритм реализован в виде встроенных функций в инструменте OpenCv и Matlab 2012b.

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

person Mayank Jain    schedule 24.01.2013