# Comparisons between our implementation, Alpha Tree and Higra
## Computer Details
### CPU
- Intel(R) Core(TM) i5-7300HQ @ 2.50GHz
- Run on (4 X 3500 MHz CPU s)
- CPU Caches:
- L1 Data 32 KiB (x4)
- L1 Instruction 32 KiB (x4)
- L2 Unified 256 KiB (x4)
- L3 Unified 6144 KiB (x1)
### RAM
- 16 GO DDR4 2400 MT/s
## Remarks
- Alpha Tree implementation is the one developped by Edwin Carlinet
- Parallel sort in next part is the sort before the kruskal algorithm that has been made parallel thanks to the parallel STL and more precisely std::execution::par. When parallel sort is mentionned, both our implementation and Alpha Tree benefits from it.
- Tuple optimization is the replacement of std::tuple by a struct in our implementation.
## Tools
Our implementation and Alpha Tree has been benchmark using Google Benchmark and Higra has been benchmark using timeit builtin in python.
The profiling has been done using the perf tool.
## Quasi Flat Zone construction
### Without parallel sort / tuple optimization but with parallel Higra
#### Benchmark
| | Our implementation | Alpha Tree | Higra |
|:-----------------------:|:------------------:|:----------:|:-------:|
| Plane (766 x 518) | 0.678 s | 0.427 s | 0.222 s |
| Nature (3903 x 2925) | 27.8 s | 19.9 s | 9.61 s |
| Mountains (5472 x 3648) | 49.4 s | 32.2 s | 14.9 s |
| Hong Kong (8192 x 5187) | 108 s | 78.4 s | 40.5 s |
#### Profiling on Plane image (766 x 518)
##### Alpha Tree
| Time percentage | Step |
|:---------------:|:------------------:|
| 29% | Sort of edges |
| 25% | Graph construction |
| 25% | Kruskal |
| 5% | Node map creation |
##### Our implementation
| Time percentage | Step |
|:---------------:|:-------------------:|
| 44% | Sort of edges |
| 22% | Kruskal |
| 6% | Tree simplification |
| 5% | Graph construction |
### With parallel sort / tuple optimization / parallel Higra
#### Benchmark
| | Our implementation | Alpha Tree | Higra |
|:-----------------------:|:------------------:|:----------:|:-------:|
| Plane (766 x 518) | 0.298 s | 0,303 s | 0.222 s |
| Nature (3903 x 2925) | 11.2 s | 11.9 s | 9.61 s |
| Mountains (5472 x 3648) | 17.7 s | 18.5 s | 14.9 s |
| Hong Kong (8192 x 5187) | 45.2 s | 49.9 s | 40.5 s |
<!-- ### Profiling on Plane (766 x 518)
#### Alpha Tree
| Time percentage | Step |
|:---------------:|:------------------:|
| 28% | Sort of edges |
| 22% | Graph construction |
| 29% | Kruskal |
| 5% | Node map creation |
#### Our implementation
| Time percentage | Step |
|:---------------:|:-------------------:|
| 28% | Sort of edges |
| 27% | Kruskal |
| 10% | Graph construction |
| 9% | Tree simplification | -->
#### Profiling on Hong Kong image (8192 x 5187)
##### Alpha Tree
| Time percentage | Step |
|:---------------:|:------------------:|
| 35% | Kruskal |
| 28% | Sort of edges |
| 15% | Graph construction |
| 5% | Node map creation |
##### Our implementation
| Time percentage | Step |
|:---------------:|:-------------------:|
| 32% | Kruskal |
| 28% | Sort of edges |
| 12% | Tree simplification |
| 7% | Graph construction |
### Without parallel sort / parallel Higra but with tuple optimization
| | Our implementation | Alpha Tree | Higra |
|:-----------------------:|:------------------:|:----------:|:-------:|
| Plane (766 x 518) | 0.396 s | 0.418 s | 0.491 s |
| Nature (3903 x 2925) | 16.3 s | 18.3 s | 20.1 s |
| Mountains (5472 x 3648) | 29.1 s | 31.2 s | 33.5 s |
| Hong Kong (8192 x 5187) | 70.9 s | 77.1 s | 81.2 s |
<!-- :warning: We cannot conclude that our implementation is faster than Alpha Tree because Alpha Tree implementation also include Pylene integration (node map and component tree). -->
### With hierarchical queues without parallel sort
| | Alpha Tree without HQueue | Alpha Tree With HQueue |
|:-----------------------:|:-------------------------:|:----------------------:|
| Plane (766 x 518) | 0.421 s | 0.852 s |
| Nature (3903 x 2925) | 18.5 s | 33.5 s |
| Mountains (5472 x 3648) | 31.7 s | 54.1 s |
| Hong Kong (8192 x 5187) | 78.1 s | 130 s |
## Quasi Flat Zone construction, Horizontal cut and Image reconstruction
The image reconstruction is done using mean color per node.
### With parallel sort / tuple optimization / parallel Higra
| | Threshold | Our implementation | Alpha Tree | Higra |
|:-----------------:|:---------:|:------------------:|:----------:|:-------:|
| Plane (766 x 518) | 0.05 | 0.694 s | 0.463 s | 8.71 s |
| Plane (766 x 518) | 100 | 0.551 s | 14.2 s | 0.282 s |
The difference between Alpha Tree and Higra can be explain by the horizontal cut algorithm.
In Higra, the cut begin at the root and, thus, is more efficient for high cuts.
In Alpha Tree, the cut begin at the leaves and, thus, is more efficient for low cuts.
## Final Benchmark
### Alpha Tree construction
```c=
// Pylene Alpha Tree without HQueue construction
mln::morpho::alphatree(img, mln::c4,
[](const auto& a, const auto& b) -> std::float_t { return mln::l2dist(a, b); });
// Pylene Alpha Tree with HQueue construction
mln::morpho::alphatree(img, mln::c4,
[](const auto& a, const auto& b) -> std::uint16_t { return mln::l2dist(a, b); });
```
```python=
# Higra Alpha Tree construction
graph = hg.get_4_adjacency_graph(img.shape[:2])
edge_weights = hg.weight_graph(graph, img, hg.WeightFunction.L2)
tree, altitudes = hg.quasi_flat_zone_hierarchy(graph, edge_weights)
```
| | Alpha Tree without HQueue | Alpha Tree With HQueue | Higra |
|:-----------------------:|:-------------------------:|:----------------------:|:-------:|
| Plane (766 x 518) | 0.082 s | 0.040 s | 0.198 s |
| Nature (3903 x 2925) | 5.78 s | 3.27 s | 9.44 s |
| Mountains (5472 x 3648) | 7.74 s | 4.26 s | 14.6 s |
| Hong Kong (8192 x 5187) | 24.67 s | 13.90 s | 39.8 s |
### Watershed hierarchy by area construction
```c=
// Pylene Watershed hierarchy by area construction
mln::morpho::watershed_hierarchy(img, mln::accu::features::count<>(), mln::c4,
[](const auto& a, const auto& b) -> std::float_t { return mln::l2dist(a, b); });
```
```python=
# Higra Watershed hierarchy by area construction
graph = hg.get_4_adjacency_graph(img.shape[:2])
edge_weights = hg.weight_graph(graph, img, hg.WeightFunction.L2)
tree, altitudes = hg.watershed_hierarchy_by_area(graph, edge_weights)
```
| | Alpha Tree | Higra |
|:-----------------------:|:----------:|:-------:|
| Plane (766 x 518) | 0.135 s | 0.344 s |
| Nature (3903 x 2925) | 9.16 s | 19.6 s |
| Mountains (5472 x 3648) | 12.9 s | 29.2 s |
| Hong Kong (8192 x 5187) | 39.5 s | |
### Hierarchical segmentation pipeline with watershed hierarchy by area
```c=
// Pylene Hierarchical segmentation pipeline with watershed hierarchy by area
auto [tree, node_map] =
mln::morpho::watershed_hierarchy(img, mln::accu::features::count<>(), mln::c4,
[](const auto& a, const auto& b) -> std::float_t { return mln::l2dist(a, b); });
auto mean = tree.compute_attribute_on_values(node_map, img, mln::accu::accumulators::mean<mln::rgb8>());
// th is the selected cut threshold
auto node_map_cut = tree.horizontal_cut(th, node_map);
tree.reconstruct_from(node_map_cut, ranges::make_span(mean));
```
```python=
# Higra Hierarchical segmentation pipeline with watershed hierarchy by area
graph = hg.get_4_adjacency_graph(img.shape[:2])
edge_weights = hg.weight_graph(graph, img, hg.WeightFunction.L2)
tree, altitudes = hg.watershed_hierarchy_by_area(graph, edge_weights)
# th is the selected cut threshold
explorer = hg.HorizontalCutExplorer(tree, altitudes)
cut_nodes = explorer.horizontal_cut_from_altitude(th)
mean_color = hg.attribute_mean_vertex_weights(tree, img)
output = cut_nodes.reconstruct_leaf_data(tree, mean_color)
```
#### Threshold cut at 1e6
| | Alpha Tree | Higra |
|:-----------------------:|:----------:|:-------:|
| Plane (766 x 518) | 0.151 s | 0.435 s |
| Nature (3903 x 2925) | 10.2 s | 22.1 s |
| Mountains (5472 x 3648) | 14.2 s | 36.1 s |
| Hong Kong (8192 x 5187) | 41.1 s | |
#### Threshold cut at 1e3
| | Alpha Tree | Higra |
|:-----------------------:|:----------:|:-------:|
| Plane (766 x 518) | 0.148 s | 0.617 s |
| Nature (3903 x 2925) | 9.92 s | 184 s |
| Mountains (5472 x 3648) | 14.3 s | 545 s |
| Hong Kong (8192 x 5187) | 40.9 s | |
Sign in with Wallet
Connect another wallet