مقاله – کاربرد الگوريتم رقابت استعماري براي انتخاب ويژگي در سيستم تشخيص چهره

 

مسئله انتخاب ويژگي، يکي از پيچيده‌ترين مسائل در بازشناسي الگو است و يک مسئله NP-Hard مي‌باشد. در اين مقاله به بررسي کاربرد الگوريتم رقابت استعماري (ICA: Imperialis Competitive Algorithm) براي انتخاب ويژگي در مسئله تشخيص چهره مي‌پردازيم. ويژگي‌هاي استخراج شده براي سيستم تشخيص چهره مورد نظر، با استفاده از موجک Gabor محاسبه مي‌شوند.  …” … اینها بخشهایی از چکیده مقاله نوشته شده در مورد استفاده از الگوریتم رقابت استعماری برای انتخاب ویژگی در سیستم تشخیص چهره می باشد. نویسنده این مقاله جناب آقای محمدحسين سيگاري هستند که در لحظه انتشار این پست، دانشجوی دکتری هوش مصنوعی در دانشگاه تهران می باشند. ایشان، این کار ارزشمند را زیر نظر مرحوم دکتر لوکس انجام داده و منتشر کرده اند. اگر علاقه مند، به مطالعه کامل این مقاله هستید، با ما در ادامه مطلب که باز نشری از نسخه کامل این مقاله است، همراه باشید. نسخه پی دی اف به همراه فیلم توضیحات کامل این مقاله نیز در انتهای پست قابل دانلود است.



چکیده: مسئله انتخاب ويژگي، يکي از پيچيده‌ترين مسائل در بازشناسي الگو است و يک مسئله NP-Hard مي‌باشد. در اين مقاله به بررسي کاربرد الگوريتم رقابت استعماري (ICA: Imperialis Competitive Algorithm) براي انتخاب ويژگي در مسئله تشخيص چهره مي‌پردازيم. ويژگي‌هاي استخراج شده براي سيستم تشخيص چهره مورد نظر، با استفاده از موجک Gabor محاسبه مي‌شوند. بنابراين هدف از انتخاب ويژگي، انتخاب بهترين موجک‌هاي Gabor براي استخراج ويژگي است. در آزمايش‌هاي انجام شده، عملکرد الگوريتم ICA با الگوريتم بهينه‌سازي جمعي ذرات (PSO: Particle Swarm Optimization) براي انتخاب ويژگي در مسئله تشخيص چهره مورد ارزيابي قرار گرفت. براي بررسي کارايي دو الگوريتم PSO و ICA، از پايگاه داده تصاوير FERET استفاده شده است. از اين پايگاه داده دو مجموعه A و B استخراج شد که هر مجموعه شامل 100 کلاس چهره مي‌باشد. هر کلاس چهره فقط شامل 2 تصوير است که يک تصوير براي آموزش سيستم و يک تصوير براي آزمايش سيستم استفاده مي‌شود. در الگوريتم ICA و PSO، برازش هر جواب (مجموعه ويژگي‌هاي انتخاب شده) بر اساس ميزان دقت بازشناسي بدست آمده از آن جواب روي مجموعه A محاسبه گرديد. پس از پايان الگوريتم انتخاب ويژگي، ويژگي‌هاي انتخاب شده توسط بهترين جواب نسل آخر، براي تشخيص چهره روي مجموعه B مورد استفاده قرار گرفت. نتايج آزمايش‌ها نشان داد که الگوريتم ICA ويژگي‌هاي مناسبي را براي سيستم تشخيص چهره انتخاب مي‌کند، به طوري که با تعداد ويژگي‌هاي بسيار محدود مي‌توان دقت شناسايي خوبي بدست آورد. علاوه بر اين، کارايي الگوريتم ICA در انتخاب ويژگي، بيشتر از الگوريتم PSO مشاهده گرديد.

واژه‌های کلیدی: الگوريتم رقابت استعماري (ICA)، بهينه‌سازي جمعي ذرات (PSO)، تشخيص چهره، انتخاب ويژگي، موجک Gabor.

1-    مقدمه

يکي از مهمترين و مشکل‌ترين مسائل در حوزه بازشناسي الگو مسئله انتخاب ويژگي است. هدف از انتخاب ويژگي، انتخاب يک زيرمجموعه از مجموعه ويژگي‌ها است به طوري که تعداد ويژگي‌هاي انتخاب شده کمترين و دقت بازشناسي الگو بيشترين مقدار را داشته باشد. مسئله انتخاب ويژگي يک مسئله NP-Hard است و يکي از مناسب‌ترين ابزارهاي حل اين مسئله، الگوريتم‌هاي تکاملي هستند.

يکي از محبوب‌ترين و پرکاربردترين الگوريتم‌هاي تکاملي، الگوريتم ژنتيک (GA) مي‌باشد. بيشترين شکل استفاده از الگوريتم‌هاي ژنتيک براي مسئله انتخاب ويژگي اين گونه است که هر کروموزم با يک رشته بيتي با طولي به اندازه کل مجموعه ويژگي‌ها بازنمايي مي‌شود. حال انتخاب يا عدم انتخاب يک ويژگي از اين مجموعه با بيت يک و صفر نمايش داده خواهد شد. به اين ترتيب نمايش جواب‌هاي ممکن مسئله به صورت مجموعه‌اي از رشته‌هاي بيتي است. بنابراين به راحتي مي‌توان از عملگر‌هاي ترکيب (Recombination) و جهش (Mutation) براي رشته‌هاي بيتي استفاده کرد. براي تابع برازش نيز مي‌توان معياري قرار داد که ضمن انتخاب زيرمجموعه‌اي از ويژگي‌ها که بيشترين دقت بازشناسي را دارند، تعداد اعضاي آن زير مجموعه نيز حداقل باشد. مثلا اگر بخواهيم تابع برازش را يک ترکيب خطي از دقت بازشناسي و تعداد اعضاي زيرمجموعه ويژگي انتخاب شده قرار دهيم، چنين خواهد شد:

fitness\left( {{F_i}} \right) = \alpha CCR\left( {{F_i}} \right) + (1 - \alpha )length\left( {{F_i}} \right) (1)

در رابطه فوق Fi زيرمجموعه‌اي از ويژگي‌هاي انتخاب شده، CCR دقت بازشناسي با استفاده از اين ويژگي‌ها، length تعداد اعضاي زيرمجموعه و α يک عدد در بازه [0,1] مي‌باشد.

در پژوهش حاضر، مقايسه‌اي ميان دو الگوريتم PSO و ICA در مسئله انتخاب ويژگي براي تشخيص چهره انجام مي‌شود. هر دوي اين الگوريتم‌ها جزو الگوريتم‌هاي بهينه‌سازي برگرفته از رفتار اجتماعي موجودات زنده هستند که شباهت‌هاي زيادي به هم دارند. در اين مقاله فرض شده تعداد ويژگي‌ها ثابت و از پيش تعريف شده است.، بنابراين در رابطه (1)، مقدار α برابر يک انتخاب مي‌گردد.

2-    بهينه‌سازي جمعي ذرات (PSO)

الگوريتم PSO يک الگوريتم بهينه‌سازي مبتني بر رفتار اجتماعي حرکت پرندگان است. اين الگوريتم اولين بار توسط Kennedy و Eberhart در سال 1995 ارائه شد [2]. در الگوريتم PSO، چند ذره (Particle) به عنوان جواب‌هاي اوليه در فضاي جستجو ايجاد مي‌شوند. حرکت اين ذرات در فضاي جستجو يک حرکت تصادفي و متاثر از تجربه خود و ديگر ذرات است. به عبارت ديگر، بردار حرکت هر ذره، به طور تصادفي از برايند حرکت در راستاي بهترين مکاني که قبلا در آن بوده (LBest) و بهترين مکاني که قبلا در کل ذرات مشاهده شده (GBest)، تعيين مي‌گردد.

فرض کنيد Xi مکان ذره iام و Vi سرعت اين ذره باشد، در اين صورت بردار حرکت هر ذره بر اساس روابط زير محاسبه خواهد شد:

\begin{array}{l} {V_i}(t + 1) = w.{V_i}(t)\\  + {C_1}.{R_1}.\left( {X_i^{LBest}(t) - {X_i}(t)} \right)\\  + {C_2}.{R_2}.\left( {{X^{GBest}}(t) - {X_i}(t)} \right) \end{array}   (2)
{X_i}(t + 1) = {V_i}(t + 1) + {X_i}(t)  (3)

در اين رابطه w، C1 و C2 به ترتيب ضريب اينرسي، ضريب حرکت به سمت LBest و ضريب حرکت به سمت GBest است که جزو پارامترهاي الگوريتم محسوب مي‌شوند. R1 و R2 نيز اعداد تصادفي هستند.

3-    الگوريتم رقابت استعماري (ICA)

براي فهم بهتر الگوريتم ICA سعي مي‌کنيم رابطه‌اي ميان الگوريتم ICA و GA برقرار کنيم. در الگوريتم GA تعدادي فرد وجود دارد که يک جمعيت را تشکيل مي‌دهند. افراد جمعيت بر اثر عملگرهاي ترکيب و جهش در فضاي جستجو به دنبال پيدا کردن بهترين جواب جابجا مي‌شوند. انتخاب والدين و انتخاب فرزندان جديد براي نسل بعد در الگوريتم GA بر اساس ميزان برازش هر فرد انجام مي‌شود.

در الگوريتم ICA، به جاي افراد، کشورهايي وجود دارند که هر کشور مشابه يک فرد در الگوريتم GA داراي مشخصاتي است که مکان آن کشور را در فضاي جستجو مشخص مي‌کند. در اين مجموعه از کشورها که به عنوان نقاطي از فضاي جستجو هستند، تعدادي کشور که ميزان برازش بيشتري دارند به عنوان استعمارگر انتخاب مي‌شوند. در الگوريتم ICA به جاي اصطلاح ميزان برازش از اصطلاح قدرت (Power) استفاده مي‌شود. به اين ترتيب کشورهاي قدرتمند به عنوان استعمارگر و کشورهاي ضعيف به عنوان مستعمره قرار مي‌گيرند. هرچه ميزان قدرت استعمارگر بيشتر باشد، تعداد کشورهاي مستعمره بيشتري را به خود اختصاص خواهد داد. در ابتداي اجراي الگوريتم، کشورها به طور تصادفي توليد مي‌شوند و چند کشور قدرتمند به عنوان استعمارگر انتخاب مي‌شوند. سپس ساير کشورها به طور تصادفي به يکي از استعمارگران منتسب مي‌شوند، به طوري که تعداد مستعمرات هر استعمارگر متناسب با قدرتش خواهد بود.

حرکت در فضاي جستجو به اين شکل مي‌باشد که هر کشور در راستاي کشوري که مستعمره آن است به صورت تصادفي حرکت مي‌کند. به عنوان مثال اگر يک استعمارگر را با ستاره و کشور مستعمره آن را با دايره نشان دهيم، حرکت کشور مستعمره به سمت کشور استعمارگر مطابق شکل 2 خواهد بود.

http://www.icasite.info/icasite/post_i/image478-la.jpg
شکل 2: نحوه حرکت کشورها در فضاي جستجو بر اساس الگوريتم ICA

همانطور که در شکل ديده مي‌شود، اگر فاصله بين کشور مستعمره تا استعمارگر برابر d باشد، حرکت کشور مستعمره به اندازه x و به سمت محل استعمارگر نظير آن خواهد بود. البته اين حرکت با زاويه θ منحرف مي‌شود که مقدار حرکت x و زاويه θ به طور تصادفي تعيين مي‌گردد. معمولا مقدار زاويه θ به طور يکنواخت در بازه [-γ,γ] و مقدار حرکت x به طور يکنواخت در بازه [0,βd] انجام مي‌شود. مقادير γ و β به عنوان پارامترهاي الگوريتم ICA است که به ترتيب برابر 45 درجه و 2 پيشنهاد شده است [1].

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

در هر مرحله از تکرار الگوريتم ICA، رقابتي استعماري ميان استعمارگران برقرار است. در اين رقابت، استعمارگري که نسبت به ديگر استعمارگران قدرت کمتري دارد، يکي از مستعمرات خود را از دست مي‌دهد. به اين ترتيب ضعيف‌ترين مستعمره از ضعيف‌ترين استعمارگر به طور تصادفي به يکي از استعمارگران ديگر ملحق مي‌شود. احتمال انتساب اين مستعمره جديد به هر يک از استعمارگران متناسب با ميزان قدرت استعمارگران خواهد بود.

اگر استعمارگري به دليل از دست دادن مستعمرات خود، هيچ مستعمره‌اي نداشته باشد، آن استعمارگر خود به صورت مستعمره يک استعمارگر ديگر در خواهد آمد. مراحل الگوريتم ICA به همين ترتيب ادامه مي‌يابد تا بالاخره تعداد استعمارگران به يک برسد. در اين حالت تمام کشورها، مستعمره يک استعمارگر هستند و الگوريتم به پايان مي‌رسد. البته شرايط ديگري نيز مي‌توان براي پايان الگوريتم قرار داد که از جمله آن اجراي تعداد تکرار معيني از الگوريتم يا يافتن بهترين جواب ممکن است. به اين ترتيب فلوچارت الگوريتم ICA مطابق شکل 3 خواهد شد.

http://www.icasite.info/icasite/post_i/image417-la.jpg
شکل 3: فلوچارت الگوريتم ICA
4- استخراج و انتخاب ويژگي در مسئله تشخيص چهره

دو الگوريتم PSO و ICA براي انتخاب ويژگي در مسئله تشخيص چهره مورد استفاده قرار گرفتند. در اين تحقيق فرض شده که تعداد ويژگي‌ها معين است و هدف، تنها يافتن بهترين ويژگي‌هاست که بتواند دقت تشخيص چهره را افزايش دهد. در آزمايش‌هاي انجام شده، تعداد ويژگي‌هاي قابل انتخاب، برابر 50 فرض شده است.

قبل از بکارگيري اين دو الگوريتم در يافتن ويژگي‌هاي برتر، ابتدا لازم است تا اندکي در مورد اين ويژگي‌ها صحبت شود. در اين مسئله از ويژگي‌هاي استخراج شده مبتني بر موجک Gabor استفاده شده است.

4-1-    موجک Gabor
موجک Gabor دوبعدي از حاصلضرب يک تابع گوسي در يک تابع سينوسي بدست مي‌آيد و به شکل زير توصيف مي‌شود:

G\left( {x,y} \right) = \cos \left( {\frac{{2\pi X}}{\lambda }} \right)\exp \left( { - \frac{{{{\left( {X - {\mu _x}} \right)}^2} + {{\left( {Y - {\mu _y}} \right)}^2}}}{{2{\sigma ^2}}}} \right)   (4)

که X و Y مختصات چرخش‌يافته x و y حول مرکز موجک و به اندازه زاويه θ است:

\left\{ {\begin{array}{ccccccccccccccc} {X = x\cos \theta  - y\sin \theta }\\ {Y = x\sin \theta  + y\cos \theta } \end{array}} \right.   (5)

به اين ترتيب موجک Gabor پنج پارامتر دارد: μx و μy مختصات مرکز موجک Gabor، λ طول موج سيگنال سينوسي، θ زاويه چرخش موجک، نشان‌دهنده جهت نوسانات موجک و σ شعاع (انحراف معيار) تابع گوسي.

در تابع موجک، معمولا شعاع تابع گوسي را ضريبي از طول موج سيگنال سينوسي قرار مي‌دهند. به اين ترتيب براي موجک‌هاي مختلف Gabor با طول موج‌هاي متفاوت، همواره تعداد معيني از نوسانات تابع سينوسي در موجک ظاهر مي‌شود.

4-2-    استخراج ويژگي
در انتخاب ويژگي براي مسئله تشخيص چهره، هدف انتخاب تعداد محدودي از موجک‌هاي Gabor است که بر اساس ضرايب بدست آمده از عمليات کانولوشن بين موجک Gabor و قسمتي از تصوير ورودي، بازشناسي الگو را انجام داد. عمليات بازشناسي الگو در تشخيص چهره، مشابه روش پيشنهادي در پايان‌نامه مجيدپور [3] مي‌باشد.

4-3-    انتخاب ويژگي
با توجه به توضيح بخش قبل، يک موجک Gabor 4 پارامتر مستقل دارد: μx و μy مختصات مرکز موجک، λ طول موج نوسانات موجک و θ زاويه چرخش موجک. اگر تصاوير استفاده شده براي بازشناسي الگو 50×50 پيکسل و تعداد مقادير ممکن براي λ و θ به ترتيب 10 و 8 مقدار مفروض باشند، 200000 موجک Gabor مختلف و در نتيجه به همين تعداد ويژگي مختلف وجود دارد. هرچند برخي از اين ويژگي‌ها همبستگي دارند، اما به هر حال مرتبه زماني حل مسئله انتخاب ويژگي از اين مجموعه بزرگ بسيار مشکل است. حتي با فرض اينکه فاصله هيچ دو موجک روي محور x و y کمتر از 5 پيکسل نباشد، 8000 ويژگي مختلف وجود دارد که در اين حالت همبستگي بين ويژگي‌ها تا حد زيادي کاسته شده است. به اين ترتيب براي انتخاب 100 ويژگي از اين مجموعه 8000 تايي، \frac{{8000!}}{{100!7900!}} حالت مختلف وجود دارد که بررسي تمام حالت‌ها براي انتخاب بهترين زيرمجموعه 100 عضوي بسيار دشوار است.

5-    نتايج آزمايش

براي مسئله تشخيص چهره از 200 کلاس چهره از بانک داده FERET استفاده شد. 100 کلاس چهره به عنوان مجموعه A براي اجراي الگوريتم انتخاب ويژگي و 100 کلاس چهره به عنوان مجموعه B براي بررسي کيفيت ويژگي‌هاي استخراج شده، استفاده گرديد. هر کلاس چهره شامل 2 تصوير چهره از روبرو (Frontal) با ابعاد 48×56 مي‌باشد. اين تصاوير از نظر اندازه، چرخش و مکان چشم‌ها نرمال شده‌اند.

در آزمايش‌هاي انجام شده، از دقت بازشناسي به عنوان تابع برازش استفاده شد. به عبارت ديگر، ميزان برازش هر جواب (زيرمجموعه‌اي از ويژگي‌هاي انتخاب شده) برابر با دقت بازشناسي بر اساس آن دسته از ويژگي‌ها است. بنابراين لازم است تا به ازاي هر جواب (زيرمجموعه ويژگي‌هاي انتخاب شده) از جمعيت، يکبار سيستم بازشناسي آموزش داده شده و مورد ارزيابي قرار گيرد. براي اين منظور از مجموعه A استفاده شد که در آن هر کلاس شامل دو تصوير است: يک تصوير براي آموزش سيستم و يک تصوير براي آزمايش سيستم.

تمام آزمايش‌ها با استفاده از نرم‌افزار MATLAB R2008a، روي يک کامپيوتر شخصي با پردازنده AMD 5600+ Dual Core با حافظه 1 GB و در شرايط يکسان انجام شده است.

همانطور که قبلا گفته شد، ويژگي‌هاي استخراج شده، ويژگي‌هاي استخراج شده مبتني بر موجک Gabor هستند. هر موجک Gabor چهار پارامتر دارد. علاوه بر پارامتر‌هاي موجک Gabor، يک پارامتر به نام ضريب وزن نيز براي هر ويژگي انتخاب شده تعيين مي‌شود. ضريب وزن هر ويژگي، به عنوان ضريب آن ويژگي در محاسبه کوتاه‌ترين فاصله مورد استفاده قرار مي‌گيرد. بنابراين براي هر ويژگي پنج پارامتر تعريف مي‌شود که عبارتند از:

  • μx و μy: مختصات مرکز موجک Gabor که مرکز موجک مي‌تواند هر نقطه از تصوير 48×56 باشد.
  • λ: طول موج سيگنال سينوسي که يکي از مقادير مجموعه \left\{ {1,2,3,4,5,6,7,8,9,10,11,12} \right\} مي‌باشد.
  • θ: زاويه چرخش موجک، نشان‌دهنده جهت نوسانات موجک که يکي از مقادير مجموعه \left\{ {0,\frac{\pi }{8},\frac{\pi }{4},\frac{{3\pi }}{8},\frac{\pi }{2},\frac{{5\pi }}{8},\frac{{3\pi }}{4},\frac{{7\pi }}{8}} \right\} مي‌باشد.
  • w: ضريب وزن ويژگي که يک عدد در بازه (0,1] است.

مقادير λ و θ بر اساس مقادير مشابهي که در [4] و [5] پيشنهاد شده، استفاده گرديد. براي کاهش حجم محاسبات، از طبقه‌بندي‌کننده کوتاه‌ترين فاصله استفاده شد.

براي الگوريتم PSO پارامترهاي زير مورد استفاده قرار گرفت:

  • Number of Particles=100
  • w=0.2
  • C1=C2=2

همچنين، سعي شد براي الگوريتم ICA نيز پارامترهاي مشابهي انتخاب گردد. پارامترهاي انتخابي براي الگوريتم ICA به شرح زير است:

  • Number of Countries=100
  • Number of Imperialists=10
  • γ=45°
  • β=2

شرط پايان الگوريتم‌ها، اجراي 100 تکرار است. اين الگوريتم‌ها 10 مرتبه روي داده‌هاي مجموعه A اجرا شدند تا بهترين ويژگي‌ها را انتخاب نمايند.

 شکل 4: تغييرات مقدار برازش (دقت تشخيص چهره روي مجموعه A) بهترين جواب در هر نسل


شکل 5: تغييرات مقدار متوسط برازش (دقت تشخيص چهره روي مجموعه A) جواب‌ها در هر نسل

شکل 4 و شکل 5 به ترتيب نحوه تغيير ميزان برازش بهترين جواب و متوسط برازش جواب‌هاي هر نسل را نشان مي‌دهد. همانطور که مشاهده مي‌شود، سرعت همگرايي ICA بيشتر از PSO است. ضمن اينکه مقدار نهايي بهترين جواب پس از 100 نسل، در الگوريتم ICA بيشتر مي‌باشد. اين پديده را چنين مي‌توان توجيه کرد که در PSO بردار حرکت هر ذره، به طور تصادفي از برايند حرکت در راستاي بهترين مکاني که قبلا در آن بوده (LBest) و بهترين مکاني که قبلا در کل ذرات مشاهده شده (GBest)، تعيين مي‌گردد. اما در الگوريتم ICA، حرکت کشورها به سمت چند استعمارگر (چند جواب از بهترين جواب‌هاي بدست آمده تاکنون) است. بنابراين انتظار مي‌رود الگوريتم ICA قدرت جستجو و اکتشاف بيشتري داشته باشد و بتواند نسبت به ابگوريتم PSO، به جواب‌هاي بهتري دست يابد.

پس از پايان الگوريتم انتخاب ويژگي، براي بررسي کيفيت ويژگي‌هاي انتخاب شده، از بهترين ويژگي‌هاي انتخاب شده در نسل آخر، براي تشخيص چهره روي مجموعه B استفاده شد. در مجموعه B نيز براي هر کلاس دو تصوير وجود دارد: يک تصوير براي آموزش سيستم و يک تصوير براي آزمايش آن. آزمايش‌ها نشان داد که متوسط دقت تشخيص چهره با استفاده از ويژگي‌هاي انتخاب شده توسط الگوريتم PSO و ICA روي مجموعه B، به ترتيب برابر 86.6% و 90.2% است (جدول 1). مدت زمان متوسط سپري شده براي حل اين مسئله توسط PSO و ICA، تقريبا با هم برابر و حدود 6.5 بود.

جدول 1: دقت متوسط تشخيص چهره با استفاده از ويژگي‌هاي انتخاب شده توسط الگوريتم PSO و ICA

الگوريتم
PSO
ICA
دقت متوسط تشخيص چهره روي مجموعه A
96.2%
97.4%
دقت متوسط تشخيص چهره روي مجموعه B
86.6%
90.2%
5-1-    مقايسه نتايج
در اين بخش نتايج حاصل از تشخيص چهره با ويژگي‌هاي انتخاب شده و نتايج روش‌هاي مشابه تشخيص چهره از جمله روش انطباق گراف‌هاي خوشه‌اي کشسان (EBGM) [4] و روش پيشنهادي سيگاري [5] مقايسه و ارزيابي مي‌شوند.
روش EBGM توسط Wiskott و همکارانش [4] ارائه شد. در اين روش ابتدا 30 نقطه از چهره به کمک يک گراف کشسان از قبل تهيه شده، تعيين مي‌گردد. سپس در هر يک از اين نقاط ضرايب موجک Gabor براي 5 طول موج (λ) و 8 جهت (θ) مختلف محاسبه مي‌گردد. بنابراين براي هر چهره 1200 ويژگي استخراج شده . به کمک يک معيار شباهت، تشخيص چهره انجام مي‌گيرد. اين الگوريتم بر روي تصاوير روبه‌جلو از پايگاه داده FERET مورد ارزيابي قرار گرفت و دقت تشخيص آن 98% گزارش شده است.
سيگاري [5] براي انتخاب بهينه طول موج موجک Gabor از الگوريتم ژنتيک استفاده کرد. در اين الگوريتم تعداد نقاط روي چهره براي انتخاب ويژگي به 14 نقطه تقليل يافت و 6 مقدار به عنوان بهترين طول موج‌هاي (λ) مناسب موجک براي تشخيص چهره معرفي شد. در اين روش نيز از 8 جهت (θ) مختلف براي موجک Gabor استفاده شده است. به اين ترتيب براي هر چهره 672 ويژگي استخراج مي‌گردد. اين الگوريتم بر روي تصاوير روبه‌جلو از پايگاه داده FERET مورد آزمايش قرار گرفت و دقت 91% بدست آمد.
در مقاله فعلي، دو روش براي انتخاب ويژگي بر اساس الگوريتم‌هاي تکاملي ارائه شد که در اين روش‌ها، تعداد ويژگي‌هاي انتخاب شده به مراتب کمتر از روش‌هاي [4] و [5] است. براي ارزيابي ويژگي‌هاي استخراج شده از اين الگوريتم‌ها، از تصاوير روبه‌جلو پايگاه داده FERET استفاده شد.
جدول 2 مقايسه دقت تشخيص چهره بر اساس ويژگي‌هاي استخراج شده با روش‌هاي پيشنهادي و دو روش ديگر را نشان مي‌دهد.
جدول 2: مقايسه نتايج دقت تشخيص چهره بر اساس روش‌هاي پيشنهادي براي استخراج و انتخاب ويژگي و ساير روش‌هاي مشابه

نام روش
تعداد ويژگي براي هر چهره
دقت تشخيص چهره
روش EBGM [4]
1200
98%
روش پيشنهادي سيگاري [5]
672
91%
روش پيشنهادي با ويژگي‌هاي استخراج شده از الگوريتم PSO
50
86.6%
روش پيشنهادي با ويژگي‌هاي استخراج شده از الگوريتم ICA
50
90.2%

همان‌گونه که در جدول 2 مشاهده مي‌گردد، بهترين دقت تشخيص چهره مربوط به الگوريتم EBGM و معادل 98% است. البته در اين روش براي تشخيص چهره 1200 ويژگي از هر تصوير استخراج مي‌شود که اين تعداد ويژگي زياد است. در حالي که روش‌هاي پيشنهادي براي استخراج ويژگي، با تعداد ويژگي بسيار کمتر، توانسته‌اند دقت قابل قبولي را بدست آورند. به ويژه اينکه تعداد ويژگي‌هاي استخراج شده کمتر از 5% ويژگي‌هاي مورد استفاده در [4] مي‌باشد.

6-    نتيجه‌گيري و پيشنهادات
در اين مقاله به بررسي کاربرد الگوريتم ICA براي مسئله انتخاب ويژگي در سيستم تشخيص چهره پرداختيم و کارايي آن را با الگوريتم PSO مورد مقايسه قرار داديم. آزمايش‌هاي انجام شده براي انتخاب ويژگي در سيستم تشخيص چهره نتايج خوبي ارائه کرد و نشان داد با تعداد ويژگي‌هاي بسيار کمي مي‌توان به نرخ بازشناسي خوبي دست يافت. بر اساس اين آزمايش‌ها، به نظر مي‌رسد الگوريتم ICA نسبت به الگوريتم PSO توانايي بيشتري دارد. البته اين پديده تاحدودي قابل توجيه است، چرا که در PSO بردار حرکت هر ذره، به طور تصادفي از برايند حرکت در راستاي بهترين مکاني که قبلا در آن بوده (LBest) و بهترين مکاني که قبلا در کل ذرات مشاهده شده (GBest)، تعيين مي‌گردد. اما در الگوريتم ICA، حرکت کشورها به سمت چند استعمارگر (بهترين جواب‌هاي بدست آمده تاکنون) است. بنابراين انتظار مي‌رود الگوريتم ICA بتواند به جواب‌هاي بهتري نسبت به PSO دست يابد.
در اين پژوهش، با فرض معين بودن تعداد ويژگي، فقط به انتخاب بهترين ويژگي‌ها پرداختيم. براي کارهاي آينده پيشنهاد مي‌شود، راه‌کاري ارائه گردد تا بتوان با استفاده از اين دو الگوريتم، علاوه بر انتخاب بهترين ويژگي‌ها، تعداد بهينه ويژگي‌ها نيز مشخص گردد.
مراجع
[1] Esmaeil Atashpaz-Gargari, Caro Lucas, “Imperialist Competitive Algorithm: An Algorithm for Optimization Inspired by Imperialistic Competition”, IEEE Congress on Evolutionary Computation (CEC), Singapore, 4661-4667, 2007.
[2] J. Kennedy, R. Eberhart, “Particle Swarm Optimization”, IEEE International Conference on Neural Networks, Perth, Australia, 1942-1948, 1995.
[3] مصطفي مجيدپور، «بازشناسي چهره با الهام از فزيک روان و علوم اعصاب»، پايان‌نامه کارشناسي ارشد، دانشکده مهندسي برق و کامپيوتر، دانشگاه تهران، تهران، ايران، 1387.
[4] Laurenz Wiskott, Jean-Marc Fellous, Norbert Kruger, Christoph von der Malsburg, “Face Recognition by Elastic Bunch Graph Matching”, IEEE Transaction on Pattern Analysis and Machine Intelligence, vol. 19, no. 7, pp. 775-779, 1997.
[5] Mohamad Hoseyn Sigari, “Best Wavelength Selection for Gabor Wavelet using GA for EBGM Algorithm”, IEEE International Conference on Machine Vision, Pakistan, 35-39, 2007.
اطلاعات علمی مقاله

کاربرد الگوريتم رقابت استعماري براي انتخاب ويژگي در سيستم تشخيص چهره
محمدحسين سيگاري، کارو لوکس
قطب کنترل و پردازش هوشمند، دانشکده مهندسي برق و کامپيوتر، دانشگاه تهران
hoseyn_sigari@ieee.org, lucas@ut.ac.ir

دانلود نسخه کامل در قالب فایل پی دی اف
نسخه کامل این مقاله را به صورت فایل پی دی اف، در بخش مقالات فارسی الگوریتم رقابت استعماری در این لینک (“مقالات فارسی” الگوریتم رقابت استعماری (کلیک کنید)) دانلود کرده و مطالعه نمایید.
دانلود رایگان فیلم آموزشی توضیحات کامل در مورد این مقاله از زبان نویسنده
این مقاله در یکی از نشست های آنلابن اولین دوره وبینار محاسبات تکاملی نیز ارائه شده. در صورت تمایل به کسب اطلاعات بیشتر، فیلم کامل این نشست را از این لینک دانلود کرده و ببینید (فیلم: کاربرد الگوريتم رقابت استعماري در انتخاب ويژگي (Feature Selection))
0 پاسخ

دیدگاه خود را ثبت کنید

تمایل دارید در گفتگوها شرکت کنید؟
در گفتگو ها شرکت کنید.

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *