Utility functions for graph and images

graph_4_adjacency_2_khalimsky(graph, …[, …])	Create a contour image in the Khalimsky grid from a 4 adjacency edge-weighted graph.
khalimsky_2_graph_4_adjacency(khalimsky[, …])	Create a 4 adjacency edge-weighted graph from a contour image in the Khalimsky grid.
get_4_adjacency_graph(shape)	Create an explicit undirected 4 adjacency graph of the given shape.
get_8_adjacency_graph(shape)	Create an explicit undirected 8 adjacency graph of the given shape.
get_4_adjacency_implicit_graph(shape)	Create an implicit undirected 4 adjacency graph of the given shape (edges are not stored).
get_8_adjacency_implicit_graph(shape)	Create an implicit undirected 8 adjacency graph of the given shape (edges are not stored).
get_nd_regular_graph(shape, neighbour_list)	Creates a regular graph of the given shape with the adjacency given as a neighbour_list.
get_nd_regular_implicit_graph(shape, …)	Creates an implicit regular graph of the given shape with the adjacency given as a neighbour_list.
mask_2_neighbours(mask[, center])	Converts as a neighbouring mask as a neighbour list.
match_pixels_image_2d(image1, image2[, …])	Computes a matching between the pixels of two images.

graph_4_adjacency_2_khalimsky(graph, edge_weights, shape, add_extra_border=False)

Create a contour image in the Khalimsky grid from a 4 adjacency edge-weighted graph.

Parameters:

• graph – must be a 4 adjacency 2d graph (Concept CptGridGraph)

• edge_weights – edge weights of the graph

• shape – shape of the graph (deduced from CptGridGraph)

• add_extra_border – if False result size is 2 * shape - 1 and 2 * shape + 1 otherwise

Returns:

a 2d array

khalimsky_2_graph_4_adjacency(khalimsky, extra_border=False, graph=None)

Create a 4 adjacency edge-weighted graph from a contour image in the Khalimsky grid.

Parameters:

• khalimsky – a 2d array

• extra_border – if False the shape of the Khalimsky image is 2 * shape - 1 and 2 * shape + 1 otherwise, where shape is the shape of the resulting grid graph

• graph – a 4-adjacency graph (Concept CptGridGraph) of the correct shape (optional). If not given, a new graph is created.

Returns:

a graph (Concept CptGridGraph) and its edge weights

get_4_adjacency_graph(shape)

Create an explicit undirected 4 adjacency graph of the given shape.

Parameters:

shape – a pair (height, width)

Returns:

a graph (Concept CptGridGraph)

get_8_adjacency_graph(shape)

Create an explicit undirected 8 adjacency graph of the given shape.

Parameters:

shape – a pair (height, width)

Returns:

a graph (Concept CptGridGraph)

get_4_adjacency_implicit_graph(shape)

Create an implicit undirected 4 adjacency graph of the given shape (edges are not stored).

Parameters:

shape – a pair (height, width)

Returns:

a graph (Concept CptGridGraph)

get_8_adjacency_implicit_graph(shape)

Create an implicit undirected 8 adjacency graph of the given shape (edges are not stored).

Parameters:

shape – a pair (height, width)

Returns:

a graph (Concept CptGridGraph)

get_nd_regular_graph(shape, neighbour_list)

Creates a regular graph of the given shape with the adjacency given as a neighbour_list.

See the helper function mask_2_neighbours() to create a suitable neighbour_list.

Example:

Create a 2d 4-adjacency implicit graph of size (13, 24):

>>> graph = get_nd_regular_graph((13, 24), ((-1, 0), (0, -1), (0, 1), (1, 0)))

Create a 3d 6-adjacency implicit graph of size (10, 13, 24):

>>> mask = [[[0, 0, 0], [0, 1, 0], [0, 0, 0]],
>>>         [[0, 1, 0], [1, 0, 1], [0, 1, 0]],
>>>         [[0, 0, 0], [0, 1, 0], [0, 0, 0]]]
>>> neighbours = mask_2_neighbours(mask)
>>> graph = get_nd_regular_graph((10, 13, 24), neighbours)

Parameters:

• shape – a tuple of \(n\) elements representing the dimension of the graph vertices.

• neighbour_list – a 2d array of \(k\) \(n\)-d integer vectors

Returns:

a regular graph

get_nd_regular_implicit_graph(shape, neighbour_list)

Creates an implicit regular graph of the given shape with the adjacency given as a neighbour_list.

See the helper function mask_2_neighbours() to create a suitable neighbour_list.

Example:

Create a 2d 4-adjacency implicit graph of size (13, 24):

>>> graph = get_nd_regular_implicit_graph((13, 24), ((-1, 0), (0, -1), (0, 1), (1, 0)))

Create a 3d 6-adjacency implicit graph of size (10, 13, 24):

>>> mask = [[[0, 0, 0], [0, 1, 0], [0, 0, 0]],
>>>         [[0, 1, 0], [1, 0, 1], [0, 1, 0]],
>>>         [[0, 0, 0], [0, 1, 0], [0, 0, 0]]]
>>> neighbours = mask_2_neighbours(mask)
>>> graph = get_nd_regular_implicit_graph((10, 13, 24), neighbours)

Parameters:

• shape – a tuple of \(n\) elements representing the dimension of the graph vertices.

• neighbour_list – a 2d array of \(k\) \(n\)-d integer vectors

Returns:

an implicit regular graph

mask_2_neighbours(mask, center=None)

Converts as a neighbouring mask as a neighbour list. A neighbouring mask is a \(n\)-d matrix where each strictly positive value represent a neighbour of the center point. The neighbour list is obtained by offsetting the coordinates of those positive values by the coordinates of the center.

The default center is the center of the mask matrix: i.e. mask.shape // 2.

Example:

>>> mask = [[0, 1, 0], [1, 0, 1], [0, 1, 0]]
>>> hg.mask_2_neighbours(mask)
array([[-1, 0], [0, -1], [0, 1], [1, 0]])

>>> mask = [[0, 1, 0], [1, 0, 1], [0, 1, 0]]
>>> center = [2, 1]
>>> hg.mask_2_neighbours(mask)
array([[-2, 0], [-1, -1], [-1, 1], [0, 0]])

>>> mask = [[[0, 0, 0], [0, 1, 0], [0, 0, 0]],
>>>         [[0, 1, 0], [1, 0, 1], [0, 1, 0]],
>>>         [[0, 0, 0], [0, 1, 0], [0, 0, 0]]]
>>> hg.mask_2_neighbours(mask)
array([[-1, 0, 0], [1, 0, 0], [0, -1, 0], [0, 1, 0], [0, 0, -1], [0, 0, 1]])

Parameters:

• mask – a \(n\)-d matrix

• center – a 1d array of size \(n\) (optional)

Returns:

a list of point coordinates

match_pixels_image_2d(image1, image2, max_distance=0.0075, mode='relative')

Computes a matching between the pixels of two images.

The matching is computed by solving a minimum cost bipartite graph matching problem. Any pixel whose value if less than or equal to 0 is considered as a missing pixel and is not matched. The cost of a match between two pixels is the Euclidean distance between the two pixels.

Two pixels are matchable if their distance is less than:

• max_distance * diagonal size if mode is “relative”

• max_distance if mode is “absolute”

The algorithm computes a matching of maximum size and minimum cost between the matchable pixels of both images. The algorithm returns a pair of arrays (sources, targets) representing the edges linking matched pixels:

• sources[i] is the linear index of the source pixel in image_1 of the edge i

• targets[i] is the linear index of the target pixel in image_2 of the edge i

The following figure illustrates the matching of pixels between two images. The blue squares represent the pixels of the first image, the green squares represent the pixels of the second images, and the red lines represent the matching between blue and green pixels.

This function is a reimplementation of the function correspondPixels used to compute boundary based assessment measures of segmentations in the BSDS500 dataset.

Example:

Let’s match two images, with a maximum distance of \(1.3\approx \sqrt(2)\):

>>> im1 = np.asarray([[1, 0, 0, 1, 1],
>>>                   [0, 0, 0, 1, 0],
>>>                   [0, 0, 0, 1, 0],
>>>                   [0, 0, 1, 1, 1]])
>>> im2 = np.asarray([[0, 0, 1, 1, 0],
>>>                   [0, 0, 1, 0, 0],
>>>                   [0, 0, 1, 0, 1],
>>>                   [1, 1, 1, 1, 0]])
>>> hg.match_pixels_image_2d(im1, im2, 1.3, "absolute")
(array([ 3, 4, 8, 13, 17, 18, 19]), array([ 2, 3, 7, 12, 17, 18, 14]))

Hence, pixel 3 of im1 is matched with pixel 2 of im2, pixel 4 of im1 is matched with pixel 3 of im2, and so on.

Parameters:

• image1 – a 2d array representing the first image

• image2 – a 2d array representing the second image

• max_distance – the maximum distance between two pixels to be matched

• mode – “relative” or “absolute”

Returns:

a pair of arrays (sources, targets) representing the edges linking matched pixels