In this recipe, we will show an application of graph theory in image processing. We will compute connected components in an image. This method will allow us to label contiguous regions of an image, similar to the bucket fill tool of paint programs.
Finding connected components is also useful in many puzzle video games such as Minesweeper, bubble shooters, and others. In these games, contiguous sets of items with the same color need to be automatically detected.
Let's import the packages:
In [1]: import itertools import numpy as np import networkx as nx import matplotlib.colors as col import matplotlib.pyplot as plt %matplotlib inlineWe create a 10 x 10 image where each pixel can take one of three possible labels (or colors):
In [2]: n = 10 In [3]: img = np.random.randint(size=(n, n), low=0, high=3)Now, we create the underlying 2D grid graph encoding the structure of...