طراحی الگوریتم پردازش تصویر برای ردیابی اشیاء متحرک :انجام پروژه متلب - انجام پروژه متلب |پروژه متلب | انجام پروژه متلب برق | شبیه سازی با متلب

طراحی الگوریتم پردازش تصویر برای ردیابی اشیاء متحرک :انجام پروژه متلب

:انجام پروژه متلب

طراحی الگوریتم پردازش تصویر برای ردیابی اشیاء متحرک

فهرست مطالب

عنوان                                                                                                                                                              صفحه

فهرست مطالب …………………………………………………………………………………………………………………………………….سه

چکیده…………………………………………………………………………………………………………………………………………………..١ فصل اول: مقدمه

١-١ مقدمه …………………………………………………………………………………………………………………………………………….٢

١-٢ تعریف ردیابی اشیاء متحرک……………………………………………………………………………………………………………..٢

١-٣ کاربرد ها……………………………………………………………………………………………………………………………………….٢

١-۴ اهداف پروژه …………………………………………………………………………………………………………………………………..٣

١-۵ ساختار پایان نامه ……………………………………………………………………………………………………………………………۴

فصل دوم ابیات موضوع

٢-١ مقدمه …………………………………………………………………………………………………………………………………………………………………..۴

٢-٢روش های تخمین حرکت بر پایه مشخصه ………………………………………………………………………………………………………….۴

٢-٣ ردیابی مشخصه …………………………………………………………………………………………………………………………………………………..۵

٢- ۴روشهای مبتنی برویژگیهای کلی……………………………………………………………………………………………………………………….٧

٢-۵روشهای مبتنی برویژگیهای جزئی………………………………………………………………………………………………………………………٩

٢-۶روشهای مبتنی بر ویژگی های جزئی کلی………………………………………………………………………………………………………..١۴

٢-٧روشهای مبتنی بر هم بستگی ویژگیها………………………………………………………………………………………………………………١۶

٢-٨ روشهای مبتنی بر یک الگوی خاص …………………………………………………………………………………………………………………١۶

٢-٩ جمع بندی………………………………………………………………………………………………………………………………………………………..١٧ فصل سوم روش پیشنهادی

٣-١مقدمه …………………………………………………………………………………………………………………………………………..١٨

٣- تشخیص مناطق متحرک……………………………………………………………………………………………………………………… …………..٢٠

٣-٢-١روش تفاضل دو تصویر متوالی……………………………………………………………………………………………………………………….٢٠

٣-٢-٢ روش حذف پس زمینه ….. ……………………………………………………………………………………………………………………………٢٠

٣-٢-٢-١ مدل مبانگین ……………………………………………………………………………………………………………………………………………٢١

٣-٣ تخمین حرکت به کمک جریان نوری………………………………………………………………………………………………………………٢١

٣-۴جریان نوری………………………………………………………………………………………………………………………………………………………..٢٢

٣-۴-١حرکت دوبعدی………………………………………………………………………………………………………………………………………………٢٢

٣-۴-٢معادله جریان نوری………………………………………………………………………………………………………………………………………..٢٣

٣-۵کلیات تخمین حرکت یک شئ………………………………………………………………………………………………………………………….٢۵

٣-۶نمایش حرکت  ………………………………………………………………………………………………………………………………………………….٢۶

الف

٣-٧ معیار تخمین حرکت ………………………………………………………………………………………………………………………٢٨

٣-٨ معیار شار. نوری……………………………………………………………………………………………………………………………..٢٩

٣-٩ معیار  Bayesian………………………………………………………………………………………………………………………..30

٣-١٠ تخمین بر پایه پیکسل ………………………………………………………………………………………………………………….٣١

٣-١١ الگوریتم تطبیق بلوک………………………………………………………………………………………………………………….٣١

٣-١٢ الگوریتم جستجوی سریع ……………………………………………………………………………………………………………..٣٣

٣-١٣ روش جستجوی D-LOG-2……………………………………………………………………………………………………….33

٣-١۴ روش جستجوی سه گام ……………………………………………………………………………………………………………….٣۴

٣-١۵ مقایسه الگوریتمهای جستجو…………………………………………………………………………………………………………………………..٣۴

٣-١۶ الگوریتم های تطبیق بلوک تغییر پذیر…………………………………………………………………………………………………………..٣۵

٣-١٧ مدل حرکت نقطه ای………………………………………………………………………………………………………………………………………٣۶

٣-١٨ تخمین حرکت با استفاده ازمدل نقطه ای……………………………………………………………………………………………………..٣٨

٣-١٩ تخمین حرکت بر پایه مش …………………………………………………………………………………………………………………………….٣٨

٣-٢٠ نمایش حرکت با روش مش ……………………………………………………………………………………………………………………………٣٩

٣-٢١ تخمین حرکت با استفاده از مدل مش …………………………………………………………………………………………………………..۴١

٣-٢٢ تخمین حرکت بر پایه ناحیه …………………………………………………………………………………………………………………………۴٢

٣-٢٣ جمع بندی………………………………………………………………………………………………………………………………………………………۴۴ فصل چهارم : نتایج تجربی وشبیه سازی

۴-١مقدمه …………………………………………………………………………………………………………………………………………………………………۴۵

۴-٢ پایگاه داده …………………………………………………………………………………………………………………………………………………………..۴۶

۴-٣روش جریان نوری………………………………………………………………………………………………………………………………………………..۴٧

۴-۴مسئله .Aperture………………………………………………………………………………………………………………………..50

۴-۵روشهای حل مسئله Aperture………………………………………………………………………………………………………50

۴-۶ روش Horn schunck………………………………………………………………………………………………………………….50

۴-٧روش kanade &Lucas ……………………………………………………………………………………………………………..52

۴-٨روش   حل Least squares…………………………………………………………………………………………………………..54

۴-٩مقایسه روشهای گفته شده ………………………………………………………………………………………………………………۵۶

۴-١٠ابزار استفاده شده …………………………………………………………………………………………………………………………۵۶

۴-١١ نتایج شبیه سازی………………………………………………………………………………………………………………………..۵۶

۴-١٢ فلوچارت برنامه ……………………………………………………………………………………………………………………………۵٨

۴-١٢جمع بندی  ………………………………………………………………………………………………………………………………..۶۵ فصل پنجم  نتیجه گیری و پیشنهادات

۵-١نتیجه گیری………………………………………………………………………………………………………………………………….۶۶

۵-٢ پیشنهادات ………………………………………………………………………………………………………………………………….۶٧

ضمیمه ١……………………………………………………………………………………………………………………………………………۶٨

ب

ضمیمه ٢……………………………………………………………………………………………………………………………………………٨۵

مراجع ………………………………………………………………………………………………………………………………………………..٨۶

ج

فهرست شکل ها

عنوان                                                                              شماره صفحه

٢-١ :مراحل یک الگوریتم ردیابی مشخصه                                        ۶

٢-٢ : استفاده ازمشخصات شکل در الگوریتم  شناسائی صورت               ۸

٢-٣:استفاده از لبه های متحرک افقی و عمودی برای ردیابی اشیاء متحرک  ۹

٢-۴: نمونه نتایج الگوریتم های شناسائی گوشه وحفره                           ۱۰

٢-۵:بکارگیری مشخصات گوشه و حفره در ردیابی شئ متحرک              ۱۱

٢-۶: ردیابی صورت انسان با مشخصه نقطه                                     ۱۲

٢-٧ ردیابی بااندازه گیری فواصل در صورت انسان                            ۱۳

٢-٨ : ردیابی با استفاده توام از مشخصات فاصله و زاویه در صورت انسان  ۱۴

٢-٩ : ردیابی با استفاده از مشخصات جزئی وکلی                               ۱۵

٣-١: بلوک دیاگرام مربوط به یک سامانه ردیاب                                 ۲۰

٣-٢: دو مثال برای ارزیابی تفاوت حرکت واقعی با حرکت مشاهده شده      ۲۳

٣-٣: تجزیه بردار سرعت به دو مولفه عمود بر هم                              ۲۴

٣-۴: مشکل روزنه یا ابهام در تخمین بردار حرکت                              ۲۵

٣-۵: نمایش تخمین حرکت رو به جلو و رو به عقب                             ۲۶

٣-۶: انواع نمایش های حرکت بر روی یک تصویر شامل سر و شانه یک  انسان     ۲۸

٣-٧: نحوه اجرای الگوریتم تطبیق بلوک                                          ۳۳

٣-٨: نحوه اجرای روش جستجوی D-Log-2                                    ۳۴

٣-٩: نحوه اجرای روش جستجوی سه گام                                         ۳۵

٣-١٠: عملکرد الگوریتم تطبیق بلوک تغییر پذیر                                ۳۶

٣-١١: نحوه جابجایی یک نقطه داخلی یک بلوک                                ۳۷

٣-١٢: مقایسه عملکرد روش بلوک و روش مش                                 ۳۹

٣-١٣: نحوه تغییر شکل سلولها و جابجایی نقاط گوشه آنها                      ۴۰

د

٣-١۴: سلولهای سه ضلعی و چهار ضلعی استاندارد                             ۴۰

٣-١۵: استفاده از یک سلول مرجع واحد برای دو سلول متناسب در دو فریم متوالی    ۴۲

٣-١۶: استفاده از روش ناحیه در بدن انسان                                       ۴۳

۴-١:دو نمونه ازقابهای گرفته شده                                                   ۴۶

۴-٢: نشاندهنده میدان برداری حاصل ازجریان نوری                           ۴۹

۴-٣: اعمال روش  kanade&Lucas                                            ۵۴

۴-۴:نتایج شبیه سازی بر روی فریمهای ٣-٧-٢٧                                ۵۷

ه

فهرست جداول

عنوان                                                                              شماره صفحه

٣-١ : مقایسه عملکرد سه روش جستجوی تطبیق بلوک،D-log-2،سه گام  ۳۵

٣-٢ : نتایج مقایسه روشهای گفته شده                                              ۴۴

۴-١: مقایسه زمانی روشهای شار نوری                                            ۵۵

و

چکیده

یکی از مسائل مهم و درحال توسعه در پردازش تصویر و بینایی ماشین ، مسألۀ ردیابی اشیاء است .

در واقع ردیابی اشیاء، نمایش تغییرات موقعیت یک شئ و دنبال کردن آن در یک دنبالۀ تصاویر ویدیویی، با یک هدف خاص میباشد. اگر چه سابقۀ ایجاد پدیده ردیابی اشیاء به مسائل نظامی بر میگردد ولی امروزه به دلیل کاربردهای بسیار گسترده ردیابی اشیاء در زمینه های مختلف این مقوله و جوانب مختلف آن در سالهای اخیر (عمدتاً از ١٩٨٠ به بعد ) مورد توجه ویژه ای قرار گرفته است .در این پروژه درباره نحوه تشخیص اشیاء ،ردیابی و روشهای تخمین حرکتی صحبت شده است .

در نهایت برای پیاده سازی ردیابی از الگوریتم  جریان نوری استفاده شده است .در این روش با استفاده از اختصاص بردار حرکت برای هر پیکسل شئ مورد نظر ردیابی می شود.درپیاده سازی این روش با مشکل پنجره مواجه می شویم که برای حل آن از روش Lucas kanadبهره گرفته شده و بر روی پایگاه داده تهیه شده ، درپیاده سازی این الگوریتم از ابزار بسیار قوی و کامل     Open cv که محصول شرکت اینتل و مخصوص پردازش تصویر می باشد استفاده شده است .

کلمات کلیدی:.ردیابی شئ،تشخیص و جداسازی،جریان نوری،تخمین حرکت .

۱

فصل اول

مقدمه

فصل اول

١-١) مقدمه

یکی از مسائل مهم و درحال توسعه در پردازش تصویر و بینایی ماشین ، مسألۀ ردیـابی اشـیاء است . در واقع ردیابی اشیاء، نمایش تغییرات موقعیت یک شـئ و دنبـال کـردن آن در یـک دنبالـۀ تصاویر ویدیویی، با یک هدف خاص میباشد.

١-٢) سابقه

پیشینه ایجاد پدیده ردیابی اشیاء به مسائل نظامی بر میگردد، در واقع مسائلی چـون هـدف یابی مخصوصاً اهداف متحرک، ردیابی مسیر موشک شلیک شده برای اطمینان از صحت عمل هدف گیری و یا ردیابی مسیر موشک شلیک شده از سوی دشمن برای جلوگیری از اصابت آن به هدف و یا هدف گیری موشک دشمن در آسمان و مسائلی از این قبیل باعث پدید آمدن یک مقولۀ جدید به نام ردیابی اشیاء در زمینۀ پردازش تصاویر نظامی گردید. این مقوله و جوانب مختلف آن در سالهای اخیر (عمدتاً از ١٩٨٠ به بعد )  مورد توجه ویژه ای قرار گرفته است .

١-٣)کاربردها

امروزه به دلیل کاربردهای بسیار گسترده ردیابی اشیاء در زمینه های مختلف به جزء زمینـه های نظامی مانند زمینه های اکتشافی در حوزه هوانوردی، فشرده سـازی هوشـمند ویـدئو، مراقبـت ویدئویی، کنترل مبتنی بر بینایی ماشین ، ارتباط مفهومی کامپیوتر با انسان ، تصویربرداری پزشکی و رباتیک ،زیر سطحی، زیر دریا، تعیین مسیر حرکت دسته های پرندگان یا گله های ماهی و…، زمینه های پزشکی مانند ردیابی مسیر دارو و یا حتی اشیاء خارجی قرار داده شده در بدن و بسیاری زمینه های دیگراز جمله جوانب مرتبط با مقوله ردیابی اشیاء، ارائه الگوریتمهایی است که در مقابل پدیـده هایی چون تغییر روشنایی١ محیط ، همپوشانی٢ اشیاء، عدم حرکت اشـیاء بـا سـرعت ثابـت و یـا در راستای یک خط مستقیم و … از پایایی کافی بر خوردار بوده و حتی الامکان قابـل پیـاده سـازی در کاربردهای بی درنگ ٣ باشند.

ارائه چنین الگوریتمهایی در درجه اول نیاز به مطالعه و تحقیق کافی در مورد چگونگی و انواع حرکتهای اشیاء و مفاهیم مرتبط با آنها، انواع روشهای شناسایی حرکت و تخمین حرکت و مزایـا و معایب این روشها نسبت به یکدیگر، مسألۀ حرکت نسبی شئ ، دوربین ، بیان توابع ، روابط ریاضی و هندسی ای که این حرکات را در قالب پارامترهای ریاضی  قابـل تعیـین و تخمـین میـسر سـازد  و

۱- Illumination                                                                                                                         ۲- Occlusion

۳- Real time

۲

همچنین نحوه پارامتری کردن محیط حرکت و شناخت این  مسأله و روشهای فائق آمـدن بـر ایـن مشکلات در ردیابی و … دارد.

١-۴) اهداف پروژه

با توجه به نیاز رو به گسترش سامانه های ردیاب در کاربردهای گوناگون و مشکلات ذکر شـده در این زمینه و اهمیت کار در زمینه تحقیق و مطالعه سامانه های ردیاب مشخص میشود. در ایـن پروژه سعی شده است ، یک روش توانمند برای ردیابی اشیاء متحرک معرفی شود. دامنه کاربرد ایـن روش بر روی ویدئوهای گرفته شده با دوربین ثابت است و ردیابی بر روی انسان انجام میگیرد.

١- )ساختار پایان نامه

در فصل دوم ، روشهای تخمین حرکت بر پایه ویژگی ومفهوم میـدان حرکـت و بـردار حرکـت و نحوه نمایش آنها که از جمله مفاهیم مهم در زمینۀ تخمین حرکت و ردیابی هستند بیان میشـود.

در ادامه   مفهوم حرکت سه بعدی یک شئ صلب و ساده سازیها وتقریب هایی که برای مدل کردن آن بکار میروند و مزایا و معایب هر یک بیان میشوند.

در فصل سوم ، پدیده شار نوری ب١ه عنوان روش پیشنهادی در دنیای پـردازش تـصویر معرفـی میشود. سپس انواع الگوریتمهای تخمین حرکت دو بعدی که بر پایۀ این معادله پدید آمده انـد بـه همراه روابط و مزایا و معایب مربوط به هر یک معرفی و بررسی میگردند.

فصل چهارم مقایسه روشهای مختلف ونیز نتایج عملی بدسـت آمـده از طریـق الگـوریتم پیـشنهادی

ومعرفی نرم افزار استفاده شده را در بر  میگیرد.

فصل پنجم نیز یک جمع بندی کلی از آنچه در این پایان نامه آمده است خواهیم داشت و به نتیجه گیری از آنچه آورده شده است میپردازیم  در انتها پیشنهاداتی برای انجام کارهـا وتحقیقـات آتـی می آوریم .

۱-Optical flow

۳

فصل دوم

ادبیات موضوع

فصل دوم

ادبیات موضوع

٢-١) مقدمه

از آنجا که در این پروژه روشی برای ردیابی اشیاء متحرک بیان می شود لذا لازم است تا ابتدا روش های مختلف که اساس کار آنها با هم متفاوت است را بیان کنیم .محدودیت های کار برد هر یـک را بیان کنیم .  روش های مختلف در سامانه های ردیاب وجود دارند که عمده آنها ، به دو دستۀ اصـلی طبقه بندی     میشوند: ١) روشهای مبتنی بر ویژگی ٢) روشهای مبتنی بر شدت روشنایی، مـا در این فصل ابتداتخمین حرکت و ردیابی بر اساس ویژگی را بررسی میکنیم . مزایـا و معایـب آنهـا را بیان می کنیم . سپس در فصل بعـد روش مبتنـی بـر روشـنائی را کـه اسـاس پیـاده سـازی وروش پیشنهادی می باشد شرح می دهیم .

٢-٢)روشهای تخمین حرکت دو بعدی بر پایه ویژگی

در روشهای مبتنی بر ویژگی  نخست مشخصاتی از شئ یا اشیائی که باید ردیابی شوند یـا حرکـت آنها تخمین زده شود، در نظـر گرفتـه مـیشـود کـه ایـن مشخـصات بوسـیلۀ کـاربر و یـا بوسـیلۀ الگوریتمهای انتخاب ویژگی تعیین میگردند. شناسایی و ردیابی اشیاء بر پایـۀ همـین مشخـصات و ویژگیها انجام  میشود، به این گونه که در هر فریم از دنبالۀ تصاویر ویدئویی، این ویژگیها جـستجو شده و با تطبیق این ویژگیها در فریمهای متوالی ، پروسۀ ردیابی وتخمین حرکت صورت مـیگیـرد.

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

۴۴

٢-٣) ردیابی ویژگی

در واقع مهمترین دلیل استفاده از روش ردیابی بر پایۀ ویژگی و یا استفاده از آن در کنار یکی از روشهای ردیابی دیگر ایجاد یک الگوریتم ردیابی است که در مقابل تغییرات ناشی از تغییر شـدت روشنایی محیط و یا تغییر زاویۀ دید از قدرت بیشتری برخوردار باشد.

بسیاری از ویژگیها، برای مثال ویژگی لبه ، حساسیت کمتری در مقابـل ایـن تغییـرات دارنـد.

بعضی از ویژگیها مانند ویژگی گوشه نیز به طور محلی دارای قابلیت شناسایی دقیق هستند. مکـان این ویژگیها میتواند مکان مناسبی برای محاسبات هندسی مانند تخمین حرکت دوربین نسبت بـه صحنه باشد. ایجاد یک الگوریتم ردیابی مناسب بر پایۀ ویژگی ، در وهلۀ اول مستلزم شناخت کـافی از ویژگیها و مشخصات شئ ای که میخواهد ردیابی شود است تا بتوان از شناساگرهای متناسب بـا آنها استفاده کرد. اکثر الگوریتمهای ردیابی ویژگی ، یک حلقۀ چهار مرحله ای مطابق شـکل ۵-١ را

دنبال میکنند[١٨]:

۴

١) پیش بینی کردن

۵

٢) شناسایی ویژگی

۶

٣) مطابقت دادن

۷

۴) بازیابی اطلاعات

نخست مکان ویژگی در فریم بعدی بر اساس مکانهای قبلی آن و مدل حرکت پیش بینی می –  شود. سپس تعدادی ویژگی کاندید شناسایی شده و با ویژگی اصلی مطابقت داده مـیشـوند. آنگـاه بهترین تطبیق بر اساس معیار تطبیق بهینه انتخاب میشود. البته الگوریتمهای ردیابی در اینکه چه ویژگیهائی را انتخاب کنند و پیش بینی را چگونه انجام دهند و چه معیار تطبیقی را بکار بگیرند بـا یکدیگر متفاوت هستند.

مرحلۀ پیش بینی بر پایۀ حرکت شئ از یک فریم به فریم بعدی و مدل حرکت انتخابی مـی- باشد که مدل حرکت از مدلهای سـاده ماننـد مـدل سـرعت ثابـت تـا مـدلهای پـارامتری پیچیـده وحرکتهای با توزیع احتمال خاص میتواند باشد.

۱- Prediction                                                                                                                                 ۲- feature detection

۳- Matching                                                                                                                                  ۴- Update

۵

۵

شکل ١-١: مراحل یک الگوریتم ردیابی ویژگی

مرحلۀ تطبیق بر اساس ایجاد رابطه بین مکان اصلی ویژگی و مکانهای پیش بینی شده اسـت یک روش معمول ، ماکزیمم کردن کورولیشن بین قطعه های تصویر در اطراف مکان اصلی ویژگی و کاندیدها است . به عبارت دیگر اختلاف بین ویژگی اصلی و کاندیدها مینیمم شود.

در بسیاری کاربردها، مراحل بالا متناسب با یکدیگر هستند. مثلاً، مدل حرکت اسـتفاده شـده در مرحلۀ پیش بینی، میتواند برای معیار تطبیق نیز بکار رود. همچنین مدل حرکـت بـرای پـیش بینی حضور ویژگی و در نتیجه شناسایی آن نیز میتواند استفاده شود.

اینکه چه ویژگیهائی را برای ردیابی انتخاب کنیم ، کاملاً به نوع کاربرد و نوع تـصاویر بـستگی دارد. البته در سالهای اخیر کارهایی برای شناسایی اتوماتیک ویژگی از طریق یافتن نقاطی که فرض تغییرات وابستۀ محلی را برآورده میکنند انجام شده است که از آن جمله میتوان به روش  Shi and

-Tomasi ١٩٩۴اشاره کرد [٢١،٢٠،١٩].

برای نمونه در [٢٢] ، یک الگوریتم ردیابی بر اساس ویژگی برای پردازش تصاویر زیر دریـا بـا استفاده از روش شناسایی اتوماتیک فوق ارائه گردیده است . پردازش تصاویر زیر دریا به منظور نصب تجهیزات صنعتی، قراردادن اهداف در مسیر و موقعیت از پیش تعیین شده آنها، حفـظ و نگهـداری لوله های زیر دریا، عمل موزائیک بندی وتصویر برداری از کف دریا و غیره صورت میگیرد و از آنجا که ردیابی، یک قسمت اصلی در پردازش تصاویر گرفته شده از زیر دریا بـا اهـداف فـوق مـیباشـد، اهمیت انتخاب درست وصحیح ویژگی در الگوریتم ردیابی بیش از پیش نمایان میگردد. ردیـابی در چنین الگوریتمهایی به معنی تخمین حرکت یک یا چند ناحیه در فریمهای دنبالۀ تصاویر است .

روشهای مبتنی بر ویژگی را بسته به ویژگیهایی که مد نظر قرار میگیرند، مـیتـوان بـه پـنج

دستۀ کلی تقسیم کرد:

۶

١)  روشهای مبتنی بر ویژگیهای کلی

٢)  روشهای مبتنی بر ویژگیهای جزئی

٣)  روشهای مبتنی بر ویژگیهای جزئی ـ کلی

۴)  روشهای مبتنی بر همبستگی ویژگیها

۵)  روشهای مبتنی بر یک الگوی خاص

٢-۴) روشهای مبتنی بر ویژگیهای کلی

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

روشهایی که از مشخصات شکل استفاده میکنند نیز نیاز به جداسازی اشیاء از یکدیگر دارنـد و وجود اشیاء متعدد در صحنه و همپوشانی آنها با یکدیگر و همچنین سایه هایی کـه روی یکـدیگر میاندازند، کار شناسایی وردیابی شئ مورد نظر را دشوار میسازد [٢٣] و در بعضی مواقع نیز وجود کلاترهای پس زمینه ، شناسایی داده صحیح از کلاتر را با مـشکل مواجـه مـیکنـد. عملکـرد فیلتـر کالمن که از گسترده ترین روشها در ردیابی اشیاء است ، از جمله مواردی اسـت کـه بـه شـدت بـه حضور چند شئ متحرک در صحنه و وجود کلاتر بستگی دارد. این امر لزوم استفاده از الگوریتمهای ردیابی براساس مشخصۀ شکل که در مقابل کلاتر از قدرت بیشتری برخوردار هستند را نشان مـی- دهد [٢۴].

روشهایی که از مشخصات شکل استفاده مـیکننـد، در الگوریتمهـای شناسـایی صـورت و یـا الگوریتمهای شناسایی انسان کاربرد بسیار زیادی دارند [٢۵]. شکل ٢-٢ نتایج یکی از این روشها را نشان میدهد. در الگوریتم نشان داده شده در شکل ٢-٢، نخست صورت فرد ناحیه بندی شده و در هر ناحیه ، از روی مشخصات شکلی کـه قـبلاً در الگـوریتم منظـور شـده اسـت بـرای مثـال محـل قرارگرفتن ابروها نسبت به چشمها و یا محل و نحوه قرارگیری بینی و لبها نسبت به یکدیگر، نقـاط خاصی جستجو میشوند که در نهایت نقاط یافت شده در این الگوریتم ، مشخـصات صـورت فـرد از جمله گردی صورت ، محدوده چشمها و ابروها، محدوده بینـی و لبهـا و محـدوده موهـا را بـه دقـت مشخص میکنند.

۷

(الف )                                       (ب )

(ج )                                           (د)

شکل ٢-٢ (الف )ناحیه بندی صورت -(ب )استفاده از نحوه قرار گرفتن اچزاء صورت -(ج )استفاده از گودی چشم و محل

قرار گیری بینی ولب و ابرو-( )استفاده ازمرز اچزاء صورت [٢۵]

در بعضی از الگوریتمها، از مشخصات شکل و رنگ در کنار یکدیگر [٢۶] و در بعضی دیگر تنها از هیستوگرام نرمال شده رنگ [٢٧] ودر برخی، از هیستوگرام رنگ به همراه شناسایی دقیق طیـف رنگ [٢٨] برای شناسایی صورت استفاده می شود.

با تغییر زاویۀ دید و حرکات شئ و دوربین نسبت به یکدیگر، بسیاری از ویژگیها مانند شـکل ، اندازه ، محیط و مساحت شئ تغییر میکنند. اما یک ویژگی که نسبتاً ثابت بـاقی مـیمانـد، ویژگـی رنگ و یا هیستوگرام رنگ است . علاوه بر این ، شناسایی و دنبال کردن اشیاء بر اساس ویژگی رنـگ ساده است . الگوریتمهایی که از ویژگی رنگ استفاده میکنند، معمولاً الگوریتمهـای سـریع ، مـوثر و قابل کاربرد در سیستمهای ردیابی بی درنگ میباشند [٢٨]. البته باید توجه داشت که ممکن است این ویژگی همواره یک ویژگی کاملاً مطلوب در دنبال کردن اشیاء نباشد. مـثلاً زمـانی کـه چنـدین منبع نور رنگی و یا اشیاء مختلف با رنگهای متفاوت و در نتیجه سـطوح بازتـابش متفـاوت در فـضا وجود دارد، اطلاعات رنگ ویاهیستوگرام رنگ شئ میتواند تغییر کند. یک مثال ملموس آن ، سطوح خارجی و شیشه های اتومبیل هستند که شبیه آینه عمل کرده و با بازتابش نور باعث تغییـر طیـف روشنایی در دنبالۀ تصویر شده و لذا الگوریتمهای ردیابی مخصوصاً آنهایی که از آسـتانه گـذاری در ردیابی استفاده میکنند را با مشکل روبه رو میسازند. این مشکل در الگوریتمهـای ردیـابی صـورت نیز بسیار بوجود میآید. بنابراین واضح است که در صورتی که تـصاویر نخـست در مقابـل تغییـرات

۸

شدت روشـنایی تـصحیح شـوند، الگـوریتم ردیـابی عملکـرد بهتـری خواهـد داشـت . بـرای نمونـه الگوریتمهای ردیابی در [٣٠،٢٩] به گونه ای طراحی شده اند که خـود را در مقابـل شـرایط تغییـر شدت روشنایی وفق میدهند و یا در[٣١] از یک الگوریتم رنگ وفقی که متناوباً اطلاعات رنگ شئ را با اطلاعات موقعیت و اندازه شئ ترکیب کرده و آنها را در فضای تصویر و فضای رنگ وفـق مـی- دهد، استفاده شده است . اما علاوه بر این ، اگر نواحی با بازتابش شدید که باعث تغییـرات زیـادی در طیف روشنایی میشوند نیز شناسایی و جبران شوند، مطمئناً عملکرد الگوریتم ردیابی بسیار بهبـود مییابد. در [٢٨] روشی برای شناسایی و جبران این نواحی بیان شده است . بر اساس توضیحات بالا، دنبال کردن شئ تنها بر اساس ویژگی رنگ ، در بعضی موارد میتواند کار دنبال کردن شئ را دشوار سازد و درصد خطای آن را افزایش دهد.

٢-۵) روشهای مبتنی بر ویژگیهای جزئی

ویژگیهای جزئی، ویژگیهایی مانند خطوط ، منحنیها، مرزها، گوشه ها، نقطه ها، لبه ها، فواصل و غیره هستند. لبه ها معمولاً به نقاطی که روشنایی تصویر در آنها دارای یک تغییـر ناگهـانی اسـت گفته   میشود.

در [٣٢] تنها از لبه های متحرک افقی و عمودی برای ردیابی اشیاء متحرک در صحنۀ تصویر استفاده شده است که نتایج این ردیابی را درشکل ٢-٣ میبینید. از روشـهای شناسـایی لبـه بـرای شناسایی مرزهای اشیاء نیز میتوان استفاده کرد [٣٣].

در سالهای اخیر از روش لبۀ وفقی و یا snake برای شناسایی مرزهایی که دارای هیچ شکل و

قاعده خاصی نیستند بهره گرفته شده است .

(الف )                                                                    (ب )

شکل ٢-٣:(الف ) استفاده از خطوط -(ب )اسـتفاده از لبـه هـای متحـرک افقـی و عمـودی بـرای ردیـابی اشـیاء متحرک[٣٣]

گوشه ها نقاط لبه ای هستندکه منحنی تغییر شدت روشنایی در آنها دارای یـک مـاکزیمم محلـی باشد. نقاط گوشه بر خلاف خطوط ، به خوبی به صورت محلی قابل شناسایی وتفکیک هستند. در

۹

[٣۴] الگوریتم قدرتمندی برای ردیابی بر اساس مشخصات طبیعـی مانندگوشـه کـه هـم قابلیـت کالیبره شدن و هم پایداری در برابر نویز و همپوشانی را دارد ارائـه گردیـده اسـت . حفـره هـا٨ کـه تاریکترین یا روشنترین نواحی محلی را در تصاویر غیر رنگی نشان مـیدهنـد، عـلاوه بـر شـیارها و نواحی با خصوصیت خاص از دیگر ویژگیهای جزئی هستند که میتوانند برای ردیـابی اشـیاء مـورد استفاده قرار گیرند. شکل ٢-۴، نمونه هایی از شناسایی گوشه و حفره را نشان میدهد. در شکل ٢-

۴-الف ، تصویر اصلی به همراه نتایج الگوریتم شناسایی و انتخاب گوشه نشان داده شده است که این نقاط گوشه در فریمهای بعدی جستجو و ردیابی خواهند شد. شکل ٢-۴-ب نیز تصویر اصـلی را بـه همراه نتایج الگوریتم شناسایی حفره نشان میدهد که این حفره ها نیز در فریمهـای بعـدی دنبـال خواهند شد.

(الف )

(ب )

شکل ٢-۴(الف ) نمونه نتایج الگوریتمهای شناسایی گوشه -(ب ) نمونه نتایج الگوریتمهای شناسایی گوشه

حفره [٣۴]

در [١٨] روشهای متعددی برای شناسـایی ویژگیهـایی چـون گوشـه ، لبـه ، حفـره و شـیار و همچنین الگوریتم کاملی برای ردیابی این ویژگیها ارائه شده است که نمونۀ نتایج آن در شکل ٢-۵

۱-blob

۱۰

نشان داده شده است . توجه کنید که در ردیابی قطار، دوربین ثابت است و قطار متحرک مـیباشـد.

در حالی که در ردیابی تلفن ، دوربین حرکت میکند و تلفن ثابت است .

ردیابی با مشخ(صالۀح)فره و به روش انتخاب وفقی                   ردیابی با مشخ(صۀب )گوشه و به روش

نمونه نتایج ردیابی در فریمهای ٣٠ و٩٠ و١۵٠                        نمونه نتایج ردیابی در فریمهای ٣٠

الف

ب

شکل ٢-۵ (الف )ردیابی با مشخصه حفره وبه روش انتخاب وقفی      شکل ٢-۵ (ب )ردیابی با مشخصۀ گوشه و به روش انتخاب وفقی

نمونه نتایج در فریمهای ٣٠و٩٠و١۵٠[١٨]                              نمونه نتایج ردیابی در فریمهای ٣٠ و۵٠ و۶٠[١٨]

نقطه ها از دیگر ویژگیهای جزئی هستند که در ردیابی به روش ویژگی مورد استفاده قرار میگیرند.

یکی از کاربردهای وسیع ردیابی با مشخصۀ نقطه ، ردیـابی صـورت انـسان اسـت  [٣۶،٣۵]. در ایـن

۱۱

روشها صورت انسان با یک مجموعه نقاط خاص مشخص گردیده و این نقـاط در فریمهـای متـوالی شناسایی و ردیابی میگردند. شکل ٢-۶ نمونه ای از ردیابی صورت انسان با مشخصۀ نقطه را نـشان میدهد. همانگونه که در شکل ٢-۶-الف نشان داده شده است ، نخست صورت فرد با یـک مجموعـۀ

١٢ تایی از نقاط خاص برای مثال نقاط تعیین کننده محدوده ابروها و بینی و لبها مشخص گردیده است که روش مشخص کردن این نقاط میتواند به صورت دستی یا با استفاده از ابزارهـای طراحـی باشد. در مرحلۀ بعد، این نقاط در هر فریم جدید از دنبالۀ تصاویر با توجـه بـه مکـان آنهـا در فـریم قبلی، در یک محدوده از پیش تعیین شده جستجو و یافت میشوند و بـدین ترتیـب عمـل ردیـابی انجام میگرددکه نتایج جستجوی نقاط تعیین کننده محل بینی در دو فریم متوالی را در شـکل ٢-

۶-ب مشاهده میکنید.

(الف )

(ب )

شکل ٢-۶(الف )انتخاب نقاط مناسب برای ردیابی صورت انسان -(ب ) ردیابی نقاط مورد نظر در دو فریم

متوالی

ردیابی با اندازه گیری فواصل ، از دیگر روشهای ردیـابی مخـصوصاً در ردیـابی صـورت انـسان است [٣۵ . در این روشها یک مجموعه فواصل خاص ، به عنوان مثال فاصلۀ گوشۀ لب از بینـی یـا از ابرو یا فاصلۀ دو چشم از هم در صورت انسان اندازه گیری شده و سپس این فواصل مبنـای ردیـابی در فریمهای متوالی قرار میگیرند. شکل ٢-٧ ردیابی با فواصل را در صورت انسان نـشان مـیدهـد.

مطابق شکل ٢-٧-الف ، نخست فاصلۀ دو سوراخ بینی از هم و فاصلۀ وسـط خـط واصـل دو سـوراخ بینی از لب بالایی و لب پایینی و همچنین فاصلۀ لب بالایی از پایینی اندازه گیری شده و به عنـوان مبنا در نظر گرفته میشوند. در مرحله بعد، از آنجا که فاصـلۀ دو سـوراخ بینـی از هـم و همچنـین فاصلۀ آنها از لبها (مشروط به اینکه لبها در حالتی خاص قرار نگیرند) ثابت بـاقی مـیمانـد، لـذا بـه

۱۲

راحتی با جستجوی یکی از این نقاط با توجه به مکان    قبلی اش در فریم قبل و یافتن آن ، میتوان مکان سایر نقاط را نیز مطابق شکل ٢-٧-ب تعیین کرده و آنها را در فریمهای متوالی ردیابی کنیم .

(الف )

(ب )

شکل ٢-٧:(الف ) اندازه گیری فواصل در صورت انـسان -(ب )ردیـابی فواصـل انـدازه گیـری شـده در دو فـریم

متوالی [٣۵]

در کنار انتخاب فواصل ، میتوان زوایایی که در فریمهای متوالی ثابت باقی میمانند را نیـز بـه عنوان مشخصات ردیابی در نظر گرفت . برای مثال در صورت انسان میتوان زاویۀ بین سوراخ بینـی وگوشۀ ابرو یا گوشۀ لب را انتخاب کرد. شکل ٢-٨ ردیابی با اسـتفاده تـوأم از مشخـصات فاصـله و زاویه در صورت انسان را نشان میدهد. در شکل ٢-٨-الـف ، فاصـلۀ دو سـوراخ بینـی و زاویـۀ بـین سوراخ بینی و گوشۀ ابرو به عنوان ویژگی در نظر گرفته شده است . شکل ٢-٨-ب نیز ردیابی در دو فریم متوالی با استفاده از مشخصات فاصلۀ دو سوراخ بینی و زاویۀ بین سوراخ بینـی وگوشـۀ لـب را نشان میدهد. البته از آنجا که حالت لب میتواند تغییر کند، لـذا همانگونـه کـه در شـکل ٢-٨-ب مشاهده میکنید، برای یافتن نقطۀ گوشۀ لب علاوه بر مشخصۀ زاویه باید یک ناحیه جستجو نیز در نظر گرفته شود.

۱۳

(الف )

(ب )

شکل ٢-٨: (الف ) استفاده توأم از مشخصات فاصله و زاویه در صورت انسان -(ب )ردیابی این مشخصات در دو

فریم متوالی[٣۵]

به طور کلی، برای دنبال کردن یک شئ، ابتدا در فریم اول ، گوشه ها، لبه ها، حفره ها، منحنی مرز بیرونی شئ و یا هر مشخصۀ دیگـری از شـئ شناسـایی و تعیـین شـده و سـپس بـا یـافتن آن مشخصات در فریمهای متوالی، میتوان شئ مورد نظر را دنبال کرد.

روشهای مبتنی بر ویژگیهای جزئی و کلی، روشهای نـسبتاً سـریعی هـستند و مـیتواننـد در کاربردهای بی درنگ بکار روند. این روشها در برابر همپوشانی جزئی تاحدودی پایا هـستند ولـی در برابر همپوشانی کامل ، کارایی خود را از دست میدهند. همچنین اگر حرکت نسبی شـئ و دوربـین نسبت به یکدیگر باعث تغییر در ویژگیهای استخراج شده از شئ شود، عمل ردیـابی شـئ را دشـوار کرده و این روشها را از دنبال کردن شئ باز میدارد.

٢-۶) روشهای مبتنی بر ویژگیهای جزئی ـ کلی

روشهایی که تاکنون در مورد آنها صحبت شد، از یک یا چند ویژگی کلی و یـا یـک یـا چنـد ویژگی جزئی برای ردیابی اشیاء استفاده میکردند. اما در بعضی روشها، ترکیبی از ویژگیهای جزئـی و کلی به طور توأم استفاده میگردد. مزیت این کار، افـزایش کـارایی، دقـت و پایـایی الگـوریتم در مقابل نویز، کلاتر و تغییر شدت روشنایی است . به عنوان مثال در [٣٧] از ترکیبی از مشخصات لبه

۱۴

وگرادیان ، به همراه اطلاعات رنگ ، ساختار، شکل و ناحیه برای ردیابی شئ استفاده شده است .

شکل ٢۵-٩ نتایج ردیابی را نشان   میدهد. مطابق شکل ٢-٩-الف ، نخست در فریم اول ناحیـه ای که میخواهد ردیابی شود یعنی سر کودک با یک مرز بسته تعیین میگردد که انتخاب این مرز نیز میتواند به روشهای مختلف مثلاً به صورت دستی یا با ابزارهای طراحی و یا با الگوریتمهـای تعیـین مرزهای فعال انجام شود.

سپس مشخصات این ناحیه برای مثال هیستگرام رنگ ، مساحت ، گرادیان مرزهای این ناحیـه ، مشخصات لبه ها دراین ناحیه در کنار مشخصات ساختاری و شکلی چون محل قـرار گـرفتن موهـا نسبت به صورت استخراج شده و در ردیابی مورد استفاده قرار میگیرند. در هر فریم جدیـد، ناحیـۀ مورد نظر با توجه به مکان آن در فریم قبلی و همچنین مشخصات هیستگرام رنگ و گرادیان مرزها جستجو شده و سپس با بررسی سایر مشخصات داخلی ناحیه یعنی مشخصات لبه ، مساحت ، ساختار و شکل ، بهترین کاندید برای ناحیۀ مورد نظر انتخاب میشود. شکل ٢-٩-ب نتایج ردیـابی را نـشان میدهد.

(الف )

(ب )

شکل ٢-٩(الف  استفاده از مشخصات جزئی ـ کلی -(ب )ردیابی این مشخصات در فریم های متوالی[٣٧]

۱۵

مجموعه مشخصات خاص از ناحیۀ داخلی این مرز بسته استخراج میشود. آنگـاه مکـان مـرز بسته با توجه به این مشخصات خاص در فریمهای متوالی جستجو و ردیابی میگردد. در هـر فـریم جدید، در مرحلۀ اول مکان تقریبی مرز بسته با توجـه بـه تخمـین میـدان حرکـت در چنـد نقطـۀ انتخابی روی مرز مشخص میشود که میتوان از روش تقریب چند ضلعی [١٧]  برای تعیین چنـد نقطۀ خاص روی مرز و از معادلۀ شار نوری [١٠] برای تخمین میدان حرکت استفاده کرد.

در مرحلۀ بعد نیز با توجه به مشخصات ناحیۀ در حال ردیابی، بهترین مرز بسته انتخاب مـی- شود، به این صورت که چندین مرتبه با روش B-spline [٣٨] مرز تقریبی تغییر داده میشود و هر بار مشخصات ناحیه با مشخصات مورد نظر سنجیده میشـود تـا در نهایـت بهتـرین مـرز بـسته بـا نزدیکترین مشخصات به مشخصات مد نظر بدست آید [٣٨].

٢-٧) روشهای مبتنی بر همبستگی ویژگیها

در این روشها، همبستگی ویژگیها وارتباط هندسی بین آنها و یا تعیین ویژگی ارتباط هندسی بین شئ سه بعدی و دوربین [٣٩] مورد توجه قرار میگیرد. بنابراین واضـح اسـت کـه ایـن روشـها مستلزم محاسبات زیادی هستند و لذا هم هزینۀ بالایی دارند و هم از سرعت پایینی برخوردار مـی- باشند و برای کاربردهای بی درنگ مناسب نیستند [۴٠].

٢-٨) روشهای مبتنی بر یک الگوی خاص

در این روشها، یک ا لگوی خاص از ناحیه ای که باید جستجو، شناسایی و ردیابی شود بوسیلۀ یک تکنیک کلیک کردن و یا با توجه به یک تصویری که از قبل وجود دارد مورد توجه قرار میگیرد و سپس از طریق روشهای مختلف ، برای مثال روش HHFM9 [۴١] ، آن الگوی خاص در فریمهـای مختلف شناسایی و ردیابی میشود. در [۴٢]  الگوریتمی بر اساس روش فوق بدون اینکه از اطلاعات رنگ استفاده شود بیان شده است که از مزایای آن میتوان سادگی، سرعت بالا، مینیمم اندازه شـئ تا۵٠ پیکسل و قدرت آن در مقابل تغییراتی مانند تغییـر روشـنایی، حرکـت انتقـالی و چـرخش در صفحۀ تصویر تا زاویۀ تقریباً ٩٠ درجه را بیان کرد

۱- Holistic Harr-like Feature Matching

۱۶

٢-٩) جمع بندی

در این فصل روشهائی که بر اساس ردیابی ویژگیها هستند ارائه شد. در ادامه مراحـل ردیـابی این ویژگیها گفتـه شـد.مهمتـرین تقـسیم بنـدی آنهـا بـر اسـاس جزئـی بـودن وکلـی بـودن مـی باشد.بـارزترین ویژگیهـای کلـی عبارتنـد از محیط ،مـساحت ،شکل و رنـگ مـی باشـند و بـارزترین ویژگیهای جزئی عبارتند از لبه ،خط ،مرز،گوشه ،حفره واندازه گیری فواصل معین می باشند که بطـور مفصل در باره آنها صحبت شد.

۱۷

فصل سوم

روش پیشنهادی

فصل سوم

روش پیشنهادی

٣-١) مقدمه

تخمین حرکت ، یک قسمت مهم از هر سیستم پردازش ویدیویی میباشد در این فصل ، تمرکز روی تخمین حرکت دو بعدی است . تخمین حرکـت دو بعـدی عـلاوه بـر اینکـه دامنـۀ وسـیعی از کاربردها شامل تغییر نرخ نمونه برداری١٠، فیلترکردن ، فشرده سـازی ویـدیوئی١١ و غیـره را شـامل میشود، اغلب یک مرحله پیش پـردازش لازم درتخمـین حرکـت سـه بعـدی و همچنـین تخمـین ساختار سهُ بعدی نیز محسوب میشود. بسته به نوع کاربرد، روشهای تخمین حرکت میتوانند بسیار متنوع باشند.

۱- Sampling rate conversion                                                                                ۲- Video compression

۱۸

برای مثال ، برای کاربردهای بینایی ماشین کـه بردارهـای حرکـت دوُ بعـدی بـرای اسـتخراج ساختار و پارامترهای حرکت سـه بعـدی اسـتفاده مـیشـوند، یـک مجموعـۀ محـدود و پراکنـده از بردارهای حرکت دوبعدی در نقاط مشخصۀ خاص کفایت می کند.

از طرف دیگر، برای کاربردهای فشرده سازی ویدیوئی، بردارهـای حرکـت تخمـین زده شـده ، برای پیش گویی حرکت در یک فریم که باید براساس یک فریم مرجع کـد شـده قبلـی، کـد شـود استفاده      میشوند. هدف نهایی، مینـیمم کـردن تعـداد بیتهـای اسـتفاده شـده بـرای کـدکردن بردارهای حرکت و پیش بینی خطاها میباشد. یک چالش ١٢ بین دقت حرکت تخمـین زده شـده و تعداد بیتهای استفاده شده برای مشخص کردن مشخصات حرکت وجود دارد [١].

ممکن است حتی هنگامی که حرکت تخمین زده شده یک بیان دقیق از یک حرکـت واقعـی فیزیکی نمیباشد، منجر به پیش بینی مطلوبی از حرکت شود لذا همچنان یـک تخمـین خـوب در نظر گرفته میشود. این فصل ، بر روی انواع الگوریتمهای تخمین حرکت دو بعدی که برای پـردازش حرکت اعم از پیش بینی ، فیلتر کردن و پـالایش ، درون یـابی حرکـت ١٣ و غیـره شـکل گرفتـه انـد متمرکز میشود [٢ ،٣ ۴].

بلوک دیاگرام یک سامانه ردیاب در شکل ٣-١ نشان داده شده  که در ادامـه ابتـدا روشـهای تشخیص شئ متحرک گفته شده و نیز تعدادی از این روش هـا بـا هـم مقایـسه مـی شـود سـپس روشهای مختلف تخمین بر پایه شار نوری گفته شده ودر انتها با هم مقایسه می شوند.

٣-١ بلوک دیاگرام مربوط به یک سامانه ردیاب

۱-Trade off                                                                                                                                    ۲- Interpolation

۱۹

٣-٢ تشخیص مناطق متحرک

در این قسمت به تشریح چگونگی تشخیص اشیاء متحرک می پردازیم ،برای تشخیص منـاطق

متحرک و اشیاء متحرک دو روش را تشریح می نمائیم :

٣-٢-١ روش تفاضل دو تصویر متوالی

در این روش برای استخراج نواحی حرکت ، از اختلاف دو یا سه قاب متوالی در دنباله تصاویر استفاده می کنند. پس از این عمل ، تصویر حاصل از تفاضل قاب ها را با استفاده از یک تابع ، آستانه ای می – کنند. این روش بسیار سریع و برای محیط های پویا بسیار مناسب است . اما مشکل ایـن روش ایـن است که برخی از نواحی حرکت را ممکن است حذف نماید و یا برخی از نواحی ثابت اطـراف جـسم متحرک را به عنوان ناحیه حرکت در نظر بگیرد. در [۵١] از تفریق زمانی برای بدست آوردن ناحیه

حرکت استفاده کرده اند. آنها قدرمطلق تفاضل دو قاب متوالی را به صورت زیر بدست آورده اند:

∆n = In − In−۱                                                                                                                                                                                            (۱-۳)

که In تصویر خاکستری قاب n ام از دنباله تصاویر است . سپس برای بدست آوردن تصویر حرکت به

صورت زیر عمل شده است :

Mn (u, v)=In u v                                                ∆n u v ≥T  (۲-۳)

( , )                                                                                             ,    ( , )

۰                                                                                                 ,    ∆n (u, v) ≥T 

که T مقدار آستانه سازی است و به طور تجربی حدود ۴٠ برای دنباله تـصاویر خاکـستری بـا ٢۵۵ سطح بدست آورده اند.

سپس با استفاده از آلگوریتم برچسب زنی اجزاء پیوسته نواحی حرکـت را اسـتخراج کـرده انـد. در نسخه اصلاح شده تفریق زمانی از اختلاف سه قاب متوالی استفاده مـی شـود. روش تفریـق زمـانی اگرچه بسیار سریع است ولی به تنهایی از کارایی بالایی برخوردار نیست و نواحی حرکت را به طـور کامل تشخیص نمی دهد. ترکیب این روش با روش های دیگر می تواند نتایج بهتری به دست دهد.

٣-٢-٢  روش حذف پس زمینه

در این قسمت روش هایی که سعی در مدل کردن پس زمینه در طول زمان را دارند را بررسـی مـی- کنیم . در اینگونه از روش ها یک اطلاعات آماری از هر یـک از پیکـسل هـای تـصویر در طـول زمـان بدست میآید و در زمانی که نقطه ای از این آمارگان فاصله گرفت آنرا به عنوان پـیش زمینـه اعـلام میکنند. در این دسته روش های گوناگونی جای میگیرند کـه مـا روش مـدل میـانگین  را بررسـی میکنیم .

۲۰

٣-٢-٢-١ مدل میانگین

در این روش میانگین قاب های متوالی در طول زمانی محدود بدست آورده مـی شـود و بـه عنـوان تصویر زمینه در نظر گرفته می شود. سپس قدر مطلق تفریق تصویر هر قاب از آن محاسبه و با یک مقدار آستانه ، آستانه ای و نواحی حرکت استخراج می گردد [۵٢] و [۵٣].

در [۵٣]  از میانگین زمانی دنباله تصاویر برای بدست آوردن تصویر زمینه استفاده کرده اند. تـصویر

زمینه را در زمان t به صورت زیر بدست آورده اند:

B(x, y,t) =1  t∑I( x, y,t’)                                                            (۳-۳)

tt’=1

که (I)x, y, t مقدار پیکسل (x, y) در زمان t است . فرمول فوق به صورت زیر نیـز قابـل محاسـبه

میباشد:

B(x, y, t) =t1B(x, y, t−۱) +۱I(x, y, t)                    (۴-۳)

−

t          t

با تفریق تصویر از زمینه ، تـصاویر اشـیاء متحـرک

بدست می آید که البته این تصویر با مقداری ثابت آستانه ای می شود.

روش میانگین زمانی دنباله تصاویر بسیار سریع است و برای استفاده در محیط های سربسته نتیجه خوبی بدست می دهد، اما نسبت به تغییرات نور، نویز و حرکت های جزیی در محیطهای سرباز مثل حرکت برگ درختان بسیار حساس است و نمی تواند تغییرات زمینه محیطهای سرباز را بـه خـوبی مدل کند.

٣-٣ تخمین حرکت به کمک شار نوری

دراین قسمت پدیده شار نوری تعریف میگـردد و سـپس معـادلات مربـوط بـه آن کـه یـک محدودیت بین گرادیانهای تصویر و بردارهای سرعت تحمیل میکنند بررسی میشـوند. بـسیاری از الگوریتمهای تخمین حرکت بر پایه همین معادلۀ مهم و اساسی میباشند. در ادامه ، روشهای معمول برای تخمین حرکت دو بعدی بیان شده و مشاهده خواهد شد که مشکل تخمین حرکت معمولاً بـه یک مسالۀ بهینه سازی مبدل میشود که شامل سه قسمت کلیدی است : پـارامتری کـردن میـدان حرکت ، فرمول بندی کردن معیار و ملاک بهینه سازی و جستجو برای پارامترهـای بهینـه . در ایـن فصل ، مگر در موارد خاص ، هرجا کلمه  “حرکت ”  بکار برده شود منظور حرکت دوُ بعدی است .

٣ ۴) شار نوری

٣-۴-١) حرکت دوبعدی و معادله شار نوری

چشم انسان ، حرکت را با استفاده از شناسایی نقاط متناسب در زمانهای مختلف درک میکند. ایـن تناسب معمولاً با استفاده از این فرض که شدت روشنایی یک نقطه پس از حرکت تغییـر نمـیکنـد

۲۱

تعیین میشود. توجه شود که حرکت دوبعدی مشاهده شده میتواند با حرکت دوبعدی دیـده شـده واقعی تحت شرایط خاص متفاوت باشد. شکل ٣-٢ دو حالت خاص را نشان میدهد. در مثـال اول ، یک کره با سطح یکنواخت ، در حال چرخش حول محور کره و در یک محیط با روشنایی ثابت است .

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

در ادبیات بینایی ماشین حرکت دو بعدی مشاهده شده تحت عنوان شار نوری بیان میشـود.

ولی مثالهای بالا نشان دادند که شار نوری ممکن است با حرکت دو بعـدی واقعـی یکـسان نباشـد.

زمانی که تنها اطلاعات رنگ تصویر در دسترس است و هیچ اطلاع دیگری راجع به نحوه حرکت در دسترس نیست ، روش امید بخش تخمین حرکت ، پدیده شار نوری یعنی مبنـا قـرار دادن مـشاهده است . در ادامۀ این فصل ، عبارت  “حرکت دو بعدی”  یا به طور ساده تـر عبـارت “حرکـت ”  بـرای اشاره به شار نوری بکار میرود. ممکن است در بعضی مواقع ، شار نوری بـا حرکـت دوبعـدی واقعـی متفاوت باشد.

شکل ٣-٢: دو مثال برای ارزیابی تفاوت حرکت واقعی با حرکت مشاهده شده [١]

٣-۴ ٢) معادله شار نوری و ابهام در تخمین حرکت

یک دنبالۀ ویدیویی که تغییرات روشنایی در آن با تابع (ψ)x, y,t بیـان مـیشـود را در نظـر

بگیرید. فرض کنید نقطه تصویر (x, y) در زمان t بـه نقطـه (           x) در زمـان t+d حرکـت

t                                                                                                                                                   +d x, y+d y

میکند. تحت فرض شدت روشنایی ثابت ، تصاویر یک نقطۀ یکسان در زمانهای متفاوت دارای مقدار

روشنایی یکسان میباشد بنابراین خواهیم داشت :

ψ(x+dx,y+dy,t+dt) =ψ(x, y,t)                                                                  (۴-۳)

با استفاده از بسط تیلور و با فرض کوچک بودن d،d  و d داریم :

t    y  x

۲۲

ψ(x+dx, y+d y,t+dt) =ψ(x, y,t)+ ∂∂ψ dx + ∂∂ψ dy +∂∂ψdt                                                (۵-۳)

x    y    t

با ترکیب دو رابطه فوق ، رابطه زیر بدست میآید:

∂ψ ∂ψ ∂ψ                                                                      (۶-۳)

∂xdx + ∂ydy + ∂tdt=0

رابطه بالا بر حسب بردار حرکت (d, d) میباشد که با تقسیم آن بر  d میتوان رابطه را بر

t                                                                                                                                       x   y

حسب بردار سرعت حرکت بازنویسی کرد:

(٣-٧)                       ψ∂        یا         ψ∂ψ ∂ψ ∂

∂vx + ∂yvy+∂t =0                                                                            ∇ψTV+∂t =0

x

که (vy ,vx ) بردارسرعت یا بردار شارش و y[T∂ψ. ∂x ∂ψ. ∂] =ψ ∇ بردار گرادیان (ψ)x, y,t

است . رابطه ٣-٧ به عنوان معادلۀ شار نوری شناخته میشـود و پایـۀ بـسیاری از روشـهای تخمـین حرکت است .

با فرض کوچک بودن  d،dt .v= dx  و dt.dy  = خواهد بود. توجه کنید که معادلـه فـوق

vy                                                                                                                                                          x                    t

با فرض شدت روشنایی ثابت بدست آمد.

مطابق شکل ٣-٣ بردار سرعت  v میتواند در هر نقطه  x به دو مولفه عمود بر هـم تجزیـه

شود. یعنی:

v = ve+ve

n n     t t

شکل ٣-٣: تجزیۀ بردار سرعت v به دو مولفه عمود بر هم [١٧]

e بردار واحد هم جهت گرادیان تصویر است و جهت نرمال را مـشخص مـیکنـد و e

t                                                                                                                                 n

مؤلفه عمود بر e بوده و جهتی را که مشخص میکند جهت تانژانت مینامند. براین اساس می

n

توان رابطه -٣-٧ را به صورت زیر بازنویسی کرد:

∂ψ                                                                              (۸-۳)

vn∇ψ+ ∂= ۰

t

۲۳

که   اندازه بردارگرادیان است سه نتیجه گیری از رابطه ٣-٧ قابل حصول است :

∇ψ

١) در هر پیکسل  x، نمیتوان بردار سرعت v را به تنهایی بر پایۀ ψ∇ و t∂ .ψ ∂ تعیین

کرد. فقط یک معادله برای دو مجهول v و v ( یا v وv) وجود دارد. لذا باید شرایط اولیه اضافی

t                                                                                                                                                       n         y     x

بر روی معادله قرار داده شود. معمول ترین شرط این است که بردار سرعت باید به طـور یکنواخـت تغییر کند به گونه ای که همواره بتوان از تغییرات شدت روشـنایی در یـک همـسایگی کوچـک در اطراف پیکسل x برای تخمین حرکت در  x استفاده نمود.

٢) اگــرψ∇ و t∂ .ψ ∂ مــشخص باشــند، تــصویر بــردار ســرعت روی جهــت نرمــال برابــر

ψ∇ . (t ∂ .ψ ∂)− =v  خواهد بود ولی تـصویر آن روی جهـت تانژانـت بایـد تعیـین شـود. هـر

n

مقدار v معادله شار نوری را برقرار میسازد. این به معنی آن است که هر نقطه روی خـط تانژانـت ،

t

در معادله شار نوری صدق میکند. این ابهام در تخمین بردار حرکت تحت عنـوان مـشکل روزنـه ١۴ شناخته میشود. کلمه روزنه در اینجا به پنجره کوچکی که برای استفاده از فرض شـدت روشـنایی ثابت بکار میرود اطلاق     میشـود. شـکل ٣-۴ ایـن ابهـام را نـشان مـیدهـد. تعیـین اینکـه آیـا حرکت x به سمت بالا و یا عمود بر لبه است ، غیر ممکن میباشد زیرا تنها یک جهت گرادیـان در

۱

روزنۀ ١ وجوددارد؛ در حالی که به دلیل وجود دو جهت گرادیان متفاوت در روزنۀ ٢ تعیـین دقیـق جهت حرکت x امکان پذیر است .

۲

شکل ٣-۴: مشکل روزنه یا ابهام در تخمین بردار حرکت [١]

٣) در نواحی با شدت روشنایی ثابت یا نواحی مسطح که اندازه گرادیان شدت روشنایی صـفر

است یعنی ٠ ψ∇، امکان تعیین بردار سرعت وجود نـدارد. تخمـین حرکـت تنهـا در نـواحی بـا

=

تغییرات شدت روشنایی یا به عبارتی نواحی غیر مسطح و با وجود لبه امکان پذیر است .

در مباحث بعدی، نقش کلیدی و مهم معادلۀ شار نوری درکلیه الگوریتمهای تخمـین حرکـت

بیشتر روشن می شود.

۱- Aperture problem

۲۴

٣-۵) کلیات تخمین حرکت یک شئ

تخمین حرکت برای یک نقطـه خـاص بـین دو فـریم یعنـی ( ,  , ) و (  ,  , ) را در نظـر

ψ x y t2  ψ x y t1

بگیرید. بردار حرکت بین دو زمان t و  t در نقطۀ مربوطه به عنوان جابه جایی این نقطه از زمان

۲            ۱

t تا زمان  t تعریف میشود. فریم مربوط به زمان t، فریم مبدأ یا اصطلاحاً فریم لنگـر١۵ و فـریم

۱                                                                                                                                                         ۲                              ۱

مربوط به زمان  t ، فریم هدف ١۶ نامیده میشود. توجه کنید که فریم مبدأ لزوماً قبل از فریم هدف

۲

قرار ندارد و بسته به نوع کاربرد، میتواند قبل یا بعد از فریم هدف باشد. مطابق شکل ٣-۵ زمانی که

t>t باشد، عنوان تخمین حرکت روبه جلو١٧ و زمانی که t<t باشد، عنوان تخمـین حرکـت رو

۱                                                                                                                                                                          ۲     ۱          ۲

به عقب ١٨ بکار برده میشود. برای سهولت ، فریمهای مبدأ و هدف بـه ترتیـب بـا (  )  و ( )

ψ۲   x   ψ۱   x

نشان داده میشود.

به طور کلی، میتوان گفت که بردار حرکت در واقع یک بردار به صورت (d)x;a است که a ،

یک بردار شامل کلیه پارامترهای حرکت و به صـورت T[ ]  مـیباشـد. بنـابراین تـابع

a = a1 a2  aL

,    ,…,

نگاشت متناظر با چنین بردار حرکتی نیز میتوانـد بـه صـورت (x;a)d + =w)x;a(  نـشان داده

x

شود. تخمین حرکت در واقع تخمین بردار پارامترهای حرکت یعنی a است .

روشهایی که تاکنون برای تخمین حرکت مورد استفاده قرار گرفته اند را میتوان به دو گـروه

اصلی طبقه بندی کرد:

ـ روشهای مبتنی بر ویژگی ١٩ـ روشهای مبتنی بر شدت روشنایی

۲۰

در روشهای مبتنی بر ویژگی، نخست مشخصاتی مانند نقطه ، خط ، گوشه و غیره انتخاب شده و در دو فریم جستجو میشوند. سپس تناسبهایی بین دو مشخصۀ یافـت شـده در دو فـریم برقـرار میگردد. آنگاه با استفاده از این تناسبها، پارامترهای مدل حرکت انتخاب شده بدست میآیند.

۱-Anchor frame                            ۲- Target frame

۳- Forward motion estimation     ۴- Backward motion estimation

۵- Feature                                     ۶- Intensity

۲۵

تخمین حرکت رو به عقب

تخمین حرکت رو به جلو

فریم مبداء

فریم هدف

شکل ٣-۵: نمایش تخمین حرکت رو به جلو و رو به عقب [١]

روشهای مبتنی بر شدت روشنایی، از فرض روشنایی ثابت یا معادله شار نوری درهـر پیکـسل

استفاده میکنند و حرکت را براساس ارضاء این معادله (تا جایی که ممکن است ) تخمین میزنند.

این روش زمانی که حرکت نمیتواند به صورت یک مدل ساده بیان شده و مـشخص گـردد و

تخمین میدان حرکت پیکسل یا بلوک مورد نیاز میباشد، بسیار مناسب است .

روشهایی که درادامه بیان میشـوند، همگـی مبتنـی بـر روشـنایی بـوده و دارای کاربردهـای گسترده ای در پیش بینی وجبران حرکت هستند. به طور کلی، مسأله تخمـین حرکـت بـر اسـاس شدت روشنایی    میتواند به یک مسأله بهینه سازی که در آن سه پرسش کلیدی باید پاسـخ داده

شوند تبدیل شود:

١)     چگونه میدان حرکت را پارامتری کنیم ؟

٢)     چه معیاری را برای تخمین پارامترها استفاده کنیم ؟

٣)     چگونه پارامترهای بهینه را جستجو کنیم ؟

در این قسمت ، نخست چندین روش برای بیان یک میـدان حرکـت توضـیح داده مـیشـود و سپس معیارهای مختلف تخمین معرفی شده و در نهایت استراتژیهای جستجویی کـه عمـدتاً بـرای تخمین حرکت بکار میروند بیان میشود.

٣-۶) نمایش حرکت

یک مسأله کلیدی درتخمین حرکت ، نحوه پارامتری کردن میدان حرکت است . میدان حرکت

دو بعدی ناشی از حرکت یک شئ یا حرکت دوربین را معمـولاً مـیتـوان بـا چنـد پـارامتر محـدود

۲۶

مشخص کرد و یک نمایش حرکت سرتاسری ٢١ را برای مشخص کردن میدان حرکت بکار بـرد. امـا این روش ، زمانی کارایی دارد که تنها دوربین در حال حرکت است و یـا صـحنۀ تـصویر شـده تنهـا شامل یک شئ متحرک مسطح میباشد.

ولی از آنجا که معمولاً چندین شئ متحرک کـه دارای حرکتهـای مختلفـی هـستند در یـک صحنۀ تصویر شده وجود دارند، لذا تنها استفاده از مدل پارامتری سرتاسری در اغلب مواقع مناسـب نیست . در واقع ساده ترین روش که هیچ محدودیتی ندارد، تخصیص یک بردار حرکت به هر پیکسل است . به این روش ، بازنمایی حرکت براساس پیکسل ٢٢ گفته میشود. این روش قابل کـاربرد اسـت ، ولی نیاز به تخمین تعداد مجهولهای زیادی به اندازه دو برابر تعداد پیکسلها برای تخمین حرکت در دو جهت x وy دارد.

به طور کلی، برای صحنه های شامل چندین شئ متحرک، بهتر اسـت یـک فـریم تـصویر بـه چندین ناحیه تقسیم شود، به گونه ای که حرکت در داخل هر ناحیه را بتوان به خوبی از طریق یک مدل پارامتری مشخص کرد. این روش تحت عنوان بازنمایی حرکت بر پایۀ ناحیه ٢٣ شناخته میشود و شامل یک الگوی ناحیه بندی٢۴ و چندین مجموعه پارامترهای حرکت که هر کدام به یـک ناحیـه تخصیص دارند میباشد. مشکل یک چنین روشی این است که شخص هیچ اطلاعی از اینکه تعدادی از پیکسلها دارای حرکت مشابهی هستند ندارد. لذا ناحیه بندی و تخمین حرکت در هر ناحیه بایـد به طور متوالی انجام شود که نیاز به محاسبات زیادی دارد و ممکن است در عمل مطلوب نباشد.

یک راه حل برای کاهش پیچیدگی محاسبات روش فوق ، استفاده از یک الگوی ناحیـه بنـدی ثابت است که تصویر را به تعدادی زیادی بلوک کوچک تقسیم میکند، به گونه ای که هر بلوک بـه اندازه کافی کوچک بوده و حرکت در داخل هر بلوک را میتوان به خوبی با یک مدل ساده توصـیف کرد و پارامترهای حرکت را به طور مستقل تخمین زد. این روش تحت عنوان بازنمایی حرکت برپایۀ بلوک ٢۵ شناخته     میشود. ساده ترین مدل حرکت در هر بلوک، یک انتقال ثابت است به گونه ای که مساله تخمین حرکت به یافتن یک بردار حرکت برای هر بلوک محدود میشود. از آنجا که ایـن روش سادگی و دقت قابل قبولی به دنبال دارد، در سیستمهای ویدیویی موفقیت زیادی کسب کرده است .یک مشکل مهم این روش ، عدم تحمیل تمهیدات لازم بر روی بردارهای حرکـت تخمـین زده شده در بلوکهای مجاور است . لذا حرکت شناسایی شده با این روش اغلب دارای عدم پیوسـتگی در مرزهای بلوکها، حتی در مواقعی که میدان حرکت به طور یکنواخت از بلوکی به بلوک دیگـر تغییـر کرده است   میباشد. روش بلوک، روی نواحی داخلی یک شئ که معمولاً دارای حرکت پیوسته ای هستند بسیار مناسب است . ولی برای شناسایی حرکتهای ناپیوسته در مرزهای شـئ از کـارائی لازم برخوردار نیست .

۱- Global motion representation                            ۲- Pixel based representation

۳- Region based motion representation                                             ۴- Segmentation

۵- Block based representation

۲۷

راه حل فائق آمدن بر این مشکل ، استفاده از روش بازنمایی حرکت بر پایـۀ مـش ٢۶ اسـت . در این روش ، فریم تصویر به نواحی فاقد همپوشانی تقسیم میشود و میدان حرکـت روی کـل تـصویر تنها با استفاده از بردارهای حرکت در نقاط گوشۀ نواحی مختلف که اصطلاحاً بـه آنهـا گریـد گفتـه میشود توصیف میگردد. در این روش بردارهای حرکت نقاط داخلی هر ناحیه از بردارهای حرکـت نقاط گوشه مجزا    میشوند. حاصل این روش ، میدان حرکتی است که همه جا پیوسته میباشد.

شکل ٣-۶ عملکرد روشهای فوق بر روی یک تصویر شامل سر و شانۀ یک انسان را نشان می- دهد. شکلهای (الف )، (ب )، (ج ) و (د) به ترتیب نمایشهای حرکت سرتاسری، پیکسل ، بلوک و ناحیه هستند.

(الف )                                    (ب )

(ج )                                          (د)

شکل ٣-۶: انواع نمایشهای حرکت بر روی یک تصویر شامل سر و شانۀ یک انسان

(الف ) سرتاسری (ب ) پیکسل (ج ) بلوک (د) ناحیه [١]

٣-٧) معیار تخمین حرکت مسأله اساسی برای یـک مـدل حرکـت انتخـاب شـده، نحـوه تخمـین پارامترهای مدل است . در این قسمت ، چندین معیار مختلف برای تخمین پارامترهـای حرکـت بیـان می شود.متداول ترین معیار تخمین حرکت ، تفاضل مقادیر روشنایی هر جفت نقطه متناسب در فـریم مبدأ ψ و فریم هدف ψ است . یادآوری می شود که نقطه  xدر فریم ψ به  ( w)x;a د ψ حرکت

۲                                                                   ۱                                                                                                                      ۲                                     ۱

می کند. بنابراین تابع ویژگی می تواند به صورت زیر نوشته شود:

(  )                                                                                (  (  ;  ))          (  ) p                                      (۹-۳)

EDFD a = Σx∈Λ ψ۲  w x a −ψ۱  x

۱- mesh based representation

۲۸

در رابطه بالا، Λ مجموعه همه پیکسلهای فریم ψ و p یک عدد مثبت است . اگر ١= p باشد،

۱

تابع خطای فوق ، متوسط قدر مطلق تفاضل ٢٧ و اگر ٢= p باشد، متوسط مربعـات تفاضـل ٢٨ نامیـده میشود. تصویر خطا یعنی ( )ψ (a ;w  )ψ =a  ;e   معمولاً فریم جابـه جـایی٢٩ و یـا تـصویر

−

۲                                                                                                                      ۱

تفاضلی ٣٠ نامیده شده و اندازه خطای DFD31 را بـه تـصویر مـیکـشد. شـرط لازم بـرای مینـیمم کردن E، صفر قراردادن گرادیان آن نسبت به a است .

DFD

٣-٨) معیار برپایه معادله شار نوری

علاوه بر روش مینیمم کردن خطای DFD، روش دیگر حل مجموعه معادلات بیـان شـده در

رابطه ٣-٧ یعنی معادلۀ شار نوری است .

اگر (x, y(  ψ)x, y,t)ψ  و (x, y,t+d)         (x, y)ψ  باشـد و همچنـین d نیزکوچـک باشـد،

t                                                                                                                  ۲                    =ψ      t               ۱              =

میتوان فرض کرد که (  )           (  )  t dt∂ψ. ∂) است . لذا معادله شار نوری را میتوان به صورت

=ψ۲    x −ψ۱   x

زیر بازنویسی کرد:

∂ψ ∂ψ                                                                                          (۱۰-۳)

∂۱dx + ∂y1dy+(ψ۲ −ψ۱) =۰

x

معادله شار نوری فوق اغلب برای تخمین حرکت در ویدیوی دیجیتال بکار میرود. حل معادله

بالا برای همه نقاط x میتواند به یک مسأله مینیمم سازی با تابع ویژگی زیر تبدیل شود [١]:

(  )                                                                (            (  ) )T     (  )  (  )                                      (۱۱-۳)

P

Eof a = Σx∈Λ ∇ψ x  d(x  ) +ψ۲ x −ψ۱  x

در این حالت نیز مانند حالت قبل ، شرط مینیمم کردن E، صفر قراردادن گرادیان آن نسبت

of

به  a است که در آن میتوان شرایط ثابت بودن میـدان حرکـت در یـک ناحیـۀ کوچـک و یـا در صورتی که حرکت ثابت نیست ولی میتواند به صورت یک مدل پـارامتری خطـی توصـیف شـود را منظور کرد.اگر پارامترهای حرکت به طور خطی به بردارهـای حرکـت نـسبت داده شـوند، مینـیمم سازی Eمنجر به یک مینیمم یکتا شده و حل ساده ای خواهد داشت ؛ در صورتی کـه ایـن حالـت

of

برای E وجود ندارد. اما در هر حال معادله شار نوری تنها زمانی کـه حرکـت کوچـک اسـت و یـا

DFD

زمانی که یک تخمین ابتدایی حرکت      ~  نزدیک به حرکت واقعی میتواند یافت شود و براسـاس

(d ( ))

آن (ψ)x به ((x)x d~)

بازیابی شود، صحیح است . در صورتی که این حالات وجود نداشته باشـد

ψ۲ +                                         ۲

بهتر است از معیار DFD استفاده گردد.

۱- Mean absolute difference(MAD)                                                         ۲- Mean squared difference(MSD)

۳- Displaced frame                                                                                                             ۴- difference image

۵- Displaced frame difference

۲۹

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

یک ویژگی میدان حرکت این است که به جز در مرزهای اشیاء معمولاً بـه طـور یکنواخـت از پیکسلی به پیکسل دیگر تغییر میکند. برای منظور کردن ایـن اثـر یکنـواختی مـیتـوان از انـدازه اختلاف بین بردارهای حرکت پیکسلهای مجاور در یک همسایگی چهار یـا هـشت پیکـسل x بـه

صورت رابطه زیر استفاده کرد:

(  )                                                                                                         d (x  )  d ( y  )۲                                                      (۱۲-۳)

E a =Σ ∈ΛΣ ∈Λ     −

s                                                                                                                                                       x   y

بنابراین با توجه به مطالب بالا، میتوان معیار مینیمم کلی را به صورت زیر بیان کرد:

E E wE                                                                            (۱۳-۳)

=   +

DFD                                                                                                                                                                                                                                                                                                                                                                                                                         s s

ضریب وزن  w براساس میزان اهمیت یکنواختی حرکت و متناسب با مقدار خطا انتخـاب

s

میشود. برای اجتناب از بلورشدن در مرزهای شئ، بایـد ضـریب وزن را در مرزهـا کـاهش داد کـه چنین عملی مستلزم شناسایی دقیق مرزهای شئ است ، این در حالی است کـه شناسـایی مرزهـای شئ عمل  ساده ای نیست .

٣-٩ )معیار Bayesian

این معیار تخمین که براساس یک فرمول احتمالی [۴ ۵] میباشد، برای یک فریم تصویر ψ

۱

، دو میدان تصادفی   وD در نظر گرفته و ψ را به عنـوان یـک مقـدار در میـدان تـصادفی  و

ψ                                                                                                                        ۲                                                ψ

همچنین d را به عنوان یک مقدار در میدان تصادفی D منظور میکنـد. براسـاس قـانون Bayes ،

توزیع احتمال میدان حرکت D را نسبت به ψ و ψ میتوان به صورت زیر بیان کرد:

۱

۳۰

P(ψ =ψ ۲|D=d;ψ۱) P(D=d;ψ۱)                               (۱۴-۳)

P(D=d|ψ =ψ ۲;ψ۱)=                                                                                                    P(          ;   )

ψ =ψ۲ ψ۱

معیار تخمین Bayesian ، در جستجوی یک مقدار d برای ماکزیمم کردن احتمال بیان شده

در رابطه ٣-١۴ است .

٣-١٠) تخمین حرکت بر پایه پیکسل

در روش تخمین حرکت بر پایه پیکسل ، برای هر پیکسل یک بردار حرکت تخمـین زده مـی- شود. اما واضح است که این روش به درستی تعریف نشده است ؛ زیرا اگر یک پیکسل خاص در نظـر گرفته شده و از فرض شدت روشنایی ثابت برای هر پیکـسل در فـریم مبـدأ اسـتفاده شـود، تعـداد زیادی پیکسل در فریم هدف وجود دارند که دقیقاً شدت روشنایی یکسانی با پیکسل مربوطه دارنـد و اگر از معادله شار نوری استفاده شود، هنوز مشکل باقی اسـت ، زیـرا بـرای دو مجهـول تنهـا یـک

معادله وجود دارد. برای حل این مشکل ، به طور کلی چهار راه حل وجود دارد [١]:

١) میتوان از تکنیکهای یکنواخت سازی روی میدان حرکت استفاده کـرد، بـه گونـه ای کـه میدان حرکت یک پیکسل جدید متأثر از بردارهای حرکت یافت شده بـرای پیکـسلهای اطـراف آن باشد.

٢) میتوان فرض کرد که بردارهای حرکت در یـک همـسایگی اطـراف هـر پیکـسل یکـسان

هستند و فرض شدت روشنایی ثابت و یا معادله شار نوری را روی کل همسایگی بکار برد [۶].

٣) استفاده از تمهیدات اضافی علاوه بر فرض شدت روشنایی ثابت ؛ مثلاً استفاده از این فـرض

که گرادیان شدت روشنایی در حین حرکت ثابت و بدون تغییر است [٧،٨،٩،١٠].

۴) استفاده از تناسب بین توابع فاز فریم در قبل و بعد از حرکت [٧] .

٣-١١) الگوریتم تطبیق بلوک

مشاهده شدکه یک راه حل برای مشکل تخمین حرکت بر پایـه پیکـسل ، تحمیـل تمهیـدات یکنواختی است . یک روش تحمیل تمهیدات یکنواختی روی میدان حرکت تخمینی، تقـسیم حـوزه تصویر به نواحی کوچک بدون همپوشانی به نام بلوک است و با ایـن فـرض کـه میـدان حرکـت در داخل هر بلوک میتواند بوسیله یک مدل پارامتری ساده برای مثال مدل انتقال ثابت ، مـدل affine

و یا مدل bilinear بیان شود. اگر بلوکها به اندازه کافی کوچک باشند، ایـن روش مـیتوانـد کـاملاً دقیق باشد. دراین قسمت ، الگوریتمهای تخمین حرکت که از نمایش حرکت بر پایه بلـوک اسـتفاده میکنند توضیح داده میشوند.

اگر B نشان دهنده mُ امین بلوک تصویر و M تعـداد بلوکهـا باشـد و {M,…,1,2}=m،آنگـاه

m

بلوکها باید در شرط زیر صدق کنند:

۳۱

(٣-١۵)                                   n= m , ∅=B  B              و

Bm=Λ                                                                                                  m     n

m∈M

یادآوری میشود که Λ نشان دهنده کل پیکسلهای فریم مربوطه است . به طور تئـوری، یـک

بلوک میتواند دارای هر شکلی باشد. ولی در عمل ، از شکلهای مربعی یا مثلثی اسـتفاده مـیشـود.

مخصوصاً زمانی که حرکت در هر بلوک بوسیله یک مدل affine بیان میشود، شکل مثلثـی بـسیار مناسب است .

در ساده ترین حالت ، فرض میشود حرکت در هر بلوک ثابت باشد، یعنـی کـل بلـوک بـدون تغییر شکل فقط دارای یک حرکت انتقالی است . بنابراین مشکل تخمین حرکت ، به یافتن یک بردار حرکت منفرد برای هر بلوک محدود میشود. این نوع الگوریتمهـا بـه طـور کلـی الگـوریتم تطبیـق بلوک ٣٢ نامیده   میشوند. در قسمت بعد، حالت کلی تر که حرکت درهر بلوک بوسـیله یـک مـدل پیچیده تر بیان میشود در نظرگرفته میشود.

یک بلوک Bدر فریم مبـدأ داده شـده اسـت ، مـشکل تخمـین حرکـت ، تعیـین یـک بلـوک

m

تطبیقی ′ در فریم هدف است ؛ چنانچه خطا بین این دو بلوک مینیمم شود. بردار جابه جایی

dm                                                                                              B m

بین مکانهای فضایی این دو بلوک (مکان بلوکها میتواند بوسیله مرکز یا یـک گوشـۀ انتخـاب شـده بلوکها مشخص شود) بردار حرکت بلوک Bاست .

m

تحت مدل انتقالی فوق یا همان مدل حرکت ثابت ، B∋d x + =a  ;w   اسـت و خطـا بـین دو

x                                                                                    ,

m      m

بلوک میتواند به صورت زیر بیان شود:

E (d ,∀m∈M)    Σ  Σ     (x + d )                  (  ) P                            (۱۶-۳)

m                                                                                                      = m∈M x∈B ψ۲                  m −ψ۱  x

m

d m بهینه برای یک بلوک Bm در فریم مبدأ، بوسیله مقایسه آن با همه بلوکهای کاندیـد B′m

در فریم هدف و در داخل یک ناحیه جستجوی پیش بینی شده و سپس محاسبه خطـا و در نهایـت یافتن بلوک صحیح با مینیمم خطا، تعیین می شود. d یعنی جابه جایی بین دو بلوک، بردار حرکت

m

بلوک B میباشد. شکل ٣-٧ این روند را نشان میدهد.

m

فریم هدف

فریم مبداء

شکل ٣-٧: نحوه اجرای الگوریتم تطبیق بلوک[١]

۱- Exhaustive Block- Matching Algorithm; EBMA

۳۲

٣-١٢) الگوریتمهای جستجوی سریع

واضح است که الگوریتم تطبیق بلوک که در بالا توضیح داده شد، نیـاز بـه محاسـبات زیـادی

دارد. برای مثال ، در یک ناحیۀ جستجوی R ± و با گامهای به انـدازه یـک پیکـسل ، تعدادکاندیـدها

٢(١+ R ٢) است که نشان دهنده حجم بالای محاسبات میباشـد. کلیـد کـاهش محاسـبات ، کـاهش تعداد کاندیدها است که برای میسر شدن این امر و برای سرعت بخشیدن به جستجو، الگوریتمهـای جستجوی سریع متعددی برای تطبیق بلوکها پدیـد آمـده انـد. در ادامـه ، بـه توضـیح دو نمونـه از مهمترین الگوریتمهای جستجوی سریع پرداخته میشود.

٣-١٣) روش جستجوی D-log-2

یک الگوریتم جستجوی سریع ، الگوریتم D-log-2 [١١] مطابق شکل ٣-٨ است . این الگوریتم ، جستجو را با مکانی با جابه جایی صفر شروع کرده و در هر مرحله ، پنج نقطه را بررسی و تست می – کند. در مرحله بعد، جستجو با مرکز حرکت داده شده به بهترین نقطۀ منطبق بدست آمده از مرحله قبل تکرار میشود. اندازه گامهای جستجو در مراحل مختلف ثابت باقی میمانند، مگر اینکه بهترین نقطۀ تطبیقی، نقطۀ مرکزی پنج نقطۀ بررسی شده باشـد و یـا مکـان جـستجودر مـاکزیمم شـعاع جستجو قرار داشته باشد که در این حالت اندازه گامها کاهش مییابد. از طرف دیگر مرحلـۀ نهـایی زمانی است که گام جستجو، به یک پیکسل کاهش یابد که در این مرحلـۀ آخـر، ٩ نقطـۀ جـستجو مورد بررسی قرار میگیرند. اندازه گام ابتدایی را معمولاً نصف ماکزیمم شعاع جستجو قرار میدهند.

عیب این روش این است که نمیتوان تعداد مراحل و به تبع تعداد کل نقاطی کـه بررسـی خواهنـد شد را از قبل تعیین کرد.

شکل ٣-٨: نحوه اجرای روش جستجویD-log-2 [١]

۳۳

٣-١۴) روش جستجوی سه گام

یک الگوریتم جستجوی سریع دیگر، الگوریتم سـه گـام [١٢] مطـابق شـکل ٣-٩ اسـت . ایـن الگوریتم ، جستجوی را با اندازه گام برابر یا بزرگتر از نصف ماکزیمم شعاع جستجو شروع کـرده و در این مرحله ٩ نقطه را تست و مقایسه میکند. اندازه گام جستجو بعد از هر مرحله نصف مـیشـود و جستجو با اندازه گام یک پیکسل خاتمه مییابد. در هر مرحله جدید، مرکز جستجو به بهترین نقطه تطبیقی بدست آمده از مرحلۀ قبل حرکت داده میشود. به جز مرحله اول که ٩ نقطه بررسی مـی- شود، در مراحل بعدی هشت نقطه مورد بررسی قرار میگیرند. لذا کـل تعـداد نقـاط بررسـی شـده

١+ ۸L است که L تعداد مراحل بوده و به اندازه گام جستجوی ابتدایی بستگی دارد. برخلاف روش جستجوی D-log-2 ، در روش سه گام تعداد مراحل و تعداد نقاطی که بررسی خواهند شد از قبـل قابل پیش بینی است . بـه عـلاوه ایـن روش سـاختار مـنظم تـری نـسبت بـه روش  D-log-2 دارد.

همچنین برای مثال با یک رنج جستجوی ٣٢= R و با روش تطبیـق بلـوک، تعـداد نقـاط جـستجو

۴٢٢۵ است ، در حالی که با روش سه گام ، تعداد نقاط به ۴١ کاهش مییابد. ایـن مشخـصات باعـث شده است روش سه گام ، از نظر الگوریتمهای جستجوی سریع و همچنین از نظر پیاده سازی VLSI

بیشتر مورد توجه قرار گیرد.

شکل ٣-٩: نحوه اجرای روش جستجوی سه گام [١]

٣-١۵) مقایسۀ الگوریتمهای جستجو

جدول ٣-١، تعداد مراحل جستجو و مینیمم و ماکزیمم تعداد نقاطی که باید بررسی شوند را در سه الگوریتم جستجوی مختلف که در قسمتهای قبل توضیح داده شدند و برای رنج جستجوی    نـشان میدهد. مشاهده میشود که در روش جستجوی معمولی استفاده شده در الگوریتم تطبیـق بلـوک، باید ٢٢۵ نقطه بررسی شود که این حجم بالای محاسبات را نشان میدهد. در صورتی که تعداد این نقاط در روش جستجوی D-log-2 به ماکزیمم ٢۶ نقطه و در روش جستجوی سه گام به ٢۵ نقطه کاهش مییابد. تفاوت دیگری که در جدول ٣-١ مشهود میباشد این است که تعداد نقـاط بررسـی شده و تعداد مراحل در روش سه گام ثابت و قابل پیش بینی است ، در حالی که در مـورد روش -٢ D-log چنین نیست .

۳۴

:انجام پروژه متلبجدول ٣-١: مقایسۀ عملکرد سه روش جستجوی تطبیق بلوک، D-log- و سه گام

روش                                      تعداد نقاط جستجو                    تعداد مراحل جستجو

ماکزیمم                                                               مینیمم              ماکزیمم            مینیمم

لگاریتمی دوبعدی                            ۱۳                 ۲۶                  ۲                 ۸

سه گام                                             ۲۵                 ۲۵                 ۳                  ۳

سه گام قابل پیش بینی                          ۲۲۵               ۲۲۵                 ۱                  ۱

۳۳

٣-١۶) الگوریتمهای تطبیق بلوک تغییر پذیر

در الگوریتم تطبیق بلوک که در قسمت قبل توضیح داده شد، فرض شده است که هـر بلـوک فقط دارای یک حرکت انتقالی و بدون هیچ تغییر شکلی باشد. اما این مدل برای بلوکهایی که دارای حالت چرخش ، زوم و غیره هستند مناسب نیست . لـذا بایـد مـدلهای حرکـت مناسـب تـری ماننـد

Bilinear ،Affine  و یا projective mapping برای تشریح حرکت هر بلوک استفاده شود. البتـه واضح است که این مدلهای حرکت ، مدل حرکت انتقالی را نیز به عنوان یک حالـت خـاص پوشـش میدهند. بااین مدلها، یک بلوک مربعی در فریم مبدأ مطابق شکل ٣-١٠ به یک چهـار ضـلعی غیـر مربعی در فریم هدف متناظر میشود. بنابراین ، دسته ای از روشهای تخمین حرکت بر پایۀ بلوک را که از مدلهای درجه بالاتر استفاده میکنند، الگوریتمهای تطبیق بلوک تغییر پذیر مینامند [١٣].

شکل ٣-١٠: عملکرد الگوریتم تطبیق بلوک تغییر پذیر[١٣]

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

۱- Deformable block- matching algorithms , DBMA

۳۵

٣-١٧) مدل حرکت نقطه ای٣۴در این قسمت ، یک مدل حرکت نقطه ای [١٣] که میتوانـد بـرای مدل کردن حرکت یک بلوک استفاده شود و از لحاظ پیاده سازی نیز آسان تر میباشد توضیح داده میشود. در این مدل فرض میشود که نقاط کنترلی یعنی نقاط گوشۀ بلوکها   مـی تواننـد آزادانـه حرکت کنند و جابه جایی نقاط داخلی هر بلوک   میتواند بر حسب جابه جایی نقاط کنترلی بیـان شود. اگر تعداد نقاط کنترلی یک بلوک با k و بردارهای حرکـت نقـاط کنترلـی در بلـوک B بـا  d

m,k       m

نشان داده شود، آنگاه تابع حرکت روی بلوک B به صورت زیر بیان میشود:

m

d (x    ∑φ(x d  B                                                       (۱۷-۳)

K

=                                                                                                                                     ,x∈

m                                                                                                                                                                                            m,k                  m,k        m

k=1

۱-node based motion representation

۳۶

رابطۀ بالا، جابه جایی هر نقطه در یک بلوک را به عنوان یک تابع از جا به جایی نقاط کنترلی

آن بلوک مطابق شکل ٣-١١ بیان میکند.

توابع φ توابع کرنل هستند که میتوانند به صورتهای متفاوت بسته به توزیع k اُمـین نقطـه

m,k

کنترلی در بلوک B و با توجه به نقطه x تعریف شوند. یک روش بیان توابع کرنل ، استفاده از توابع

m

شکل است که در قسمتهای بعدی به توضیح آن پرداخته میشود. در واقع مدلهای حرکت انتقـالی، affine و bilinear  حالتهای خاصی از مدل حرکت نقطه ای با به ترتیب یـک ، سـه  و چهـار نقطـۀ کنترلی هستند. توابع کرنل در حالت یک نقطه ای (در مرکز بلوک یا یک گوشه انتخابی) یک تـابع پالس هستند. معمولاً برای استفاده از یک مدل affine با یک بلوک چهار ضلعی، ابتدا بلوک بـه دو مثلث تقسیم میشود وسپس هرمثلث بوسیلۀ سه نقطه مدل میشود.

شکل ٣-١١: نحوه جابه جایی یک نقطه داخلی یک بلوک به عنوان تابعی از

جا به جایی نقاط کنترلی آن بلوک در مدل حرکت نقطه ای[١٣]

٣-١٨) تخمین حرکت با استفاده از مدل نقطه ای

با مدل حرکت نقطه ای، پارامترهای حرکت برای هر بلـوک، بردارهـای حرکـت نقـاط گوشـۀ

بلوک هستند. این پارامترها میتوانند بوسیلۀ مینیمم کردن تابع خطای زیر روی هر بلوک تخمـین

زده شوند:

P

E (  )   Σ   (  (  ;  ))                                                               (  )                                                              (۱۸-۳)

a = x∈Bψ۲ w x a −ψ۱ x

w  ;a  =x +Σk Kφ (x)d                                                              (۱۹-۳)

∈ k     k

مشاهده میشود که حجم محاسبات کاملاً به روشی که برای مینیمم کردن تابع خطای فـوق

مورد استفاده قرار میگیرد بستگی دارد. روشهای متعددی برای این کار وجود دارد که بـرای مثـال

۳۷

میتوان به روشهای بر پایۀ گرادیان و یا روش Newton-Ralphson [١٣] اشاره کرد. مطلوبیت یک روش ، به حجم محاسبات و یا میزان پیچیده بودن محاسبات و همچنین امکان کـاربرد آن در عمـل مخصوصاً در کاربردهای بی در نگ بستگی دارد.

٣-١٩) تخمین حرکت بر پایه مش

در روش تخمین حرکت بر پایۀ بلوک، پارامترهای حرکت هر بلوک مـستقل از انـدازه بلوکهـا محاسبه شده و تخصیص داده میشود. به علاوه جز در حالتی که الزام میزان یکنواختی زیاد بر روی پارامترهای حرکت بلوکهای مجاور تحمیـل شـده باشـد، اغلـب میـدان حرکـت تخمـین زده شـده ناپیوسته و در بعضی مواقع کاملاً بی نظم و آشفته خواهد بودکه ایـن در شـکل ٣-١٢- الـف نـشان داده شده است . یک روش فائق آمدن بر این مشکل ، استفاده از روش تخمین مش است .

همانگونه که در شکل ٣-١٢- ب مشخص است ، فریم مبدأ کـاملاً بوسـیله یـک شـبکۀ مـش پوشانده شده است . مشکل تخمین حرکت به یافتن حرکت در نقاط گوشۀ سلولهای این شبکۀ مش مبدل میشود، به گونه ای که الگوی تصویر داخل هر سلول در فریم مبدأ به خوبی با سـلول تغییـر شکل داده متناسب با آن در فریم هدف منطبق میشود.

روش مش ، یک نمایش میدان حرکت پیوسته را تضمین میکند و لذا دیگر اثرات اغتـشاشات بلوک بندی که در روش بلوک وجود دارد را نخواهد داشت . مزیت دیگـر روش مـش ، امکـان دنبـال کردن پیوستۀ مجموعه ای از نقاط در فریمهای متوالی است که در کاربردهای ردیابی شئ مورد نیاز میباشد.

در روش مش ، نخست باید یک شبکۀ مش برای فریم اول ایجاد شود و سپس در مرحلۀ بعـد، حرکات نقاط گوشۀ سلولهای این شبکه بین هر دو فـریم متـوالی تخمـین زده شـود. در هـر فـریم جدید، مش ایجاد شده در مرحله قبل استفاده میشود یا به عبارت دیگر، روی کلیه فریمها مجموعه ای یکسان از نقاط دنبال میشوند. این امر برای روش بلوک امکان پـذیر نیـست ، زیـرا روش بلـوک مستلزم این است که هر فریم جدید مجددًا با یک مجموعه بلوک منظم ناحیه بندی و بلوک بنـدی شود.

(الف )

(ب )

شکل ٣-١٢: مقایسۀ عملکرد (الف ) روش بلوک و (ب ) روش مش [١۴]

۳۸

توجه کنید که پیوستگی ذاتی روش مش همواره مطلوب نیست . زیرا در دنباله های ویـدیویی واقعی، اغلب در مرزهای اشیاء، حرکت ناپیوسته میشود. در یک نمایش بسیار دقیق از حرکت ، باید سلولهای مش مجزا برای اشیاء مختلف استفاده شود. مشابه روش بلوک، دقـت روش مـش نیـز بـه تعداد نقاطی که حرکت در آنها تخمین زده میشود بستگی دارد. حتی یـک میـدان حرکـت بـسیار پیچیده را نیز میتوان با تعداد کافی نقطه مجددًا بازیابی کرد. برای مینیمم کردن تعداد نقاط مـورد نیاز، شبکۀ مش باید با صحنۀ تصویر شده وفق داده شود، به گونه ای که حرکت واقعی در داخل هر سلول شبکۀ مش یکنواخت باشد. اگر یک شبکۀ مش غیر وفقی بـرای یـک تـصویر اسـتفاده شـود، معمولاً برای تقریب زدن دقیق میدان حرکت ، تعداد نقاط زیادی مورد نیاز است . در ادامـه ، نخـست نحوه مشخص کردن یک میدان حرکت بـا اسـتفاده از روش مـش توضـیح داده مـیشـود و سـپس الگوریتمهایی برای تخمین حرکت نقاط در یک شبکۀ مش بیان میشود.

٣-٢٠) نمایش حرکت با روش مش

در نمایش حرکت با روش مش ، نخست سطح تصویر در فریم ابتدایی به نـواحی یـا سـلولهای بدون همپوشانی تقسیم میشود. هر سلول بوسیله چند نقطه و خط مطابق شکل ٣-١٣ تعریف می- شود. در این روش ، میدان حرکت روی کل سطح فریم ، تنها بوسیله بردارهای حرکت در نقاط گوشه سلولها مشخص میشود و بردارهای حرکت در نقاط داخلی یک سلول از بردارهای حرکت در نقـاط گوشه سلول مجزا   میشوند.

تعداد سلولها و تعداد نقاط به ترتیب با M و N و تعداد نقاطی که هر سلول را تعریف میکنند

با K نشان داده می شود. اگر mُ  امین سلول در فریم t {برای فریم مبدأ ١= t و برای فریم هدف ٢= t}

با B و n اُمین نقطه در فریم t با xt n و بردار حرکت در nُ امین نقطه با  x−x  =d  نـشان داده

n                                                                                                             ۲,n     ۱,n                                                                        ,                   t,m

شود، آنگاه میدان حرکت در  B بر حسب بردارهای حرکت نقطه ای  d به صورت زیر تعریف می –

n                                                                                                                                                                                              ۱,m

شود:

d (x  =Σ φ(x       B                                                    (۲۰-۳)

m                                                                                                                                                   k∈K m k    d ,x ∈

,                                                                                                                n(m,k)               ۱,m

(n)m,k اندیس نقطۀ k ام سلول m ام را نشان میدهد. تابع (φ)x تابع کرنل ٣۵ تخـصیص

m,k

داده شده به نقطه k در سلول m است . برای تضمین پیوستگی روی مرزهای سلول ، این توابع کرنل

باید دارای شرایط زیر باشند:

۰≤ φ (x ≤۱ ,Σkφm k(x  =۱ ,∀x ∈B1 m                                       (۲۱-۳)

m,k                                                                                                                                                                                                               ,

۱- Kernel function                                                                                                               ۲-shape function

۳۹

این توابع کرنل ،توابع شکل ٣۶ نیز نامیده میشوند [١۴]. اگر همه سـلولها دارای شـکل یکـسان

باشند، توابع شکل هم صرفنظر از شماره سلول یکسان خواهند بود یعنی (  )φ  (  )φ .

x =  x

m,k                                                                                                                                                                                                                        k

سلولهای سه ضلعی و چهار ضلعی استاندارد در شکل ٣-١٣ نشان داده شده اند. (توجه کنیـد که نحوه شماره گذاری نقاط گوشه سلولها در جهت مثلثاتی یـا خـلاف جهـت عقربـه هـای سـاعت است .)

شکل ٣-١٣: نحوه تغییر شکل سلولها و جابه جایی نقاط گوشۀ آنها

در یک شبکۀ مش در دو فریم متوالی[١۴]

(الف )                                          (ب )

شکل ٣-١۴ (الف ) سلولهای چهار ضلعی – (ب ) سه ضلعی استاندارد[١۴]

توابع شکل برای سلول مثلثی به صورت زیر هستند:

φ′ (x, y) = y               φ′ (x, y) = 1− x − y                                                        (۲۲-۳)

۲                                                                                                                                                                                                                ۳

φ (     )      δ ۱,k =l

φ′۱(x, y) = x                                                                                                                             m k xl = k,l=۰,k ≠l

,

۱-Kernel function

۴۰

واین توابع برای سلول مربعی به فرم زیر میباشند:

φq(x, y) = (1+ x)(1 −y).4                     φq(x, y) = (1+ x)(1 +y).4                            (۲۳-۳)

۱                                                                                                                                                                                           ۲

φ۴q(x, y) = (1− x)(1 −y).4                φ q (x     = (۱ −  )(۱ + y).4

۳

در [١۵] توابع شکل برای سلولهای مثلثی با شکل دلخواه نیز بیان شده اند. ضرایب این توابـع به مکان نقاط بستگی دارد.توجه کنید که نمایش حرکت در داخل هر سـلول براسـاس رابطـه ٣-٢٢ مشابه نمایش حرکت به روش نقطه ای براساس رابطه ٣-٢٣ است . با این تفاوت که در روش نقطـه ای بردارهای حرکت نقاط به طور مستقل از سلولی به سلول دیگر محاسبه میشوند، در صورتی کـه در روش مش چنین نیست .این نکته مهمی است ، زیـرا اگرچـه در مـدل نقطـه ای، چنـدین بلـوک همسایه ممکن است دارای نقطۀ مشترکی باشند، ولی بردارهای حرکت نقطـه ای در هـر بلـوک بـه طور مجزا و مستقل از بلوکهای مجاور تعیین میشوند.مجددًا به شکل ٣-١٣ توجه کنیـد، در مـدل مش ، نقطه n یک بردار حرکت منفرد را مشخص     میکند که بر توابع حرکت چهار سلول مربعـی متصل به این نقطه اثر خواهد گذاشت . در صورتی که در مـدل نقطـه ای، n مـیتوانـد چهـار بـردار حرکت متفاوت بسته به بلوکی که نقطه مورد نظر متعلق به آن در نظر گرفته میشود داشته باشد.

٣-٢١) تخمین حرکت با استفاده از مدل مش

در تخمین حرکت با روش مش ، دو مساله وجود دارد که باید حل شوند:

١) یک مش یا به طور معادل یک مجموعه نقطه در فریم مبدأ داده شده است ، چگونه مکـان

نقاط را در فریم هدف تعیین کنیم ؟

٢) چگونـه مـش را در فـریم مبـدأ قـراردهیم بـه گونـه ای کـه بـه مرزهـای اشـیاء محـدود

شود؟[١۶،١٧]

توجه کنید که یک ساختار مش که درآن هر سلول به یک قطعۀ مسطح و یکنواخـت در یـک شئ منفرد نسبت داده میشود، میتواند تخمین حرکت بسیاردقیقتری نسبت به یک سـاختار مـش اختیاری در پی داشته باشد. به عبارت دیگر، یک ساختار مش وفقی (با اشیاء) بـرای دنبـال کـردن حرکت در فریمهای متوالی بسیار مناسب تر است .مطابق با رابطه ٣-٢٢، در روش مـش ، پارامترهـای حرکت همان بردارهای حرکت نقطه ای هستند که باید تعیین گردند. برای تخمین ایـن پارامترهـا، مجددًا میتوان از یک روش مینیمم خطا استفاده کرد. با مدل مش ، تابع خطای DFD به فـرم زیـر

است :

E (  .n N)   Σ Σ     (  (  ))                                           (  ) P                                      (۲۴-۳)

d n ∈ =m∈M x∈B1,     ψ۲ wm x −ψ۱ x

m

۴۱

که درآن (x)  در واقع انتقال یافته نقطه  x در فریم هدف و به صورت زیر است :

wm

wm( x ) =x +Σk∈K φm k( x ) d                     ,x ∈B1,m                                       (۲۵-۳)

,                                                                                                                             n(m,k)

محاسبۀ تابع خطای فوق به دلیل شکل نا١م۴ظم سلولهای m B1 مشکل میباشد. بـرای سـادگی

محاسبات ، میتوان تصورکرد که سلول B (٢و١= t ) نخست مشابه یک سلول مرجع با شکل منظم

t,m

بوده است و سپس تغییر شکل داده است . به طور کلی، سلول مرجع ، برای سلولهای مختلف میتواند متفاوت باشد. ساده ترین حالت ، حالتی است که همۀ سلولها، دارای توپولوژی یکـسانی مـیباشـند، یعنـی همگـی  مـیتواننـد بـر یـک سـلول مرجـع یکـسان بـه نـام ~B منطبـق و متنـاظر شـوند.

شکل ٣-١۵ این انطباق رانشان میدهد [١].

شکل ٣-١۵: استفاده از یک سلول مرجع واحد برای دو سلول متناسب در دو فریم

متوالی[١۶]

در مطالب بالا به طور ضمنی فرض شده است که از قبل یـک سـاختار مـش روی کـل فـریم جاری ایجاد شده است (و یا در دنبال کردن حرکت از مرحله قبل وجود دارد) و هـر نقطـه در ایـن مش به یک و تنها یک نقطه در فریم هدف نسبت داده میشود، به گونه ای که نقاط در فریم هدف هنوز یک ساختار مش کامل که کل فریم هدف را میپوشاند ایجاد میکنند. اما ممکن است در یک صحنه ، اشیاء جدید آشکار شده و یا اشیایی که وجود داشته اند ناپدید شوند. برای ایـن حالـت بایـد نقاط متناسب با اشیاء ناپدید شده حذف شوند و برای اشیایی که جدیدًا آشکار شده اند نقاط جدیـد ایجاد شود [١٧].

٣-٢٢) تخمین حرکت بر پایه ناحیه

معمولاً چندین نوع حرکت مربوط به اشیاء مختلف در یک صحنۀ تصویر شده وجـود دارد. در تخمین حرکت بر پایه ناحیه ، فریم مبدأ به چندین ناحیه تقسیم بندی میشود و سپس پارامترهای حرکت هر ناحیه تخمین زده میشوند. تقسیم بندی تصویر باید به گونـه ای باشـد کـه یـک مـدل حرکت پارامتری منفرد، حرکت در هر ناحیه را به خوبی بیان کند. بنابراین در روش تخمین حرکت بر پایۀ ناحیه ، نکتۀ مهم و اساسی، نحوه ناحیه بندی و تقسیم بندی تصویر است .

۴۲

ساده ترین روش تقسیم بندی به صورتی است که هر ناحیه دارای یک حرکت انتقـالی سـاده باشد، ولی این امر باعث نواحی کوچک زیادی میشود؛ زیرا حرکت دو بعدی در یک ناحیۀ متناسب با یک شئ فیزیکی، ندرتاً بوسیله یک حرکت انتقالی ساده مدل میشود. بنابراین یک ناحیه بـه زیـر ناحیه های کوچک زیادی تقسیم میشود تا هر زیر ناحیه دارای یک حرکت انتقالی باشد.

برای یک نمایش حرکت موثرتر، مدلهای affine ،bilinear  و یا perspective باید استفاده شوند. برای تخمین حرکت بر پایه ناحیه ، روشـهای مختلفـی وجـود دارد. روش اول ایـن اسـت کـه نخست فریم تصویر به نواحی مختلف براساس بافت ساختاری تصویر، اطلاعات لبه ، یـا مـرز حرکـت بدست آمده از اختلاف بین دو فریم تصویر، تقسیم بندی شده و سپس حرکت در هر ناحیه تخمین زده میشود. یک روش دیگر این است که نخست میدان حرکت روی کل فریم تخمـین زده شـده و سپس میدان حرکت حاصل تقسیم بندی شود، به نحوی که هر ناحیه را بتـوان بوسـیله یـک مـدل حرکت پارامتری منفرد مدل کرد. براین اساس روش اول ، روش اول ـ ناحیـه و روش دوم ، روش اول ـ حرکت نیز نامیده میشوند [١]. روش سوم این است که تخمین حرکت و ناحیه بندی متعاقباً و با هم انجام شوند [١]. به عنوان نمونه شکل ٣-١۶ استفاده از روش ناحیه در بدن انسان را نشان مـی- دهد.

الف                                                                 ب

شکل ٣-١۶: استفاده از روش ناحیه در بدن انسان (الف )تصویر اصلی –(ب )اعمال روش ناحیه

۴۳

روشهای بیان شده برای جریان نوری و تفاوتهایشان  در جدول زیر آورده شده است .

جدول ٣-٢ نتایج مقایسه روشهای گفته شده را نشان میدهد.

مزایا                               معایب            مشخصات روش       پارامترمقایسه       روش

استفاده از چند پارامتر    تنها دور بین در حال    از پارامتر های محدود

حرکت باشد ویا فقط یک  برای حرکت سراسری      Global

محدود

شئ محرک باشد       شئ استفاده می شود

دقیق                                   تعداد مجهولات    برای هر پیکسل بردار در

ومعادلات زیاد     نظر گرفته می شود      Pixel Based

حرکت بخوبی مدل                                              از توابع : انتقال

محاسبات زیاد       ،چرخش ،زوم  استفاده   Region Based

می شود

می شود

محاسبات کاهش       عدم پیوستگی در مرز   تصویر به تعدادی بلوک   Block Based

می یابد

تقسیم می شود

٣-٢٣ جمع بندی

در این فصل روش شار نوری بعنـوان روش پیـشنهادی مطـرح شـد.ومعادلـه مربوطـه مطـرح

شد.روش پارامتری کردن میدان حرکت وانتخاب معیـار تخمـین وپـارامتر هـای بهینـه بیـان شـد.

روشهای دیگر تخمین حرکت برای مقایسه با روش شار نوری بیان شد ومشکلات هر کدام گفته شد.

روشهای تخمین حرکت به دو دستۀ اصلی روشهای مبتنی بر روشنایی و روشهای مبتنی بر ویژگـی تقسیم میشوند که در این فصل انواع روشهای تخمین حرکت مبتنی بر شدت روشـنایی بررسـی و توضیح داده شدند.

۴۴

فصل چهارم

نتایج تجربی

فصل چهارم

نتایج تجربی

۴-١) مقدمه

در این بخش روش ردیابی با استفاده از جریان نوری به علت عملکرد قابل توجه بالا در ردیابی اشیا به عنوان روش انتخابی مورد بررسی کامل قرار میگیرد. این روش از توزیع روشنایی در جهات مختلف    (زمانی- مکانی) استفاده می کند. برای حالتهای دوربین متحرک مناسب است . در بسیاری از کاربردها اعم از فشرده سازی- استخراج دقیق شی و ردیابی اشیاء در کاربردهای ویدیوئی مورد استفاده قرار میگیرد. روشهای مختلف را با هم مقایسه کرده مزایا ومعایب هر کدام از روشها بررسی خواهد.

۴۵

۴ ٢) پایگاه داده

روش های پیاده سازی شده بر روی تعدادی ویدئو است که در یک فضای آزاد گرفته شـده اسـت که درساعاتی از روز برداشته شده اند. اندازه تصاویر   ٣٢٠ x ٢۴٠است و نرخ تصویر برداری ٣٠ قاب در ثانیه است .  شکل ۴-١ چند نمونه از قاب های این ویدئو را نمایش میدهد تصاویر استفاده شـده برای کار با الگوریتم در فضای آزاد با روشنایی متناسب مـیباشـدکه بـرای برداشـت تـصویر از یـک دوربین با مدل (۲L-14-NWC)Dual Lens  استفاده شده است .

شکل ۴-١ الف و ب دو نمونه از قابهای گرفته شده در فضای آزاد

۴۶

۴-٣) روش جریان نوری

۱

در روش جریان نوری یک میدان برداری دو بعدی که ١تصویر  بردارهای واقعی شیء در سه بعد استخراج میشودکه به این میدان برداری، جریان نوری گفته می شود.در این روش فرض می – شود، که اشیاء متحرک در صفحه دارای حرکتهای مستقلی ازحرکت پس زمینه هستند.حرکت پس زمینه میتواند، در اثر حرکت دوربین ایجاد شود، با فرض حرکت کلی پس زمینه  یک مدل پارامتری برای آن استخراج میشود. با استفاده از این مدل پارامتری بردار حرکت معادل بر حسب حرکت کل٢ی پس زمینه در آن نقطه تخمین زده میشود. حال بامقایسه این بردار با جریان نوری در آن نقطه ، حرکت باقیمانده در آن نقطه محاسبه میشود. در صورتی که بردار حرکت جریان نوری با بردار به دست آمده ازحرکت کلی پس زمینه هم خوانی داشته باشد بدین معنی است که آن نقطه یا بلوک جزء پس زمینه میباشد و حرکت باقیمانده صفر خواهد بود، اما هرچه این همخوانی کمتر باشد، یا تفاوت بین دو بردار بیشتر باشد، نشان دهنده وجود شیء متحرک  مستقل از پس زمینه در آن نقطه یا بلوک٣خواهد بود، اگر نقاط یا بلوکهای دارای حرکت متفاوت با حرکت کلی پس زمینه هستند، را دسته بندی میکنیم . تصویر به دو دسته نقاط پس زمینه و نقاط پیش زمینه ، تقسیم خواهد شد. حال اگر فرض شود که تمامی بردارهای حرکت مربوط به یک شیء در یک جهت و راستا وتقریبا هم اندازه باشند یا به تعبیر دیگر شی دارای حرکت صلب باشد، میتوان با دسته بندی این بردارهای حرکت که دارای تشابه هستند، به تمام ناحیه شیء دسترسی پیدا کرد، یا در حقیقت میتوان گفت که شی متحرک را از بقیه جدا کرده ایم .اما در صورتی که شیء دارای حرکت صلب نباشد، یا به عبارت دیگر اجزای مختلف یک شیء دارای بردارهای مختلف حرکتی باشند، این دسته بندی بر اساس شباهت بردارها، منجر به جداسازی و تشخیص شی نخواهد شد درنتیجه فقط از معیار انحراف از حرکت پس زمینه برای تشخیص  نواحی متحرک میتوان استفاده کرد.

1. Projection
2. Global motion
3. Residual motion

۴۷

حال به تعریف ریاضی و مفهوم کلی میدان حرکت  جریان نوری و روش تخمین حرکت کلی خواهیم پرداخت .به منظور شفاف تر شدن واژه حرکت ابتدا به تعریف این ١ مفهوم با استفاده از شدت نور میپردازیم ، فرض کنید که        ( t,0 I)x , نمایان گر شدت نور در یک تصویر در نقطه  ,x)X= (y, z  در زمان حرکت که در حقیقت ، تصویر حرکت سه بعدی اشیا در مختصات واقعی میباشد را میتوان با یک میدان برداری به نام جریان نوری مدل کرد.

بردار ((q)x,y ,P)x,y() =d)a( جابجائی نقطه x مابین دو زمان t ∆+t  وt دو صفحه

تصویر را تعیین میکند، که نهایتا به تغییر  (t,I)  منجر میشود  (p)x,y و (x,y)q   مولفه های

بردار d میباشد، که خود تابعی عددی از مختصات نقطه میباشد.

بنابراین بردار تغییرات شدت نور (ddxt, ddyt ) =(y(,x )v  ,u)x,y()=U)x( را میتوان به عنوان سرعت نقطه x در لحظه t در نظر گرفت شکل  ۴-٢ یک نمونه از میدان حاصل از جریان نوری را نشان میدهد در عمل به منظور تخمین حرکت یا میدان برد٢اری جریان نوری از روشهای مختلفی استفاده میشود که از مهمترین آنها به روش kanade &Lucas  [١٩] و  Horn  schunck [١٠]  که به همراه تطبیق بلوکی [۴۵] استفاده میشود که در ادامه به بررسی هر کدام از آنها خواهیم پرداخت .

1. Intensit      ۲٫ Block matching

۴۸

شکل ۴-٢(ب ) نشان دهنده  میدان برداری حاصل از جریان نوری اعمال شده برروی شکل

۴-٢(الف )

معادله جریان نوری را در کلیه ابعاد و زمان به صورت زیر در نظر میگیریم .

(۱-۴)

I ( x y, z, t) = I ( x + δx, y + δy, z + δz, t + δt)

,

یعنی مقدار درخشندگی یک نقطه در فضا در کلیه ابعاد هندسی و زمان به میزان ناچیزی تغییرمی نماید. بنابراین به دلیل کوچک بودن تغییرات حول نقطه اولیه میتوانیم از بسط تیلور به صورت زیر استفاده کنیم .

I ( x + δx , y + δy , z + δz , t +δt)                           (۲-۴)

(    ,     ,    ,  )                                                                                    ∂Iδ  ∂Iδ  ∂Iδ  ∂Iδt  H .O .T

= I x y z t+    x+    y+    z+    +

x                                                                  ∂y         ∂z         ∂t

H.O.T  به معنای جملات با ضرائب بالاتر میباشد که قابل صرف نظر میباشد.

با در نظر گرفتن یکسان بودن نقطه جابجا شده مورد بررسی میتوان معادله فوق را به

صورت زیر ساده کرد.

∂Iδx +∂Iδy +∂Iδz +∂Iδt= 0                                           (۳-۴)

∂x    ∂y      z    ∂t

با تقسیم کلیه جملات بر  خواهیم داشت :

∂I∂x+∂Iδy+∂Iδz+∂Iδt= 0                                                (۴-۴)

∂xδt ∂yδt ∂tδt ∂tδt

در نتیجه معادله دیفرانسیل جریان نوری به صورت زیر خواهد بود:

۴۹

به این ترتیب مولفه های سرعت را به دست خواهیم آورد  در معادلات فوق نیاز به مشتقات

جزئی در جهات (x,y,z) برای درخشندگی تصویر خواهیم داشت که از طریق فیلترهای Sobel

جهت دار به دست خواهد آمد ولی درنهایت یک معادله و چند مجهول خواهیم داشت که حل آن ناممکن خواهد بود و از آن با عنوان Aperture Problem یاد میشود.

۴ ۴) مسئله Aperture

این مشکل ناشی از چند بعدی بودن سرعت در تصاویر میباشد  (در واقع کم بودن تعداد معادلات نسبت به مجهولات ) در حالی که تنها یک معادله  (۴-۴)  جهت حل کردن و به دست آوردن سرعت وجود دارد. [۴۶]

۴-۵) روشهای حل مسئله Aperture

١- روش Horn  shunk که به وسیله اعمال معادلات کمکی Smoothness عمل میکند.

[۱۰]

٢- روش Kanade &Lucas  که از طریق در نظر گرفتن Voxel واعمال least squares

عمل میکند. [١٩]

٣- روش Anandan که بااستفاده ازهم بستگی متقابل عمل میکند.[۴٧]

۴- روش Jepson &Fleet  که به وسیله محاسبه فاز بین دو فریم عمل میکند. [۴٨]

از بین روشهای فوق دو روش اول از نظر حجم پردازشی مناسبتر بوده و ما نیز به آنها اشاره خواهیم کرد ونیزروش kanade &Lucas  در پیاده سازی حجم پردازشی کمتری را نسبت به   Horn schunck بر روی پردازنده عمل   مینماید. در نتیجه در مراحل نهایی پیاده سازی نیز به کار گرفته می شود.روش سوم یعنی روش Anandan که بر پایه همبستگی متقابل میباشد، برای پیاده سازی بر روی سخت افزار از جمله FPGA مناسب میباشد زیرا از نظر پردازشی دارای پیچیدگی بسیار کمی بوده در حالی که حجم بسیار بالایی از پردازش موازی رانیاز دارد. کلیات این روش مقایسه فریم شیفت داده شده در جهات مختلف نسبت به فریم قبلی میباشد که این مقایسه به وسیله همبستگی انجام میپذیرد. روش آخر نیز برپایه فاز به دست آمده که از سرعت تک تک نقاط نسبت به همدیگر عمل کرده و به نوعی تعادل فاز بین فریم ها  موجب تشخیص حرکت خاص نسبت به سایر حرکات امکان پذیرخواهد شد.این روش برای استفاده در ردیابی مناسب نمیباشد، زیرا امکان ایجاد خطاها در آن بسیار زیاد خواهد بود.

۴ ۶) روش  Horn schunck

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

f = ∫((∇I.V + It )2 +α( ∇v  ۲ + ∇Vy2 +(∇vz )2))dxdydz                                         (۵-۴)

۵۰

که در آن Ix,Iy,Iz[T] =I ∇ مربوط به مشتقات جهتی درخشندگی درجهات اصلی کارتیزین سه

بعدی میباشد همچنین  مشتق جهتی حول زمان برای درخشندگی میباشد، از آنجائی که

دارای مولفه های vx,vy,vz بوده معادله فوق نیز با استفاده از روش Euler به صورت زیر تجزیه

خواهد شد:

(۶-۴)

∆VX − ۱ Ix(IxVx + IyVy + IzVz + It ) =0

α

(۷-۴)

∆Vy − ۱αIy(IxVx + IyVy + IzVz + It ) =0

∆Vz − ۱ Iz(IzVx + IyVy + IzVz + It )     ۰

=                                                                             (٨-۴)

α

که در معادلات فوق داریم :

∆VX= ∂∂x∂∂Vxx, ∆Vy=∂∂y∂∂Vyy,∆Vz=∂∂z∂∂Vzz            (٩-۴)

حال میتوان معادلات به دست آمده را با روش Gauss- Seidel به صورت زیر تبدیل نمود:

∆Vxk − ۱ Ix (IyVyk+ IZVzk+It)                                 (١٠-۴)

+          α

Vxk1   =                                                                                                ۱

Ix2

α

∆Vyk − ۱ I I Vk + I Vk +I                                       (١١-۴)

y ( x x                                                                                                                                                              Z z            t)

Vk+1                                α

y   =

۱ Iy2

α

∆Vzk − ۱ Iz (IxVxk+ IyVyk +It)                                 (١٢-۴)

Vzk+1                                α

=

۱ Iz2

α

۵۱

که در آن اندیس ۱+k مربوط به مشتقات جهتی فریم بعدی بوده و اندیس k مربوط به آخرین

فریم محاسبه شده (فریم حال ) میباشد. همچنین   را میتوان به صورت زیر نوشت .

∆Vi = N(P) (  ( ) −( ))                                                                (١٣-۴)

Vi N p Vi P

که در آن (N)P  مربوط به نقاط همسایه نقطه P میباشد اشکال این روش حجم پردازشی بالا در پیاده سازی   میباشد و در پیاده سازی واقعی نرخ فریم های پردازش شده پائینی را برای کاربرد ردیابی نشان میدهد.

۴-٧) روش Kanade &Lucas

در این روش برای حل مشکل کمبود تعداد معادلات نسبت به مجهولات در جریان نوری از مفهوم

Voxel که ترکیبی از کلمات Volume به معنای حجم و Pixel به معنای نقطه میباشداستفاده می شود در واقع مجموعه ای از نقاطی در تصویر در نظر گرفته میشوند که مربوط به یک حجم ثابت  (یک شی سه بعدی صلبی)  میباشد در نتیجه معادله را برای تک تک نقاط تشکیل دهنده حجم صلب مینویسیم و در کنار یکدیگر قرار میدهیم به این ترتیب برای حل مسئله تعداد زیادی معادله و چند مجهول خواهیم داشت که میتوان با روش Least Squares آن را حل نمود.

بنابراین ابتدا حجم m x m x m را که در آن         باشد را به صورت یک Voxel در نظر

میگیریم سپس معادله  جریان نوری را برای تک تک اجزای آن باز نویسی میکنیم [۴٩]

Ix Vx + Iy Vy + Iz Vx = −It                                (۱۴-۴)

۱                                                                                                                                                    ۱          ۱                     ۱

.                                                                                                                .       .         .

.                                                                                                                .       .         .

Ix 2Vx + Iy2Vy + Iz 2Vx = −It2                                           (۱۵-۴)

.         .       .         .

.         .     .       .

Ix Vx + IynVy + Iz Vz = −Itn

n                                                                                                                                   n                          (۱۶-۴)

۵۲

سپس معادلات راماتریسی و به صورت زیر باز نویسی میکنیم .

x                                                                                                                                                          y                                          z            It1

I 1                                                                                                                                                                                                          I 1                       I1

Ix                                                                                                            Iy 2                                  Iz2 VX−۲        (١٧-۴)

۲

.                                                                                     .                 y   =.

.                                                                                             .

z

Ixn                                                                                                                                                               Iyn                       Izn                         Itn

که در نهایت میتوانیم بگوییم :

AV = −b                                                                                                    (١٨-۴)

حال برای حل معادله فوق با استفاده از روش Least Squares عمل خواهیم کرد.

T         T

A AV = A (−b)

(۱۹-۴)

که بردار سرعت را میتوانیم به صورت زیر به دست آوریم .

V = ( A A) 1A (−b)                                                                     (٢٠-۴)

T   −  T

در نهایت به صورت زیر خواهیم نوشت .

∑I 2                                                                            ∑I  I               ∑I I 

Vx  Xi                                                                                                                                 Xi vi                                        Xi zi  −∑IXi Iti

Vy ∑I  I             ∑I2       ∑I I    −۱                                I I        (٢١-۴)

=   Xi yi                                                                                                  yi                                           yi zi                              yi ti

که در آن متiغItیرIziiاز ١ تا N که بt2راzبIر تعداد نقاط ziموجyوIد∑در یک IVXoxziel∑خواهد zبVود.

در شکل ۴-٣ نمونهای از اعمال روش  kanade &Lucas  نشان داده شده است .

۵۳

(الــف                                              (ب )

شکل ۴-٣(ب ) نمایش اعمال روش  Lucas& kanade را بروی شکل ۴-٣(الف ) نشان می دهد.

۴-٨) روش حل Least Squares

در این روش از نوعی رگرسیون خطی (Linear Regression) استفاده میشود. ابتدا تقریب زیر را در نظر  میگیریم .

F(x) ≈ y                                                                                                     (٢٢-۴)

بنابراین میتوانیم با در نظر گرفتن خطا تقریب معادله فوق را به صورت زیر در نظر بگیریم :

F(x) ≈ y + ε                                                                                           (٢٣-۴)

که در آن خطا از نوع تصادفی با میانگین صفر در نظر گرفته میشود:

:انجام پروژه متلب همچنین باید توجه داشت که چون مولفه های سرعت بین دو فریم مورد نظر بوده ، بنابراین تنها نیاز به رگرسیون خطی به صورت ε +βx  +α  =y  خواهیم داشت ، حال در صورت به دست آوردن مقادیر  و  میتوانیم مولفه های سرعت بین دو فریم را به دست آوریم . برای انجام این مهم

ماتریس زیر که شامل چندین معادله بر حسب  و  است را در نظر میگیریم . [۵٠]

 ۱                                                                                                       x1      ε۱ 

۲    =      ۲    +۲                                              (٢۴-۴)

y1

α

۳                                                                                                                                                                                                                   β  ۳

۳

n                                                                                                                                                                                                   ۴

حال مقادیر زیر را برحسب اعضای ماتریس فوق به دست میآوریم

۵۴

S = x + x +x +xn                                      (٢۶-۴)

x    ۱                                                                                                                                ۲      ۳    …

Sy = y1 + y2 + y3 +…yn                                                                    (٢٧-۴)

Sx = x2 + x2 + x3 +…xn                                                                (٢٨-۴)

x    ۱                                                                                                                                          ۲     ۳             n

sxy =x1y1+x2y2 +x3y3 +…xnyn                                         (٢٩-۴)

و در نتیجه مقادیر α و β را میتوانیم به صورت زیر به دست بیاوریم .

β

α= sy −sx                                                          β=nsxy −sxy              (٢٩-۴)

n                                                                                                                nsxt −sx sy

بنابراین میتوانیم مشکل کمبود تعداد معادلات نسبت به مجهولات را حل نمائیم . این روش از نظر پیاده سازی نیز مناسب بوده و با کمی تغییرات سرعت خوبی را در حل معادلات مورد نیاز و به دست آوردن سرعت بین دو فریم نشان داده است .

۴-٩ )مقایسه روشهای گفته شده

جدول ۴-١ نتایج مقایسه زمانی روشهای استفاده شده را نشان می دهد.

جدول ۴-١ مقایسه زمانی را نشان می دهد

روشها  Fleep&jepson Lucas Horn   Anandan

kanade  schunck

زمان اجرا      ٨:١٢         ۴:٠٠     ٠٠:٢٣                          ۳۰:۰۲

۵۵

۴-١٠ ) ابزار استفاده شده

در این قسمت ابزار استفاده شده برای پیاده سازی الگوریتم معرفی میشود  برای پیاده سازی روش های گوناگون از زبان ++c استفاده می شود. این زبان به این دلیل انتخاب شده که توانایی بالایی در تولید کد ماشین بهینه به منظور اجرای سریع برنامه ها دارد. این سامانه در محیط ++c Visual نوشته شده و کامپایل شده است . برای اجرا و آزمایش سامانه تمام برنامه بر روی یک کامپیوتر لپ تاپ با پردازنده Intel و مدل Pentium Dualcore با سرعت پردازش ٢.٢ گیگا هرتز بر ثانیه استفاده شده است . این کامپیوتر دارای حافظه RD و به حجم ١ گیگا بایت است .برای کار با ویدئو و تصاویر از ابزار ۳۷Open cv استفاده شده که دارای کتابخانه های قویای در زمینه بینایی ماشین و کار با ویدئو و تصاویر است .این ابزار در سیستم عاملهای ویندمز و لینوکس قابل استفاذه استفاده است .  در کاربردهای بی درنگ نیز قابل پیاده سازی است . تیمی حرفهای از شرکت اینتل در اواخر سال ١٩٩٩واوایل ٢٠٠٠ رسماَ این ابزار را معرفی کردند وهر سال نسخه جدیدتر آنرا در صورت ایجاد ارائه می شود.

علاوه بر  ++VC می توان در محیط ۵.۵ ++Borland c و ++Intel cبا x.5 compiler

و… استفاده کرد.

این ابزار کاربردهای بسیاری در پردازش تصویر دارد که از آن جمله می توان به تشخیص شئ،قطعه بندی و جداسازی،تشخیص صورت ،تشخیص حالت ،ردیابی حرکت ،ساختار حرکت ،حالت استریو و…

اشاره کرد.این محصول دارای چهار کتابخانه قوی در زمینه پردازش تصویر می باشدکه عبارتند از

شامل توابع جبر خطی می باشد.                                         Cv core

شامل توابع اصلی پردازش تصویر می باشد.

Cvشامل توابع فرعی می باشد.                                                    Cv aux

شامل توابع گرافیکی می باشد.                                                  High gui

از توابع موجود در این کتابخانه ها برای کار روی پیکسلها  (cv point) ،ماتریسها (cv mat)

،اندازه (cv size)رنگ (cv rgb) وانواع تبدیلات وفیلتر ها استفاده می شود.

استفاده از ابزار استفاده شده که در سالهای اخیر ارائه شده یکی از امتیازات در این پروژه می باشـد مخصوصآ زمانی که ردیابی بصورت بی درنگ انجام می شود،وجود توابع متعدد در این ابزار ، قـدرت انعطاف پذیری بالایی را فراهم نموده است که آن را در برابر ابزار دیگر همچون مطلب متمایز نـشان می دهد.

۴-١١) نتایج شبیه سازی

در این بخش نتایج شبیه سازی الگوریتم جریان نوری را بر روی تصاویر گرفته شده مشاهده می –

۱)Open computer vision 37

۵۶

کنیم ، همانطور که در شکل ۴-٢ نشان داده شده بردارهای حرکتی شی متحرک در جهات مختلف می باشد که این بردارها حرکت قسمتهای مختلف شی را دربرمیگیرد.

(الف )

(ب )

(ج )

شکل ۴-۴ الف -فریم ٣ وشکل ۴-٣ ب فریم ٧ وشکل ۴-٣ ج فریم ٢٧را نشان می دهد

۵۷

Start

Opening device

Capture

First  Yes                                                        Save

image              image

No

Convert to

gray scale

Get difference between frames

and thresholding

Update

MHI

Clear destination image

Select largest

component

Des lco>lcn                                                          yes Estimate

motion

No

Set ROI

Estimate

des

Optical

flow

۵۸

#ifdef _CH_

#pragma package <opencv>

#endif

#ifndef _EiC

.. motion templates sample code

#include “cv.h”

#include “highgui.h”

#include <time.h>

#include <math.h>

#include <ctype.h>

#include <stdio.h>

#include <stdlib.h>

#include <conio.h>

#endif

.. various tracking parameters (in seconds)

const double MHI_DURATION = 1;

const double MAX_TIME_DELTA = 0.5;

const double MIN_TIME_DELTA = 0.05;

int slider_pos = 70;

.. Load the source image. HighGUI use.

IplImage *image02 = 0, *image03 = 0, *image04 = 0;

.. Define trackbar callback functon. This function find contours,

.. draw it and approximate it by ellipses.

void process_image(int h)

{

CvMemStorage* stor;

CvSeq* cont;

CvBox2D32f* box;

CvPoint* PointArray;

CvPoint2D32f* PointArray2D32f;

.. Create dynamic structure and sequence.

stor = cvCreateMemStorage(0);

cont = cvCreateSeq(CV_SEQ_ELTYPE_POINT, sizeof(CvSeq), sizeof(CvPoint) ,

stor);

.. Threshold the source image. This needful for cvFindContours().

cvThreshold( image03, image02, slider_pos, 255, CV_THRESH_BINARY );

.. Find all contours.

cvFindContours( image02, stor, &cont, sizeof(CvContour),  CV_RETR_LIST,

CV_CHAIN_APPROX_NONE, cvPoint(0,0));

.. Clear images. IPL use.

cvZero(image02);

cvZero(image04);

۵٩

.. This cycle draw all contours and approximate it by ellipses.

for(;cont;cont = cont->h_next)

{

int i; .. Indicator of cycle.

int count = cont->total; .. This is number point in contour

CvPoint center;

CvSize size;

.. Number point must be more than or equal to 6 (for cvFitEllipse_32f).

if( count < 6 )

continue;

.. Alloc memory for contour point set.

PointArray = (CvPoint*)malloc( count*sizeof(CvPoint) );

PointArray2D32f= (CvPoint2D32f*)malloc( count*sizeof(CvPoint2D32f) );

.. Alloc memory for ellipse data.

box = (CvBox2D32f*)malloc(sizeof(CvBox2D32f));

.. Get contour point set.

cvCvtSeqToArray(cont, PointArray, CV_WHOLE_SEQ);

.. Convert CvPoint set to CvBox2D32f set.

for(i=0; i<count; i++)

{

PointArray2D32f[i].x = (float)PointArray[i].x;

PointArray2D32f[i].y = (float)PointArray[i].y;

}

.. Fits ellipse to current contour.

cvFitEllipse(PointArray2D32f, count, box);

.. Draw current contour.

cvDrawContours(image04,cont,CV_RGB(255,255,255),CV_RGB(255,255,255),0,1,8,

cvPoint(0,0));

.. Convert ellipse data from float to integer representation.

center.x = cvRound(box->center.x);

center.y = cvRound(box->center.y);

size.width = cvRound(box->size.width*0.5);

size.height = cvRound(box->size.height*0.5);

box->angle = -box->angle;

.. Draw ellipse.

cvEllipse(image04, center, size,

box->angle, 0, 360,

CV_RGB(0,0,255), 1, CV_AA, 0);

۶۰

.. Free memory.

free(PointArray);

free(PointArray2D32f);

free(box);

}

.. Show image. HighGUI use.

cvShowImage( “Result”, image04 );

}

int main( int argc, char** argv )

{

const char* filename = argc == 2 ? argv[1] : (char*)”lena.jpg”;

.. load image and force it to be grayscale

if( (image03 = cvLoadImage(filename, 0)) == 0 )

return -1;

.. Create the destination images

image02 = cvCloneImage( image03 );

image04 = cvCloneImage( image03 );

.. Create windows.

cvNamedWindow(“Source”, 1);

cvNamedWindow(“Result”, 1);

.. Show the image.

cvShowImage(“Source”, image03);

.. Create toolbars. HighGUI use.

cvCreateTrackbar( “Threshold”, “Result”, &slider_pos, 255, process_image );

process_image(0);

.. Wait for a key stroke; the same function arranges events processing

cvWaitKey(0);

cvReleaseImage(&image02);

cvReleaseImage(&image03);

cvDestroyWindow(“Source”);

cvDestroyWindow(“Result”);

return 0;

}

#include “cv.h”

#include “highgui.h”

۶١

int slider_pos = 70;

.. Load the source image. HighGUI use.

IplImage *image02 = 0, *image03 = 0, *image04 = 0;

.. Define trackbar callback functon. This function find contours,

.. draw it and approximate it by ellipses.

void process_image(int h)

{

CvMemStorage* stor;

CvSeq* cont;

CvBox2D32f* box;

CvPoint* PointArray;

CvPoint2D32f* PointArray2D32f;

.. Create dynamic structure and sequence.

stor = cvCreateMemStorage(0);

cont = cvCreateSeq(CV_SEQ_ELTYPE_POINT, sizeof(CvSeq), sizeof(CvPoint) ,

stor);

.. Threshold the source image. This needful for cvFindContours().

cvThreshold( image03, image02, slider_pos, 255, CV_THRESH_BINARY );

.. Find all contours.

cvFindContours( image02, stor, &cont, sizeof(CvContour),

CV_RETR_LIST, CV_CHAIN_APPROX_NONE, cvPoint(0,0))

.. Clear images. IPL use.

cvZero(image02);

cvZero(image04);

.. This cycle draw all contours and approximate it by ellipses.

for(;cont;cont = cont->h_next)

{

int i; .. Indicator of cycle.

int count = cont->total; .. This is number point in contour

CvPoint center;

CvSize size;

.. Number point must be more than or equal to 6 (for cvFitEllipse_32f).

if( count < 6 )

continue;

.. Alloc memory for contour point set.

PointArray = (CvPoint*)malloc( count*sizeof(CvPoint) );

PointArray2D32f= (CvPoint2D32f*)malloc( count*sizeof(CvPoint2D32f) );

.. Alloc memory for ellipse data.

box = (CvBox2D32f*)malloc(sizeof(CvBox2D32f));

.. Get contour point set.

۶٢

cvCvtSeqToArray(cont, PointArray, CV_WHOLE_SEQ);

.. Convert CvPoint set to CvBox2D32f set.

for(i=0; i<count; i++)

{

PointArray2D32f[i].x = (float)PointArray[i].x;

PointArray2D32f[i].y = (float)PointArray[i].y;

}

.. Fits ellipse to current contour.

cvFitEllipse(PointArray2D32f, count, box);

.. Draw current contour.

cvDrawContours(image04,cont,CV_RGB(255,255,255),CV_RGB(255,255,255),0,1,8,

cvPoint(0,0));

.. Convert ellipse data from float to integer representation.

center.x = cvRound(box->center.x);

center.y = cvRound(box->center.y);

size.width = cvRound(box->size.width*0.5);

size.height = cvRound(box->size.height*0.5);

box->angle = -box->angle;

.. Draw ellipse.

cvEllipse(image04, center, size,

box->angle, 0, 360,

CV_RGB(0,0,255), 1, CV_AA, 0);

.. Free memory.

free(PointArray);

free(PointArray2D32f);

free(box);

}

.. Show image. HighGUI use.

cvShowImage( “Result”, image04 );

}

int main( int argc, char** argv )

{

const char* filename = argc == 2 ? argv[1] : (char*)”lena.jpg”;

.. load image and force it to be grayscale

if( (image03 = cvLoadImage(filename, 0)) == 0 )

return -1;

.. Create the destination images

image02 = cvCloneImage( image03 );

image04 = cvCloneImage( image03 );

۶٣

.. Create windows.

cvNamedWindow(“Source”, 1);

cvNamedWindow(“Result”, 1);

.. Show the image.

cvShowImage(“Source”, image03);

.. Create toolbars. HighGUI use.

cvCreateTrackbar( “Threshold”, “Result”, &slider_pos, 255, process_image );

process_image(0);

.. Wait for a key stroke; the same function arranges events processing

cvWaitKey(0);

cvReleaseImage(&image02);

cvReleaseImage(&image03);

cvDestroyWindow(“Source”);

cvDestroyWindow(“Result”);

return 0;

}

۶۴

۴-١٢ )جمع بندی

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

روش روش kanade &Lucas  به سبب زمان پیاده سازی کمتر انتخاب شد.

۶۵

فصل پنجم

نتیجه گیری وپیشنهادات

فصل پنجم

۵-١ نتیجه گیری و پیشنهادات

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

از میان روشهای گفته شده روش جریان نوری در کاربردهای بی درنگ و مراقبتی بسیار مفید می باشد این روش که میتواند با کمک مکملهای خود (Kanade- Horn Shunk &Lucas )

از روشهای دیگر  بهتر عمل کند،ونیز در حالتی که دوربین متحرک است ویا پس زمینه متحرک بوده نتیجه بهتری داشته است تنها مشکل آن محاسبات زیاد در پیاده سازی میباشد، این روش هم برای اجسام صلب و هم برای اجسام غیر صلب قابل ارائه میباشد.ونیز پایداری مناسبی در برابر تغییر نور محیط دارد.

۵-٢ پیشنهادات

ایده استفاده از جریان نوری به ویژه در کاربردهای دوربین متحرک ایده بسیار مناسب میباشد.

امکان توسعه الگوریتم برای حالتهایی که امکان انسداد چند شی وجود دارد با استفاده از روشهای مانند لبه یابی هریس و نیز استفاده از تطبیق مرز در فریمهای مختلف وجود دارد.

در الگوریتم گفته شده اگر روشهای سیستماتیک انتخاب شئ و مکانیزم هائی مانند کلیک کردن بر روی تصویر برای تعیین ناحیه شئ مورد نظر در فریم اول استفاده شود نتایج حاصله برای شرایطی که روشنائی متغیر ویا روشنائی قدرت کافی ندارد می تواند موثر باشد.

برای حل مسئله انسداد می توان از الگوریتمهای مربوط به  Data Association استفاده نمود.

در تصاویری که چندین شئ وجود دارد اگر اشیاء مورد نظر از لحاظ ساختاری  (شکل -رنگ ) نزدیک به هم باشند الگوریتم های  Data Association  کارا می باشند.

از مهمترین این الگوریتم ها می توان روش  Jail  را نام برد ،در این روش  قبل از انسداد ویژگیهای مورد نظر اشیاء استخراج می شود وپس از انسداد بوسیله تطبیق این ویژگی ها  و انتخاب نزدیکترین جواب می توان شئ مورد نظر را از م۶یا۶ن  اشیاء دیگر شناسائی کرد.در صورتی که دو شئ برای مدت طولانی با یکدیگر  هم پوشانی  داشته باشند آن دو شئ تا مدت هم پوشانی بصورت یک شئ در نظر گرفته می شوند.

از طرفی اگر بخواهیم رفع هم پوشانی دقیق تر انجام گیرد می توان از الگوریتم های دیگر از جمله

Fit Ellipse استفاده کرد در این روش برای هر شئ مورد ردیابی  یک بیضی محاط می شود وسپس با بدست آوردن نسبت های اقطار آن قبل از هم پوشانی و مقایسه آن نسبت با نسبت اقطار بیضی های محاط شده احتمالی از اشیاء دیگر بعد از هم پوشانی می توان  شئ مورد نظررا ردیابی کرد.

این روش بیشتر برای اشیاء غیر صلب استفاده می شود.برای اشیاء صلب که دارای شکل هندسی منظم تر و گوشه های  قابل قبول تری  هستند می توان ازروش همبستگی گوشه ها استفاده کرد و اشیاء قبل وبعد هم پوشانی را با یکدیگر مقایسه کرد.در صورت وجود تشابه بین گوشه ها  شئ مورد نظر ردیابی شده است .

همچنین روشهای دیگری از قبیل نشانه گذاری قسمت های مختلف اشیاء برای جلوگیری از هم پوشانی وجود دارد که قسمت های مختلف اشیاء پس از نشانه گذاری در فریم های بعدی دنبال می شوند.

:انجام پروژه متلب

۶٧

مراجع :

[۱] Wang, Y. Ostermann, J. Zhang, Y., Video processing and communications, 1,

Prentice Hall, New Jersey, 2002.

[۲] Yakimovsky, Y. Cunningham, R., “A system for extracting three—dimensional

measurements from a stereo pair of TV cameras”, Computer Graphics and Image

Processing, Vol. 7, pp. 195-210, 1978.

[۳] Foley, J. A., Introduction to computer graphics, 1, Addison Wesley, 1994.

[۴] Musmann, H. G., “Object oriented analysis synthesis coding of moving images”,

Signal Processing and Image Communication, Vol. 1, pp.119-138, 1989.

[۵] Mann, S., “Video orbits of the projective group: A simple approach to featureless

estimation of parameters”, IEEE Trans.Image Process, Vol. 6, pp. 1281-1295,1997.

[۲] Aggarwal, j. k., “On the computation of motion from sequences of images”,

Proceedings of the IEEE, Vol. 76, pp. 917-935, 1988.

[۳] Musmann, H. G., “Advances in picture coding”, Proceedings of the IEEE, Vol.

۷۳, pp. 523-548, 1985.

[۴] Stiller, C., “Estimating motion in image sequences”, IEEE Signal Processing

Magazine, Vol. 16, pp. 70-91, 1999.

[۵] Konrad, J., “Bayesian estimation of motion vector fields”, IEEE Trans. Pattern

Anal. Machine Intell, Vol. 14, pp. 910-927, 1997.

[۶] Horn, B., “Determining constant optical flow”, ۲۰۰۳٫

[۷] Fleet, D., J., “Computation of component image velocity from local phase

information”, International Journal of Computer Vision, Vol. 5, pp. 77-104, 1990.

[۸] Haralick, R., M., “The facet approach to optical flow”, In Image Understanding

Workshop, 1993.

[۹] Mitiche, A., “Aggarwal experiments in computing optical flow with gradient

based, multiconstraint method”, Pattern Recognition, Vol. 20, pp. 173-179, 1987.

[۱۰] Horn, B., “Determining optical flow”, Artificial Intelligence Laboratory,

Massachusetts Institute of Technology, pp. 185-203, 1980.

[۱۱] Jain, J. R., “Displacement measurement and its application in inter frame image

coding”, IEEE Trans. Communication, Vol. 29, pp. 1799-1808, 1981.

١٣٠

[۱۲] Koga, T., Motion compensated inter frame coding for video conferencing, In

Nat. Telecommunication. Conf, G5.3.1-5, New Orleans, 1981.

[۱۳] Lee, O., Wang, Y., “Motion compensated prediction using nodal based

deformable block matching”, Journal  of  Visual  Communications  and  Image

representation, Vol. 6, pp. 26-34, 1995.

[۱۴] Zienkewicz, O. C., Taylor, R. L., The Finite Element Method, Vol. 1, 4th ed,

Upper Saddle River, Prentice Hall, 1989.

[۱۵] Wang, Y., Lee, O., “Use of 2-D deformable mesh structures for video

compression. Part I—the synthesis problem: Mesh based function approximation and

mapping”, IEEE Trans. Circuits Syst.for Video Technology, Vol. 6, pp. 636-646,

[۱۶] Wang, Y., Lee, O., “Active mesh-a feature seeking and tracking image sequence

representation scheme”, IEEE Trans.Image Process, Vol. 3, pp. 610-624, 1994.

[۱۷] Altunbasak, Y., “Occlusion- adaptive, content based mesh design and forward

tracking”, IEEE Trans.Image Process, Vol. 6, pp.1270-1280, 1997.

[۱۸] Bretzner, L., “Multi scale feature tracking and motion estimation”,

Computational Vision and Active Perception Laboratory, pp. 1-153, 1999.

[۱۹] Lucas, B. D., Kanade, T., “An iterative image registration technique with an

application to stereo vision”, in Proceedings of International Joint Conference on

Artifical Intelligence, pp. 242-251,1981.

[۲۰] Shi, J., Tomasi, C., “Good features to track”, in Proceedings of the IEEE

Conference on Computer Vision and Pattern Recognition, pp. 593–۶۰۰, ۱۹۹۴٫

[۲۱] Tomasi, C., Kanade, T., Detection and tracking of point features, Technical

Report CMU-CS-91-132,Carnegie Mellon University, Pittsburg, Pennsylvania, April

[۲۲] Trucco, E., “Feature tracking in video and sonar subsea sequences with

applications”, Computer Vision and Image Understanding, Vol. 79, pp. 92-122, 2000.

[۲۳] Gua, Z., Object detection and tracking in video, TR., Department of Computer

Science, Kent State University, 2001.

[۲۴] Nascimento, J., “Robust shape tracking in the presence of cluttered

background”, IEEE Trans.Image Process, Vol. 7, pp.82-85, 2000.

[۲۵] Goto, T., “Real time facial feature tracking and speech acquisition for cloned

head”, MiraLab, University of Geneva, pp. 1-6, 2000.

١٣١

[۲۶] Darrell, T., Gordan, G., “Integrated person tracking using stereo, color, and,

pattern detection”, Proceedings of the Conference on Computer Vision and Pattern

Recognition, Santa Barbera, pp. 601-609, 1998.

[۲۷] Schwerdt, K., “Robust face tracking using color”, pp. 1-6, 2000.

[۲۸] Byung Park, J., “Tracking objects and faces using color histograms enhanced

with specularity detection”, Proceeding of the IEEE Conference on Robotics,

Automation and Mechatronics”, Singapore, pp. 975-980, 2004.

[۲۹] Dockstader, S., Tekalp, A. M., “Real time object tracking and human face

detection in cluttered scenes”, Image and Video Communications and Processing,

SPIE, San Jose, 2002.

[۳۰] Gregory, D., Belhumeur, N., “Efficient region tracking with parametric models

of geometry and illumination”, IEEE Trans on Pattern Analysis and Machine

Intelligence, Vol. 20, No. 10, 1998.

[۳۱] Ren, Y., “Color based tracking by adaptive modeling”, Seventh International

Conference on Control, Automation, Robotics And Vision(ICARCV02), Singapore,

2002. ۱۵۹۷-۱۶۰۲, ۲۰۰۲٫

[۳۲] Wang, J., “Tracking object features using dynamically defined spatial context”,

Brown University, pp. 1-6, 2004.

[۳۳] Dokladal, P., “Contour-based object tracking with gradient-based contour

attraction field”, IEEE Trans.Image Process, Vol. 9, pp.17-20, 2004.

[۳۴] Park, J., “Natural Feature Tracking for Extendible Robust Augmented

Realities:, University of Southern California, pp. 1-7, 1999.

[۳۵] Bourel, F., Claude, C., “Robust facial feature tracking”, Staffordshire

University, pp.1-10, 2000.

[۳۶] Cohen, I., Tian, Q., “Feature selection using principal feature analysis”, pp. 1-

۷, ۱۹۹۸٫

[۳۷] Zhong, Y., “Object tracking using deformable templates”, IEEE Transactions on

Pattern Analysis and Machine Intelligence, Vol. 22, No. 5, pp. 544-549, 2000.

[۳۸] Tanju Erdem, A., “Tracking visible boundary of objects using occlusion adaptive

motion snake”, IEEE Transaction on Image Processing, Vol. 9, No. 12, pp. 2051-

۲۰۶۰, ۲۰۰۰٫

[۳۹] Okuma, T., “A natural feature-based 3D object tracking method for wearable

augmented reality”, IEEE Trans.Image Process, pp. 451-456, 2004.

١٣٢

[۴۰] Hu, W., Tan, T., Wang, L., “A survey on visual surveillance of object motion and

behaviors”, IEEE     Transaction     on     systems,     MAN,     and     cybernetics—part

C:Application and reviews, Vol. 34, No.3, 2004.

[۴۱] Lixin, F., “Image recognition system and method using holistic harr-like feature

matching”, U.S. Patent Application.

[۴۲] Lixin, F., “Generic object detection and tracking without training”, pp. 1-3.

[۴۳] Wang, J., Huang, T. S., and Ahuja, N., Motion and structure from image

sequences, New York, Springer-Verlag, 1993.

[۴۴] Faugeras, O., Three-dimensional computer vision—A geometric viewpoint,

Cambridge, MA: MIT Press, 1993.

[۴۵] Bierling M.,” Displacement Estimation by Hierarchical Block Matching ”,Visual

Communication and Image Processing , Vol , 1001,pp.942-951,1998.

[۴۶] J.L .Barron and N.A. Thacker. Tina Memo .”Tutorial ;Computing 2D and 3D

optical flow”,Mo.2004-012,2005.

[۴۷] M-K.H U.,” Visual pattern recognition by moment invariants ”.Computer

method in image analysis, pp.168-176,2002.

[۴۸] H. Blum .”  Atrans formation for extracting new descriptions of shape ”,

Computer methods in image analysis .pp. 343-352,2004.

[۴۹]  B.D .Lucas and T. Kanade ,”An Iterative Image Registration Technique with an

Application to stereo vision”. Darpa .Image Understanding work shop,1999.pp,130-

۱۴۰

[۵۰]  Abdi , H . BECK ,A, Bryman, T . Futing,” Encyclopedia for research method for

the social sciences”, Thousand  oaks (CA),pp.792-795,1998

[۵۱] A. J. Lipton, H. Fujiyoshi, and R. S. Patil, “Moving Target Classification and

Tracking from Real-Time Video,” Proc. IEEE Workshop Applications of Computer

Vision, pp. 8-14, 1998.

[۵۲]D. Koller, J. Weber, T. Huang, J. Malik, G. Ogasawara, B. Rao, and S. Russel,

“Toward Robust Automatic Traffic Scene Analysis in Real-Time,” Proc. Int. Conf.

Pattern Recognition, Israel, pp. 126-131, 1994.

[۵۳] N. Friedman and S. Russel, “Image Segmentation in Video Sequences: A

Probabilistic Approach,” Proc. 13th Conf. Uncertainty in Artificial Intelligence, pp. 1-

۳, ۱۹۹۷٫

١٣٣

Abstract Object tracking is considered as one of the important and

progressive problem in machine vision and image processing field.

Object tracking method monitors the position change of an object

and its  follow  up  among   sequence  video  images  based  on  a  particular

goal .Although this tracking history goes back to  military applications , but

because  of  its  high  application  rate  in  object  tracking in different fields,

it is considered deeply in recent years. In this project  then, object recognition

,tracking techniques , and  movement assessment methods are considered and

finally an  optical flow  algorithm  is used  for  tracking  application. Methods

of optimizing this algorithm as well as the current problems are detailed and

the provided data base is studied. For Solved of this problem used of lucas

kanade method. for implementation of this Algorithm use of robust tools open

cv that is provided of Intel company, and use for particular image processing

application.

Keyword: Object tracking, Detection and Segmentation ,Optical flow,  Motion

estimation

١٣۴