Contents
1. Hungarian matching algorithm 정의
2. Hungarian algorithm설명
3. 코드
1. Hungarian matching algorithm
- 이분 그래프상에서 최대 가중치 매칭을 찾는 알고리즘이다.
- 할당 문제
- $O(|V|^3)$
알고리즘 적용 상황 예시)
Musician, Chef, Cleaners를 고용하려고 하고, 하나의 회사에서 하나의 서비스만 제공할 수 있다.
(CompanyA, B, C는 Musician, Chef, Cleaners를 파견하는 서비스 제공회사이다)
사용자는 금액을 최소화 하면서 서비스를 이용 하고 싶다.
위의 상황은 이분 그래프로 표현이 가능하다. 하나의 회사가 하나의 서비스만을 제공할 수 있기 때문이다.
2.Hungarian algorithm 설명
1) 행의 다른 모든 항목에서 가장 작은 항목을 뺀다(행의 최소 값은 0이 된다)
2) 열의 다른 모든 항목에서 가장 작은 항목을 뺀다(열의 최소 값은 0이 된다)
3) 항목이 0인 곳의 행과 열을 최소한으로 표시한다.
4) 만약 n개의 선이 그려지면, 최적의 0 할당이 가능하고 알고리즘 완료(n = 3, 이분 그래프 한쪽 Vertex수)
행 수가 n 보다 작으면, 최적의 0에 도달하지 않았으므로 (5)로 이동
5) 어떤 줄에도 포함되지 않는 가장 작은 항목을 찾는다. 줄이 표시되지 않은 각 행에서 이 항목을 뺀다음, 줄이 표시된 각 열에 추가한다. (3)단계로 돌아간다
>>> 상세
(5) 과정에서 어떤 줄에도 포함되지 않은(흰색 바탕) 가장 작은 항목은 2이다
항목이 0이 있는 열 혹은 행을 추가한다. (현재 상황에선 1행 혹은 3열을 그으면 된다)
(최소한의 선이 그어져야 하므로 하나만 긋는다)
※ 최대 이분 매칭(Maximum Bipartite Matching) 알고리즘과의 차이
- 최대 이분 매칭 알고리즘은 Bipartite 노드끼리 최대한 많은 수의 매칭이 이뤄지게 하는 것이 목표이며
e.g. (선호도를 조사한 후에) 최대한 많은 커플의 탄생, 최대한 많은 구직자와 회사 매칭
- Hungarian 매칭은 가중치가 존재하여 최소한의 가중치로 매칭이 이뤄지게 하는 것이 목표이다
e.g. 사업 부문별 발주를 내고, 최소한의 금액으로 수주할 회사를 모집
3. 코드
- 단순 Brute Force로 최적의 매칭 경우를 찾으려면 O(n!)이 걸린다.
- Munkres Algorithm은 $O(n^3)$ 복잡도를 가진다.
구현 - 라이브러리)
from munkres import Munkres
matrix = [[5, 9, 1],
[10, 3, 2],
[8, 7, 4]]
m = Munkres()
indexes = m.compute(matrix) # compute 메소드
total = 0
for row, column in indexes:
value = matrix[row][column]
total += value
print(f'({row}, {column}) -> {value}')
print(f'total cost: {total}')'
'''
(0, `) -> 5
(1, 1) -> 3
(2, 2) -> 4
total cost=12
'''
Computer Vision에서의 활용)
class HungarianMatcher(nn.Module):
"""This class computes an assignment between the targets and the predictions of the network
For efficiency reasons, the targets don't include the no_object. Because of this, in general,
there are more predictions than targets. In this case, we do a 1-to-1 matching of the best predictions,
while the others are un-matched (and thus treated as non-objects).
"""
def __init__(self, cost_class: float = 1, cost_bbox: float = 1, cost_giou: float = 1):
"""Creates the matcher
Params:
cost_class: This is the relative weight of the classification error in the matching cost
cost_bbox: This is the relative weight of the L1 error of the bounding box coordinates in the matching cost
cost_giou: This is the relative weight of the giou loss of the bounding box in the matching cost
"""
super().__init__()
self.cost_class = cost_class
self.cost_bbox = cost_bbox
self.cost_giou = cost_giou
assert cost_class != 0 or cost_bbox != 0 or cost_giou != 0, "all costs cant be 0"
@torch.no_grad()
def forward(self, outputs, targets):
""" Performs the matching
Params:
outputs: This is a dict that contains at least these entries:
"pred_logits": Tensor of dim [batch_size, num_queries, num_classes] with the classification logits
"pred_boxes": Tensor of dim [batch_size, num_queries, 4] with the predicted box coordinates
targets: This is a list of targets (len(targets) = batch_size), where each target is a dict containing:
"labels": Tensor of dim [num_target_boxes] (where num_target_boxes is the number of ground-truth
objects in the target) containing the class labels
"boxes": Tensor of dim [num_target_boxes, 4] containing the target box coordinates
Returns:
A list of size batch_size, containing tuples of (index_i, index_j) where:
- index_i is the indices of the selected predictions (in order)
- index_j is the indices of the corresponding selected targets (in order)
For each batch element, it holds:
len(index_i) = len(index_j) = min(num_queries, num_target_boxes)
"""
bs, num_queries = outputs["pred_logits"].shape[:2]
# We flatten to compute the cost matrices in a batch
out_prob = outputs["pred_logits"].flatten(0, 1).softmax(-1) # [batch_size * num_queries, num_classes]
out_bbox = outputs["pred_boxes"].flatten(0, 1) # [batch_size * num_queries, 4]
# Also concat the target labels and boxes
tgt_ids = torch.cat([v["labels"] for v in targets])
tgt_bbox = torch.cat([v["boxes"] for v in targets])
# Compute the classification cost. Contrary to the loss, we don't use the NLL,
# but approximate it in 1 - proba[target class].
# The 1 is a constant that doesn't change the matching, it can be ommitted.
cost_class = -out_prob[:, tgt_ids]
# Compute the L1 cost between boxes
cost_bbox = torch.cdist(out_bbox, tgt_bbox, p=1)
# Compute the giou cost betwen boxes
cost_giou = -generalized_box_iou(box_cxcywh_to_xyxy(out_bbox), box_cxcywh_to_xyxy(tgt_bbox))
# Final cost matrix
C = self.cost_bbox * cost_bbox + self.cost_class * cost_class + self.cost_giou * cost_giou
C = C.view(bs, num_queries, -1).cpu()
sizes = [len(v["boxes"]) for v in targets]
indices = [linear_sum_assignment(c[i]) for i, c in enumerate(C.split(sizes, -1))]
return [(torch.as_tensor(i, dtype=torch.int64), torch.as_tensor(j, dtype=torch.int64)) for i, j in indices]
def build_matcher(args):
return HungarianMatcher(cost_class=args.set_cost_class, cost_bbox=args.set_cost_bbox, cost_giou=args.set_cost_giou)
https://www.geeksforgeeks.org/hungarian-algorithm-assignment-problem-set-1-introduction/?ref=rp
http://www.hungarianalgorithm.com/index.php
en.wikipedia.org/wiki/Hungarian_algorithm
brilliant.org/wiki/hungarian-matching/
github.com/tdedecko/hungarian-algorithm/blob/master/hungarian.py
github.com/facebookresearch/detr/blob/master/models/matcher.py
'심화 > 영상 - Algorithm' 카테고리의 다른 글
| Eight Points algorithm(Normalized) - 과제 해결 (0) | 2022.11.19 |
|---|---|
| Bag of Visual Words 개념 (0) | 2021.07.07 |
| Hausdorff Distance (0) | 2020.12.28 |
