دسته‌بندی تصاویر

تغییرات پروژه از تاریخ 1393/09/15 تا تاریخ 1393/11/14
در این پروژه شما باید هر تصویر را با توجه به محتوای[^Content] آن دسته‌بندی[^Classification] نمایید. برای مثال آیا شیئی[^Object] از یک دسته[^Class] خاص (مثل صفحه کلید) در تصویر وجود دارد یا خیر. یا اینکه تصویر متعلق به صحنه[^Scene] فرودگاه است یا خیابان. به مثال اول دسته‌بندی شیء و به مثال دوم دسته‌بندی صحنه گفته می‌شود.

در حالت کلی این سامانه‌ها بر پایه‌ی چارچوب یادگیری ماشین کار می‌کنند. بدین معنی که با داشتن تعدادی نمونه‌ی مثبت:
![positive](http://bayanbox.ir/id/4413769390211746038?view)

و تعدادی نمونه منفی:
![negative](http://bayanbox.ir/id/1300467730143874044?view)

برای یک تصویر جدید بتواند دسته‌بندی را انجام دهد:
![query](http://bayanbox.ir/id/4811798205273713626?view)

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

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

# کارهای مرتبط
یک پژوهش انجام‌گرفته در این زمینه، استفاده از تکنیک SPM[^Spatial Pyramid Matching] برای شناسایی مناظر طبیعی است.[3]
در این روش تصویر به تعداد زیادی قسمت‌های کوچک‌تر تقسیم می‌شود. سپس برای هر قسمت نمودار ویژگی‌های محلی آن قسمت محاسبه می‌گردد. با داشتن نمودار ویژگی‌های تمامی قسمت‌های تصویر می‌توان محتوای تصویر اولیه را با دقت نسبتا بالایی تشخیص داد. این امر با تکنیکی تحت عنوان bag-of-features انجام می‌پذیرد.
اساس کار تکنیک bag-of-features بر مبنای تقسیمات نامنظم تصویر مورد بررسی، قرار گرفته است.[11] البته این تکنیک شاخه‌های دیگری همچون تشخیص الگو و یا تشخیص کلمات نیز دارد. تصاویر زیر[12] مربوط به شاخه‌ی  تشخیص الگو  می‌باشد که سعی شده با استفاده از آن کلیات عملکرد این تکنیک توضیح داده شود.
![استخراج ویژگی‌های هر الگو](http://upload7.ir/imgs/2014-12/52690727197622393380.png)
در تصویر فوق سه الگو وجود دارد. برای هر الگو سه ویژگی در نظر گرفته شده است، شامل سه قطعه‌ی کوچک از تصویر. در واقع این سه قطعه bag-of-features الگوی مورد نظر را تشکیل می‌دهند.
تصویر زیر مربوط به تشخیص هر الگو از روی bag-of-features است. همانطور که پیش‌تر گفته شد، نمودار همه‌ی قطعات برای هر نمونه ترسیم می‌شود و سپس از روی نمودار می‌توان تشخیص داد هر نمونه مربوط به کدام الگو بوده است.
![محاسبه نمودار قطعات bag-of-features برای نمونه‌ها](http://upload7.ir/imgs/2014-12/04257456580094244629.png)
پژوهش دیگری که بیشتر روی تصاویر حاوی اشیاء کارایی دارد، روش LLC[^Locality-constrained Linear Coding] نام گرفته که با تاکید بر نیازمند بودن رویکرد bag-of-features از روش SPM به دسته بندهای غیر خطی، سعی در ارائه‌ی روشی دارد که در آن از دسته‌بندی خطی استفاده شود.[6]
در روش LLC ویژگی‌های استخراج‌شده از تصویر در چند مرحله مورد نگاشت قرار می‌گیرند تا در نهایت در قالب برداری از ویژگی‌ها درآیند. تصویر زیر شمایی از تبدیل چندمرحله‌ای ویژگی‌های تصویر به بردار ویژگی‌هاست.
![توضیح تصویر](http://upload7.ir/imgs/2014-12/85085731412202984797.png)

برای محاسبه تقریبی از روش LLC می‌توان از روش جستجوی k همسایه‌ی نزدیک استفاده نمود و با مرتبه‌ی پیچیدگی (O(M+K^2  به جواب رسید.

# آزمایش‌ها

# کارهای آیندهسبد ویژگی‌ها انجام می‌پذیرد.
اساس کار تکنیک سبد ویژگی‌ها بر مبنای تقسیمات نامنظم تصویر مورد بررسی، قرار گرفته است.[11] البته این تکنیک شاخه‌های دیگری همچون تشخیص الگو و یا تشخیص کلمات نیز دارد. تصاویر زیر[12] مربوط به شاخه‌ی  تشخیص الگو  می‌باشد که سعی شده با استفاده از آن کلیات عملکرد این تکنیک توضیح داده شود.
![استخراج ویژگی‌های هر الگو](http://upload7.ir/imgs/2014-12/52690727197622393380.png)
در تصویر فوق سه الگو وجود دارد. برای هر الگو سه ویژگی در نظر گرفته شده است، شامل سه قطعه‌ی کوچک از تصویر. در واقع این سه قطعه سبد ویژگی‌های الگوی مورد نظر را تشکیل می‌دهند.
تصویر زیر مربوط به تشخیص هر الگو از روی سبد ویژگی‌ها است. همانطور که پیش‌تر گفته شد، نمودار همه‌ی قطعات برای هر نمونه ترسیم می‌شود و سپس از روی نمودار می‌توان تشخیص داد هر نمونه مربوط به کدام الگو بوده است.
![محاسبه نمودار قطعات bag-of-features برای نمونه‌ها](http://upload7.ir/imgs/2014-12/04257456580094244629.png)
پژوهش دیگری که بیشتر روی تصاویر حاوی اشیاء کارایی دارد، روش LLC[^Locality-constrained Linear Coding] نام گرفته که با تاکید بر نیازمند بودن رویکرد سبد ویژگی‌ها از روش SPM به دسته بندهای غیر خطی، سعی در ارائه‌ی روشی دارد که در آن از دسته‌بندی خطی استفاده شود.[6]
در روش LLC ویژگی‌های استخراج‌شده از تصویر در چند مرحله مورد نگاشت قرار می‌گیرند تا در نهایت در قالب برداری از ویژگی‌ها درآیند. تصویر زیر شمایی از تبدیل چندمرحله‌ای ویژگی‌های تصویر به بردار ویژگی‌هاست.
![توضیح تصویر](http://upload7.ir/imgs/2014-12/85085731412202984797.png)

برای محاسبه تقریبی از روش LLC می‌توان از روش جستجوی k همسایه‌ی نزدیک استفاده نمود و با مرتبه‌ی پیچیدگی (O(M+K^2  به جواب رسید.

# آزمایش‌ها
برای پیاده سازی پروژه از روش استخراج ویژگی‌ها استفاده شده است. در واقع هدف آنست که با انجام پردازش‌های لازم روی تصاویر، نمودار[^Histogram] مربوط به ویژگی‌های هر تصویر را محاسبه کرده و دسته‌بند مورد استفاده را بر مبنای نمودارهای حاصل آموزش داده و مورد آزمایش قرار دهیم. خوشبختانه داده‌های تهیه شده از قبل مورد پردازش قرار گرفته‌اند و نمودار ویژگی‌های آن‌ها محاسبه گشته و قابل استفاده است. لذا در انجام پیاده‌سازی تنها بر روی آموزش و آزمایش دسته‌‌بند مورد استفاده کار شده است. در قسمت «پیوندهای مفید» این گزارش، پیوندی برای دسترسی به داده‌های استفاده شده قرار داده شده است.
روند کلی پیاده‌سازی اینگونه است که در مرحله‌ی اول از تعدادی نمونه‌ی مثبت و تعداد خیلی بیشتری نمونه‌ی منفی استفاده می‌شود و این نمونه‌ها به یک دسته‌بند SVM خطی آموزش داده می‌شوند. همانطور که پیشتر گفته شد آموزش دسته‌بند با استفاده از نمودار ویژگی‌های این تصاویر انجام می‌شود. در مرحله‌ی بعدی تعدادی نمونه‌ی مثبت و منفی دیگر به عنوان تست به دسته بند داده می‌شود و دسته‌بند با توجه به نمودار ویژگی‌های هر تصویر و آنچه که قبلا یاد گرفته است، برای هر تصویر یک امتیاز در نظر می‌گیرد. از آنجاییکه مثبت و یا منفی بودن نمونه‌های تست مشخص است می‌توان بررسی کرد امتیازهای درنظر گرفته شده برای نمونه‌ها تا چه حد تناسب داشته است. (توضیحات جزئی‌تر در رابطه با پیاده‌سازی انجام شده بصورت کامنت در متن برنامه آورده شده است و علاقه‌مندان می‌توانند به فایل برنامه مراجعه نمایند.)
نکته‌ای که در این روش وجود دارد آنست که نتیجه‌ی دسته‌بند برای یک نمونه‌ی مجهول یک امتیاز تعلق به کلاس مثبت است. یعنی عددی که هرچه بزرگتر باشد نشان‌دهنده‌ی احتمال تعلق بیشتر به کلاس مثبت است. اما اینکه چه حد آستانه‌ای برای اعلام تعلق به کلاس مثبت انتخاب شود(با توجه به امتیاز در نظر گرفته شده برای نمونه‌ی مجهول)، بستگی به نتایج دسته‌بند در مرحله‌ی آزمایش دارد. می‌توان حد آستانه‌های متفاوتی در نظر گرفت و دقت دسته‌بند را برای هریک اندازه‌گیری کرد و مقداری که به دقت بالاتری منجر می‌شد را به عنوان حد آستانه معرفی کرد.
به عنوان نمونه‌ای از عملکرد دسته‌بند، از 112 نمونه تصویر هواپیما(مثبت) و 1019 نمونه تصویر متفرقه(منفی) به منظور آموزش دسته‌بند استفاده شد. همچنین 126 تصویر هواپیما و 1077 تصویر متفرقه‌ی دیگر به عنوان نمونه‌های تست استفاده شدند که با تصاویر نمونه‌های آموزش متفاوت بودند.
در نتیجه‌ی این آزمایش تعداد 36 تصویر با امتیازی بالاتر از 0.1(به عنوان حد آستانه) مشخص شدند که از این تعداد 23 نمونه واقعا تصویر هواپیما بوده و مابقی به اشتباه هواپیما تلقی شده اند. شکل زیر نشان‌دهنده‌ی نمونه‌های منفی و مثبتی است که در این 36 تصویر قرار دارند، به همراه امتیازی که برای هریک در نظر گرفته شده است.
![نتایج آزمایش دسته بند](http://upload7.ir/uploads//bc6f32dd878e6787dd453d7390838ef06cfcfd48.png)

همانطور که ملاحظه می‌شود بالاترین امتیاز 3.45 بوده که به اولین تصویر از سمت چپ در بالای شکل تعلق گرفته است و پس از آن امتیازات روندی نزولی داشته‌اند تا به تصویری با کمترین امتیاز، یعنی 0.1، رسیده است.
باتوجه به آنچه گفته شد از 36 نمونه‌ی دسته‌بندی شده به عنوان کلاس مثبت، تنها 23 عدد واقعا به کلاس مثبت تعلق داشته‌اند و با این حساب می‌توان دقت دسته‌بند آموزش داده شده را در حدود 0.64 دانست.
لازم به ذکر است در این پیاده‌سازی از کتابخانه‌ی VLfeat استفاده شده است که امکانات زیادی در امر پردازش تصویر در اختیار برنامه‌نویس قرار می‌دهد. فایل‌های مربوط به این کتابخانه به همراه کد پیاده‌سازی پروژه در سایت گیت‌هاب قرار داده‌شده است. پیوندی برای صفحه‌ی حاوی این فایل‌ها در قسمت «پیوندهای مفید» گزارش درج گردیده است.

# بهبود نتایج
اولین موردی که برای بالا رفتن دقت دسته‌بند پیشنهاد می‌شود تعیین کردن حد آستانه‌ی مناسب است. این موضوع که در بخش قبلی نیز مطرح شد، نیازمند آزمون و خطا در تعیین حد آستانه‌ی مناسب برای بدست آوردن بالاترین دقت ممکن است. البته این روش کارایی چندانی ندارد و بیشتر بر این موضوع تاکید دارد که حد آستانه‌ای که برای دسته‌بند در نظر گرفته می‌شود نباید نامعقول باشد زیرا دقت دسته‌بند را تحت تاثیر قرار خواهد داد.
مورد دیگری که پیشنهاد می‌شود مربوط به نرمال کردن نمودار ویژگی‌های تصاویر مورد استفاده است. البته در نسخه‌ی قبلی هم نمودارهای نرمال‌سازی شده بودند ولی در این مرحله از تابع دیگری برای نرمال‌کردن نمودارها استفاده شده که دقت دسته‌بند را تا حد بسیار خوبی بالا برده است. لذا باید توجه داشت از میان توابع متفاوتی که برای نرمال کردن نمودارها وجود دارد، تابعی استفاده شود که نتیجه‌ی بهتری بدست می‌دهد. در اینجا با جایگزین کردن دو خط زیر در متن برنامه بجای تابع قبلی، تابع ساده‌ی رادیکال را برای نرمال کردن نمودارها بکار می‌بریم.
trainHistograms = sqrt(trainHistograms) ;
testHistograms = sqrt(testHistrograms) ;
پس از انجام این تغییر مجددا آزمایش قبل را تکرار کرده تا تغییری که در امتیازدهی به تصاویر انجام شده است را مشاهده کنیم. بدیهیست هیچ یک از پارامترهای دیگر برنامه را تغییر نمی‌دهیم و از همان نمونه‌های قبلی استفاده می‌کنیم تا فقط تاثیر تغییر تابع نرمال‌سازی در نتایج جدید اعمال شده باشد.
![نتایج جدید پس از تغییر تابع نرمال سازی](http://upload7.ir/uploads//653a374f9e528dfa7100451371a5f9e02a88e34f.png)

ملاحظه می‌شود این بار 64 نمونه دارای امتیازی بالاتر از 0.1 بوده‌اند. از این تعداد 51 نمونه به درستی دسته‌بندی شده اند و به این ترتیب دقت دسته‌بند چیزی در حدود 0.79 محاسبه می‌شود که نسبت به حالت قبل افزایش داشته است.
اگر نگاه دقیق‌تری به نتایج جدید بیندازیم متوجه می‌شویم که از سه تصویر آخر دوتای آن‌ها متعلق به کلاس منفی هستند. و این بدان معناست که اگه سه تصویر آخر از نمونه‌های تلقی شده به عنوان مثبت حذف شوند، دقت دسته بند افزایش خواهد یافت. به عبارت دیگر با تغییر حد آستانه به مقدار جدید 0.15 مشاهده خواهیم کرد که از 61 نمونه‌ی تعلق گرفته به کلاس مثبت، 50 نمونه به درستی دسته‌بندی شده‌اند و دقت دسته‌بند در این حالت 0.82 خواهد بود. البته واضح است حد آستانه را نباید صرفا از روی یک دسته نمونه‌ی آموزش و تست تعیین کرد و موردی که مطرح شد فقط مثالی بود برای درک بهتر پیشنهاد تغییر حد آستانه برای بهبود دقت دسته‌بند.



# کارهای آینده
در بخش آزمایش‌ها از داده‌هایی استفاده شد که نمودار ویژگی‌های آن‌ها از پیش آماده بودند. پیشنهادی که مطرح می‌شود تا شاید به بهبود دقت دسته‌بند منجر شود، انجام پیاده‌سازی لازم برای محاسبه نمودار ویژگی‌های تصویر است. برای محسابه‌ی این نمودار ابتدا لازم است تصویر مورد پردازش قرار گیرد و طی مراحلی مطابق تصویر زیر keypointها و SIFT[^Scale-Invariant Feature Transform]  descriptorهای آن استخراج شوند.
![بدون توضیح](http://upload7.ir/uploads//fbcccef9206179d98a70ca486ea7d2a22e102241.png)
همانطور که تغییر در تابع نرمال‌سازی نمودارها منجر به افزایش دقت دسته‌بند شد، ممکن است با تغییر رویه‌ی تولید نمودار ویژگی‌ها و استفاده از روشی صحیح‌تر و کارآمدتر، نمودارهای تعیین کننده‌تری تولید کرد و دقت دسته‌بند را در امتیازدهی به داده های تست افزایش داد.

# مراجع
[1] Visual Object Recognition, Kristen Grauman and Bastian Leibe, Synthesis Lectures on Artificial Intelligence and Machine Learning, April 2011, Vol. 5, No. 2, Pages 1-181. [پیوند](http://bayanbox.ir/id/3567863871569365905?info)
[2] Gabriella Csurka, et al, Visual Categorization with Bags of Keypoints, ECCV Wrokshops 2004" [پیوند](http://www.cs.berkeley.edu/~efros/courses/AP06/Papers/csurka-eccv-04.pdf)
[3] Beyond Bags of Features: Spatial Pyramid Matching for Recognizing Natural Scene Categories, Lazebnik, Schmid, and Ponce, CVPR 2006 [پیوند](http://www-cvr.ai.uiuc.edu/ponce_grp/publication/paper/cvpr06b.pdf)
[4] Modeling the Shape of the Scene: a Holistic Representation of the Spatial Envelope, Oliva and Torralba, IJCV 2001. [پیوند](http://people.csail.mit.edu/torralba/courses/6.870/papers/IJCV01-Oliva-Torralba.pdf)
[5] Perronnin, Florent, and Christopher Dance. "Fisher kernels on visual vocabularies for image categorization." Computer Vision and Pattern Recognition, 2007. CVPR'07. IEEE Conference on. IEEE, 2007. [پیوند](http://image.ntua.gr/iva/files/PerronninDance_CVPR2007%20-%20Fisher%20Kernels%20on%20Visual%20Vocabularies%20for%20Image%20categorization.pdf)
[6] Locality-Constrained Linear Coding for Image Classification.  J. Wang, J. Yang, K. Yu,  and T. Huang  CVPR 2010 [پیوند](http://www.ifp.illinois.edu/~jyang29/papers/CVPR10-LLC.pdf)
[7] Chatfield, Ken, et al. "The devil is in the details: an evaluation of recent feature encoding methods." (2011). [پیوند](http://lucca.robots.ox.ac.uk/~vgg/publications/2011/Chatfield11/chatfield11.pdf)
[8] A. Quattoni, and A.Torralba. Recognizing Indoor Scenes. IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2009. [پیوند](http://people.csail.mit.edu/torralba/publications/indoor.pdf)
[9] Shape Matching and Object Recognition using Low Distortion Correspondences, A. Berg, T. Berg and J. Malik, Proc. of CVPR 2005, pages 26–33. [پیوند](http://acberg.com/papers/berg_correspondence_cvpr.pdf)
[10] In Defense of Nearest-neighbor Based Image Classification,  O. Boiman,  E. Shechtman and  M. Irani,  Proc. of  CVPR 2008. [پیوند](http://grail.cs.washington.edu/pub/papers/boiman2008ido.pdf)
[11] Introduction to the Bag-of-features Paradigm for Image Classification and Retrieval, Stephen O'Hara and Bruce A. Draper, arXiv 2011. [پیوند](http://arxiv.org/pdf/1101.3354)
[12] Bag-of-features for Category Classification, Cordelia Schmid, CVML 2011. [پیوند](http://www.di.ens.fr/willow/events/cvml2011/materials/CVML2011_Cordelia_bof.pdf)
[13] Linear Spatial Pyramid Matching using Sparse Coding for Image Classification, J. Yang, K. Yu, Y. Gong and T. Huang, Proc. of CVPR 2009. [پیوند](http://www.ifp.illinois.edu/~jyang29/papers/CVPR09-ScSPM.pdf)

# پیوندهای مفید
+ [PASCAL VOC CHALLENGE](http://pascallin.ecs.soton.ac.uk/challenges/VOC/)
+ [Indoor Scene Dataset](http://web.mit.edu/torralba/www/indoor.html)
+ [Caltech 256](http://www.vision.caltech.edu/Image_Datasets/Caltech256/)
+ [Source Code (GitHub)](https://github.com/matin110amtp/SPR-Final-Project)
+ [Dataset](http://www.di.ens.fr/willow/events/cvml2011/materials/practical-classification/practical-image-classification-data-only.tar.gz)