Hungarian Algorithm

Overview

The Hungarian algorithm is a combinatorial optimization algorithm that solves the linear assignment problem in polynomial time. It computes a globally optimal one-to-one assignment between rows and columns of a cost matrix such that the total cost is minimized.

In UFIL, the Hungarian algorithm is used to associate tracks and measurements based on a previously computed cost matrix.

The algorithm guarantees:

  • Globally optimal solution

  • Deterministic behavior

  • One-to-one assignments

Problem Formulation

Given a cost matrix \(C \in \mathbb{R}^{n \times m}\), the goal is to find an assignment matrix \(A\) that minimizes:

\[\sum_{i,j} C_{ij} A_{ij}\]

subject to:

  • Each row is assigned at most once

  • Each column is assigned at most once

  • \(A_{ij} \in \{0,1\}\)

Characteristics

  • Optimal solution

  • Time complexity: \(\mathcal{O}(n^3)\)

  • Suitable for moderate-sized problems

  • Widely used in tracking systems

Selection Note

The Hungarian algorithm is recommended when a guaranteed optimal assignment is required and computation time is acceptable.

Code Documentation

The interface to the Hungarian algorithm is implemented in association_functions.hpp and the underlying implementation in hungarian_algorithm.hpp.

Function Definition

namespace ufil
{
namespace association
{

inline void hungarian(
  const type::CostMatrix & cost_matrix, type::AssignmentMatrix & assignment_matrix)
{
  const auto n_rows = cost_matrix.rows();
  const auto n_cols = cost_matrix.cols();

  // Resize and initialize assignment matrix
  assignment_matrix.resize(n_rows, n_cols);
  assignment_matrix.setZero();

  // No assignment if matrix is empty
  if (!(n_rows > 0 && n_cols > 0)) {
      return;
  }

  // Create and solve assignment problem with hungarian algorithm
  auto problem = HungarianAlgorithm<ufil::type::Scalar>(cost_matrix);
  problem.SolveAssignmentProblem();

  // Set assignment matrix with solution
  problem.GetAssignmentMatrix(assignment_matrix);
}

}  // namespace association
}  // namespace ufil

Example Usage

#include <iostream>
#include <ufil_object_tracking/ufil_object_tracking.hpp>

// Get cost matrix and prepare assignment matrix buffer

ufil::type::AssignmentMatrix assignment_matrix;
ufil::association::hungarian(cost_matrix, assignment_matrix);
std::cout << "Assignment Matrix:" << assignment_matrix << std::endl;

Parameters

  • cost_matrix: The cost matrix to be used for hungarian assignment.

  • assignment_matrix: The output assignment matrix.

References

  1. Burkard, M. Dell’Amico, S. and Martello, “Assignment Problems: Revised”, Society for Industrial and Applied Mathematics (SIAM), 2012

Reference Implementation: M. Emam, https://github.com/mxemam/hungarianAlgorithm, 2020