How to create a 4 or 8 connected adjacency matrix

Question

I have been looking for a python implementation that returns a 4- or 8-connected adjacency matrix, given an array. I find it surprising that cv2 or networkx don't include this functionality. I came across this great Matlab implementation and decided to make something similar in python.

Problem: I'm looking for an implementation that improves on the linked Matlab solution in runtime / space OR other interesting approaches.

Disclaimer:

I submit my own implementation here as I figure I can't be the only person who will ever need to create an (4 / 8 connected) adjacency matrix for image processing or other applications. It is my hope that improvements or better implementations will be offered.

Answer 1

Using the diagonal structure, as detailed in this answer regarding "Construct adjacency matrix in MATLAB", I create only the upper diagonals and add them in the appropriate positions to a sparse diagonal matrix using scipy.sparse.diags. This sparse matrix is added to its transpose to give us the adjacency matrix.

When working with images it is often desirable to break up the image into non-overlapping rectangular sub-images or patches. The patch_size parameter is a tuple (rows, cols) that describes the rectangular patch of size 'rows x cols'.

import numpy as np
import scipy.sparse as s

def connected_adjacency(image, connect, patch_size=(1, 1)):
    """
    Creates an adjacency matrix from an image where nodes are considered adjacent 
    based on 4-connected or 8-connected pixel neighborhoods.

    :param image: 2 or 3 dim array
    :param connect: string, either '4' or '8'
    :param patch_size: tuple (n,m) used if the image will be decomposed into 
                   contiguous, non-overlapping patches of size n x m. The 
                   adjacency matrix will be formed from the smaller sized array
                   e.g. original image size = 256 x 256, patch_size=(8, 8), 
                   then the image under consideration is of size 32 x 32 and 
                   the adjacency matrix will be of size 
                   32**2 x 32**2 = 1024 x 1024
    :return: adjacency matrix as a sparse matrix (type=scipy.sparse.csr.csr_matrix)
    """

    r, c = image.shape[:2]

    r = r / patch_size[0]
    c = c / patch_size[1]

    if connect == '4':
        # constructed from 2 diagonals above the main diagonal
        d1 = np.tile(np.append(np.ones(c-1), [0]), r)[:-1]
        d2 = np.ones(c*(r-1))
        upper_diags = s.diags([d1, d2], [1, c])
        return upper_diags + upper_diags.T

    elif connect == '8':
        # constructed from 4 diagonals above the main diagonal
        d1 = np.tile(np.append(np.ones(c-1), [0]), r)[:-1]
        d2 = np.append([0], d1[:c*(r-1)])
        d3 = np.ones(c*(r-1))
        d4 = d2[1:-1]
        upper_diags = s.diags([d1, d2, d3, d4], [1, c-1, c, c+1])
        return upper_diags + upper_diags.T
    else:
        raise ValueError('Invalid parameter \'connect\'={connect}, must be "4" or "8".'
                     .format(connect=repr(connect)))

A simple example:

a = np.arange(9).reshape((3, 3))
adj = connected_adjacency(a, '4').toarray()
print a

[[0 1 2]
 [3 4 5]
 [6 7 8]]

print adj

[[ 0.  1.  0.  1.  0.  0.  0.  0.  0.]
 [ 1.  0.  1.  0.  1.  0.  0.  0.  0.]
 [ 0.  1.  0.  0.  0.  1.  0.  0.  0.]
 [ 1.  0.  0.  0.  1.  0.  1.  0.  0.]
 [ 0.  1.  0.  1.  0.  1.  0.  1.  0.]
 [ 0.  0.  1.  0.  1.  0.  0.  0.  1.]
 [ 0.  0.  0.  1.  0.  0.  0.  1.  0.]
 [ 0.  0.  0.  0.  1.  0.  1.  0.  1.]
 [ 0.  0.  0.  0.  0.  1.  0.  1.  0.]]

Using networkx + matplotlib to plot the adjacency matrix as a graph: