Оптимизация HOG с использованием SIMD

Question

Оптимизация HOG с использованием SIMD

Существует несколько попыток оптимизировать вычисление дескриптора HOG с использованием инструкций SIMD: OpenCV, Dlib, а также Симд. Все они используют скалярный код для добавления результирующей величины к гистограмме HOG:

float histogram[height/8][width/8][18];
float ky[height], kx[width];
int idx[size];
float val[size];

for(size_t i = 0; i < size; ++i)
{
histogram[y/8][x/8][idx[i]] += val[i]*ky[y]*kx[x];
histogram[y/8][x/8 + 1][idx[i]] += val[i]*ky[y]*kx[x + 1];
histogram[y/8 + 1][x/8][idx[i]] += val[i]*ky[y + 1]*kx[x];
histogram[y/8 + 1][x/8 + 1][idx[i]] += val[i]*ky[y + 1]*kx[x + 1];
}

Там значение size зависит от реализации, но в целом смысл тот же.

Я знаю эту проблему расчет гистограммы с использованием SIMD не имеет простого и эффективного решения. Но в этом случае мы имеем маленький размер (18) гистограммы. Это может помочь в оптимизации SIMD?

1

c++dlib opencv simd simd-library

Решение

Другие решения

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

uint32_t i = 0;

for (y = 0; y < height; ++y)   // for each row
{
uint32_t inds[width * 4];  // flattened histogram indices for this row
float vals[width * 4];     // histogram bin increments for this row

// SIMD loop for this row - calculate flattened histogram indices and bin
// increments (scalar code shown for reference - converting this loop to
// SIMD is left as an exercise for the reader...)

for (x = 0; x < width; ++x, ++i)
{
indices[4*x]   = (y/8)*(width/8)*18+(x/8)*18+idx[i];
indices[4*x+1] = (y/8)*(width/8)*18+(x/8 + 1)*18+idx[i];
indices[4*x+2] = (y/8+1)*(width/8)*18+(x/8)*18+idx[i];
indices[4*x+3] = (y/8+1)*(width/8)*18+(x/8 + 1)*18+idx[i];

vals[4*x]   = val[i]*ky[y]*kx[x];
vals[4*x+1] = val[i]*ky[y]*kx[x+1];
vals[4*x+2] = val[i]*ky[y+1]*kx[x];
vals[4*x+3] = val[i]*ky[y+1]*kx[x+1];
}

// scalar loop for this row

float * const histogram_base = &histogram[0][0][0]; // pointer to flattened histogram

for (x = 0; x < width * 4; ++x) // for each set of 4 indices/increments in this row
{
histogram_base[indices[x]] += vals[x];  // update the (flattened) histogram
}

}

0

Источник

Accepted Answer

Я нашел решение. Это временный буфер. Сначала мы суммируем гистограмму во временный буфер (и эта операция может быть векторизована). Затем мы добавляем сумму из буфера к выходной гистограмме (и эту операцию также можно векторизовать):

float histogram[height/8][width/8][18];
float ky[height], kx[width];
int idx[size];
float val[size];
float buf[18][4];

for(size_t i = 0; i < size; ++i)
{
buf[idx[i]][0] += val[i]*ky[y]*kx[x];
buf[idx[i]][1] += val[i]*ky[y]*kx[x + 1];
buf[idx[i]][2] += val[i]*ky[y + 1]*kx[x];
buf[idx[i]][3] += val[i]*ky[y + 1]*kx[x + 1];
}

for(size_t i = 0; i < 18; ++i)
{
histogram[y/8][x/8][i] += buf[i][0];
histogram[y/8][x/8 + 1][i] += buf[i][1];
histogram[y/8 + 1][x/8][i] += buf[i][2];
histogram[y/8 + 1][x/8 + 1][i] += buf[i][3];
}

1