تشخیص سگ و گربه در تصویر

**به نام خدا**

اسیرا [^Asirra (**A**nimal **S**pecies **I**mage **R**ecognition for **R**estricting **A**ccess)] یکی از انواع آزمون‌های شناخت انسان از رایانه ([کپچا](https://en.wikipedia.org/wiki/CAPTCHA)[^CAPTCHA(**C**ompletely **A**utomated **P**ublic **T**uring test to tell **C**omputers and **H**umans **A**part)]) است که از کاربر می خواهد از مجموعه ی 12 عکس سگ و گربه فقط تصاویر گربه‌ها را انتخاب کند. انجام این تست برای انسان بسیار ساده است. به‌طوری که 99/6% از انسان‌ها در کمتر 30 ثانیه به آن پاسخ می‌دهند. ولی شواهد نشان می دهند که تشخیص گربه و سگ به صورت خودکار از یکدیگر کار دشواری است. [1]
![شکل 1-یک نمونه تست اسیرا](https://boute.s3.amazonaws.com/197-asirra.jpg)
در این تست اگر اشاره‌گر موس روی هریک از تصاویر نگه داشته شود تصویر حیوان به صورت بزرگ تر نمایش داده شده و جمله‌ی"Adopt me" در زیر آن تصویر ظاهر می شود که در صورت کلیک بر آن کاربر را به صفحه‌ی آن حیوان در سایت [^بزرگترین سایت برای یافتن خانه برای حیوانات بی‌خانمان][Petfinder.com](Petfinder.com)ارجاع می‌دهد. لازم به ذکر است که این تست برای مجموعه‌ی داده‌[^dataset]ای خود از آرشیو این سایت استفاده می‌کند.[2]

**#مقدمه**

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

-در دسته‌‌ی اول این اطلاعات صرفا اعداد و حروف تصادفی هستند. 
-در دسته دوم این اطلاعات تصاویر هستند.

دسته دوم علاوه بر تصادفی بودن به پایگاه داده[^database]ی بزرگی از تصاویر دسته‌بندی شده [^classified] نیاز دارد. اما دسته اول را می توان با چند خط کد پیاده‌سازی کرد. و این در حالی است که امکان موفقیت رایانه‌ها در این نوع تست بیشتر از نوع دوم است. در میان دلایل متعدد برتری دسته ی دوم می‌توان به این دلیل اشاره کرد که مجهز کردن ماشین به بینایی [^machine vision] بسیار دشوارتر از مجهز کردن آن برای تشخیص متن [^text recognition]است. اما فراهم آوردن پایگاه داده‌ی مورد نیاز دسته دوم نیز کار دشواریست.

![شکل 2-چند نمونه از کپچا‌های دسته‌ی دوم](https://boute.s3.amazonaws.com/197-123.jpg)

اسیرا در دسته دوم از انواع کپچا‌‌‌ها قرار می‌‌گیرد و پایگاه داده ای خود را از سایت Petfinder.com تامین می کند. [3] Petfinder دارای پایگاه داده‌ای شامل بیش از 3 میلیون تصویر از سگ و گربه است که روزانه 10000 تصویر را به پروژه‌ی اسیرا اختصاص می‌دهد. همچنین لازم به ذکر است که اسیرا توسط شرکت مایکروسافت [^microsoft] ابداع شده است.[4] انگیزه‌ی انجام این پروژه شناخت تصاویر سگ و گربه از یکدیگر به کمک الگوریتم های هوش مصنوعی به منظور عبور از اسیرا می باشد.

**# شرح مسئله**

در این مسئله وظیفه ی ما یافتن الگوریتمی با بالاترین میزان دقت در تشخیص تصاویر سگ و گربه برای دسته بندی آن‌هاست. ورودی این مسئله مجموعه داده‌ای جهت آموزش[^training dataset] از تصاویر سگ و گربه و خروجی آن میزان دقت در طبقه بندی تصاویر در مجموعه داده‌ای مورد آزمایش [^test dataset] است.[5] مجموعه داده ای که توسط سایت [Kaggle.com](https://www.kaggle.com/c/dogs-vs-cats) در اختیار ما قرار داده شده است قسمتی از پایگاه داده اسیرا است که توسط مایکروسافت ارائه شده است. مجموعه داده‌ای جهت آموزش آن شامل 25000 تصویر که 12500 تصویر آن سگ و 12500 تصویر دیگر آن گربه است. و همچنین مجموعه داده‌ای مورد آزمایش آن نیز شامل 12500 تصویر است. سایز متوسط تصاویر ارائه شده در حدود 500*350 پیکسل است.

![شکل 3- کار یادگیری](https://boute.s3.amazonaws.com/197-learn.png)

با توجه به آنچه که در شکل 3 مشاهده می کنید در کار یادگیری، ورودی، مجموعه داده مخصوص آموزش است و خروجی که به کمک یکی از الگوریتم هایی که در
قسمت بعدی ذکر می شود به دست می‌آید، مدل طبقه بندی شده است و در قسمت عملکرد کار (شکل 4) از این مدل طبقه بندی شده استفاده کرده و مجموعه داده مخصوص آزمایش را مورد بررسی قرار می دهد.

![شکل 4-عملکرد کار](https://boute.s3.amazonaws.com/197-test.jpg)

#کارهای مرتبط

در ادامه به توضیح روش هایی که می توان برای حل این مسئله از آن‌ها بهره برد می‌پردازیم:

**##SIFT[^SIFT( تبدیل ویژگی مقیاس ‌نابسته[^SIFT]**  )]

"تبدیل مستقل از مقیاس ویژگی" یک الگوریتم در بینایی ماشین  است؛ که برای استخراج ویژگی‌های مشخص از تصاویر، استفاده در الگوریتم‌ کارهایی چون تطبیق نماهای مختلف یک جسم یا صحنه و شناسایی اجسام به کار می‌رود. در این الگوریتم ابتدا تصویر اصلی به طور پیش‌رونده با فیلترهای گاوسی با سیگما در بازه ۱ تا ۲ محو می‌شود که حاصلش یک سری تصاویر محو شده گاوسی است (به این کار فیلتر کردن آبشاری می گویند) سپس، این تصویرها از همسایگان بلافصل خود(از دید سیگما) کم می‌شوند تا یک سری جدید از تصاویر پدید آیند.[6]
گام‌های اصلی در محاسبه ویژگی‌های تصویر عبارت‌اند از:
1.آشکارسازی اکسترمم‌های فضای مقیاس هر پیکسل در تصاویر با هشت همسایه‌اش و نه پیکسل(پیکسل متناظر و هشت همسایه‌اش) از هر یک از تصاویر دیگر سری مقایسه می‌شود.
2.محلی‌سازی کلیدنقطه‌ها - کلیدنقطه‌ها از اکسترمم‌های فضای مقیاس گزیده می‌شوند.
3.گرایش گماری - برای هر کلیدنقطه در یک پنجره ۱۶x۱۶، نمودار فراوانی گرایش گرادیان‌ها به کمک درونیابی دوسویه محاسبه می‌شوند.
4.توصیفگر کلیدنقطه - نمایش در یک بردار ۱۲۸ عنصری.
![شکل 5- توصیفگر SIFT](https://boute.s3.amazonaws.com/197-Untitled.png)

**##bag of words(BoW)** : 

در بینایی کامپیوتر مدل BoW در صورتی که در آن با ویژگی‌های تصاویر مانند کلمات برخورد گردد می‌تواند برای دسته‌بندی تصاویر مورد استفاده قرار گیرد. در این مدل یک لغت‌نامه به وسیله طبقه خوشه‌بندی [^clustering]ویژگی‌های بازاستخراج شده‌ی [^extracted] مجموعه داده‌های آموزشی تشکیل می دهد. و همچنین هر خوشه[^cluster] یک کلمه از این فرهنگ لغت تصویری محسوب می شود. و تصاویر با بردار های فراوانی که در آن هر بعد نشان دهنده نسبت ویژگی های متعلق به یک خوشه است.[5]

![شکل 6- bag of the words](https://boute.s3.amazonaws.com/197-bag.png)

**##یادگیری عمیق  [^deep learning] :**

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


در بخش بعد به فرمول ها و پیاده سازی این الگوریتم ها می پردازیم. 
در بخش بعد پیاده سازی این الگوریتم ها می پردازیم. 

#آزمایش ها

##داده های مورد استفاده 

همان طوری که در قسمت شرح مسئله توضیح داده‌شد مجموعه داده‌ای که مسابقه‌ی [Kaggle](https://www.kaggle.com/c/dogs-vs-cats)  در اختیار ما قرار داده است به شرح زیر است : 

**مجموعه‌ی داده‌ای جهت آموزش :** شامل 25000 تصویر سگ و گربه که تصاویر دارای برچسب می باشند.
**مجموعه‌ی داده‌ای جهت آزمایش :** شامل 12500 تصویر است (واضح است که این تصاویر فاقد برچسب می‌باشند.)

که تمام تصاویر این دو مجموعه دارای فرمت jpg بوده و می‌توان آن‌ها را از [اینجا](https://www.kaggle.com/c/dogs-vs-cats/data) به دست آورد و همچنین سایز متوسط تصاویر ارائه شده در حدود 500*350 پیکسل است.
![یک نمونه تصویر گربه از مجموعه‌ی داده‌ای جهت آموزش](http://uupload.ir/files/lfw7_cat.7397.png)

##پیاده سازی 

در این قسمت مدل BoW را برای پیاده سازی پروژه و الگوریتم SIFT را جهت استخراج ویژگی‌های تصاویر انتخاب کردیم.( در قسمت کارهای مرتبط به توضیح آن‌ها پرداختیم.)

مراحل ابتدایی جهت این کار عبارتند از :

1. خواندن تمام تصاویر از مجموعه داده‌ای جهت آموزش و برچسب‌های آن‌ها.
2. استخراج ویژگی‌های هر تصویر به کمک روش bag of words.
3. یادگیری از طریق بردار‌های تصاویر.
4. ارائه‌ی تصاویر از مجموعه‌ی داده‌ای جهت آزمایش به الگوریتم برای پیش بینی دسته تصاویر.

برای پیاده‌سازی BoW از زبان برنامه نویسی [**پایتون**](https://www.python.org/)[^python :یک زبان برنامه نویسی همه منظوره،سطح بالا،شیءگرا و مفسر است]،کتابخانه‌ی [**scikit-learn**](http://scikit-learn.org/stable/) [^یک کتابخانه‌ی یادگیری ماشین منبع باز برای زبان برنامه نویسی پایتون .] و کتابخانه [**openCV**](http://opencv.org/) [^یک کتابخانه‌ی بینایی ماشین منبع باز جهت دستکاری تصاویر.] استفاده می‌کنیم.

از الگوریتم SIFT جهت استخراج [نقاط کلیدی](http://stackoverflow.com/questions/29133085/what-are-keypoints-in-image-processing)[^Keypoints] و توصیف نقاط کلیدی[^  نمایش یک بردار عددی از ویژگی‌های تصاویر : Keypoint descriptors] هر تصویر بهره‌می‌بریم.در این مرحله الگوریتم آرایه‌ای از توصیفات را برمی‌گرداند. بعد از استخراج نقاط کلیدی و توصیفات آن‌ها باید فراداده‌ها را از هر فایل تصویر به‌دست‌آوردیم. فراداده‌ها[^metadata] شامل نام فایل‌ها،مسیر[^path] و کلاس یا دسته [^category]تصاویر می باشند.
مراحل پیاده سازی‌شده در کد را می توان به کمک تصویر زیر بهتر درک‌نمود.
![مراحل پیاده سازی‌ ](http://uupload.ir/files/sizi_111.jpg)

همانطوری که در شکل مشاهده می کنید بعد از به‌دست‌آوردن آرایه‌ی ویژگی‌ها، به خوشه‌بندی ویژگی‌ها و استخراج واژه‌نامه‌ای از ویژگی‌ها[^در اینجا منظور واژگان بصریست.] می‌پردازیم. سپس استخراج‌کننده‌ی ویژگی [^feature extractor] می‌تواند از واژه‌نامه‌ی به‌دست‌آمده برای پردازش تصاویر استفاده‌کند.
این الگوریتم صرفا از یک مدل آموزش‌یافته جهت پیش‌بینی نوع تصویر استفاده‌می‌کند.

کد کامل پروژه را می‌توان از [اینجا](https://github.com/farzanefakhrian/CatsVsDogs) دریافت‌کنید.

## نتایج 
نتایج زیر به کمک یک مجموعه‌ی داده‌ای جهت آموزش شامل 100 تصویر و مجموعه‌ی داده‌ای جهت آزمایش شامل 12 تصویر به‌دست‌آمده‌است.
از 12 تصویر 9 تصویر درست  پیش‌بینی شده‌است. از این جمله می‌توان نتیجه‌گرفت که الگوریتم با 75% دقت درستی می‌تواند تصاویر سگ و گربه را از هم تشخیص‌دهد. در زیر بعضی از نمونه‌های درست و نادرست را نمایش‌می‌دهیم.
 ![نمونه درست(1)](http://uupload.ir/files/yj67_0.jpg)  
  ![نمونه درست(2)](http://uupload.ir/files/u27z_1.jpg) 
 ![نمونه درست(3)](http://uupload.ir/files/7vs9_2.jpg) 
![نمونه نادرست(1)](http://uupload.ir/files/aoio_3.jpg) 
![نمونه درست(4)](http://uupload.ir/files/asz8_6.jpg)
![نمونه درست(5)](http://uupload.ir/files/o4zt_7.jpg)
![نمونه نادرست(2)](http://uupload.ir/files/tv73_8.jpg)
![نمونه درست(6)](http://uupload.ir/files/og4m_9.jpg)
![نمونه نادرست(3)](http://uupload.ir/files/rbtk_10.jpg)
![نمونه درست(7)](http://uupload.ir/files/psyv_11.jpg)
![نمونه درست(8)](http://uupload.ir/files/icso_12.jpg)

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


 [1] Philippe Golle, Machine Learning Attacks Against the Asirra CAPTCHA
[2] Jeremy Elson, John R. Douceur, Jon Howell, Jared Saul, Asirra: A CAPTCHA that Exploits Interest-Aligned Manual Image Categorization, in Proceedings of 14th ACM Conference on Computer and Communications Security (CCS), Association for Computing Machinery, Inc., Oct. 2007
[3]  Jared Saul. Petfinder. http://www.petfinder.com.
[4] [Dogs vs. Cats competition from Kaggle](https://www.kaggle.com/c/dogs-vs-cats)
[5] Bang Liu, Yan Liu, Kai Zhou, Image Classification for Dogs and Cats
[6] David G. Lowe, Distinctive Image Features from Scale-Invariant Keypoints
[7] Yoshua Bengio,Deep Learning of Representations: Looking Forward

**پیوندهای مفید**
   [صفحه مربوط به مسابقه تشخیص سگ و گربه](https://www.kaggle.com/c/dogs-vs-cats)
  + [Image Classification for Dogs and Cats](https://www.ualberta.ca/~bang3/files/DogCat_report.pdf)
  + [Deep Learning Wins Dogs vs Cats competition on Kaggle](http://www.kdnuggets.com/2014/02/deep-learning-wins-dogs-vs-cats-competition.html)