برگشت به دنیای پرخاطره بعد از سالها

از موقعی که آخرین پستمو گذاشتم داخله این بلاگ حول و حوش دوسالی میگذره. موضوع زیبا و قشنگی که قبلا میخوندم به بدترین نحو مجبور به ترکش شدم!!! استادی که باهاش کار میکردم ول کرد رف واسه دله خودش، از دانشگا استعفا داد :))

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

آقا خودت دستبکار شو!!!!! رو پای خودت ایستادن خیلی بیشتر ارزش داره!

lucas & kanade method

به بررسی روش دوم میپردازیم .در این روش مبحث اصلیمون را از یه دید دیگه شروع به بررسی میکنیم : روش حداقل مربعات ! (اگه احیانا مثه خودم اوایل با اون آشنایی ندارید میتونید به کتابهایی که در مورد محاسبات عددی بحث میکنن رجوع کنید ) خوب ! بهتره شروع کنیم :

توجه : در این روش فرض میشه که ذاتا فلو در همسایگی محلی پیکسل های تحت محاسبه ثابت است و به وسیله least squares criterion مسئله پایه فلو را در همسایگی حل میکنیم .در ضمن این روش چون فرض بالا رو داره نسبت به نویز حساسیت کمتری داره.

یه بار دیگه معادله فلو را در نظر بگیرید

اگر ما این معادله را برای یه پنجره بنویسیم (منظورم پنجره حاصل از پیکسلهاست) به صورت زیر میشه :

هدف اینه که حاصل این معادله  رو کمینه کنیم  :

در اینجا برای اینکه درکی از ساختن و کار کردن با معادله داسته باشیم من ماتریس A رو 2*2 فرض کردم :

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

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

1- در لبه ها :

حاصل ضرب فوق مقدار ویژه یکتا داره ، به شکل زیر دقت کنید :

که در اون(-Iy,Ix) بردار ویژه با مقدار ویژه صفر است.

2- در پیکسل های همجنس و یکجور و موافق (homogeneous)

حاصلضرب تقریبا صفره و مقادیر ویژه صفر رو میده

3- در نواحی بافت (textured regions)

دو مقدار ویژه زیاد داره

 که نتیجه گیری ساده از سه مورد فوق اینکه : در دو مورد اول ما از نتیجه حاصل شده راضی نیستیم ولی در مورد سوم هستیم )

پس ما تا اینجا دو مورد از break down  مون رو فهمیدیم سه مورد دیگه هم به اونها اضافه میکنم :

4- اگه پایداری روشنایی مورد رضایت نباشه (Brightness constancy)

5- اگه یه پیکسل مثه دیگر نقاط همسایش حرکت نکنه (در اینجا اینکه اندازه مناسب پنجره چقدره، پیش میاد)

6-اگه حرکت کوچیک نباشه  ( یعنی بسط تیلور رو نشه استفاده کرد)

در مورد اول راهکاری که میتونیم بکار بگیریم Correlation based method  است

در مورد دوم راهکار مناسب Regularization based method  است

و در مورد آخر هم  Use multi scale estimate  است

در ادامه به اینکه multi scale estimation  چیه یکم بحث میکنیم

کلا یه بحثی هست در مورد multi scale flow estimation که با ابزاری توسط هرم های پیاده سازی میشن .بهتره اول بفهمیم هرم در پردازش عکس چیه ؟؟!!

من مختصری در مورد هرم های توضیح میدم بعد میریم سراغ هرم هایی که باهاشون کار داریم یعنی هرم لاپلاس و هرم گوسی .

Pyramid or Pyramid representation  یه نوع نمایش  multi-scale سیگنال است که توسط زمینه هایی چون image processing  و computer vision و signal processing توسعه داده شده، و مواقعی بکار گرفته میشه که یک عکس یا سیگنال به تکرار مورد عمل smoothing  و subsampling قرار میگیره (در حقیقت هرم یک رویه برای نمایش scale space و آنالیز  multiresolution  است) ودر مورد تقسیم بندی هرم ، میتونیم بگیم که دو نوع هرم داریم : هرم پایین گذر و هرم بالا گذر(lowpass pyramids & bandpass pyramid)

هرم پایین گذر : این هرم بوسیله یک هموار( smoothing) کننده عکس با یک فیلتر هموار سازی مناسب و سپس subsampling کردن اون عکس هموار شده ، انجام میشه و در نهایت حاصل این اعمال برای محاسبات استفاده میشه .طی تکرار این روش نتایج به این صورت خواهد بود که در هر مرحله عکس های هموار شده نسبت به مرحله قبل هموار تر میشوند و از لحاظ شکلی این نمایش multi-scale شبیه یه هرم میشه .

خوب فکر کنم که دیگه بیشتراز این لازم نباشه که ببنیم چیه !

Gaussian-Laplacian Pyramid Image Coding

به صورت چندتا نکته این رو بررسی میکنیم :

مرحله  (Down-sampling)

            1.برای مرحله جدید کانولوشن با یک فیلتر گوسین بالا گذر انجام میدیم-

2.تفاوت عکسها(band-pass)

توجه داریم که پارامتر h تفاوت بین دو عکس است .

3. Down-sampling f’l+1

4.تمامی عکسها را میتوان توسط هرم لاپلاس بدست آورد(هرم لاپلاس اولین بار توسط burt & adelson برای فشرده سازی عکسها آورده شد.)

مرحله (up-sampling)

1.متقاطع کردن صفرها(سطر و ستون)

2.کانولوشن کردن با یک فیلتر گوسین پایین گذر

بطور کلی اگه بخواهیم که بصورت دیاگرامی آنچه گفته شد را نمایش بدیم به صورت زیر میشود

در مورد هرم لاپلاس هم این عکس کمکی برای درک عملی اون دار

و اما یه کم بیشتر در مورد هرم لاپلاس :

بعد از این عمل تنها یک نمونه از دو نمونه باقی میمونه که در اون تعداد پیکسل ها از طریق دو ویژگی های دو نمونه در هر scaling  کاهش پیدا میکنه.برای این عمل کانولوشنی با h  داریم که از طریقه اون عمل فوق انجام میشه :

برای درک بهتر به نمونه زیر دقت کنید

که در اون گذر C0 به C1 نمایش داده شده است.و برای باز سازی Cjاز Cj+1 عمل زیر را انجام میدهیم:

و برای درک اینهم به شکل زیر دقت کنید تا گذر C1 به C0 را مشاهده کنید :

که این عمل در فضای دو بعدی همان تعریف بالا را دارد با این تفاوت که ،باز هدف کشیدن یک نمونه از دو نمونه است ولی اینبار در دو جهت !!!! یعنی کانولوشن به فرم زیر در میآید :

و فرم بازگشت هم به صورت زیر میشود :

به طور کلی تعداد نمونه ها بر4 تقسیم میشه ، به طوری که اگه ما یه عکس N*N داشته باشیم آنگاه اندازه هرم 4/3N^2 میشه .در شکل زیر هم مراحل هرم رو میبینیم :

خوب ، پس یه دید کلی هم در مورد هرم های پیدا کردیم .

در حقیقت آقایان lucas , kanade ترجیح دادن قبل از اعمال معادله محدودیت گرادیان یک pre-smooth داشته باشن روی عکهاشون!!

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

که در اون W(x) یه قابیه (پنجره اییه )که هر چه به مرکز پنجره نزدیکتر میشیم بیشتر تحت تاثیر مرکز همسایگیه Ω قرار میگیره.که اگه بخواهیم دوباره به معرفی پارامترهای این معادله بپردازیم :

در ضمن قابل توجه که نکته مفید قابل ذکر در روش فوق نسبت به روش هورن اینه که در این روش از حضور یک اندازه ضریب استفاده میکنیم.و کمترین مقداری که eigenvalue  ماتریس زیر به خودش میگیره (λ) یه معیار اندازه گیری برای تعیین normal vilocity  از سرعت دو بعدی است .

در مقاله آقای Barron  گزارش شده که این روش طبق نتایجی که داده به عنوان دومین روش مناسب برای تشخیش  optic flow است.

به علت دقتی که ما از روشها انتظار داریم ، تحقیقات در جهت کاهش اثر هموار کردن در نواحیی که دارای گرادیان شدت روشنایی تیزی(شیب دار) هستند ادامه داره .آقایان Nagel , Enkelmann و اولین کسایی بودند که در جهت جهت بندی هموارسازی (oriented smoothness constraint) و فرموله کردن روششون تلاش کردن که این موضوع روش سوم ماست!!!!

خوب حالا یه کم! در مورد فیلترهای گوسی بحث کنیم (که در بالا از آنها استفاده کردیم )

فیلترپایین گذر گوسی برای کاهش اثر خطوط ،کاهش دادن جزئیات تصویر(کدر شدن تصویر) ، و کلا به عنوان یک پیش پردازش در تحلیل عکس هایی که دارای جزییات زیادی هستند مورد استفاده قرار میگیره (البته در این فیلتر باید با توجه فرکانس قطع فیلتر کار کنیم !)و یه کاربرد عملی هم در OCR هاست!

و فیلتر بالا گذر برای افزایش جزییات تصویر مورد استفاده قرار میگیره

در مورد اینکه این در فیلتر توسط چه فرمولهای ریاضی تعریف میشوند میتونید به کتاب گنزالز(digital image processing ) مراجعه کنید.

منابع : Performance of Optic Flow Techniques(J.L.Barron…)

LITERATURE REVIEW on OPTICAL FLOW

اسلایدهای The Optical Flow Field(Caltech,oct.2004__lihi zelnik-manor)

کتاب اصول پردازش دیجیتال (دکتر محمد شمس آبادی /مهندس ابوالفضل احمدی)

 

Horn _Schunk method

قبل از اینکه این رو شروع کنید به خوندن یه نکته مهم !!!!! من خودم دارم با یکی از استادای machin vision  کار میکنم ، خانم دکتر قیصری ، یه نصیحتی از جانب ایشون  :  برای اینکه در این موضوع بخوایم پیشرفت کنیم لازم نیست که بشینیم و ریاضیات رو از اول تا اخر بخونیم ، کافیه هر جا به مسئله ای برخورد کردیم به سراغش بریم ، پس توی خوندن این مقاله هر جا به مسئله ای برخورد کردید همونجا برید دنبالش.

در روش هورن برای حل مسئله aperture  محدودیتی را معرفی کرده ، با نام smoothness   در این محدودیت فرض بر این است که تمامی پیکسل های تصویر در حرکتی که انجام میدهند میزان سطح خاکستری ثابتی دارند (در حقیقت آقای هورن برای حل optic flow  فرضی گرفته و با اون روشهایی رو داده که این روشها در حیطه حل معادلات دیفرانسیلی است) و در این روش سعی بر این شده که با کمینه سازی اعوجاج بهترین حل رو برای این مسئله ارائه بدهد.

در این روش به flow   به دیدگاه یک تابع انرژی و اینکه این تابع انرژی باید از نظر مقدار کمینه باشد ، نگاه شده است .این تابع  برای دیمانسیون دو بعدی به صورت زیر است

نکته مهم : term فوق محدودیت مهمی است که توسط هورن وارد این زمینه شد و به یاد داشته باشیدش!!!!

 به طوریکه Iy,It,Ix مشتقات  مقدار روشنایی عکس در طول محورهای x,y و بردار محور زمان هستند بردار

 optic flow   است و پارامتر آلفا (regularisation parameter) یک ضریب تنظیم ثابت است که درجه smoothness را معین میکند. مقادیر بیشتر آلفا به smooth  شدن هرچه بیشتر flow  میشود.(به نقل از مقاله Barron, Fleet and Beauchemin این مقدار آلفا در 0.5 نتایج خوبی را در بر دارد)این تابع از حل معادلات مرتبط  اویلر-لاگرانژ کمینه میشود که عبارتند از :

به طوریکه L تابع زیر انتگرال عبارت انرژی است .که بصورت زیر بیان میشود

بطوریکه اندیسهایi در بالا توضیح داده شدند.همچنین عملگر دلتا اشاره به عملگر لاپلاسین دارد :

در عمل laplacian   تقریبی عددی است که با استفاده از دیفرانسیل محدود(Finite Differences) بدست میآید و ممکن است به فرم زیر نوشته شود

به طوری که u (با ر) میانگین وزندار u که در همسایگی حول pixel  در نقطه (x,y) است. با نکات گفته شده معادله  فوق به صورت زیر نیز نوشته میشود

وu,v, ممکن است برای هر پیکسل در عکس حل شوند. باید به این نکته توجه داشت که چون حل به نقاط همسایگی وابسته است پس به محض به روز شدن پیکسل ها این حل باید تکرار شود. Gauss-Seidel equations :

که K+1 اشاره به تکرار بعدی دارد.(اگر مقدار k=0 آنگاه u,v به مقدار اولیه تخمین که برابر صفر است اشاره دارد)

(به نقل از مقاله Barron, Fleet and Beauchemin) چون این روش (به همین فرم توضیح داده شده) روشی است که  سرچشمه خطاهای زیادی است میتوان قبل از اعمال این روش از روشهای زیر استفاده کرد (برای کمتر شدن خطا)
(در مورد این که چرا خطا تولید میکنه ، خود مقاله بارون رو یه ترجمه کوچولو دارم میکنم ، اونجا توضیح خوبی وجود داره)

-. بهتره ماسکی با ضرائب  (1 و-8 و 0و8 و-1) * 0.08333  استفاده کنیم

-.استفاده از پیش فیلتر گوسی با انحراف معیار 1.5 پیکسل در فضا و 1.5 پیکسل در زمان(1.5 pixel-frames)

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

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

-          فرضیات :

پایداری شدت روشنایی

سرعت در همسایگی تقریبا یکسان است

     -ویژگیها :

                        اطلاعات کلی(global information ) را یکپارچه میکنه

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

                        Itrative

                        با همواری لبه ها در حرکت کار میکنه

           

یه خلاصه کوچیک تا اینجا :

هورن اومد و محدودیت gradiant  و محدودیت global smoothness رو برای تخمین v(x,t) = (u(x,t),v(x,t))  استفاده کرد.با کمینه سازی اون انتگرالی که توضیح داده شد.که در اون انتگرال ضریب α اثر محدودیت global smoothness  رو نشون میده که barron   در آزمایشهای خودش 0.5 رو پیشنهاد کرد .

مراجع :

(در این مقاله از مقاله barron  و ویکی پدیا و همچنین یکی از دوستان عزیز به نام آقای عباد پیر مرادیان نیز کمک گرفتم )

robost.Stanford.edu(/)cs223b(/)index.(html)

Performance of Optic Flow Techniques(J.L.Barron…)

LITERATURE REVIEW on OPTICAL FLOW