__
در این پروژه باید تلاش می کنیم تا با استفاده از تکنیک‌های هوش مصنوعی، به روشی برای دسته‌بندی عکس مبنی بر این که سگ و یا گربه در آن هستند برسید. این دسته‌بندی برای یک انسان کار خیلی ساده‌ای است. اما برای کامپیوتر به این سادگی‌ها هم نخواهد بود.

مقدمه :

همان طور که بالا گفته شد ما دنبال یک الگوریتم برای دسته بندی تصاویر گربه وسگ هستیم که

مهمترین کاربرد این بروژه Assira است که این یک نوع از captcha است .که از کاربر میخواهد عکس های گربه از 12 تا عکس گربه و سگ تشخیص کند که این کار انسان میتواند با دقت 99% وبا سرعت خیلی کم انجام بدهد . در عین حال این کار برای کامپیوتر دشوار وبا دقت کمتر از انسان انجام میدهد . که باعث پیچیده شدن شکستن آن .

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

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

دسته بندی:
در دسته بندی تصاویر دیجیتال، با استفاده از اطلاعات طیفی هر پیکسل، پیکسل های تصویر در کلاس ها یا دسـته های خاص قرار می گیرند به طوریکه ویژگی های پیکسل های یک کلاس، مشابه هم و با پیکسل های کلاس مجاور غیـر مشابه هستند [2]. دسته بندی را می توان یک فرایند تصمیم گیری دانست که در آن داده های تصویری به فضای کلاس های مشخص انتقال می یابند [1] . دسته بندی از مهمترین روش های استخراج اطلاعات بـه خـصوص اطلاعـات پوشـش های مختلف زمین به شمار می رود.

1-انواع روش های دسته بندی:

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

دسته بندی سخت4-دسته بندی نرم :
در دسته بندی سخت، خروجی برای یک پیکسل تنها برچسب یک کلاس خواهـد بود . اما در دسته بندی نرم خروجی برای یک پیکسل لیستی از برچسب کلاس ها خواهد بـود کـه معمـولا بـا روش هـای فازی این خروجی به دست می آید

. دسته بندی پارامتریک- دسته بندی غیر پارامتریک :
تمام روش های این دو دیـدگاه جز دسته بند نظارت شده محسوب می شوند. در دسته بندی پارامتریک برای چگونگی توزیع احتمال نمونه ها یک پـیش فرض در نظر گرفته می شود. بر اساس پیکسل های معلوم معرفی شده، پارامترهای مختلفی را محاسبه کرده و بر اسـاس آن ها در مورد مابقی پیکسل ها تصمیم گیری می کند . در دسته بندی غیر پارامتریک هیچ فرضی برای آن، لحـاظ نمـی شود. تنها بر اساس معیارهایی که از مقادیر پیکسل های معلوم به دست می آیند تـصمیم گیـری مـی کنـد[1]

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

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

2-ماشین بردار پشتیبان(SVM) :

یک گروه از الگوریتم های دسته بندی نظارت شده هستند، که پیش بینی می کند یک نمونه در کدام کلاس یا گروه قرار می گیرد. این الگوریتم برای تفکیک دو کلاس از هم، از یک صفحه استفاده می کند به طوریکـه ایـن صـفحه از هـر طرف بیشترین فاصله را تا هر دو کلاس داشته باشد . نزدیک ترین نمونه های آموزشی به این صفحه "بردارهای پشتیبان" نام دارند [6]

به عنوان مثال، صفحه ی H1 و H2 دو کلاس را از هم تفکیک کرده اند، اما کلاس H3 در شرایط این الگوریتم صدق مـی کند.

روش کلی ماشین بردار پشتیبان :
فرض کنید n نمونه آموزشی در یک فضای حقیقی با ابعاد p و دو کلاس داریم، برای هر نمونه می توان نوشت:

که Ci خروجی هر کلاس برای نمونه آموزشی i ام است می خواهیم صفحه ای را پیدا کنیم که نقاط کلاس Ci=1 را از نقاط کلاس Ci=-1 جدا کنیم معادله این صفحه به صورت w.x-b=0 نوشته می شود که w
بردار نرمال و عمود بر صفحه است و پارامتر |b/|w فاصله ی صفحه از مبدا بردار نرمـال، را مـشخص مـی کند برای هر نمونه اگر w.x-b>=1 آنگاه نمونه Xi متعلق به کلاس اول خواهد بود و در غیر این صورت اگر w.x-b=<-1 آنگاه نمونه Xi متعلق به کلاس دوم خواهد بود .مقادیر b و w باید به نحوی انتخاب شوند تا شرط مـاکزیمم بـودن فاصـله تامین شود. در مسئله ی بهینه سازی می توان دو رابطه ی بالا را به صور ت1=<(Ci(w.Xi - b (رابطه 1) نوشت که در این مسظله به دنبال مینیمم کردن مقادیر b و ||W|| هستیم .

3- توابع کرنل
تابع کرنل، تابع وزنی است که در تکنیک های پیش بینی غیر پارامتریک استف اده شده و دارای دو شـرط اسـت [6]:

برایی تمام مقادیر u . اگر گر دو کلاس به نحوی باشند که نتوان آنها را با یـک صـفحه جدا کرد، از روش های غیر خطی و تعریف تابع تصمیم گیری و توابع کرنل استفاده می کنیم.
یک تابع تصمیم گیری به صورت روبرو تعریف میشود:

که Yi خروجی دسته بندی ai ضرایب لاگرانژ تابع K تابع کرنل مورد نظر و M وتعداد نمونه ها می باشد توابع کرنل پر کاربرد
در ماشین های بردار پشتیبان عبارتند از تابع نومیال . تابع پلی نومیال

4- روش های طبقه بندی چند کلاسی :
1-4 - روش یکی در مقابل همه :
در این روش که "یکی در مقابل بقیه" و یا “winner take all” هم نامیده می شـود، یـک مجموعـه از طبقـه بنـدی کننده های باینری برای تفکیک یک کلاس از بقیه ی کلاس ها استفاده می شود . به عنوان مثال اگر تعداد کـلاس هـا M باشد، M طبقه بندی کننده ایجاد می شود، که هر طبقه بندی کننده یک کلاس را از بقیـه ی M-1 کـلاس متمـایز مـی سازد . اندازه ی ناموزون یک کلاس، اختصاص حافظه ی زیاد به محاسبات و صحت پایین طبقه بندی، را به عنـوان برخـی از مشکلات این روش می توان نام برد [4].
2-4- روش یکی در مقابل یکی:
در این روش برای M کلاس، M(M-1)/2 طبقه بندی کننده ایجاد می شود، و هر طبقه بندی کننده به کلاس برنده یک رای اختصاص می دهد، سپس یک پیکسل مجهول براساس کلاسی با اکثریت رای، برچسب می خورد . در مقایسه بـا روش " یکی در مقابل همه"، در این روش اندازه ی کلاس ها متقارن تر بوده، تعداد داده های آموزشی مورد نیاز برای هر طبقه بندی کننده و همچنین نسبت اندازه ی بردار داده ی آموزشی کمتر است. محدودیت این روش، افزایش تعداد طبقه بندی کننده ها با افزایش تعداد کلاس ها است[4] و [5].
3-4- روش همه با هم :
این روش که به نام توسعه دهندگان آن یعنی Crammer and Singer هم نامیده می شود، مـسئله ی طبقـه بنـدی چند کلاسی را مستقیم حل می کند. در این روش، در مسئله ی بهینه سازی تمام بردارهای پشتیبان با هم، در یک زمان در نظر گرفته می شوند، به همین خاطر با داده های حجیم به راحتی کار می کند، اما اختـصاص بـسیار بـالای حافظـه و زمان زیاد محاسبات از معایب آن است [4].
4-4 گراف غیر حلقوی مستقیم:
این روش ساختاری شبیه ساختار درختی دارد. همانطور کـه در شـکل نـشان داده شـده، یـک گـراف غیـر حلقـوی مستقیم گرافی است که در آن هیچ سیکلی و هیچ ارتباط دو طرفه ای وجود ندارد [6].
در این روش طبقه بندی، هر طبقه بندی کننده در یک نود قرار می گیرد، سپس در نود ریشه، مقدار خروجی طبقه بندی کننده برای یک بردار ورودی محاسبه شده و بر اساس این خروجی، تصمیم می گیرد که از کدام مسیر بـه سـطح بعـدی برود [4]

البته ما در این مقاله از روش غیر خطی و روش یک در مقابل یک استفاده میکنیم .
قبل از دادن داتا به SVM که دسته بندی کند باید اول نویز عکس ها برطرف کرد و با استفاده از روش دورنیابی نزدیک ترین همسایگی به عکس های 64×64 تبدیل می کند تا عکس ها نرمال شوند . سپس بدست آوردن ویژگی ها .
مقالات مختلف ایده های مختلفی را برای بدست آوردن ویژگی ها استفاده می کنند. برای نمونه روش مطرح شده در [7]، برای هر عددی که در عکس وجود دارد 4 دیدگاه مختلف تعریف می شود و از روی هر دیدگاه 16 ویژگی استخراج کرده است. بنابراین در کل برای هر عکس 64 ویژگی خواهد داشت.

مراجع

        [1] فاطمی سید باقر، رضایی یوسف، 1385 ، مبانی سنجش از دور، چاپ اول، 1384 ، انتشارات آزاده، 257

[2]. Baofeng Guo, Steve R. Gunn, R. I. Damper, and James D. B. Nelson, 2008, Customizing Kernel
Functions for SVM-Based Hyperspectral Image Classification, IEEE Transactions On Image Processing,
vol. 17, no. 4, 622-629.
[3]. Luis G´omez-Chova, Gustavo Camps-Valls, Jordi Mu˜noz-Mar´, and Javier Calpe, 2007, Semisupervised
Image Classification with Laplacian Support Vector Machines, IEEE Geoscience and Remote
Sensing Letters, vol.XX, no. Y, 1-5.
[4]. Mahesh Pal, 2005, Multiclass Approaches for Support Vector Machine Based Land Cover
Classification, MapIndia 2005 conference, 1-16.
[5]. T.Kavzoglu, I.Colkesen, 2009, A kernel functions analysis for support vector machines for land cover
classification, International Journal of Applied Earth Observation and Geoinformation, 352-359.
[6]. www.wikipedia.or
[7]. J. Sadri, C. Suen and T. Bui, "Application of support vector machines for recognition of handwritten Arabic/Persian digits," in Proceedings of Second Iranian Conference on Machine Vision and Image Processing, 2003.