Optimisation HOG avec utilisation de SIMD

Question

Il existe plusieurs tentatives pour optimiser le calcul du descripteur HOG en utilisant des instructions SIMD: OpenCV, Dlib et Simd. Tous utilisent le code scalaire pour ajouter amplitude résultant à histogramme 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]; 
} 

Il la valeur de size dépend de la mise en œuvre, mais en général, le sens est le même.

Je sais que le problème de histogram calculation with using of SIMD n'a pas une solution simple et efficace. Mais dans ce cas, nous avons une petite taille (18) d'histogramme. Peut-il aider dans les optimisations SIMD?

Answer 1

J'ai trouvé une solution. C'est un tampon temporel. Au début, nous additionnons l'histogramme au tampon temporaire (et cette opération peut être vectorisée). Ensuite, nous ajoutons la somme de tampon à l'histogramme de sortie (et cette opération peut être vectorisé aussi):

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]; 
} 

Answer 2

Vous pouvez effectuer une optimisation partielle en utilisant SIMD pour calculer tous les indices d'histogramme (aplatis) et les incréments de bac. Puis les traiter dans une boucle scalaire après. Vous avez probablement aussi besoin de strip-mine ceci de sorte que vous traitez une ligne à la fois, afin de garder les index et les incréments de la corbeille temporaire dans le cache. Il pourrait sembler que ce serait inefficace, en raison de l'utilisation de tampons intermédiaires temporaires, mais en pratique, j'ai vu un gain global utile dans des scénarios similaires.

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 
    } 

}