چکیده: امروزه روش های مختلف رهگیری در یک فایل ویدیویی در قالب دو دسته کلی مطرح می شوند. دسته اول مربوط به مسائلی هستند که فرآیند رهگیری را بصورت دنبال کردن یک هدف در یک رشته ویدیویی تعریف می کنند و دسته دوم روش هایی را مورد برررسی قرار می دهد که توانایی رهگیری چندین هدف را بصورت همزمان دارا می باشند. هدف رهگیری همزمان چند شی، تخمین وضعیت آنها با حفظ هویت و با در نظر گرفتن تغییرات حرکت و ظاهر آن ها با گذشت زمان می باشد. در یک محیط مختلط و شلوغ، این موضوع به خصوص بواسطه تصادم پی در پی ناشی از بهم ریختگی، ظاهر شبیه به یکدیگر سایر اهداف و .... بیشتر چالش برانگیز می شود. دنبال کردن عابران پیاده درصحنه های واقعی یک مولفه بحرانی برای بسیاری ار کاربردهاست، از قبیل سیستم های نظارت ویدیویی و سیستم های دستیار راننده. شناسایی و طبقه بندی دقیق عابران در بهبود فرآیند دنبال کردن عابران موثر است. اخیرا الگوریتم های دنبال کردن عابران پیاده توانسته اند کارایی خوبی را در صحنه های کم ترد بدست آورند اما کارایی آنها در صحنه های شلوغ بشدت کاهش می یابد بطوریکه ابهام در شکل ظاهری به سبب تصادم های زیاد ارتباط فضایی پیچیده ای را در بین عابران مختلف ایجاد می کند. از طرف دیگر الگوریتم های دنبال کننده در فضای حالت مانند کالمن و فیلتر ذره ای توانایی مقابله با تصادم های طولانی مدت و حل مسئله ای با پیچیدگی بالا و شباهت ظاهری زیاد اهداف را ندارند. در این تحقیق مسئله دنبال کردن عابران پیاده در یک محیط شلوغ بوسیله یک ابر گراف مدل شده است. یک استراتژی جستجوی محلی به کل برای طبقه بندی شناسایی ها بصورت سلسله مراتبی بکار گرفته شده است که سبب کاهش بسیار زیاد پیچیدگی های محاسباتی در هنگام مواجهه با تغییرات ناگهانی ظاهری و حرکتی اهداف می شود.نخست فایل ویدیوی به چند قسمت در حوزه زمان تقسیم می شود و همسایگی های متراکم در هر قسمت جستجو می شوند تا چندین مسیرک طولانی تر ساخته شوند. سپس قسمت های نزدیک بهم برای ساختن تقسیم بندی جدید جهت بکارگیری در لایه بعد باهم یکپارچه می شوند. این دو مرحله تکرار می شوند تا زمانی که فقط یک قسمت در لایه باقی بماند یعنی کل ویدیو مورد نظر و جستجوی همسایگی های متراکم در این قسمت انجام می شود تا مسیر نهایی حرکت اهداف بدست آید. این روش قادر است تا بطور همزمان چند هدف را در یک محیط شلوغ دنبال کند. نتایج بدست آمده بر روی پایگاه داده ParkingLot بخوبی نشان می دهد که مسیر حرکت اهداف بصورت صحیح دنبال شده است.