Visual Servoing Platform version 3.6.0
Loading...
Searching...
No Matches
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:

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>
// 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(HAVE_OPENCV_HIGHGUI)
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;
}
Class to define RGB colors available for display functionalities.
Definition vpColor.h:152
static const vpColor red
Definition vpColor.h:211
static const vpColor black
Definition vpColor.h:205
static const vpColor blue
Definition vpColor.h:217
static const vpColor green
Definition vpColor.h:214
Display for windows using Direct3D 3rd party. Thus to enable this class Direct3D should be installed....
Display for windows using GDI (available on any windows 32 platform).
The vpDisplayGTK allows to display image using the GTK 3rd party library. Thus to enable this class G...
The vpDisplayOpenCV allows to display image using the OpenCV library. Thus to enable this class OpenC...
Use the X11 console to display images on unix-like OS. Thus to enable this class X11 should be instal...
Definition vpDisplayX.h:132
static bool getClick(const vpImage< unsigned char > &I, bool blocking=true)
static void displayCircle(const vpImage< unsigned char > &I, const vpImageCircle &circle, const vpColor &color, bool fill=false, unsigned int thickness=1)
static void display(const vpImage< unsigned char > &I)
static void displayLine(const vpImage< unsigned char > &I, const vpImagePoint &ip1, const vpImagePoint &ip2, const vpColor &color, unsigned int thickness=1, bool segment=true)
static void setTitle(const vpImage< unsigned char > &I, const std::string &windowtitle)
static void flush(const vpImage< unsigned char > &I)
static void displayText(const vpImage< unsigned char > &I, const vpImagePoint &ip, const std::string &s, const vpColor &color)
error that can be emitted by ViSP classes.
Definition vpException.h:59
Class that defines a 2D point in an image. This class is useful for image processing and stores only ...
static double distance(const vpImagePoint &iP1, const vpImagePoint &iP2)
Definition of the vpImage class member functions.
Definition vpImage.h:135
unsigned int getWidth() const
Definition vpImage.h:242
unsigned int getHeight() const
Definition vpImage.h:184
vpDisplay * display
Definition vpImage.h:140
static std::vector< std::pair< unsigned int, unsigned int > > run(std::vector< std::vector< Type > > costs)
Definition vpMunkres.h:315
Class for generating random numbers with uniform probability density.
Definition vpUniRand.h:122

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{};
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):

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