Region connectivity graphs in Python [edit: minor bug]

[edit] Nowadays you can find  much better implementations of this over at scikit-image.[/edit]
Recently I started playing with CRFs on superpixels for image segmentation.

While doing this I noticed that Python has very little methods for morphological operations on images. For example I did not find any functions to exctract connected components inside images.

For CRFs one obviously needs the superpixel neighbourhood graph to work on and I didn't find any ready made function to obtain it.

After some pondering, I came up with something. Since I didn't find anything else online
I thought I'd share it.

def make_graph(grid):
    # get unique labels
    vertices = np.unique(grid)

    # map unique labels to [1,...,num_labels]
    reverse_dict = dict(zip(vertices,np.arange(len(vertices))))
    grid = np.array([reverse_dict[x] for x in grid.flat]).reshape(grid.shape)
  
    # create edges
    down = np.c_[grid[:-1, :].ravel(), grid[1:, :].ravel()]
    right = np.c_[grid[:, :-1].ravel(), grid[:, 1:].ravel()]
    all_edges = np.vstack([right, down])
    all_edges = all_edges[all_edges[:, 0] != all_edges[:, 1], :]
    all_edges = np.sort(all_edges,axis=1)
    num_vertices = len(vertices)
    edge_hash = all_edges[:,0] + num_vertices * all_edges[:, 1]
    # find unique connections
    edges = np.unique(edge_hash)
    # undo hashing
    edges = [[vertices[x%num_vertices],
              vertices[x/num_vertices]] for x in edges] 

    return vertices, edges

This code assumes a grid is given to it with uniquely labeled connected components.
First, the unique labels are mapped to [1,..,num_labels] (which is not strictly necessary but I ran into problems since my labels were huge).

Then I create "down" and "right" edges using a technique I saw at scikits.learn. I stack the edges and sort them, then hash them and find unique edges.
[edit] I also remove self-connections. Missed that on the first try. [/edit]

Hashing is necessary since "unique" only works on numbers. I could also have used a set, I guess.
Then I undo the hash and I'm done.
I find this code to be pretty fast and I thought it would be a lot more work to do this.
Numpy makes stuff so easy :) - I love it.

Now we want to visualize our graph. I start from the label-image in grid and [vertices, edges]:

# compute region centers:
gridx, gridy = np.mgrid[:grid.shape[0], :grid.shape[1]]
centers = dict()
for v in vertices:
    centers[v] = [gridy[grid == v].mean(), gridx[grid == v].mean()]

# plot labels
plt.imshow(grid)

# overlay graph:
for edge in edges:
    plt.plot([centers[edge[0]][0],centers[edge[1]][0]],
             [centers[edge[0]][1],centers[edge[1]][1]])

And done.

Give it a try together with quickshift.