kuhn_munkres.hpp

// Copyright (C) 2018-2024 Intel Corporation
// SPDX-License-Identifier: Apache-2.0
//
 
#pragma once
 
#include "opencv2/core.hpp"
 
#include <memory>
#include <vector>
 
 
class KuhnMunkres {
public:
    explicit KuhnMunkres(bool greedy = false);
 
    std::vector<size_t> Solve(const cv::Mat &dissimilarity_matrix);
 
private:
    static constexpr int kStar = 1;
    static constexpr int kPrime = 2;
 
    cv::Mat dm_;
    cv::Mat marked_;
    std::vector<cv::Point> points_;
 
    std::vector<int> is_row_visited_;
    std::vector<int> is_col_visited_;
 
    int n_;
    bool greedy_;
 
    void TrySimpleCase();
    bool CheckIfOptimumIsFound();
    cv::Point FindUncoveredMinValPos();
    void UpdateDissimilarityMatrix(float val);
    int FindInRow(int row, int what);
    int FindInCol(int col, int what);
    void Run();
};