Hungarian Algorithm

الخوارزمية الهنغارية طريقة تحسين دقيقة تجد أقل مطابقة تكلفةً أحاديةً إلى أحادية، بحيث تقرن كل عنصر في المجموعة الأصغر من مجموعتين. وهي تقلل التكلفة الإجمالية لجميع الأزواج المحددة. وفي الرؤية الحاسوبية، تربط الكشوفات بالأجسام المتعقبة أو التنبؤات بأهداف التدريب.

قدّم Harold W. Kuhn هذه الخوارزمية عام 1955 في الطريقة الهنغارية لمسألة الإسناد. وتُعدّ الطريقة الهنغارية وخوارزمية Kuhn–Munkres اسمين بديلين لعائلة الخوارزميات نفسها. ويكرّم اسمها عالِمَي الرياضيات الهنغاريين Dénes Kőnig وJenő Egerváry، اللذين يشكّل عملهما أساس هذه الطريقة.

آلية عمل الخوارزمية الهنغارية#

المدخل هو مصفوفة تكلفة: يمثّل كل صف عنصرًا من إحدى المجموعتين، ويمثّل كل عمود عنصرًا من المجموعة الأخرى، وتقيس كل قيمة تكلفة إقرانهما. في المصفوفة المربعة، يختار الحل قيمة واحدة بالضبط من كل صف وعمود. تلتزم الاستراتيجية الجشعة بأزواج فردية تبدو مناسبة؛ أما المطابقة الهنغارية فتجد الحد الأدنى العالمي للمجموع.

في إجراء اختزال المصفوفة الكلاسيكي، اطرح أصغر قيمة في كل صف من جميع قيم ذلك الصف، ثم اطرح أصغر قيمة في كل عمود من جميع قيم ذلك العمود. تحافظ هذه الاختزالات على أفضل إسناد كامل، لأن كل إسناد يستخدم كل صف وعمود مرة واحدة. غطِّ جميع الأصفار بأقل عدد من الخطوط الأفقية والعمودية. إذا لزم n خطًا لمصفوفة n x n، فاختر n أصفار لا يشترك أيٌّ منها في صف أو عمود. وإلا، فاطرح أصغر قيمة غير مغطاة من القيم غير المغطاة، وأضفها عند تقاطعات خطوط التغطية، ثم أعد اختبار التغطية. احسب تكلفة الإسناد باستخدام المصفوفة الأصلية.

تعمل تطبيقات الخوارزمية الهنغارية الفعّالة في زمن O(n³) للمصفوفات المربعة، مقارنةً بـ n! إسنادًا كاملًا ممكنًا.

تطبيقات في الرؤية الحاسوبية#

تتبّع الأجسام المتعددة. يجمع تصميم SORT الأصلي بين الإسناد الهنغاري ومرشح كالمان، الذي يتنبأ بموضع كل مسار. ويقيس التقاطع على الاتحاد مقدار التداخل بين الصناديق المحيطة المتنبأ بها والمكتشفة. ويحلّ التطبيق المرجعي لـ SORT مسألة الإسناد باستخدام LAPJV أو SciPy، ويرفض الارتباطات ذات التداخل المنخفض، وينشئ هويات للكشوفات غير المطابقة.

تدريب كشف الأجسام. يستخدم DETR المطابقة الهنغارية لإقران التنبؤات غير المرتبة بالأجسام المصنفة. وينتج المحوّل الخاص به خانات للتنبؤات، وتجمع المطابقة بين تكاليف التصنيف وتحديد موضع الصندوق. ومع وجود عدد كافٍ من الخانات، يحصل كل هدف على تنبؤ واحد، ما يجعل دالة الخسارة مستقلة عن ترتيب التعليقات التوضيحية؛ وتتعلّم الخانات غير المطابقة فئة "لا يوجد جسم". وتطبّق 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، وهو أصغر مجموع ممكن عند اختيار قيمة واحدة من كل صف وعمود.

الطرق ذات الصلة والأجسام غير المطابقة#

مسألة الإسناد هي المهمة؛ والخوارزمية الهنغارية أحد المحلّلات لها. يزيل كبت غير الأعظميات الكشوفات المتنافسة داخل الصورة. ويوفّر إعادة التعرّف على الأجسام معلومات المظهر لربط الأجسام، وغالبًا ما يتم ذلك عبر التضمينات التي تُقارَن باستخدام التشابه الجيبي. ويمكن أن تصبح هذه الدرجات تكاليف للمطابقة.

تنتج المجموعات ذات الأحجام غير المتساوية مصفوفات مستطيلة. ويحتاج التتبّع أيضًا إلى قواعد للرفض أو إلى إدخالات وهمية ذات تكاليف محددة لعدم المطابقة، كي يتعامل مع الكشوفات المفقودة والأجسام التي تظهر حديثًا. ويؤدي الربط الخاطئ إلى تبديل الهوية: إذ ينتقل معرّف المسار إلى جسم آخر.

يحلّ محلّل الإسناد الخطي في SciPy مسألة التحسين نفسها باستخدام خوارزمية Jonker–Volgenant معدّلة. وفي مصفوفة مستطيلة أبعادها r x c، يعيد بالضبط min(r, c) من الأزواج إذا توفر إسناد كامل ممكن.