Efficiently amalgamate duplicate pixels (by summing) from sparse representation using Python/numpy

user_435129 0
Viewed 81

Suppose I have a list of (greyscale) pixels, e.g.

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

So, e.g. the second pixel is at location (14, 7) with intensity 0.7

NOTE: x is always non-decreasing in this list. So p > q => x[p] >= x[q].

However the same pixel may be revisited. In my example, pixels #1 and #3 have coordinates (14, 7).

How to efficiently amalgamate the duplicates? So that in my example, I get:

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

NOTE: Order isn't important, so it may help to sort by increasing y for pixels with a given x.

NOTE: x, y, V came from cols of a matrix M. What I am to do could be considered as a 2-D histogram or cumulative sum.

IDEA: I could map x, y -> x + y*nPixelsX, so now I'm dealing with pairs, e.g. (1073, 0.4), (1071, 1.8), (1073, 0.7) which I could sort.

EDIT: This is the problem I am actually trying to solve (code is Python despite variable glyphs):

# 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

What I'm doing isn't great. I'm writing sparse data to a bitmap so as to solve this "multiple trades on the same pixel" problem, then sparsifying the bitmap to flatten the trades, then recombining.

I need to be working with sparse data all the way to the end, I think.

duplicates numpy arrays python
2 Answers

I'd start by sorting the arrays using 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]

It's fairly easy to identify duplicates among the coordinates using np.diff and np.flatnonzero:

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

The problem is that this does not make it easy to process the case where you have multiple duplicate of the same pixel. I propose instead that you generate an index of all the non-duplicates, with some small modifications:

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

The really neat thing is that all duplicates, even multiple visits will be simply missing from diff. That means that you can pass it directly to np.add.reduceat:

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

You can delete duplicate coordinates using np.delete:

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

If you care about the original sort order, you can use the fact that np.argsort is its own inverse. That means that to return the arrays to original order, you need to delete same + 1 from i and argsort it to reinstate the order:

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

Keep in mind that when we deleted same from x and y, we were keeping the last duplicated element. To preserve the order, you likely want to keep the first element, hence same + 1.

If you are OK with simply reconstructing an image, the task becomes infinitely simpler, since you can use np.add.at to accumulate the pixels directly in an unbuffered manner:

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

And indeed you can see that

>>> img[7, 14]
0.8999999999999999

Contrast with img[y, x] += V, which is buffered, and will therefore discard duplicates.

user_29887300

I have been trying to develop a purely numpy way of doing this however I am not currently successful, however I am able to come up with one using pandas if that is acceptable:

bitmap = np.zeros((15, 16))

## generate data 
s_x = np.array([a for a in range(-5,18)], dtype=int)
s_x = np.repeat(s_x, 2)
s_y = np.array([a for a in range(-3,20)], dtype=int)
s_y = np.repeat(s_y, 2)

np.random.shuffle(s_x)
np.random.shuffle(s_y)

## make sure there are some repeats 
s_x = np.concatenate((s_x, s_x[:5]))
s_y = np.concatenate((s_y, s_y[:5]))

pixel_count = s_x.shape[0]
pixel_val = np.random.rand(pixel_count)

# ## generate is done 

start = time.time()

## create dataframe
df = pd.DataFrame({'s_x':s_x, 's_y':s_y, 'pixel_val': pixel_val})

## remove pixels outside the image
df = df[(s_x >= 0)*(s_x < bitmap.shape[1])*(s_y >= 0)*(s_y < bitmap.shape[0])]

## sum duplicate pixels 
pixel_val = df.groupby(['s_x', 's_y'])['pixel_val'].transform('sum')

## get the index of the unique pixel locations 
use = pixel_val.index

bitmap[s_y[use], s_x[use]] = pixel_val

end = time.time()

print(end- start)

plt.imshow(bitmap)

source: Pandas Sum of Duplicate Attributes

output:

enter image description here

user_134672240
Related