بخشی از مقاله
.1 هقذهه
یکی از مهمترین وظایف پردازش تصویر کمک به دیجیتال کردن متون چاپی موجود است. این کار نیاز به تشخیص کاراکتر با روشهای بینایی ماشین دارد. نقطه مشترک تمامی روشهایی که تا کنون به کار رفتهاند، استخراج ویژگیهایی از کاراکتر مورد نظر و سپس کلاسبندی به کمک این ویژگیهاست. تشخیص کاراکتر در زبانهای مختلف چالشهای متفاوتی دارد. بعضی چالشها از جمله نویز، چرخش، تغییر شکل و ... در همه زبانها وجود دارند و برخی دیگر از جمله نقطه، پیوستهنویسی، شکلهای مختلف از یک حرف و ... فقط در زبانهایی مانند فارسی وجود دارند.
در کنار روش های پردازش تصویر که برای این کار وجود دارند، هندسه محاسباتی نیز پای خود را به این زمینـه
1عضو هیأت علمی دانشکده علوم ریاضی و کامپیوتر، دانشگاه خوارزمی، تهران، ایران.
2 عضو هیأت علمی دانشکده فنی و مهندسی، دانشگاه خوارزمی، تهران، ایران.
3 دانشجوی کارشناسی ارشد دانشکده فنی و مهندسی، دانشگاه خوارزمی، تهران، ایران.
4 دانش آموخته کارشناسی ارشد دانشکده فنی و مهندسی، دانشگاه خوارزمی، تهران، ایران. * نویسنده مسؤل
باز کرده است. یکی از این روش ها استخراج گراف از تصویر کاراکتر و سپس مقایسه ریختشناسانه گرافهـا بـا هـم بـه منظور دسته بندی و تشخیص کاراکترهاست. روش های یادگیری رقابتی و نقشه های خودسازمان ده انواعی از شبکه هـای عصبی هستند که با تکرارهای زیاد، در نهایت شبکه ای از گرهها و یالها را نتیجه میدهند. این شبکه همان گرافی است که ریخت تصویر مورد نظر (که در اینجا تصویر یک کـاراکتر اسـت.) را در خـود حفـظ کـرده اسـت. هـدف ایـن مقالـه بکارگیری روش GNG برای تشخیص کاراکترهای فارسی تایپ شده است.
.2 نتایج اصلی: الگوریتن گاز عصبی رشذ یابنذه (GNG)
این الگوریتم برای اولین بار در سال 1995 توسط Bernd Fritzke ارائه شد. الگوریتم GNG یکی از انواع SOM [1] است که ریخت را استخراج میکند یا دادهها را کلاسبندی میکند. این الگوریتم برای بهبود روشی که از ترکیب گاز عصبی (Neural Gas) و یادگیری هب رقابتی (CHL) استفاده میکرد به وجود آمد و آن روش را بهبود داد و منعطفتر کرد .[2]
در این قسمت، مراحل مختلف الگوریتم GNG بر روی تصویر کاراکتر را شرح میدهیم:
1. الگوریتم با دو گره اولیه s1 و s2 آغاز میشود. این گرهها به صورت تصادفی انتخاب میشوند و در ابتدا الزامی وجود ندارد که در داخل فضای دادههای مورد نظر (در اینجا دادههای مورد نظر پیکسلهای کاراکتر هستند) قرار داشته باشند. برای هر گره متغیری به نام خطا((Error برابر با صفر مقداردهی اولیه میشود.
مجموعه یالها نیز شامل یال بین این دو گره است و سن این یال برابر با صفر مقداردهی میشود. این دو گره و یال مورد اشاره، شبکهای را شکل میدهند که باید در پایان به داده مورد نظر همگرا شود.
2. یکی از پیکسلهای داده مورد نظر، به صورت تصادفی، به عنوان ورودی((Input به شبکه داده میشود.
3. بر اساس مختصات پیکسل ورودی جدید، یک گره از شبکه گاز عصبی به عنوان گره برنده انتخاب میشود. این گره که با اندیس s1 نامگذاری میشود نزدیکترین گره به پیکسل ورودی است. اندیسگذاری گره برنده به این دلیل است که به همین ترتیب، بر اساس کاربردهای الگوریتم، میتوان تعداد گرههای برنده را بیش از یک هم در نظر گرفت. در اینجا از فاصله اقلیدسی به عنوان معیاری از نزدیکی استفاده شده است:
(1)
که در آن مختصات پیکسل ورودی و مختصات گره ام از شبکه گاز عصبی هستند.
4. سن همه یالهای متصل به s1 افزایش مییابد.
5. خطای گره s1 به اندازه مربع فاصله بین پیکسل ورودی و s1 افزایش مییابد.
(2)
.6 گره s1 با ضریبی به نام شدت یادگیری، به سمت پیکسل ورودی میل میکند.
(3)
در اینجا و شماره تکرار الگوریتم را نشان میدهند. شدت یادگیری که در اینجا با و به صورت متغیری
وابسته به تعداد تکرار نشان داده شده، میتواند ثابت باشد یا با توجه به تعداد تکرارها کاهش یابد. .7 همه همسایههای مستقیم s1 نیز به سمت پیکسل ورودی میل میکنند.
(4)
رابطه شماره (4) برای همه همسایههای مستقیم اجرا میشود.
8. یک یال با سن صفر بین s1 و s2 (دومین گره نزدیک به پیکسل ورودی) اضافه میشود. اگر این دو گره از قبل متصل باشند سن یال بین آن دو صفر میشود.
9. یالهایی که سن آنها بیشتر از حداکثر سن مجاز (Max Age) باشد، حذف میشوند. این حداکثر سن مجاز بر اساس کاربرد تعیین میشود.
1. اگر گرههایی تنها باقی مانده باشند که یال ندارند (Isolate Nodes)، آن گرهها نیز حذف میشوند.
11. بعد از هر تعداد مشخصی از اجرای مراحل 1 تا 9، یک گره به شبکه اضافه میشود. تعداد گرههای شبکه نیز محدودیت دارد .(Max Nodes) اضافه کردن گره به این صورت انجام میشود:
.1-11 گره با بیشترین مقدار خطا درشبکه را تعیین میکنیم و نام آن را q میگذاریم.
.2-11 اگر مقدار خطای q از حداکثر خطا (Max Error) که در ابتدای الگوریتم تعیین میشود، بیشتر باشد، گره جدید r را بین q و دورترین همسایه مستقیم آن یعنی f اضافه میکنیم:
(1)
.3-11 مقادیر حداکثر تعداد گره و حداکثر خطا، بر ایجاد گرهها و یالهای مستقل و همچنین دور در گراف تاثیر میگذارند و انتخاب آنها با توجه به کاربرد مورد نظر، در به جواب رسیدن الگوریتم تاثیرگذار است.
.12 بعد از هر تعداد مشخصی از پیکسلهای ورودی، مقدار خطای همه گرهها به صفر تغییر میکند.
.13 اگر هیچکدام از شرطهای پایان الگوریتم برقرار نبود به شماره 2 برمیگردد. شرطهای پایان الگوریتم میتوانند عبارت باشند از: اجرای الگوریتم با تعداد تکرار مشخص، رسیدن به خطای قابل قبول، همگرا نشدن برنامه با توجه به روند تغییر خطا .[3]
.3 نتایج اجرا و شبیه سازی الگوریتن
با توجه به اینکه خروجی الگوریتم گاز عصبی رشد یابنده، مجموعهای از نقاط شبکه هستند که ساختار اصلی تصویر ورودی را به ما میدهد، میتوان گفت که خروجی الگوریتم GNG، از نوع ویژگی (feature) است.
در ادامه، در شکل 1، به عنوان نمونه، خروجی الگوریتم بر روی حروف فارسی »ک« و »د« آمده است:
شکل :1 خروجی حاصل از الگوریتم GNG روی حروف »د« و »ک«
مراحل مختلف اجرای الگوریتم روی حرف »ج« در شکل 2 و گراف خروجی حاصل از اجرای GNG در شکل 3 به تصویر آمده است:
