#!/usr/bin/env python
# file Tree.py
# author Florent Guiotte <florent.guiotte@irisa.fr>
# version 0.0
# date 13 nov. 2019
"""
Trees
=====
This submodule contains the component tree classes.
Example
-------
Simple creation of the max-tree of an image, compute the area attributes
of the nodes and reconstruct a filtered image removing nodes with area
less than 100 pixels:
>>> t = sap.MaxTree(image)
>>> area = t.get_attribute('area')
>>> filtered_image = t.reconstruct(area < 100)
"""
import higra as hg
import numpy as np
from pprint import pformat
import inspect
import tempfile
from pathlib import Path
from .utils import *
[docs]def available_attributes():
"""
Return a dictionary of available attributes and parameters.
Returns
-------
dict_of_attributes : dict
The names of available attributes and parameters required.
The names are keys (str) and the parameters are values (list
of str) of the dictionary.
See Also
--------
get_attribute : Return the attribute values of the tree nodes.
Notes
-----
The list of available attributes is generated dynamically. It is
dependent of higra's installed version. For more details, please
refer to `higra documentation
<https://higra.readthedocs.io/en/stable/python/tree_attributes.html>`_
according to the appropriate higra's version.
Example
-------
>>> sap.available_attributes()
{'area': ['vertex_area=None', 'leaf_graph=None'],
'compactness': ['area=None', 'contour_length=None', ...],
...
'volume': ['altitudes', 'area=None']}
"""
params_remove = ['tree']
dict_of_attributes = {}
for x in inspect.getmembers(hg):
if x[0].startswith('attribute_'):
attribute_name = x[0].replace('attribute_', '')
attribute_param = \
[str(x) for x in inspect.signature(x[1]).parameters.values()]
if attribute_param[0] != 'tree': continue
attribute_param = \
list(filter(lambda x: x not in params_remove, attribute_param))
dict_of_attributes[attribute_name] = attribute_param
return dict_of_attributes
[docs]def save(file, tree):
"""Save a tree to a NumPy archive file.
Parameters
----------
file : str or pathlib.Path
File to which the tree is saved.
tree: Tree
Tree to be saved.
Examples
--------
>>> mt = sap.MaxTree(np.random.random((100,100)))
>>> sap.save('tree.npz', mt)
"""
tree_file = Path(tempfile.mkstemp()[1])
graph_file = Path(tempfile.mkstemp()[1])
# TODO: Remove _alt once higra fixed
hg.save_tree(str(tree_file), tree._tree, {'_alt': tree._alt})
hg.save_graph_pink(str(graph_file), tree._graph)
with tree_file.open('rb') as f:
tree_bytes = f.read()
with graph_file.open('rb') as f:
graph_bytes = f.read()
tree_file.unlink()
graph_file.unlink()
data = tree.__dict__.copy()
data['_tree'] = tree_bytes
data['_graph'] = graph_bytes
data['__class__'] = tree.__class__
np.savez_compressed(file, **data)
[docs]def load(file):
"""Load a tree from a Higra tree file.
Parameters
----------
file : str or pathlib.Path
File to which the tree is loaded.
Examples
--------
>>> mt = sap.MaxTree(np.arange(10000).reshape(100,100))
>>> sap.save('tree.npz', mt)
>>> sap.load('tree.npz')
MaxTree{num_nodes: 20000, image.shape: (100, 100), image.dtype: int64}
"""
data = np.load(str(file), allow_pickle=True)
payload = {}
for f in data.files:
payload[f] = data[f].item() if data[f].size == 1 else data[f]
tree_file = Path(tempfile.mkstemp()[1])
graph_file = Path(tempfile.mkstemp()[1])
with tree_file.open('wb') as f:
f.write(payload['_tree'])
with graph_file.open('wb') as f:
f.write(payload['_graph'])
tree_cls = payload.pop('__class__')
tree = tree_cls(None)
tree.__dict__.update(payload)
tree._tree = hg.read_tree(str(tree_file))[0]
tree._graph = hg.read_graph_pink(str(graph_file))[0]
tree_file.unlink()
graph_file.unlink()
return tree
[docs]class Tree:
"""
Abstract class for tree representations of images.
Notes
-----
You should not instantiate class `Tree` directly, use `MaxTree` or
`MinTree` instead.
"""
def __init__(self, image, adjacency, image_name=None, operation_name='non def'):
if self.__class__ == Tree:
raise TypeError('Do not instantiate directly abstract class Tree.')
self._image_name = image_name
self._image_hash = ndarray_hash(image) if image is not None else None
self._adjacency = adjacency
self._image = image
self.operation_name = operation_name
if image is not None:
self._graph = self._get_adjacency_graph()
self._construct()
def __str__(self):
return str(self.__repr__())
[docs] def get_params(self):
return {'image_name': self._image_name,
'image_hash': self._image_hash,
'adjacency': self._adjacency}
def __repr__(self):
if hasattr(self, '_tree'):
rep = self.get_params()
rep.update({'num_nodes': self.num_nodes(),
'image.shape': self._image.shape,
'image.dtype': self._image.dtype})
else:
rep = {}
return self.__class__.__name__ + pformat(rep)
def _get_adjacency_graph(self):
if self._adjacency == 4:
return hg.get_4_adjacency_graph(self._image.shape)
elif self._adjacency == 8:
return hg.get_8_adjacency_graph(self._image.shape)
else:
raise NotImplementedError('adjacency of {} is not '
'implemented.'.format(self._adjacency))
[docs] def available_attributes(self=None):
"""
Return a dictionary of available attributes and parameters.
Returns
-------
dict_of_attributes : dict
The names of available attributes and parameters required.
The names are keys (str) and the parameters are values (list
of str) of the dictionary.
See Also
--------
get_attribute : Return the attribute values of the tree nodes.
Notes
-----
The list of available attributes is generated dynamically. It is
dependent of higra's installed version. For more details, please
refer to `higra documentation
<https://higra.readthedocs.io/en/stable/python/tree_attributes.html>`_
according to the appropriate higra's version.
Example
-------
>>> sap.Tree.available_attributes()
{'area': ['vertex_area=None', 'leaf_graph=None'],
'compactness': ['area=None', 'contour_length=None', ...],
...
'volume': ['altitudes', 'area=None']}
"""
return available_attributes()
[docs] def get_attribute(self, attribute_name, **kwargs):
"""
Get attribute values of the tree nodes.
Parameters
------
attribute_name : str
Name of the attribute (e.g. 'area', 'compactness', ...)
Returns
-------
attribute_values: ndarray
The values of attribute for each nodes.
See Also
--------
available_attributes : Return the list of available attributes.
Notes
-----
Some attributes require additional parameters. Please refer to
`available_attributes`. If not stated, some additional
parameters are automatically deducted. These deducted parameters
are 'altitudes' and 'vertex_weights'.
The available attributes depends of higra's installed version.
For further details Please refer to `higra documentation
<https://higra.readthedocs.io/en/stable/python/tree_attributes.html>`_
according to the appropriate higra's version.
Examples
--------
>>> image = np.arange(20 * 50).reshape(20, 50)
>>> t = sap.MaxTree(image)
>>> t.get_attribute('area')
array([ 1., 1., 1., ..., 998., 999., 1000.])
"""
try:
compute = getattr(hg, 'attribute_' + attribute_name)
except AttributeError:
raise ValueError('Wrong attribute or out feature: \'{}\'')
if 'altitudes' in inspect.signature(compute).parameters:
kwargs['altitudes'] = kwargs.get('altitudes', self._alt)
if 'vertex_weights' in inspect.signature(compute).parameters:
kwargs['vertex_weights'] = kwargs.get('vertex_weights', self._image)
return compute(self._tree, **kwargs)
[docs] def reconstruct(self, deleted_nodes=None, feature='altitude',
filtering='direct'):
"""
Return the reconstructed image according to deleted nodes.
Parameters
----------
deleted_nodes : ndarray or boolean, optional
Boolean array of nodes to delete. The length of the array should be
of same of node count.
feature : str, optional
The feature to be reconstructed. Can be any attribute of the
tree (see :func:`available_attributes`). The default is
`'altitude'`, the grey level of the node.
filtering : str, optional
The filtering rule to use. It can be 'direct', 'min', 'max' or
'subtractive'. Default is 'direct'.
Returns
-------
filtered_image : ndarray
The reconstructed image.
Examples
--------
>>> image = np.arange(5 * 5).reshape(5, 5)
>>> mt = sap.MaxTree(image)
>>> mt.reconstruct()
array([[ 0, 1, 2, 3, 4],
[ 5, 6, 7, 8, 9],
[10, 11, 12, 13, 14],
[15, 16, 17, 18, 19],
[20, 21, 22, 23, 24]])
>>> area = mt.get_attribute('area')
>>> mt.reconstruct(area > 10)
array([[ 0, 0, 0, 0, 0],
[ 0, 0, 0, 0, 0],
[ 0, 0, 0, 0, 0],
[15, 16, 17, 18, 19],
[20, 21, 22, 23, 24]])
"""
if isinstance(deleted_nodes, bool):
deleted_nodes = np.array((deleted_nodes,) * self.num_nodes())
elif deleted_nodes is None:
deleted_nodes = np.zeros(self.num_nodes(), dtype=np.bool)
feature_value = self._alt if feature == 'altitude' else \
self.get_attribute(feature)
rules = {'direct': self._filtering_direct,
'min': self._filtering_min,
'max': self._filtering_max,
'subtractive': self._filtering_subtractive}
feature_value, deleted_nodes = rules[filtering](feature_value, deleted_nodes)
return hg.reconstruct_leaf_data(self._tree, feature_value, deleted_nodes)
def _filtering_direct(self, feature_value, direct):
deleted_nodes = direct.astype(np.bool)
return feature_value, deleted_nodes
def _filtering_min(self, feature_value, direct):
deleted_nodes = hg.propagate_sequential(self._tree, direct,
~direct).astype(np.bool)
return feature_value, deleted_nodes
def _filtering_max(self, feature_value, direct):
deleted_nodes = hg.accumulate_and_min_sequential(self._tree, direct,
np.ones(self._tree.num_leaves()),
hg.Accumulators.min).astype(np.bool)
return feature_value, deleted_nodes
def _filtering_subtractive(self, feature_value, direct):
deleted_nodes = direct.astype(np.bool)
delta = feature_value - feature_value[self._tree.parents()]
delta[direct] = 0
delta[self._tree.root()] = feature_value[self._tree.root()]
feature_value = hg.propagate_sequential_and_accumulate(self._tree, delta,
hg.Accumulators.sum)
return feature_value, deleted_nodes
[docs] def num_nodes(self):
"""
Return the node count of the tree.
Returns
-------
nodes_count : int
The node count of the tree.
"""
return self._tree.num_vertices()
[docs]class MaxTree(Tree):
"""
Max tree class, the local maxima values of the image are in leafs.
Parameters
----------
image : ndarray
The image to be represented by the tree structure.
adjacency : int
The pixel connectivity to use during the tree creation. It
determines the number of pixels to be taken into account in the
neighborhood of each pixel. The allowed adjacency are 4 or 8.
Default is 4.
image_name : str, optional
The name of the image Useful to track filtering process and
display.
Notes
-----
Inherits all methods of `Tree` class.
"""
def __init__(self, image, adjacency=4, image_name=None):
super().__init__(image, adjacency, image_name, 'thickening')
def _construct(self):
self._tree, self._alt = hg.component_tree_max_tree(self._graph, self._image)
[docs]class MinTree(Tree):
"""
Min tree class, the local minima values of the image are in leafs.
Parameters
----------
image : ndarray
The image to be represented by the tree structure.
adjacency : int
The pixel connectivity to use during the tree creation. It
determines the number of pixels to be taken into account in the
neighborhood of each pixel. The allowed adjacency are 4 or 8.
Default is 4.
image_name : str, optional
The name of the image Useful to track filtering process and
display.
Notes
-----
Inherits all methods of `Tree` class.
"""
def __init__(self, image, adjacency=4, image_name=None):
super().__init__(image, adjacency, image_name, 'thinning')
def _construct(self):
self._tree, self._alt = hg.component_tree_min_tree(self._graph, self._image)
[docs]class TosTree(Tree):
"""
Tree of shapes, the local maxima values of the image are in leafs.
Parameters
----------
image : ndarray
The image to be represented by the tree structure.
adjacency : int
The pixel connectivity to use during the tree creation. It
determines the number of pixels to be taken into account in the
neighborhood of each pixel. The allowed adjacency are 4 or 8.
Default is 4.
image_name : str, optional
The name of the image Useful to track filtering process and
display.
Notes
-----
Inherits all the methods of `Tree` class.
Todo
----
- take into account adjacency
"""
def __init__(self, image, adjacency=4, image_name=None):
super().__init__(image, adjacency, image_name, 'sd filtering')
def _construct(self):
self._tree, self._alt = hg.component_tree_tree_of_shapes_image2d(self._image)
[docs]class AlphaTree(Tree):
"""
Alpha tree, partition the image depending of the weight between pixels.
Parameters
----------
image : ndarray
The image to be represented by the tree structure.
adjacency : int
The pixel connectivity to use during the tree creation. It
determines the number of pixels to be taken into account in the
neighborhood of each pixel. The allowed adjacency are 4 or 8.
Default is 4.
image_name : str, optional
The name of the image Useful to track filtering process and
display.
weight_function : str or higra.WeightFunction
The weight function to use during the construction of the tree.
Can be 'L0', 'L1', 'L2', 'L2_squared', 'L_infinity', 'max',
'min', 'mean' or a `higra.WeightFunction`. The default is
'L1'.
"""
def __init__(self, image, adjacency=4, image_name=None, weight_function='L1'):
if isinstance(weight_function, str):
try:
self._weight_function = getattr(hg.WeightFunction, weight_function)
except AttributeError:
raise AttributeError('Wrong value \'{}\' for attribute' \
' weight_function'.format(weight_function))
elif isinstance(weight_function, hg.higram.WeightFunction):
self._weight_function = weight_function
else:
raise NotImplementedError('Unknow type \'{}\' for parameter' \
' weight_function'.format(type(weight_function)))
super().__init__(image, adjacency, image_name, 'alpha filtering')
def _construct(self):
weight = hg.weight_graph(self._graph, self._image, self._weight_function)
self._tree, alt = hg.quasi_flat_zone_hierarchy(self._graph, weight)
self._alt, self._variance = hg.attribute_gaussian_region_weights_model(self._tree, self._image)
[docs]class OmegaTree(Tree):
"""
Partition the image depending of the constrained weight between pixels.
Parameters
----------
image : ndarray
The image to be represented by the tree structure.
adjacency : int
The pixel connectivity to use during the tree creation. It
determines the number of pixels to be taken into account in the
neighborhood of each pixel. The allowed adjacency are 4 or 8.
Default is 4.
image_name : str, optional
The name of the image Useful to track filtering process and
display.
"""
def __init__(self, image, adjacency=4, image_name=None):
super().__init__(image, adjacency, image_name, '(ω) filtering')
def _construct(self):
edge_weights = hg.weight_graph(self._graph, self._image, getattr(hg.WeightFunction, 'L1'))
vertex_weights = hg.linearize_vertex_weights(self._image, self._graph)
tree, alt = hg.quasi_flat_zone_hierarchy(self._graph, edge_weights)
min_value = hg.accumulate_sequential(tree, vertex_weights, hg.Accumulators.min)
max_value = hg.accumulate_sequential(tree, vertex_weights, hg.Accumulators.max)
value_range = max_value - min_value
range_parents = value_range[tree.parents()]
violated_constraints = value_range >= range_parents
self._tree, node_map = hg.simplify_tree(tree, violated_constraints)
self._alt, self._variance = hg.attribute_gaussian_region_weights_model(self._tree, self._image)