هدف این پروژه طبقه‌بندی ارقام دستنویس به منظور تشخیص رقم مربوطه است. برای این منظور می‌توان از هریک از روشهای طبقه‌بندی استفاده کرد. در این پروژه انتظار می‌رود چند روش برای طبقه‌بندی ارقام که به نظر مناسب‌تر هستند بررسی و مقایسه شوند. برای این منظور می‌توان از مجموعه دادگان فارسی و یا انگلیسی استفاده کنید.
مقدمه
تعاملات انسانها از قدیم با روشهای مختلفی از جمله گفتار و نوشتار صورت گرفته است و با پیدایش فناوریهای جدید، همچون صفحه کلیدها و موبایل ها، میزان این تعاملات افزایش نیز یافته است. اما در سال های اخیر با پیشرفت فناوری، این ارتباطات به شیوه های نوینی همچون استفاده از صفحات لمسی نیز صورت می پذیرد. تشخیص کاراکترها یا OCR یکی از شیوه های موفق در حوزه شناسایی خودکار الگوها است. تشخیص اعداد دست نوشته یکی از زیر بخش های جالب توجه و مهم از تشخیص کاراکترها می باشد که کاربردهای زیادی همچون، دسته بندی نامه های پستی، خواندن خودکار مبالغ چک های بانکی، شناسایی خودکار اطلاعات ثبت شده در فرم ها، خواندن نوشته ها از روی صفحه های لمسی و خواندن اعداد از روی تصاویر دست نوشته دارد. برای تشخیص اعداد فارسی روش های متفاوتی وجود دارد که می توان به مواردی همچون استفاده از روش های آماری shadow coding، مدل مخفی مارکوف [1]، [2]SVM، نزدیک ترین همسایگی یا K-NN و یا روش های شبکه های عصبی، ژنتیک [3] و فازی اشاره نمود. دقت و سرعت انجام کار در تمامی این موارد از اهمیت ویژه ای برخوردار است که در این راستا از روش هایی مانند PCA برای کاهش حجم داده ها استفاده می شود. یکی از سوالات مهم در این زمینه، تشخیص دست نویس بودن و یا چاپی بودن اعداد است که در این زمینه پژوهشهای بسیاری برای تفکیک این دو حالت از یکدیگر انجام شده است [4]. نکته دیگر آنکه، طرز نوشتن (دستخط) افراد در شهرهای مختلف و همچنین نوشتار اعداد فارسی با زبان های دیگر مانند عربی و هندی با هم متفاوت است که در این زمینه نیز پژوهشهای بسیاری صورت گرفته است [5]. از زمینه های پژوهشی دیگر، می توان به تشخیص درشت نویسی و یا مورب نویسی اعداد فارسی نیز اشاره نمود که در زبان فارسی تقریباً کاری در این حوزه انجام نشده است.
شکل 1 نمایش اعداد فارسی [2]
در زبان فارسی 13 نوع نمایش اعداد دستنویس وجود دارد که شکل 1 نمونه ای از آنها را به تصویر کشیده است. از آنجا که اعداد صفر، چهار و شش در این زبان به دو صورت نوشته می شوند [2]. پس باید برای آن 13 دسته ایجاد کرد و کار تشخیص را برای هر دسته انجام داد.
برای تشخیص اعداد فارسی نیاز به پایگاه داده ای می باشد که مشتمل بر یک سری اعداد دست نوشته فارسی باشد. پایگاه های داده زیادی برای انجام این کار وجود دارد که جدول 1 مجموعه ای از موارد معروف در این زمینه را در بر گرفته است.
روند انجام کار بدین صورت است که برای تشخیص اعداد، ابتدا نویز های عکس ها را برطرف نموده و بعد آن ها را نرمال سازی می کنند. یعنی همه آنها را به یک اندازه خاص به عنوان مثال 64×64 تبدیل نموده و بعد با استفاده از یک و یا ترکیبی از روش های مطرح، سعی به آموزش دادن و یا جمع آوری اطلاعات و تولید ویژگی برای حل مسئله می کنند. در نهایت، مدل آموزش دیده را با داده های آزمونی، مورد سنجش قرار می دهند تا بتوانند میزان دقت کار را بدست آورند.
| نام پایگاه داده | dpi | نمونه های آزمایشی | نمونه های آزمونی | مجموعه نمونه ها |
|---|---|---|---|---|
| CENPARMI | 166 | 4000 | 2000 | 60000 |
| CEDAR | 300 | 18468 | 2711 | 21179 |
| MNIST | Normalized into 20*20 | 7291 | 2007 | 9298 |
جدول 1- مجموعه ای از پایگاه های داده های مهم [6]
در ادامه این مقاله، ابتدا از یک سری از روش های مطرح و طرز کار آنها در قالب کارهای مرتبط توضیحاتی داده خواهد شد. آزمایشات انجام شده و نتایج بدست آمده، و همچنین مقایسه روش ها نیز در بخش های بعدی ارائه خواهند شد. در پایان نیز نتیجه گیری نهایی از کارهای انجام شده را ارائه خواهیم نمود.
کارهای مرتبط
همان طور که می دانید روش SVM یکی از روش های مطرح در حوزه شناسایی الگو می باشد که از این روش در شناسایی اعداد فارسی نیز استفاده شده است. نکته مهم در این روش، ایده ای است که برای بدست آوردن ویژگی ها استفاده می شود. هدف اصلی این ویژگی ها این است که بتوان یک شی یا نمونه را به وسیله آنها اندازه گیری کرد تا آنهایی که اندازه شان به هم نزدیک تر است بتوانند در یک دسته قرار بگیرند. مقالات مختلف، ایده های متفاوتی را برای بدست آوردن ویژگی ها به کار گرفته اند. برای نمونه روش مطرح شده در [2]، برای هر عددی که در عکس وجود دارد، 4 دیدگاه مختلف تعریف می نماید و از روی هر دیدگاه 16 ویژگی استخراج می کند که از این رو در کل برای هر عکس 64 ویژگی پدید خواهد آمد. با این ویژگی ها یک SVM چندگانه آموزش داده می شود تا بتواند اعداد را با دقت 94.14% تشخیص دهد.
این روش ابتدا عکس ها را بعد از برطرف کردن نویزها با استفاده از روش دورنیابی به نزدیک ترین همسایگی به عکس های 64×64 تبدیل می کند تا عکس ها نرمال شوند. در مرحله بعد، دیدگاه های بالا، پائین، چپ و راست ایجاد می شوند. از آنجا که عکس مورد نظر در ابعاد 64×64 است، ماتریس عکس نیز یک ماتریس 64×64 خواهد بود که ارزش رنگ در آن نوشته شده است. از این ماتریس، به میزان 1/4 که برابر با یک ماتریس 16×16 است، انتخاب می شود. از روی این ماتریس، از هر سو (بالا، پائین، چپ و راست) تعداد خانه های سفید تا رسیدن به مرز خانه سیاه، شمارش می شود. نتیجه تولید نموداری مانند شکل 2 است که از اتصال تعداد نقاط سفید در هر جهت از عکس، منحنی ایجاد کرده اند. اگر از روی این منحنی مشتق گرفته شود، شکل 3 را برای دیدگاه های بالا، پائین، چپ و راست ایجاد می کند. در حقیقت مقادیر مشتق، ویژگی های این مسئله خواهند بود. حال 64 ویژگی استخراج شده را برای آموزش به 13 تا SVM که 13 نوع اعداد را مشخص می کنند استفاده می شود و نتیجه نهایی برای تشخیص یک نمونه جدید نیز بیشترین مقدار بین این 13 تا SVM خواهد بود.
شکل 2 a: عکس اصلی، b: عکس نرمال شده، c-f: دیدگاه مختلف از بالا و پائین، چپ و راست [2]
شکل 3 نمودار های مشتق گرفته شده از منحنی های دیدگاه های مختلف شکل 2 [2]
حوزه دیگری که بسیار قابل رقابت با روش SVM است روش دیاگرام تکرار 1 است. این روش نشان می دهد که چگالی رنگ مشکی در عکس به چه میزان است که در [6] مورد بررسی قرار گرفته است. این مرجع، ابتدا عکس ها را به اندازه های 40×40 نرمال سازی می کند. سپس، ماتریس عکس هایی را که عدد 5 را مشخص می کنند با هم رنگهای مشکی جمع، و همچنین رنگهای سفید را نیز با هم جمع می نماید و در ادامه رنگ سیاه را از سفید و یا سفید را از سیاه تفریق می کند. در نهایت ساختاری که نشان دهنده عدد 5 باشد را ایجاد می کند. شکل 4 نشان دهنده این حالت است که از مجموعه ای از عکس ها که متعلق به عدد 5 هستند ایجاد شده است. همچنین، این کار را بر روی اعداد دیگر نیز اعمال می کند و برای تشخیص از روش شباهت 2 استفاده می شود تا بتوانند یک عدد را تشخیص دهند. اگر بخواهید روش بدست آوردن دیاگرام تکرار را فرموله کنید می توانید از فرمول D_i(x,y)=\frac{1}{N_i} \sum_{n=0}^{N_i} (f_n(x,y)*2-1)*100 که در آن x,y = 0,…,39 می باشد، استفاده کنید. همچنین فرمول تشابه نیز می تواند به صورت زیر باشد.
شکل 4 دیاگرام تکرار برای 300 نمونه از عدد 5، حالت سیاه و سفید آن نیز در سمت بالا سمت راست نشان داده شده است [6]
همان طور که مشخص است، این روش ها نیاز دارند تا در زمان تشخیص، این الگو ها را تولید کنند و این می تواند یکی از معایب آنها باشد. لذا، همه این عملیات با حجم بسیار زیادی از داده های آموزشی باید در سیستم معمولی مانند یک موبایل و یا تبلت اجرا شود. این کار هزینه انجام کار را بالا خواهد برد که از این رو سعی می شود تا با استفاده از روش های کاهش سایز آموزشی، زمان انجام کار را پایین و سرعت انجام آن را بالا ببرند.
برای کاهش سایز در پایگاه داده باید دو کار انجام شود. اول باید بٌعد را کاهش دهند و دوم باید سایز را کاهش دهند [7]. در کاهش بٌعد سعی می شود تا در ابتدا ویژگی هایی که اهمیت کمی دارند را شناسایی و از مجموعه ویژگی ها حذف کنند. برای انجام این کار از روش های مختلفی مانند PCA، EMG، random projection و ... استفاده می شود. همچنین، انجام این کار با استفاده از روش های ترکیبی نتیجه بهتری را در پی خواهد داشت.
در کاهش سایز سعی می شود تا نمونه های آموزشی را کاهش دهند. اکثر روشها دو گروه از نمونه های آموزشی را از مجموعه خود حذف می کنند. 1) نمونه هایی که خیلی از کلاس خود دور هستند. 2) نمونه هایی که خیلی به مرکز کلاس خود نزدیک هستند. برای انجام این کار از روش هایی مانند K-means و یا روش های مختلف داده کاوی استفاده می کنند تا نمونه ها را به چندین کلاس تقسیم کنند. به عنوان یک مثال، در [7] و با استفاده از روش کاهش سایز PCA برای روش دیاگرام تکرارها به دقت 97% دست یافته شده است که در صورت عدم استفاده از کاهش سایز،این روش در زمانی دو برابر به دقت 97.7% می رسید.
یکی از پر طرفدار ترین روش های تشخیص الگو و آموزش دادن به سیستم ها روش شبکه های عصبی است. برای نمونه [8] بعد از حذف نویز و نرمال سازی، عکس نرمال شده را به عکسی به ضخامت یک پیکسل تبدیل می کند و سعی می کند تا عکس نازک سازی شود و اسکلت تصویر مشخص شود، دوباره عکس مورد نظر را به سایز دو برابر تبدیل می کند. این عمل باعث می شود تا میزان کلفتی و نازکی پهنای دست نوشته تاثیری بر روی روش نداشته باشد. حال کل ماتریس عکس را به 16 خانه n*n تقسیم می کنند و از مقدار داخل آنها میانگین گرفته می شود. حاصل 16 عدد است که نشان دهنده ویژگی ها خواهند بود. با استفاده از روش شبکه های عصبی با وزن دهی به نرون ها و بایاس کردن مقدار اولیه و استفاده از تابع سیگموئید دو قطبی مانند تانژانت سیگموئید سعی به شناسایی الگو می کند که نتیجه، دقت 97.2% در شناسایی اعداد است. لازم به توضیح است که اگر از روش projection استفاده می شد به درصد دقت 99% می رسید [9]. البته اگر ویژگی ها با استفاده از روش ژنتیک استخراج می شدند و روش های شبکه عصبی پرسپترون بر آنها اعمال می شد،دقت 98.1% حاصل می گشت [10].
یکی دیگر از ویژگی هایی که می توان در شناسایی اعداد از آن تاثیر گرفت، جهت حرکت قلم و یا جهت شکستگی ها می باشد. از این ویژگی بیشتر در حوزه های SVM، شبکه های عصبی [8] و مدل مخفی مارکوف [1] استفاده می شود. برای مشخص کردن جهت حرکت قلم ابتدا اسکلت عکس را استخراج می کنند. جهت قلم می تواند 4 سمت شمال، جنوب، شرق و غرب باشد. همچنین 4 جهت نیز با چرخش 45 درجه این جهت ها وجود خواهد داشت. اگر این جهت ها را در جهت چرخش عقربه ساعت شماره گذاری کنید در نتیجه، 8 سمت خواهید داشت. در شکل 5 دنباله مشاهدات برای عدد 1 نشان داده شده است. در روش مطرح در [1] از مدل مخفی مارکوف، روش جهت حرکت قلم استفاده گردیده تا تشخیص اعداد را انجام دهد. با توجه به اینکه براساس جهت حرکت قلم طراحی شده، برای هر رقم به ازای هر روش نوشتن از لحاظ جهت حرکت قلم یک مدل مخفی ایجاد شده است. هر مدل حداکثر 8 حالت انتقال و هر کدام آنها 8 مشاهده دارند که همان جهت حرکت قلم است. احتمالات انتقال بین حالتها و مشاهدات با توجه به شکلهای استاندارد و غیراستاندارد هر رقم تعیین می شود. در این مدلها ویژگی هدایت شوندگی دیده می شود، به این معنی که در مسیر حرکت بین حالتها امکان بازگشت به حالت قبلی وجود ندارد و مدل را مجبور به طی کردن یک مسیر مشخص می کند، که این ویژگی به تشخیص دقیق تر مدل کمک بسیاری کرده است. و در نهایت این روش دارای دقت 96.76% در تشخیص اعداد می باشد.
شکل 5 چند نمونه دنباله مشاهدات برای رقم 1 [11]
البته اگر در روش شناسایی جهت حرکت قلم، از روش قطعه بندی استفاده نمایید، به میزان دقت 94.4% خواهید رسید [11]. در روش قطعه بندی سعی می شود تا بعد از بدست آوردن اسکلت اعداد، بخش های مختلف اسکلت را از هم جدا نموده و هر بخش را جداگانه مورد بررسی قرار بدهند که این کار می تواند در شناسایی اعداد فارسی موثر واقع گردد.
روش مطرح دیگری که در این حوزه باقی می ماند، روش های آماری مانند بیز است. در [12] از مدل مخروطی گوسی برای تشخیص اعداد لاتین استفاده شده است و نتیجه حاصل، دقت 94% است. در این روش از مدل مخروطی گوسی در دو مرحله استفاده شده است که مرحله اول، برای تعیین زیر کلاسهای مربوط به هر عدد بوده و مرحله دوم، برای تخمین وفقی تابع چگالی احتمال هر زیر کلاس در قالب یک دسته بندی کننده بیز می باشد. اگر این روش با ترکیب روش های HMM و SVM استفاده شود، به میزان دقت 98% خواهید رسید [13].
روش های یادگیری نیمه نظارتی نیز از جمله روش هایی هستند که مورد توجه قرار دارند. روشهای نیمه‌نظارتی دسته‌ای از روشهای یادگیری ماشین است که در آن از داده‌های بدون برچسب و داده‌های برچسب‌دار به صورت هم‌زمان برای بهبود دقت یادگیری استفاده می‌شود. در این نوع آموزش تعداد کمی از داده ها برچسب دارند و مابقی بدون برجسب مورد استفاده قرار خواهند گرفت. این روش ها اکثراً بر روی شبکه های عصبی اعمال می شوند. این در حالی است که خود شبکه های عصبی عضو روش های نظارتی هستند. این روش دو بخش عمده دارد، در بخش اول پیش آموزش بدون نظارت مطرح می شود که در آن وزن های لایه ها با استفاده از آموزش بدون نظارت مقدار دهی اولیه می شوند. در بخش دوم که fine-tuning نام دارد، وزنهای عمومی که با برچسب ها آموزش دیده اند بر روی روش های نظارتی به صورت انتشار عقبگرد اعمال می شوند. همه روش هایی که به این صورت عمل می کنند را روش نیمه نظارتی می گویند. داده های بدون برچسب نیز داده هایی هستند که بیشترین احتمال را برای یک کلاس داشته باشند و کلاس آنها نیز درست پیش بینی شده باشد. این روش می تواند همه مدل های شبکه های عصبی را با روش های آموزش به خوبی ترکیب کند. این روش در [14]، به صورت کامل مطرح شده و از نمونه های MNIST نیز استفاده کرده است تا شناسایی اعداد را انجام دهد. این کار را با چندین روش مقایسه کرده و همه آنها را با تعداد نقاط آموزشی 100، 600، 1000 و 3000 انجام داده است. برای تست نیز از 1000 نمونه استفاده کرده است که در جدول 2 میزان خطای کلاس بندی نشان داده شده است (در [14] روش های +dropNN، PL و روش +PL+DAE مطرح شده است). عمومآً برای جلوگیری از overfitting از روش drop کردن استفاده می شود که بدین منظور، از آموزش نظارتی استفاده می شود. در روش +PL به شبکه های عصبی آموزش بدون برچسب نیز اضافه شده است و در +PL+DAE ، به آموزش بدون برچسب بدون نظارت، DAE نیز اضافه می شود. DAE را در بخش اول یعنی در پیش آموزش بدون نظارت استفاده می کنند.
| روش | 100 | 600 | 1000 | 3000 |
|---|---|---|---|---|
| NN | 25.81 | 11.44 | 10.7 | 6.04 |
| SVM | 23.44 | 8.85 | 7.77 | 4.21 |
| CNN | 22.98 | 7.68 | 6.45 | 3.35 |
| TSVM | 16.81 | 6.16 | 5.38 | 3.45 |
| DBN-rNCA | - | 8.7 | - | 3.3 |
| EmbedNN | 16.86 | 5.97 | 5.73 | 3.59 |
| CAE | 13.47 | 6.3 | 4.77 | 3.2 |
| MTC | 12.03 | 5.13 | 3.64 | 2.57 |
| dropNN | 21.89 | 8.57 | 6.59 | 3.72 |
| +PL | 16.15 | 5.03 | 4.30 | 2.80 |
| +PL+DAE | 10.49 | 4.01 | 3.46 | 2.69 |
جدول 2 میزان خطای روش های مختلف که برای تشخیص اعداد است و با 100، 600، 1000 و 30000 نقطه آموزشی [14]
همان طور که در جدول 2 مشاهده می شود، روش های نیمه نظارتی شبکه های عصبی +PL+DAE دارای خطای کمتری است. ولی با این تفاوت که در تعداد نمونه های زیاد میزان خطای روش MTC از همه کمتر است.
هرچند نمی توان همه این روش ها را، به دلیل برابر نبودن وضعیت داده های آموزشی، تعداد آنها و همچنین نوع زبان، با هم مقایسه کرد. ولی با توجه به درصدهایی که ارائه شده اند می توان به این نتیجه رسید که روش های شبکه های عصبی و همچنین شبکه های عصبی نیمه متمرکز، نتایج مطلوب تری را در بر خواهند داشت. در ادامه نیز برای انجام آزمایشات با استفاده از روش نمونه برداری ارائه شده در مرجع [2]، روش آموزشی SVM و همچنین داده های آموزشی استفاده شده در مرجع [6]، سعی می شود تا یک روش آموزشی مورد سنجش و ارزیابی قرار گیرد.
آزمایش‌ها
برای انجام آزمایش، در ابتدا باید پایگاه داده اعداد دستنویس فارسی را در نظر گرفت که ما در این آزمایش از اعداد فارسی موجود در مرجع [6] استفاده خواهیم کرد. در این پایگاه داده 60000 داده آموزشی وجود دارد (برای هر یک از اعداد صفر تا نه، 6000 نمونه). همچنین، 20000 نمونه نیز برای تست در این پایگاه داده وجود دارد (برای هر کدام از اعداد صفر تا نه، 2000 نمونه).
روش کار مدنظر، متناسب با روش ارائه شده در [2] می باشد. همان طور که در روش مربوطه نیز ذکر شد، در ابتدا داده ها باید نرمال سازی شوند. در ابتدا همه عکس ها را به عکس های 64*64 تبدیل می کنیم. برای انجام این کار در متلب از دستور {[Data{i} = imresize(Data{i}, [64 64استفاده می کنیم که منظور از {Data{i، نمونه ها و یا عکس ها می باشد. در شکل 6 یکی از نمونه های آموزشی، قبل (بالایی) و بعد (پائینی) از نرمال سازی نشان داده شده است.
شکل 6 یکی از نمونه های مجموعه داده های آزمایشی که عدد 6 را نشان می دهد.
بدست آوردن ویژگی ها
با توجه به خاکستری بودن رنگ عکسها، برای هر رنگ یک عدد بین 0 تا 255 در نظر گرفته می شود. در هر عکس 64 ستون و 64 سطر وجود دارد. می توان هر عکس را از چهار دیدگاه بالا، پایین، چپ و راست مورد مشاهده قرار داد و نقاط سفید را برای هر چهار دیدگاه شمارش نمود تا به اولین عنصری که رنگ متفاوت با سفید دارد برسیم. به دلیل اینکه رنگ عکس ها را معکوس کرده ایم، نوشته ها سفید و ضمینه سیاه خواهد شد. این کار را برای دیدگاه های چپ و راست (بر روی 64 سطر موجود) و بر روی سطرهای ضرایب 8 انجام می دهیم. همچنین، برای دیدگاه های بالا و پائین (بر روی 64 ستون موجود) بر روی ستون های ضرایب 8 نیز این کار را تکرار می کنیم. اگر به شکل 6 توجه کنید، مشاهده می شود که، در سطر اول از چپ به راست 11 خانه صفر وجود دارد و همچنین 43 خانه صفر نیز از راست به چپ داریم. به علاوه در ستون اول از دیدگاه های بالا و پایین نیز به ترتیب 13 و 35 خانه صفر وجود دارد.
شکل 7 دیدگاه های بالا و پائین، و چپ و راست از نمونه مورد بررسی در شکل 6.
در شکل 7 نمونه های برداشت شده از شکل 6 نشان داده شده است. بعد از بدست آوردن همه این اطلاعات، از هر یک از نمونه ها، در هر دیدگاهش، شیب بین نقطه هایش را بدست می آوریم.
پس برای هر دیدگاه 15 ویژگی خواهیم داشت که از این رو در کل برای هر نمونه، 60 ویژگی تعریف خواهد شد. در شکل 8، یک نمونه از ویژگی های حاصله، از دیدگاه های، به ترتیب از چپ به راست، بالا، پایین، راست و چپ برای اعداد 0 تا 9 نشان داده شده است.برای انجام اینکار از نرم افزار متلب استفاده شده است. با استفاده از قطعه کد زیر می توان دیدگاه ها را از نمونه ها بدست آورد.
for Fleft = 1:16
CFCount = 1;
while (CFCount<65 && 0 == IMaGeF((Fleft)*4,CFCount))
Left(i,Fleft) = Left(i,Fleft)+1;
CFCount = CFCount+1;
end
if Fleft>2
MLeft(i,Fleft-1) = Left(i,Fleft) - Left(i,Fleft-1);
end
end
% Right cal
for Fleft = 1:16
CFCount = 1;
while (CFCount<65 && 0 == IMaGeF((Fleft)*4,65-CFCount))
Right(i,Fleft) = Right(i,Fleft)+1;
CFCount = CFCount+1;
end
if Fleft>2
MRight(i,Fleft-1) = Right(i,Fleft) - Right(i,Fleft-1);
end
end
% TOP cal
for Fleft = 1:16
CFCount = 1;
while ( CFCount<65 && 0 == IMaGeF(CFCount,(Fleft)*4))
TOP(i,Fleft) = TOP(i,Fleft)+1;
CFCount = CFCount+1;
end
if Fleft>2
MTOP(i,Fleft-1) = TOP(i,Fleft) - TOP(i,Fleft-1);
end
end
% Down cal
for Fleft = 1:16
CFCount = 1;
while (CFCount<65 &&0 == IMaGeF(65-CFCount,(Fleft)*4))
DOWN(i,Fleft) = DOWN(i,Fleft)+1;
CFCount = CFCount+1;
end
if Fleft>2
MDOWN(i,Fleft-1) = DOWN(i,Fleft) - DOWN(i,Fleft-1);
end
end
%end hadi
که در این کد متغیر IMaGeF نمونه های ما می باشد.
شکل 8 دیدگاه های بالا و پائین و چپ و راست یک نمونه از هر یک از مجموعه نمونه های اعداد صفر تا یک.
ویژگی های هر نمونه را با استفاده کد ذیل در متغیر MALLDATA قرار می دهیم.
MALLDATA = zeros(TotalRec,60);
MALLDATA(1:end,1:15) = MTOP(1:end,1:end);
MALLDATA(1:end,16:30) = MDOWN(1:end,1:end);
MALLDATA(1:end,31:45) = MRight(1:end,1:end);MALLDATA(1:end,46:60) = MLeft(1:end,1:end);
و با استفاده از کد زیر با استفاده از روش SVM سعی می کنیم تا نمونه ها را یاد بگیریم.
for i=0:9
Group = MakesGroups_SVM(i,labels);
svmStruct(i+1) = svmtrain(MALLDATA,Group, 'kernel_function', 'polynomial');
end;
برای انجام عمل آموزش با توابع خطی و چند جمله ای و گوسی استفاده شد که در گوسی و خطی آموزش روند آموزش دچار مشکل می شد و به جواب نمی رسید. ولی در تابع چند جمله درجه 3 به جواب با دقت 90.87% دست پیدا کردیم. برای انجام عمل تست نیز از تابع ذیل استفاده شده است که از بین 20000 نمونه 1867 نمونه را درست تشخیص نداده است. در این مجموعه، از هر کلاس 2000 نمونه وجود دارد.
DT_lables = zeros(10,TotalRec);
for i =1:10
DT_lables(i,1:end) = svmclassify(svmStruct(i),MALLDATA);
end;
در کلاس های 0 تا 9 به ترتیب 205، 145، 216، 279، 338، 238، 186، 55، 53، 152 مورد نادرست تشخیص داده شده است. همان طور که ملاحظه می شود در این کلاس ها، کلاس 8 از همه کلاس ها کمترین خطا را دارد. اگر بخواهیم این خطاها را بهتر تحلیل کنیم، باید به جدول 3 بیشتر توجه کنیم.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | NON | sum | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 27 | 8 | 4 | 8 | 69 | 12 | 17 | 5 | 10 | 45 | 205 |
| 1 | 73 | 0 | 1 | 0 | 1 | 18 | 1 | 0 | 0 | 3 | 48 | 145 |
| 2 | 13 | 26 | 0 | 32 | 11 | 12 | 3 | 3 | 0 | 6 | 110 | 216 |
| 3 | 11 | 7 | 124 | 0 | 36 | 9 | 3 | 1 | 1 | 2 | 85 | 279 |
| 4 | 14 | 21 | 16 | 57 | 0 | 68 | 16 | 7 | 2 | 25 | 112 | 338 |
| 5 | 83 | 27 | 4 | 1 | 1 | 0 | 17 | 28 | 20 | 17 | 40 | 238 |
| 6 | 14 | 22 | 7 | 0 | 3 | 4 | 0 | 5 | 3 | 62 | 66 | 186 |
| 7 | 5 | 4 | 8 | 0 | 0 | 3 | 4 | 0 | 0 | 4 | 27 | 55 |
| 8 | 2 | 2 | 0 | 1 | 0 | 6 | 0 | 0 | 0 | 30 | 12 | 53 |
| 9 | 10 | 21 | 6 | 2 | 1 | 4 | 33 | 0 | 10 | 0 | 65 | 152 |
| sum | 225 | 157 | 174 | 97 | 61 | 193 | 89 | 61 | 41 | 159 | 610 | 1867 |
جدول3 جدول خطا ها
در جدول 3 میزان هر خطا و نوع اشتباه در تشخیص را نشان می دهد. در این جدول ستون ها کلاس های بدست آمده اند و سطر ها کلاس های واقعی نمونه ها هستند. به عنوان نمونه در ستون 0 با سطر 1 نشان می دهد که در کلاس 0 ای که تشخیص داده شده 73 مورد را صفر را، یک تشخیص داده است. همچنین، در ستون 1 و سطر صفر، 27 مورد 1 را به اشتباه صفر تشخیص داده است. همان طور که ملاحظه می شود، 83نمونه صفر، عدد 5 تشخیص داده می شوند و بعد از آن عدد 1 می باشد. همچنین، عدد 2 با عدد 3، 3 با 4، 4 با 3، 5 با 1 و صفر، 6 با 9، 7 و 8 با 5 و 9 با 6 هستند که بیشترین اشتباه ها را دارند. در این دسته از کلاس ها به غیر از کلاس های 0 تا 9 یک دسته با NON نیز وجود دارد که این کلاس نشان می دهد که این دسته را نمی تواند تشخیص دهد که از چه نوعی است.
همچنین شما می توانید کد ها و نمونه ها را از اینجا دریافت کنید.
بهبود نتایج آزمایشات
همان طور که در مرحله قبلی گفته شد، توانستیم تا با روش SVM به دقت 90% برسیم، برای بهبود کار، سعی بر آن شد تا از روش های گروهی 3 استفاده شود. همان طور که بیان شد 60000 نمونه آموزشی و 20000 نمونه تست در مجموعه نمونه ها وجود دارد که می توان از آن برای آموزش 7 تا SVM با 8000 نمونه آموزشی مختلف تولید کرد (در کل 78000=56000 نمونه استفاده خواهد شد). در قطعه کد زیر طریقه تولید SVM ها نشان داده شده است. پس در کل از این داده های آموزشی 78000 نمونه آموزشی استفاده می شود و لازم به توجه است که داده های آموزشی برای آموزش هر SVM با هم متفاوت هستند، حتی یک نمونه برابر هم ندارند. بنابراین، این SVM ها هیچ وابستگی ای به هم ندارند.
step = 8000;
[data, labels, TOTALM] = ReadDATA();
totalsvmn = 7;
for i=1:totalsvmn
traninedsvmStructure((i-1)*10+1:(i)*10) = ReadCDB_Matlab_SVMTraining((i-1)*step+1,(i)*step, data , labels);
end;
در این آزمایش از هسته های مختلف برای آموزش استفاده شده است که نتایج را در ادامه مقایسه خواهیم کرد. تابع ReadCDB_Matlab_SVMTraining را در قطعه کد زیر مشاهده می کنید. لازم به توضیح است که برای تولید SVM ها با هسته های مختلف فقط کافی است که نام polynomial را با هسته مورد نظر خود جایگزین کنید مانند rbf و یا اگر خواستید که درجه polynomial را از حالت معمولی که 3 می باشد تغییر دهید ,'polyorder', p را به ورودی های تابعی svmtrain اضافه کنید که p درجه چند جمله ای از درجه p را نشان می دهد.
function [ svmStruct ] = ReadCDB_Matlab_SVMTraining(a , b , MALLDATA ,labels)
MALLDATAME = MALLDATA(a:b,1:end);
labelsME = labels(a:b);
for i=0:9
Group = MakesGroups_SVM(i,labelsME);
%'Kernel_Function','rbf','rbf_sigma', 0.1,'boxconstraint',1000 /// ,'polyorder', 5
svmStruct(i+1) = svmtrain(MALLDATAME,Group, 'kernel_function', 'polynomial');
end;
end
تا این محل از کار، نمونه ها را با 7 تا SVM که آنها از SVM1 تا SVM7 نام گذاری شده اند و هیچ وابستگی ای به همدیگر ندارند، آموزش داده اید و آماده برای تست هستند.
برای تست این موارد می توان از قطعه کد زیر استفاده کرد. در این راستا، ابتدا نمونه های تست را می خواند و با استفاده از تابع ReadCDB_Matlab_SVMTesting نمونه ها را مورد تست قرار می دهد. در ادامه نیز میزان خطای هر تک SVM را به ازای هر نمونه تست شده بدست می آورد.
[data, labels, TotalRec] = ReadDATATesting();
labels_s = zeros(TotalRec,totalsvmn);
for i=1:totalsvmn
svm = traninedsvmStructure((i-1)*10+1:(i)*10);
labels_s(:,i) = ReadCDB_Matlab_SVMTesting(svm,data,TotalRec);
end;
ERROR = zeros(1,totalsvmn + 2); % the last col. is final error count voting, + bayes
% calculate each svm error count.
for j = 1:totalsvmn
for i = 1:TotalRec
if(labels_s(i,j) ~= labels(i))
ERROR(1,j) = ERROR(1,j) + 1;
end;
end;
end;
در شکل 18 میزان خطای هر روش را نشان می دهد. برای تولید SVM ها ابتدا از هسته های مختلف از جمله rbf استفاده کردیم و مشاهده شد که در تولید فضای بُرش دچار مشکل می شود و یا دقت خوبی ندارد. بنابراین از هسته polynomial برای این امر استفاده شد. در این راستا، برای این هسته نیز از درجه های چند جمله ای مختلف مانند 1،2،3،4 و 5 استفاده شد. همان طور که در شکل 18 مشاهده می شود میزان دقت هر یک از این 7 تا SVM بیان شده است که در درجه چند جمله ای 3 از همه دقت بهتری دارد. ولی در درجه چند جمله ای 2 دقت کمی از درجه 3 کمتر است. حال کدام بهترند؟ لازم به توضیح است که دقت در درجه های 4 و 5 نیز به شدت در حال کاهش است که نشان می دهد که از درجه 3 به بعد آموزش در حال overtraning می باشد.
حال می توان نتایج را به صورت یک نتیجه گروهی و تصمیم گروهی در نظر گرفت. در ایجا دو روش رای گیری وزندار و بیز ساده شده 4 مد نظر قرار داده شده است و آنها را با هم مقایسه می کند.
برای انجام رای گیری وزن دار در ابتدا باید وزن ها را استخراج کرد. در اینجا، برای هر SVMiای، یک وزن با فرمول w_i=log(P_i/1-P_i) که 1>P_i>0 دقت SVMi را نشان می دهد، بدست می آید. قطعه کد زیر وزن ها را بدست می آورد و با استفاده از تابع CountNumberForVoting سعی میکند تا رای گیری وزندار انجام دهد و نتیجه را در متغیر index قرار می دهد. در ادامه نیز میزان خطای این روش محاسبه شده که در شکل 18 میزان خطای رای گیری وزن دار در کنار هر تک SVM بیان شده است.
ACRate = 100.0 - (ERROR*100.0)/TotalRec;
w = zeros(totalsvmn,1)*1.0;
for i=1:totalsvmn
w(i) = log10(ACRate(i)*.01/(1-ACRate(i)*.01));
end;
[numbers,index] = CountNumberForVoting(labels_s,TotalRec, totalsvmn,w);
ERROR(1,totalsvmn + 1) = 0;
for i = 1:TotalRec
if(index(i) ~= labels(i))
ERROR(1,totalsvmn + 1) = ERROR(1,totalsvmn + 1) + 1;
end;
end;
در شکل ها 9 تا 15 ماتریس اختلال5 را برای هر یک از SVMi با هسته چند جمله ای از درجه 3 نشان داده شده است که در قطعه کد طریفه بدست آمدن آن نوشته شده است. در شکل 16 ماتریس اختلال روش رای گیری وزن دار نشان داده شده است. در این ماتریس ها، سطر بیان کننده کلاس های درست و واقعی هستند که از 0 تا 9 نام گذاری می شوند و ستون ها کلاس های پیشبینی شده از ماشین می باشد که بین 0 تا 10 می باشد که ستون 10ام نشان دهنده این است که جزء هیچ یک از کلاس های 0 تا 9 بیشبینی نشده است و آن نمونه ها را اصلاً عدد تشخیص نداده است.
CM = zeros(10*(totalsvmn+2),11);
for i=1:totalsvmn
CM(10*(i-1)+1:10*(i),:) = Confusion_Matrix(labels_s(:,i),labels,TotalRec);
end;
CM(10*totalsvmn+1:10*(totalsvmn+1),:) = Confusion_Matrix(index,labels,TotalRec);
که تابع ماتریس اختلال نیز در ذیل مشاهده می شود.
function [ CM ] = Confusion_Matrix( e_labels, t_labels, len )
CM = zeros(10,11);
for i=1:len
if(e_labels(i) == -1)
CM(t_labels(i)+1,11)=CM(t_labels(i)+1,11)+1;
else CM(t_labels(i)+1,e_labels(i)+1)=CM(t_labels(i)+1,e_labels(i)+1)+1;
end;
end;
end
جهت مقایسه روش، در کنار روش رای گیری وزن دار از روش بیز ساده شده نیز استفاده شد. روش بیز ساده شده نیز با توجه به ماتریس اختلال ها کار خود را برای پیشبینی گروهی انجام می دهد و خاستار یک درصد خطای بهتری از رای گیری وزن دار می باشد. در قطعه کد زیر روش بیز ساده شده و روش بدست آوردن میزان خطای این روش نشان داده شده است. نتیجه حاصله از بیز ساده شده در Bayes_c قرار می گرید. در شکل 17 ماتریس اختلال به خوبی نشان داده شده است.
Bayes_c = NaiveBayes_1(10, step, TOTALM, CM, TotalRec, labels_s, totalsvmn);
ERROR(1,totalsvmn + 2) = 0;
for i = 1:TotalRec
if(Bayes_c(i) ~= labels(i))
ERROR(1,totalsvmn + 2) = ERROR(1,totalsvmn + 2) + 1;
end;
end;
CM(10*(totalsvmn+1)+1:end,:) = Confusion_Matrix(Bayes_c,labels,TotalRec);
ACRate = 100.0 - (ERROR*100.0)/TotalRec;
کد بیز ساده شده نیز در زیر مشاهده می کنید.
function [ Bayes_C ] = NaiveBayes_1( C, Nk, NT, CM, TOTN, e_labels, L )
%UNTITLED Summary of this function goes here
% Detailed explanation goes here
Bayes_C = ones(TOTN,1)*-1;
Bayes_R = ones(TOTN,1)*-1.0;
Nk = Nk*1.0;
c = 1/C*1.0;
for p=1:TOTN
for k=1:C
PK = Nk/NT;
for i=1:L
x = K(CM, k, e_labels(p,i), i);
PK = PK * ((x + c)/(Nk+1));
end;
if PK>Bayes_R(p)
Bayes_R(p) = PK;
Bayes_C(p) = k-1;
end;
end;
end;
end
function [r] = K(CM, k, si, i)
if si ~= -1
r = CM(10*(i-1) + (k) ,(si+1));
else r = CM(10*(i-1) + (k) ,11);
end;
end
حال که نتیجه های رای گیری وزن دار و روش بیز ساده شده را در دسترس داریم، به راحتی می توانیم آنها را مورد مقایسه هم قرار دهیم که این مباحث را تحت عنوان نتیجه گیری در ادامه مطرح می کنیم.
نتیجه گیری و کارهای آینده
همان طور که در شکل های 9 تا 15 نشان داده شده است. هر روش SVM با هم متمایز بوده و میزان خطا و دقت خاص خود را دارا هستند که این در ستون آخر که برای بیش بینی نشدن نمونه ها به عنوان اعداد می باشد به خوبی محسوس می باشد. به همین امر است که بعد از گروهی تصمیم گرفتن در ماتریس تداخل های شکل های 16 و 17 ستون آخر صفر شده اند. لازم به توضیح است که دلیل متمایز بودن SVMi ها متمایز بودن نمونه های آزمایشی است.
همچنین این امر در شکل 18 که نتیجه حاصلی این پروژه می باشد به خوبی نشان داده شده است. ولی با این وجود به دلیل سخت بود روش SVM دقت نهایی به میزان 4 درصد افزایش داشته است که از جمله دلایل آن تعداد کم روش ها SVM می تواند باشد که اگر این تعداد از 7 تا SVM حدود 30 تا 40 SVM برسد شاید دقت بهتری را نشان بدهد. در ضمن همانطور که در همین شکل نشان داده شده است، در همه موارد میزان دقت روش بیز ساده شده از روش رای گیری وزن دار بهتر است.
در نتیجه، در این پروژه از روش SVM استفاده شده که بتوان اعداد دست نویس فارسی را تشخیص داد. در این راستا 7 SVM آموزش دیدند که در این میان SVM های چند جمله ای از درجه 3 و 2 از همه بهتر بوده اند ولی بعد از تصمیم گیری گروهی با استفاده از دو روش رای گیری وزن دا و بیز ساده شده بر روی آنها دقت نهایی افزایش پیدا کرد، همان طور که در شکل 18 نشان داده شده است میزان دقت روش بیز ساده شده از رای گیری وزن دار بیشتر است. در نهایت نیز SVM های چند جمله درجه 2 با روش تصمیم گیری گروهی بیز ساده شده دقت بهتری بر روی نمونه های تست شده داشته است.
همچنین شما می توانید کد ها و نمونه ها را از اینجا دریافت کنید. همچنین برای اجرای کد نیز با اجرای اسکریپت SVMTraining هم قسمت آموزش و هم قسمت آزمون و نتیجه های مشاهده شده در برنامه به خوبی اجرا و قابل مشاهده می باشد.
مراجع
[1] ا. ابراهمی مقدم, و. فاضلی نیا, ل. رشیدی و م. وفایی جهان, “تشخیص دست نویس رقم لاتین توسط مدل مخفی مارکوف,” در اولین همایش ملی مهندسی رایانه و مدیریت فناوری اطلاعات, 1393.
[2] 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.
[3] م. اشکواری و م. کبانی, “تشخیص اعداد دست نویس فارسی با استفاده از تکنیک PCA و شبکه عصبی,” در همایش منطقه ای علوم کامپیوتر، مهندسی کامپیوتر و فناوری اطلاعات, خرداد 1391.
[4] J. Franke and M. Oberlander, "Writing style detection by statistical combination of classifiers in form reader applications," in Second International Conference on Document Analysis and Recognition, 1993.
[5] C. Tanprasert and S. Sae Tang, "Thai type style recognition," in IEEE International Symposium on Circuits and Systems.
[6] H. Khosravi and E. Kabir, "Introducing a very large dataset of handwritten Farsi digits and a study on their varieties," Pattern Recognition Letters, vol. 28, pp. 1133-1141, 2007.
[7] M. A. Shayegan and S. Aghabozorgi, "A New Dataset Size Reduction Approach for PCA-Based Classification in OCR Application," Mathematical Problems in Engineering, pp. 1-14, 2014.
[8] ع. جعفرنژاد, “ارائه یک سیستم کارآمد برای شناسایی اعداد دست نویس با استفاده از شبکه عصبی,” در اولین کنفرانس ملی رویکردهای نویس در مهندسی کامپیوتر و بازیابی اطلاعات ایران, 15 مهر 1392.
[9] M. A. Abu-Zanona and B. M. El-Zaghmour, "Current Arabic ( Hindi ) Hand Written Numbers Segmentaion and Recognition Advance ImageProcessing and Neural Network," Journal of Emerging Trends in Computing and Information Sciences, vol. 3, no. 6, pp. 936-941, 2012.
[10] م. ل. افراسیابی, ز. فرهمندپور و ح. ختن لو, “تشخیص اعداد دست نویس عربی با استفاده از ترکیب الگوریتم ژنتیک و شبکه عصبی,” در سومین کنفرانس مهندسی برق و الکترونیک ایران, 22 تیر 1390.
[11] م. زیارت بان, ک. فائز, س. مظفری و م. ازوجی, “ارائه یک روش ساختاری جدید مبتنی بر قطعه بندی تصویر نازک شده برای شناسایی اعداد دست نویس فارسی/عربی,” در سویمن کنفرانس ماشین بینایی و پردازش تصویر ایران, 1383.
[12] م. ر. ارباب شیرانی و م. ت. صادقی, “بازشناسی خودکار اعداد دست نویس لاتین با استفاده از مدل گوسی دو مرحله ای,” در پانزدهمین کنفرانس مهندسی برق ایران.
[13] ع. برومند نیا و ا. امیری, “تشخیص اعداد فارسی (عربی) با استفاده از ساختار ترکیبی SVM/HMM,” در اولین کنفرانس ملی محاسبات نرم و فناوری اطلاعات.
[14] D.-H. Lee, "Pseudo-Label : The Simple and Effcient Semi-Supervised Learning Method for Deep Neural Networks," in Challenges in Representation Learning (WREPL), Atlanta, Georgia, USA, 2013.
پیوندهای مفید
Frequency Diagram
similarity
ensemble
Naive Bayes
confusion matrix