DynamicTreeAttributeComputer.hpp

#pragma once
 
#include "../ValuedMorphologicalTree.hpp"
#include "../../utils/Image.hpp"
 
#include <algorithm>
#include <cmath>
#include <utility>
#include <vector>
 
namespace mmcfilters::adjust {
 
enum class BoundingBoxMeasure {
    Width,
    Height,
    DiagonalLength
};
 
template <AltitudeValue T> class DynamicTreeAttributeComputer {
  public:
    using buffer_type = std::vector<double>;
 
    virtual ~DynamicTreeAttributeComputer() = default;
 
    virtual void resize(const ValuedMorphologicalTree<T>& tree, buffer_type& buffer) const {
        buffer.resize(static_cast<size_t>(tree.topology().numInternalNodeSlots()), 0.0);
    }
 
    virtual void preProcessing(NodeId nodeId, const ValuedMorphologicalTree<T>& tree, buffer_type& buffer) const = 0;
 
    virtual void mergeProcessing(NodeId parentId, NodeId childId, const ValuedMorphologicalTree<T>& tree, buffer_type& buffer) const = 0;
 
    virtual void postProcessing(NodeId nodeId, const ValuedMorphologicalTree<T>& tree, buffer_type& buffer) const = 0;
 
    virtual void onMoveProperParts(NodeId, NodeId, const ValuedMorphologicalTree<T>&) const {}
 
    virtual void onMoveProperPart(NodeId, NodeId, PixelId, const ValuedMorphologicalTree<T>&) const {}
 
    virtual void onNodeRemoved(NodeId, const ValuedMorphologicalTree<T>&) const {}
 
    void computeAttribute(const ValuedMorphologicalTree<T>& tree, buffer_type& buffer) const {
        resize(tree, buffer);
        const MorphologicalTree& topology = tree.topology();
        for (NodeId nodeId : topology.postOrder()) {
            preProcessing(nodeId, tree, buffer);
            for (NodeId childId : topology.children(nodeId)) {
                mergeProcessing(nodeId, childId, tree, buffer);
            }
            postProcessing(nodeId, tree, buffer);
        }
    }
 
    void computeAttributeOnNode(const ValuedMorphologicalTree<T>& tree, NodeId nodeId, buffer_type& buffer) const {
        preProcessing(nodeId, tree, buffer);
        for (NodeId childId : tree.topology().children(nodeId)) {
            mergeProcessing(nodeId, childId, tree, buffer);
        }
        postProcessing(nodeId, tree, buffer);
    }
};
 
template <AltitudeValue T> class DynamicAreaAttributeComputer : public DynamicTreeAttributeComputer<T> {
  private:
    using base_t = DynamicTreeAttributeComputer<T>;
 
  public:
    using buffer_type = typename base_t::buffer_type;
 
  public:
    void preProcessing(NodeId nodeId, const ValuedMorphologicalTree<T>& tree, buffer_type& buffer) const override {
        buffer[static_cast<size_t>(nodeId)] = static_cast<double>(tree.topology().properPartCardinality(nodeId));
    }
 
    void mergeProcessing(NodeId parentId, NodeId childId, const ValuedMorphologicalTree<T>&, buffer_type& buffer) const override {
        buffer[static_cast<size_t>(parentId)] += buffer[static_cast<size_t>(childId)];
    }
 
    void postProcessing(NodeId, const ValuedMorphologicalTree<T>&, buffer_type&) const override {}
};
 
template <AltitudeValue T> class DynamicBoundingBoxAttributeComputer : public DynamicTreeAttributeComputer<T> {
  private:
    using base_t = DynamicTreeAttributeComputer<T>;
 
  public:
    using buffer_type = typename base_t::buffer_type;
 
  private:
    struct BoxState {
        int xmin = 0;
        int xmax = -1;
        int ymin = 0;
        int ymax = -1;
        bool empty = true;
    };
 
    struct LocalBoxState {
        int xmin = 0;
        int xmax = -1;
        int ymin = 0;
        int ymax = -1;
        int xminCount = 0;
        int xmaxCount = 0;
        int yminCount = 0;
        int ymaxCount = 0;
        int properPartCount = 0;
        bool empty = true;
        bool dirty = true;
    };
 
    BoundingBoxMeasure measure_ = BoundingBoxMeasure::DiagonalLength;
    mutable std::vector<LocalBoxState> local_;
    mutable std::vector<BoxState> subtree_;
 
    static void resetLocalBox(LocalBoxState& local) {
        local.xmin = 0;
        local.xmax = -1;
        local.ymin = 0;
        local.ymax = -1;
        local.xminCount = 0;
        local.xmaxCount = 0;
        local.yminCount = 0;
        local.ymaxCount = 0;
        local.properPartCount = 0;
        local.empty = true;
    }
 
    void resetLocalSummary(NodeId nodeId) const {
        auto& local = local_[static_cast<size_t>(nodeId)];
        resetLocalBox(local);
        local.dirty = false;
    }
 
    void resetSubtreeSummary(NodeId nodeId) const {
        auto& subtree = subtree_[static_cast<size_t>(nodeId)];
        subtree.xmin = 0;
        subtree.xmax = -1;
        subtree.ymin = 0;
        subtree.ymax = -1;
        subtree.empty = true;
    }
 
    void expandLocalBoxWithPixel(LocalBoxState& local, PixelId pixelId, int numColumns) const {
        const auto [y, x] = ImageUtils::to2D(pixelId, numColumns);
        if (local.empty) {
            local.xmin = x;
            local.xmax = x;
            local.ymin = y;
            local.ymax = y;
            local.xminCount = 1;
            local.xmaxCount = 1;
            local.yminCount = 1;
            local.ymaxCount = 1;
            local.empty = false;
            return;
        }
 
        if (x < local.xmin) {
            local.xmin = x;
            local.xminCount = 1;
        } else if (x == local.xmin) {
            ++local.xminCount;
        }
 
        if (x > local.xmax) {
            local.xmax = x;
            local.xmaxCount = 1;
        } else if (x == local.xmax) {
            ++local.xmaxCount;
        }
 
        if (y < local.ymin) {
            local.ymin = y;
            local.yminCount = 1;
        } else if (y == local.ymin) {
            ++local.yminCount;
        }
 
        if (y > local.ymax) {
            local.ymax = y;
            local.ymaxCount = 1;
        } else if (y == local.ymax) {
            ++local.ymaxCount;
        }
    }
 
    void rebuildLocalBox(NodeId nodeId, const ValuedMorphologicalTree<T>& tree) const {
        auto& local = local_[static_cast<size_t>(nodeId)];
        resetLocalBox(local);
        const int numColumns = tree.topology().numColumns();
        for (PixelId pixelId : tree.topology().properPart(nodeId)) {
            expandLocalBoxWithPixel(local, pixelId, numColumns);
        }
        local.properPartCount = tree.topology().properPartCardinality(nodeId);
        local.dirty = false;
    }
 
    void ensureLocalSummary(NodeId nodeId, const ValuedMorphologicalTree<T>& tree) const {
        auto& local = local_[static_cast<size_t>(nodeId)];
        const int properPartCount = tree.topology().properPartCardinality(nodeId);
        if (!local.dirty && local.properPartCount == properPartCount) {
            return;
        }
        rebuildLocalBox(nodeId, tree);
    }
 
    void copyLocalToSubtree(NodeId nodeId) const {
        const auto& local = local_[static_cast<size_t>(nodeId)];
        auto& subtree = subtree_[static_cast<size_t>(nodeId)];
        subtree.xmin = local.xmin;
        subtree.xmax = local.xmax;
        subtree.ymin = local.ymin;
        subtree.ymax = local.ymax;
        subtree.empty = local.empty;
    }
 
    static void mergeSubtreeStates(BoxState& target, const BoxState& source) {
        if (source.empty) {
            return;
        }
        if (target.empty) {
            target = source;
            return;
        }
        target.xmin = std::min(target.xmin, source.xmin);
        target.xmax = std::max(target.xmax, source.xmax);
        target.ymin = std::min(target.ymin, source.ymin);
        target.ymax = std::max(target.ymax, source.ymax);
        target.empty = false;
    }
 
    static void mergeLocalBoxes(LocalBoxState& target, const LocalBoxState& source) {
        if (source.empty) {
            return;
        }
        if (target.empty) {
            target = source;
            return;
        }
 
        if (source.xmin < target.xmin) {
            target.xmin = source.xmin;
            target.xminCount = source.xminCount;
        } else if (source.xmin == target.xmin) {
            target.xminCount += source.xminCount;
        }
 
        if (source.xmax > target.xmax) {
            target.xmax = source.xmax;
            target.xmaxCount = source.xmaxCount;
        } else if (source.xmax == target.xmax) {
            target.xmaxCount += source.xmaxCount;
        }
 
        if (source.ymin < target.ymin) {
            target.ymin = source.ymin;
            target.yminCount = source.yminCount;
        } else if (source.ymin == target.ymin) {
            target.yminCount += source.yminCount;
        }
 
        if (source.ymax > target.ymax) {
            target.ymax = source.ymax;
            target.ymaxCount = source.ymaxCount;
        } else if (source.ymax == target.ymax) {
            target.ymaxCount += source.ymaxCount;
        }
 
        target.properPartCount += source.properPartCount;
        target.empty = false;
        target.dirty = false;
    }
 
  public:
    explicit DynamicBoundingBoxAttributeComputer(BoundingBoxMeasure measure = BoundingBoxMeasure::DiagonalLength) : measure_(measure) {}
 
    void resize(const ValuedMorphologicalTree<T>& tree, buffer_type& buffer) const override {
        base_t::resize(tree, buffer);
        const size_t size = static_cast<size_t>(tree.topology().numInternalNodeSlots());
        local_.resize(size);
        subtree_.resize(size);
    }
 
    void preProcessing(NodeId nodeId, const ValuedMorphologicalTree<T>& tree, buffer_type&) const override {
        ensureLocalSummary(nodeId, tree);
        copyLocalToSubtree(nodeId);
    }
 
    void mergeProcessing(NodeId parentId, NodeId childId, const ValuedMorphologicalTree<T>&, buffer_type&) const override {
        mergeSubtreeStates(subtree_[static_cast<size_t>(parentId)], subtree_[static_cast<size_t>(childId)]);
    }
 
    void postProcessing(NodeId nodeId, const ValuedMorphologicalTree<T>&, buffer_type& buffer) const override {
        const auto& subtree = subtree_[static_cast<size_t>(nodeId)];
        if (subtree.empty) {
            buffer[static_cast<size_t>(nodeId)] = 0.0;
            return;
        }
 
        const double width = static_cast<double>(subtree.xmax - subtree.xmin + 1);
        const double height = static_cast<double>(subtree.ymax - subtree.ymin + 1);
        switch (measure_) {
        case BoundingBoxMeasure::Width:
            buffer[static_cast<size_t>(nodeId)] = width;
            break;
        case BoundingBoxMeasure::Height:
            buffer[static_cast<size_t>(nodeId)] = height;
            break;
        case BoundingBoxMeasure::DiagonalLength:
            buffer[static_cast<size_t>(nodeId)] = std::sqrt(width * width + height * height);
            break;
        }
    }
 
    void onMoveProperParts(NodeId targetId, NodeId sourceId, const ValuedMorphologicalTree<T>& tree) const override {
        ensureLocalSummary(targetId, tree);
        ensureLocalSummary(sourceId, tree);
        mergeLocalBoxes(local_[static_cast<size_t>(targetId)], local_[static_cast<size_t>(sourceId)]);
        resetLocalSummary(sourceId);
    }
 
    void onMoveProperPart(NodeId targetId, NodeId sourceId, PixelId pixelId, const ValuedMorphologicalTree<T>& tree) const override {
        ensureLocalSummary(targetId, tree);
        if (sourceId != InvalidNode) {
            ensureLocalSummary(sourceId, tree);
        }
 
        const int numColumns = tree.topology().numColumns();
        expandLocalBoxWithPixel(local_[static_cast<size_t>(targetId)], pixelId, numColumns);
        local_[static_cast<size_t>(targetId)].properPartCount += 1;
        local_[static_cast<size_t>(targetId)].dirty = false;
 
        if (sourceId == InvalidNode) {
            return;
        }
 
        auto& source = local_[static_cast<size_t>(sourceId)];
        if (source.properPartCount <= 1) {
            resetLocalSummary(sourceId);
            return;
        }
 
        const auto [y, x] = ImageUtils::to2D(pixelId, numColumns);
        --source.properPartCount;
 
        bool exhaustsXmin = false;
        bool exhaustsXmax = false;
        bool exhaustsYmin = false;
        bool exhaustsYmax = false;
 
        if (!source.dirty) {
            if (x == source.xmin) {
                if (source.xminCount <= 1) {
                    exhaustsXmin = true;
                } else {
                    --source.xminCount;
                }
            }
            if (x == source.xmax) {
                if (source.xmaxCount <= 1) {
                    exhaustsXmax = true;
                } else {
                    --source.xmaxCount;
                }
            }
            if (y == source.ymin) {
                if (source.yminCount <= 1) {
                    exhaustsYmin = true;
                } else {
                    --source.yminCount;
                }
            }
            if (y == source.ymax) {
                if (source.ymaxCount <= 1) {
                    exhaustsYmax = true;
                } else {
                    --source.ymaxCount;
                }
            }
        }
 
        source.dirty = source.dirty || exhaustsXmin || exhaustsXmax || exhaustsYmin || exhaustsYmax;
    }
 
    void onNodeRemoved(NodeId nodeId, const ValuedMorphologicalTree<T>&) const override {
        resetLocalSummary(nodeId);
        resetSubtreeSummary(nodeId);
    }
};
 
} // namespace mmcfilters::adjust