python - 使用 Python/numpy 从稀疏表示中有效地合并重复像素(通过求和)

Question

假设我有一个(灰度)像素列表，例如

x = np.array([13, 14, 14, 14, 15])
y = np.array([ 2,  7,  5,  7,  8])
V = np.array([.3, .7, .4, .2, .1])

所以，例如第二个像素位于位置 (14, 7)强度 0.7注意: x在此列表中始终不减少。所以 p > q => x[p] >= x[q] .
然而，可以重新访问相同的像素。在我的例子中，像素 #1和 #3有坐标 (14, 7) .
如何有效地合并重复项？所以在我的例子中，我得到:

x2 = np.array([ 13, 14    , 14, 15 ])
y2 = np.array([  2,  7    ,  5,  8 ])
V2 = np.array([ .3, .7+.2 , .4, .1 ])

注意:顺序并不重要，因此通过增加 y 进行排序可能会有所帮助。对于具有给定 x 的像素.
注意:x、y、V 来自矩阵 M 的列。我要做的可以被视为二维直方图或累积总和。
想法:我可以映射 x, y -> x + y*nPixelsX ，所以现在我正在处理对，例如 (1073, 0.4), (1071, 1.8), (1073, 0.7)我可以排序。

编辑:这是我实际试图解决的问题(尽管字形可变，但代码是 Python):

# split columns of tradematrix into 1D numpy arrays
time_ms, price, vol, buyer_is_maker = ᬑ.ᘐA.T

# TODO: https://stackoverflow.com/questions/67191535/efficiently-plot-set-of-coordinatevalues-to-numpy-array-bitmap

# convert time,price to pixel x,y coords
x = pX(time_ms)
y = pY(price)

brightness = vol
rgb_channel = np.where(buyer_is_maker, 2, 1)  # cv2 uses BGR not RGB

# make a clear canvas
𐌎f = np.zeros((ᬑ.pixelsY, ᬑ.pixelsX, 3))

# additively plot trades
for i in range(len(ᬑ.ᘐA)):
    try:
        𐌎f[y[i],x[i],rgb_channel[i]] += brightness[i]
    except:
        # don't plot offscreen coords
        # try/catch is waaay faster than doing if on_screen(x[i],y[i]):
        pass

# flatten dynamic range (as some trades are huge)
# ... by doing `w -> log(1+w)` 3 times

# # This was the original (slow) code
# for _ in range(3):
#     𐌎f = np.log(1+𐌎f)  # any 0 pixel maps back to 0 (log 1 = 0)

# sped up!
sparse_red = coo_matrix(𐌎f[:,:,2])
sparse_green = coo_matrix(𐌎f[:,:,1])
for _ in range(3):
    np.log(1+sparse_red.data, sparse_red.data)  # perform operation in place
    np.log(1+sparse_green.data, sparse_green.data)  # perform operation in place
𐌎f[:,:,2] = sparse_red.todense()
𐌎f[:,:,1] = sparse_green.todense()

# normalize canvas
sup = np.max(𐌎f)
if sup > 0:
    𐌎f /= sup

我正在做的事情并不好。我正在将稀疏数据写入位图，以解决“同一像素上的多次交易”问题，然后对位图进行稀疏化以展平交易，然后重新组合。
我想，我需要一直使用稀疏数据直到结束。

Answer 1

我首先使用 np.lexsort 对数组进行排序:

i = np.lexsort([y, x])  # [0, 2, 1, 3, 4]
y = y[i]                # [2, 5, 7, 7, 8]
x = x[i]                # [13, 14, 14, 14, 15]
V = V[i]                # [0.3, 0.4, 0.7, 0.2, 0.1]

使用 np.diff 很容易识别坐标中的重复项和 np.flatnonzero :

mask = (np.diff(x) == 0) & (np.diff(y) == 0)
same = np.flatnonzero(mask)  # [2]

问题在于，如果您有多个相同像素的副本，这并不容易处理。我建议您生成所有非重复项的索引，并进行一些小的修改:

diff = np.r_[0, 1 + np.flatnonzero(~mask)]

真正巧妙的是， diff 中会丢失所有重复项，甚至多次访问。 .这意味着您可以将其直接传递给 np.add.reduceat :

V = np.add.reduceat(V, diff)

您可以使用 np.delete 删除重复坐标:

x = np.delete(x, same)
y = np.delete(y, same)

如果您关心原始排序顺序，则可以使用 np.argsort 的事实。是它自己的逆。这意味着要将数组恢复到原始顺序，您需要删除 same + 1来自 i并对其进行 argsort 以恢复订单:

i = np.delete(i, same + 1).argsort()
x = x[i]
y = y[i]
V = V[i]

请记住，当我们删除 same 时来自 x和 y ，我们保留了最后一个重复的元素。为了保持顺序，您可能希望保留第一个元素，因此 same + 1 .

如果您可以简单地重建图像，那么任务将变得无限简单，因为您可以使用 np.add.at 以无缓冲的方式直接累积像素:

nPixelsY = 16
nPixelsX = 16
img = np.zeros((nPixelsY, nPixelsX))
np.add.at(img, (y, x), V)

你确实可以看到

>>> img[7, 14]
0.8999999999999999

对比 img[y, x] += V ，这是缓冲的，因此将丢弃重复项。