Как я могу сделать это быстрее?(C / C ++) OpenCV

Question

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

Это мой алгоритм:

IplImage *videoFrame = cvCreateImage(cvSize(bufferWidth, bufferHeight), IPL_DEPTH_8U, 4);
videoFrame->imageData = (char*)bufferBaseAddress;
int channels = videoFrame->nChannels;
int widthStep = videoFrame->widthStep;
int width = videoFrame->width;
int height = videoFrame->height;

for(int i=0;i<height;i++){

    uchar *col = ((uchar *)(videoFrame->imageData + i*widthStep));

    for(int j=0;j<width;j++){

        double pRed     = col[j*channels + 0];                      
        double pGreen   = col[j*channels + 1];       
        double pBlue    = col[j*channels + 2];       

        double dRed     = green.val[0] - pRed;
        double dGreen   = green.val[1] - pGreen;
        double dBlue    = green.val[2] - pBlue;

        double sDRed    = dRed * dRed;
        double sDGreen  = dGreen * dGreen;
        double sDBlue   = dBlue * dBlue;


        double sum = sDRed + sDGreen + sDBlue;

        double euc = sqrt(sum);
        //NSLog(@"%f %f %f", pRed, pGreen, pBlue);

        if (euc < threshold) {
            col[j*channels + 0] = white.val[0];
            col[j*channels + 1] = white.val[1];
            col[j*channels + 2] = white.val[2];
        }

    }
}

Спасибо!

ОБНОВЛЕНИЕ Хорошо, так что это делает цикл по каждому пикселю изображения и вычисляет евклидово расстояние между цветомпиксель и зеленый цвет.Итак, в целом это алгоритм зеленого экрана.

Я сделал несколько тестов, и fps без использования этого алгоритма составляет 30.0fps.Используя этот алгоритм, он падает примерно до 8 кадров в секунду.Но большая часть отбрасывания происходит от col[j*channels + 0]; Если алгоритм ничего не делает и использует доступ к массиву, он падает примерно до 10 кадров в секунду.

ОБНОВЛЕНИЕ 2 Хорошо, это интересно, я удалил случайные строки из материала внутри двойного цикла, чтобы посмотреть, что вызывает большие издержки, и вот что я обнаружил: создание переменных в стеке приводит к ОГРОМНОМУ падению FPS.Рассмотрим этот пример:

for(int i=0;i<height;i++){

    uchar *col = ((uchar *)(data + i*widthStep));

    for(int j=0;j<width;j++){

        double pRed     = col[j*channels + 0];                      
        double pGreen   = col[j*channels + 1];       
        double pBlue    = col[j*channels + 2];       

    }
}

Это уменьшает число кадров в секунду до 11-ти.

Теперь это с другой стороны:

for(int i=0;i<height;i++){

    uchar *col = ((uchar *)(data + i*widthStep));

    for(int j=0;j<width;j++){

        col[j*channels + 0];                      
        col[j*channels + 1];       
        col[j*channels + 2];       

    }
}

не сбрасывает FPSсовсем!FPS остается на уровне 30,0.Я подумал, что я должен обновить это и дать вам знать, что это за настоящая бутылочная горлышко, а переменные не складываются.Интересно, если я встраиваю все, я мог бы получить чистые 30.0fps.

Nvm ... возможно, выражения, которые не назначены для переменной, даже не оцениваются.

Answer 1

sqrt - монотонно возрастающая функция, и вы, похоже, используете ее только в пороговом тесте.

Из-за монотонности, sqrt(sum) < threshold эквивалентно sum < threshold * threshold (при условии, что порог положительный).

Нет более дорогого квадратного корня, и компилятор переместит умножение за пределы цикла.

---

В качестве следующего шага вы можете удалить дорогостоящее умножение j * channels из внутреннего цикла. Компилятор должен быть достаточно умен, чтобы делать это только один раз и использовать результат три раза, но это все равно будет умножение, от которого зависит остальная часть вычислений, поэтому мешает конвейерной обработке.

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

for(int j=0;j<width;j++){
    double pRed     = col[0];
    double pGreen   = col[1];
    double pBlue    = col[2];

    double dRed     = green.val[0] - pRed;
    double dGreen   = green.val[1] - pGreen;
    double dBlue    = green.val[2] - pBlue;

    double sDRed    = dRed * dRed;
    double sDGreen  = dGreen * dGreen;
    double sDBlue   = dBlue * dBlue;


    double sum = sDRed + sDGreen + sDBlue;

    //NSLog(@"%f %f %f", pRed, pGreen, pBlue);

    if (sum < threshold * threshold) {
        col[0] = white.val[0];
        col[1] = white.val[1];
        col[2] = white.val[2];
    }

    col += channels;
}

Далее у вас есть дорогие преобразования между uchar и double. Они не нужны для порогового теста:

int j = width;
do {
    int_fast16_t const pRed   = col[0];
    int_fast16_t const pGreen = col[1];
    int_fast16_t const pBlue  = col[2];

    int_fast32_t const dRed   = green.val[0] - pRed;
    int_fast32_t const dGreen = green.val[1] - pGreen;
    int_fast32_t const dBlue  = green.val[2] - pBlue;

    int_fast32_t const sDRed   = dRed * dRed;
    int_fast32_t const sDGreen = dGreen * dGreen;
    int_fast32_t const sDBlue  = dBlue * dBlue;

    int_fast32_t const sum = sDRed + sDGreen + sDBlue;

    //NSLog(@"%f %f %f", pRed, pGreen, pBlue);

    if (sum < threshold * threshold) {
        col[0] = white.val[0];
        col[1] = white.val[1];
        col[2] = white.val[2];
    }

    col += channels;
} while (--j);

Answer 2

Ну, не зная, что делает ваш алгоритм, если вы хотите немного улучшить его, вы можете избавиться от этого sqrt вызова. Просто замените:

double euc = sqrt(sum);

if (euc < threshold) {
    ....
}

Автор:

if (sum < threshold_2) {
    ....
}

Где threshold_2 равно threshold * threshold, которое можно предварительно рассчитать и вынуть из циклов.

Это немного повысит производительность, но не стоит ожидать слишком много.

Answer 3

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

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

Если вы действительно действительно должны оптимизировать этот код, лучший способ сделать это - использовать инструкции MMX и SIMD, чтобы по существу векторизовать все двойные «тройки» в одну инструкцию.

Answer 4

Если вы работаете в Linux, взгляните на oprofile и утилиту perf (поставляется с исходным кодом ядра).

Кстати, код в UPDATE2, скорее всего, ничего не делает, он компилируется, так как эффекты выражений нигде не хранятся.В таких случаях компилятор решает вообще не помещать его в вывод.Скомпилируйте код с помощью -S (вывод ассемблера) и посмотрите.

Answer 5

Учитывая ваш комментарий, что col[j*channels + 0]; отнимает много времени: channels всегда 3? или даже всегда 4? Если это так, вы можете избежать математики смещения, просто продвигая указатель, например так:

for(int i=0;i<height;i++){
   uchar *col = ((uchar *)(videoFrame->imageData + i*widthStep));   
   for(int j=0;j<width;j++){
      double dRed     = green.val[0] - *col++;   
      double dGreen   = green.val[1] - *col++;  
      double dBlue    = green.val[2] - *col++; 

   //math here

   if (euc < thresholdSqrd) {
     *(col-3) = white.val[0];
     *(col-2) = white.val[1];
     *(col-1) = white.val[2];
   }
   col++; //do this only if `channels`==4
}

Кроме того, поскольку ваши необработанные данные выглядят как rgb как последовательные байты, вы можете установить пиксель в белый цвет, используя *(int32_t*)(col-3) |= 0xFFFFFF;

А вычитание в виде целых чисел может быть немного быстрее (хранить green в виде целых чисел):

      int16_t iRed     = green.val[0] - *col++;   
      int16_t iGreen   = green.val[1] - *col++;  
      int16_t iBlue    = green.val[2] - *col++; 
      double euc = (double)iRed*iRed + iGreen*iGreen + iBlue*iBlue;

Answer 6

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

Answer 7

sqrt является довольно медленным.почему бы вам не вычислить double threshold_sq = threshold * threshold; перед внешним циклом и использовать sum < threshold_sq для сравнения.Кроме того, ключевое слово restrict может или не может помочь вам немного.

Answer 8

Вы используете вложенный for loops, но я не вижу, чтобы вы использовали переменную из вашего внешнего цикла вообще. Если написанное действительно правильно, я бы посоветовал вам изменить внешний for loop, который изменит ваше время работы с O(n^2) на O(n).