消除分支當在二進制數{0，255}尋找中值圖像

我有一個二進制圖像，所述二進制值是0或255中的圖像數據的類型是無符號字符。在這裏，我需要對此圖像進行中值濾波。消除分支當在二進制數{0，255}尋找中值圖像

我想用直方圖發現平均要快。使用一些代碼來解釋：

unsigned int hist[2] = {0, 0}; 

for (int i = 0; i < kernel_h; ++i) { 
    for (int j = 0; j < kernel_w; ++j) { 
      if (image(i,j) == 0) { 
       hist[0]++; 
      } 
      else { 
       hist[1]++; 
      } 
    } 
}

然後，我們可以得到非常快的中值。但由於這種情況下，代碼仍然可以改進：

int counter = 0; 

for (int i = 0; i < kernel_h; ++i) { 
    for (int j = 0; j < kernel_w; ++j) { 
      if (image(i,j) == 0) { 
       counter++ 
      } 
      else { 
       counter--; 
      } 
    } 
}

但我不知道有沒有消除的if-else分支，如使用位操作來映射{0，255}的東西那麼一些其他的方式我們可以更新一個沒有分支的標誌。

任何人的任何建議？

來源

2013-10-04 blackball

是矢量一個選擇？你在哪個平臺上？使用SSE，NEON或DSP擴展，二進制映像上的3x3和5x5中值濾波器可以在x86和ARM處理器上簡單地進行矢量化。在字節大小的數據上，您應該能夠使用SSE一次處理16個像素。 –

的255所有位是1，因此可以簡化，「如果」來：

hist[image(i,j) & 1]++;

如果你想使用計數器，你可以這樣做：

counter += (image(i,j) & 2)-1;

來源

2013-10-04 06:20:46 Joni

哇！非常感謝！ – blackball

'counter'示例可以進一步簡化。你正在執行'kernel_h * kernel_w'減去-1，它們很容易從循環中升到單個'counter - kernel_w * kernel_h'。 – MSalters

@EricPostpischil：'＆2'給你+2或0.原始代碼使用counter ++和counter--，所以+1和-1。每個像素的差異是一個常數-1。 – MSalters

這種計算可以製成更快，更具體地說，像素數量和內核大小無關。

這個想法是先做一個計算summed area table的「掃描轉換」，其中每個（x，y）像素的值被從（0,0）到（x，y）。

鑑於這種你可以使用

st(x0, y0) + st(x1, y1) - st(x0, y1) - st(x1, y0)

並給予每個像素爲0或1的和給你的人的數量在固定的時間多的像素是如何在任何RECT設置知道。

總計算時間是O(n)建立和表和O(n)做中值濾波，不管有多大的計算區域。

在中位數的情況下過濾，你可以預先計算取決於總和和在內部循環式的結果可能是：

result[x] = res[p0[x] + p1[x+box] - p0[x+box] - p1[x]];

此外總和表不需要被完全計算（由此每個像素需要一個整數），但可以在執行結果時「懶惰」地計算出來，並且只需要與內核高度一樣多的表格行數仍然保持計算時間O(image_width*image_height)但只需要kernel_height*image_width內存。

來源

2013-10-04 06:29:37 6502

是的，你是對的，如果圖像或內核相對較大，使用積分圖像（或彙總表）可能會更好。但是爲了實現這個算法，我們需要另一個內存緩衝區塊，並且對於每個內核窗口，我們必須進行分割以獲得* 1 *的數量。這裏我的核心尺寸很小，例如3x3或5x5，圖像尺寸也很小。所以我選擇了直接的方式來完成我的工作。 – blackball

@ user1786323：請參閱編輯。通過使用帶有'kernel_area'元素的查找表可以簡單地避免分割。 – 6502

消除分支當在二進制數{0，255}尋找中值圖像

回答

相關問題