헝가리안 알고리즘(Hungarian Algorithm)이란? AI에서 전체 비용을 줄이며 대상을 짝짓는 방법

TL;DR

헝가리안 알고리즘은 두 집합의 대상을 일대일로 연결할 때 전체 비용이 가장 작은 조합을 찾는 방법입니다. 각 대상이 따로 가장 가까운 상대를 고르면 같은 상대를 중복 선택할 수 있어 전체 배정을 함께 결정합니다. 영상 AI의 탐지와 추적 연결에 쓰이며 비용 설계·연결 금지·미배정 규칙에 따라 실제 결과가 달라집니다.

핵심 3줄 요약

• 핵심 1
  전체 조합을 기준으로 고릅니다. 각 행의 최솟값만 고르지 않고 같은 열을 중복 사용하지 않는 배정을 찾습니다.
• 핵심 2
  비용과 연결 규칙이 먼저입니다. 알고리즘은 주어진 숫자를 최적화하므로 잘못 만든 비용을 스스로 바로잡지 않습니다.
• 핵심 3
  배정과 추적은 역할이 다릅니다. 짝을 정한 뒤 위치 보정·새 ID 생성·추적 종료는 별도 단계에서 처리합니다.

이 글에서 다룰 내용

헝가리안 알고리즘을 한 문장으로 정의하면 무엇인가요?

헝가리안 알고리즘은 두 집합 사이의 일대일 배정 제약을 지키면서 선택한 쌍의 비용 합을 최소화하는 선형 할당 문제의 해법입니다.

영문으로 Hungarian Algorithm 또는 Hungarian Method라고 부르며 쿤-멍크레스 알고리즘이라는 이름도 쓰입니다. 헝가리어를 처리하는 언어 모델은 아닙니다. 어떤 작업을 누구에게 맡길지, 어떤 관측을 어느 기존 대상에 붙일지처럼 서로 겹치지 않는 짝을 정하는 계산입니다.

양쪽의 대상 수가 같은 기본 문제에서는 각 행과 각 열에서 하나씩 선택합니다. 비용 행렬의 한 칸은 그 행의 대상과 그 열의 대상을 연결할 때 드는 비용입니다. 여기서 선형은 선택한 칸들의 비용을 더한다는 의미이며 입력값으로 직선을 학습하는 선형 회귀와는 다릅니다.

한 줄 정리: 헝가리안 알고리즘은 개별적으로 좋아 보이는 짝보다 전체 배정의 비용과 일대일 제약을 함께 봅니다.

쉬운 예시로 이해해 볼까요?

감자나라ai님이 이전 프레임의 대상 A·B를 새 탐지 X·Y에 연결한다고 가정해 보겠습니다. 비용은 작을수록 더 어울리는 쌍입니다. 아래 숫자는 원리 설명용 가정이며 실제 영상에서 측정한 거리나 권장 임계값이 아닙니다.

• A를 X에 연결하는 비용은 1, Y에 연결하는 비용은 2입니다.
• B를 X에 연결하는 비용은 2, Y에 연결하는 비용은 100입니다.
• A부터 가장 싼 X를 차지하면 B에는 Y만 남아 전체 비용은 101입니다.
• A를 Y에, B를 X에 연결하면 전체 비용은 4입니다.

A만 보면 X가 더 싸지만 두 대상을 함께 배정하면 A가 Y를 선택하는 쪽이 유리합니다. 두 행에서 각각 가장 작은 값을 독립적으로 고르면 둘 다 X를 선택해 일대일 조건을 어깁니다. 이런 경쟁을 전체 조합 안에서 해결하는 것이 할당 알고리즘의 역할입니다.

이 예시는 가능한 일대일 조합을 모두 계산해 합계가 맞는지 확인할 수 있습니다. 대상이 많아지면 모든 조합을 직접 나열하는 대신 헝가리안 알고리즘처럼 문제의 구조를 이용하는 해법을 씁니다. 반환된 짝이 현실에서도 같은 물체인지는 정답 영상으로 따로 확인합니다.

쉬운 예시: 한 사람에게 가장 좋은 자리를 먼저 주는 것과 모두의 자리 배정을 합리적으로 정하는 것은 다른 문제입니다.

왜 AI에서 헝가리안 알고리즘이 중요한가요?

같은 관측을 중복해서 가져가는 일을 막습니다

여러 추적 대상이 가까이 있으면 같은 탐지 상자를 서로 가장 좋은 후보로 고를 수 있습니다. 일대일 배정은 한 탐지를 여러 대상에 동시에 붙이지 않도록 제한합니다. 다만 실제 장면에서 한 상자에 여러 물체가 뭉쳐 보이는 경우까지 이 제약만으로 해결하지는 못합니다.

학습 점수와 최종 연결을 구분합니다

신경망이 계산한 외형 유사도나 운동 모델이 계산한 위치 차이는 쌍별 단서입니다. 이 점수로 비용 행렬을 만든 뒤 전체 연결을 선택하는 단계는 별도로 필요할 수 있습니다. 특징 추출을 잘하는 모델과 배정 문제를 푸는 알고리즘은 서로 다른 역할을 맡습니다.

전체 비용의 의미를 명확히 합니다

SORT 원 논문은 칼만 필터로 움직임을 예측하고 헝가리안 방법으로 관측을 연결하는 구성을 설명합니다. 이때 최적이라는 말은 주어진 프레임의 비용 행렬과 배정 조건 안에서의 최적입니다. 앞으로의 모든 프레임까지 가장 정확한 경로를 보장한다는 뜻은 아닙니다.

헝가리안 알고리즘은 어떤 순서로 작동하나요?

1. 두 집합과 비용 행렬을 준비합니다

행에는 기존 대상, 열에는 새 관측처럼 각 축의 의미를 고정합니다. 위치 거리나 외형 차이를 이용해 모든 후보 쌍의 비용을 계산합니다. 같은 값이라도 거리가 작을수록 좋은지, 유사도가 클수록 좋은지에 따라 최적화 방향이 달라지므로 입력부터 구분합니다.

2. 비용의 하한과 후보 연결을 관리합니다

헝가리안 방법은 행과 열에 보조 값을 두고 최적 비용의 하한을 관리하는 방식으로 설명할 수 있습니다. 보조 값의 합이 해당 칸의 비용과 같은 연결을 후보로 삼습니다. 이런 보조 값을 잠재값이라고 부르며 AI의 학습된 가중치나 연결 확률과는 다릅니다.

3. 기존 짝을 바꾸며 배정을 늘립니다

아직 짝이 없는 대상에서 출발해 기존 연결과 새 연결을 번갈아 바꾸는 경로를 찾습니다. 경로를 따라 짝을 재배치하면 앞서 고른 연결을 일부 바꾸면서 배정 수를 늘릴 수 있습니다. 한 번 고른 가장 싼 짝을 끝까지 고정하는 탐욕적 선택과 다른 부분입니다.

더 연결할 경로가 없으면 조건을 유지하는 범위에서 잠재값을 조정해 새 후보 연결을 만듭니다. 이 과정을 반복하며 전체 배정을 완성합니다. 정사각형 기본 문제에서는 선택한 총비용이 관리하던 하한에 도달하면 최적 배정을 얻었다고 판단할 수 있습니다.

4. 원래 비용과 대상 식별자로 결과를 읽습니다

출력 인덱스를 원래 행·열의 대상에 다시 연결하고 원본 비용을 합산합니다. 중간에 조정한 값만 합쳐 실제 비용이라고 보고하지 않습니다. 구현마다 내부 절차와 반환 형식이 다를 수 있으므로 알고리즘 이름만 보고 배열의 의미를 추측하지 않는 편이 안전합니다.

핵심 인사이트: 최적화가 보장하는 것은 입력한 비용과 제약에 맞는 해입니다. 비용이 실제 동일성을 잘 나타내는지는 별도의 검증 문제입니다.

비용 행렬과 주요 설정은 무엇을 뜻하나요?

거리 최소화와 유사도 최대화를 구분합니다

SciPy의 linear_sum_assignment 는 기본적으로 비용을 최소화하며 maximize=True 를 지정하면 가중치 합을 최대화합니다. IoU처럼 클수록 더 많이 겹치는 값은 최소화 비용과 방향이 반대입니다. 부호를 바꾸거나 최대화 옵션을 쓰는 등 선택한 구현에 맞게 처리합니다.

직사각형 행렬과 자유로운 미배정은 다릅니다

양쪽 수가 달라도 직사각형 할당을 지원하는 구현을 쓸 수 있습니다. 일반적인 완전 배정에서는 작은 쪽의 대상 수만큼 짝을 만들고 큰 쪽의 일부가 남습니다. 두 집합 모두에서 나쁜 연결을 자유롭게 포기하는 기능이 저절로 생기는 것은 아닙니다.

쓸 만한 상대가 없을 때 연결하지 않으려면 미배정을 나타내는 가상 대상과 비용, 허용 가능한 연결 조건 등 문제 설계가 더 필요합니다. 미배정 비용이 너무 싸면 연결을 쉽게 포기하고 너무 비싸면 어색한 짝을 강요할 수 있으므로 실제 사례로 비교합니다.

함수 이름과 내부 알고리즘을 구분합니다

현재 SciPy 공식 문서는 linear_sum_assignment 의 내부 구현을 수정된 Jonker-Volgenant 알고리즘이라고 설명합니다. 선형 할당 문제를 푼다는 이유만으로 그 함수가 고전적인 헝가리안 절차를 그대로 실행한다고 쓰면 부정확합니다. 해결하는 문제와 해법의 이름을 나눠 읽습니다.

헝가리안 알고리즘과 헷갈리는 용어는 무엇이 다른가요?

객체 추적과의 차이

객체 추적은 탐지·움직임 예측·관측 연결·ID 관리가 이어지는 전체 작업입니다. 헝가리안 알고리즘은 그중 연결을 정하는 데 쓸 수 있는 도구입니다. 객체 추적 용어 설명은 영상에서 ID와 경로를 유지하는 전체 흐름을 다룹니다.

칼만 필터와의 차이

칼만 필터는 상태를 예측하고 연결된 관측으로 보정합니다. 할당 알고리즘은 어느 관측을 어느 상태에 넘길지 결정합니다. 위치 예측이 정확해도 관측 연결이 잘못되면 다른 물체의 값으로 보정할 수 있습니다. 두 방법은 대체 관계보다 함께 사용하는 구성 요소에 가깝습니다.

비최대 억제와의 차이

NMS는 한 프레임의 겹치는 탐지 후보를 점수 순서로 정리합니다. 일대일 할당은 두 집합 사이에서 서로 충돌하지 않는 짝을 고릅니다. 두 방법 모두 IoU를 참고할 수 있지만 입력 집합의 의미와 출력이 달라 같은 후처리로 취급하지 않습니다.

최근접 선택과 일반 그래프 매칭의 차이

각 대상의 최근접 후보만 고르면 같은 상대를 중복 선택할 수 있습니다. 헝가리안 방법은 두 집합을 잇는 비용 합과 일대일 조건을 함께 봅니다. 여러 일을 한 대상에게 맡기거나 쌍 사이의 상호작용 비용까지 고려하는 문제는 기본 선형 할당과 조건이 다릅니다.

실전에서는 어디에 쓰이나요?

영상의 기존 궤적과 새 탐지를 연결합니다

SORT는 예측 상자와 새 탐지 상자의 겹침을 관측 연결에 사용합니다. 공개 구현에는 IoU 기반 배정 뒤 낮은 IoU의 쌍을 제외하는 처리와 미연결 탐지·추적 대상을 따로 반환하는 코드가 있습니다. 배정 함수의 결과를 그대로 모든 대상의 확정 ID로 쓰지 않는 이유를 보여 줍니다.

외형 단서를 포함한 연결을 구성합니다

Deep SORT 원 논문은 움직임과 외형 정보를 함께 다루고 최근 관측된 추적 대상을 우선하는 단계별 매칭을 설명합니다. 외형 단서를 넣었다고 전체 시스템이 단일 비용 행렬을 한 번 푸는 것과 같아지지는 않습니다. 연결 순서와 허용 조건까지 살펴야 실제 동작을 이해할 수 있습니다.

실전 팁: 비용을 만든 모델, 배정 해법, 연결을 거절하는 기준, ID 수명 규칙을 각각 기록하면 오류가 어느 단계에서 생겼는지 찾기 쉽습니다.

헝가리안 알고리즘을 적용할 때 어떤 순서로 확인하나요?

1. 축의 의미와 비용 방향을 고정합니다

행·열의 ID 목록과 단위, 거리 또는 유사도의 정의를 함께 저장합니다. 위치 비용과 외형 비용을 더한다면 값의 척도와 가중치도 확인합니다. 한 항목의 숫자가 크다는 이유로 다른 단서가 사실상 무시되지 않는지 검증 자료에서 비교합니다.

2. 작은 행렬과 미연결 사례를 시험합니다

앞의 예시처럼 탐욕적 선택이 틀리는 행렬부터 확인합니다. 양쪽 수가 다른 경우, 한쪽이 비어 있는 경우, 모든 후보가 나쁜 경우도 시험합니다. 반환한 행·열 인덱스가 중복되지 않는지와 입력 ID에 올바르게 돌아가는지를 함께 점검합니다.

3. 비용과 실제 연결 오류를 따로 평가합니다

선택한 쌍의 총비용, 거절된 쌍, 미연결 대상과 ID 전환을 남깁니다. 비용 합이 줄었더라도 실제 오연결이 늘면 비용 설계가 목적과 어긋난 것입니다. 같은 비용 행렬에서는 해법을, 같은 영상에서는 전체 연결 품질을 비교해야 원인을 구분하기 쉽습니다.

사용할 때 무엇을 주의해야 하나요?

금지할 연결을 단순히 큰 숫자로만 표시하지 않습니다. 큰 비용도 허용된 후보로 남아 있으면 다른 선택지가 없을 때 배정될 수 있습니다. 미배정 가능성, 금지 쌍의 처리 방식, 해가 없는 경우의 동작을 구현별로 확인합니다. 없는 관측을 비용 0으로 채우는 것도 의미를 바꿀 수 있습니다.

배정 뒤 거절한 결과의 최적성을 과장하지 않습니다. 완전 배정을 먼저 구한 뒤 나쁜 쌍을 삭제하는 처리와 처음부터 미배정·금지 조건을 포함해 푸는 문제는 다를 수 있습니다. SORT의 거절 처리를 모든 제약 문제의 최적 해법으로 일반화하지 않습니다.

동점과 가림 구간을 따로 봅니다. 같은 총비용의 최적 배정이 여러 개면 최적 비용만으로 특정 ID 연결을 유일하게 정할 수 없습니다. 입력 순서와 동점 처리 규칙을 기록하고 비슷한 외형의 대상이 교차하거나 오래 가려지는 장면을 평가에 포함합니다.

비용을 확률이나 신원으로 읽지 않습니다. 작은 비용은 정한 기준에서 좋은 쌍이라는 뜻입니다. 같은 사람일 확률이나 실제 신원을 보장하지 않습니다. 사람의 이동 경로를 다룬다면 수집 목적·접근권한·보관 범위를 정하고 중요한 판단은 원본과 다른 근거를 함께 검토합니다.

주의: 정확한 최적화 결과와 정확한 현실 인식은 다릅니다. 탐지 누락·잘못된 특징·부적절한 제약은 배정 알고리즘만 바꿔도 그대로 남을 수 있습니다.

자주 묻는 질문

Q1. 헝가리안 알고리즘은 딥러닝인가요?

아닙니다. 주어진 비용 행렬에서 배정을 찾는 최적화 알고리즘입니다. 신경망이 만든 특징이나 점수를 입력으로 활용할 수 있지만 알고리즘 자체를 반드시 데이터로 학습하는 것은 아닙니다.

Q2. 각 행에서 최솟값을 고르면 같은 결과 아닌가요?

그렇게 고르면 여러 행이 같은 열을 선택할 수 있습니다. 중복을 피하려고 앞선 선택을 고정하는 방식도 전체 비용을 최소화하지 못할 수 있습니다. 일대일 조건을 포함해 조합 전체를 결정합니다.

Q3. 양쪽 대상 수가 같아야 하나요?

기본 설명은 정사각형 행렬을 쓰지만 직사각형 문제를 지원하는 구현도 있습니다. SciPy는 직사각형 비용 행렬을 받습니다. 이 기능과 나쁜 연결을 자유롭게 포기하는 미배정 정책은 구분합니다.

Q4. SciPy 함수를 부르면 헝가리안 알고리즘이 실행되나요?

현재 공식 문서는 수정된 Jonker-Volgenant 구현이라고 명시합니다. 같은 선형 할당 문제를 해결해도 내부 알고리즘은 다를 수 있습니다. 재현 실험에서는 함수와 라이브러리 버전을 함께 남깁니다.

Q5. 최적 배정이면 추적 ID가 절대 바뀌지 않나요?

아닙니다. 해당 비용 행렬에서 합계가 최적이어도 실제 연결은 틀릴 수 있습니다. 탐지 품질, 운동 예측, 외형 단서, 미배정과 ID 관리 정책을 함께 평가해야 합니다.

출처

마무리

헝가리안 알고리즘은 두 집합의 대상을 중복 없이 연결하면서 전체 비용을 줄이는 배정 방법입니다. 각 대상의 가장 가까운 상대만 고르는 방식과 달리 다른 대상의 선택까지 고려합니다. 영상 AI에서는 탐지와 기존 궤적을 연결하는 과정에 이 원리를 활용합니다.

처음에는 비용 행렬의 행·열이 무엇인지, 작은 값과 큰 값 중 어느 쪽이 좋은지, 연결하지 않을 선택이 있는지부터 확인하세요. 그다음 반환 인덱스와 실제 ID를 대조하면 최적화의 성공과 추적 품질을 구분해서 읽을 수 있습니다.