Constrained connectivity hierarchy¶
Alpha-omega constrained connectivity hierarchy based on the given vertex weighted graph. |
|
Strongly constrained connectivity hierarchy based on the given edge weighted graph. |
-
constrained_connectivity_hierarchy_alpha_omega
(graph, vertex_weights)[source]¶ Alpha-omega constrained connectivity hierarchy based on the given vertex weighted graph.
For \((i,j)\) be an edge of the graph, we define \(w(i,j)=|w(i) - w(j)|\), the weight of this edge. Let \(X\) be a set of vertices, the range of \(X\) is the maximal absolute difference between the weights of any two vertices in \(X\): \(R(X) = \max\{|w(i) - w(j)|, (i,j)\in X^2\}\)
Let \(\alpha\) be a positive real number, a set of vertices \(X\) is \(\alpha\)-connected, if for any two vertices \(i\) and \(j\) in \(X\), there exists a path from \(i\) to \(j\) in \(X\) composed of edges of weights lower than or equal to \(\alpha\).
Let \(\alpha\) and \(\omega\) be a two positive real numbers, the \(\alpha-\omega\)-connected components of the graph are the maximal \(\alpha'\)-connected sets of vertices with a range lower than or equal to \(\omega\), with \(\alpha'\leq\alpha\).
Finally, the alpha-omega constrained connectivity hierarchy is defined as the hierarchy composed of all the \(k-k\)-connected components for all positive \(k\).
The definition used follows the one given in:
P. Soille, “Constrained connectivity for hierarchical image partitioning and simplification,” in IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 30, no. 7, pp. 1132-1145, July 2008. doi: 10.1109/TPAMI.2007.70817
The algorithm runs in time \(\mathcal{O}(n\log(n))\) and proceeds by filtering a quasi-flat zone hierarchy (see
quasi_flat_zones_hierarchy()
)- Parameters:
graph – input graph
vertex_weights – edge_weights: edge weights of the input graph
- Returns:
a tree (Concept
CptHierarchy
) and its node altitudes
-
constrained_connectivity_hierarchy_strong_connection
(graph, edge_weights)[source]¶ Strongly constrained connectivity hierarchy based on the given edge weighted graph.
Let \(X\) be a set of vertices, the range of \(X\) is the maximal weight of the edges linking two vertices inside \(X\).
Let \(\alpha\) be a positive real number, a set of vertices \(X\) is \(\alpha\)-connected, if for any two vertices \(i\) and \(j\) in \(X\), there exists a path from \(i\) to \(j\) in \(X\) composed of edges of weights lower than or equal to \(\alpha\).
Let \(\alpha\) be a positive real numbers, the \(\alpha\)-strongly connected components of the graph are the maximal \(\alpha'\)-connected sets of vertices with a range lower than or equal to \(\alpha\) with \(\alpha'\leq\alpha\).
Finally, the strongly constrained connectivity hierarchy is defined as the hierarchy composed of all the \(\alpha\)- strongly connected components for all positive \(\alpha\).
The definition used follows the one given in:
P. Soille, “Constrained connectivity for hierarchical image partitioning and simplification,” in IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 30, no. 7, pp. 1132-1145, July 2008. doi: 10.1109/TPAMI.2007.70817
The algorithm runs in time \(\mathcal{O}(n\log(n))\) and proceeds by filtering a quasi-flat zone hierarchy (see
quasi_flat_zones_hierarchy()
)- Parameters:
graph – input graph
edge_weights – edge_weights: edge weights of the input graph
- Returns:
a tree (Concept
CptHierarchy
) and its node altitudes