OSNet-reidentification/hungarian_matcher.py at main · antosiowsky/OSNet-reidentification · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
"""
Hungarian Algorithm Matcher
----------------------------
Implementacja algorytmu węgierskiego (Hungarian algorithm) do optymalnego
przypisywania detekcji do ID z galerii.

Algorytm węgierski zapewnia globalne optimum w przypisywaniu,
w przeciwieństwie do greedy matching który przypisuje lokalnie.
"""

import numpy as np
from typing import List, Tuple, Optional
from scipy.optimize import linear_sum_assignment


def hungarian_match(
    similarity_matrix: np.ndarray,
    threshold: float = 0.5
) -> Tuple[List[Tuple[int, int]], List[int], List[int]]:
    """
    Dopasowuje detekcje do ID galerii używając algorytmu węgierskiego.

    Args:
        similarity_matrix: Macierz podobieństw (detekcje x galeria)
                          similarity_matrix[i, j] = podobieństwo między detekcją i a ID j
        threshold: Minimalny próg podobieństwa dla uznania dopasowania

    Returns:
        matched: Lista krotek (det_idx, gallery_idx) dla dopasowanych par
        unmatched_detections: Lista indeksów niedopasowanych detekcji (nowe osoby)
        unmatched_gallery: Lista indeksów niedopasowanych ID z galerii

    Przykład:
        similarity_matrix = np.array([
            [0.8, 0.3, 0.1],  # detekcja 0 najlepiej pasuje do ID 0
            [0.2, 0.9, 0.4],  # detekcja 1 najlepiej pasuje do ID 1
            [0.1, 0.2, 0.7]   # detekcja 2 najlepiej pasuje do ID 2
        ])
        matched, unmatched_det, unmatched_gal = hungarian_match(similarity_matrix, 0.5)
        # matched = [(0, 0), (1, 1), (2, 2)]
    """
    if similarity_matrix.size == 0:
        return [], list(range(similarity_matrix.shape[0])), []

    num_detections, num_gallery = similarity_matrix.shape

    # Przekształć podobieństwo na koszt (odległość)
    # linear_sum_assignment minimalizuje koszt, więc: cost = 1 - similarity
    cost_matrix = 1.0 - similarity_matrix

    # Algorytm węgierski - znajduje optymalne przypisanie minimalizujące koszt
    row_ind, col_ind = linear_sum_assignment(cost_matrix)

    matched = []
    unmatched_detections = []
    unmatched_gallery = list(range(num_gallery))

    # Sprawdź które dopasowania przekraczają próg
    for det_idx, gal_idx in zip(row_ind, col_ind):
        if similarity_matrix[det_idx, gal_idx] >= threshold:
            matched.append((det_idx, gal_idx))
            if gal_idx in unmatched_gallery:
                unmatched_gallery.remove(gal_idx)
        else:
            unmatched_detections.append(det_idx)

    # Dodaj detekcje, które w ogóle nie zostały przypisane
    all_matched_dets = set(det_idx for det_idx, _ in matched)
    for i in range(num_detections):
        if i not in all_matched_dets and i not in unmatched_detections:
            unmatched_detections.append(i)

    return matched, unmatched_detections, unmatched_gallery


def greedy_match(
    similarity_matrix: np.ndarray,
    threshold: float = 0.5
) -> Tuple[List[Tuple[int, int]], List[int], List[int]]:
    """
    Dopasowuje detekcje do ID galerii używając zachłannego (greedy) algorytmu.
    Szybsze niż Hungarian, ale nie gwarantuje globalnego optimum.

    Args:
        similarity_matrix: Macierz podobieństw (detekcje x galeria)
        threshold: Minimalny próg podobieństwa

    Returns:
        matched, unmatched_detections, unmatched_gallery
    """
    if similarity_matrix.size == 0:
        return [], list(range(similarity_matrix.shape[0])), []

    num_detections, num_gallery = similarity_matrix.shape

    # Zbierz wszystkie pary (det_idx, gal_idx, similarity)
    pairs = []
    for i in range(num_detections):
        for j in range(num_gallery):
            if similarity_matrix[i, j] >= threshold:
                pairs.append((i, j, similarity_matrix[i, j]))

    # Sortuj po podobieństwie malejąco
    pairs.sort(key=lambda x: x[2], reverse=True)

    matched = []
    matched_dets = set()
    matched_gal = set()

    # Greedy assignment - przypisuj najlepsze pary najpierw
    for det_idx, gal_idx, sim in pairs:
        if det_idx in matched_dets or gal_idx in matched_gal:
            continue
        matched.append((det_idx, gal_idx))
        matched_dets.add(det_idx)
        matched_gal.add(gal_idx)

    unmatched_detections = [i for i in range(num_detections) if i not in matched_dets]
    unmatched_gallery = [j for j in range(num_gallery) if j not in matched_gal]

    return matched, unmatched_detections, unmatched_gallery