How to create 4 or 8 related adjacency matrices
I was looking for a python implementation that returns a 4- or 8-connected adjacency matrix given by an array. Surprisingly, cv2 or networkx doesn't include this functionality. I came across this wonderful Matlab implementation and decided to do something similar in python.
Problem . I'm looking for an implementation that improves on Matlab's linked solution at runtime / space, or other interesting approaches.
Renouncement
I am presenting my own implementation here, as I believe I may not be the only person who ever needs to create a (4/8) adjacency matrix for image processing or other applications. I hope that improvements or better implementations will be suggested.
source to share
Using the diagonal structure detailed in this answer regarding "Constructacality matrix in MATLAB", I create only the top diagonals and add them at the appropriate positions to the sparse diagonal matrix using scipy.sparse.diags . This sparse matrix is added to its transposition to give us an adjacency matrix.
When working with images, it is often desirable to split the image into non-overlapping rectangular sub-images or patches. The patch_size parameter is a tuple (rows, columns) that describes a "rows x cols" rectangular patch.
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)))
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:
source to share