Поиск шаблона изображения

Question

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

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

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

Answer 1

Кажется прямолинейным.

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

Answer 2

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

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

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

Answer 3

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

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

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

После вычисления нормированной корреляции вы можете проверить, нашли ли вы шаблон, выполнив либо threshold test, либо тест с максимальным значением [2].

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

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

Answer 4

5 * 5 = 25

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

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

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