correct_attribute_BPT

[ShoufaChen]

Hi,

Thanks for your awesome work.

I am confused by the following code:

Higra/include/higra/hierarchy/watershed_hierarchy.hpp

Lines 24 to 47 in 314a358

	auto correct_attribute_BPT(const tree_t &tree,
	const T1 &altitude,
	const T2 &attribute) {
	using value_type = typename T2::value_type;
	tree.compute_children();
	array_1d<value_type> result = xt::empty_like(attribute);
	for (auto n: leaves_iterator(tree)) {
	result(n) = 0;
	}
	for (auto n: leaves_to_root_iterator(tree, leaves_it::exclude, root_it::exclude)) {
	if (altitude(n) != altitude(parent(n, tree))) {
	result(n) = attribute(n);
	} else {
	value_type maxc = std::numeric_limits<value_type>::lowest();
	for (auto c: children_iterator(n, tree)) {
	maxc = (std::max)(maxc, (is_leaf(c, tree)) ? 0 : result(c));
	}
	result(n) = maxc;
	}
	}
	result(root(tree)) = attribute(root(tree));
	return result;
	};
	}

Could you give me some hints about the purpose of these steps?

Thanks in advance.

[PerretB]

Hello,

this function is here to handle cases where more than 2 neighboring minima merge at the same altitude. Consider the following case (Fig 3 of https://hal.archives-ouvertes.fr/hal-00798621/document ) where we consider an area attribute:

The nodes n1, n2 and n3 represent three minima, of respective sizes 2, 3 and 6, that are linked by edges of weight 1. Then the node n6 represent the merge of n1 and n2, its "true" area is 2+3 = 5. The node n7 is the merge of n6 and n3, its "true" area is 5 + 6 = 11.

Now, what we want is not the "true" area of the nodes: we want to know at which area filter size, the minima below a given node will disappear. The minima below n6 both disappear if we remove the components of area <= 3 = max(2,3). However, the situation is different for n7 which will still contain a minimum up to a filtering size of 11 = 5 + 6. We can differentiate those two situations by looking at the altitude of the current node and its parent: if the altitude is the same, we are in the first case, if they are different, it's the second case.

So the correct_attribute_BPT function takes as input a "real" attribute and deduce the "persistence" of the minima below a node for this attribute.

I hope this helps, this part is only very briefly described in the article mentioned above and as an internal function of the library it is even worse here :)

[PeizeSun]

@PerretB Hi, Thanks for your great work.

Could you give more explanation about "the situation is different for n7 which will still contain a minimum up to a filtering size of 11 = 5 + 6. " ? I am confused why area <= 6 = max(5,6) doesn't work for n7 ? Why different altitudes of the current node and its parent could differentiate those two situations ?

Thanks very much.

[PerretB]

In the case of n6, as its parent n7 has the same altitude, there isn't any "real" component with an area of 5. If we remove the components of area <= 3 we get this (sorry crappy figure editing, right part of the figure ignored):

There is no more minimum under n6, just a plateau that is part of the regional minimum represented by n3.

While in the case of n7, there is actually a component of area 11 in the signal. If we remove the components of area <= 6 we get this:

And there is a still a minimum of area 11 below n7.

[ShoufaChen]

Hi, @PerretB

Thanks very much for your illustration.

We have got a better understanding from your explanation.

However, we don't know why chose area <= 3 = max(2,3) for the first situation, i.e., why not min or mean?

Besides, what's the purpose of the following accumulate_parallel (by min)?

Higra/include/higra/hierarchy/watershed_hierarchy.hpp

Line 88 in 314a358

auto persistence = accumulate_parallel(bpt, corrected_attribute, accumulator_min());

[PerretB]

However, we don't know why chose area <= 3 = max(2,3) for the first situation, i.e., why not min or mean?

I suggest that you try making figures as I did : what happens if your remove components of area <= min(2,3) =2 or mean(2,3) = 2.5 ?

Besides, what's the purpose of the following accumulate_parallel (by min)?

For this you should refer to the paper Constructive links between some morphological hierarchies on edge-weighted graphs, in particular Section 7, Hierarchies of minimum spanning forests explains the definition of extinction and persistence values and their link with hierarchical watersheds.