component_tree.rst 11.8 KB
Newer Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
Component Trees (Overview)
==========================

* Include :file:`<mln/morpho/component_tree.hpp>`
* Include :file:`<mln/morpho/maxtree.hpp>`
* Include :file:`<mln/morpho/tos.hpp>`

.. cpp:namespace:: mln::morpho



Component trees are morphological hierarchical representations of
images based on their level set decomposition:

* The *min-tree* organizes lower connected-components into a tree:

  .. math::

     \Gamma^- = \{ CC(X) : X \in [u \le \lambda] \}

* The *max-tree* organizes upper connected-components into a tree:

  .. math::

     \Gamma^+ = \{ CC(X) : X \in [u \ge \lambda] \}

* The *tree of shapes* merges the hole-filled components of the  min and
  max-trees into a single tree.


.. list-table:: Example
    :align: center
    :widths: 2 1 1 1

    * - Input
      - Min-tree
      - Max-tree
      - Tree of Shapes
    * - .. image:: /figures/morpho/simpleimage_grayv.svg  
        .. image:: /figures/morpho/simpleimage-shapes.svg
      - .. image:: /figures/morpho/simpleimage-mintree.svg
      - .. image:: /figures/morpho/simpleimage-maxtree.svg
      - .. image:: /figures/morpho/simpleimage-tos.svg



.. contents:: Table of contents
    :local:


Component tree Internal Representation
--------------------------------------

A tree is represented as an array of nodes where a node contains:

1. The index of the parent node
2. The level of the current node

The :cpp:class:`component_tree` is thus composed of two arrays:

1. A ``parent`` array with element of type ``int``
2. A ``level`` array 

These arrays are **sorted** in the topological order, that is, we have ``parent[i] < i``. The parent of the root
node is -1 (``parent[0] = -1``).

The correspondance between the pixels and the node they belong is stored in an image, called the `node_map`.

.. list-table:: Example
    :align: center

    * - Node map
      - Component tree internal arrays
    * - .. image:: /figures/morpho/simpleimage-nodemap.svg
      - .. image:: /figures/morpho/simpleimage-treenc.svg

.. cpp:class::  template <class V> component_tree

    .. cpp:var:: std::vector<int> parent

        Get the underlying *parent* array

    .. cpp:var:: std::vector<V> levels

        Get the underlying *levels*

Computing trees
---------------

See :doc:`maxtree` and :doc:`tos`.


Tree traversal examples
-----------------------

.. topic:: Traversing a branch to get all the components containing `p`

    .. code::

        int id = node_map(p);
        while (id != -1) {
            // do something with id
            id = t.parent[id];
        }

.. topic:: Computing the size of each component of tree `t`

   .. code::

        std::size_t n = t.size();
        std::vector<int> sz(n, 0);
        // Iterate on the image
        mln_foreach(auto id, node_map.values())
          sz[id]++;

        // Accumulate bottom up
        for (int i = n - 1; i > 0; --i)
          sz[t.parent[i]] += sz[n];


Attribute Computation
---------------------

It is common to associate values to nodes. The implementation keeps a distinction between the data structure (the
*tree*) and the values associated to the nodes through *property maps*. A property map is a mapping `node id -> value`
that is encoded with a standard vector.

Here is a example to compute the number of children per node for a tree `t`::

    // Declare and initialize to 0 a property map for the tree `t`:
    std::size_t n = t.size();
    std::vector<int> nchildren(n, 0);

    for (int i = n - 1; i > 0; --i)
        nchildren[t.parent[i]]++;


One may compute features for each component of the tree (e.g. for filtering) related with the image content. Most common
attributes are related to the shape of the component or its colors, e.g.:

* The size of the component
* The average gray level of the component
* The circularity of the component
* ...

A :cpp:class:`component_tree` `t` has the following methods.


.. cpp:namespace-push::  template <class V> component_tree

151
152
153
.. cpp:function:: auto compute_attribute_on_points(Image node_map, Accumulator accu, bool propagate) const
                  auto compute_attribute_on_values(Image node_map, Image values, Accumulator accu, bool propagate) const
                  auto compute_attribute_on_pixels(Image node_map, Image values, Accumulator accu, bool propagate) const
154
155
156
157
158
159

    Accumulate the points of each component.

    :param node_map: An image thats maps: point -> node id
    :param values: An image where values to accumlate are taken from
    :param accu: The feature to compute
160
    :param propagate: Option to propagate the values to the parent (default: true)
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193

    :return: A vector mapping for each node the result of accumulation.

    Pseudo-code::

        std::vector<Acc> accus(n);
        std::vector<...> result(n);

        // (1) On points
        mln_foreach(auto px, node_map.pixels())
            accus[px.val()].take(px.point());
        
        // or (2) On values
        auto zz = mln::ranges::view::zip(node_map.values(), values.values());
        mln_foreach((auto [id, v]), zz)
            accus[id].take(v);

        // or (3) on pixels
        mln_foreach(auto px, values.pixels())
            accus[node_map(px.point())].take(px);           

        for (int i = n-1; i > 0; --i)
            accus[parent[i]].take(accus[i]);
        
        std::ranges::transform(accus, result, [](auto&& a) { return a.to_result(); });


Example: computing the size (number of points) of the components.

::

    #include <mln/accu/accumulators/count.hpp>

194
    auto sizes = tree.compute_attribute_on_points(node_map, mln::accu::features::count<>());
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258

.. cpp:function:: auto compute_depth() const

    Compute the depth attribute for each node where *depth* stands for the length of the path from the root to the node.
    (the root node has a null depth).

    :return: An `int` vector mapping `node_id -> int`





Tree Filtering
--------------

Filtering is also a common operation on morphological trees to simplify the tree or filter some unwanted shapes.  Let
`pred` be a predicate where `pred(x) = true` says that we want to preserve the node of id `x`. We have the following
filtering strategies.

MIN (`CT_FILTER_MIN`)

    A node is remove if it does not pass the predicate and all its descendant are removed as well. Formally, a component
    Γ is kept if  𝓒(Γ) with 𝓒(Γ) = ⋁ { 𝓟(Γ'), Γ ⊆ Γ' }.

MAX (`CT_FILTER_MAX`)

    A node is remove if every node in its childhood does not pass
    the predicate. All its descendant are removed as well.  Formally, a
    component Γ is kept if 𝓒(Γ) with 𝓒(Γ) = ⋀ { 𝓟(Γ'), Γ' ⊆ Γ }.

DIRECT (`CT_FILTER_DIRECT`)

    A node is remove if it does not pass the predicate, the others remain.


A :cpp:class:`component_tree` `t` has the following methods.

.. cpp:function::  void filter(ct_filtering strategy, Predicate pred)
                   void filter(ct_filtering strategy, Image node_map, Predicate pred)


    Filter the tree according to a given strategy. If *node_map* is provided, it is updated so that
    pixels map to valid nodes.

    :param strategy: The filtering strategy
    :param node_map: (Optional) An image thats maps ``point -> node id``
    :param pred: The predicate fuction ``node id -> bool``

    .. rubric:: Example


    Here is an example of filtering to collapse the nodes part of a chain
    to simplify the tree::

        #include ... // as above
        #include <mln/morpho/component_tree.hpp>

        component_tree<uint8_t> t = ...;
        std::vector<int> nchildren;
        // Compute the attribute node_id -> #number of children (see above)

        auto pred = [&](int id) { nchildren > 1; };      
        t.filter(CT_FILTER_DIRECT, pred);

259

260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
Image reconstruction
--------------------

The next step after image filtering is generally the reconstruction of
the image from the filtered tree.

.. cpp:function::  auto reconstruct(Image node_map)
                   auto reconstruct_from(Image node_map, std::span<V> values)

    Reconstruct the tree from the initial levels or from levels taken from the parameter *values*.


    :param node_map: An image thats maps ``point -> node id``
    :param values: (Optional) Recontruction values (default is ``t.levels``) 

    .. rubric:: Example

    Connected opening of size 20::

        auto [t, node_map] = ...; // Tree Computation
        auto area = t.compute_attribute_on_points(node_map, mln::accu::features::count<>());
        t.filter(CT_FILTER_DIRECT, [&area](int id) { return area[id] > 20; });
        auto out = t.reconstruct(node_map);

284
285
286
287
288
Horizontal cut
--------------
When the tree is a hierarchy of partition, such as the :doc:`alphatree`, it is possible
to make an horizontal cut of this tree.

289
290
.. cpp:function::   I horizontal_cut(const T threshold, I nodemap) const
                    I horizontal_cut_from_levels(const T threshold, I nodemap, ::ranges::span<V> levels) const
291

292
    Make an horizontal cut at threshold ``threshold`` of the tree and return the nodemap associated to the cut.
293

294
295
296
    :param threshold: The threshold of the horizontal cut
    :param nodemap: An image thats maps ``point -> node id``
    :param levels: (Optional) The altitude of each node in the tree (for example the :math:`\alpha` associated to each node for the alphatree).
297

298
Saliency Computation
299
--------------------
300
301
It is also possible to compute the saliency map to obtain another visualization.

Baptiste Esteban's avatar
Baptiste Esteban committed
302
.. cpp:function:: auto saliency(image2d<int> node_map, ranges::span<double> values) const
303

Baptiste Esteban's avatar
Baptiste Esteban committed
304
    Compute and return the saliency map of the tree. **Works only for 2D images and with tree node values of type** ``double``.
305
306

    :param node_map: An image thats maps ``point -> node id``
Baptiste Esteban's avatar
Baptiste Esteban committed
307
    :param values: the levels of the tree for each node
308
309
310

    :return: The saliency map as an image

311
312
.. list-table::

Baptiste Esteban's avatar
Baptiste Esteban committed
313
   * - .. image:: /images/lena_gray.jpg
314
315
316
317
318
          :width: 100%

     - .. image:: /images/saliency_watershed.png
          :width: 100%

Baptiste Esteban's avatar
Baptiste Esteban committed
319
320
   * - Original image
     - Saliency map of the watershed hierarchy by area
321

322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
A complete example
------------------

Filtering the square roadsigns.

.. image:: /snippets/images/roadsigns.png

Method description
^^^^^^^^^^^^^^^^^^

The method will proceed as follows:

1. Compute the ToS of the input image::

    auto [t, node_map] = mln::morpho::tos(f);

2. The ToS uses a special representation that needs to double the
   size of the image by adding intermediate pixels. We thus need to
   reconstruct an image of the right size::

        mln::image2d<uint8_t> f2 = t.reconstruct(node_map);



3. Compute the bounding box, the size and the variance of each shape. We create a custom
   accumulator object for this, whose implementation is described below in the full code section::

        struct my_accu_t : mln::Accumulator<my_accu_t>
         {
           using result_type   = my_accu_t;
352
           using argument_type = mln::image_pixel_t<mln::image2d<uint8_t>>;
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381

           my_accu_t() = default;

           template <class Pix> void take(Pix px) { ... };
           void take(const my_accu_t& other) { ... };

           int count() const { ... }
           int area_bbox() const { ... }
           double variance() const { ... }
           my_accu_t to_result() const { return *this; }
         };

        auto prop_map = t.compute_attribute_on_pixels(node_map, f2, my_accu_t{});


4. Filter the objects that:

   * are not too big (< 1000 x 1000 pixels)
   * are not too small (> 100 x 100 pixels)
   * cover 95% of the bounding box at least (so rectangular shapes)

   ::

        auto pred = [&prop_map](int x) {
            int sz = prop_map[x].count();
            return sz > (0.95 * prop_map[x].area_bbox()) && sz > 10000 and sz < 1000000 and prop_map[x].variance() > 250;
        };

        // Filter
382
        t.filter(mln::morpho::CT_FILTER_DIRECT, node_map, pred);
383
384
385
386
387
388
389
390
391
392
393
394
395

5. Reconstruct the image::

    t.values[0] = 0; // Set the root gray level to 0
    auto out = t.reconstruct(node_map);


.. image:: /snippets/images/roadsigns-square-2.png

Full code
^^^^^^^^^

.. literalinclude:: /snippets/component_tree_1.cpp