Data Structure

MainPage

The max-tree is build from a gray-scale image f and our toolbox uses an array-based representation that has two main structures to represent it: node_array, and node_index.

node_array

The node_array structure is a 2d-array, where each column represents a max-tree node, and the lines represent the node attributes. node_array needs at least two lines to fully represent the image max-tree: one line to represent the parent (par) relationship, and another to represent the gray-level (h) of the node. In our toolbox, node_array is a or a array depending whether we are working with 2D or 3D images, respectively. The attributes that are stored during the max-tree construction are summarized in the table below.

Line Attribute Meaning
0 par Parent
1 nchild Number of children
2 level Gray-level
3 area Node area
4 seed Seed for node reconstruction
5 sumx Sum of x coordinates
6 xmin Minimum x coordinate
7 xmax Maximum x coordinate
8 sumy Sum of y coordinates
9 ymin Minimum y coordinate
10 ymax Maximum y coordinate
11 sumz Sum of z coordinates
12 zmin Minimum z coordinate
13 zmax Maximum z coordinate

Table 1. Summary of the attributes stored in the lines of node_array. The last three lines only exist when working with 3D images.

Our convention is that node 0 (column 0) is the root of the tree, and it points to itself, i.e. . The columns are ordered so that when scanning the tree from node 0 to node n-1, any node is processed only after having processed all its ancestors. Many of the algorithms implemented in this toolbox make use of this ordering property.

node_index

The node_index structure is a 2d-array with the same dimensions of the gray-scale image represented by the max-tree. Each element of the array points to the max-tree node it belongs. The image represented by the max-tree can be easily recovered from this structure using an array programming package, such as NumPy from Python:

1 level = node_array[2,:]
2 recovered_image = level[node_index]

Bc

Boolean array that defines the connectivity used to build the tree.

shape

Tuple containing the dimensions of the image used to build the max-tree.

_children_list, _cum_children_hist, _children_updated

Structure used to store the children of the max-tree nodes. _children_list is a 1-d array storing the nodes and _cum_children_hist is a 1-d array containing the indexes to recover the children of a given node. _children_updated is a boolean variable that tells us if the structure is up to date. This structure is meant only for internal use, for more info see getChildren. The user of the toolbox only needs to use it, if he intends to extend the toolbox with new methods.

_sb, _cum_sb_hist, _sb_updated

Structure used to store the sub-branches of the max-tree. _sb is a 1-d array storing the nodes and _cum_sb_hist is a 1-d array containing the indexes to recover each sub-branch of the tree. _sb_updated is a boolean variable that tells us if the structure is up to date. This structure is meant only for internal use, for more info see getSubBranches. The user of the toolbox only needs to use it, if he intends to extend the toolbox with new methods.

implementation

Flag used to decide whether to use the C++/OpenMP optimized code or the purely python code.