# Data Structure

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:

# 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.