بهبود کارآیی روش مینیمم تابع اختلاف تصویر چرخشی با استفاده از الگوریتم CMA-ES در جهت یابی بهینه

محورهای موضوعی : آمار

سید وحید لکزیان ¹ , موسی الرضا شمسیه زاهدی ² , عقیله حیدری ³ , مجید انجیدنی ⁴

1 - گروه ریاضی، دانشگاه پیام نور، ص. پ.19395-3697، تهران، ایران
2 - گروه ریاضی، دانشگاه پیام نور، ص. پ.19395-3697، تهران، ایران
3 - گروه ریاضی، دانشگاه پیام نور، ص. پ.19395-3697، تهران، ایران
4 - گروه کامپیوتر، دانشگاه پیام نور، ص. پ.19395-3697، تهران، ایران

تاریخ دریافت : 1401/01/16 تاریخ پذیرش : 1401/06/15 تاریخ انتشار : 1402/03/01

کلید واژه: Panoramic image, image processing, Rotational image difference function (rIDF), Optimal navigation,

چکیده مقاله :

جهت‌یابی یک توانایی حیاتی برای انسان و حیوان محسوب می‌گردد. برای بهبود مهارت‌های جهت‌یابی در ربات‌ها، می‌توان از روشی که حشرات در طبیعت با کمک آن جهت‌یابی می‌کنند، الهام گرفت. یک سوال اصلی در مورد حشراتی که به‌ کمک توانایی بصری خود جهت‌یابی می‌کنند؛ این‌ است که آن‌ها چه اطلاعاتی از تصاویر ‌طبیعی را در پیدا کردن جهت حرکت استفاده می‌کنند؟ برای جهت‌یابی، می‌توان از روش ‌مینیمم تابع ‌‌‌اختلاف تصویر چرخشی ‌ (MrIDF) به کمک پردازش تصاویر پانوراما استفاده کرد [1]. در روش MrIDF حتی با شیفت کامل در صورتی-که فاصله مکان تصویر نمای فعلی تا تصویر مرجع زیاد شود، نمی‌توان مسیر برگشت را به دلیل زیاد شدن اختلاف دو تصویر، به‌‌درستی شناسایی کرد. در این مقاله، ما راه‌کاری ارائه می‌دهیم که در نقاط دور از مکان مرجع نیز، می‌توان مسیر و زاویه برگشت را شناسایی ‌کرد. همچنین با استفاده از الگوریتم بهینه‌سازی استراتژی ‌تکاملی ‌انطباق ‌ماتریس ‌کوواریانس (CMA-ES)، کارآیی روش‌ MrIDF را بهبود می‌بخشیم و در ادامه کارآیی آن ‌را در قالب یک مثال ناوبری نشان می‌دهیم. نتایج نشان می‌دهند که یافتن جهت حرکت از طریق الگوریتم پیشنهادی، با دقت کافی و در زمان بسیار کمتری انجام می‌شود.

چکیده انگلیسی:

Orientation is a vital ability for humans and animals. Noticing the way insects orient in nature can be used to improve the orientation skills of robots. The main question of this research can be stated as follows. What kind of information do insects perceive of natural scenes, using their visual ability, that enables them to orient and to find the direction of movement? For orientation, the minimum of rotational image difference function (MrIDF) method can be applied using panoramic image processing [1]. In MrIDF method, even with full shift, if the distance between the location of the current view image and the reference image increases, the return path cannot be correctly identified due to the increase in the difference between the two images. In this paper, we present a solution that can be used to identify the path and return angle in places far from the reference location. We also improve the efficiency the rotIDF minimum method by using the covariance matrix adaptation evolutionary strategy (CMA-ES) optimization algorithm. We show the efficiency of this method via a navigation example. The results show that finding the direction of movement through the proposed algorithm is done with sufficient accuracy and in much less time.

منابع و مأخذ:

 

[1]  W, Zeil J. Depth, contrast and view-based homing in outdoor scenes. Biological Cybernetics.2007; 96:219-531.

 

[2] M. Giurfa and E. A. Capaldi, ‘‘Vectors, routes and maps: new discoveries about navigation in insects,’’ Trends Neurosci. 22, 237-242 (1999).

 

[3] Cartwright BA, Collett TS. Landmark learning in bees-experiments and models. J Comp Physiol. 1983;151:521-543.

 

[4] Wehner R,  F. Visual spatial memory in desert ants, Cataglyphis bicolor (Hymenoptera: Formicidae).Cell Mol Life Sci. 1979; 35: 1569-1571

 

[5] Zeil J, Hofmann MI, Chahl JS. Catchment areas of panoramic snapshots in outdoor scenes. J Opt SocAm A.2003; 20: 450-469.

 

[6] Baddeley B, Graham P, Husbands P, Philippides A (2012) A Model of Ant Route Navigation Driven by Scene Familiarity. PLoS Comput Biol 8(1): e1002336. Doi:10.1371/journal.pcbi.1002336

 

[7] Zahedi MS, Zeil J (2018) Fractal dimension and the navigational information provided by natural scenes. PloS ONE 13(5): e0196227. https://doi.org/10.1371/journal.pone.0196227.

 

[8] Pardalos P. and Romeijn E., eds. (2002) Handbook of global optimization, Vol. 2, Kluwer Acad. Publ., Dordrecht.

 

[9] Beyer HG, Schwefel HP. Evolution strategies - a comprehensive introduction. Nat. Comput. 2002; 1(1):3–52. doi: 10.1023/a:1015059928466. [CrossRef] [Google Scholar]

 

[10] Holland JH. Genetic algorithms. Sci. Am. 1992;267(1):66-73. doi:10.1038/ scientificamerican 0792-66. [CrossRef] [Google Scholar]

 

[11] Roubos J, van Straten G, van Boxtel A. An evolutionary strategy for fed-batch bioreactor optimization; concepts and performance. J. Biotechnol. 1999; 67(2–3):173–187. doi: 10.1016/s0168-1656(98) 00174-6. [CrossRef] [Google Scholar]

 

[12] Zeugmann T, et al. Particle swarm optimization. In: Sammut C, Webb GI, et al., editors. Encyclopedia of Machine Learning. Heidelberg: Springer; 2011. pp. 760–766. [Google Scholar]

 

[13] Storn R, Price K. Differential evolution-a simple and efficient heuristic for global optimization over continuous spaces. J. Global Optim. 1997; 11(4): 341–359. doi: 10.1023/A:1008202821328. [CrossRef] [Google Scholar]

 

[14] N. Hansen, S. D. , and P. Koumoutsakos. Reducing the time complexityof the derandomized evolution strategy with covariance matrix adaptation. Evolutionary Computation, 11(1):1-18, 2003.

 

[15] Anjidani M, Motlagh MJ, Fathy M, Ahmadabadi M. A novel online gait optimization approach for biped robots with point-feet. ESAIM: COCV, 25 (2019) 81. Published online:19 December 2019. DOI: 10.1051/cocv/2017034

 

[16] Akimoto Y, Hansen N. CMA-ES and Advanced Adaptation Mechanisms, GECCO '21: Proceedings of the Genetic and­Evolutionary­Computation Conference Companion. July 2021. Pages 636–663. https://doi.org/10.1145/3449726.3462748

 

[17] Nikolaus Hansen. 2016. The CMA Evolution Strategy: A Tutorial. ArXiv e-prints (April 2016). arXiv: cs.LG/ 1604.00772

 

[18] N. Hansen. The CMA evolution strategy: a comparing review. In J. A. Lozano, P. Larranaga, I. Inza, and E. Bengoetxea, editors, Towards a new evolutionary computation. Advances on estimation of distribution algorithms, pages 75-102. Springer, 2006.

 

[19]  W, Grixa I, Mair E, Narendra A, Zeil J. Three-dimensional models of natural environments and the mapping of navigational information, Journal of Comparative Physiology A.2015; 201: 563±584.

 

[20] Gonzalez, R. C. , and Woods, R. E. (2002), Digital Image Processing (2nd ed.), Prentice-Hall, Inc., ISBN0-201-18075-8

متن کامل:



دسترسي در سايتِ http://jnrm.srbiau.ac.ir

سال نهم، شماره چهل و دوم، خرداد و تیر  1402

شماره شاپا: X2588-588

 

 

 

 

بهبود کارآیی روش مینیمم تابع اختلاف تصویر چرخشی با استفاده از الگوریتم CMA-ES در
جهت­یابی بهینه

 

 

سید وحید لکزیان1، موسی­الرضا شمسیه زاهدی2¹، عقیله حیدری3، مجید انجیدنی4

 

(1و2و3)   گروه ریاضی، دانشگاه پیام نور، ص. پ.19395-3697، تهران، ایران

(4)   گروه کامپیوتر، دانشگاه پیام نور، ص. پ.19395-3697، تهران، ایران

 

 

تاريخ ارسال مقاله:         16/01/1401   تاريخ پذيرش مقاله: 15/06/1401

چکيده

جهت­یابی یک توانایی حیاتی برای انسان و حیوان محسوب می­گردد. برای بهبود مهارت­های جهت­یابی در ربات­ها، می­توان از روشی که حشرات در طبیعت با کمک آن جهت­یابی می­کنند، الهام گرفت. یک سوال اصلی در مورد حشراتی که به‌ کمک توانایی بصری خود جهت­یابی می‌کنند؛ این­ است که آن­ها چه اطلاعاتی از تصاویر ‌طبیعی را در پیدا کردن جهت حرکت استفاده می­کنند؟ برای جهت­یابی، می­توان از روش ‌مینیمم تابع اختلاف تصویر چرخشی (MrIDF) به کمک پردازش تصاویر پانوراما استفاده کرد. [1] در روش MrIDF حتی با شیفت کامل در صورتی­که فاصله مکان تصویر نمای فعلی تا تصویر مرجع زیاد شود، نمی­توان مسیر برگشت را به دلیل زیاد شدن اختلاف دو تصویر، به­­درستی شناسایی کرد. در این مقاله، ما راه­کاری ارائه می‌دهیم که در نقاط دور از مکان مرجع نیز، می­توان مسیر و زاویه برگشت را شناسایی کرد. همچنین با استفاده از الگوریتم بهینه‌سازی استراتژی ‌تکاملی ‌انطباق ‌ماتریس ‌کوواریانس(CMA-ES)، کارآیی روش‌ MrIDF را بهبود می­بخشیم و در ادامه کارآیی آن را در قالب یک مثال ناوبری نشان می­دهیم. نتایج نشان می­دهند که یافتن جهت حرکت از طریق الگوریتم پیشنهادی، با دقت کافی و در زمان بسیار کمتری انجام می­شود.

 

واژه‌هاي کليدي: تصاویر پانوراما، پردازش­ تصویر، ناوبری بهینه، تابع اختلاف­ تصویر چرخشی (rIDF).

 

---

[1] . عهده­دار مکاتبات:                                                                   Email: [e-mail] 

۱- مقدمه

انسان­ها و حیوانات جهت بقاء باید بتوانند اهداف مهّم حیات خود مانند خانه و غذا را به خاطر بسپارند و دوباره به آن­ها مراجعه کنند. شواهدی زیادی وجود دارد که نشان می‌دهد، حشرات از حافظه ‌بصری برای حرکت ‌به سمت هدف استفاده می‌کنند.[2] بر اساس این شواهد، تعدادی مدل برای چگونگی جهت­یابی حشرات با استفاده از مقایسه تصویر نمای فعلی و تصویر مرجعی که به خاطر سپرده­اند، ارائه شده است. یکی از مؤثرترین مفاهیم ناشی از تحقیقات جهت­یابی حشرات، فرضیه تطبیق تصاویر لحظه‌ای است که از آزمایش­‌های کلاسیک بر روی زنبور­ها [3] و مورچه­‌ها [4] نشأت گرفته است. با توجه به این فرضیه، حشرات هنگامی که می­خواهند به جستجوی هدف مانند لانه یا منبع غذایی بروند، تصاویر لحظه‌ای پانوراما با وسعت زیاد از محیط اطراف خود را در حافظه ذخیره می­­کنند که آن­‌ها را قادر می‌سازد با حرکت در جهت مینیمم اختلاف تصویر نمای فعلی و تصویر مرجع ذخیره شده، به مکان هدف برگردند. در این­صورت تابع اختلاف تصاویر پانوراما حاصل از rIDF با نزدیک شدن به مکان مرجع به­طور آهسته کاهش می­یابد؛ زیرا این مینیمم اختلاف تصویر، مقدارtIDF  در آن مکان است. [1و5]

بدلی و همکاران، مدلی از جهت­یابی در مورچه­های صحرایی با استفاده از روش MrIDF ارائه کرده­اند؛ نتایج نشان داد که مسیریابی شبیه­سازی شده توسط آن­ها، به رفتار واقعی مورچه­ها بسیار نزدیک است. [6] در ادامه، ­زاهدی و زیل دریافتند که بعد فرکتال¹ تصاویر ­طبیعی با اطلاعاتی که از مینیمم اختلاف تصاویر پانوراما برای جهت­یابی به­دست
می­آید، رابطه معکوس دارد. [7] ما در این مقاله قصد داریم برای بهبود کارآیی روش MrIDF، از یک روش ­بهینه­سازی مدرن و برتر استفاده کنیم.

روش­ بهینه­سازی سراسری ­تصادفی، روشی برای حل یک مسئله بهینه­سازی سراسری است که شامل عناصر تصادفی در داده­های مسئله (از جمله تابع هدف و محدودیت­ها) یا خود الگوریتم یا هر دو
می­باشد. بهینه­سازی سراسری بخش مهّمی از ریاضیات کاربردی و علوم کامپیوتر است. اهمیت بهینه­سازی سراسری به زمینه­های کاربردی مانند مهندسی، شیمی­محاسباتی، مالی، پزشکی و بسیاری از زمینه­های دیگر مربوط می­شود؛ [8] اگر تابع هدف به­­عنوان کد رایانه­ای "جعبه سیاه" درنظر گرفته شود، بهینه­سازی مسئله با مشکل مواجه خواهد شد. رویکردهای تصادفی اغلب با مشکلاتی از این دست بسیار آسان­تر از الگوریتم­های قطعی برخورد می­کنند. با این حال روش بهینه­­سازی سراسری تصادفی، نیاز زیادی به ویژگی­های مسئله بهینه­­سازی خود ندارد و وابسته به مسئله خاصی نیست؛ بنابراین یک روش معمول برای حل مسائل بهینه­­سازی می­باشد.

محاسبات تکاملی² خانواده­ای از مدرن­ترین الگوریتم­ها جهت بهینه­­سازی سراسری­ تصادفی هستند. [9] از زمانی که محاسبات­ تکاملی طراحی شد، به ­سرعت توسعه یافت و شاخه‌های زیادی را تشکیل داد. در این شاخه­ها می­توان از الگوریتم ژنتیک (GA) [10]، استراتژی تکاملی (ES)  [11]، بهینه‌سازی ازدحام­ جمعیت (PSO) [12]، الگوریتم تکامل دیفرانسیل (DE) [13] و استراتژی­ تکاملی انطباق ماتریس کوواریانس (CMA-ES) [14] نام برد. این الگوریتم­ها نیاز به دانش­های مکمل ندارند و فقط تابع هدف و شایستگی مربوط در جهت­های جستجو تاثیر گذارند. یکی از مزایای الگوریتم­های بدون گرادیان مانند الگوریتم CMA-ES این است که در صورت عدم وجود گرادیان و ناپیوستگی
می­توانند به­کار خود ادامه دهند؛ [15] امّا با افزایش اندازه مسئله، محاسبه جواب­بهینه توسط الگوریتم­­ها و روش­های سنتی، ساعت­ها و یا حتی روزها طول می­کشد. الگوریتم CMA-ES یک الگوریتم بهینه سازی تکراری است که در سال­های اخیر پیشنهاد شده است. [16] یکی دیگر از مزایای این الگوریتم، تنظیم خودکار انحراف ­­معیار با توجه به ­توزیع جمعیت است؛ زیرا می­تواند از اطلاعات جواب­ بهینه به­­طور همزمان برای تنظیم پارامتر­ها در تکرار بعدی استفاده کند؛ درنتیجه الگوریتم بهینه‌سازی CMA-ES به­عنوان یکی از محبوب­ترین الگوریتم­های بهینه­­سازی بدون گرادیان، منتخب بسیاری از محققان و متخصصان می­باشد. در این مقاله، اختلاف زاویه تصویر نمای فعلی و تصویر مرجع ذخیره شده در مثالی با استفاده از روش MrIDF و الگوریتم CMA-ES مورد ارزیابی قرار می­گیرد. روش MrIDF با توجه به این­که تمام فضا را برای یافتن بهینه سراسری جستجو می­کند، میزان محاسبات زیادی نیاز داشته و زمان­بر می­باشد. همچنین در روش فوق حتی با شیفت کامل در صورتی­که فاصله مکان تصویربرداری فعلی تا مکان مرجع زیاد شود، نمی­توان زاویه حرکت را به­­درستی شناسایی کرد و این به دلیل زیاد شدن اختلاف تصویر نمای فعلی با تصویر مرجع می­باشد. راه­کار ارائه شده در این مقاله به این­­صورت است که مورچه در حین فاصله گرفتن از تصویر مرجع ذخیره شده، مانند خانه یا غذا در نقاط متوالی نزدیک به­هم تصویربرداری کرده و توسط محاسبه اختلاف زاویه دو تصویر متوالی، در هر لحظه زاویه خود با تصویر مرجع را به­­روز می­کند. به این ترتیب با فاصله گرفتن از مکان مرجع نیز می­تواند مسیر برگشت را با دقت بالایی شناسایی ­کند. فرضیه­های تحقیق به این­صورت می­باشند که ما از حرکت قائم سر مورچه و همچنین تغییر ­زاویه‌ ناگهانی آن در طول حرکت صرف­­نظر می­کنیم؛ زیرا در این­صورت اختلاف زاویه دو تصویر متوالی کم بوده و استفاده از الگوریتم بهینه‌سازی CMA-ES احتمال­گیر کردن در مینیمم محلی را به حداقل می­رساند.

ساختار مقاله در ادامه به شرح زیر است: در بخش دوم به بیان روش MrIDF و الگوریتم CMA-ES می‌پردازیم. سپس در بخش سوم الگوریتم پیشنهادی را توضیح می­دهیم. در بخش چهارم در قالب یک مثال ناوبری ابتدا روش تصویربرداری، پردازش تصاویر و در ادامه الگوریتم و راه­کار پیشنهادی برای یافتن جهت بازگشت به مکان مرجع را توضیح می­دهیم. در بخش آخر، بحث و نتيجه­گيري آمده است.

 

2- مواد و روش­ها

در این مقاله برای بهبود کارآیی روش MrIDF از الگوریتم CMA-ES استفاده می­کنیم. محاسبه MrIDF برای جهت­یابی نیازمند به چرخش کامل تصویر نمای فعلی نسبت به تصویر مرجع است که در صورت وجود تصاویر با سایز بالا می­تواند زمان­بر باشد. الگوریتم پیشنهادی برای رفع این نقص از تلفیق روش MrIDF و الگوریتم بهینه‌سازی CMA-ES استفاده می­کند. همچنین در الگوریتم پیشنهادی راه­کاری ارائه می­شود که در فواصل دور از مکان مرجع می­توان زاویه و مسیر برگشت را شناسایی کرد. در این بخش، روش MrIDF و الگوریتم بهینه‌سازی CMA-ES را توضیح می­دهیم و در بخش بعدی الگوریتم پیشنهادی را ارائه می­کنیم.

 

2-1: روش MrIDF

روش مینیمم ­تابع اختلاف تصویر چرخشی یک روش بهینه‌سازی سراسری می­باشد که برای یافتن زاویه حرکت، از اختلاف پیکسلی تصویر پانورامای مکان فعلی و تصویر مرجع استفاده می­کند؛ در این روش برای به­­دست آوردن کمترین اختلاف (بیشترین شباهت) بین دو تصویر پانوراما، ابتدا جهتی را پیدا می­کنیم­ که  rIDFدر آن جهت مینیمم است و سپس با حرکت در آن جهت، tIDF کاهش می‌یابد. [1و6] فرم ماتریسی پیکسل­های دو تصویر خاکستری عبارتند از  و  که به ترتیب تصویر مرجع ذخیرشده و تصویر نمای فعلی هستند. تابع اختلاف تصویر برابر با مجموع مربعات درایه­های ماتریس حاصل از اختلاف پیکسلی دو ماتریس تصویر می­باشد،

 

 

حال MrIDF را برای ماتریس‌های تصویر  و  به­­صورت زیر تعریف می‌کنیم ([7] را ببینید):

(1)                     

 

به­­طوری­که ماتریس نتیجه اعمال واحد شیفت (چرخش) دایره­ای () ماتریس تصویر به­­­صورت ستونی می­باشد و تعریف می­کنیم:

(2)

 

حال اگر اختلاف یک تصویر پانورامای 360 درجه را با شیفت یافته همان تصویر محاسبه کنیم، مقدار  rIDF  به­صورت زیر محاسبه می­شود:

(3)

رابطه (3) را می­توان به­صورت متفاوت زیر بازنویسی کرد:

 

 

که با شکستن سیگما از محل و با استفاده از رابطه (2)،  به­صورت زیر تبدیل می­شود:

(4)

 

همچنین برای محاسبه تابع اختلاف بین دو ماتریس تصویر از رابطه ­(4) نیز می­توان استفاده کرد. بنابراین مینیمم rIDF برابر با کمترین مقدار رابطه­ (1) یا (3) به ازای می­باشد،

 

 

که این مقدار برای رابطه (3)، صفر می­باشد.

 

2-2: الگوریتم CMA-ES

 الگوریتم بهینه‌سازی CMA-ES در سال 1996 توسط هن­سن و آستمیر معرفی شده است. این الگوریتم یک روش بدون مشتق و تصادفی جدید برای حل مسائل غیرخطی، غیرمحدب و جدا ناپذیر است. در این نوع استراتژی با استفاده از پارامترهای میانگین، واریانس و ضریب پراکندگی از توزیع نرمال، داده‌ها استخراج می­شوند و پس از بررسی آن­ها، بهترین داده­ها انتخاب شده و ماتریس کوواریانس و میانگین جدید تولید می­شوند. سپس مجددا داده­ها از توزیع جدید استخراج می­شوند و با ادامه این روند، الگوریتم کم­کم به­سمت نقطه بهینه همگرا می­شود. قوانین مختلف به‌روز‌رسانی، ماتریس کواریانس تطبیق­یافته‌ای را در هر نسل ایجاد می‌کند که در کیفیت جمعیت جدید و در نتیجه هدایت تکامل نقش مهمی دارد. تولید جمعیت جدید، انتخاب و ترکیب دوباره، کنترل اندازه گام و انطباق ماتریس کوواریانس چهار بخش اساسی فرآیند تکاملی هستند. اکنون یک الگوریتم بهینه ‌سازی خلاصه شده CMA-ES از هن­سن را ارائه می­کنیم. [17]

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

معمولا  در­نظر گرفته می­شود.

 

 

 

 

 

 

 

 

در ابتدا ، ، ماتریس کوواریانس  و مرتبه تکرار  را در‌ نظر می‌گیریم. اندازه گام  و میانگین توزیع گام مسئله مورد نظر را انتخاب می‌کنیم.

مرحله دوم: حلقه تکاملی گام 

را ادامه می­دهیم تا به جواب بهینه (معیار توقف) برسیم:

نمونه جمعیت جدید از نقاط جستجو:

 

 

 

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

        

(5)

 

که

 

 

کنترل اندازه گام:

(6)

 

(7)

 

انطباق ماتریس کوواریانس:

(8)

(9)

 

(برای جزئیات بیشتر [18] را ببینید).

3- الگوریتم پیشنهادی مبتنی بر پردازش تصویر با تلفیق روش MrIDF ­و الگوریتم CMA-ES

در الگوریتم پیشنهادی برخلاف روش MrIDF برای یافتن زاویه بین دو تصویر پانوراما از شیفت کامل تصویر استفاده نمی‌شود. در این الگوریتم برای افزایش دقت جهت­یابی، در هر نقطه از پیش تعیین­ شده، پنج تصویر پانورامای منتخب داریم که تصویربرداری در هر نقطه را یک گام در نظر
می­گیریم. این تصاویر پس از انتقال به رایانه و اعمال فیلترهایی در نرم­افزار متلب، پردازش و طبقه­بندی می­شوند (در بخش چهارم توضیحات تکمیلی داده می­شود). سپس توسط الگوریتم پیشنهادی با CMA-ES، برای یافتن زاویه هر تصویر نسبت­ به تصویر در گام قبلی، مسئله بهینه­سازی زیر را تعریف می­کنیم:

(10)

 

که تصویرام در گامام می­باشد. شرط توقف در الگوریتم CMA-ES را می­توان بر اساس تعیین مینیمم مقدار تابع هزینه یا تعداد تکرارهای الگوریتم تنظیم کرد. مینیمم اختلاف پیکسلی (minimum point) دو تصویر  و  به­­صورت زیر مشخص می­گردد:

(11)

 

سپس با تبدیل مینیمم اختلاف پیکسلی دو تصویر به زاویه از طریق رابطه ­(12)، زاویه حرکت مشخص می‌‌شود:

(12)

 

ما در این مقاله برای محاسبه هر زاویه، پنج تصویر منتخب پردازش­­شده در هر گام داریم و برای افزایش دقت جهت­یابی، پنج زاویه به­­دست آمده از الگوریتم پیشنهادی در هر گام را با استفاده از روابط­ پیشنهادی (13) و (14) به­صورت وزنی تلفیق می­کنیم.

(13)

(14)

 

روش کار به این صورت است که تصاویری که شباهت³ بیشتری (­rIDF کمتری) دارند به­­­طور نمایی، تاثیر بیشتری در زاویه بهینه⁴ می­گذارند؛ سپس در جهت زاویه بهینه به­دست آمده حرکت می‌کنیم تا به نقطه مرجع برسیم. در بخش بعدی این روند در قالب یک مثال ناوبری برای مسیرهای فرضی از پیش تعیین شده با پنج نقطه، به­طور کامل بیان می­شود. در روش MrIDF برای یافتن زاویه حرکت از اختلاف پیکسلی تصویر پانورامای نمای فعلی و تصویر مرجع استفاده می­شود؛ بنابراین به احتمال زیاد در نقاط دور از مرجع زاویه برگشت به دلیل اختلاف زیاد دو تصویر به­درستی محاسبه نمی­گردد. [19] راه­کار ارائه شده در این مقاله برای نقاط دور از تصویر مرجع به این­صورت می­باشد که ما درحین فاصله گرفتن از تصویر مرجع در نقاط متوالی نزدیک به­هم تصویربرداری می­کنیم و توسط محاسبه­اختلاف­زاویه دوتصویر درنقاط متوالی، در هر لحظه زاویه حرکت با تصویر مرجع به ­روز می­شود. به این ترتیب با فاصله گرفتن از مکان مرجع
می­توان مسیر برگشت را با دقت بالا شناسایی کرد. شکل(1)نمایی از الگوریتم­پیشنهادی­را نشان­می­دهد.

 

4- مثال کاربردی و نتایج

در این بخش، ابتدا روش تصویربرداری و پردازش تصاویر را بیان می­کنیم و سپس در قالب یک مثال ناوبری از الگوریتم و راه­کار پیشنهادی برای مسیریابی استفاده می­کنیم؛ در ادامه مسیر بهینه از طریق الگوریتم پیشنهادی و روش  MrIDFبا راه­کار مشابه توسط نرم­افزار متلب، مورد تجزیه و تحلیل قرار می­گیرد و نتایج مقایسه می­شوند.

 

4-1: روش تصویربرداری

در این مقاله پنج مکان متفاوت در شهرستان نیشابور از ایران، برای ثبت تصاویر پانوراما با استفاده از دوربین 360 درجه "RICOHTETHA S" با 2/0­ فریم در ثانیه (فواصل 5 ثانیه) انتخاب گردید که در شکل (2) آورده شده است. در هر مکان یک مسیر فرضی از پیش تعیین­ شده در­نظر گرفته ­شد. سه مسیر برای به­دست آوردن اطلاعات دقیق‌تر روی صفحه چوبی ترسیم و در مکان­های مورد نظر قرار داده شدند. در هر مسیر پنج نقطه با فواصل یکسان قرار داده­ایم؛ در نقطه اول دو مرحله تصویربرداری به مدت دو دقیقه در جهت حرکت و دو دقیقه در جهت شمال (جهت ­مرجع) داریم؛ ولی در سه نقطه بعدی فقط یک مرحله تصویربرداری در جهت حرکت داریم. این تصاویر پانورامای کروی را به رایانه انتقال داده و ­به تصاویر پانورامای­360 درجه با سایز 1024×2048 تبدیل شدند. باتوجه به ­این­­که تصویربرداري صحیح و دقیق نقش به­سزایی در موفقیت پردازش ­تصویر [20] دارد، تقریبا از 20 تصویر به­­دست آمده در هر­نقطه از مسیر فرضی، پنج مورد از بهترین تصاویر را انتخاب می­کنیم که در شکل (3) نشان داده شده است.

 

---

[1]  Fractal dimension

[2]  Evolutionary Computation

[3]  similarity

[4]  optimal angle

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

شکل(1): نمایی از الگوریتم پیشنهادی

 

(آ) (ب) (ج) (د) (ه)

شکل(2): پنج مسیر از پیش تعیین­شده در پنج مکان متفاوت از شهرستان نیشابور.

 

 

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

 

 

4-2: پردازش تصاویر

به­منظور پردازش ­تصاویر از نرم­افزار متلبR2014b 

روی لپ‌تاپ Lenovo G560 مدل 20042 استفاده شد. ابتدا تصاویر از فایلی در رایانه به نرم­ افزار متلب، فراخوانی و براي برنامه قابل شناسایی شدند. در مرحله بعدي توسط دستوراتی تصاویر رنگی به تصاویر خاکستري8 تبدیل گردیدند و برای افزایش دقت ناوبری با استفاده از پردازش­تصویر، روش یکنواخت­سازی هیستوگرام9 به­تصاویر سطح خاکستری اعمال شد. این­گونه عملیات ساده پردازش تصویر، تابع تفاوت­های تصاویر را در برابر تغییرات نور و اثرات جعلی سایه­ها تقویت می­کند. [1] در­ ادامه، بخشی از قسمت پایین تصاویر پانوراما به دلیل تغییرات زیاد در گسترده تصاویر کروی نزدیک به دوربین، حذف گردید که اندازه تصاویر از 1024×2048 به 555×2048 پیکسل تبدیل شدند. این تصاویر نیاز به فضاي ذخیره‌سازي کمتري دارند و موجب ایجاد شرایط بهتر براي انجام دستور بعدي می­گردند. پردازش تصویرهای انجام شده در این مقاله در شکل (4) دیده می­شود.

 

4-3: مثال ناوبری با استفاده از الگوریتم پیشنهادی

شکل (5) یکی از مسیرهای فرضی از پیش تعیین شده در هوای نیمه ­ابری می­باشد. در این مسیر پنج نقطه با ­فواصل یکسان به اندازه 20 سانتی­متر در­ نظر می­گیریم. در نقطه اول پنج تصویر منتخب در جهت مرجع و پنج تصویر منتخب در جهت حرکت داریم و در سه نقطه بعدی، فقط پنج تصویر منتخب در جهت حرکت داریم. فیلترهای شکل (4) را برای افزایش دقت محاسبه زوایا به این تصاویر اعمال
می­کنیم. تصاویر طبقه­بندی شده شکل (3) را در الگوریتم پیشنهادی با دستورات جدید در برنامه متلب، فراخوانی کرده و از مسئله بهینه­سازی در رابطه (10) برای به­­دست آوردن مینیمم­ مقدار rIDF استفاده می­کنیم که دراین رابطه ، ،  و   در ­نظر گرفته می­شود. سپس از طریق رابطه (11) و (12) اختلاف پیکسلی  تصاویر و زاویای حرکت مشخص می‌‌شوند؛ شرط توقف در این الگوریتم برابر با 100 تکرار در نظر گرفته شد­ که غالبا در تکرار کمتری به جواب می­رسیم؛ یک مرحله از خروجی الگوریتم پیشنهادی در شکل (6) دیده می­شود. سپس در هر نقطه با توجه به زاویه حرکت به­­دست ‌آمده در جهت مینیمم اختلاف­تصاویر، حرکت­می­کنیم و باادامه این روند مسیر حرکت به سمت هدف مشخص می­گردد.

 

 

 

شکل(4): فیلترهای که روی تصاویر برای روند کار و افزایش دقت ناوبری انجام می­شود عبارتند از: آ) تبدیل تصویر کروی به پانورامای 360 درجه. ب) خاکستری­کردن تصویر و یکنواخت کردن هیستوگرام. ج) بریدن پایین تصویر. ^1   2

 

شکل(5): یکی از مسیرهای فرضی از پیش تعیین ­­شده ( شکل1- ه) با پنج نقطه برای تصویر­برداری. در نقطه اول، دو مرحله تصویر­برداری به مدت دو دقیقه در جهت مرجع و جهت حرکت داریم ولی در نقاط دوم و سوم و چهارم فقط یک مرحله تصویر­برداری در جهت حرکت داریم؛ در هر مرحله، یک تصویر منتخب در شکل آورده شده است.

 

 

 

 

شکل (6): یک مرحله از استفاده الگوریتم پیشنهادی برای محاسبه MrIDF بین دو تصویر در نقاط متوالی یک مسیر.

 

 

---

[1]  greyscale

[2]  Histogram Equalization

برای افزایش دقت ناوبری، براساس پنج تصویر گرفته شده در گام­های مختلف شکل (3)، زوایای حرکت برای مسیر شکل (5) در جدول (1) آمده است. هر ستون از زوایای جدول (1)، زوایای یک مسیر حرکت را نشان می­دهد که با استفاده از این زوایا، پنج مسیر متفاوت رسم می‌شود (شکل7- آ). برای افزایش دقت ناوبری از تلفیق وزنی زاویای پنج مسیر به­دست آمده در گام­های مختلف استفاده می­گردد و زاویه بهینه گامام با استفاده از روابط­ (13) و (14) محاسبه می­شود؛ در ادامه مسیر ­بهینه تلفیقی با استفاده از این زوایا توسط برنامه متلب رسم می‌شود (شکل 7- ب).

 

 

جدول 1- زوایای ناوبری به­دست آمده با الگوریتم پیشنهادی

مسیر حرکت پنجم	مسیر حرکت چهارم	مسیر حرکت سوم	مسیر حرکت دوم	مسیر حرکت اول	زاویه نسبت به شمال
9.8438	9.6680	9.8438	9.8438	9.6680	زاویه در نقطه اول
15.9961	16.6993	16.1715	15.6746	16.3477	زاویه در نقطه دوم
30.2344	30.5860	30.0582	29.5313	30.2344	زاویه در نقطه سوم
60.1172	60.4688	59.9410	59.9415	60.2930	زاویه در نقطه چهارم

 

                

                                                       (آ) (ب)

شکل (7): آ) پنج مسیرحرکت به­­دست آمده توسط الگوریتم پیشنهادی ، ب) تلفیق وزنی زوایای پنج مسیر حرکت

 

جدول (2): مسیرهای حرکت به­دست آمده توسط روش MrIDFو الگوریتم پیشنهادی با راه‌کار مشابه.

 

 

به این ترتیب، ایده پیشنهادی برای ناوبری بهینه از طریق پردازش­ تصاویر پانورامیک تکمیل می­شود که بر اساس تلفیق روش ­­ MrIDFبا الگوریتم بهینه‎‌­سازی تکراری CMA-ES می­باشد؛ بدون استفاده از این الگوریتم، باید به تعداد پیکسل‌های طول تصویر، rIDF محاسبه شود؛ یعنی اگر تصویر دارای سایز 555×2048 پیکسل باشد باید 2048 بار rIDF را محاسبه کرده و مینیمم مقدارش را به عنوان جواب ­بهینه و زاویه­ واقعی حرکت در آن نقطه انتخاب ­کنیم. به­­عبارتی در روش MrIDF برای یافتن مسیر بهینه، تمام فضا جستجو می‌شود و محاسبه آن 1222 ثانیه برای نرم­­افزار متلب، زمان می­برد که در مسیرهای طولانی­تر با تعداد نقاط بیشتر برای تصویربرداری، این محاسبه ممکن است ساعت­ها زمان ببرد؛ امّا توسط الگوریتم پیشنهادی با توجه به فرضیه تحقیق که در حین حرکت تغییر زاویه ناگهانی نداریم، اختلاف زاویه دو نقطه متوالی زیاد نمی­باشد و معمولا در چندین تکرار به جواب بهینه می‌رسیم. سرعت ناوبری در الگوریتم پیشنهادی بسیار بالاتر از روش MrIDF و کمتر از 20 ثانیه می­باشد. بنابراین، برای افزایش سرعت ناوبری در این روش، مجبور به کاهش سایز تصاویر می­شویم که در این­­صورت دقت ناوبری کاهش پیدا می­کند. مقایسه زوایای بهینه به­­دست آمده برای سه مسیر فرضی در جدول (2)، نشان می­دهد که دقت ناوبری با استفاده از الگوریتم پیشنهادی بیش از 98 درصد و نزدیک به روش MrIDF می­باشد؛ همچنین در الگوریتم پیشنهادی با تعیین مقدار عددی مناسب برای متغیر ، می­توان دقت یا سرعت ناوبری را افزایش داد. با توجه به این­که مینیمم مقدار rIDF تصاویر گرفته شده، هیچ وقت صفر نمی­شود؛ می­توان برای این متغیر در الگوریتم بهینه­سازی تکراری CMA-ES مقدار عددی مناسبی در نظر گرفت تا از تکرار­های اضافی در هر مرحله شکل ­(6) جلوگیری شود و سرعت ناوبری را تا حدی افزایش داد که دقت ناوبری کاهش پیدا نکند و بلعکس. در الگوریتم پیشنهادی برای مسیر فرضی اول در جدول (2)، مقدار  در نظر گرفته شده است. روش کار الگوریتم پیشنهادی به این­صورت است که اگر مقدار تابع هزینه در رابطه­ (10) در هر مرحله از 52 کمتر شود، از تکرارهای اضافی در آن مرحله جلوگیری می­کند و در کمتر از 100 تکرار به جواب بهینه می­رسیم.

 

5- بحث و نتیجه­گیری

جهت­یابی و شناسایی اهداف یک توانایی و نیاز ضروری حیاتی برای انسان و حیوان محسوب می­گردد. در روش MrIDF، در صورتی­که فاصله مکان تصویر فعلی تا تصویر مرجع زیاد شود، نمی­توان مسیر برگشت را به دلیل زیاد شدن اختلاف دو تصویر، به­­درستی شناسایی کرد. راه­کار ارائه شده در این مقاله، برای نقاط دور از تصویر مرجع به این­صورت می­باشد که در هنگام فاصله گرفتن از تصویر مرجع در نقاط متوالی نزدیک به­هم، تصویربرداری می­کنیم و توسط محاسبه اختلاف زاویه دو تصویر در نقاط متوالی، در هر لحظه زاویه حرکت با تصویر مرجع به­روز می­شود. به این ترتیب با فاصله گرفتن از مکان مرجع نیز می­توان مسیر و زاویه برگشت را با دقت بالا شناسایی کرد. همچنین در این مقاله ناوبری بهینه از طریق ادغام تصاویر ­پانوراما با الگوریتم پیشنهادی که تلفیق روش MrIDF و الگوریتم CMA-ES می­باشد، انجام گرفت. در روش MrIDF بدون استفاده از CMA-ES برای یافتن مسیر بهینه، تمام فضا جستجو می­شود و محاسبه آن توسط نرم­­افزار متلب، 1222 ثانیه زمان می­برد؛ امّا در الگوریتم پیشنهادی، این زمان به کمتر از 20 ثانیه کاهش پیدا می­کند. نهایتا در روش MrIDF  برای افزایش سرعت ناوبری، مجبور به کاهش اندازه تصاویر می‌شویم که در این­صورت دقت ناوبری کاهش پیدا می­کند. مقایسه زوایای مسیر بهینه به­دست آمده توسط نرم­افزار متلب، در هر دو روش با راه­کار مشابه نشان می‌دهد که از طریق الگوریتم پیشنهادی با دقت بیش از 98 درصد، مسیر بازگشت به مکان هدف شناسایی
می­گردد. همچنین در الگوریتم پیشنهادی، با تعیین مقدار مناسب برای متغیر ، می‌توان دقت یا سرعت ناوبری را افزایش داد.

 

 

 

جدول (3): جدول نمادها

مسیر فرضی سوم (شکل2- ج)		مسیر فرضی دوم (شکل2- د)		مسیر فرضی اول (شکل2- ه)		زاویا نسبت به شمال
الگوریتم پیشنهادی	روش MrIDF	الگوریتم پیشنهادی	روش MrIDF	الگوریتم پیشنهادی	روش MrIDF	روش­های بهینه­سازی
10.0196	10.0295	28.8615	28.8281	9.5844	9.8438	زاویه بهینه در نقطه اول
21.6509	21.9086	22.0253	21.8994	15.9258	16.5429	زاویه بهینه در نقطه دوم
6.0153	6.3055	29.6496	29.4580	30.1550	30.7267	زاویه بهینه در نقطه سوم
30.3802	30.6642	-32.4312	-32.4170	60.0968	60.6095	زاویه بهینه در نقطه چهارم
=20		=35		=52		مقداردر CMA-ES
18.67	1195	20.07	1208	19.47	1222	زمان ناوبری  (s)
98.5		99.6		98.3		دقت ناوبری (
						مسیر بهینه رسم شده با الگوریتم پیشنهادی توسط نرم­افزار متلب

توضیحات	نماد
­(مرتبه چرخش) واحد شیفت دایره­ای ماتریس تصویر به­­صورت ستونی می­باشد.
تعداد جمعیت اولیه در الگوریتم CMA-ES می­باشد.
تعداد والدین که از جمعیت اولیه در الگوریتم CMA-ES به­­دست می­آید.
ماتریس همانی
مرتبه تکرار حلقه در الگوریتم CMA-ES می­باشد.
انحراف ­معیار
مقدارمتغیرعددی stop fitness در الگوریتم CMA-ES می­باشد.
ماتریس کوواریانس
تعداد گام در الگوریتم پیشنهادی می­باشد که در هر گام پنج تصویر منتخب وجود دارد.

 

 

فهرست منابع

 

[1]  W, Zeil J. Depth, contrast and view-based homing in outdoor scenes. Biological Cybernetics.2007; 96:219-531.

 

[2] M. Giurfa and E. A. Capaldi, ‘‘Vectors, routes and maps: new discoveries about navigation in insects,’’ Trends Neurosci. 22, 237-242 (1999).

 

[3] Cartwright BA, Collett TS. Landmark learning in bees-experiments and models. J Comp Physiol. 1983;151:521-543.

 

[4] Wehner R, F. Visual spatial memory in desert ants, Cataglyphis bicolor (Hymenoptera: Formicidae).Cell Mol Life Sci. 1979; 35: 1569-1571

 

[5] Zeil J, Hofmann MI, Chahl JS. Catchment areas of panoramic snapshots in outdoor scenes. J Opt SocAm A.2003; 20: 450-469.

 

[6] Baddeley B, Graham P, Husbands P, Philippides A (2012) A Model of Ant Route Navigation Driven by Scene Familiarity. PLoS Comput Biol 8(1): e1002336. Doi:10.1371/journal.pcbi.1002336

 

[7] Zahedi MS, Zeil J (2018) Fractal dimension and the navigational information provided by natural scenes. PloS ONE 13(5): e0196227. https://doi.org/10.1371/journal.pone.0196227.

 

[8] Pardalos P. and Romeijn E., eds. (2002) Handbook of global optimization, Vol. 2, Kluwer Acad. Publ., Dordrecht.

 

[9] Beyer HG, Schwefel HP. Evolution strategies - a comprehensive introduction. Nat. Comput. 2002; 1(1):3–52. doi: 10.1023/a:1015059928466. [CrossRef] [Google Scholar]

 

[10] Holland JH. Genetic algorithms. Sci. Am. 1992;267(1):66-73. doi:10.1038/ scientificamerican 0792-66. [CrossRef] [Google Scholar]

 

[11] Roubos J, van Straten G, van Boxtel A. An evolutionary strategy for fed-batch bioreactor optimization; concepts and performance. J. Biotechnol. 1999; 67(2–3):173–187. doi: 10.1016/s0168-1656(98) 00174-6. [CrossRef] [Google Scholar]

 

[12] Zeugmann T, et al. Particle swarm optimization. In: Sammut C, Webb GI, et al., editors. Encyclopedia of Machine Learning. Heidelberg: Springer; 2011. pp. 760–766. [Google Scholar]

 

[13] Storn R, Price K. Differential evolution-a simple and efficient heuristic for global optimization over continuous spaces. J. Global Optim. 1997; 11(4): 341–359. doi: 10.1023/A:1008202821328. [CrossRef] [Google Scholar]

 

[14] N. Hansen, S. D., and P. Koumoutsakos. Reducing the time complexityof the derandomized evolution strategy with covariance matrix adaptation. Evolutionary Computation, 11(1):1-18, 2003.

 

[15] Anjidani M, Motlagh MJ, Fathy M, Ahmadabadi M. A novel online gait optimization approach for biped robots with point-feet. ESAIM: COCV, 25 (2019) 81. Published online:19 December 2019. DOI: 10.1051/cocv/2017034

 

[16] Akimoto Y, Hansen N. CMA-ES and Advanced Adaptation Mechanisms, GECCO '21: Proceedings of the Genetic and­Evolutionary­Computation Conference Companion. July 2021. Pages 636–663. https://doi.org/10.1145/3449726.3462748

 

[17] Nikolaus Hansen. 2016. The CMA Evolution Strategy: A Tutorial. ArXiv e-prints (April 2016). arXiv: cs.LG/ 1604.00772

 

[18] N. Hansen. The CMA evolution strategy: a comparing review. In J. A. Lozano, P. Larranaga, I. Inza, and E. Bengoetxea, editors, Towards a new evolutionary computation. Advances on estimation of distribution algorithms, pages 75-102. Springer, 2006.

 

[19]  W, Grixa I, Mair E, Narendra A, Zeil J. Three-dimensional models of natural environments and the mapping of navigational information, Journal of Comparative Physiology A.2015; 201: 563±584.

 

[20] Gonzalez, R. C. , and Woods, R. E. (2002), Digital Image Processing (2nd ed.), Prentice-Hall, Inc., ISBN0-201-18075-8

 

 

 

 

 

---