Hungarian Algorithm

헝가리안 알고리즘은 두 집합 중 크기가 작은 집합의 모든 항목을 짝짓는 최소 비용 일대일 매칭을 찾는 정확한 최적화 방법입니다. 선택된 모든 쌍의 총비용을 최소화합니다. 컴퓨터 비전에서는 탐지 결과와 추적 중인 객체를 연결하거나 예측 결과와 학습 타깃을 연결합니다.

Harold W. Kuhn은 1955년에 할당 문제를 위한 헝가리안 방법에서 이 방법을 소개했습니다. 헝가리안 방법과 Kuhn–Munkres 알고리즘은 같은 알고리즘 계열을 가리키는 다른 이름입니다. 이 알고리즘의 이름은 방법의 기반이 된 연구를 수행한 헝가리 수학자 Dénes Kőnig와 Jenő Egerváry를 기립니다.

헝가리안 알고리즘의 작동 방식#

입력은 비용 행렬입니다. 각 행은 한 집합의 항목을, 각 열은 다른 집합의 항목을 나타내며, 각 원소는 두 항목을 짝지을 때의 비용을 나타냅니다. 정방 행렬에서는 해가 각 행과 열에서 정확히 하나의 원소를 선택합니다. 탐욕적 전략은 개별적으로 매력적인 쌍을 선택해 확정하지만, 헝가리안 매칭은 전체 비용이 최소가 되도록 합니다.

고전적인 행렬 축소 절차에서는 각 행의 최솟값을 해당 행에서 뺀 다음, 각 열의 최솟값을 해당 열에서 뺍니다. 모든 할당은 각 행과 열을 한 번씩 사용하므로 이러한 축소는 최적의 완전 할당을 보존합니다. 가능한 한 적은 수의 수평선과 수직선으로 모든 0을 덮습니다. n x n 행렬에서 n개의 선이 필요하면, 행이나 열을 공유하지 않는 n개의 0을 선택합니다. 그렇지 않으면 덮이지 않은 원소 중 최솟값을 덮이지 않은 원소에서 빼고, 덮는 선들이 교차하는 위치에는 더한 다음, 덮기 검사를 반복합니다. 원래 행렬을 사용해 할당 비용을 계산합니다.

효율적인 헝가리안 알고리즘 구현은 정방 행렬에서 O(n³) 시간에 실행되며, 이는 가능한 완전 할당 n!개를 모두 고려하는 것과 비교됩니다.

컴퓨터 비전 분야의 활용#

다중 객체 추적. SORT의 원래 설계는 헝가리안 할당과 각 트랙의 위치를 예측하는 칼만 필터를 결합합니다. 교집합 대 합집합 비율은 예측된 바운딩 박스와 검출된 바운딩 박스 간의 중첩 정도를 측정합니다. SORT의 참조 구현은 LAPJV 또는 SciPy를 사용해 할당 문제를 해결하고, 중첩도가 낮은 연결을 제외하며, 매칭되지 않은 검출 항목에 ID를 생성합니다.

객체 탐지 학습. DETR은 헝가리안 매칭을 사용해 순서가 정해지지 않은 예측 결과를 레이블이 지정된 객체와 짝짓습니다. Transformer는 예측 슬롯을 생성하며, 매칭은 분류 비용과 박스 위치 비용을 결합합니다. 슬롯이 충분하면 각 타깃에 예측 결과 하나가 할당되므로 손실 함수는 어노테이션 순서에 영향을 받지 않습니다. 매칭되지 않은 슬롯은 "객체 없음" 클래스를 학습합니다. Ultralytics는 RT-DETR에서 이 할당 방식을 적용합니다. HungarianMatcher는 분류 비용, L1 좌표 거리, 일반화된 IoU 비용을 결합합니다. 선형 할당 백엔드는 수정된 Jonker–Volgenant 솔버를 사용해 학습 쌍을 선택합니다.

Python에서의 헝가리안 매칭#

munkres Python 패키지는 헝가리안 방법을 구현합니다. 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 전환이 발생하여 트랙 ID가 다른 객체로 넘어갑니다.

SciPy의 선형 할당 솔버는 수정된 Jonker–Volgenant 알고리즘을 사용해 동일한 최적화 문제를 풉니다. r x c 직사각형 행렬의 경우, 실행 가능한 완전 할당이 존재하면 정확히 min(r, c)개의 쌍을 반환합니다.