پیاده‎­سازی الگوریتم تخمین حرکت مورد استفاده در تصاویر ویدیویی

۱- مقدمه: سیستم‌های نهفته، هم‌طراحی سخت افزار/نرم افزار

امروزه در هزاره‌ی سوم، بیش از ۹۶% سیستم‌های کامپیوتری را سیستم‌های نهفته (Embedded Systems) تشکیل می‌دهند [۱]. سیستم نهفته یک سیستم پردازش اطلاعات است که درون محصول فراگیرنده‌ی آن نهفته است. بستر کاربرد چنین سیستم‌‎هایی بسیار گسترده است و از تلفن‌‎های راه دور تا بسیاری از تجهیزات نظامی را در بر می‌گیرد. سیستم‌‎های نهفته با مشخصه‌‎های متنوعی شناسایی می‌شوند. یکی از این مشخصه‌ها که در بیشتر این سیستم‌ها مشترک است، استفاده از هم‌طراحی یا طراحی توأمان سخت‌افزار و نرم‌افزار (Hardware-Software Co-design) است، یعنی سبکی از طراحی که بر طراحی ترکیبی نرم‌افزاری-سخت‌افزاری دلالت دارد تا بتواند نیازهای پیچیده و گاه متعدد سیستم‌های نهفته را برآورده کند. ایجاد تعادل بین هزینه‌ی سخت‌افزار-نرم افزار (از جمله مساحت، قیمت، توان مصرفی و …) و کارایی از جمله مهم‌ترین اهداف هم‌طراحی است. هدف این بخش از مجموعه مسابقات طراحی سخت­افزار، به رقابت گذاشتن توانایی‌‎های شرکت‌کنندگان از نظر مهارت‎های کاربردی ایشان در به کارگیری توانایی طراحی نرم‌افزار و سخت‌افزار به صورت توأمان است.

با توجه به دشواری‎های چند بعدی انتخاب سوال برای مسابقات هم طراحی سخت افزار/نرم افزار، موضوع سوال در نظر گرفته شده برای مسابقات امسال به گونه‎­ای است که علاوه بر پرهیز از پیچیدگی­‎های غیر ضروری، بتواند بیشتر بر روی ارزیابی راندمان معماری­‎های تلفیقی سخت افزاری/نرم افزاری پیشنهادی (و به عبارت دیگر کیفیت تقسیم بندی معماری مورد نظر به بخش‎های نرم افزاری و سخت افزاری توسط شرکت‎کنندگان) تمرکز کند. همچنین در این دوره از مسابقات با ایجاد شفافیت و خودکار کردن فرایند ارزیابی راندمان طرح­‎های پیشنهادی، از هرگونه خطای انسانی یا ابزاری نیز جلوگیری بعمل خواهد آمد تا دقت بیشتری برای نتایج به دست آمده حاصل گردد.

در ادامه، ابتدا به منظور آشنایی بیشتر با مفاهیم مورد استفاده، به معرفی مختصری از فناوری ویدیو، ضرورت فشرده­‎سازی آن و الگوریتم تخمین حرکت [۲] به عنوان یک روش افزایش بهینگی در شیوه­‎های فشرده­‎سازی ویدیوها پرداخته می­شود. پس از آن، مساله مورد نظر این دوره از مسابقات مطرح خواهد شد و در انتها شیوه ارزیابی طرح­‎های شرکت‎­کننده در مسابقه و همچنین روش برگزاری مسابقات ارائه می­‎گردد.

۲- فناوری ویدیو و ضرورت استفاده از فشرده‎­سازی

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

بررسی­‎ها نشان می­‎دهند که در دنباله‎­های ویدیویی افزونگی اطلاعاتی بین فریم‎­ها بسیار زیاد هستند. یک فشرده­‎ساز ویدیو دنباله‎­ی تصاویر ویدیویی را با استفاده از حذف این افزونگی‎­ها فشرده می‎­کند. یکی از این افزونگی‎­ها افزونگی زمانی است. در اغلب تصاویر متحرک رایج، تفاوت بین فریم‎­های متوالی در یک دنباله ویدیویی به دلیل فاصله‎­ی زمانی بسیار کوتاه بین آن­ها بسیار کم است که این همبستگی زیاد بین فریم‎­های متوالی، افزونگی زمانی نامیده می‎­شود. یکی از راهکارهای حذف این نوع از افزونگی استفاده از انواع الگوریتم‎­های تخمین حرکت می­‎باشد. معروف­‎ترین الگوریتم تخمین حرکت جست­‎و­جوی سرتاسری است که برای ارسال یک فریم، آن‎ را به بلاک‎های a X a تقسیم‎بندی می‎کند و سپس برای هر یک از این بلاک‎ها شبیه­‎ترین بلاک در فریم ارسال شده قبلی را می‎یابد و بدین ­ترتیب بجای ارسال یا ذخیره‎سازی تمامی بلاک‎های فریم تصویر، تنها با ذخیره اطلاعات بردارهایی وزن­‎دار، میزان و جهت جابجایی بلوک‎­های فریم‎­های متوالی را ذخیره می­‎کنند. تخمین حرکت به دلیل اهمیت و بار محاسباتی بسیار بالایی که دارد از بحرانی‎ترین بخش‎های فشرده‎­سازی ویدیو به حساب می‎آید. در راستای کاهش حجم محاسبات الگوریتم‎­های سنتی و افزایش کارایی جست‎­و­جوهای سرتاسری که همه بلوک­‎های تصویر را پیمایش می­‎کنند و سعی در یافتن بلو‎ک‎­های کاملا یکسان را دارند، الگوریتم‎­های متنوعی معرفی گردیدند که با الگوهای جست‎­و­جوی مختلفی سعی در یافتن شبیه‎ترین بلوک را دارند.

۳- صورت مساله

مساله مورد نظر این مسابقه با الهام از الگوریتم تخمین حرکت، که پیشتر توضیح داده شد، به صورت زیر تعریف می‎گردد:
هدف پیدا کردن شبیه­‎ترین بلوک یا بلوک‎های تصویر از یک فریم کامل تصویر به بلوکی از پیش مشخص­‎شده است. به طوری که بلوک یا بلوک‎های شناسایی‎شده دارای کمترین میزان تفاوت محتوایی بین تمام بلوک‎­های آن تصویر با بلوک تصویری مد نظر سوال را داشته باشند. به منظور تشخیص شباهت بین بلوک مدنظر با بلوک‎­های تحت جست­‎و­جو، از رابطه معروف Mean-Squared Error استفاده می­‎گردد.

اطلاعات مورد نیاز برای آغاز کار:

• ابعاد تصویر مبنا: ۷۶۸ * ۱۲۸۰ (تصویر مورد نظر مسابقه را از اینجا دانلود نمایید)
• ابعاد بلوک مورد جست و جو: ۱۰۰ * ۱۰۰
• کیفیت تصویر: Grayscale 8-bit

توجه: کد ++C الگوریتم تشخیص بلوک مشابه مورد استفاده برای حل مسأله‎­­ی مسابقه نیز در اختیار شرکت‎­کنندگان قرار داده شده است که می­‎تواند برای درک بهتر صورت مساله و بررسی صحت عملکرد سامانه طراحی شده توسط تیم­‎ها مورد استفاده قرار بگیرد. (کد نرم‎­افزاری الگوریتم را از اینجا دانلود نمایید)

۴-  نحوه اجرای مسابقه و ارزیابی پیاده­‎سازی­‎های انجام‎شده

فایل مربوط به اطلاعات پیکسل‎های تصویر مبنا پیش از شروع مسابقه (در روز برگزاری مسابقه) در اختیار شرکت‎کنندگان قرار می‎گیرد. در زمان برگزاری مسابقه، ابتدا سایر مقادیر اولیه مورد نیاز برای شروع کار نظیر سایز و مقادیر پیکسل‎های بلوک مورد نظر (برای جست‎وجوی بلاک‎های مشابه آن) از طریق درگاه UART سامانه داوری مسابقات در اختیار شرکت‎­کنندگان قرار خواهند گرفت. بدین صورت که، پس از اتصال پورت UART سامانه شرکت­‎کننده به سامانه داوری، سامانه‎­ی شرکت­‎کننده با ارسال یک بایت داده‎­ی مشخص (که تمامی بیت‎­های آن ۱ هستند) به سامانه‎­ی داوری، آمادگی خود را برای دریافت مقادیر اولیه اعلام می‎­کند. پس از آن، سامانه‎­ی داوری به ترتیب ابتدا یک بایت داده‎­ی مشخص (که تمامی بیت­‎های آن ۰ هستند)، پس از آن بلافاصله یک بایت شامل سایز بلاک مورد نظر (مقدار a که در این مسابقه ۱۰۰ انتخاب شده است)، سپس مجدد یک بایت داده­‎ی مشخص (که تمامی بیت­‎های آن ۱ هستند) و در نهایت بایت‎های مقادیر هر یک از a² تا پیکسل بلوک مورد نظر برای جست‎وجو را (با شروع از بالاترین و چپ‎ترین پیکسل و بصورت ردیف به ردیف) به سامانه شرکت‎­کننده ارسال خواهد کرد. توجه داشته باشید که فایل مربوط به اطلاعات پیکسل‎های تصویر مبنا پیش از شروع مسابقه (در روز برگزاری مسابقه) در اختیار شرکت‎کنندگان قرار می‎گیرد و در زمان اجرای مسابقه و از طریق سامانه داوری اطلاعات تصویر مبنا منتقل نخواهد شد. برای مثال اگر a=5 باشد، سامانه داوری به تعداد ۲۸ بایت اطلاعات به سامانه شرکت‎کننده ارسال می‎کند که پس از دریافت این اطلاعات امکان آغاز فعالیت سامانه‎­های شرکت­‎کننده برای یافتن پاسخ مسابقه میسر خواهد شد. برای نمونه در صورتیکه a=6 باشد؛ شکل زیر ترتیب ارسال بایت‎های شامل پیکسل­‎های بلاک ۶*۶ را توسط سامانه داوری نشان می‎دهد:

در پایان اجرای الگوریتم نیز پاسخ مورد نظر مسابقه (تعداد و مختصات بلاک‎های مشابه یافته شده) ­باید توسط سامانه‎­ی شرکت‎کننده از طریق درگاه UART برای سامانه داوری ارسال گردد. بدین صورت که پس از ارسال یک بایت مشخص (که تمامی بیت‎های آن ۱ هستند)، ابتدا بایت شامل تعداد بلاک‎های مشابه و سپس به همین تعداد مختصات بلاک‎های مشابه یافت شده را به سامانه داوری ارسال می‎نماید. منظور از مختصات هر بلوک مشابه یافته شده در واقع مختصات (x,y) پیکسل سمت چپ و بالای بلوک جواب (مثال نشان داده شده در شکل زیر) می‎­باشد که به ترتیب اول مقدار x و بعد از آن مقدار y ارسال می‎گردد (هر کدام بصورت دو بایت ۸ بیتی، هشت بیت اول بعنوان بیت‎های کم‎ارزش و هشت بیت دوم بعنوان بیت‎های پرارزش). برای مثال اگر در تصویر ۶*۶ نشان داده شده در شکل زیر بخواهیم مختصات بلاک ۳*۳ نشان داده شده را ارسال نماییم کافیست ابتدا یک بایت شامل مقدار ۱ و یک بایت شامل مقدار ۰ بعنوان x و سپس یک بایت شامل ۲ و یک بایت شامل ۰ بعنوان مقدار y ارسال شود.

نرخ ارسال و دریافت اطلاعات بر روی درگاه UART برابر ۹۶۰۰ بیت در هر ثانیه در نظر گرفته شده و اطلاعات بصورت کاراکترهای ۸ بیتی منتقل خواهند شد.

ارزیابی نتیجه­ مسابقه بر مبنای دو پارامتر “زمان اجرا و خاتمه‎­ی الگوریتم” و “هزینه‎­ی بستر پیاد‎ه‎­سازی” الگوریتم خواهد بود. به طوری که زمان اجرا و هزینه­‎ی کمتر دو هدفی هستند که انتظار می‎­رود شرکت­‎کنندگان به بهترین شکل به تعادل برسانند. به عبارت دیگر بتوانند کمترین میزان را برای عبارت زیر حاصل کنند:

( زمان اجرا و خاتمه‎ی الگوریتم X هزینه‎­ی بستر پیاده‎­سازی )

۱-۴- محاسبه­‎ی “زمان اجرا“

بلافاصله پس از انتقال آخرین بیت از بلوک تصویر مورد نظر، تایمر سامانه‎­ی داوری شروع به شمارش می­‎کند. این شمارش تا زمانی ­که آخرین بیت از مختصات آخرین بلاک مشابه یافت شده از UART سامانه­‎ی تیم شرکت­‎کننده توسط سامانه‎­ی داوری دریافت گردد، ادامه خواهد داشت. پس از آن و با توجه به امکان محاسبه‎­ی زمان صرف شده برای دریافت پاسخ مسابقه از سامانه‎­ی شرکت­‎کننده توسط سامانه­‎ی داوری، و کسر آن از زمان محاسبه شده توسط شمارنده، زمان دقیق اجرای الگوریتم توسط سامانه‎­ی شرکت­‎کننده به ­طور خودکار محاسبه می­‎گردد.

توجه: در روز مسابقه، سامانه داوری جهت ارسال و دریافت داده‌ها و هم‎­چنین محاسبه‎­ی زمان اجرای تیم‌های مختلف شرکت‎کننده، در محل مسابقه تعبیه خواهد شد.  قطعه کد طراحی‌شده جهت اجرا بر روی ریزپردازنده ARM Cortex-M3 LPC1768 بعنوان هسته‎ی سامانه داوری، جهت ارسال و دریافت داده‎‎ها میان سامانه‌­های شرکت­‎کننده و داوری نیز در اختیار شرکت‌­کنندگان قرار دارد. شرکت­‎کنندگان می­‎توانند از قطعه کد مذکور جهت اطمینان از صحت انتقال اطلاعات بین سامانه خود و سامانه داوری و یا جهت ارزیابی زمان اجرای طرح خود استفاده کنند.

پروژه ی ایجاد شده در محیط برنامه ی Keil μvision 4 (همچنین قابل اجرا بر روی نسخه های جدیدتر Keil) برای بورد آزماینده‌ LANDTIGER NXP ARM LPC1768 DEVBOARD، از اینجا قابل دانلود است.

تصویر بورد آزماینده مذکور به همراه تصویر کابل‎­های مورد استفاده (DB9 به USB و DB9 به DB9) را در ادامه می­‌بینید. توجه داشته باشید که شرکت‌­کنندگان در روز مسابقه مجاز هستند تا با استفاده از تنها یکی از کابل‎­های مذکور ارتباط بین سامانه­‎های شرکت­‎کننده و داوری را برقرار کنند.

۲-۴- محاسبه‎ی “هزینه بستر پیاده‎سازی“

با توجع به قوانین مسابقات در بخش هم‌طراحی سخت‌افزار/نرم‌افزار، استفاده از کلیه بوردهای سخت افزاری و سخت افزاری/نرم افزاری تجاری رایج در بستر هم­‎طراحی مجاز است. برای محاسبه‎­ی هزینه بستر پیاده‎­سازی، قیمت بوردهای مورد استفاده توسط شرکت­‎کنندگان توسط تیم داوری مسابقات بر مبنای قیمت‎­های به روز و از سایت شرکت سازنده بورد استعلام خواهد شد. البته قابل ذکر است که در صورت عدم استفاده از بوردهای تجاری و ساخت بورد اختصاصی توسط شرکت­‎کنندگان؛ تیم داوری مسابقات نسبت به تخمین هزینه آن اقدام خواهند نمود. علاوه بر آن قیمت هرگونه سیستم پردازشی دیگر مانند لپتاپ و یا کامپیوتر رومیزی، که در زمان اجرای الگوریتم نیاز به وجودشان باشد، جداگانه بر اساس مشخصات سخت­‎افزاری و نرم‎­افزاری آن­ها محاسبه و به هزینه بورد اضافه می‎­گردند.

توجه: به غیر از سامانه داوری که توسط تیم برگزاری مسابقات آماده خواهد شد، فراهم آوردن هرگونه سخت­‎افزار/نرم‎­افزار مورد استفاده در بستر هم‎­طراحی شرکت­‎کنندگان در روز مسابقه بر عهده‎­ی تیم­‎های شرکت­‎کننده است.

مراجع:

[۱] Marwedel, Embedded System Design, 2^nd Ed., Springer, ISBN 9789400702578, 2011.

[۲] M. Bock, Video Compression Systems: From first principles to concatenated codecs. IET Digital Library, 2009.

برنامه اجرایی مسابقه

ضمن عرض خسته نباشید به شرکت­ کنندگان محترم مسابقه هم طراحی سخت افزار/نرم افزار، موارد زیر به استحضار میرسد:

1.  در روز چهارشنبه (۱۴ آذر) حضور تیم ها در محل مسابقات ضروری نیست هرچند که اگر تمایل به انجام زمان گیری و انجام تست طرح خود را داشته باشید می توانید از ساعت ۱۱ الی ۱۲:۳۰ در محل برگزاری مسابقات حاضر باشید و طرح خود را با سامانه داور مسابقات امتحان کنید.
2. کلیه تیم های شرکت کننده میبایست در روز پنج شنبه (۱۵ آذر) رأس ساعت ۹ صبح به منظور تکمیل فرم مربوط به اطلاعات تیم ها حضور داشته باشند.
3. شروع رکورد گیری اصلی مسابقات از ساعت ۱۱ روز پنج شنبه (۱۵ آذر) خواهد بود.
4. ترتیب فراخوانی گروه ها به قید قرعه مشخص خواهد شد و تیم ها موظف هستند در هنگام فراخوانی در محل حضور داشته باشند.
5. از هر تیم فقط یکبار رکوردگیری خواهد شد و نتایج بلافاصله به صورت آنلاین اعلام خواهد شد.
6. پس از پایان رکوردگیری و محاسبه هزینه بسترهای طراحی، در صورت نیاز و به صلاحدید ناظر مسابقات، سه تیم برتر مسابقه میبایست نسبت به در اختیار گذاشتن اطلاعات مربوط به سامانه طراحی شده (اعم از کدها و سخت افزارهای مورد استفاده) و همچنین انجام تست های تکمیلی معین شده از طرف تیم داوری مسابقه هم طراحی اقدام نمایند. نتیجه مسابقه پس از اتمام این مرحله نهایی و اعلام خواهد شد.
7. بدیهی است در صورت احساس نیاز به انجام تست های تکمیلی، هر تیمی از این امر امتناع کند از دور مسابقات کنار گذاشته خواهد شد.

نتیجه نهایی مسابقه هم‎طراحی سخت‎افزار/نرم‎افزار :

‎

رتبه ۱) تیم KNM از دانشگاه شهید بهشتی: آقایان عباس‎زاده، مزرعه‎لی و قهرمان‎زاده

رتبه ۲) تیم Team IV از دانشگاه شهید بهشتی: آقایان پاینده، اسدی رحمانی و حسینی

رتبه ۳) تیم Hormoz-Codesign از دانشگاه هرمزگان: آقایان ناصریان و تختی‎نژاد

‎