Visual Servoing Platform  version 3.5.1 under development (2022-05-22)
Tutorial: Munkres Assignment Algorithm

Table of Contents

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:

img-munkres-assignment.png
Note
It can also work with less (or more) detection than tracked points:
img-munkres-assignment1.png
img-munkres-assignment2.png
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:
img-munkres-total-cost.png

Assignment

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

// Display
#include <visp3/gui/vpDisplayD3D.h>
#include <visp3/gui/vpDisplayGDI.h>
#include <visp3/gui/vpDisplayGTK.h>
#include <visp3/gui/vpDisplayOpenCV.h>
#include <visp3/gui/vpDisplayX.h>
#include <visp3/core/vpColor.h>
// Munkres
#include <visp3/core/vpMunkres.h>
// Math
#include <visp3/core/vpUniRand.h>
int main()
{
#if (VISP_CXX_STANDARD >= VISP_CXX_STANDARD_17) && \
(!defined(_MSC_VER) || ((VISP_CXX_STANDARD >= VISP_CXX_STANDARD_17) && (_MSC_VER >= 1911)))
#if defined(VISP_HAVE_DISPLAY)
// 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));
}
try {
// Init display
const auto disp_scale_type = vpDisplay::SCALE_AUTO;
#if defined(VISP_HAVE_X11)
vpDisplayX d(I, disp_scale_type);
#elif defined(VISP_HAVE_GDI)
vpDisplayGDI d(I, disp_scale_type);
#elif defined(VISP_HAVE_OPENCV)
vpDisplayOpenCV d(I, disp_scale_type);
#elif defined(VISP_HAVE_GTK)
vpDisplayGTK d(I, disp_scale_type);
#elif defined(VISP_HAVE_D3D9)
vpDisplayD3D d(I, disp_scale_type);
#else
std::cout << "No image viewer is available..." << std::endl;
#endif
vpDisplay::setTitle(I, "Munkres Assignment Algorithm");
// 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);
};
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));
// Ask user to clic on point
std::vector<vpImagePoint> user_ips{};
while (button != vpMouseButton::button2) {
vpDisplay::getClick(I, ip, button, true);
if (button == vpMouseButton::button1) {
user_ips.push_back(ip);
} else if (button == vpMouseButton::button3) {
return EXIT_SUCCESS;
}
std::for_each(begin(user_ips), end(user_ips), std::bind(display_point, std::placeholders::_1, vpColor::green));
}
// 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
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);
} catch (const vpException &e) {
std::cout << "Catch an exception: " << e << std::endl;
}
#endif // defined(VISP_HAVE_DISPLAY)
#endif
return EXIT_SUCCESS;
}

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

img-munkres-tracked.png
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):

img-munkres-detected.png
std::vector<vpImagePoint> user_ips{};
while (button != vpMouseButton::button2) {
vpDisplay::getClick(I, ip, button, true);
if (button == vpMouseButton::button1) {
user_ips.push_back(ip);
} else if (button == vpMouseButton::button3) {
return EXIT_SUCCESS;
}
std::for_each(begin(user_ips), end(user_ips), std::bind(display_point, std::placeholders::_1, vpColor::green));
}

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):

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