Самый быстрый способ поиска указанного элемента на изображении?

Question

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

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

Какой самый быстрый метод обработки изображения для поиска указанного элемента в простом 2D-изображении?

Answer 1

Типичным способом поиска объекта на изображении является кросс-корреляция . По сути, вы ищете положение, в котором взаимная корреляция между mask (объект, который вы пытаетесь найти) и изображением является самой высокой. Эта позиция - вероятное местоположение объекта, который вы пытаетесь найти.

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

Некоторые проблемы с вышеуказанным подходом:

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

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

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

Answer 2

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

Если вы уже знаете точную форму и имеете представление о размере, возможно, вы захотите взглянуть на обобщенное преобразование Хафа * 1008.*, что в основном является формализованным описанием вашего "алгоритма грубой силы"

Answer 3

Шаг 1: пороговое значение - уменьшите изображение до 1 бита (черного или белого), если это позволяет общий набор изображений.[Для примера, который вы привели, я предполагаю, что пороговое значение будет работать хорошо - оставляя достаточно деталей для поиска объектов].

Шаг 2: При необходимости сделайте некоторое сглаживание / удаление шума.

Шаг 3: Используйте некоторый подход кластеризации для сбора объектов переднего плана.

Шаг 4: Используйте соответствующую эвристику для идентификации объектов.

Параметры в шагах 1/2 будут сильно зависеть от типаизображения, а также эксперименты / наблюдения.3 обычно проста, если вы выполнили 1/2 правильно.4 будет очень сильно зависеть от проблемы (например, в вашем случае определение звезд - что будет зависеть от того, какова реальная форма звезд, ожидаемых на изображениях).

Answer 4

Когда вы указываете свойство, которое не перекрывает фигуры, я предполагаю, что эффективный алгоритм сможет

• вырезать все фигуры, сканируя изображение некоторым образом (я могу представить себе относительноэффективный и простой алгоритм для выпуклых форм)
• когда у вас останутся вырезанные фигуры, вы можете использовать упомянутое перекрестное соотношение

Вы должны описать проблему немного лучше

• можно ли повернуть или масштабировать фигуры (или каким-либо другим преобразованием?)
• - это цвет фона, равный
• - это цвет формы, одинаковый
• - это фигурызаполнено

В зависимости от ответа на вышеуказанные вопросы у вас могут быть более менее или более простые решения.

Также, возможно, эта статья может быть интересной.

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