تشخيص ارقام دستنويس فارسي به روش جديد فازي بهينه شده با الگوريتمهاي تکاملي
چکيده: تشخيص ارقام دست نويس فارسي در تصاوير با روشهاي مختلفي صورت گرفته است كه عمدتاً داراي درصدي خطا در پياده سازي مي باشند. مراحل بکار رفته در اين پروژه عبارتند از: عمل پيش پردازش شامل نازک سازي و دوران تصوير و تبديل آن به اندازهاي معين ميباشد، براي استخراج ويژگيها از تصاوير مجموعه آموزش از روش جعبه با پارامترهاي فاصله، زاويه و جهت تشخيص ارقام از يک سيستم فازي استفاده شده است. درصدي خطا جز لاينفک سيستم هاي فازي مي باشد که بوسيله ترکيب الگوريتم هاي تکاملي ژنتيک و تبريد تدريجي کارايي سيستم مورد نظر به طور قابل توجهي افزايش يافته است. براي مقايسه کارايي نهايي سيستم، کاهش خطاي سيستم فازي و مقادير برازندگي بدست آمده طي نسلهاي تركيب اين دو الگوريتم تکاملي مورد بررسي قرار گرفته است.
واژه هاي كليدي: تشخيص ارقام دست نويس فارسي, سيستم فازي, الگوريتم ژنتيک، الگوريتم تبريد تدريجي .
1- مقدمه
تشخيص كاراكترهاي دست نويس در تصاوير با استفاده از روشهاي مختلفي انجام شده است كه هر يك داراي درصد قابل توجهي خطا مي باشند. در اکثر روشهاي دستهبندي، کل پيکسلهاي تصوير مورد مقايسه قرار گرفته که اين خود محدوديتي براي مسئله بوجود ميآورد. خطاي سيستمهاي فازي براي تشخيص بيشتر به استفاده از ويژگيهاي نامناسب تصوير حاصل ميگردد[2][3].
در اين پروژه ابتدا با روشي تحت عنوان "روش جعبه" عمل نازكسازي و استاندارسازي تصوير انجام شده و استخراج ويژگيهاي تصاوير با استفاده از پارامتر فاصله، مجموعه دادههاي آموزش و تست براي سيستم فازي تعيين مي گردند[1]. براي حذف ويژگيهاي اضافي و ويژگيهاي خالي از مقدار مي توان الگوريتمهاي تکاملي را بکار برد. الگوريتم ژنتيك به عنوان يکي از پرکاربردترين روش تکاملي استفاده شده است، اما از آنجائيکه الگوريتمهاي ژنتيك طي نسلها امكان دارد در جواب بهينه محلي گرفتار شود و همچنين بدليل سرعت همگرايي کم از الگوريتم تبريد تدريجي[6] براي رهايي از اين مشكل استفاده مي گردد كه در تركيب با يكديگر كارايي نسبتا خوبي را بهمراه داشته است.
استفاده از ويژگيهاي خوب هر يک از اين دو الگوريتم و ترکيب آنها موجب باقيماندن اين مزايا بعد از ترکيب خواهد شد. از آنجاييکه عملگر جهش در الگوريتم ژنتيک موجب تنوع در جمعيت ميشود و مايليم با پيشروي نسلها تنوع کمتر شده تااينکه مسئله به جواب همگرا شود، ازطرفي کاهش پارامتر دما در الگوريتم تبريد تدريجي به سمت جواب سوق مييابد، بنابراين ميتوان تناسبي بين دو پارامتر نرخ عملگر جهش و دما در نظر گرفت و به اين ترتيب ترکيب از آنها حاصل ميگردد.
اين پروژه به تشخيص ارقام دست نويس فاررسي به کمک سيستم فازي و کاهش خطاي سيستم بر اساس الگوريتمهاي ژنتيك و تبريد تدريجي پرداخته شده است. براي افزايش كارايي مرحله پيش پردازش از پارامتر زاويه نيز استفاده مي گردد كه موجب دقيقتر شدن مقدار ويژگيها مي شود.
2- پيش پردازش
ورودي اين سيستم ارقام فارسي ميباشند بطوريکه تصوير صفحه‌اي كه در آن حروف به طور جداگانه (هر حرف داخل يك كادر) نوشته شده است، به وسيلة اسكن وارد سيستم ميشود. مرحلة بعدي اين است كه حروف بازشناسي شوند، يعني مكان آنها از ديگر خطوط (مثل خطوط كادري كه داخل آن نوشته شده) بازشناسي شود، و اگر متن پيوسته تايپي است، حروف جدا شوند و زوايد تصوير حذف شود. مثلاً اگر شخصي "7" را به گونه‌اي نوشت كه بيرون از كادر بود، به رايانه بفهمانيم كه بي‌دقتي شده است او بايد همان حرف داخل كادر را بخواند. در مرحلة بازشناسي الگو، با تعدادي شرط ميتوان فهميد كه مثلاً رقمي "7" است يا نه، و رايانه تشخيص مي‌دهد كه حرف "7" است يا "6". براي اين تشخيص لازم است كه تصوير رقم "7"با "7" هاي نمونه كه قبلاً به سيستم داده شده است منطبق شود. ارقام نمونه قبلاً از روي يك مجموعه بزرگ آموزشي تهيه شده و ويژگيهاي مشترك از آن استخراج شده است. اما از آنجا كه تنوع صورت‌ها نوشتاري يك حرف به صورت دستنويس بسيار زياد است، مدلي آماري استخراج ميشود كه در آن شباهت ويژگيهاي استخراج شدة قبلي با نمونه ورودي به رايانه بررسي ميشود. در اينجا «بازشناسي الگو» با روشهاي آماري انجام ميشود كه روش معمول در سيستمهاي تشخيص کاراکتر ميباشد.
حذف سطر و ستونهاي اضافي از لبههاي تصوير به سمت مرکز براي افزايش کارايي به طوريکه سطر و ستونهايي حاوي پيكسلهايي با مقدار صفر حذف ميشوند .
براي همه كاراكترهاي فارسي يك اندازه معيني براي سطرها و ستونها در نظر گرفته ميشود. براي نمونه مجموعه داده هايي از تصاوير ارقام فارسي با اندازه استاندارد 32*42 در نظر گرفته شده است [1].
2-1 تصحيح منحنيها و کجيها
حروف دستنويس بسته به شيوه نگارش افراد در يک جهت خميده ميشوند. براي رفع اين مشکل هر حرف را به دو قسمت بالايي و پاييني تقسيم نموده و سپس مرکز تجمع پيکسلها را در هر دو نيمه محاسبه شده و اين دو مرکز توسط يک خط به هم متصل ميشوند. شيب خط متصلکننده دو مرکز در يک پنجره شيب حرف را مشخص ميکند. با استفاده از تبديل (1) ميتوان اصلاح را انجام داد [8]].
(1) X=
) , Y=y
) , Y=yدر اين تبديل def ميزان انحناي نرمال دادههاست.x و y مختصات نقاط قبل از تصحيح و از بين بردن شيب کاراکتر ميباشند و X , Y مختصات همان نقاط تصوير بعد از تصحيح هستند. s نيز شيب خط متصل کننده دو مرکز تجمع پيکسلها در نيمه بالاي و پاييني تصوير است.
در شکل1 قسمت (الف) و (ب) به ترتيب تصوير نوشته‌شده توسط کاربر و تصوير اصلاح شده آورده شده است.
شکل 1 - تصحيح منحني و کجيها
بعد از تبديل تصوير به يک تصوير دودويي صفرهاي زيادي (نقاط سفيد که مربوط به زمينه ميباشند و حاوي هيچ اطلاعاتي نيستند) در چهار طرف وجود دارد. براي شروع بايد چهار وجهي که اطلاعاتِ زيادي دارند حذف شوند و حرف، محصور به يک چهار وجهي شود.
2-2 استخراج ويژگي ها از مجموعه آموزش
روشي كه براي استخراج ويژگيها از مجموعه آموزش معرفي ميشود به شرح زير مي باشد.:
استفاده از يك جعبه 4*6 بر روي كل تصوير و بدست آوردن تابعي براي محاسبه مقدار ويژگي در هر يك از 24 جعبه كه در شکل نشان داده شده است.
شکل 2- جعبه ارقام با اندازه 6*4
ويژگي اول: بردار فاصله هر جعبه تا مبدا (0و0) گوشه سمت چپ و پايين استفاده نمود . فاصله پيكسل k از جعبه b :
(2) 
همچنين بردار فاصله نرمال به استفاده از رابطه زير محاسبه مي شود:
(3) 
که در آنN برابر تعداد كل پيكسلهاي جعبه مي باشد N=(42*32)/24 .
رابطه bα براي هر 24 جعبه اي كه تصوير يك كاراكتر مي باشد محاسبه مي شود. در اين صورت مجموعه 24 ويژگي براي هر كاراكتر بدست مي آيد .
لازم به ذكر مي باشد جعبه خالي داراي ويژگي با مقدار صفر مي باشد .
ويژگي دوم:
زاويه هر جعبه نسبت به افق به عنوان ويژگي دوم مورد استفاده قرار مي گير.، به طوريکه با استفاده از فاصله عمودي و افقي هر پيکسل نسبت به مبدا و محاسبه تابع ArcTan زاويه تعيين شده و ميانگين زواياي بدست آمده در هر يک از 24 جعبه به عنوان يکي از ويژگيها تعيين مي گردد.
با استفاده از ويژگيهاي تشريح شده مجموعا 48 ويژگي براي هر تصوير ورودي استخراج مي شود .
مرحله بعدي ميانگين ويژگيهاي بدست آمده براي هر نمونه از ارقام كه مقدار ويژگي آن جعبه را مشخص مي نمايد.
3- طراحي سيستم فازي
3-1 تابع عضويت
تابع عضويت به صورت گوسين با دو پارامتر مقدار ميانگين و واريانسي بر اساس مقدار ويژگي هاي بدست آمده از مجموعه آموزش مي باشد که به روش زير محاسبه مي شود :
(4)  = | |
 |  |
: iامين ويژگي يك از 24 كاراكتر مي باشد .Ni : تعداد نمونه ها در مجموعه i ام .
: مقدار ويژگيj ام رقم از مجموعه فازي i ام .3-2 قوانين فازي
تعداد قوانين فازي مساوي تعداد كاراكترهاي فارسي يعني 32 مي باشد.
قانون 1: اگرx1 برابر B11 و x2 برابر B12و . . . x48 برابر B148 آنگاه رقم صفر .
قانون 2: اگر x1 برابر B21 و x2 برابر B22 و . . .و x48 برابر B248 آنگاه رقم يک .
. . .
قانون 10: اگر x1 برابر B101 و x2 برابر B102 و . . .و x48 برابر B1048 آنگاه رقم نه .
در واقع براي هر رقم از صفر تا نه يك قانون بوجود آورده و تصوير ورودي با همه 10 رقم فارسي مقايسه مي شود و فقط يك قانون برنده شده و كاراكتر مورد نظر را تعيين مي كند .
موتور استنتاج حاصلضرب ممداني به صورتيكه حاصلضرب توابع عضويت را محاسبه مي كند وغير فازي ساز ميانگين مراكز .
3-3 محاسبه خطا
يك روش براي محاسبه خطا محاسبه اختلاف مقدار خروجي مرحله آموزش و مرحله تست مي باشد.
روش دوم استفاده از ميانگين مقدار تابع عضويت به صورت زير:
(5) 
بهينهسازي سيستم فازي براي تشخيص ارقام دست نويس فارسي را مي توان از چند وجه بررسي نمود :
کم نمودن تعداد جعبههاي خالي از مقدار براي افزايش سرعت همگرايي، که در اينجا الگوريتمي تکاملي جديد معرفي مي شود که از ترکيب الگوريتم ژنتيک و تبريد تدريجي نتيجه شده است.
4- الگوريتمي تكاملي ترکيبي براي بهينه سازي
ترکيب الگوريتمهاي ژنتيک و تبريد تدريجي با يکديگر بدليل باقي ماندن ويژگيهاي خوب آنها عملي منطقي به نظر مي رسد. راهي که براي ترکيب اين دو استفاده شده است، در نظر گرفتن تناسب نرخ عملگر جهش در الگوريتم ژنتيک و همچنين پارامتر خنک کنندگي دما در الگوريتم تبريد تدريجي مي باشد. جزئيات مربوط به ترکيب اين دو الگوريتم به شرح زير مي باشد:
جمعيت و دما مقداردهي اوليه مي شوند و به تعداد نسلها گامهاي بعدي تکرار مي شوند. زوجي از والدين اتنخاب مي شوند و عملگرهاي جهش و برش روي آنها اعمال مي شود. دو فرزند براي جايگزيني توليد مي شوند که با شرط زير هر يک از فرزندان مي توانند جايگزين والدي با بدترين مقدار برازندگي شوند. بدين ترتيب شرط جايگزيني فرزند با بدتيرن والد fworst با رابطه زير توصيف ميشود:
(6) 
در پايان هر نسل دما با ضريب α کم شده و همچنين نرخ عملگر جهش نيز در هر ده نسل با ضريب α کم مي شود .
فرضيات الگوريتمها
فرضيات مربوط به الگوريتمهاي ژنتيك و تبريد تدريجي به ترتيب عبارتند از:
نحوه کدگذاري به ترتيبي ميباشد که کروموزومي به طول 48 با ژنهاي صفر که نشان دهنده در نظر گرفتن خانهاي از جعبه و همچنين يک ميباشد.
بعد از انتخاب دو كروموزوم با استفاده از عملگر تقاطع تک نقطهاي نيمههاي دو کروموزوم منتخب با هم تعويض ميشوند.
شکل 3- چگونگي عملگر تاطع
عملگر جهش با احتمالي ژنهايي از کروموزومهاي جمعيت را دچار تغيير نموده كه موجب تنوع در جمعيت خواهد شد.
شکل 4- چگونگي عملگر جهش
تعداد جمعيت = 50 ، طول كروموزوم= 501 ، تعداد نسلها=100 ، نرخ عملگر تقاطع = 85/0 ، نرخ عملگر جهش =3/0 .
براي افزايش تنوع در جمعيت ابتدا نرخ عملگر جهش 0.40Pm= در نظر گرفته شده است همچنين براي افزايش سرعت همگرايي در نسلهاي انتهايي اين نرخ بايد كم شود كه بوسيله زمانبندي دما در الگوريتم تبريد تدريجي تعيين مي شود. براي كاهش دما و نرخ عملگر جهش پارامتري با عنوان α برابر 0.85 به عنوان ضريب كاهشي مي باشد.
الگوريتم ترکيب به صورت زير مي باشد:
1: t = 0
2: initialize P(t) and temperature Tt
3: evaluate P(t)
4: while not termination-condition do
5: t = t + 1
6: select P(t) from P(t-1)
7: select individuals for reproduction from P(t)
8: repeat
9: select two unused individuals P1, P2
10: crossover & mutation; generate two children C1,C2
11: evaluate C1,C2
12: for all i = 1 to 2 do
13: if min{1, exp((fi-fworst)/Tt)}> random[0,1) then
14: accept Ci and replace the corresponding parent
15: update the new best and worst points
16: end if
17: end for
18: until all selected parents finish reproduction
19: Tt+1 = Tt × α; 0 <α < 1
20: if the modulus of t divided by 10 == 0&& pm > 1/n then
21: pm = pm×α
22: end if
23: end while
براي افزايش کارايي تشخيص سيستم فازي لازم مي باشد تنها ويژگي هاي بهينه مورد استفاده قرار گيرد، بنابراين الگوريتمهاي تکاملي به انتخاب اين ويژگي ها طي نسلها مي پردازد.
5- نتايج
كارايي سيستم مذكور با استفاده از نرخ خطاي كاهشي سيستم با اعمال الگوريتمهاي تكاملي بررسي ميشود.
دليل افزايش كارايي الگوريتم تركيبي عبارتند از:
- استفاده از زمانبندي پارامتر دما و تناسب دادن آن با نرخ عملگر جهش
- حفظ تنوع در جمعيت طي پيشروي نسلها
- استفاده از الگوريتم تبريد تدريجي با تابع پذيرش بر اساس مقادير برازندگي والدين و فرزندان
- رهايي الگوريتم ژنتيك از جواب بهينه محلي به وسيله الگوريتم تبريد تدريجي
- بهينهشدن سيستم تشخيص فازي با حذف ويژگيهاي نامناسب بوسيله الگوريتمهاي ژنتيك و تبريد تدريجي
نمودارهاي بدست آمده نشان دهنده كارايي سيستم تشخيص مي باشد:
شکل 5- نرخ كاهشي خطا در بهينه سازي سيستم فازي به كمك الگوريتمهاي ژنتيك
با تركيب الگوريتمهاي ژنتيك و تبريد تدريجي خطايي كاهشي طي نسلها برآورده شده است.
شکل 6- نرخ كاهشي خطا در بهينه سازي سيستم فازي با تركيب الگوريتمهاي ژنتيك و تبريد تدريجي
استفاده از روش جعبه و فازي به دقتي معادل 89% دست يافته، اين درحالي ميباشد که روش ترکيبي ارائه شده به دقتي معادل 95% رسيده است، همچنين اين نتيجه در مقايسه با روشهايي ديگر مانند شبکه عصبي [4] نيز داراي دقت بيشتر ميباشد.
نتايج نشان دهنده افزايش كارايي و بهينگي سيستم تشخيص با تركيب الگوريتمهاي تبريد تدريجي و ژنتيك شده است.
مراجع
[3] S.Chuai-areee,C.Lursinsap,P.Sophatsathit,S.Siripant, "Fuzzy C-Mean:A Statistical Feature Classification of Text and Image Segmentation Method",Advanced Virtual and Intelligence Computing Center, Department of Mathematics and Computer Science, Chulalongkorn Unversity, Bangkok,10330,Tailand.
پستها
هیچ نظری موجود نیست:
ارسال یک نظر