کاهش ویژگی توسط اذحام ذرات دودویی برای بازشناسی ارقام دستنویس فارسی

نوع مقاله: مقاله علمی فارسی

نویسندگان

1 دانشجوی کارشناسی ارشد برق، دانشکده مهندسی برق و رباتیک- دانشگاه صنعتی شاهرود- شاهرود- ایران

2 عضو هیأت علمی، دانشکده مهندسی برق و رباتیک- دانشگاه صنعتی شاهرود- شاهرود- ایران

چکیده

: بازشناسی ارقام دستنویس یکـی از مسائل مهم درحوزه شناسی الگو است. در این مقاله با ترکیب روشهای هیستوگرام گرادیان و مکان مشخصه توسعه یافته، ویژگیهای تصاویر ارقام دستنویس فارسی استخراج شده است. توسط الگوریتم بهینه سازی توده ذرات دودویی بهبود یافته جدید (INBPSO) و ارائه تابع برازندگی مناسب، ویژگیها با اهمیت بیشتر انتخاب و ارقام توسط طبقه بند ماشین بردار پشتیبان (SVM) شناسایی شده‌اند. ابتدا در مرحله آموزش پس از استخراج ویژگی بر روی داده‌های آموزش با استفاده از روش پیشنهادی، الگوی مناسبی برای انتخاب ویژگی بدست می‌آید سپس در مرحله آزمون پس از استخراج ویژگی داده‌های آزمون بردار ویژگی توسط الگوی بدست آمده کاهش داده شده و عمل طبقه بندی نهایی صورت می‌گیرد. با اعمال روش ذکر شده روی پایگاه داده تصاویر ارقام دستنویس فارسی هدی، دقت بازشناسی99.40% بدون کاهش ویژگی و دقت بازشناسی 99.28% با کاهش ویژگی بدست آمده است. مقایسه نتایج با کار محققان دیگر حاکی از آن است روش ارائه شده در استخراج ویژگی و انتخاب ویژگی از کارآیی مناسبی برخوردار است.

کلیدواژه‌ها


عنوان مقاله [English]

Feature Reduction Using Binary PSO towards Recognition of Farsi Handwritten Digits

نویسندگان [English]

  • mohsen sedighinav 1
  • ali Soleimani 2
  • Hossein khosravi 2
1 Dept. of Electrical Engineering, Shahrood University of technology, shahrood, Iran
2 Dept. of Electrical Engineering, Shahrood University of technology, shahrood, Iran
چکیده [English]

Recognition of handwritten digits is one of the most important problems in Optical Character Recognition (OCR) domain. In this paper a combination of two features, gradient histogram and modified characteristic Loci, are used for Persian handwritten digits. Furthermore, the most important features are selected using improved New Binary Particle Swarm Optimization algorithm (INBPSO) with an appropriate fitness function. SVM is used for classification of the digits. Having the selection pattern found in the training phase, the extracted features of the test samples are reduced using this pattern and then the final vector of the selected features are classified with the trained SVM model. The proposed method is applied on HODA database. Without reducing the features we achieved 99.40% accuracy and after reducing, the accuracy of 99.28% is reached. Comparing the results with the previous works, indicates that the proposed method has better performance in feature extraction and feature selection.

کلیدواژه‌ها [English]

  • Handwritten Recognition Digits
  • Gradient Histogram
  • Modified Characteristic Loci
  • Improved New Binary Particle Swarm Optimization
  • Support Vector Machine

بازشناسی ارقام دستنویس کاربردهای زیادی در شناسایی کدهای درج شده بر فرم­های مختلف و چک­های بانکی و کدپستی دارد[1]. استفاده از یک سیستم بازشناسی ارقام دستنویس، در عمل با چالش‌هایی مواجه است که مهمترین آنها ضرورت بالا بودن نرخ باز­شناسی است. در حوزه زبان فارسی به علت شباهت زیادی که ارقام به هم دارند و همچنین، تفاوت در شیوه رسم آنها، ایجاد یک سیستم بازشناسی با دقت قابل قبول برای استفاده عملی با مشکلاتی مواجه است. از این رو، توسعه روشها برای بالا بردن نرخ بازشناسی در آنها ضروری است. روش­های مختلفی برای شناسایی ارقام دستنویس، به ویژه در زبان فارسی ارائه شده است که از جمله آنها می­توان به روشهای آماری و ساختاری و روشهای مبتنی بر تبدیلات اشاره نمود. انتخاب روش استخراج ویژگی، مهمترین عامل در بازشناسی الگو مطرح است]2[. برای بازشناسی ارقام و حروف از ویژگی­های ناحیه­ای]3[، گشتاورهای هندسی]4[، گشتاورهای زرنیکی]5 [، توصیفگرهای فوریه]6[، پایا­های گشتاوری]7[، هیستوگرام­نما و ویژگی­های مکان مشخصه ]8[ استفاده شده است. یکی دیگر از کارهای مؤثر در بالا بردن نرخ بازشناسی، تفکیک ویژگی‌هایی است که علاوه بر اینکه در بالا بردن نرخ بازشناسی نقشی ندارند، به کاهش نرخ بازشناسی نیز منجر می‌شوند. با انتخاب زیر مجموعه مناسب از ویژگی­های استخراجی می­توان در بالا نگه داشتن نرخ بازشناسی گام مناسبی برداشت.

الگوریتم‌های زیادی برای استخراج ویژگی بررسی و معرفی وسپس استفاده می‌شوند و حتی هم اکنون نیز در راه بهبود این الگوریتم­ها پژوهش­ها و مقالات زیادی در دست اجراست و هر یک به نوبه خود در جایی که استفاده می‌شوند، مزیت­ها و محدودیت­هایی دارند. این الگوریتم­ها داده‌ها را در ابعاد مختلف تولید می‌نمایند. همچنین، پردازش سریع اطلاعات به عنوان چالشی برای پژوهشگران محسوب می‌شود و برای پردازش سریع و بلادرنگ به داده‌ها با ابعاد ویژگی کم نیاز است. ویژگی‌هایی نیز در بین این داده‌های استخراجی وجود دارد که اثر سوء بر نرخ بازشناسی دارند. در همین راستا، بهتر است علاوه بر پژوهش و استفاده از انواع روشهای استخراج ویژگی، روی مسأله انتخاب ویژگی نیز تمرکز کرده، با کاهش ابعاد داده سرعت و دقت شناسایی را بالا نگه داریم.

در پژوهش ­هایی که در زمینه بازشناسی ارقام دستنویس فارسی صورت گرفته، پایگاه داده استانداردی ارائه شده است. این پایگاه از 102352 تصاویر ارقام دودویی که از حدود 11942 از دو نوع فرم ثبت نام آزمون سراسری، که توسط دانشجویان مقاطع کارشناسی و کارشناسی ارشد پرشده، استخراج شده است. از این فرم­ها دونوع پایگاه داده ارقام و حروف تهیه شده است که در این مقاله از پایگاه داده ارقام آن استفاده شده است. تعداد کل ارقام این پایگاه داده 102352 رقم است که 60000 رقم آن به عنوان داده‌های آموزش و 20000 رقم آن به عنوان نمونه­های آزمایش استفاده شده و 22352 رقم آن هم به عنوان ارقام باقی مانده در نظر گرفته شده است]9[. شکل (1) تعدادی از این ارقام را نشان می‌دهد.

                       

شکل (1): نمونه ای از اعداد پایگاه داده هدی

 

در این مقاله، ابتدا سیستم پیشنهادی برای شناسایی ارقام دستنویس فارسی معرفی شده است. در بخش 3 دو روش استخراج ویژگی معرفی شده است، در بخش 4 بهینه سازی توده ذرات معرفی شده است و در انتها در بخش 5 نتایج به­دست آمده با استفاده از روش پیشنهادی قرار داده شده است.

 

1- معرفی سیستم پیشنهادی

در سیستم پیشنهادی برای بازشناسی ارقام دستنویس فارسی مطابق شکل (2)، مجموعه داده‌های آزمون و آموزش به طور جداگانه در دو مرحله بررسی می­شوند. در مرحله آموزش، ابتدا ویژگی­های ارقام دستنویس فارسی با استفاده از ترکیب الگوریتم‌های هیستوگرام گرادیان و مکان مشخصه توسعه یافته استخراج می­شود. سپس با استفاده از الگوریتم PSO دودویی بهبود یافته، الگویی از نحوه انتخاب ویژگی­ها برای داشتن بهترین دقت و کمترین تعداد ویژگی به­دست آمده و نیز پارامتر‌های مربوط به طبقه بند SVM که برای محاسبه تابع برازندگی استفاده شده، ذخیره می­شود. برای مجموعه آزمون در مرحله آزمون، ابتدا ویژگی‌های ارقام با استفاده از ترکیب الگوریتم‌های هیستوگرام گرادیان و مکان مشخصه توسعه یافته استخراج شده، سپس با استفاده ازالگوی به­دست آمده در مرحله آموزش، ویژگی‌ها برای هر رقم انتخاب می­شود. در نهایت، با استفاده از پارامترهای مربوط به طبقه بند SVM که در مرحله آموزش به­دست آمد، بازشناسی انجام گرفته و درصد تشخیص برای مجموعه آزمون به­دست می­آید.

 

 

 

شکل (2): سیستم پیشنهادی برای بازشناسی ارقام دستنویس

 

 

2- استخراج ویژگی

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

 

2-1- الگوریتم هیستوگرام گرادیان

1 - ابتدا تصویر ارقام به اندازه64×64 نرمال شده و سپس به 16 بلوک غیر همپوشان با ابعاد 16×16 تقسیم شده است.

2 - برای هر پیکسل از هر بلوک، گرادیان با استفاده از عملگر سوبل که در جدول (1) نمایش داده شده، محاسبه شده است. روش کار براساس معادله‌های (1) تا (3) است.

 

(1)

    

(2)

    

(3)

    

عبارت f(x,y) مقدار پیکسل در مکان (x,y) است.

3 - برای هر پیکسل فاز و اندازه گرادیان با استفاده از معادله‌های (4) و (5) محاسبه می‌شود.

(4)

    

(5)

    

4- فاز به 16 زاویه از صفر تا  کوانتیزه شده سپس برای هر بلوک 16 ویژگی مطابق با 16 فاز با استفاده از معادله (6) استخراج شده است.

(6)

    

عبارت  ویژگی متحد با فاز  است. عبارت‌های  و  تمام مختصات‌هایی هستند که فازشان برابر  است. در نتیجه، برای 16 چرخش به تعداد 256=4×4×16 ویژگی با استفاده از عملگر سوبل به­دست آمده و نرمالیزه شده­اند. می‌توان تعداد چرخش‌ها را به تعداد کمتری مانند 4 یا 8 جهت نیز کوانتیزه کرد. تعداد ویژگی‌ها برای چرخش‌های مختلف مطابق جدول (2) است.

 

جدول (1):(الف) و (ب) عملگر‌های سوبل

1

2

1

 

1-

0

1

0

0

0

2-

0

2

1-

2-

1-

1-

0

1

   

         
   
   

ب

   
   
         
   
   

الف

   
   

 

 

جدول (2): تعداد ویژگی‌ها برای چرخش‌های مختلف

تعداد ویژگی‌ها

تعداد چرخش

256 =4×4×16

16

128 =4×4×8

8

64 =4×4×4

4

2-2- الگوریتم مکان مشخصه توسعه یافته

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

 

 

شکل (3): جزئیات روش مکان مشخصه توسعه یافته

 

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

(7)

    

در ادامه کار باید نمودار فراوانی اعداد به دست آمده از انتقال رشته اعداد به مبنای مشخص شده را به دست آورده و به عنوان بردار ویژگی استفاده کرد. همان گونه که بیان شد در این مقاله گذرهای افقی به مبنای 4 و گذرهای عمودی به مبنای 3 منتقل شده است. این بدین معنی است که در جهت‌های افقی باید تعداد گذرها به 3 و در جهت عمودی تعداد گذرها به مقدار 2 محدود گردد. بنابراین، بیشترین تعداد بردار ویژگی زمانی رخ می‌دهد که با شمارش تعداد گذرها، رشته (2323) تولید شود. در مرحله بعد، این رشته به دست آمده به مبنای ذکر شده در دو جهت عمودی و افقی بر اساس معادله (7) منتقل می‌شود. طبق جدول (3) کمترین و بیشترین مقدار طول بردار ویژگی از مجموع انتقال یافته اعداد به پایه‌های مربوطه از رشته (0000) تا (2323) برابر]0 تا 143[ است. حال طبق توضیحات داده شده باید رشته اعداد فوق به مبنای 3 و4 برده شود. جدول (3) این انتقال را نمایش داده است.

در نتیجه، طول بردار ویژگی که در این روش به دست می­آید، برابر 144 ویژگی است. نهایتاً طول بردار ویژگی اصلی از مجموع طول بردار ویژگی 2 روش فوق برابر 400 است.

جدول (3): انتقال رشته اعداد به مبنای 3 و4

تعداد ویژگی‌ها

رشته اعداد

(1×4×3) × 0+ (1×4×3×4) ×   0

0= (1) × 0+ (1×4) × 0+

0000

(1×4×3) × 3+ (1×4×3×4) ×   2

143= (1) × 3+ (1×4) × 2+

2323

 

3- بهینه سازی توده ذرات

PSO یک الگوریتم محاسبه­ای تکاملی مبتنی بر قوانین احتمال، الهام گرفته از طبیعت و بر اساس تکرار است که برای اولین بار توسط Kennedy و Eberhart در سال 1995 مطرح شد و یکی از الگوریتم­های بسیار پرکاربرد در زمینه بهینه­سازی استاتیک و دینامیک است[11]. دراین سیستم، عامل­ها به طور محلی با هم همکاری می‌نمایند و رفتار جمعیت باعث همگرایی در نقطه­ای نزدیک به جواب بهینه سراسری می‌شود. نقطه قوت این الگوریتم بی­نیازبودن از یک کنترل سراسری است. هرذره در این الگوریتم خودمختاری نسبی دارد که می­تواند در سراسر فضای جواب حرکت کند و ‌باید با سایر ذرات همکاری داشته باشد. تفاوت عمده­ای که این روش با الگوریتم‌های دیگر چون الگوریتم ژنتیک دارد، این است که اعضای جامعه از وضعیت سایر اعضا و یا بهترین عضو جامعه باخبر هستند و نتیجه به­دست آمده توسط آنها را در تصمیم گیری‌های خود لحاظ می‌کنند. همچنین، اعضا بهترین نتیجه خود، در طی اجرای الگوریتم را به یادداشته، همواره سعی می‌کنند تا آن را نیز در تصمیمات خود دخالت دهند. به همین علت، درصورتی که اشتباهی رخ دهد و تصمیم بدی بگیرند، به زودی آن را جبران می­کنند. به این ترتیب، اعضای جامعه می‌توانند به راحتی محدوده اطراف خود را جستجو کنند، بدون آنکه نگران خرابتر شدن نتیجه باشند. امروزه در بسیاری از زمینه‌ها این الگوریتم کاربرد دارد. انتخاب ویژگی یکی از این کاربردها بوده که در این مقاله به این منظور از آن استفاده شده است]12و13[.

 

3-1- الگوریتم PSO

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

پس از هر تکرار  الگوریتم PSO بردار سرعت جدید را به­صورت معادله (8) بروز رسانی می‌کند.

 

(8)

    

که در آن w ضریب اینرسی،  فاکتور بهترین جواب محلی و  فاکتور بهترین جواب عمومی است. ضرایب یادگیری  و  در بازه ]2،0[ و معمولا  اختیار می‌شود. و  اعداد تصادفی حاصل از توزیع یکنواخت در بازه ]0،1[ هستند. همگرایی الگوریتم شدیداً به ضریب اینرسی وابسته است و به صورت دینامیک در بازه] 0.8،0.2 [ انتخاب می‌شود که به صورت خطی در طی روند تکامل جمعیت کاهش می‌یابد و در ابتدا بزرگ است تا امکان یافتن جواب‌های خوب در همان مراحل اولیه فراهم شود و در مراحل پایانی کوچک بودن w همگرایی بهتری را سبب می‌شود. در این مقاله، این مقدار بر اساس تعداد تکرار با معادله (9) تعیین شده است که مقدار  برابر با 0.9 است.

(9)

    

سرعت ذره‌ها در هر بعد، برای جلوگیری از واگرایی الگوریتم محدود به ماکزیمم سرعت  است که چگونگی حرکت ذره­ها در فضای جستجو را مشخص می‌کند و اگر  خیلی کوچک باشد، ممکن است ذره‌ها بخوبی در فضاهای مناسب محلی کاوش نکنند و در بهینه محلی به­دام بیفتند. از سویی دیگر، اگر این مقدار بیش از حد زیاد باشد، ممکن است ذرات در فضاهای دور از جواب حرکت کنند معادله (10).

(10)

    

در نهایت، ذرات به سوی موقعیت جدید، بنا به رابطه مکانی معادله (11) حرکت می‌نمایند.

(11)

    

مدلی که طی رابطه 8 و 11 ارائه شد، مدل کلی نام دارد. برای این الگوریتم مدل دیگری به نام مدل محلی نیز ارائه شده است که در مدل محلی برای هر ذره یک همسایگی تعریف شده و بهترین موقعیت دیده شده در تمام همسایگان ذره محاسبه شده و با  نمایش داده می‌شود. در این شرایط به جای آنکه تمام ذرات در به روز رسانی از  استفاده کنند، هر ذره از  مربوط به خود استفاده می‌کند. آزمایش­ها نشان می‌دهد که مدل محلی در حل مسائل پیوسته به مراتب بهتر از مدل کلی است. در این مقاله، از مدل کلی این الگوریتم استفاده شده است. شرط خاتمه الگوریتم همگرایی و یا توقف بعد از تعداد معینی تکرار است.

 

3-2- الگوریتم دودوییPSO

برای حل مسائل گسسته روش دودویی این الگوریتم توسط کندی در سال 1997 ارائه شد و به دودویی PSO شهرت یافت[14]. استفاده از الگوریتم دودویی PSO همچنین زمان محاسبات را کاهش می‌دهد. تفاوت عمده این روش با الگوریتم اصلی در روابط بروز رسانی موقعیت و سرعت است که ابتدا باید مقدار بردار سرعت توسط تابع سیگموید به بازه ]0،1[ منتقل و سپس موقعیت جدید ذره محاسبه شود. در نسخه دودویی موقعیت هر ذره در هر بعد با دو مقدار صفر و یک مشخص می‌شود و وضعیت انتخاب ویژگی را نمایش می‌دهد. در الگوریتم نسخه دودویی، مفهوم سرعت به مفهوم احتمال، تغییر یافته و  احتمال یک بودن  را بیان می‌کند. هرذره بر اساس معادله‌های (12) و (13) به روزرسانی می‌شود که سرعت بر اساس معادله 9 به دست می‌آید.

(12)

    

(13)

    

در اینجا Rand یک عدد تصادفی در بازه ]0،1[ است. همان­گونه که در الگوریتم پیوسته مقدار  به یک مقداری محدود می‌شد، در این روش نیز مقدار سرعت محدود به یک مقدار بیشینه  است. شایان ذکر است که الگوریتم دودویی نیز همانند نوع پیوسته با استفاده از مدل‌های محلی و کلی قابل پیاده سازی است. همان گونه که قبلا بیان شد، ذرات در الگوریتم اجتماع ذرات پیوسته با دو کمیت X و V تعریف می‌شوند که X موقعیت ذره و V معرف سرعت برای هر ذره است و نشان دهنده میزان تغییر در موقعیت بعدی ذره، نسبت به موقعیت فعلی آن است. مقادیر بزرگ V نشان دهنده فاصله زیاد ذره تا رسیدن به مکان بهینه بوده، بنابراین جابه­جایی بیشتری برای ذره لازم است و بالعکس، مقادیر کوچک نشان دهنده نزدیک شدن مکان ذره به جواب مسأله به گونه­ای که اگر موقعیت ذره با موقعیت بهینه یکی شود، مقدار سرعت ذره برابر صفر می‌شود و این نشان دهنده آن است که دیگر جابه­جایی ذره لازم نیست.

در نسخه دودویی الگوریتم، تعاریف متفاوتی از X و V ارائه شده است. به­طوری که سرعت ذره به جای آنکه ذره را به سمت جواب­های بهینه مسائل هدایت کند، به صورت تابع احتمالات، یک یا صفر شدن X را مطرح می‌کند؛ یعنی مقدار  احتمال اینکه مقدار  یک یا صفر باشد را تعیین می‌کند. از آنجایی که مقدار احتمال باید در بازه صفر و یک باشد،  از تابع محدود کننده سیگموید می‌گذرد.

همان­طور که مشاهده می‌شود، در نسخه دودویی، بزرگ بودن مقدار  نشان دهنده تغییرات زیاد  نیست، بلکه متناسب با بزرگ بودن سرعت در جهت مقادیر مثبت احتمال یک بودن ، افزایش می‌یابد و به همین نحو متناسب با بزرگ بودن سرعت در جهت منفی احتمال صفر بودن  زیاد می‌شود. از سویی دیگر، اگر سرعت برابر صفر شود، مقدار  ثابت نمانده و با احتمال 50% صفر و با همین احتمال یک خواهد شد. با توجه به آنچه بحث شد می‌توان ایرادات زیر را به نسخه دودویی متداول وارد دانست]15و16[.

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

ب: ایراد دوم از رابطه به روزرسانی موقعیت ذره رابطه (12) است. در این رابطه موقعیت قبلی ذره برای محاسبه موقعیت بعدی آن در نظر گرفته نمی‌شود.

این دو ایراد باعث می‌شود الگوریتم همگرا نشده و ذرات از مکان بهینه دور شوند. برای رفع ایراد اول از تابع احتمال رابطه (14) و در ادامه سرعت با استفاده از رابطه (15) به روز می‌شود.

(14)

    

(15)

    

 

در رابطه (14) مقدار α یک ضریب ثابت است که تقریبا یک در نظر گرفته می‌شود.

هنگامی که الگوریتم اجتماع ذرات دچار همگرایی می‌شود، ذرات به سمت یک بهینه محلی حرکت کرده، در آن گرفتار می‌شوند. در این حالت از آنجایی که ذرات به ذره با موقعیت  نزدیک شده­اند، سرعت آنها به صفر نزدیک می‌شود. در چنین حالتی احتمال تغییر مکان ذره‌ها در الگوریتم دودویی روابط (14) و (15) کم شده، به سمت صفر میل می‌کند و در بهینه محلی گرفتار می‌شود. برای حل این مشکل و گریز از این مشکل، رابطه (14)به صورت رابطه 16 تغییر می‌کند.

(16)

    

در این رابطه ضریب A برای جلوگیری از رکود الگوریتم استفاده شده  و با استفاده از رابطه (17) به دست می‌آید]15[.

(17)

    

در این رابطه k، یک ضریب ثابت، T ثابت زمانی که با توجه به نوع و بعد مساله انتخاب می‌شود و F یک شمارنده است و دفعاتی را که الگوریتم دچار شکست می‌شود، می‌شمارد. شکست این­گونه تعریف می‌شود که الگوریتم نتواند موقعیت بهتری را به دست آورد یا به عبارتی دیگر ؛ بنابراین، با هر دفعه شکست به مقدار F یکی افزوده می‌شود. شایان ذکر است که F در لحظه شروع برابر صفر و پس از هر بار موفقیت، الگوریتم این شمارنده صفر خواهد شد. هنگامی که مقدار F برابر صفر باشد، مقدار A نیز صفر خواهد بود و بدان معنی است که الگوریتم در مسیر درستی قرار دارد و هیچ­گونه جهشی صورت نمی‌گیرد. الگوریتم بهبود یافته فوق در محیط گسسته را INBPSO می‌نامیم]15[.

تابع برازندگی مورد استفاده در این مقاله که توسط الگوریتم BPSO بهینه می‌شود، به دو مقدار تعداد ویژگی­های انتخاب شده و دقت بازشناسی وابسته است. برای این منظور، از طبقه­بند ماشین بردار پشتیبان SVM کتابخانه LIBSVM استفاده شده است. با ترکیب دو مقدار تعداد ویژگی و دقت بازشناسی تابع برازندگی با معادله (18) تعیین می­گردد.

(18)

    

که در آن  برابر تعداد ویژگی‌های انتخابی و  و  اعداد ثابت هستند.

 

3-3- انتخاب ویژگی

مسأله انتخاب ویژگی، یکی از مسائلی است که در مبحث یادگیری ماشین و در بررسی مسائل شناخت الگو از دیدگاه آمار مطرح است. با انتخاب ویژگی مناسب در نرخ بازشناسی و کنارگذاشتن ویژگی­هایی که در طبقه بندی تأثیر منفی دارند، می­توان هم نرخ بازشناسی را بهبود بخشید و همچنین، هزینه محاسباتی را کاهش و سرعت پردازش را افزایش داد که این امر در سیستم‌های بلادرنگ امر حیاتی است. عموماً از الگوریتم‌های متفاوتی می‌توان برای استخراج ویژگی استفاده نمود که در سال­های اخیر کارهای فراوانی روی آن صورت گرفته است، اما استفاده از کل این ویژگی‌ها که ممکن است ویژگی‌هایی نیز در آن باشد که اثر منفی در نرخ بازشناسی دارد، مقرون به صرفه نبوده و نیز طول بردار ویژگی بزرگ سرعت و کارایی سیستم بازشناسی را کاهش داده، ما را در یافتن پاسخ بهینه و سریع باز می‌دارد[17]. در این مقاله پس از استخراج ویژگی با استفاده از ترکیب الگوریتم‌های هیستوگرام گرادیان و مکان مشخصه توسعه یافته ویژگی­های مناسب با استفاده از الگوریتم دودویی PSO بهبود یافته انتخاب شده است. روندنما برای به دست آوردن الگوی انتخاب ویژگی به صورت شکل (4) است.

 

4- نتایج

در این مقاله از پایگاه داده ارقام دستنویس فارسی هدی استفاده شده است]9[. با استفاده از ترکیب الگوریتم‌های هیستوگرام گرادیان و مکان مشخصه توسعه یافته ویژگی­ها برای 60000 داده آموزش و 20000 داده آزمون استخراج شد و با کنار هم قرار دادن بردارهای ویژگی استخراجی از دو روش ذکر شده، بردار ویژگی اصلی با طول 400 به دست آمد. دقت بازشناسی برای 20000 داده آزمون با 16 چرخش در روش گرادیان با استفاده از طبقه­بندSVM  بدون کاهش ویژگی در تعداد نمونه‌های آموزش مختلف به صورت جدول (4) است. در بین داده‌ها بازشناسی ارقام 2 و3 نسبت به سایر ارقام بازشناسی پایینی دارند و ارقام 0 و1 و8 بیشترین بازشناسی را به خود اختصاص داده‌اند.

             

               
    
    

محاسبه مقدار برازندگی

    
    

          

               
    
    

محاسبه P_best

    
    

              

               
    
    

بررسی      شرط توقف

    
    

          

               
    
    

به روز رسانی سرعت

    
    

          

               
    
    

به      روز رسانی موقعیت

    
    

                      

               
    
    

بدست      آوردن الگوی انتخابی

    
    

              

               
    
    

محاسبه G_best

    
    

                

               
    
    

مقدار دهی اولیه به پارامتر‌های INBPSO  ایجاد سرعت و موقعیت اولیه

    
    

    

 

شکل (4): روندنما به دست آوردن الگوی انتخاب

 

درادامه در جدول (5) نتیجه به دست آمده با کارهایی که قبلاً بر روی این دیتابیس صورت گرفته، بررسی شده است. سپس تعداد ویژگی‌ها با استفاده از الگوریتم بهینه سازی توده ذرات دودویی بر اساس انتخاب ویژگی کاهش داده شده است؛ به­طوری­که دقت بازشناسی بالا نگه داشته شود. برای این کار در تابع برازندگی معادله (18) مقدار  بزرگتر از  انتخاب شده است.

پارامتر‌های انتخاب شده برای الگوریتم PSO دودویی بهبود یافته به صورت جدول (6) است.

مقدار  برابر با 0.9 در نظر گرفته شده که پس از هر تکرار با استفاده از معادله (9) بروز رسانی شده است. نتایج به دست آمده از ترکیب ویژگی‌های استخراج شده با استفاده از دو روش بالا و کاهش ویژگی در جدول (7) نشان داده شده است.

 

 

 

جدول (4): دقت بازشناسی برای20000 نمونه آزمون و تعداد نمونه‌های آموزش مختلف بدون کاهش ویژگی با استفاده از طبقه­بند SVM

60000

50000

40000

30000

20000

10000

5000

1000

تعداد   نمونه‌های آموزش

99.40%

99.33%

99.29%

99.22%

99.11%

98.84%

98.46%

96.66%

دقت   بازشناسی

 

جدول (5): مقایسه کارهای قبلی با روش پیشنهادی بر روی دیتابیس هدی

Recognition Rate %

Dataset Size

Algorithms

Test

Train

Test

Train

97.60

-

500

230

Harifi., Aghagolzadeh [18]

92

-

480

480

Hosseini, Bouzerdum [19]

91.88

99.29

1600

2240

Mowlaei et al. [20]

91.37

98.00

1600

2240

Mozaffari et al. [21]

94.44

100

1600

2240

Mozaffari et al. [22]

92.44

100

1600

2240

Mowlaei, Faez [23]

97.80

-

1300

2600

Shirali-Shahreza et al.[24]

99.57

-

3939

4979

Soltanzadeh, Rahmati [25]

97.01

-

4000

6000

Dehghan, Faez [26]

97.65

100

4000

6000

Ziaratban et al. [27]

94.14

-

3035

7390

Sadri et al. [28]

98.71

99.99

20000

60000

A. Alaei et al. [29]

99.02

99.99

20000

60000

A. Alaei et al. [30]

98.27

-

20000

60000

H. Parvin et al. [31]

98.89

-

20000

60000

Parvin et al. H [32]

99.15

-

20000

60000

نحوی،   کیانی، ابراهیم پور]33[

99.40

100

20000

60000

Proposed Algorithm

 

 

جدول (6): پارامتر‌های انتخاب شده برای الگوریتم INBPSO

30

تعداد   ذرات

2

ضریب      و     

4

ضریب     

6

ضریب     

15

تعداد   تکرار

1000

T

1

A

0.98

α

 

جدول (7): دقت بازشناسی برای20000 نمونه آزمون و تعداد نمونه‌های آموزش مختلف با کاهش ویژگی با استفاده از طبقه­بند SVM

60000

50000

40000

30000

20000

10000

5000

1000

تعداد نمونه‌های آموزش

64

58

59

56

53

54

54

49

تعداد ویژگی

99.28%

99.09%

98.96%

98.80%

98.53%

98.48%

98.23%

96.1%

دقت بازشناسی

 

 

 

 

با مقایسه جدول (4) و جدول (7) می‌توان دید که دقت‌های به دست آمده از روش بدون کاهش ویژگی و با کاهش ویژگی به وسیله الگوریتم بهینه سازی توده ذرات دودویی بهبود یافته، تفاوت چندانی در بازشناسی با هم ندارند و با کاهش ویژگی تا تعداد قابل قبولی هنوز دقت بازشناسی به مقدار قابل قبولی در حد بالا قرار دارد. جدول (8) مقدار بازشناسی را برای تعداد ویژگی‌های مختلف با استفاده از الگوریتم INBPSO نشان می‌دهد. در شکل (5) گراف مربوط به متوسط شایستگی بر اساس تعداد تکرار برای 1000 نمونه از داده‌های آموزش و 20000 نمونه آزمون رسم شده است. با توجه به شکل مشاهده می‌شود که متوسط شایستگی با افزایش تعداد تکرار الگوریتم رشد داشته، به مقدار خاصی همگرا می‌گردد.

 

 

جدول (8): دقت بازشناسی برای20000 نمونه آزمون و تعداد ویژگی‌های مختلف با استفاده از طبقه­بندSVM

400

334

270

210

151

105

64

تعداد   ویژگی

99.40%

99.37%

99.34%

99.31%

99.24%

99.19%

99.27%

دقت   بازشناسی

 

                                                                                                                                                                                                                                                                                         

                       
      
      

0

      
      

                           

                       
      
      

5

      
      

                           

                       
      
      

10

      
      

                           

                       
      
      

15

      
      

                           

                       
      
      

20

      
      

                           

                       
      
      

25

      
      

                           

                       
      
      

30

      
      

                           

                       
      
      

35

      
      

                           

                       
      
      

40

      
      

                           

                       
      
      

45

      
      

                           

                       
      
      

50

      
      

                           

                       
      
      

0.75

      
      

                           

                       
      
      

0.76

      
      

                           

                       
      
      

0.77

      
      

                           

                       
      
      

0.78

      
      

                           

                       
      
      

0.79

      
      

                           

                       
      
      

0.8

      
      

                           

                       
      
      

0.81

      
      

                           

                       
      
      

0.82

      
      

                           

                       
      
      

0.83

      
      

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        

                   
     
     

تکرار

     
     

     
شکل (5): همگرایی متوسط شایستگی، با افزایش تعداد تکرار در الگوریتم بهینه سازی توده ذرات دودویی بهبود یافته

 

 

 

5- نتیجه­گیری

در این مقاله ویژگی­های ارقام دستنویس فارسی با استفاده از ترکیب دو الگوریتم هیستوگرام گرادیان و مکان مشخصه توسعه یافته استخراج گردید و توسط طبقه­بند SVM بازشناسی با 400 ویژگی به دست آمده صورت گرفت و دقت 99.40% حاصل شد. توسط الگوریتم بهینه‌سازی توده ذرات دودویی و تعریف تابع برازندگی خاص، 64 ویژگی انتخاب و دقت بازشناسی 99.28% حاصل گردید. در تابع برازندگی ارائه شده دقت بازشناسی و تعداد ویژگی‌های مورد استفاده لحاظ شده است. بازشناسی در دو مرحله آموزش و آزمون صورت گرفت. در مرحله آموزش که برای 60000 نمونه صورت گرفت، پارامترهای طبقه­بند SVM تعیین، و در مرحله آزمون استفاده شد.

مقایسه نتایج با کار محققان دیگر حاکی از آن است روش ارائه شده در استخراج ویژگی و انتخاب ویژگی از کارایی مناسبی برخوردار است.

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

[1]     HS. Impedovo, P.S. Wang, and H. Bunke, editors, "Automatic Bankcheck Processing", World Scientific Publ. Co, Singapore, 1997.

[2]     I.D. Trier, A.K. Jain, "Feature Extraction Methods for Character Recognition- A Survey", Pattern Recognition, Vol. 29, No. 4, pp. 641-662, 1996.

[3]     H. Takahashi, "A Neural Net OCR Using Geometrical and Zonal Pattern Features", in proceedings of the first international Conference on Document Analysis and Recognition, pp. 821-828, 1991.

[4]     L.O. Jimenez, A. Morales-Morell, "Classification of Hyperdimensional Data Based on Feature and Decision Fusion Approachs Using Projection Pursuit, Majority Voting, and Neural Networks", IEEE Trans. on Geoscience and Remote Sensing, Vol. 37, No.3, pp.1360,1366, May 1999.

[5]     M.H ShirAli, A.R. Khotanzad, "Shift and Scale Invariant Digit Recognition Using Zernik Moments and Neural Networks", 2nd Iranian Conference on Electrical Engineering, Vol. 5, pp. 417-424, 1994

[6]     R. Azmi, E. Kabir, K. Badi, "Printed Character Recognition Using Features of Peripheral Curvature", Iranian Journal of Electrical and Computer Engineering, Vol 1, Issue 1, pp. 29-37, 2003.

[7]     Y. Li., "Reforming the Theory of Invariant Moments for Pattern Recognition", Pattern Recognition Letters, Vol. 25, Issue 7, pp. 723-730, July1992.

[8]     H.A. Glucksman, "Multicategory of Patterns Represented by High-Order Vectors of Multilevel Measurement", IEEE Transaction Computer, pp. 1593- 1598, Dec. 1971.

[9]     H. Khosravi, E. Kabir, "Introducing a Very Large Dataset of Handwritten Farsi Digits and a Study on their Varieties", Pattern Recognition Lett,Vol. 28, Issue 10, pp.1133-1141.

[10]     H. Khosravi, E. Kabir, "Introducing Two Fast and Efficient Features for Recognition of Persian Handwritten Digits", 4th Conference on Machine Vision and Image Processing, pp.25-26, 2006.

[11]     J. Kennedy and R. C.  Eberhart, "Particle Swarm Optimization", Proceedings of  IEEE International Conference on Neural Networks, Vol. 4, pp.1942-1948, 1995.

[12]     M. Rostami, H. Nezamabadipoor, "Feature Selection in Content Based Image Retrieval Using PSO Algorithm", 11th Iranian CSI Computer Conference, pp.269-275, 2005.

[13]     H. A. Firip, and E. Goodman, "Swarmed Feature Selection", in IEEE Proceedings of the 33rd Applied Imagery Pattern Recognition Workshop, pp. 112-118, 2004.

[14]     J. Kennedy and R. C.  Eberhart, "A Discrete Binary Version of the Particle Swarm Algorithm", IEEE International Conference on Computational Cybernetics and Simulation, Vol. 5, pp.4104-4108, 1997.

[15]     H. Nezamabadipoor, M. Rostami, M. Maghfoori, "Particle Swarm Optimization, Challenges and New Solutions", Iranian Journal of Electrical and Computer Engineering, Vol.6, No. 1, pp. 21-32, 2008.

[16]     M. Rostami, H. Nezamabadipoor, "Introducing New Algorithm for Binary PSO", 14th Iranian Conference on Electrical Engineering, 2006.

[17]     R. M. Ramadan and R. F. Abdel-Kader, "Face Recognition Using Particle Swarm Optimization-Based Selected Features", International Journal of Signal Processing, Image Processing and Pattern Recognition, Vol. 2, No.2, pp. 51-66, June 2009.

[18]     A. Harifi and A. Aghagolzadeh., "A New Pattern for Handwritten Persian/ Arabic Digit Recognition", Journal of Information Technology, Vol. 3, pp. 249-252, 2004.

[19]     H. Mir Mohammad Hosseini and A. Bouzerdoum, "A Combined Method for Persian and Arabic Handwritten Digit Recognition", Australian New Zealand Conference on Intelligent Information System pp. 80 – 83, 1996.

[20]     A. Mowlaei, K. Faez & A. Haghighat, "Feature Extraction with Wavelet Transform for Recognition of Isolated Handwritten Farsi/Arabic Characters and Numerals", 14th International Conference on Digital Signal Processing, Vol. 2, pp. 923-926, 2002.

[21]     S. Mozaffari, K. Faez & H. RashidyKanan, "Recognition of Isolated Handwritten Farsi/Arabic Alphanumeric Using Fractal Codes", Image Analysis and Interpretation, 6th Southwest Symposium, pp. 104-108, 2004.

[22]     S. Mozaffari, K. Faez and M. Ziaratban, "Structural Decomposition and Statistical Description of Farsi/Arabic Handwritten Numeric Characters", Proceedings of the 8th Intl. Conference on Document Analysis and Recognition, Vol. 1, pp. 237- 241, 2005.

[23]     A. Mowlaei and K. Faez, "Recognition Of Isolated Handwritten Persian Arabic Characters And Numerals Using Support Vector Machines", Proceedings of XIII Workshop on Neural Networks for Signal Processing, pp. 547-554, 2003.

[24]     M. H. Shirali-Shahreza, K. Faez and A. Khotanzad, "Recognition of Hand-written Persian/Arabic Numerals by Shadow Coding and an Edited Probabilistic Neural Network", Proceedings of International Conference on Image Processing, Vol. 3, pp. 436-439, 1995.

[25]     H. Soltanzadeh and M. Rahmati, "Recognition of Persian Handwritten Digits Using Image Profiles of Multiple Orientations", Pattern Recognition Letters 25, pp. 1569–1576, 2004.

[26]     M. Dehghan and K. Faez, "Farsi Handwritten Character Recognition With Moment Invariants", Proceedings of 13th International Conference on Digital Signal Processing, Vol 2, pp. 507-510, 1997.

[27]     M. Ziaratban, K. Faez and F. Faradji, "Language-Based Feature Extraction Using Template-Matching in Farsi/Arabic Handwritten Numeral Recognition", Proceedings of 9th International Conference on Document Analysis and Recognition, Vol.1, pp. 297-301, 2007.

[28]     J. Sadri, C. Y. Suen and T. D. Bui, "Application of Support Vector Machines for Recognition of Handwritten Arabic/Persian Digits", Proceedings of the 2nd Conference on Machine Vision and Image Processing & Applications, Vol. 1, pp. 300-307, 2003.

[29]     Alireza Alaei, Umapada Pal and P. Nagabhushan, "Using Modified Contour Features and SVM Based Classifier for the Recognition of Persian/Arabic Handwritten Numerals", Proceedings of 7th International Conference on Advances in Pattern Recognition, pp.391-394, 2009.

[30]     Alireza Alaei, P. Nagabhushan and Umapada Pal, "Fine Classification of Unconstrained Handwritten Persian/Arabic Numerals by Removing Confusion Amongst Similar Classes", Proceedings of 10 the International Conference on Document Analysis and Recognition, pp. 601-605, 2009.

[31]     H. Parvin, H.Alizadeh and B.Minaei-Bidgoli, "A New Approach to Improve the Vote-Based Classifier Selection", Proceedings of Fourth International Conference on Networked Computing and Advanced Information Management, pp. 91-95, 2008.

[32]     H. Parvin, H. Alizadeh, B. Minaei-Bidgoli and M.Analoui, "A Scalable Method for Improving the Performance of Classifiers in Multiclass Applications by Pairwise Classifiers and GA", Proceedings of Fourth International Conference on Networked Computing and Advanced Information Management, pp.137-142, 2008.

[33]     M. Nahvi, K. Kiani, R. Ebrahimpoor, "Improving Gradient Feature Extraction Based on Discrete Cosine Transform Towards Recognition of Persian Handwritten Digits", 18th Iranian Conference on Electrical Engineering, pp.3067-3071, 2010.