|
mmcfilters
Public API documentation
|
This guide describes the public hierarchy model, construction factories, smallest-node rules, node domains, and altitude contracts used by mmcfilters.
The public tree API separates topology from node altitude:
MorphologicalTree owns rooted topology and smallest-node mapping;ValuedMorphologicalTree<T> owns a topology and a dense altitude buffer;ValuedMorphologicalTreeView<T> borrows a topology and an external altitude span.MorphologicalTree stores:
NodeId slots;Pixel-domain objects use PixelId: this includes the infinity pixel, proper-part elements, support and boundary pixels, and flat-zone representatives. Tree slots and parent/child links use NodeId. Their current integer representations are equal, but code must use InvalidPixel for the pixel domain and InvalidNode for the node domain. Counts use ordinary integral count types rather than either identifier alias.
Operations that read altitude require ValuedMorphologicalTree<T> or ValuedMorphologicalTreeView<T>. Topology/support operations can use the topology alone.
MorphologicalTreeSemantics declares the capabilities of a hierarchy:
NodeAltitudeOrder::Increasing requires altitude(parent) < altitude(child);NodeAltitudeOrder::Decreasing requires altitude(parent) > altitude(child);NodeAltitudeOrder::Unconstrained declares no global altitude direction;MorphologicalTreeConstructionContext records explicit absence of construction provenance, a shared adjacency, saturated-residual parameters, or a complete topographic convention;MorphologicalTreeKind is a descriptive label, not an algorithm-dispatch contract.Algorithms validate the capabilities they use. A topology/support operation may require regular 2D geometry without requiring altitude, construction adjacency, or a particular descriptive tree kind.
| Operation | Required capabilities |
|---|---|
topology traversal and AREA | finite smallest-node mapping |
nodeAltitude, nodeAltitudes, and reconstruction from node altitudes | altitude buffer |
GrayLevelHeight, MeanGrayLevel, GrayLevelVariance, and VOLUME | altitude buffer |
| reconstruction and pixel mapping | regular 2D domain |
| moments, bounding boxes, and contours | regular 2D domain |
| bitquad attributes | regular 2D domain, canonical 4/8 projection connectivity, and exact node altitudes when lower/upper shape connectivity differs |
distance-transform attributes (DIST_TRANSF, DIST_TRANSF_EXACT) | regular 2D domain |
| hierarchy saliency projection | regular 2D domain and one compatible projection adjacency |
On a 2D square grid, radius=1.0 selects 4-connectivity and radius=1.5 selects 8-connectivity. RegularGridAdjacency2D also supports centered rectangles, digital lines, and symmetric structuring elements:
An adjacency-inducing structuring element must contain the origin exactly once and be centrally symmetric. A component-tree adjacency must also connect its finite image domain. Traversal ranges own their cursors, so nested and interleaved iteration over the same relation is safe.
Use MorphologicalTreeFactory for public construction:
C++ max-tree and min-tree factories are typed:
Python image factories accept two-dimensional C-contiguous np.uint8 arrays and return ValuedMorphologicalTree. See Python API for the binding-specific contract.
createUnrestrictedResidualTree constructs a hierarchy from synchronized max-tree and min-tree states using one symmetric adjacency. The saturated variant also requires the complement of a selected extremum to remain connected to the row-major infinityPixel supplied by the caller.
The unrestricted and saturated factories publish distinct UnrestrictedResidualTree and SaturatedResidualTree kinds. The former retains a SharedAdjacencyContext; the latter retains a SaturatedResidualContext, including its infinity pixel. Both publish:
NodeAltitudeOrder::Unconstrained.Their alternating gray-level altitudes are not a monotone hierarchy valuation. Use a structural or otherwise non-decreasing node valuation for operations that require values to increase toward the root.
An explicit adjacency can replace the radius:
Construction policies are grouped by mode, so unrestricted callers cannot accidentally configure saturation-only mechanisms:
By default, construction uses RowMajorSpatialOrder, LCA computation by following parent links, and multi-source boundary fallback. See Self-dual residual trees for the candidate schedule, boundary maintenance, and event assembly.
TopographicConvention records and controls:
CanonicalComplementaryGridImmersion carrying only its ComplementaryPairing, a ComplementaryGridImmersion carrying explicit minimum/maximum adjacencies, or SelfDualSpanImmersion;TopographicDomainExtension::ExteriorRing or None;infinityPixel in the active topographic domain;TopographicAltitudeEncoding::UInt8 or ExactDoubled.The default convention selects the canonical minimum-4/maximum-8 complementary-grid immersion without domain padding, uses infinity pixel zero, and publishes unchanged 8-bit source levels:
A canonical immersion declares only the ordered pairing, so it needs no domain. It is resolved against the source domain during construction, and the retained convention always exposes the concrete adjacencies:
Both padding policies publish the original source pixels as the tree domain and attach the original GridDomain2D. The immersion grid is not exposed as the pixel domain.
A complementary-grid immersion floods the interpolated domain over the source level set itself, so every construction level is already a source gray level. TopographicAltitudeEncoding::UInt8 publishes those levels unchanged and reconstructFromNodeAltitudes() returns the source image. The encoding is exact, not a quantization: the published hierarchy is the doubled hierarchy with every altitude halved, so no parent-child altitude distinction is lost.
A self-dual span immersion propagates from a boundary reference level that, on an even boundary, is the mean of the two central boundary values and may therefore fall between two source levels. That reference level lives on the exterior ring and is the only source of half levels, so the admissible encodings depend on the domain extension:
| Immersion | TopographicDomainExtension | Admissible encodings |
|---|---|---|
| Complementary grid | either | UInt8, ExactDoubled |
| Self-dual span | None | UInt8, ExactDoubled |
| Self-dual span | ExteriorRing | ExactDoubled only |
Without the exterior ring the reference level is cropped away and no interior cell reads it, so every construction level stays on the source lattice and the 8-bit encoding is exact:
Under ExactDoubled a source value v is represented by 2 * v; odd values represent half levels, and reconstructFromNodeAltitudes() also returns doubled values. Half levels are never quantized into std::uint8_t, because doing so can create equal-altitude parent-child edges and destroy shape polarity.
The published altitude type is a compile-time choice in C++ and must match the encoding declared by the convention; createTreeOfShapes throws std::invalid_argument when they disagree. Python selects the instantiation from the altitude_encoding field at run time.
Every non-root tree-of-shapes node has a polarity derived from these exact altitudes:
ShapePolarity::Upper when the node altitude is greater than its parent altitude;ShapePolarity::Lower when the node altitude is less than its parent altitude.The root has no shape polarity. Scalar bitquad materialization uses an explicit BitquadConnectivityPolicy after hierarchy-independent bitquad-family counts have been computed. Under a complementary convention, lower shapes use minAdjacency, upper shapes use maxAdjacency, and the unpolarized root follows the policy's explicit root connectivity. The current root projection remains 8-connected when the two complementary choices differ; this is not inferred by classifying the root as an upper or lower shape.
Use ValuedMorphologicalTree<T> when an operation must own topology and altitude state, including:
UltimateAttributeOpening, adjust::CasfComponentTrees, and paired-tree adjustment;Use ValuedMorphologicalTreeView<T> for read-only C++ operations over caller-owned altitude storage:
The caller must keep the topology and altitude storage alive for the lifetime of the view. A view captures the topology mutation version and rejects reads after the topology changes.
The internal node domain is dense:
Edits may leave dead internal slots. Node-indexed buffers retain the complete slot count so existing IDs remain addressable. In C++, iterate tree.aliveNodeIds() when consuming live nodes; in Python, use the tree.alive_node_ids property.
Image pixels have row-major IDs:
The main structural queries are:
properPart(node) returns the pixels in \(\rho(X)=X\setminus\bigcup_{Y\in children(X)}Y\). nodeSupport(node) returns every pixel in the complete node support. The smallest-node map satisfies pixel in properPart(smallestNode(pixel)).
Topology query names describe the relation they return:
| Meaning | C++ | Python |
|---|---|---|
| root node | root() | root |
| parent node | parent(node) | parent(node) |
| direct children | children(node) | children(node) |
| inclusive ancestor chain | ancestors(node) | ancestors(node) |
| strict descendants | descendants(node) | descendants(node) |
| inclusive subtree | subtreeNodes(node) | subtree_nodes(node) |
| lowest common ancestor | lowestCommonAncestor(a, b) | lowest_common_ancestor(a, b) |
| batch of lowest common ancestors | lowestCommonAncestors(pairs) | lowest_common_ancestors(pairs) |
ancestors(node) includes node itself and ends at the root. Conversely, descendants(node) excludes node, whereas subtreeNodes(node) includes it. The subtree range uses pre-order, but callers must rely on the stated relation rather than on incidental sibling order unless an algorithm explicitly defines that order.
postOrder() and breadthFirstTraversal() (Python: post_order and breadth_first_traversal) return tree-wide traversal schedules. Post-order visits every child before its parent. It can schedule bottom-up aggregation, but traversal and aggregation are distinct operations.
lowestCommonAncestors(pairs) preserves the order of the input pairs. Invalid, dead, or disconnected endpoints produce InvalidNode (-1 in Python), matching the scalar query.
The batch operation reuses the tree's Euler tour and range minimum query cache when that cache already exists. Without it, depth-first search intervals first resolve equal nodes, ancestor pairs, and disconnected nodes. The remaining incomparable pairs use either an Euler/RMQ index or iterative offline Tarjan. The implementation estimates both storage requirements from the number N of node slots and the number Q of pairs, then chooses the smaller representation. Tarjan takes O((N + Q) alpha(N)) time and O(N + Q) temporary storage and does not create a persistent LCA cache. The Euler/RMQ representation uses O(N log N) storage and remains available to later tree queries.
dfsEntryIndex(node) and dfsExitIndex(node) (Python: dfs_entry_index(node) and dfs_exit_index(node)) are indices in one shared, zero-based DFS event sequence. The counter advances when DFS enters a node and again when it exits after visiting every descendant. For a tree with numNodes() live nodes, the combined entry and exit indices form a permutation of [0, 2 * numNodes()).
The inclusive ancestor relation is characterized by interval containment: \(u\) is an ancestor of \(v\) exactly when dfsEntryIndex(u) <= dfsEntryIndex(v) and dfsExitIndex(u) >= dfsExitIndex(v). The number of strict descendants is (dfsExitIndex(node) - dfsEntryIndex(node) - 1) / 2. These values are event indices, not wall-clock timestamps or independent positions in two traversals.
Node IDs and pixel IDs are independent domains. A live node may have an empty proper part when its support is supplied by descendants. Every committed live node must nevertheless have non-empty node support. Such a tree remains a valid MorphologicalTree, but it is not a morphological tree of partial partitions; use isTreeOfPartialPartitions() or validateTreeOfPartialPartitions() when that stricter specialization is required.
Builders that already have node parents and smallest-node mapping can use the native representation directly:
This overload attaches no coordinate interpretation. Topology/support attributes remain available, while reconstruction and geometry-dependent attributes reject the missing GridDomain2D. An overload with rows and columns attaches a regular 2D domain and requires one smallest-node-map entry per grid position.
NativeHierarchyView<T> provides the equivalent synchronous C++ import from borrowed spans. The factory copies or moves the validated buffers into owning tree storage.
Altitude buffers are indexed by internal NodeId:
Accepted altitude types satisfy AltitudeValue:
bool is rejected.Construction and committed edits validate strict parent/child inequalities for ordered hierarchies. NodeAltitudeOrder::Unconstrained skips only monotonicity validation; buffer shape and finite values remain required.
GrayLevelHeight is defined for every altitude order as the maximum absolute altitude difference between a node and any node in its subtree. On monotone max-tree and min-tree hierarchies this is the usual one-sided gray-level span.
The project adopts the fixed reconstruction baseline zero. For every non-root node n, nodeResidue(n) is nodeAltitude(n) - nodeAltitude(parent(n)); for the root it is simply nodeAltitude(root). No baseline parameter or baseline state is part of the public API.
With this convention, summing node residues along the path from the root to a node telescopes to that node's altitude. Assigning the resulting altitude to each pixel through its smallest node therefore reconstructs the image represented by the valued tree. reconstructFromNodeAltitudes() performs the equivalent direct reconstruction from the stored node altitudes.
pruneNode(node) and mergeNodeIntoParent(node) are complete local edits. Multi-step structural changes use an editor session and cross a checked commit boundary. Topology mutations invalidate cached objects and node-indexed results computed against the previous topology. See Editing API for rollback, valued-tree edits, and Python exposure.
1.9.8