خوارزمية التكثيف

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

وُصفت الخوارزمية بالتفصيل من قِبل إيسارد وبليك في منشورٍ نُشر في المجلة الدولية لرؤية الحاسوب عام ١٩٩٨. ^{[ ١ ]} من أبرز جوانب هذه الخوارزمية أنها لا تُجري عمليات حسابية على كل بكسل في الصورة، بل تُختار البكسلات المراد معالجتها عشوائيًا، ولا تُعالج إلا مجموعة فرعية منها. يدعم الطابع الاحتمالي لهذا النهج فرضياتٍ متعددة حول ما يتحرك. تستند دوال التقييم في معظمها إلى أعمالٍ سابقة في هذا المجال، وتشمل العديد من الأساليب الإحصائية القياسية. أما الجزء الأصيل من هذا العمل فهو تطبيق تقنيات تقدير مرشح الجسيمات.

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

تسعى خوارزمية التكثيف إلى حل مشكلة تقدير شكل جسم موصوف بواسطة متجه.${\displaystyle \mathbf {x_{t}} }$في ذلك الوقت${\displaystyle t}$بالنظر إلى الملاحظات${\displaystyle \mathbf {z_{1},...,z_{t}} }$من السمات المكتشفة في الصور حتى الوقت الحالي. تُخرج الخوارزمية تقديرًا لكثافة الاحتمال الشرطي للحالة${\displaystyle p(\mathbf {x_{t}} |\mathbf {z_{1},...,z_{t}} )}$ من خلال تطبيق مرشح غير خطي يعتمد على أخذ العينات العاملية، ويمكن اعتباره تطويرًا لطريقة مونت كارلو . ^{[ 1 ]}${\displaystyle p(\mathbf {x_{t}} |\mathbf {z_{1},...,z_{t}} )}$يمثل هذا تمثيلاً لاحتمالية التكوينات الممكنة للأجسام بناءً على التكوينات والقياسات السابقة. خوارزمية التكثيف هي نموذج توليدي ^{[ 2 ]} لأنها تُنمذج التوزيع المشترك للجسم والمراقب.

الكثافة الشرطية للكائن في الوقت الحالي${\displaystyle p(\mathbf {x_{t}} |\mathbf {z_{1},...,z_{t}} )}$يتم تقديرها كمجموعة عينات مرجحة ومفهرسة زمنيًا${\displaystyle \{s_{t}^{(n)},n=1,...,N\}}$مع الأوزان${\displaystyle \pi _{t}^{(n)}}$يمثل N مُعاملًا يُحدد عدد مجموعات العينات المختارة. أحد تطبيقات ذلك${\displaystyle p(\mathbf {x_{t}} |\mathbf {z_{1},...,z_{t}} )}$يتم الحصول عليها عن طريق أخذ عينة مع الإحلال من المجموعة${\displaystyle s_{t}}$باحتمالية تساوي العنصر المقابل من${\displaystyle \pi _{t}}$[ ^{1 ]​}

تسهل الافتراضات القائلة بأن ديناميكيات الجسم تشكل سلسلة ماركوف زمنية ، وأن الملاحظات مستقلة عن بعضها البعض وعن الديناميكيات، تطبيق خوارزمية التكثيف. يسمح الافتراض الأول بتحديد ديناميكيات الجسم بالكامل من خلال الكثافة الشرطية.${\displaystyle p(\mathbf {x_{t}} |\mathbf {x_{t-1}} )}$نموذج ديناميكيات النظام المحدد بواسطة${\displaystyle p(\mathbf {x_{t}} |\mathbf {x_{t-1}} )}$يجب أيضًا اختيارها للخوارزمية، وتشمل عمومًا الديناميكيات الحتمية والعشوائية .

يمكن تلخيص الخوارزمية من خلال التهيئة في وقت${\displaystyle t=0}$وثلاث خطوات في كل وقت t :

بما أن تتبع الأجسام قد يكون هدفًا في الوقت الفعلي، فإن مراعاة كفاءة الخوارزمية يصبح أمرًا بالغ الأهمية. تُعد خوارزمية التكثيف بسيطة نسبيًا مقارنةً بالجهد الحسابي الكبير لمعادلة ريكاتي المطلوبة لتصفية كالمان.${\displaystyle N}$، الذي يحدد عدد العينات في مجموعة العينات، سيكون له بالتأكيد مفاضلة بين الكفاءة والأداء.

إحدى طرق تحسين كفاءة الخوارزمية هي اختيار نموذج ذي درجة حرية منخفضة لتمثيل شكل الجسم. النموذج المستخدم في دراسة إيسارد (1998) هو نموذج خطي مُعامل لـ B-splines ، حيث تقتصر هذه الـ B-splines على تكوينات محددة. وقد تم التوصل إلى التكوينات المناسبة من خلال تحديد تركيبات الخطوط الخارجية من مناظر متعددة للجسم في أوضاع مختلفة، ومن خلال تحليل المكونات الرئيسية (PCA) للجسم أثناء عملية التشوه.

يقوم إيسارد وبليك بنمذجة ديناميكيات الجسم${\displaystyle p(\mathbf {x_{t}} |\mathbf {x_{t-1}} )}$كمعادلة فرقية من الدرجة الثانية ذات مكونات حتمية وعشوائية:${\displaystyle p(\mathbf {x_{t}} |\mathbf {x_{t-1}} )\propto e^{-{\frac {1}{2}}||B^{-1}((\mathbf {x_{t}} -\mathbf {\bar {x}}) -A(\mathbf {x_{t-1}} -\mathbf {\bar {x}} ))||^{2})}}$

أين${\displaystyle \mathbf {\bar {x}} }$يمثل متوسط ​​قيمة الحالة، و${\displaystyle A}$،${\displaystyle B}$هي مصفوفات تمثل المكونات الحتمية والعشوائية للنموذج الديناميكي على التوالي.${\displaystyle A}$،${\displaystyle B}$، و${\displaystyle \mathbf {\bar {x}} }$يتم تقديرها باستخدام تقدير الاحتمال الأقصى أثناء قيام الجسم بحركات نموذجية. ^{[ 1 ] [ 3 ]}

نموذج الملاحظة${\displaystyle p(\mathbf {z} |\mathbf {x} )}$لا يمكن تقديرها مباشرةً من البيانات، مما يستلزم وضع افتراضات لتقديرها. يفترض إيسارد (1998) أن التشويش الذي قد يحجب رؤية الجسم هو عملية عشوائية من نوع بواسون ذات كثافة مكانية.${\displaystyle \lambda }$وأن أي قياس حقيقي للهدف يكون غير متحيز وموزع توزيعًا طبيعيًا بانحراف معياري${\displaystyle \sigma }$.

تُستخدم خوارزمية التكثيف الأساسية لتتبع جسم واحد مع مرور الوقت. ومن الممكن توسيع خوارزمية التكثيف باستخدام توزيع احتمالي واحد لوصف الحالات المحتملة لأجسام متعددة لتتبع عدة أجسام في مشهد واحد في الوقت نفسه. ^{[ 4 ]}

بما أن التشويش قد يتسبب في انقسام توزيع احتمالية الجسم إلى عدة قمم، فإن كل قمة تمثل فرضية حول تكوين الجسم. التنعيم هو أسلوب إحصائي لضبط التوزيع بناءً على القياسات السابقة واللاحقة بعد اكتمال التتبع، وذلك للحد من تأثير القمم المتعددة. ^{[ 5 ]} لا يمكن إجراء التنعيم مباشرةً في الوقت الفعلي لأنه يتطلب معلومات عن القياسات اللاحقة.

يمكن استخدام هذه الخوارزمية لتحديد موقع الروبوتات المتحركة باستخدام الرؤية الحاسوبية. ^{[ 6 ]} ولكن بدلاً من تتبع موقع جسم ما في المشهد، يتم تتبع موقع منصة الكاميرا. وهذا يسمح بتحديد موقع منصة الكاميرا بشكل شامل بالاستناد إلى خريطة مرئية للبيئة المحيطة.

استُخدمت امتدادات خوارزمية التكثيف أيضًا للتعرف على إيماءات الإنسان في تسلسلات الصور. يؤثر هذا التطبيق لخوارزمية التكثيف على نطاق التفاعلات الممكنة بين الإنسان والحاسوب. فقد استُخدمت للتعرف على إيماءات بسيطة للمستخدم على السبورة البيضاء للتحكم في إجراءات مثل تحديد مناطق من السبورة لطباعتها أو حفظها. ^{[ 7 ]} كما استُخدمت امتدادات أخرى لتتبع عدة سيارات في المشهد نفسه. ^{[ 8 ]}

كما تم استخدام خوارزمية التكثيف للتعرف على الوجوه في تسلسل الفيديو. ^{[ 9 ]}

يمكن العثور على تطبيق لخوارزمية التكثيف بلغة C على موقع مايكل إيسارد الإلكتروني .

يمكن العثور على تطبيق في MATLAB على موقع Mathworks File Exchange .

يمكن العثور على مثال للتنفيذ باستخدام مكتبة OpenCV في منتديات OpenCV .

• مرشح الجسيمات - التكثيف هو تطبيق لتقدير إعادة أخذ العينات ذات الأهمية (SIR) لتتبع الخطوط الكنتورية