Register
view
edit
current user:
anonymous
»
edit
»
iamxt
»
mxt_def4
Contents
Ajuda
DTI
Demo
MICLab
MRIHandsOn2014_A
TutorialAdesso
adessost
code
courseEA079_1S2010
courseEA998MC9331S2012
courseIA366F2S2010
courseIA368Q1S2012
courseIA369O1S2011
courseIA8981S2015
ea976A-2009
handson
ia368n-2009
ia636
ia636-2009
ia870
iaLPR
iaOPF
iamxt
iamxt-tutorial
iatexture
ipdp
main
toolboxOPF
watershed
iamxt.mxt_def4
Revision: 683632
(10)
============ Sub-branch ============ `MainPage MainPage` **Definition:** A sub-branch :eq:`SB_j` of a rooted tree :eq:`\mathcal{T}` is defined as a set of nodes that joins a ramification or a leaf until the nearest ramification child or root child. The root is defined as being a sub-branch with a single node. Sub-branches that have only one node are called trivial sub-branches. According to this definition, each node of the rooted tree belongs to one and only one sub-branch, therefore the set composed of all sub-branches of a rooted tree is disjoint and contains all its nodes. .. equation:: latex SB_j \cap SB_k = \emptyset, \quad if \quad j\neq k, \\ .. equation:: latex \mathcal{N}(\mathcal{T}) = SB_0 \cup SB_1...\cup SB_m. A rooted tree and its sub-branches are illustrated in Figure 1. We can think of each sub-branch as being a single node, and therefore we can build a sub-branch tree, as illustrated in Figure 2. The sub-branch tree is the minimal tree that preserves the same ramifications with the same degrees and ordering as the ramifications of the original tree. .. code:: graphviz :show_code: no :show_output: no :show_images: yes :img_width: 400 :img_cols: 3 digraph G5{rankdir=TD subgraph cluster_0 { style=filled; color=lightgrey; node [style=filled,color=white]; 0; label = "SB0"; } subgraph cluster_1 { style=filled; color=lightgrey; node [style=filled,color=white]; 1 label = "SB1"; } subgraph cluster_2 { style=filled; color=lightgrey; node [style=filled,color=white]; 2; label = "SB2"; } subgraph cluster_3 { style=filled; color=lightgrey; node [style=filled,color=white]; 3 label = "SB3"; } subgraph cluster_4 { style=filled; color=lightgrey; node [style=filled,color=white]; 7 -> 6->5->4; label = "SB4"; } subgraph cluster_5 { style=filled; color=lightgrey; node [style=filled,color=white]; 9 -> 8; label = "SB5"; } 0[ style=filled, shape="circle"]; 1[style=filled, shape="circle"]; 2[style=filled, shape="circle"]; 3[style=filled, shape="circle"]; 4[style=filled, shape="circle"]; 5[style=filled, shape="circle"]; 6[style=filled, shape="circle"]; 7[style=filled, shape="circle"]; 8[style=filled, shape="circle"]; 9[style=filled, shape="circle"]; 1->0 2->1 3->1 4->3 8->3 } Figure 1. Illustration of sub-branches. .. code:: graphviz digraph G3{rankdir=TD SB0[fixedsize=true, style=filled, shape="circle"]; SB1[ fixedsize=true, style=filled, shape="circle"]; SB2[ fixedsize=true, style=filled, shape="circle"]; SB3[fixedsize=true, style=filled, shape="circle"]; SB4[ fixedsize=true,style=filled, shape="circle"]; SB5[fixedsize=true, style=filled, shape="circle"]; SB1->SB0 SB2->SB1 SB3->SB1 SB4->SB3 SB5->SB3 } Figure 2. Illustration of the sub-branch tree corresponding to the tree in Figure 1. In the max-tree, each set of nodes :eq:`SB_j` that constitutes a sub-branch represents the variation of a connected component for different threshold values, before it splits in two or more components or before it completely disappears. The number of threshold levels before the connected component represented by the sub-branch splits or completely disappears will be denoted by :eq:`ntlevels`, and is given by the following equation: .. equation:: latex ntlevels(SB_j) = \underset{\forall k \in SB_j}{\sum} nlevels(k). The number of nodes in the sub-branch tree is equal to the number of sub-branches in the original tree and is given by the number of leaves :eq:`n` plus the number of ramifications plus one, if the root is not a ramification. Its minimum value is equal :eq:`n+1`. It happens when all leaves are connected directly to the root. Its maximum value happens when the sub-branch tree is almost a full binary tree, except for the root that has only one child. From the theory, the number of nodes in a full binary tree is :eq:`2n-1`, since in the sub-branch tree, the root may have only one child, the maximum number of nodes of the sub-branch tree is :eq:`2n`. Therefore, .. equation:: latex n+1 \leq \text{Number of sub-branch tree nodes} \leq{2n}. The case where the number of nodes in the sub-branch tree is equal to the lower bound :eq:`n+1` is illustrated in Figure 3(a), and the case where the number of nodes in the tree is equal to the upper bound :eq:`2n` is illustrated in Figure 3(b) . .. code:: graphviz digraph G4{rankdir=BT 0[shape="circle",label=""]; 1[shape="circle",label=""]; 2[shape="circle",label=""]; 3[shape="circle",label=""]; 1->0 3->0 2->0 } .. code:: graphviz digraph G4{rankdir=BT 0[shape="circle",label=""]; 1[shape="circle",label=""]; 2[shape="circle",label=""]; 3[shape="circle",label=""]; 4[shape="circle",label=""]; 5[color = "red",shape="circle",label=""]; 0->5 1->0 3->2 4->2 2->0 } Figure 3. Illustration of the cases where the number of nodes in the sub-branch tree are equal to :eq:`n+1` (a) and :eq:`2n` (b).