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

 Human Face Detection Using Genetic Algorithm

مقدمه

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

افزایش حملات تروریستی انگیزه آثار بیشماری در این بخش است. دوربین های امنیتی که در سوپرمارکت ها ،مراکز خرید ، مترو ، مرکز شهر ، پارک ها ، اتوبوس ها و …. قرار داده می شوند یک نمونه تلاش برای شناسایی مجرمین ودر نهایت کاهش جرم است.متاسفانه سیستم های امنیتی که با دخالت انسان کار می کنند اغلب در عملکردشان با مشکل مواجه می شوند.

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

تشخیص چهره

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

تکنیک های شناسایی چهره شامل سه روش عمده هستند:

1- روش هایی بر پایه ی خصوصیات ثابت

2- روش هایی بر پایه ی ظاهر

3- روش هایی بر پایه ی دانش

روش هایی برپایه ی دانش

این روش ها براساس دانش قبلی در مورد مسئله ، چهره را در تصویر شناسایی می کنند.یک مثال در این مورد روش هایی براساس Template ها است. که برای شناسایی اشیا آنها را براساس اجزای هندسی مثل دایره ، مربع یا مثلث بررسی می کنند.درمورد تشخیص چهره بیضی مناسب ترین نوع Template بشمار می رود.

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

1- ایجاد جمعیتی تصادفی به اندازه ی N از کروموزوم ها

2- محاسبه ی تابع fitness برای هر کروموزوم

3- ایجاد کروموزوم های جدید از طریق ترکیب کردن کروموزوم های انتخاب شده از این جمعیت ، به کار بردن ترکیب recombination و جهش mutation در این کروموزوم ها

4- از بین بردن اعضای قدیمی جمعیت ، به منظور ایجاد فضا برای کروموزوم های جدید و درج آنها و همچنین ثابت ماندن مقدار N از جمعیت ( جمعیت به اندازه ی N ثابت بماند و تغییر نکند)

5- اعمال fitness ( مقدار برازندگی ) در این کروموزم های جدید و درج آنها در جمعیت

6- در صورتی که راه حل مطلوب پیدا شود یا اگر زمان (تعداد نسل ) تهی شد ، کروموزوم با بهترین fitness برگردانده می شود در غیر این صورت به گام سوم برمی گردیم.

تابع fitness

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

انتخاب

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

تولید مثل

کروموزوم جدید از ترکیب دو کروموزوم قبلی به وجود می آید.این فرآیند به دو پارامتر ( دو کروموزوم ) که اپراتور یا عملگر پیشنهاد می کند بستگی دارد. این عملگر همان crossover یا احتمال نوترکیب است که با pc نمایش داده می شود.همچنین ممکن است عمل جهش در کروموزوم جدید به وجود آید که با pm نشان داده می شود.برای شروع معمولا مقدار pc بین 1 تا 1.5 و مقدار pm بین 0.001 تا 0.02 در نظر گرفته میشود.

الگوریتم ژنتیک در تشخیص چهره

در زیر یک سیستم جدید برای شناسایی چهره با استفاده از الگوریتم ژنتیک پیشنهاد شده است که به دو بخش تقسیم می شود:

1- پیش پردازش

2- کاربرد الگوریتم ژنتیک

مرحله ی پیش پردازش

این مرحله شامل سه گام اساسی است : 1- کاهش اندازه ی تصویر : اندازه ی تصویر اصلی در حدود 256*256 پیکسل است این اندازه باید به حدود 128*128 پیکسل کاهش داده شود. 2- کاهش نویز : برای کاهش نویز در تصویر از فیلتر میانه با ماسک 3*3 استفاده شده است. 3- تشخیص لبه ها : برای شناسایی لبه ها در تصویر از عملگر سوبل استفاده شده که نتیجه ی حاصل از آن یک تصویر باینری است ، پیکسل های سفید لبه ها و پیکسل های سیاه پس زمینه ی تصویر است.

کاربرد الگوریتم ژنتیک

بعد از انجام مراحل پیش پردازش ، امکان استفاده از الگوریتم ژنتیک فراهم می شود که اساسا شامل جستجو برای پیدا کردن شی ای شبیه بیضی با نسبت تناسب 1.5:1 در تصویر است. ( قبلا ذکر کردیم که Templateچهره شبیه به بیضی است ) که احتمالا چهره ی شخص باشد.

در این مورد individual ها بیضی هایی هستند که به صورت باینری نوشته می شوند.با فرض این که هر individual در حدود 4 کروموزوم دارد که به ترتیب : مکان x ، مکان y ، نسبت x و نسبت y است. این کروموزوم ها در الگوریتم ها ی معمولی همان متغییر ها برای مختصات بیضی هستند اما در الگوریتم ژنتیک این کروموزوم ها از تنها یک individual ساخته می شوند. اندازه ی هر کروموزوم در حدود 7 بیت است که نمونه ی آن را در تصویر زیر مشاهده می کنید.

اولین گام تولید جمعیت اولیه با تعداد 100 ، individual است. هر individual به صورت تصادفی و با محدودیت ( x و y باید در اندازه گیری متناسب از 1.5:1 باشند ) نه محدودیت در مورد اندازه و موقعیت بیضی ساخته شده ، ایجاد می شود چرا که چهره در تصویر می تواند بزرگ یا کوچک باشد.

تعداد پیکسل های سفید در تصویر پیش پردازش شده را NA قرار می دهیم و تعداد پیکسل های سفید در تصویر individual را NB می نامیم ، بنابراین تابع fitness به صورت : NA/NB تعریف می شود.

فرایند انتخاب به صورت خودکار انجام می شود بدون استفاده از تطابق یا رولت روش ، برای مثال تعداد 20 عدد individual با مقدار fitness خیلی بزرگ برای تولید مثل انتخاب شد، اما با 20 individual مفهوم تولید مثل تنها برای 20 عدد individual جدید دیگر ممکن است چرا که جفت ها بین خودشان مبادله می شوند. تولید مثل از دونقطه به وجود می آید و این نقاط به صورت تصادفی انتخاب می شوند بعد از فرایند تولید مثل ممکن است کروموزوم جدید دچار mutation یا جهش شود این فرایند این قدر تکرار میشود تا حدود 150 نسل به وجود آید هر نسل با 100 عدد individual و در پایان individual ایی که بالاترین مقدار fitness را داشته است به عنوان احتمال وجود چهره در این ناحیه از تصویر مشخص می شود.

نتایج

وضوح تصاویر مورد آزمایش در حدود 256*256 پیکسل بود، همه ی تصاویر در فرمت JPG فشرده سازی شده بودند.در مورد تصاویر با پس زمینه ی غیر پیچیده ، الگوریتم عملکرد قابل قبولی داشت حتی اگر چهره شامل ریش ، سیبیل ، موی بلند ، عینک و غیره باشد.اما مواردی که پس زمینه ی تصویر پیچیده باشد الگوریتم کارآمد نخواهد بود. با توجه به این واقعیت که الگوریتم همیشه هر پیکسل از تصویر را مقایسه می کند بنابراین سرعت آن کند است.روند تشخیص چهره با اجرا در متلب 7 در یک کامپیوتر با پردازنده ی 1.8 GHZ و 256 مگابایت رم در حدود 3 دقیقه طول می کشد.

نتیجه گیری

در این مقاله یک روش برای تشخیص چهره ی انسان پیشنهاد شد ، الگوریتم برای تصاویری با پس زمینه ی ساده ( غیر پیچیده) عملکرد مناسبی داشت یقینا ، الگوریتم ژنتیک می تواند برای حل مسائل پیچیده در بینایی ماشین و غیره استفاده شود.