Производительность OpenCV при сопоставлении с шаблонами

Я пытаюсь сделать шаблон, соответствующий в основном на java. Я использовал простой алгоритм для поиска соответствия. Вот код:

minSAD = VALUE_MAX;
// loop through the search image
for ( int x = 0; x <= S_rows - T_rows; x++ ) {
    for ( int y = 0; y <= S_cols - T_cols; y++ ) {
        SAD = 0.0;

        // loop through the template image
        for ( int i = 0; i < T_rows; i++ )
            for ( int j = 0; j < T_cols; j++ ) {

                pixel p_SearchIMG = S[x+i][y+j];

                pixel p_TemplateIMG = T[i][j];

                SAD += abs( p_SearchIMG.Grey - p_TemplateIMG.Grey );
            }
    }

    // save the best found position 
    if ( minSAD > SAD ) {
        minSAD = SAD;
        // give me VALUE_MAX
        position.bestRow = x;
        position.bestCol = y;
        position.bestSAD = SAD;
    }
}

Но это очень медленный подход. Я протестировал 2 изображения (768 × 1280) и субимаг (384 x 640). Это длится веками. Совместим ли openCV с шаблоном намного быстрее или нет с готовой функцией cvMatchTemplate()?

Ответ 1

Вы найдете openCV cvMatchTemplate() намного быстрее, чем метод, который вы реализовали. То, что вы создали, является методом сопоставления статистических шаблонов. Это самый распространенный и самый простой в реализации, однако на больших изображениях очень медленно. Давайте посмотрим на основные математические данные, которые у вас есть изображение 768x1280, которое вы проецируете через каждый из этих пикселей за вычетом края, поскольку это ваши шаблонные пределы, поэтому (768 - 384) x (1280 - 640), что 384 x 640 = 245 ' 760 операций, в которых вы просматриваете каждый пиксель вашего шаблона (еще 245'760 операций), поэтому, прежде чем добавлять какие-либо математические данные в свой цикл, вы уже имеете (245'760 x 245'760) 60'397'977'600 операций. Более 60 миллиардов операций просто зацикливаются на вашем изображении. Удивительно, как быстрые машины могут это сделать.

Помните, однако, его 245'760 x (245'760 x Maths Operations), поэтому есть еще много операций.

Теперь cvMatchTemplate() фактически использует операцию сопоставления шаблонов Fourier Analysis. Это работает, применяя быстрое преобразование Фурье (FFT) на изображении, в котором сигналы, составляющие изменение интенсивности изображения, сегментируются в каждую из соответствующих форм волны. Метод трудно объяснить, но изображение преобразуется в представление сигналов комплексных чисел. Если вы хотите больше понять, пожалуйста, найдите в goggle для быстрое преобразование Фурье. Теперь эта же операция выполняется на шаблоне, сигналы, которые формируют шаблон, используются для фильтрации любых других сигналов с вашего изображения.

В простых случаях он подавляет все функции в изображении, которые не имеют тех же функций, что и ваш шаблон. Изображение затем преобразуется обратно с использованием обратного быстрого преобразования Фурье для создания изображений, где высокие значения означают совпадение, а низкие значения означают противоположное. Это изображение часто нормализуется, так что 1 представляет совпадение и 0 или там примерно означает, что объект не находится рядом.

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

Причина, по которой этот метод работает так быстро: 1) opencv - это высоко оптимизированный код С++. 2) Функция fft легко обрабатывается процессором, поскольку большинство из них имеют возможность выполнять эту операцию на оборудовании. Графические карты графического процессора рассчитаны на выполнение миллионов операций fft каждую секунду, поскольку эти вычисления столь же важны для высокопроизводительной игровой графики или кодирования видео. 3) Объем требуемых операций намного меньше.

В летнем статистическом методе сопоставления шаблонов происходит медленный процесс, и он занимает много времени, тогда как opencv FFT или cvMatchTemplate() является быстрым и высоко оптимизированным.

Статистическое сопоставление шаблонов не приведет к ошибкам, если объект не существует, тогда как opencv FFT может, если в его приложении не будет заботы.

Надеюсь, это даст вам общее понимание и ответит на ваш вопрос.

Приветствия

Крис

[EDIT]

Чтобы ответить на ваши вопросы:

Привет,

cvMatchTemplate может работать с CCOEFF_NORMED и CCORR_NORMED и SQDIFF_NORMED, включая ненормированную версию. Здесь показан вид результатов, который вы можете ожидать, и дает вам код для воспроизведения.

http://dasl.mem.drexel.edu/~noahKuntz/openCVTut6.html#Step%202

Три метода хорошо цитируются, и многие документы доступны через Google. Я привел несколько бумаг ниже. Каждый из них просто использует другое уравнение, чтобы найти корреляцию между сигналами FFT, которые формируют шаблон, и сигналы FFT, которые присутствуют в изображении. Коэффициент корреляции имеет тенденцию давать лучшие результаты в моем опыте и легче найти ссылки. Сумма квадрата разницы - это еще один метод, который можно использовать с сопоставимыми результатами. Я надеюсь, что некоторые из них помогут:

Быстрая нормализованная взаимная корреляция для обнаружения дефектов Ду-Мин Цай; Chien-Ta Lin; Письма о распознавании образов Том 24, выпуск 15, ноябрь 2003 г., стр. 2625-2631

Подбор шаблонов с использованием быстрой нормализованной кросс-корреляции Кай Бришель; Уве Д. Ханебек;

Относительная производительность методов двумерного спекл-отслеживания: нормализованная корреляция, ненормированная корреляция и сумма-абсолютная разница Friemel, B.H.; Bohs, L.N.; Traeyy, G.E.; Ультразвуковой симпозиум, 1995. Труды., 1995 IEEE

Класс алгоритмов для быстрой регистрации цифровых изображений Barnea, Daniel I.; Сильверман, Харви Ф.,
Компьютеры, IEEE Transactions, февраль 1972 г.

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

Цифровой сигнальный процессор Хотя на странице Wiki ссылки заслуживают внимания, это аппаратное обеспечение, которое выполняет вычисления FFT

Новый подход к процессу FFT для трубопроводов Шушенг Он; Матс Торкельсон; Мой любимый, поскольку он показывает, что происходит внутри процессора

Эффективный локально конвейерный FFT-процессор Лян Ян; Кьюэй Чжан; Хонксия Лю; Джин Хуан; Шитан Хуан;

В этих документах действительно показано, насколько сложным является БПФ при реализации, однако прокладка трубы процесса позволяет выполнять операцию за несколько тактов. Именно по этой причине в системах, основанных на реальном времени, используется FPGA (в частности, проектные процессоры, которые вы можете проектировать для реализации заданной задачи), поскольку они могут быть чрезвычайно параллельными в архитектуре, а прокладка труб проще реализовать.

Хотя я должен упомянуть, что для FFT изображения вы фактически используете FFT2, который является БПФ горизонтальной равнины и БПФ вертикальной равнины, так что нет никакой путаницы, когда вы найдете ссылку на нее. Я не могу сказать, что у меня есть экспертное знание о том, как реализованы уравнения и БПФ. Я попытался найти хорошие руководства, но найти хорошего гида очень сложно, так что я еще не нашел его (Не тот, который я могу понять на наименее). Однажды я могу понять их, но знаю, что у меня есть хорошее представление о том, как они работают, и о тех результатах, которые можно ожидать.

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

Крис