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

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


# مقدمه
در بازشناسی شیء، ابتدا باید با استفاده از تصاویری که به سامانه داده شده به یادگیری دسته های اشیا پرداخت، سپس باید در تصاویر جدید تشخیص داد که نمونه ای از گروه های یادگرفته شده در تصویر وجود دارد یا نه.
بازشناسی شی در تصویر به دو دسته عمومی[^Generic] و اختصاصی[^Specific] تقسیم می شود. در بازشناسی به صورت عمومی، هدف ما شناخت تصاویر مربوط به یک دسته از اشیا می باشد، مانند تشخیص ساختمان، ماشین و یا دوچرخه در تصویرهای مختلف ولی در حالی که در بازشناسی به صورت اختصاصی، شناسایی یک شی خاص مورد نظر است. برای مثال بازشناسی تصویر چهره کارل گاوس و یا برج ایفل. موضوعی که در هر دو دسته مشترک است، وجود تفاوت بین نمونه های مختلف از تصاویر یک شی و یا یک دسته است. [1]
 
 ![توضیح تصویر](http://upload7.ir/imgs/2014-10/99821571971826417360.jpg)
![توضیح تصویر](http://upload7.ir/imgs/2014-10/13339876759993416733.png)

در حال حاضر برای بازشناسی اشیا خاص، بیشتر تطابق[^Matching] و صحیح یابی هندسی[^ Geometric Verification] تصاویر بررسی می شود. ولی برای بازشناسی اشیا به صورت عمومی از مدل آماری[^Statistical Model] مربوط به شکل که با یادگیری از مثال ها به دست آمده، استفاده می شود. برای یادگیری در بازشناسی به صورت عمومی، تصاویری مربوط به یک دسته مشخص جمع آوری می شود و از آن ها مدلی برای پیش بینی[^Prediction] وجود یا مشخص کردن محل[^Localization] شی در تصاویر جدید ایجاد می شود.[1]
بازشناسی اشیا خاص نسبت به بازشناسی اشیا به صورت عمومی ، کامل تر بوده و جنبه تجاری نیز پیدا کرده است، ولی فعلا مسئله بازشناسی عمومی تا حد زیادی حل نشده است.[9]



با توجه به سطح دقتی که نیاز داریم، یک سیستم بازشناسی اشیا می تواند وظایف متفاوتی داشته باشد، برای مثال در تصویر زیر سطوح متفاوتی از دقت در بازشناسی مشخص شده است:
 
![توضیح تصویر](http://upload7.ir/imgs/2014-10/80578261547374086893.jpg)



**چالش ها**[1]
نمونه های یک شی در تصاویر مختلف، بسته به شرایط می توانند بسیار متفاوت از هم باشند، که باعث دشوار شدن فرآیند بازشناسی و دسته بندی می شود. عوامل تاثیرگذار در این زمینه عبارتند از: 
- وضعیت روشنایی[^Illumination Condition]
-  وضعیت شی[^Object Pose]
-  زاویه دید دوربین
-  انسداد [^Occlusion]
-  شلوغی[^Clutter] پس زمینه تصویر و ... .
-  در تصویر زیر به این عوامل اشاره شده است:
 
 ![توضیح تصویر](http://upload7.ir/imgs/2014-10/88519902948015759148.jpg)

به جز موارد اشاره شده در فوق که مربوط به تحمل پذیری خطا[^Robustness] بودند، چالش جدی دیگر در این زمینه مربوط به پیچیدگی محاسباتی[^Computational Complexity] و مقیاس پذیری[^Scalability] است. یعنی باید از الگوریتم هایی کارا و بهینه برای بدست آوردن ویژگی های مختلف تصاویر استفاده کنیم تا بتوان از آن ها در جستجوی پایگاه های داده بزرگ از تصاویر، استفاده کرد.


# کارهای مرتبط
در مرجع [2] روشی برای استخراج ویژگی های نامتغیر و متمایز کننده از تصاویر ارائه شده است که می توان با اطمینان بالایی از آن برای تطابق نماهای مختلفی از یک شی استفاده کرد. این ویژگی ها نسبت به مقیاس و نیز دوران تصویر نامتغیر هستند. این مقاله همچنین دیدگاهی برای استفاده از این ویژگی ها در بازشناسی اشیا ارائه می دهد.

در بازشناسی اشیا به صورت عمومی یکی از ساده ترین الگوریتم ها برای مشخص کردن یک دسته خاص از اشیا روش سبد کلمات[^Bag of Words]			 می باشد که تصاویر و اشیا را به صورت مجموعه ای غیر ترتیبی از توصیف کننده های ویژگی ها در نظر می گیرد. (بخش هایی از کتاب های [1] و [9])

در کاربردهای مختلف، دسته بندی تصاویر معمولا به صورت یک مسئله با چند برچسب در نظر گرفته می شود که هر تصویر می تواند به چند دسته تعلق داشته باشد. در مرجع [16] هر تصویر به چندین بلوک تقسیم می شود و بلوک ها برچسب می خورند. سپس از مجموعه بلوک های برچسب گذاری شده، برای توصیف یک تصویر استفاده می شود. همچنین به جای اینکه مستقیما به یک بلوک از تصویر برچسبی را نسبت دهیم، از دسته بند[^Classifier] آدابوست[^AdaBoost] چند کلاسه[^Multi-Class] برای یادگیری احتمال تعلق این بلوک به یک برچسب خاص استفاده می شود. 
در مرحله بعدی، یک مدل مبتنی بر MRF [^Markov Random Fields] برای جمع کردن اطلاعات هر بلوک برای دسته بندی معرفی می شود.
در تصویر زیر روند ارائه شده در این مقاله برای دسته بندی مشاهده می شود:
 ![توضیح تصویر](http://upload7.ir/imgs/2014-12/70741204800674029013.jpg)
این روش از خروجی های نرمال شده دسته بند آدابوست برای ساخت یک مدل MRF استفاده می کند. برای یک برچسب که به یک بلوک نسبت داده شده، هدف ما بیشینه کردن احتمال[^Likelihood]  است که به این صورت تعریف می شود:( P(X_i | l که متناسب با تابع توزیع گیبس است: (( P(X_i | l) α exp(-U(X_i | l  
در فرمول فوق l نماد برچسب است و ( U(X_i | l  تابع انرژی نامیده می شود، که از مجموع پتانسیل های مربوط به هر بلوک جداگانه و همچنین پتانسیل دو بلوک مجاور که یک برچسب دریافت کرده اند. [16]

مرجع [17] نیز برای دسته بندی تصاویر از MRF استفاده کرده است. برای سادگی محاسبات از فرض توزیع مستقل یکسان[^Identical Independent Distribution] برای پیکسل ها استفاده می کنیم که این فرض باعث بروز اشتباهاتی در نتایج می شود. برای بهبود نتایج بدست آمده و همچنین اختصاص زمان کمتر برای محاسبات، در این پروژه از مدل گرافیکی بدون جهت[^Undirected Graphical Model] (تکنیک MRF)  استفاده شده است.
ممکن است به علت محدودیت های دوربین و یا عوامل دیگر نویزی در یک قسمت کوچک از یک تصویر وجود داشته باشد که باعث دسته بندی اشتباه آن قسمت شود، برای اینکه این مشکل حل شود و یا به اصطلاح نتایج دسته بندی هموار[^Smooth] شود، باید اطلاعات همسایگی در نظر گرفته شود. بدین منظور می توان از چارچوب بیز[^Bayesian Framework] استفاده کرد. از این کار دو هدف را دنبال می شود: اول اینکه رویه دسته بندی باید اطلاعات محتوایی(متنی)[^Contextual Information] را در نظر بگیرد و هدف دوم این است که محاسبات قابل مهارشدن باشند[^Tractable]. از دیدگاه نظریه بیز اطلاعات محتوایی ، نوعی دانش پیشین است[^Prior Knowledge] و داده ها نیز برای بدست آوردن احتمال استفاده می شوند . حال ایده استفاده از چارچوب MRF این است که احتمال به صورت محلی محاسبه شود ولی اطلاعات پیشین با استفاده از تکنیک MRF به صورت احتمال توام[^Joint Probability] مربوط به پیکره بندی[^Configuration] کل تصویر مدل شود. و در نهایت از قانون بیز برای بدست آوردن اطلاعات پسین[^Posterior] مربوط به تصویر که احتمال تعلق آن به یک دسته خاص می باشد، استفاده می شود.[17]
برای اینکه محاسبات مربوط به اطلاعات پیشین قابل مهار باشد باید از فرض مارکوف[^Markov Assumption] استفاده شود. یعنی برچسب هر پیکسل مستقل از برچسب پیکسل هایی است که به طور مستقیم همسایه آن هستند.[17]
سیستم همسایگی مرتبه اول به این صورت است:
 ![توضیح تصویر](http://upload7.ir/imgs/2014-12/80095402027398056902.jpg)

در مرجع [18] در ابتدا یک مکانیزم  با استفاده از رویدادهای کلمه تصویری[^Visual Word] تشخیص اشیا را انجام داده و یک قسمت بندی[^Segmentation] به صورت تقریبی ایجاد می شود، سپس با استفاده از یک مولفه MRF مرزبندی دقیق و واضح در تصویر ایجاد می شود.

# آزمایش‌ها

داده های مورد استفاده در این پروژه مربوط به گروه تحقیقات مایکروسافت است . صفحه مربوطه و پروژه هایی که از این مجموعه دادگان استفاده کرده اند از  [اینجا](http://research.microsoft.com/en-us/projects/objectclassrecognition/) قابل دسترس می باشد.
مجموعه دادگان از [اینجا](http://research.microsoft.com/en-us/um/people/antcrim/data_objrec/msrc_objcategimagedatabase_v1.zip) قابل دریافت است.
این مجموعه دادگان شامل 240 عکس با سایز 213*320 پیکسل است که در 9 دسته قرار دارند. همچنین در همه عکس ها، پیکسل ها برچسب گذاری شده اند لذا می توان از آن برای یادگیری با ناظر استفاده کرد.
به ازای هر تصویر در این مجموعه، تصویری متناظر وجود دارد که در آن، تصویر اصلی قسمت بندی شده و همه پیکسل ها نیز برچسب گذاری شده اند. مانند تصویر زیر:

![توضیح تصویر](https://boute.s3.amazonaws.com/126-3-1.jpg)

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

![توضیح تصویر](https://boute.s3.amazonaws.com/126-3-2.jpg)

نکته مهم دیگر این است که برای یادگیری دسته های اسب، آب، کوه و گوسفند به تعداد کافی تصویر در این مجموعه دادگان وجود ندارد.

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

![توضیح تصویر](https://boute.s3.amazonaws.com/126-3-3.jpg)	

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

![توضیح تصویر](https://boute.s3.amazonaws.com/126-3-4.jpg)

در مرحله بعدی باید تصویر را قسمت بندی کنیم ، در اینجا از الگوریتم Mean-Shift برای قسمت بندی تصاویر استفاده شده است.نتایج قسمت بندی با استفاده از این الگوریتم در تصاویر زیر قابل مشاهده است:
تصویر اصلی:

![توضیح تصویر](https://boute.s3.amazonaws.com/126-3-8.jpg)

قسمت بندی تصویر با استفاده از الگوریتم Mean-Shift:

![توضیح تصویر](https://boute.s3.amazonaws.com/126-3-7.jpg)

سپس برای هر کدام از قسمت های ایجاد شده بردار میانگین ویژگی بدست می آوریم. در نهایت با استفاده از بردار های میانگین تابع پتانسیل بدست می آوریم که با استفاده از آن تابع احتمال محاسبه خواهد شد. 
مدل گرافیکی در نظر گرفته شده در این پروژه مشابه تصویر زیر است: (تصویر مربوط به درس PGM خانم Koller است)

![توضیح تصویر](https://boute.s3.amazonaws.com/126-3-9.jpg)

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

![توضیح تصویر](https://boute.s3.amazonaws.com/126-3-10.jpg)
 
که  در اینجا مقدار پارامتر تتا یک مقدار ثابت است.
سپس برای محاسبه احتمال از فرمول زیر استفاده می شود:

![توضیح تصویر](https://boute.s3.amazonaws.com/126-3-11.jpg)

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

کد پروژه از طریق [این](https://github.com/amirid/Classification) آدرس قابل دسترس است. ( همه کدهای این پروژه توسط اینجانب نوشته شده است و از کد آماده استفاده نکرده ام.)



# کارهای آینده

# مراجع
1. Kristen Grauman and Bastian Leibe,Visual Object Recognition, Synthesis Lectures on Artificial Intelligence and Machine 
Learning, April 2011, Vol. 5, No. 2, Pages 1-181. [لینک](http://bayanbox.ir/id/3567863871569365905?info)
2. David G. Lowe, "Distinctive image features from scale-invariant keypoints," International Journal of Computer Vision, 60, 2 (2004), pp. 91-110 [لینک](http://www.cs.ubc.ca/~lowe/papers/ijcv04.pdf)
3. Fischler, Martin A., and Robert C. Bolles. "Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography." Communications of the ACM 24.6 (1981): 381-395.
4. Philbin, James, et al. "Object retrieval with large vocabularies and fast spatial matching." Computer Vision and Pattern Recognition, 2007. CVPR'07. IEEE Conference on. IEEE, 2007. [لینک](http://www.robots.ox.ac.uk:5000/~vgg/publications/2007/Philbin07/philbin07.pdf)
5. Arandjelovic, Relja, and Andrew Zisserman. "Smooth object retrieval using a bag of boundaries." Computer Vision (ICCV), 2011 IEEE International Conference on. IEEE, 2011. [لینک](http://www.robots.ox.ac.uk/~vgg/publications-new/Public/2011/Arandjelovic11/arandjelovic11.pdf)
6. D. Nistér and H. Stewénius." Scalable recognition with a vocabulary tree". In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), volume 2, pages 2161-2168, June 2006 [لینک](http://www.vis.uky.edu/~stewe/publications/nister_stewenius_cvpr2006.pdf)
7. Arandjelovic, Relja, and Andrew Zisserman. "All about VLAD." Computer Vision and Pattern Recognition (CVPR), 2013 IEEE Conference on. IEEE, 2013. [لینک](http://www.cv-foundation.org/openaccess/content_cvpr_2013/papers/Arandjelovic_All_About_VLAD_2013_CVPR_paper.pdf)
8. 	Erik B.Sudderth .”Graphical Models for Visual Object Recognition and Tracking.” Dept. EECS. MIT, May 2006.
9. 	R.Szeliski, Computer Vision: Algorithms and Applications, Springer, September 2010.	
10. D.Koller and N.Friedman," Probabilistic Graphical Models: Principles and Techniques", MIT Press, 2010.
11. 	David G.Lowe, “Object Recognition from Local Scale-Invariant Features.” International Conference on Computer Vision(ICCV), September 1999.
12. 	David G.Lowe, “Distictive Image Features from Scale-Invariant Keypoints.” International Journal of Computer Vision, pages 91-110, 2004.
13. 	E.Nowak, F.Jurie, B.Triggs, “Sampling strategies for bag-of-features image classification.” Proceedings of the European Conference on Computer Vision.
14. 	Philbin, J., Chum, O., Isard, M., Sivic, J. & Zisserman, A. (2007)," Object retrieval with large vocabularies and fast spatial matching", in ‘Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition’.
15. 	Bay, H., Ess, A., Tuytelaars, T. & Van Gool, L. (2008), "SURF: Speeded-Up Robust Features", Computer Vision and Image Understanding 110(3), 346–359.
16. W.Zeng, X.Chen, H.Cheng, J.Hua,"Multi-Space Learning for Image Classification Using AdaBoost and Markov Random Fields", Solving Complex Machine Learning Problems with Ensemble Methods(COPEM), September 2013.
17. Xiaojin Shi, "Markov Random Field Modeling for Image Classification", Dept. CE. UCSC, 2004.
18. Diane Larlus, Frederic Jurie, "Combining Appearance Models and Markov Random Fields for Category Level Object Segmentation", CVPR 2008 - IEEE Conference on Computer Vision & Pattern Recognition, Jun 2008, Anchorage, United States. IEEE Computer Society, pp.1-7

# پیوندهای مفید
+ [Dataset: Oxford](http://www.robots.ox.ac.uk/~vgg/data/oxbuildings/)
+ [Dataset: Paris](http://www.robots.ox.ac.uk/~vgg/data/parisbuildings/)
+ [Dataset: Sculptures](http://www.robots.ox.ac.uk/~vgg/data/sculptures6k/)
+ [Dataset: UKBench](http://www.vis.uky.edu/~stewe/ukbench/)