使用SIMD進行HOG優化

Question

有幾個嘗試使用SIMD指令來優化HOG描述符的計算：OpenCV,Dlib和Simd。它們都使用標代碼導致幅度增加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價值取決於從執行，但一般的意義是一樣的。

我知道histogram calculation with using of SIMD的問題沒有一個簡單而有效的解決方案。但在這種情況下，我們有小的直方圖（18）。它可以幫助進行SIMD優化嗎？

Answer 1

我找到了解決辦法。這是一個暫時的緩衝區。首先，我們將直方圖合併到臨時緩衝區（並且此操作可以是矢量化的）。然後，我們從緩衝區添加總和輸出直方圖（這個操作也可以被矢量）：

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

您可以通過使用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 
    } 

}