Kalman Filter (KF)

مرشح كالمان (KF) خوارزمية تكرارية تقدّر الحالة الخفية لنظام متغير، مثل موضع جسم وسرعته، انطلاقًا من تدفق قياسات مشوشة. ففي كل خطوة زمنية، يتنبأ بالحالة التالية وفق نموذج لحركة النظام، ثم يصحح ذلك التنبؤ بالقياس الجديد، مع ترجيح كل منهما بحسب درجة عدم اليقين. نشر رودولف إ. كالمان هذه الطريقة عام 1960، وهي تعطي أقل تقدير لمتوسط مربع الخطأ للأنظمة الخطية ذات الضوضاء الغاوسية. ويُستخدم المرشح في مستقبلات GPS وملاحة الطائرات والمركبات الفضائية وتحديد موضع الروبوتات، وتقريبًا في كل متعقّب للأجسام المتعددة في الرؤية الحاسوبية، حيث يخفف اهتزاز الاكتشافات ويتنبأ بمكان ظهور كل جسم لاحقًا.

كيف يعمل مرشح كالمان#

يحتفظ المرشح بكميتين: تقدير للحالة x، مثل الموضع والسرعة، ومصفوفة تغاير P تصف مقدار عدم اليقين في ذلك التقدير. وتتألف كل دورة من خطوتين:

1. التنبؤ: يُسقط نموذج الحركة F الحالة إلى الأمام، x = F x، ويزداد عدم اليقين بفعل ضوضاء العملية Q، التي تمثل الحركة التي لا يلتقطها النموذج: P = F P Fᵀ + Q.
2. التحديث: يصل قياس جديد z يرتبط بالحالة بواسطة نموذج القياس H. يحسب المرشح المتبقي z − H x وكسب كالمان K = P Hᵀ (H P Hᵀ + R)⁻¹، حيث تمثل R ضوضاء القياس. وتصبح الحالة المصححة x + K (z − H x)، فيما ينخفض عدم اليقين إلى (I − K H) P.

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

مرشحات كالمان في تتبّع الأجسام#

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

تعمل كل أدوات التتبّع في وضع التتبّع ضمن Ultralytics YOLO بهذه الطريقة: يتتبّع KalmanFilterXYAH في ByteTrack حالة من 8 أبعاد تشمل مركز المربع ونسبة أبعاده وارتفاعه وسرعاتها، بينما يستخدم BoT-SORT وTrackTrack صيغةً تعتمد العرض والارتفاع، ويضبط كلاهما ضوضاءه بحسب حجم المربع، بحيث تتحمل الأجسام الكبيرة والقريبة قفزات أكبر بالبكسل. ويمكن تنفيذ خطوتَي التنبؤ والتحديث نفسيهما ببضعة أسطر من NumPy لإحداثي واحد لمركز مربع:

import numpy as np

F = np.array([[1.0, 1.0], [0.0, 1.0]])  # constant-velocity model, state = [position, velocity]
H = np.array([[1.0, 0.0]])  # the detector measures position only
Q = 0.001 * np.eye(2)  # process noise: how far real motion may stray from the model
R = np.array([[25.0]])  # measurement noise: detections jitter by about 5 px

rng = np.random.default_rng(0)
truth = 100 + 3.0 * np.arange(60)  # box center moving 3 px per frame
z = truth + rng.normal(0, 5.0, truth.size)  # noisy detections

x, P = np.array([z[0], 0.0]), np.diag([25.0, 100.0])  # start from the first detection
estimates = [x[0]]
for measurement in z[1:]:
    x, P = F @ x, F @ P @ F.T + Q  # predict
    K = P @ H.T @ np.linalg.inv(H @ P @ H.T + R)  # Kalman gain
    x = x + K @ (measurement - H @ x)  # update with the weighted residual
    P = (np.eye(2) - K @ H) @ P
    estimates.append(x[0])

print(f"Detection error: {np.sqrt(np.mean((z - truth) ** 2)):.2f} px")
print(f"Kalman error: {np.sqrt(np.mean((np.array(estimates) - truth) ** 2)):.2f} px")
print(f"Estimated velocity: {x[1]:.2f} px/frame")

يطبع المرشح جذر متوسط مربع خطأ قدره 4.50 px للاكتشافات الخام و2.48 px للتقديرات بعد الترشيح، وسرعة مقدّرة قدرها 2.98 px لكل إطار، قريبة من السرعة الحقيقية البالغة 3 px، رغم أن السرعة لم تُقَس مطلقًا.

مرشحات ذات صلة#

يفترض مرشح كالمان القياسي أن نماذج الحركة والقياس خطية وأن الضوضاء غاوسية. وتخفف الأنواع المرتبطة به هذه الافتراضات:

• مرشح كالمان الموسّع (EKF): يخطّي النماذج غير الخطية حول التقدير الحالي باستخدام مصفوفات يعقوبيان في كل خطوة، وهو الخيار القياسي لملاحة GPS والملاحة بالقصور الذاتي.
• مرشح كالمان غير المخفف (UKF): يمرر مجموعة صغيرة من نقاط العينة المختارة بعناية عبر النموذج غير الخطي؛ وغالبًا ما يكون أدق من التخطي الخطي ولا يحتاج إلى مشتقات.
• مرشح الجسيمات: يمثّل توزيع الحالة بعدد كبير من العينات العشوائية الموزونة، لذا يتعامل مع توزيعات الاعتقاد غير الغاوسية ومتعددة الأنماط، مثل حالة روبوت لا يعرف أي الممرين يسلك، مقابل كلفة حوسبة أعلى بكثير.
• نموذج ماركوف المخفي (HMM): يستخدم التكرار نفسه للتنبؤ والتحديث في الحالات المتقطعة؛ ويمثل مرشح كالمان نظيره للحالات المستمرة الخطية الغاوسية.

تطبيقات تتجاوز التتبّع#

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