Производительность OpenCV при сопоставлении с шаблоном - PullRequest
Новая
       16

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

11 голосов
/ 21 августа 2011

Я пытаюсь сделать сопоставление шаблона в основном на 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 Ответ

39 голосов
/ 31 августа 2011

Вы обнаружите, что 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 () фактически использует операцию сопоставления с шаблоном анализа Фурье. Это работает путем применения быстрого преобразования Фурье ( FFT ) к изображению, в котором сигналы, составляющие изменения интенсивности пикселей, сегментируются на каждую из соответствующих волновых форм. Метод трудно объяснить, но изображение преобразуется в сигнальное представление комплексных чисел. Если вы хотите понять больше, пожалуйста, найдите в goggle быстрое преобразование Фурье . Теперь та же операция выполняется с шаблоном, сигналы, которые формируют шаблон, используются для фильтрации любых других сигналов с вашего изображения.

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

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

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

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

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

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

Приветствия

Chris

[EDIT]

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

Привет

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

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

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

Быстрая нормализованная взаимная корреляция для обнаружения дефектов Du-Ming Tsai;Чиен-та Лин;Письма о распознавании образов Том 24, выпуск 15, ноябрь 2003 г., стр. 2625-2631

Сопоставление шаблонов с использованием быстрой нормализованной взаимной корреляции Kai Briechle;Уве Д. Ханебек;

Относительная эффективность двумерных методов отслеживания спеклов: нормализованная корреляция, ненормализованная корреляция и сумма-абсолютная разница Friemel, BH;Bohs, LN;Трей, Дженерал Электрик;Ultrasonics Symposium, 1995. Proceedings., 1995 IEEE

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

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

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

Новый подход к конвейерному процессору БПФ Shousheng He;Матс Торкельсон;Мой любимый, поскольку он показывает, что происходит внутри процессора

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

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

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

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

Крис

...