Tree of shapes¶
Tree of shapes of a 2d image. 

Multivariate tree of shapes for a 2d multiband 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
isTrue
, all the nodes corresponding to pixels not belonging to the input image are removed (except for the root node). Iforiginal_size
isFalse
, 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
isTrue
;\((h * 2  1, w * 2  1)\) is
original_size
isFalse
andpadding
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. Ifimmersion
is set toFalse
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). Ifimmersion
isFalse
, the result size will be:\((h, w)\) if
original_size
isTrue
or ifpadding
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. 1
Pa. Monasse, and F. Guichard, “Fast computation of a contrastinvariant image representation,” Image Processing, IEEE Transactions on, vol.9, no.5, pp.860872, May 2000
 2
Th. Géraud, E. Carlinet, S. Crozet, and L. Najman, “A Quasilinear Algorithm to Compute the Tree of Shapes of nD Images”, ISMM 2013.
 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 multiband 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é ParisEst, 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
, andimmersion
are forwarded to the functioncomponent_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
)