Builds Cousty-style hierarchical-watershed saliency from extinctions. More...

#include <HierarchicalWatershedSaliency.hpp>

Static Public Member Functions
template<AltitudeValue T, std::floating_point Real>
static EdgeSaliencyMap< Real >	compute (const ValuedMorphologicalTreeView< T > &valuedTree, std::span< const Real > leafExtinction, const RegularGridAdjacency2D &adjacency)
	Computes the full-graph extinction hierarchical-watershed saliency.

template<AltitudeValue T, std::floating_point Real>
static EdgeSaliencyMap< int >	computeRanked (const ValuedMorphologicalTreeView< T > &valuedTree, std::span< const Real > leafExtinction, const RegularGridAdjacency2D &adjacency)
	Computes the canonical dense rank scale of `compute`.

Detailed Description

Builds Cousty-style hierarchical-watershed saliency from extinctions.

This class implements the constructive route described in Section 8.1 of Cousty et al. A minimum spanning tree of the altitude-ordered component hierarchy is first selected. Extinctions are propagated through its Kruskal binary partition tree; the persistence of a binary merge is the minimum of the maximum descendant extinctions on its two sides. Finally, the persistence valuedTree MST is converted to its QFZ dendrogram and projected back to every edge of the original graph by LCA.

The input is a max-tree or min-tree view with one non-negative extinction value per internal node slot. Values are read only at component-tree leaves. Unlike the paper's arbitrary edge-valuedTree input (G,w), this API derives the graph-edge order from the supplied component tree: same-smallest-node edges come first and transition edges are ordered by the altitude of the LCA of their endpoint smallest nodes. This component-tree adapter feeds the Kruskal constructions.

Primary reference: Jean Cousty, Laurent Najman, Yukiko Kenmochi, and Silvio Guimarães, "Hierarchical segmentations with graphs: quasi-flat zones, minimum spanning trees, and saliency maps," Journal of Mathematical Imaging and Vision, 60(4):479-502, 2018. DOI 10.1007/s10851-017-0768-7. The implementation concretizes the BPTAO/extinction/persistence construction sketched in Section 8.1 and makes its otherwise non-unique ties deterministic; the component-tree-derived edge order above is specific to this library.

Definition at line 49 of file HierarchicalWatershedSaliency.hpp.

Member Function Documentation

◆ compute()

template<AltitudeValue T, std::floating_point Real>

static EdgeSaliencyMap< Real > mmcfilters::HierarchicalWatershedSaliency::compute	(	const ValuedMorphologicalTreeView< T > &	valuedTree,
		std::span< const Real >	leafExtinction,
		const RegularGridAdjacency2D &	adjacency
	)

inlinestatic

Computes the full-graph extinction hierarchical-watershed saliency.

Template Parameters

T	Component-tree altitude scalar type.
Real	Floating-point extinction and output scalar type.

Parameters

valuedTree	Immutable view of a committed max-tree or min-tree with finite monotone altitudes.
leafExtinction	Dense internal-node-id buffer. Values at live leaves must be finite and non-negative; other slots are ignored.
adjacency	Connected projection graph on exactly the tree's image grid.

Returns: Full edge-indexed QFZ saliency map with persistence values.

Exceptions

std::logic_error	If the topology changed after `valuedTree` was made.
std::invalid_argument	If the hierarchy, adjacency, extinction buffer, leaf smallest-node mapping, or monotone-altitude contract is invalid.
std::runtime_error	If a live LCA cannot be recovered for a graph edge.

Complexity: Let N count internal node slots, m live source-tree nodes, p pixels, and e adjacency edges. Including connectivity validation, time is O(N + (m + p + e) alpha(p) + e log(e + 1) + p log(p + 1)), where alpha is the inverse Ackermann function. Additional storage, including output, is O(N + e + p log(p + 1)); this includes the new dendrogram's possible Euler/RMQ cache.

These bounds exclude source-tree construction, extinction-value computation, and source-tree LCA caches. Preparing absent source caches can add O(N log(N + 1)) time and tree-owned storage.

Definition at line 383 of file HierarchicalWatershedSaliency.hpp.

◆ computeRanked()

template<AltitudeValue T, std::floating_point Real>

static EdgeSaliencyMap< int > mmcfilters::HierarchicalWatershedSaliency::computeRanked	(	const ValuedMorphologicalTreeView< T > &	valuedTree,
		std::span< const Real >	leafExtinction,
		const RegularGridAdjacency2D &	adjacency
	)

inlinestatic

Computes the canonical dense rank scale of compute.