Fast random to unique relabeling of numpy 2d regions (without loops)
<p>I have a large numpy 2d array (10000,10000) in which regions (clusters of cells with the same number) are randomly labeled. As a result, some separate regions were assigned to the same label. What I would like is to relabel the numpy 2d array so that all separate regions are assigned to a unique label (see example).</p>

<p>I now how to solve this problem with a loop. But as I am working with a large array with a lot of small regions, this process takes ages. Therefore, a vectorized approach would be more suitable.</p>

<p>Example:</p>

<p>-Two separate regions are labeled with 1<br>
-Two separate regions are
   labeled with 3</p>

<pre><code>## Input
random_arr=np.array([[1,1,3,3],[1,2,2,3],[2,2,1,1],[3,3,3,1]])
</code></pre>

<p><a href="http://i.stack.imgur.com/jJcuz.png" rel="nofollow"><img src="http://i.stack.imgur.com/jJcuz.png" alt="random"></a></p>

<pre><code>## Apply function
unique_arr=relabel_regions(random_arr)
## Output
&gt;&gt;&gt; unique_arr
array([[1, 1, 3, 3],
       [1, 2, 2, 3],
       [2, 2, 4, 4],
       [5, 5, 5, 4]])
</code></pre>

<p><a href="http://i.stack.imgur.com/KKifw.png" rel="nofollow"><img src="http://i.stack.imgur.com/KKifw.png" alt="unique"></a></p>

<p>Slow solution with loop:</p>

<pre><code>def relabel_regions(random_regions):
    # Locate random regions index
    random_labs=np.unique(random_regions)

    unique_segments=np.zeros(np.shape(random_regions),dtype='uint64')
    count=0
    kernel=np.array([[0,1,0],[1,1,1],[0,1,0]],dtype='uint8')
    # Assign unique number to each random labeled region
    for i in range(len(random_labs)):
        mask=np.zeros(np.shape(random_regions))
        mask[np.where(random_regions==random_labs[i])]=1
        labeled_mask, freq = ndimage.label(mask, structure=kernel)
        labeled_mask=labeled_mask+count
        unique_segments[np.where(labeled_mask&gt;0+count)]=labeled_mask[np.where(labeled_mask&gt;0+count)]
        count+=freq
    return unique_segments
</code></pre>

<p>Let's cheat and just use some high-quality library (<a href="http://scikit-image.org/" rel="nofollow">scikit-image</a>) which offers exactly this.</p>

<p>You may learn from it's implementation or just use it!</p>

<pre><code>import numpy as np
from skimage.measure import label

random_arr = np.array([[1,1,3,3],[1,2,2,3],[2,2,1,1],[3,3,3,1]])
labels = label(random_arr, connectivity=1)  # neighborhood-definition here!

print(labels)
</code></pre>

<h3>Output</h3>

<pre><code>[[1 1 2 2]
 [1 3 3 2]
 [3 3 4 4]
 [5 5 5 4]]
</code></pre>

<p><strong>EDIT:</strong> Like mentioned by Jeon in the comments, scipy's <a href="http://docs.scipy.org/doc/scipy-0.16.0/reference/generated/scipy.ndimage.measurements.label.html" rel="nofollow">scipy.ndimage.measurements.label</a> might also be a candidate if one does not want to use one more extra library! Thanks for the comment Jeon!</p>

python arrays numpy scipy vectorization