بازشناسی چهره

تغییرات پروژه از تاریخ 1394/11/05 تا حالا
**تعریف مسأله**: مسأله بازشناسی چهره [^Face recognition] و مکانیزم کلی عملکرد آن در این پروژه را می توان در این قالب بیان نمود: عکسی از یک چهره به عنوان ورودی و برای تست و یک مجموعه عکس از چهره‌ها جهت آموزش به سیستم داده می‌شود؛ چگونه می‌توان عمل تطبیق تصویر ورودی را با نمونه‌های آموزشی موجود در سیستم انجام داد و چگونه می‌توان تشخیص داد که عکس ورودی، چهره کدام یک از اعضای نمونه است؟

----------

#** مقدمه**

موضوع بازشناسی چهره اساساً یکی از مسائل چالش برانگیز در حوزه مباحث مرتبط با پردازش تصویر و بینایی کامپیوتر در عصر حاضر بوده است و کاربردهای فراوان و کلیدی آن در حوزه های مختلف باعث توجه بیش از پیش به این موضوع در سالهای اخیر گردیده است.
اساساً بکارگیری تکنیک‌های بایومتریکی [^Bio-metrics] در موضوع احراز هویت اشخاص از مؤثرترین و کارآمدترین روش ها می‌باشد. در حقیقت بجای آن که برای احراز هویت افراد جهت دادن دسترسی‌های خاص فیزیکی یا غیرفیزیکی به آنها از رمز عبور، پین کد، کارت‌های هوشنمد، توکن، کلید و ... استفاده شود، از روش‌هایی که اصطلاحاً از آنها تحت عنوان روش‌های بایومتریکی یاد می‌شود، استفاده می‌گردد که در آن با نمونه برداری از حالات فیزیکی یا رفتاری شخص، هویت وی بررسی می‌شود.
بطور کلی می‌توان گفت که همیشه عمل احراز هویت بصورت مکانیزه به سه روش کلی و یا ترکیبی از این سه روش انجام می‌پذیرد [1]:

1. Password, PIN, ... [**What you know**]
2. Smart Card,Token, ... [**What you have**]
3. Bio-metric elements [**What you are**]

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

روش‌های احراز هویت بایومتریکی، خود شامل شناسایی بر اساس ویژگی‌های فیزیکی (مثل چهره، اثر انگشت، کف دست، رگ‌های دست، قرنیه، شبکیه، گوش و صدا) و ویژگی‌های رفتاری (مثل راه رفتن، امضا و ...) هستند که روش بازشناسی چهره از مزیت های بیشتری نسبت به روش‌های دیگر برخوردار است که در ادامه به آنها اشاره می‌شود.
در مقام اجرا، تقریبا تمامی این تکنولوژی‌های بایومتریکی نیاز به انجام عمل خاصی از طرف کاربر دارند؛ مثلاً نیاز است کاربر کف دست خود را بر روی اسکنر مربوطه قرار دهد یا برای اسکن قرنیه یا شبکیه چشم خود در یک موقعیت خاص روبه روی دوربین قرار بگیرد در صورتی که برای بازشناسی چهره نیازی به انجام کار خاصی نیست چون عکس‌برداری از چهره از فاصله دور یا حتی در حال حرکت نیز امکان پذیر است.
همچنین روش هایی که در آن از کاربر درخواست ورود اطلاعات می شود دارای مشکلاتی هستند. احتمال آسیب دیدن بافت اپیدرمی اسکنرهای دست و انگشت یا شکستن صفحه اسکنر آن وجود دارد. روش اسکن قرنیه و شبکیه نیز به تجهیزات گران قیمت نیاز دارد و تجهیزات آن ازحساسیت زیادی برخوردار هستند. صدای انسان نیز ممکن است در نویز محیط گم شود و کیفیت و اصالت خود را از دست بدهد یا برای فریب سیستم احراز هویت از صدای ضبط شده یا ارتباط تلفنی استفاده شود اما عکسبرداری از چهره به سادگی و با یک دوربین ارزان قیمت امکان پذیر است. یک الگوریتم خوب برای بازشناسی چهره و یک پیش پردازش مناسب روی
عکسها مشکلاتی نظیر نویز در تصویر یا مشکلات نور، زاویه و ... تا حد زیادی برطرف می کند. در آخر می توان گفت یکی دیگر از مهمترین مزایای روش بازشناسی چهره نسبت به سایر روش های بایومتریک عدم نیاز به تماس فیزیکی کاربران با سنسور مربوطه است که این خود باعث جلوگیری از انتقال میکروب و بعضی بیماری‌های که نتیجه تماس فیزیکی هستند، می‌شود.[2] البته در مسیر پیاده‌سازی و بکارگیری روش بازشناسی چهره چالش‌هایی وجود دارد که در بخش بعدی به آن‌ها می‌پردازیم.

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

##فرضیات و اهداف

برخی از رویکردها، ساختار یک سیستم بازشناسی چهره را مشتمل بر سه گام اصلی زیر می دانند: [3]

![شکل1-1: فرآیند کامل تشخیص و بازشناسی چهره](https://boute.s3.amazonaws.com/208-face.jpg)

که البته موضوع سند حاضر، بررسی گام دوم و سوم یعنی استخراج ویژگی‌های مختص یک چهره و بازشناسی چهره می‌باشد و فرض بر این است که مرحله تشخیص چهره[^Face detection] از بین عناصر مختلف موجود در یک عکس، قبلاً و با الگوریتم‌های مرتبط انجام گرفته است.
در این پروژه تصمیم بر این است که در مورد انگیزه بکارگیری این تکنولوژی، کاربردهای مهم آن و برخی چالش‌های سیستم‌های مبتنی بر این تکنولوژی مطالبی ارایه شود. همچنین در ادامه بحث به معرفی اجمالی برخی الگوریتم‌های شناخته شده در این حوزه بپردازیم و مبتنی بر یکی از آن ها عملیات پیاده‌سازی، آزمایش و بهبود نتایج را انجام دهیم.


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

##روش HMM مبتنی بر مدل
در میان روش‌های مختلف بازشناسی چهره یا بررسی هویت بر اساس چهره، که به سه دسته کلی روش‌های مبتنی بر ویژگی‌های هندسی، الگو و مدل تقسیم می‌شوند، روش‌های مبتنی بر مدل در مقابل تغییرات شدت و جهت تابش نور، چرخش و مقیاس تصویر، تغییر حالات صورت و مدل مو انعطاف پذیری بیشتری به نمایش گذارده اند که نتیجه استفاده از یک مدل ریاضی ـ آماری، برای ترکیب نمونه‌های گوناگون تصویر در مقیاس‌ها و چرخش‌های مختلف است.  [^Hidden Markov Model]HMM که یک روش مبتنی بر مدل است، نسبت به تغییر وضعیت چهره، تغییر موی صورت (ریش و سبیل)، شرایط نوری متفاوت، چرخش محدود صورت (تا 22/5 درجه) و تغییر سایز تصویر حساس نمی‌باشد.[4]

##روش‌ PCA
روش [^Principal Components Analysis]PCA شامل دو فاز آموزش و طبقه بندی است. در طی این دو فاز تصاویر آموزشی (تصاویری که به عنوان تصاویر موثق در اختیار سیستم قرار می‌گیرد) مبتنی بر تکنیک‌های PCA به نحو مطلوبی و با توجه به ویژگی‌های خود طبقه بندی خواهند شد. این روش در سال 1991 توسط Turk و Pentland پیشنهاد شد که از تحلیل المان‌های اصلی یا همان PCA برای کاهش بعد استفاده کرده‎ تا بتواند زیرفضایی با بردارهای متعامد پیدا کند که در آن زیرفضا پراکندگی داده‌ها را به بهترین حالت نشان دهد. این زیرفضا را هنگامی که بر روی داده‌های چهره اعمال شوند، فضای چهره می‌گویند. پس از مشخص شدن بردارها تمامی تصاویر به این زیر فضا منتقل می‌‏‏شوند تا وزن‌هایی که بیانگر تصویر در آن زیرفضا هستند بدست آیند. با مقایسه شباهت وزن‌های موجود با وزن تصویر جدیدی که به این زیر فضا منتقل شده می‏‏توان تصویر ورودی را شناسایی کرد.
با نمایش برداری چهره‌ی انسان که توسط کنار هم قرار دادن سطرهای ماتریس تصویر حاصل می‌شود می‌توان چهره‌ی انسان را برداری در فضایی با ابعاد بالا در نظر گرفت. با توجه به خصوصیات مشابه چهره‌ها، می‌توان نتیجه گرفت که بردار چهره‌ها در زیرفضایی با ابعاد پایین‌تر واقع شده‌اند. با نگاشت چهره به این زیر فضا می‌توان تصاویر پایه‌ی جدیدی به دست آورد که هر چهره با کمک این بردارهای پایه توصیف می‌شود. در واقع هر چهره ترکیب خطی این تصاویر پایه می‌باشد .ضرایب این ترکیب خطی به عنوان بردار خصیصه مورد استفاده قرار می‌گیرند.
در این روش یک تصویر با ابعاد n*m به یک بردار با nm مؤلفه تبدیل می‌شود. یعنی می‌توان عکس را به صورت نقطه‌ای در فضای nm بعدی تصور کرد. هدف PCA یافتن بردارهایی است که به بهترین نحو ممکن کار شناسایی زیر فضا را انجام دهند. این بردارها فضای چهره را تعریف می‌کنند. از آنجایی که این بردارها، بردار ویژه‌ی ماتریس همبستگی مربوط به تصاویر چهره می‌باشند و همچنین به دلیل شباهت به چهره‌ی انسان، آن ها را Eigenface می‌نامند. [17]
![شکل 1-2: یک نمونه Eigenface](http://8pic.ir/images/5mdeibwmq3xz3j36xbx9.png)


##روش [^Linear Discriminant Analysis]LDA
از جمله روش‌های آماری‌ای است که در یادگیری ماشین و بازشناخت الگو برای پیدا کردن ترکیب خطی خصوصیاتی که به بهترین صورت دو یا چند کلاس از اشیارا از هم جدا می‌کند، استفاده می‌شوند. LDA ارتباط نزدیکی با تحلیل واریانس و تحلیل رگرسیون دارد که سعی دارند یک متغیر مستقل را به عنوان ترکیبی خطی از ویژگی های دیگر بیان کنند. این متغیر مستقل در LDA به شکل برچسب یک کلاس است. همچنین LDA ارتباطی تناتنگ با تحلیل مولفه های اصلی PCA دارد. چرا که هر دو متد به دنبال ترکیبی خطی از متغیرهایی هستند که به بهترین نحو داده ها را توصیف می کنند. LDA همچنین سعی در مدلسازی تفاوت بین کلاس های مختلف داده ها دارد. از LDA زمانی استفاده می شود که اندازه های مشاهدات، مقادیر پیوسته باشند.[14]

##  روش [^Elastic Bunch Graph Matching]EBGM
این روش عمل بازشناسی اشیا و کلاس آن‌ها را با استفاده از گراف استخراج شده از اشیاء دیگر از همان دسته انجام می‌دهد. این الگوریتم علاوه بر اشیاء در مورد چهره انسان و در حوزه بازشناسی چهره نیز کاربرد دارد.[15]
![شکل 2-2: ساخت گراف از حالات یک چهره](http://8pic.ir/images/tvbjrk58e10quvtmvyhe.png)

##روش [^Active Appearance Model]AAM
این روش یک مدل دستی از نقاط مهم و ویژگی‌های مهم تصاویر چهره انجام می‌دهد و برای شناسایی، اقدام به فیت کردن مدل ساخته شده بر روی تصاویر ورودی می کند. مدل ساخته شده با استفاده از تصاویر آموزشی Deform شده و ویژگی نهایی برای کلاس‌بندی فاصله و دقت، در مرحله سوار کردن مدل بر روی چهره می‌باشد. همچنین از مدل کم‌شهرت Lucas canade برای تحقق این مرحله استفاده می‌شود. [16]

## روش SIFT
توصیفگر [^Scale Invariant Feature Transform]SIFT امروزه به عنوان یکی از بهترین و قدرتمندترین ابزارها برای استخراج نقاط کلیدی غیر حساس به شرایط مختلف مانند چرخش، بزرگنمایی، تغییر نمای دید، نویز، نورپردازی و تبدیل کشیدگی است. به طور کلی مراحل استفاده از این الگوریتم را می‌توان به 3 قسمت اصلی زیر تقسیم نمود:[11]
1. یافتن نقاط کلیدی
2. نمایش توصیفگر نقاط کلیدی
3. تطبیق بردارهای ویژگی

## روش خوشه‌بندی کاهشی[^Subtractive Clustering]
در مواقعی که دیدگاه واضحی از تعداد خوشه‌هایی که بایستی برای مجموعه داده‌ای مشخص شود، وجود نداشته باشد این الگوریتم روشی سریع برای یافتن تعداد خوشه‌ها و همچنین مراکز آنها محسوب می‌شود. گاهی اوقات مراکزی که توسط این روش تخمین زده شده‌اند به عنوان نقاط اولیه برای دیگر الگوریتم‌های
خوشه‌بندی مورد استفاده قرار می‌گیرند. این تکنیک از آن جهت بکار گرفته شده است که بتواند نقاط کلیدی یا نمونه‌های متمایز را از میان انبوهی از رکوردهای مجموعه داده‌ها که هر رکورد حاوی ویژگی‌های یک نقطه کلیدی است، استخراج نماید.[12]

##روش SVM
الگوریتم [^Support Vector Machines]SVM  اولیه در ۱۹۶۳ توسط Vladimir Vapnik ابداع شد و در سال ۱۹۹۵ توسط Vapnik و Corinna Cortes برای حالت غیرخطی تعمیم داده شد. ماشین بردار پشتیبانی [^SVM] یکی از روش‌های یادگیری با نظارت [^Supervised learning] است که از آن برای طبقه‌بندی و رگرسیون استفاده می‌کنند.
این روش از جمله روش‌های نسبتاً جدیدی است که در سال‌های اخیر کارایی خوبی نسبت به روش‌های قدیمی‌تر برای طبقه‌بندی از جمله شبکه‌های عصبی پرسپترون نشان داده است. مبنای کاری دسته‌بندی کننده SVM دسته‌بندی خطی داده‌ها است و در تقسیم خطی داده‌ها سعی می‌کنیم خطی را انتخاب کنیم که حاشیه اطمینان بیشتری داشته باشد. حل معادله پیدا کردن خط بهینه برای داده‌ها به وسیله روش‌های [^Quadratic Programming]QP که روش‌های شناخته شده‌ای در حل مسائل محدودیت‌دار هستند صورت می‌گیرد.
الگوریتم SVM از یک تکنیک که kernel trick نامیده می شود، برای تبدیل داده‌ها استفاده می‌کند و سپس بر اساس این تبدیل، مرز بهینه بین خروجی‌های ممکن را پیدا می‌کند. به عبارت ساده تبدیلات بسیار پیچیده را انجام می‌دهد، سپس مشخص می‌کند چگونه داده‌هایتان را بر اساس برچسب‌ها یا خروجی‌هایی که تعریف کرده اید، جدا کنید.
لذا یکی از روش‌هایی که در حال حاضر به صورت گسترده برای مسئله دسته‌بندی [^Classification]مورد استفاده قرار می گیرد، روش ماشین بردار پشتیبان است. شاید به گونه ای بتوان محبوبیت کنونی روش ماشین بردار پشتیبان را با محبوبیت شبکه‌های عصبی در دهه گذشته مقایسه کرد. علت این قضیه نیز قابلیت استفاده این روش در حل مسائل گوناگون می‌باشد، در حالیکه روش‌هایی مانند درخت تصمیم‌گیری را نمی‌توان به راحتی در مسائل مختلف بکار برد.[18].[19]

###آشنایی با مفهوم دسته بندی
فرض کنید مجموعه داده ای داریم که ۵۰٪ افراد آن مرد و ۵۰٪ افراد آن زن هستند. این مجموعه داده می تواند مشتریان یک فروشگاه آنلاین باشد. با داشتن یک زیرمجموعه از این داده ها که جنسیت افراد در آن مشخص شده است، می خواهیم قوانینی ایجاد کنیم که به کمک آنها جنسیت بقیه افراد مجموعه را بتوانیم با دقت بالایی تعیین کنیم. تشخیص جنسیت بازدیدکنندگان فروشگاه، باعث می شود بتوانیم تبلیغات جداگانه‌ای را برای زنان و مردان نمایش دهیم و سودآوری فروشگاه را بالا ببریم. این فرآیند را در علم تحلیل داده، دسته‌بندی می‌نامیم.

برای توضیح کامل مسأله، فرض کنید دو پارامتری که قرار است جنسیت را از روی آنها تعیین کنیم، قد و طول موی افراد است. نمودار پراکندگی قد و طول موی افراد در زیر نمایش داده شده است که در آن جنسیت افراد با دو نماد مربع (مرد) و دایره (زن) به طور جداگانه نمایش داده شده است.
![شکل 3-2: نمودار پراکندگی قد و طول موی افراد](http://8pic.ir/images/iyliv6btz9d5u5pt2hyd.png)

با نگاه به نمودار فوق، حقایق زیر به سادگی قابل مشاهده است :
1.   مردان در این مجموعه، میانگین قد بلندتری دارند.
2.   زنان از میانگین طول موی بیشتری برخوردار هستند.

اگر یک داده جدید با قد ۱۸۰cm و طول موی ۴cm به ما داده شود، بهترین حدس ماشینی ما برای این شخص، دسته مردان خواهد بود.

###بردارهای پشتیبان و ماشین بردار پشتیبان

بردارهای پشتیبان به زبان ساده، مجموعه ای از نقاط در فضای n بعدی داده ها هستند که مرز دسته ها را مشخص می کنند و مرزبندی و دسته بندی داده‌ها براساس آنها انجام می شود و با جابجایی یکی از آنها، خروجی دسته‌بندی ممکن است تغییر کند. به عنوان مثال در شکل فوق ، بردار (۴۵,۱۵۰) عضوی از بردار پشتیبان و متعلق به یک زن است. در فضای دوبعدی،‌ بردارهای پشتیبان، یک خط، در فضای سه بعدی یک صفحه و در فضای n بعدی یک ابر صفحه را شکل خواهند داد. یا ماشین بردار پشتیبان، مرزیست که با داشتن بردارهای پشتیبان، بهترین دسته‌بندی و تفکیک بین داده‌ها را برای ما مشخص می کند.

در SVM فقط داده‌های قرار گرفته در بردارهای پشتیبان مبنای ماشینی و ساخت مدل قرار می‌گیرند و این الگوریتم به سایر نقاط داده حساس نیست و هدف آن هم یافتن بهترین مرز در بین داده ‌است به گونه‌ای که بیشترین فاصله ممکن را از تمام دسته‌ها (بردارهای پشتیبان آنها) داشته باشد.

###چگونه یک ماشین بر مبنای بردارهای پشتیبان ایجاد کنیم؟

به ازای داده‌های موجود در مثال فوق، تعداد زیادی مرزبندی می توانیم داشته باشیم که سه تا از این مرزبندی‌ها در زیر نمایش داده شده است.
![شکل 4-2: سه حالت ممکن مرزبندی](http://8pic.ir/images/ywb416k7nmsomp8ag5i5.png)
سوال اینجاست که بهترین مرزبندی در این مسأله کدام خط است؟

یک راه ساده برای انجام این کار و ساخت یک دسته‌بندی بهینه، محاسبه فاصله‌ی مرزهای به دست آمده با بردارهای پشتیبان هر دسته (مرزی‌ترین نقاط هر دسته یا کلاس) و در نهایت انتخاب مرزیست که از دسته های موجود، مجموعاً بیشترین فاصله را داشته باشد که در شکل فوق خط میانی ، تقریب خوبی از این مرز است که از هر دو دسته فاصله‌ی زیادی دارد. این عمل تعیین مرز و انتخاب خط بهینه (در حالت کلی، اَبَر صفحه مرزی) به راحتی با انجام محاسبات ریاضی نه چندان پیچیده قابل پیاده‌سازی است.

### توزیع غیر خطی داده‌ها و کاربرد ماشین بردار پشتیبان

اگر داده‌ها به صورت خطی قابل تفکیک باشند، الگوریتم فوق می تواند بهترین ماشین را برای تفکیک داده‌ها و تعیین دسته یک رکورد داده، ایجاد کند اما اگر داده‌ها به صورت غیر خطی توزیع شده باشند (مانند شکل زیر)، SVM را چگونه تعیین کنیم؟
![(شکل 5-2: حالتی از توزیع غیر خطی داده‌ها)](http://8pic.ir/images/bisgrwhbynwzvy6llowq.png)
در این حالت، ما نیاز داریم داده‌ها را به کمک یک تابع ریاضی (Kernel functions) به یک فضای دیگر ببریم (نگاشت کنیم) که در آن فضا، داده‌ها تفکیک‌پذیر باشند و بتوان SVM آنها را به راحتی تعیین کرد. تعیین درست این تابع نگاشت در عملکرد ماشین بردار پشتیبان موثر است که در ادامه به صورت مختصر به آن اشاره شده است. با فرض یافتن تابع تبدیل برای مثال فوق،‌ فضای داده ما به این حالت تبدیل خواهد شد:
![شکل 6-2: نتیجه اثر تابع نگاشت](http://8pic.ir/images/ldiugcnw93q6o561nf48.png)



##روش [^Histogram of Oriented Gradients]HoG
روش هیستوگرام گرادیان‌هـای جهـت‌دار در سـال 2005  توسط Dalal و Triggs برای تشخیص انسان معرفی شد و تاکنون در کاربردهایی از جمله تشخیص و بازشناسی اشـیاء بکار رفته است.[8] Albiol و همکارانش از ایـن ویژگـی بـرای بازشناسی چهره استفاده کرده‌اند. [9 ] آن ها با ترکیب ایـن ویژگـی و تطابق گراف کشسان (EBGM)، نقاط خاص چهره را یافتـه و بـا اعمال HoG در یک همسایگی از این نقاط، مسئله‌ی بازشناسـی چهره را مورد بررسی قرار داده‌اند. Deniz و همکارانش [10] نیـز بازشناسی چهره را با استفاده از HoG انجام داده‌اند. آن‌ها HoG را در یک شبکه منظم که کل چهـره را مـی‌پوشـاند، محاسـبه کرده و سپس با استفاده از روش‌های کاهش بعـد ماننـد PCA و LDA، به بازشناسی چهره پرداخته‌اند.
ایده‌ی اصلی در روش HoG این است که توزیع گرادیان‌های محلی یا جهت‌های لبه می‌تواند به خوبی شکل را توصـیف کنـد، حتی اگر اطلاعی از موقعیت دقیق گرادیان و یا لبه‌ی متناظر نداشته باشیم. این ویژگی، جهت گرادیان‌های تصویر را در یک همسایگی محلی نشان می‌دهد. هر کدام از این همسایگی‌ها یک سلول[^Cell] نام دارند. بسته به این که گرادیان را بدون علامت یا علامت‌دار در نظر بگیریم، فاصله‌ی بین 0-180 درجه یا 0-360 درجه به n فاصله‌ی مساوی تقسیم می‌شود که n تعداد جهت‌های گرادیان یا همان بین‌های هیستوگرام را نشان می‌دهد و هر کدام از این فاصله‌ها یک کانال هیستوگرام را تشکیل می‌دهند.

![شکل 7-2: نمونه اجرای الگوریتم HoG بر روی یک عکس](http://8pic.ir/images/1oz6qz6h6d9sdroxpzxu.png) در هر سلول، هیستوگرام جهت‌های گرادیان برای پیکسل‌های داخل سلول محاسبه می‌شود. سپس برای مقاومت در برابر تغییرات روشنایی، هیستوگرام چند سلول مجاور که با هم تشکیل یک بلوک را می‌دهند، نرمالیزه می‌شود. این هیستوگرام نرمالیزه شده، هیستوگرام گرادیان‌های جهت‌دار نامیده می‌شود. 
![شکل 8-2: فرآیند اجرای الگوریتم HoG](http://8pic.ir/images/y557cfo0eqzh6i3nsfxb.png)
بلوک‌ها را می‌توان بصورت ناهمپوشان یا همپوشان انتخاب کرد. معمولاً بلوک‌های همپوشان انتخاب می‌شوند. با این که در این حالت طول بردار ویژگی افزایش می‌یابد ولی در این صورت دقت عملکرد بهبود پیدا می‌کند. برای تصاویر رنگی، گرادیان برای هر کانال رنگی بصورت جداگانه محاسبه می‌شود و بزرگترین مقدار برای هر پیکسل بعنوان بردار گرادیان آن پیکسل انتخاب می‌شود.[13]
همچنین انتخاب مناسب اندازه سلول‌ها می‌تواند نقش بسزایی در ایجاد دقیق‌تر بردارهای گرادیان و در نتیجه بهبود عملکرد الگوریتم ایفا کند.
![شکل 9-2: سلول با اندازه‌های متفاوت](http://8pic.ir/images/h6hv8k7oean4qb62y8u2.png)

# **آزمایش‌ها**
در قسمت پیاده‌سازی از کتابخا‌نه جامع opencv و از الگوریتم‌های HoG و SVM که به ترتیب برای «استخراج ویژگی‌ها» و «دسته‌بندی و یادگیری» کاربرد دارند، استفاده شده است.
دیتاسِت[^DataSet] مورد آزمایش مربوط به لابراتور کامپیوتر دانشگاه کمبریج می‌باشد که شامل 40 مجموعه و هر مجموعه شامل 10 عکس از یک فرد خاص می‌باشد که در زوایای مختلف از چهره آن فرد عکسبرداری شده است. ([دریافت دیتاسِت)](http://www.cl.cam.ac.uk/research/dtg/attarchive/facedatabase.html)
![شکل 1-3: نمونه دیتاسِت مورد آزمایش](http://8pic.ir/images/mkrq8w0huoc6fnu4ujy6.gif)
##فرضیات آزمایش
از میان 10 عکس مربوط به هر شخص، 3 عکس در هر مجموعه را برای تست اختصاص داده‌ایم و آنها را به سیستم یاد نمی‌دهیم. یعنی پس از آموزش 7 تصویر از هر شخص به سیستم، به مرحله تست می رویم و از 3 عکس باقیمانده استفاده و آنرا بعنوان ورودی به سیستم می‌دهیم و توقع داریم سیستم بطور صحیح تصویر ورودی را بیاد آورد و تشخیص دهد که متعلق به کدام یک از مجموعه‌ها بوده است.

##نتیجه آزمایش
**ورودی سیستم جهت آموزش**: 280 عکس چهره از 40 فرد مختلف.(هر فرد 7 عکس، از زوایای مختلف) 
**ورودی سیستم جهت تست**: 120 عکس چهره از مجموعه دیتاسِت.(حالت‌هایی از چهره افراد که آن حالت‌ها جهت یادگیری به سیستم داده نشده بودند)
**خروجی سیستم**: تعداد 114 عکس به درستی توسط سیستم به یادآورده شدند و در دسته مطلوب خود جای گرفتند.6 عکس در دسته نامرتبط قرار گرفتند.

|الگوریتم‌های مورد استفاده|تعداد کل نمونه آموزشی|تعداد نمونه برای تست|تعداد تشخیص‌های صحیح|تعداد تشخیص‌های نادرست|دقت نهایی|
|:---------|:------:|:------:|:------:|:------:|:------:|
| HoG و SVM|280|120|114|6|95%|

در عکس زیر که نتیجه آزمایش را نشان می‌دهد می‌بینیم که در 6 مورد (برای 6 عکس ورودی) سیستم نتوانسته است گروه آن‌ها را به درستی تشخیص دهد (برای مشاهده اندازه اصلی عکس بر روی آن کلیک کنید).

[![شکل2-3: نتایج حاصل از آزمایش. جایگیری 6 عکس در دسته‌های نامرتبط.](http://8pic.ir/images/1h3kl9xsjwl8kx38xwxs.png)](http://8pic.ir/images/1h3kl9xsjwl8kx38xwxs.png)

##بهبود نتایج
برای بهبود نتایج آزمایش قبلی، متوجه شدیم که اگر اندازه Block stride که شامل چندین Block  size است [20] را در مرحله‌ای که از الگوریتم HoG استفاده می‌کنیم کوچکتر نماییم، می‌توانیم به نتایج دقیق‌تری برسیم. به‌عبارتی دیگر اگر اندازه Block Stride را کوچکتر بگیریم، یعنی به جزئیات بیشتری توجه کردیم. عملاً کاری که در پیاده سازی صورت گرفت این بود که اندازه Block stride و Block size با هم برابر در نظر گرفته شد. بنابراین در هر  Block stride، یک Block size قرار گرفت و با توجه به ساختار دیتاست و سبک رنگ‌بندی و استایل عکس‌های موجود در آن، این روش موجب شد تا دقت بازشناسی و دسته بندی صحیح عکس‌ها را تا 99% افزایش دهیم. این نکته نیز قابل ذکر است که امکان تغییر اندازه سلول وجود نداشت زیرا در OpenCV 2.4 تنها از اندازه 8*8 پیکسل برای سلول‌های HoG پشتیبانی می‌شود [20].

|الگوریتم‌های مورد استفاده|تعداد کل نمونه آموزشی|تعداد نمونه برای تست|تعداد تشخیص‌های صحیح|تعداد تشخیص‌های نادرست|دقت نهایی|
|:---------|:------:|:------:|:------:|:------:|:------:|
| HoG و SVM|280|120|119|1|99.17%|

در عکس زیر که نتیجه آزمایش بهبود یافته را نشان می‌دهد می‌بینیم که تنها در یک مورد (برای یک عکس ورودی) سیستم نتوانسته است گروه آن را به درستی تشخیص دهد (برای مشاهده اندازه اصلی عکس بر روی آن کلیک کنید).
[![شکل3-3: نتایج حاصل از دسته‌بندی عکس‌ها در گروه‌های خود پس از بزرگ کردن اندازه سلول‌ها. جایگیری 1 عکس در دسته نامرتبط.](http://8pic.ir/images/o6ilg1j5ri5zil4u9tre.png)](http://8pic.ir/images/0q5qx5hiolk5fc1c608t.png)

پیاده‌سازی‌های «اولیه» و «بهبود یافته» از طریق [این صفحه](https://github.com/mhrah/face_recog) قابل دسترسی هستند.

# **کارهای آینده**
روش‌های اشاره شده همگی دارای دقت شناسایی بالا و تعداد تشخیص اشتباه (FP) کم بوده‌اند. با این حال، همگی آنها نیاز به بیش از چندین ثانیه برای پردازش یک تصویر دارنـد . ایـن ضعف موجب می‌شود کـه نتـوان از ایـن روش‌هـا در کاربردهـای برخط[^Online] استفاده کرد زیرا سیسـتم‌هـای بـرخط بایـد بتواننـد هر تصویر را در کسری از ثانیه پردازش کنند. به این منظور می‌توان به‌جای استفاده از اطلاعات مربوط به پیکسل‌ها به صورت مستقیم، از مجموعه‌ی جدیدی از ویژگی‌ها بهره‌مند شد که در دسته‌ی جدیدی به نام روش‌های مبتنی بر بوستینگ[^Boosting-based Approaches] قرار می‌گیرند. لذا مطالعه این روش و تلفیق آن با دیگر الگوریتم‌ها و روش‌های مرتبط، رویکرد جدیدی با محوریت صرفه‌جویی در زمان بازشناسی چهره، در جهت بکارگیری آن در سیستم‌های برخط ایجاد خواهد کرد. 

# **مراجع**

[1]. EC-Council Certified Security Analyst Course (ECSA).
[2]. R. Jafri and H. R. Arabnia, A Survey of Face Recognition Techniques,  Journal of Information Processing Systems, Vol.5, No.2, June 2009.
[3]. Ion Marqu´es, Face Recognition Algorithms, Proyecto Fin de Carrera, 2010. 
[4]. ش. نادری و دیگران، HMM یک بعدی در بررسی هویت بر اساس تصویر چهره : بهینه سازی مدل با بهبود الگوریتم و انتخاب هوشمند تصاویر آموزشی، بانک مقالات همایش‌های دانشگاه فردوسی مشهد.
[5]. K. Delac and M. Grgic, Face recognition, Tech Education and Publishing, 2007.
[6]. Sh. K. Zhou and R. Chellappa, Unconstrained face recognition, Springer Science+Business Media, 2006. 
[7]. J. Li and Sh. Ch. Chu, Kernel Learning Algorithms for Face Recognition, Springer Science+Business Media New York, 2014.
[8]. N. Dalal and B. Triggs, “Histograms of oriented gradients for human detection,”Proc. of the IEEE Conf. on Computer Vision and Pattern Recognition, vol. 2, pp. 886–893,2005. 
[9]. A. Albiol, D.Monzo, A. Martin, J.Sastre, A.Albiol, “Face recognition using HOG-EBGM” Pattern Recognition Letters, vol.
29, pp. 1537–1543, 2010.
[10]. O. Déniz, G. Bueno, J. Salido, F. De la Torre, “Face recognition using Histograms of Oriented Gradients”Pattern Recognition Letters, vol. 32,pp. 1598–1603, 2011. 
[12,11].  ر. جوانمرد علی تپه و دیگران،کاهش نقاط ویژگی در توصیفگر SIFT با استفاده از خوشه‌بندی کاهشی، مرکز تحقیقات مکاترونیک دانشگاه آزاد قزوین.
[13]. N. Dalal and B. Triggs, “Histograms of oriented gradients for, human detection,”Proc. of the IEEE Conf. on Computer Vision, and Pattern Recognition, vol. 2, pp. 886–893,2005. 
[14]. Perriere, G.; & Thioulouse, J. (2003). "Use of Correspondence Discriminant Analysis to predict the subcellular location of bacterial proteins", _Computer Methods and Programs in Biomedicine_, 70, 99–105.
[15]. Prof. Laurenz Wiskott, Elastic Bunch Graph Matching, Institut für Neuroinformatik, Ruhr-Universität Bochum, Bochum, Germany.
[16]. A. Esmailzadeh, Jorge Orts "Face recognition techniques".
[17]. Moon, P.J. Phillips, Computational and Performance aspects of PCA-based Face Recognition Algorithms, Perception.
[18]. http://www.bigdata.ir/1394/05/svm
[19]. http://www.analyticsvidhya.com/blog/2014/10/support-vector-machine-simplified
[20]. http://docs.opencv.org/2.4/modules/gpu/doc/object_detection.html
**پیوندهای مفید**
+ [کتابخانه اپن‌سی‌وی](http://opencv.org)
+ [اپن‌سی‌وی در پایتون](http://docs.opencv.org/trunk/doc/py_tutorials/py_tutorials.html)
+ [دانلود کیوتی برای ویندوز](https://download.qt.io/archive/qt/5.1/5.1.1)
+ [نصب اپن‌سی‌وی در ابونتو](https://help.ubuntu.com/community/OpenCV)
+ [بازشناسی چهره در اپن‌سی‌وی](http://docs.opencv.org/trunk/modules/contrib/doc/facerec/facerec_tutorial.html)