Искать шаблон изображения

Question

Мне нужна программа, которая делает это: учитывая изображение (5 * 5 пикселей), я должен искать, сколько таких изображений существует в другом изображении, составленном многими другими изображениями. То есть мне нужно искать заданный шаблон на изображении.

Используемый язык - C. Я должен использовать параллельные вычисления для поиска в 4 углах (0º, 90º, 180º и 270º).

Каков наилучший способ сделать это?

Answer 1

Кажется, прямо вперед.

• Создание 4 версий изображения с поворотом на 0 °, 90 °, 180 ° и 270 °.
• Начинайте четыре темы, каждая с одной версией изображения.
• Для всех позиций от (0,0) до (width - 5, height - 5)
  • Сопоставить 25 пикселей эталонного изображения с 25 пикселями в текущей позиции
  • Если они достаточно равны по некоторой метрике, сообщите о результатах.

Answer 2

Использование нормализованной корреляции для определения соответствия шаблонов.

@ Daniel, решение Daniel отлично подходит для использования нескольких процессоров. Он не упоминает метрику качества, которая была бы полезна, и я хотел бы предложить одну метрику качества, которая очень распространена при обработке изображений.

Я предлагаю использовать нормализованную корреляцию [1] в качестве метрики сравнения, поскольку она выводит число от -1 до +1. Где 0 - нет корреляции 1 будет выведено, если два шаблона были идентичны, и -1 будет, если два шаблона были абсолютно противоположны.

Как только вы вычислите нормированную корреляцию, вы можете проверить, нашли ли вы шаблон, выполнив пороговый тест или тест от пика до среднего [2].

[1 - сноска] Как реализовать нормализованную корреляцию? Это довольно просто и имеет только два цикла. Если у вас есть достаточно хорошая реализация, вы можете проверить ее, проверив, получает ли идентичное изображение 1. 1. 1015 *

[2 - сноска] Вы задаете соотношение макс (массив) / среднее (array_without_peak). Затем определите порог, чтобы убедиться, что у вас хорошее соотношение пиковых и средних значений.

Answer 3

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

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

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

Answer 4

5 * 5 = 25

25 бит помещается в целое число.

каждое изображение может быть закодировано как массив из 4 целых чисел.

Повторяйте ваше увеличенное изображение (надеюсь, оно не слишком большое), вытащив все 5 * 5 вложенных изображений, преобразовать в массив из 4 целых чисел и сравнить.