Hungarian Algorithm

Macar algoritması, iki kümeden küçük olanındaki her öğeyi eşleştiren, en düşük maliyetli bire bir eşleşmeyi bulan kesin bir optimizasyon yöntemidir. Seçilen tüm eşleşmelerin toplam maliyetini en aza indirir. Bilgisayarlı görüde tespitleri izlenen nesnelerle veya tahminleri eğitim hedefleriyle eşleştirir.

Harold W. Kuhn, algoritmayı 1955'te Atama Problemi için Macar Yöntemi başlıklı çalışmasında tanıttı. Macar yöntemi ve Kuhn–Munkres algoritması, aynı algoritma ailesinin alternatif adlarıdır. Yöntemin adı, çalışmaları bu yöntemin temelini oluşturan Macar matematikçiler Dénes Kőnig ve Jenő Egerváry'yi onurlandırır.

Macar Algoritması Nasıl Çalışır?#

Girdi bir maliyet matrisidir: Her satır bir kümedeki öğeyi, her sütun diğer kümedeki bir öğeyi temsil eder ve her hücre bu öğeleri eşleştirmenin maliyetini belirtir. Kare bir matriste çözüm, her satır ve sütundan tam olarak bir hücre seçer. Açgözlü bir strateji, tek tek cazip görünen eşleşmeleri seçer; Macar eşleştirmesi ise toplam maliyeti küresel olarak en aza indirir.

Klasik matris indirgeme yönteminde her satırın minimum değerini o satırdaki değerlerden, ardından her sütunun minimum değerini o sütundaki değerlerden çıkar. Her atama her satır ve sütunu bir kez kullandığından, bu indirgemeler en iyi tam atamayı korur. Tüm sıfırları mümkün olan en az sayıda yatay ve dikey çizgiyle kapat. n x n boyutundaki bir matris için n çizgi gerekiyorsa, aynı satırı veya sütunu paylaşmayan n sıfır seç. Aksi takdirde, kapatılmamış en küçük değeri kapatılmamış hücrelerden çıkar, bu değeri kapatma çizgilerinin kesişimindeki hücrelere ekle ve kapatma testini tekrarla. Atamanın maliyetini özgün matrisi kullanarak hesapla.

Verimli Macar algoritması uygulamaları, kare matrislerde n! olası tam atamaya kıyasla O(n³) zamanda çalışır.

Bilgisayarlı Görü Uygulamaları#

Çoklu nesne takibi. Özgün SORT tasarımı, her izinin konumunu tahmin eden bir Kalman filtresiyle Macar atamasını birleştirir. Kesişim birleşim oranı, tahmin edilen ve tespit edilen sınırlayıcı kutular arasındaki örtüşmeyi ölçer. SORT'un başvuru uygulaması, atamayı LAPJV veya SciPy kullanarak çözer, örtüşmesi düşük eşleşmeleri reddeder ve eşleşmeyen tespitlere kimlik atar.

Nesne tespiti eğitimi. DETR, sıralanmamış tahminleri etiketlenmiş nesnelerle eşleştirmek için Macar eşleştirmesini kullanır. Transformer, tahmin yuvaları üretir ve eşleştirme; sınıflandırma maliyetini kutu konumu maliyetiyle birleştirir. Yeterli sayıda yuva olduğunda her hedef bir tahmin alır; böylece kayıp fonksiyonu açıklama sırasından bağımsız olur ve eşleşmeyen yuvalar "nesne yok" sınıfını öğrenir. Ultralytics bu atama formülasyonunu RT-DETR içinde uygular: HungarianMatcher, sınıflandırma maliyetini, L1 koordinat mesafesini ve genelleştirilmiş IoU maliyetlerini birleştirir. Doğrusal atama arka ucu, eğitim eşleşmelerini seçmek için değiştirilmiş bir Jonker–Volgenant çözücüsü kullanır.

Python'da Macar Eşleştirmesi#

munkres Python paketi, Macar yöntemini uygular. Paketi pip install munkres ile yükle, ardından örnek maliyet matrisini çöz:

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}")

Çıktı Minimum total cost: 12 olur; bu, her satır ve sütundan bir hücre seçildiğinde elde edilebilecek en küçük toplamdır.

İlgili Yöntemler ve Eşleşmeyen Nesneler#

Atama problemi çözülecek görevdir; Macar algoritması ise bu görevi çözen yöntemlerden biridir. Maksimum olmayanların bastırılması, bir görüntüde birbiriyle yarışan tespitleri kaldırır. Nesne yeniden tanımlama, eşleştirme için görünüş bilgisi sağlar; bu bilgi çoğunlukla gömme vektörleri aracılığıyla elde edilir ve bu vektörler kosinüs benzerliği kullanılarak karşılaştırılır. Bu tür puanlar eşleştirme maliyetlerine dönüştürülebilir.

Küme boyutları eşit olmadığında dikdörtgen matrisler ortaya çıkar. İzleme, eksik tespitleri ve yeni ortaya çıkan nesneleri ele almak için ret kurallarına veya tanımlı eşleşmeme maliyetleri olan kukla öğelere de ihtiyaç duyar. Yanlış eşleştirme, kimlik değişimine yol açar: Bir iz kimliği başka bir nesneye aktarılır.

SciPy'nin doğrusal atama çözücüsü, aynı optimizasyon problemini değiştirilmiş bir Jonker–Volgenant algoritması kullanarak çözer. r x c boyutundaki dikdörtgen bir matris için, uygulanabilir bir tam atama varsa tam olarak min(r, c) eşleşme döndürür.