高效地找到標記圖像區域的質心

我有一個分割圖像作爲獨特標籤1 ... k的2維矩陣。例如：高效地找到標記圖像區域的質心

img = 
    [1 1 2 2 2 2 2 3 3] 
    [1 1 1 2 2 2 2 3 3] 
    [1 1 2 2 2 2 3 3 3] 
    [1 4 4 4 2 2 2 2 3] 
    [4 4 4 5 5 5 2 3 3] 
    [4 4 4 5 5 6 6 6 6] 
    [4 4 5 5 5 5 6 6 6]

我想確定區域的質心。也就是說，根據標籤，質心的X，Y座標是什麼？例如，標籤1的質心是（1.25，0.625）。我只知道行數（(0 + 0 + 1 + 1 + 1 + 2 + 2 + 3)/8 = 1.25）和列數（(0 + 0 + 0 + 0 + 1 + 1 + 1 + 2)/8 = 0.625）

我知道如何做到這一點的唯一方法是使用for循環從1到k（或在我的例子中，1到6），找到每個標籤點的索引，並通過索引圖像的網格來平均它們的座標。

但是，我正在尋找以GPU計算優化的方式做到這一點。因此，使用for循環並不理想（在一個漂亮的GPU上，每個圖像需要花費大約1秒時間才能完成幾百個標籤）。我正在使用PyTorch，但真正的任何numpy解決方案都應該足夠了。

是否有GPU高效的解決方案來完成此任務？

來源

2017-10-20 marcman

這個計算需要積累，我不知道它在GPU上有多高效。這是僞代碼的順序算法：

int n[k] = 0 
int sx[k] = 0 
int sy[k] = 0 
loop over y: 
    loop over x: 
     i = img[x,y] 
     ++n[i] 
     sx[i] += x 
     sy[i] += y 
for i = 1 to k 
    sx[i] /= n[i] 
    sy[i] /= n[i]

然後當然，(sx[i],sy[i])是對象i的重心。

它在CPU上真的很快，除非它已經存在，否則不值得將數據發送到GPU。

來源

2017-10-20 01:24:01

是的這是我可以提出的最佳解決方案。數據已經在GPU上，因此我爲什麼要這麼做： - /。我會看看CPU如何去。這當然是高效的 - 每一個像素都會觸及一次，但我想知道是否有辦法在GPU上實現並行化... – marcman

有一件事你可以做，如果上述算法的天真GPU實現是太慢了，就是爲每個圖像列創建數組'n'，'sx'和'sy'，然後將它們添加到一起。這可能會減少等待對數組值進行原子更新的內核數量。 –

我不確定，以原子方式更新全局數組中的單個值是否有效？你在GPU上獲得虛假分享問題嗎？ –

考慮使用scikit-image或重新使用它們的code（基於numpy/scipy）。

這裏是一個演示：

import numpy as np 
from skimage import measure 
from time import perf_counter as pc 

img = np.array([[1, 1, 2, 2, 2, 2, 2, 3, 3], 
       [1, 1, 1, 2, 2, 2, 2, 3, 3], 
       [1, 1, 2, 2, 2, 2, 3, 3, 3], 
       [1, 4, 4, 4, 2, 2, 2, 2, 3], 
       [4, 4, 4, 5, 5, 5, 2, 3, 3], 
       [4, 4, 4, 5, 5, 6, 6, 6, 6], 
       [4, 4, 5, 5, 5, 5, 6, 6, 6]]) 

# assuming already labels of 1, 2, ... n 
times = [pc()] 
props = measure.regionprops(img) 
times.append(pc()) 
for i in range(np.unique(img).shape[0]): 
    print(props[i].centroid) 
    times.append(pc()) 

print(np.diff(times))

輸出：

(1.25, 0.625) 
(1.5555555555555556, 4.4444444444444446) 
(1.8999999999999999, 7.4000000000000004) 
(4.3636363636363633, 1.1818181818181819) 
(5.1111111111111107, 3.6666666666666665) 
(5.4285714285714288, 6.7142857142857144) 
[ 9.05569615e-05 8.51235438e-04 2.48126075e-04 2.59294767e-04 
    2.42692657e-04 2.00734598e-04 2.34542530e-04]

來源

2017-10-20 02:08:49 sascha

一種想法是使用bincount累積的行索引和列索引爲使用數字輸入陣列中的每個區域該箱，因此有一個矢量化的解決方案，像這樣 -

m,n = a.shape 
r,c = np.mgrid[:m,:n] 
count = np.bincount(a.ravel()) 
centroid_row = np.bincount(a.ravel(),r.ravel())/count 
centroid_col = np.bincount(a.ravel(),c.ravel())/count

Sa mple run -

In [77]: a 
Out[77]: 
array([[1, 1, 2, 2, 2, 2, 2, 3, 3], 
     [1, 1, 1, 2, 2, 2, 2, 3, 3], 
     [1, 1, 2, 2, 2, 2, 3, 3, 3], 
     [1, 4, 4, 4, 2, 2, 2, 2, 3], 
     [4, 4, 4, 5, 5, 5, 2, 3, 3], 
     [4, 4, 4, 5, 5, 6, 6, 6, 6], 
     [4, 4, 5, 5, 5, 5, 6, 6, 6]]) 

In [78]: np.c_[centroid_row, centroid_col] 
Out[78]: 
array([[ nan, nan], 
     [ 1.25, 0.62], # centroid for region-1 
     [ 1.56, 4.44], # centroid for region-2 
     [ 1.9 , 7.4 ], # centroid for region-3 and so on. 
     [ 4.36, 1.18], 
     [ 5.11, 3.67], 
     [ 5.43, 6.71]])

來源

2017-10-20 05:24:14 Divakar

高效地找到標記圖像區域的質心

回答

相關問題