Utility functions for graph and images¶

Create a contour image in the Khalimsky grid from a 4 adjacency edgeweighted graph. 

Create a 4 adjacency edgeweighted graph from a contour image in the Khalimsky grid. 

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

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

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


Creates a regular graph of the given 

Creates an implicit regular graph of the given 

Converts as a neighbouring mask as a neighbour list. 

Computes a matching between the pixels of two images. 

graph_4_adjacency_2_khalimsky
(graph, edge_weights, shape, add_extra_border=False)[source]¶ Create a contour image in the Khalimsky grid from a 4 adjacency edgeweighted 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)[source]¶ Create a 4 adjacency edgeweighted 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 4adjacency 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)[source]¶ 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)[source]¶ 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)[source]¶ 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)[source]¶ 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)[source]¶ Creates a regular graph of the given
shape
with the adjacency given as aneighbour_list
.See the helper function
mask_2_neighbours()
to create a suitableneighbour_list
. Example:
Create a 2d 4adjacency implicit graph of size
(13, 24)
:>>> graph = get_nd_regular_graph((13, 24), ((1, 0), (0, 1), (0, 1), (1, 0)))
Create a 3d 6adjacency 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)[source]¶ Creates an implicit regular graph of the given
shape
with the adjacency given as aneighbour_list
.See the helper function
mask_2_neighbours()
to create a suitableneighbour_list
. Example:
Create a 2d 4adjacency 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 6adjacency 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)[source]¶ 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 thecenter
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')[source]¶ 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 ifmode
is “relative”max_distance
ifmode
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 inimage_1
of the edgei
targets[i]
is the linear index of the target pixel inimage_2
of the edgei
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 ofim2
, pixel 4 ofim1
is matched with pixel 3 ofim2
, 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