Hungarian Algorithm

Венгерский алгоритм — это точный метод оптимизации, который находит взаимно-однозначное сопоставление с наименьшей стоимостью, связывающее каждый элемент меньшего из двух множеств с элементом другого множества. Он минимизирует суммарную стоимость всех выбранных пар. В компьютерном зрении он связывает обнаруженные объекты с отслеживаемыми объектами или прогнозы с целевыми значениями для обучения.

Гарольд У. Кун представил этот алгоритм в 1955 году в работе «Венгерский метод решения задачи о назначениях». «Венгерский метод» и «алгоритм Куна — Мункреса» — альтернативные названия одного и того же семейства алгоритмов. Название дано в честь венгерских математиков Денеша Кёнига и Йено Эгервари, чьи работы легли в основу метода.

Как работает венгерский алгоритм#

На вход подаётся матрица стоимости: каждая строка представляет элемент одного множества, каждый столбец — элемент другого, а каждое значение показывает стоимость их сопоставления. Для квадратной матрицы решение выбирает ровно по одному элементу в каждой строке и каждом столбце. Жадный алгоритм выбирает привлекательные отдельные пары, а венгерский алгоритм находит глобальный минимум суммарной стоимости.

В классической процедуре редукции матрицы вычти минимальное значение каждой строки из всех её значений, а затем вычти минимальное значение каждого столбца из всех его значений. Эти преобразования сохраняют оптимальное полное назначение, поскольку каждое назначение использует каждую строку и каждый столбец ровно один раз. Накрой все нули минимальным числом горизонтальных и вертикальных линий. Если для матрицы n x n нужны n линий, выбери n нулей так, чтобы ни у каких двух не было общей строки или столбца. В противном случае вычти наименьшее непокрытое значение из непокрытых элементов, прибавь его в точках пересечения покрывающих линий и повтори проверку покрытия. Вычисли стоимость назначения по исходной матрице.

Эффективные реализации венгерского алгоритма выполняются за время O(n³) для квадратных матриц, тогда как число возможных полных назначений составляет n!.

Применение в компьютерном зрении#

Отслеживание нескольких объектов. Исходная архитектура SORT сочетает венгерский алгоритм назначения с фильтром Калмана, который предсказывает положение каждой траектории. Пересечение по объединению измеряет степень перекрытия между предсказанными и обнаруженными ограничивающими рамками. Эталонная реализация SORT выполняет сопоставление с помощью LAPJV или SciPy, отклоняет ассоциации с низким перекрытием и присваивает идентификаторы обнаруженным объектам, для которых не нашлось пары.

Обучение детектора объектов. DETR использует венгерское сопоставление, чтобы связать неупорядоченные прогнозы с размеченными объектами. Его трансформер формирует слоты для прогнозов, а сопоставление учитывает стоимость классификации и расположения рамок. Если слотов достаточно, каждому целевому объекту соответствует один прогноз, поэтому функция потерь не зависит от порядка аннотаций; несопоставленные слоты обучаются распознавать класс «нет объекта». Ultralytics применяет эту схему назначения в RT-DETR: его HungarianMatcher объединяет стоимость классификации, расстояние между координатами по L1 и стоимость обобщённого IoU. Его модуль линейного назначения использует модифицированный алгоритм Йонкера — Фольгенанта для выбора пар при обучении.

Венгерское сопоставление в Python#

Пакет Python munkres реализует венгерский метод. Установи его с помощью pip install munkres, затем реши приведённую в примере задачу с матрицей стоимости:

from munkres import Munkres

costs = [
    [5, 9, 1],
    [10, 3, 2],
    [8, 7, 4],
]
solver = Munkres()
assignments = solver.compute(costs)
# Read costs from the original matrix.
minimum_cost = sum(costs[row][col] for row, col in assignments)
print(f"Minimum total cost: {minimum_cost}")

Результат — Minimum total cost: 12, наименьшая возможная сумма при выборе ровно одного элемента в каждой строке и каждом столбце.

Связанные методы и несопоставленные объекты#

Задача о назначениях — это задача, а венгерский алгоритм — один из методов её решения. Подавление немаксимумов удаляет конкурирующие обнаружения в пределах одного изображения. Повторная идентификация объектов предоставляет информацию о внешнем виде для ассоциации, часто с помощью эмбеддингов, сравниваемых по косинусному сходству. Такие оценки можно использовать как стоимость сопоставления.

Если размеры групп не совпадают, получаются прямоугольные матрицы. Для отслеживания также нужны правила отклонения или фиктивные элементы с заданной стоимостью несопоставления, чтобы учитывать пропущенные обнаружения и вновь появившиеся объекты. Неправильная ассоциация приводит к переключению идентификатора: ID траектории переходит к другому объекту.

Решатель линейного назначения из SciPy решает ту же задачу оптимизации с помощью модифицированного алгоритма Йонкера — Фольгенанта. Для прямоугольной матрицы r x c он возвращает ровно min(r, c) пар, если существует допустимое полное назначение.