Tutorial: Munkres Assignment Algorithm

Introduction

The Munkres algorithm described here aims to find an optimal solution which minimizes the total cost of the assignments.

For example, it can be used to match tracked (red) and detected (green) image points:

Note

It can also work with less (or more) detection than tracked points:

Warning

Keep in mind that Munkres minimizes the total cost of the assignments. As shown by the image below, minimizing the total cost can leads to, locally, not consider the closest points:

Assignment

The following example also available in tutorial-munkres-assignment.cpp shows how to use Munkres algorithm:

 
#include <functional>
 
#include <visp3/core/vpConfig.h>
// Display
#include <visp3/gui/vpDisplayFactory.h>
 
#include <visp3/core/vpColor.h>
 
// Munkres
#include <visp3/core/vpMunkres.h>
 
// Math
#include <visp3/core/vpUniRand.h>
 
int main()
{
  // Check if std:c++17 or higher
#if ((__cplusplus >= 201703L) || (defined(_MSVC_LANG) && (_MSVC_LANG >= 201703L)))
 
#if defined(VISP_HAVE_DISPLAY)
#ifdef ENABLE_VISP_NAMESPACE
  using namespace VISP_NAMESPACE_NAME;
#endif
  // Create base img
  vpImage<unsigned char> I(480, 640, 255);
 
  // Generate random points
  vpUniRand rand {};
  std::vector<vpImagePoint> rand_ips {};
  while (rand_ips.size() < 10) {
    rand_ips.emplace_back(rand.uniform(10, I.getHeight() - 10), rand.uniform(10, I.getWidth() - 10));
  }
 
  // Init display
  const auto disp_scale_type = vpDisplay::SCALE_AUTO;
#if (VISP_CXX_STANDARD >= VISP_CXX_STANDARD_11)
  std::shared_ptr<vpDisplay> display = vpDisplayFactory::createDisplay(I, disp_scale_type);
#else
  vpDisplay *display = vpDisplayFactory::allocateDisplay(I, disp_scale_type);
#endif
  vpDisplay::setTitle(I, "Munkres Assignment Algorithm");
  try {
    // Local helper to display a point in the image
    auto display_point = [&I](const vpImagePoint &ip, const vpColor &color) {
      I.display->displayCircle(ip, 5, color, true, 1);
      };
 
    vpDisplay::display(I);
 
    auto disp_lane { 0 };
    vpDisplay::displayText(I, 15 * ++disp_lane, 15, "Left click to add a point", vpColor::black);
    vpDisplay::displayText(I, 15 * ++disp_lane, 15, "Middle click to continue (run Munkres)", vpColor::black);
    vpDisplay::displayText(I, 15 * ++disp_lane, 15, "Right click to quit", vpColor::black);
 
    std::for_each(begin(rand_ips), end(rand_ips), std::bind(display_point, std::placeholders::_1, vpColor::red));
    vpDisplay::flush(I);
 
    // Ask user to clic on point
    std::vector<vpImagePoint> user_ips {};
    vpMouseButton::vpMouseButtonType button {};
    while (button != vpMouseButton::button2) {
      vpImagePoint ip {};
      vpDisplay::getClick(I, ip, button, true);
      if (button == vpMouseButton::button1) {
        user_ips.push_back(ip);
      }
      else if (button == vpMouseButton::button3) {
#if (VISP_CXX_STANDARD < VISP_CXX_STANDARD_11) && defined(VISP_HAVE_DISPLAY)
        if (display != nullptr) {
          delete display;
        }
#endif
        return EXIT_SUCCESS;
      }
 
      std::for_each(begin(user_ips), end(user_ips), std::bind(display_point, std::placeholders::_1, vpColor::green));
 
      vpDisplay::flush(I);
    }
 
    // Prepare Munkres (init cost matrix with random ip / user ip distances)
    std::vector<std::vector<double> > cost_matrix(rand_ips.size(), std::vector<double>(user_ips.size()));
    for (auto i = 0u; i < rand_ips.size(); i++) {
      for (auto j = 0u; j < user_ips.size(); j++) {
        cost_matrix.at(i).at(j) = vpImagePoint::distance(rand_ips.at(i), user_ips.at(j));
      }
    }
 
    // Display results
    vpDisplay::display(I);
    std::for_each(begin(rand_ips), end(rand_ips), std::bind(display_point, std::placeholders::_1, vpColor::red));
    std::for_each(begin(user_ips), end(user_ips), std::bind(display_point, std::placeholders::_1, vpColor::green));

    for (const auto &[i, j] : vpMunkres::run(cost_matrix)) {
      I.display->displayLine(rand_ips.at(i), user_ips.at(j), vpColor::blue, 1);
    }
 
    vpDisplay::displayText(I, 15, 15, "Click to quit", vpColor::black);
    vpDisplay::flush(I);
    vpDisplay::getClick(I);
 
  }
  catch (const vpException &e) {
    std::cout << "Catch an exception: " << e << std::endl;
  }
 
#if (VISP_CXX_STANDARD < VISP_CXX_STANDARD_11) && defined(VISP_HAVE_DISPLAY)
  if (display != nullptr) {
    delete display;
  }
#endif
#endif // defined(VISP_HAVE_DISPLAY)
#endif
  return EXIT_SUCCESS;
}

The tutorial starts with 10 random image points (red) which represent our tracked points:

  vpUniRand rand {};
  std::vector<vpImagePoint> rand_ips {};
  while (rand_ips.size() < 10) {
    rand_ips.emplace_back(rand.uniform(10, I.getHeight() - 10), rand.uniform(10, I.getWidth() - 10));
  }

Then, by clicking on the image, the user is able to simulate the detected points (green):

    std::vector<vpImagePoint> user_ips {};
    vpMouseButton::vpMouseButtonType button {};
    while (button != vpMouseButton::button2) {
      vpImagePoint ip {};
      vpDisplay::getClick(I, ip, button, true);
      if (button == vpMouseButton::button1) {
        user_ips.push_back(ip);
      }
      else if (button == vpMouseButton::button3) {
#if (VISP_CXX_STANDARD < VISP_CXX_STANDARD_11) && defined(VISP_HAVE_DISPLAY)
        if (display != nullptr) {
          delete display;
        }
#endif
        return EXIT_SUCCESS;
      }
 
      std::for_each(begin(user_ips), end(user_ips), std::bind(display_point, std::placeholders::_1, vpColor::green));
 
      vpDisplay::flush(I);
    }

Once the "fake" detection are selected, a cost matrix is built by defining the cost of assigning a track to a detection point as the Euclidean distance between them:

    std::vector<std::vector<double> > cost_matrix(rand_ips.size(), std::vector<double>(user_ips.size()));
    for (auto i = 0u; i < rand_ips.size(); i++) {
      for (auto j = 0u; j < user_ips.size(); j++) {
        cost_matrix.at(i).at(j) = vpImagePoint::distance(rand_ips.at(i), user_ips.at(j));
      }
    }

Finally, Munkres is ran to assign tracked points with the detected points (blue lines):

    for (const auto &[i, j] : vpMunkres::run(cost_matrix)) {
      I.display->displayLine(rand_ips.at(i), user_ips.at(j), vpColor::blue, 1);
    }