Tree of shapes

component_tree_tree_of_shapes_image2d(image)

Tree of shapes of a 2d image.

component_tree_multivariate_tree_of_shapes_image2d(image)

Multivariate tree of shapes for a 2d multi-band image.
component_tree_tree_of_shapes_image2d(image, padding='mean', original_size=True, immersion=True, exterior_vertex=0)[source]

Tree of shapes of a 2d image.

The Tree of Shapes was described in [1]. The algorithm used in this implementation was first described in [2].

The tree is computed in the interpolated multivalued Khalimsky space to provide a continuous and autodual representation of input image.

Possible values of padding are ‘none’, ‘mean’, and ‘zero’. If padding is different from ‘none’, an extra border of pixels is added to the input image before anything else. This will ensure the existence of a shape encompassing all the shapes inside the input image (if exterior_vertex is inside the extra border): this shape will be the root of the tree. The padding value can be:

  • 0 if padding is equal to "zero";

  • the mean value of the boundary pixels of the input image if padding is equal to "mean".

If original_size is True, all the nodes corresponding to pixels not belonging to the input image are removed (except for the root node). If original_size is False, the returned tree is the tree constructed in the interpolated/padded space. In practice if the size of the input image is \((h, w)\), the leaves of the returned tree will correspond to an image of size:

  • \((h, w)\) if original_size is True;

  • \((h * 2 - 1, w * 2 - 1)\) is original_size is False and padding is "none"; and

  • \(((h + 2) * 2 - 1, (w + 2) * 2 - 1)\) otherwise.

Advanced options:

immersion defines if the initial image should be first converted as an equivalent continuous representation called a plain map. If immersion is set to False the level lines of the shapes of the image may intersect (if the image is not well composed) and the result of the algorithm is undefined (the algorithm will arbitrarily break level lines to get a set of shapes forming a tree). If immersion is False, the result size will be:

  • \((h, w)\) if original_size is True or if padding is "none";

  • \((h + 2, w + 2)\) otherwise.

Exterior_vertex defines the linear coordinates of the pixel corresponding to the exterior (interior and exterior of a shape is defined with respect to this point). The coordinate of this point must be given in the padded/interpolated space.

Parameters:

  • image – must be a 2d array

  • padding – possible values are ‘none’, ‘zero’, and ‘mean’ (default = ‘mean’)

  • original_size – remove all nodes corresponding to interpolated/padded pixels (default = True)

  • immersion – performs a plain map continuous immersion fo the original image (default = True)

  • exterior_vertex – linear coordinate of the exterior point

Returns:

a tree (Concept CptHierarchy) and its node altitudes

component_tree_multivariate_tree_of_shapes_image2d(image, padding='mean', original_size=True, immersion=True)[source]

Multivariate tree of shapes for a 2d multi-band image. This tree is defined as a fusion of the marginal trees of shapes. The method is described in:

E. Carlinet. A Tree of shapes for multivariate images. PhD Thesis, Université Paris-Est, 2015.

The input image must be a 3d array of shape \((height, width, channel)\).

Note that the constructed hierarchy doesn’t have natural altitudes associated to its node: as a node is generally a fusion of several marginal nodes, we can’t associate a single canonical value from the original image to this node.

The parameters padding, original_size, and immersion are forwarded to the function component_tree_tree_of_shapes_image2d(): please look at this function documentation for more details.

Complexity:

The worst case runtime complexity of this method is \(\mathcal{O}(N^2D^2)\) with \(N\) the number of pixels and \(D\) the number of bands. If the image pixel values are quantized on \(K<<N\) different values (eg. with a color image in \([0..255]^D\)), then the worst case runtime complexity can be tightened to \(\mathcal{O}(NKD^2)\).

See:

This function relies on tree_fusion_depth_map() to compute the fusion of the marinal trees.

Parameters:

  • image – input color 2d image

  • padding – possible values are ‘none’, ‘zero’, and ‘mean’ (default = ‘mean’)

  • original_size – remove all nodes corresponding to interpolated/padded pixels (default = True)

  • immersion – performs a plain map continuous immersion fo the original image (default = True)

Returns:

a tree (Concept CptHierarchy)