Compress labels in "sparse array" (CCL ouput) reduction

I have a 5 million list of 32 bit integers (actually a 2048 x 2560 image) that is 90% zeros. The non-zero cells are labels (e.g. 2049, 8195, 1334300, 34320923, 4320932) that completely not sequential or consecutive in any way (it is the output of our custom component labeling CCL algorithm).

How do I go about revising these cells (labels) so that they are the sequence 1,2,3,4… that is completely monotonically increasing. e.g. if cell [1999, 2043] = 2343324; I want it to be a unique value from the set [1,2,3, …] I do not want the data moved (to front). Just the labels changed. ( I am guessing some sort of reduction, maybe prefix sum, but I need a little more hints). I am working with a NVIDA Tesla K40.

Cross reference:

http://stackoverflow.com/questions/28797147/compress-sparse-data-with-cuda-component-labeling-reduction