مباحثی پیرامون OCR و بررسی برخی از روشها

[mzjahromi]

خلاصه ای از پرژه پایانی دوره کارشناسی
تهیه کننده: محمد ذوالقدر

آذر ماه 1380

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

[mzjahromi]

در قرون اخیر شبیه سازی ماشینی خواندن کلمات بسیار جالب تر از قبل شده است. افزایش چشمگیر منابع و مقالات موجود در این زمینه بیانگر همین مطلب می باشد .
این جذابیت و فعالیت ،تنها بخاطر مبارزه با مشکلات موجود نمی باشد.، بلکه به دنبال این کار، پردازش اتوماتیک حجم بالای اطلاعات، مانند خواندن اطلاعات پستی، اتوماسیون اداری و سایر کارها و برنامه های علمی نیز به راحتی انجام خواهد شد.
وجود مشکلاتی از قبیل نویز، مسائل ویژه متون دست نویس و وابسته به نویسنده و … پیچیدگی مسئله را به شدت افزایش می دهد. جهت تحلیل اینگونه مسائل نیاز به انجام عملیاتی از قبیل جداسازی کاراکترها از کلمات و شناسائی ویژگیهای اساسی کاراکترها خواهیم داشت. هر یک از روشهای مختلف تحت عنوان کلی شناسائی کاراکترها ائم از روشهای برون خطی(Off-Line ) یا روشهای بلادرنگ(On-Line) با توجه به سخت افزار و الگوریتم خاصی کار می کنند. در شناسائی حروف و کاراکترها به صورت بلادرنگ عملیات شناسائی زمانی انجام می شود که کاربر درحال رسم حروف و یا کاراکترها می باشد جهت انجام این کار نیاز به یک صفحه الکترونیکی با دقت 200 نقطه در اینچ و سرعت نمونه برداری 100 نقطه در ثانیه، داریم همچنین این صفحه باید قادر به ارسال اطلاعات به صورت یک بعدی نیز باشد .
در بازشناسی برون خطی، عملیات پس از چاپ یا نوشتن کامل متون انجام خواهد شد.
OCR یکی از روشهای شناسائی کاراکترها در مقابل شناسائی مغناطیسی می باشد. درOCR اطلاعات ورودی توسط یک پویشگر خوانده می شود و سپس موقعیت هر کاراکتر شناسائی می شود. به دنبال آن کاراکترها از یکدیگر جدا می شوند و نتیجه به صورت یک ماتریس به پیش پردازنده ارسال می شود و عملیات نازکسازی، کاهش نویز و نرمال سازی اندازه ای روی آن انجام می شود و در نهایت ماشین مربوط به شناسائی کاراکترها آنها را شناسائی می کند .
در سه قرن گذشته روشهای بسیار زیادی توسط دانشمندان مختلف جهت شناسائی کاراکترها ارائه شده است دیدگاهها و روشهائی که تاکنون ارائه شده اند به چند دسته مختلف تقسیم می شوند. که عبارتند از : روشهای آماری، روشهای ساختاری و شبکه های عصبی. روشی که در این مبحث ارائه شده است از دسته دوم می باشد .
حال با مروری بر مراحل بازشناسی حروف بحث را ادامه می دهیم .

[mzjahromi]

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


1-1-1) پیش پردازش
در این مرحله قسمتهای مناسبی از تصویر جهت شناسائی و جداسازی قطعات علامتگذاری می شوند بطور کلی عملیاتی که در پیش پردازش انجام می شوند به شرح زیر است، اما با توجه به روش انتخاب شده ممکن است یک یا چند مرحله از مراحل زیر اصلا انجام نشود یا اینکه به شکلی متفاوت صورت پذیرد.
از دیگر عملیاتی که در پیش پردازش انجام می شود تشخیص موقعیت کاراکترها می باشد این کار نیز می تواند توسط نمودارهای چگالی افقی و عمودی انجام شود .

1-1-2)جداسازی
متون دست نویس شامل جمله ها،کلمات وکاراکترهاهستندو فرض می شود که جمله ها با نقطه ختم می شوند و بین کلمات نیز فواصل کوتاهی وجود دارد بدین ترتیب قطعات مختلف متنی که ممکن است در یک تصویر موجود باشد شناسائی می شوند. سپس احتمال اینکه جمله بدست آمده صحیح باشد بررسی می شود. اعمال فوق با روشهای مختلف جداسازی انجام می شود و در هر مورد احتمال صحت جمله بررسی می شود و جمله ای که احتمال صحیح بودن آن بیش از سایرین باشد معرفی می شود پس از آن ماشین تشخیص کلمه کار خود را شروع می کند. در صورتیکه این ماشین، عملیات تشخیص را به صورت کاراکتری انجام می دهد، باید عملیات جداسازی در سطح کاراکترها را هم انجام دهد .


1-1-3) شناسائی
این قسمت سعی در شناسائی کاراکترها و کلمات دارد. توجه شود که غالب نرم افزارهای نوشته شده در زمینه تشخیص کلمات تنها قادر به شناسائی تعداد محدودی از کلمات می باشند. آنچه در مباحث زیرین مشاهده می شود روشهائی جهت شناسائی کاراکترها و کلمات می باشند یک سیستم تشخیص کلمه تنها می تواند از استراتژیهای تحلیلی،holistic و مبتنی بر تشخیص استفاده کند روش چهارم تنها مربوط به شناسائی کاراکترها می باشد.


1-1-3-1)روشهای تحلیلی
روشهای تحلیلی کلمات را قبل از شناسائی به واحدهای کوچکتری تقسیم می کنند با توجه به روش استفاده شده، این واحدها می توانند قطعه ها کاراکترها شبه کاراکترها و… باشند. این واحدها به شدت وابسته به کاراکترها هستند بنابراین شناسائی آنها وابسته به یک مجموعه خاص از کلمات نمی باشد (محدودیت در تعداد کلمات وجود ندارد)روشهای تحلیلی عملیات جداسازی را بطور کامل و دقیق انجام می دهند چون در این روشها کلمات صریحاً به کاراکترهائی شکسته خواهند شد که به طور جداگانه شناسائی می شوند. البته در چنین مواردی نیاز به یک پردازش نهائی جهت اطمینان از صحت اطلاعات نیز وجود دارد.


1-1-3-2)روشهای holistic
روشهای holistic کلمات را بصورت یکجا و بدون هیچگونه جداسازی شناسائی می کنند و این عملیات را طی دو مرحله انجام می دهند.
1)استخراج ویژگیها
2)مقایسه شکل کلمه ناشناخته با کلمات موجود در مجموعه لغات خود


1-1-3-3)روشهای مبتنی بر تشخیص
در روشهای مبتنی بر تشخیص یک سری جداسازیهای داخلی انجام می شود و هر گروه از کاراکترهای جداسازی شده با یک ماشین جداگانه بررسی می شوند و تنها گروهی ارائه می شود که دارای معنی قابل قبولی باشد. سپس تصویر جداسازی شده به ماشین تشخیص الگو ارسال می شوند و پس از انتخاب بهترین جداسازی نتیجه نهائی استفاده خواهد شد.


1-1-3-4)بازشناسی کاراکترها
بدون شک بازشناسی کاراکترهای دست نویس پایه کلیه ماشینهای خواندن اتوماتیک هستند. بازشناسی کاراکترها به صورت تک تک می تواند نمونه ای از مسائل تشخیص الگو باشد که نیاز به انتخاب ویژگیها استخراج ویژگیها، فرایند یادگیری و دسته بندی اطلاعات دارد دو دیدگاه کلی بازشناسی کاراکترها و اعداد می توانند به صورت زیر باشند.
1-تطبیق الگو
2- تحلیل ساختاری

[mzjahromi]

روشهای شناسائی برون خطی ( Off-Line ) روی تصاویر دو بعدی اعمال می شوند درحالیکه در روشهای بلادرنگ از داده های یک بعدی استفاده می شود . در حالت بلادرنگ می توان قسمتهای مختلف متن را ذخیره کرد و سپس عملیات شناسائی را توسط روشهای برون خطی انجام داد . روشهای بلادرنگ دارای مزیتهای فراوانی هستند که تعدادی از آنها عبارتند از 1- ترتیب نوشتن 2- جهت و نحوة حرکت قلم موجود است و می تواند جهت شناسائی مورد استفاده قرار گیرد. همچنین برداشتن و گذاشتن قلم نیز می تواند جهت شناسائی ضربه ها مورد استفاده قرار گیرد .
روشهای تشخیص کاراکترها به صورت بلادرنگ ، به دو دستة عمده تقسیم می شوند .
1-تحلیل کاراکترها با استفاده از ترکیب ، که مبتنی بر مدل سازی متون تولید شده دست نویس می باشد .
2- استفاده از روشهای برون خطی جهت شناسائی بلادرنگ

[mzjahromi]

بازشناسی حروف چینی یکی از زمینه های بسیار جالب و پیچیده در تشخیص الگو می باشد و مطالعات و تحقیقات زیادی در این زمینه انجام شده است. در این راستا مشکلات زیادی وجود دارد. به عنوان مثال کاراکترهای چینی واضح و شمرده هستند اما از نظر اندازه بسیار بزرگ و از نظر ساختاری نیز با یکدیگر شباهت زیادی دارند . بنابراین دسته بندی و شناسائی آنها بسیار مشکل می باشد در این مقاله روش جدیدی جهت شناسائی متون دست نویس چینی با استفاده از روشهای آماری تشخیص الگو معرفی شده است . دسته بندی و شناسائی با استفاده از نقاط بحرانی ، استخراج ویژگیها ودسته بندی آماری کاراکترها انجام می شود . این سیستم بر روی 500 کاراکتر مختلف ( واز هر کاراکتر 40 نمونه جداگانه ) تست شده است و دارای بازده 84.43% بوده است که این مورد از بهترین نتایج حاصل حاصل شده می باشد.
در بازشناسی کارکترهای چینی مشکلات زیادی وجود دارد . اول آنکه تعداد کاراکترها بسیار زیاد است ( بیش از 50000 کاراکتر که 6000 مورد آن معمولا مورد استفاده قرار می گیرند ) دوم اینکه کاراکتر های چینی ساختار بسیار پیچیده ای نسبت به حروف الفبای معمولی دارند و همچنین بسیاری از آنها دارای ساختار مشابهی می باشند. اینگونه مسائل در متون دست نویس بسیار پیچیده تر خواهد شد . روشهائی که در این زمینه پیشنهاد شده اند به دو دسته مهم تقسیم می شوند اولین روش بررسی ضربه ها می باشد که ویژگیهائی مانند نقاط انتهائی نقاط کناری موقعیت ضربه ها و… را از نمونه ورودی استخراج می کند . و دومین روش تطبیق الگو می باشد که مبتنی بر مقایسه الگوی ورودی و مدل استاندارد می باشد. بیشتر منابع، استفاده از دیدگاه بررسی ضربه ها را پیشنهاد می کنند به عنوان مثال یکی از روشهای موجود جهت تحلیل کاراکترهای چینی ( Augi )از روابط بین نقاط اتصال ، نقاط کناری و … استفاده می کند.
یاماموتو از جهت ضربه ها ، دسته بندی ضربه ها دامنه ضربه ها و چگالی ضربه ها جهت دسته بندی کاراکترها استفاده می کند. هسیه ولی نیز از آرایه ای یک بعدی که شامل ترتیبی از ضربه ها و روابط بین آنها می باشد استفاده می کنند. برای کلیه این روشها ، نیاز به یک الگوریتم مناسب جهت استخراج صحیح ضربه ها و همچنین دستیابی به یک کارائی مناسب می باشد این روش با استفاده از تکنیک جستجوی نقاط بحرانی، ویژگیها را جهت دسته بندی و شناسائی کاراکترهای چینی با استفاده از روشهای آماری ، استخراج می کند.

[mzjahromi]

سیستمهای مبتنی بر قائده نیز در نرم افزارهای تشخیص کاراکتر مورد استفاده قرار می گیرند. مطمئنا بیشتر قوانین باید با تجربه و برخورد با کاراکترهای جدید تعریف شوند. بدین ترتیب کارائی سیستم بالاتر خواهد رفت بدیهی است هر چه تعداد قوانین معرفی شده به سیستم بیشتر باشد کارائی سیستم بالاتر خواهد رفت و به دنبال آن توانائی سیستم برای شناسائی مجموعه بزرگتری از کاراکترها نیاز به قوانین بیشتری دارد ولی در شناسائی ده رقم زبان عربی بیش از چهار صد قانون مورد استفاده قرار گرفته است که کارائی سیستم در اینحالت 91.4 % بوده است همانطور که قبلا گفته شد جهت افزایش کارائی می توان تعداد قوانین استفاده شده را افزایش داد.

[mzjahromi]

در این مبحث ، روشی از بازشناسی ارائه شده است که با استفاده از یک شبکه هوشمند عصبی ( Neocognitron ) کار می کند. این روش نوعی از شبکه های عصبی است که جهت مدل سازی تصاویر مورد استفاده قرار می گیرد و قادر به کسب توانائی هائی جهت شناسائی الگوهای تصویری توسط یادگیری می باشد. هدف این مبحث به اثبات رساندن این مطلب است که شبکه های عصبی مذکور قادر به شناسائی مجموعه بزرگی از الگوهائی که در جهان واقعی با آنها مواجه می شویم است.
توانائی شبکه های عصبی در شناسائی کاراکترها ارتباط مستقیمی با استخراج ویژگیها در شبکه دارد در این مبحث کارائی شبکه های عصبی با بکارگیری دو مقدار آستانه ای و استفاده ازیک بانک اطلاعاتی بزرگ تحت عنوان ETL1 بررسی شده است . بانک اطلاعاتی ETL1 یک مجموعه از کاراکترهای دست نویس است که شامل انواع مختلفی از ارقام دست نویس می باشد. این ازقام توسط 1400 نفر نوشته شده اند و حدود 200 نمونه مختلف و تصادفی از هر مجموعه جهت یادگیری انتخاب شده است (مجموعاً 2000 مورد). به علاوه از هر مورد مجموعه 300 رقم دیگر نیز جهت تست میزان کلیت برنامه انتخاب شده است .
. نتیجه بدست آمده رقمی بالای 98 % جهت الگوی ارقام موجود در ETL1 بوده است .

[mzjahromi]

اکثر سیستمهائی که بدون تأثیر تغییر شکلها و تغییر مکانهای تصویر عملیات شناسائی را انجام می دهند ، توانائی محدودی در این زمینه دارند و لازم است حتما تصویر تغییر شکل یافته استاندارد باشد و قادر به شناسائی تصاویری که دارای چرخش جابجائی فشردگی و کشش هستند نمی باشند به عنوان مثال نمونه ای از اینگونه ماشینها تنها قادر به شناسائی الگوهای تغییر شکل یافته ( افزایش طول یا عرض و … ) می باشند ولی الگوهای چرخش یافته را نمی توانند شناسائی کنند . Neocognitron مدلی از شبکه های عصبی چند لایه است که قادر به شناسائی الگوها می باشد این شبکه دارای یک ساختار سلسله مراتبی است که لایه های بالائی آن دارای حساسیت بیشتری نسبت به انتقال و چرخش الگو در تصویر می باشند این شبکه قادر به استخراج ویژگیهای پیچیده تصویر نیز می باشد این مدل نیز با استفاده از کاراکترهای دست نویس موجود در پایگاه داده ETL1 تست شده است و نتیجه ای بالای 98% را ارائه داده است لازم به ذکر است که این روش قادر به شناسائی الگوهائی که بیش از حد چرخش یافته اند نمی باشد

[mzjahromi]

بیشتر روشهائی که جهت دست یابی به کارائی بالا در بازشناسی کاراکترها ارائه شده است عملیات شناسائی را با استفاده از راه حلهای آماری ، شبکه های عصبی و ترکیبی از شبکه های عصبی و روشهای آماری ، انجام می دهند . اینگونه روشها را می توان با بررسی پارامترهائی از قبیل ، سرعت، کارائی ، نیازمندیهای حافظه ای ، امکان پیاده سازی بر روی سیستمهای دیجیتال و در شبکه های عصبی سرعت یادگیری ارزیابی کرد . در این میان شبکه های عصبی بیشتر از سایرین جالب توجه است . چون تعادل مناسبی را بین کارائی ، سرعت و امکانات سخت افزاری بر قرارمی کند . MLP نیز نمونه ای از شبکه های عصبی است که جهت دسته بندی اطلاعات مورد استفاده قرار می گیرد. در این مبحث مدلی برای شناسائی کاراکترهای دست نویس با استفاده از MLP مطرح شده است.
استفاده از تکنیکهای ساده پیش پردازش ، سیستم یادگیری پیشرفته و دو مرحله ای و ارائه سه گروه از نمونه های آزمایشی باعث ایجاد کارائی و سرعت بسیار قابل توجهی شده است . پیاده سازی کامل نرم افزار ( به زبان C ) در مراحل پیش پردازش و شبکه های عصبی MLP و پیاده سازی منطقی بر اساس معماری شبکه های عصبی با استفاده از زبان VHDL ، سرعت و کارائی بالائی را ارائه کرده است. مجموعه های تست و یادگیری برای این سیستم از پایگاه داده NIIST ( National In stitute for standard and tochnoloyy) انتخاب شده اند . در مرحله اول به منظور افزایش سرعت سیستم تنها چند هزار کاراکتر به سیستم شناسانده شده است . پس از حدود ده مرحله ، تعداد نمونه ها به تدریج افزایش یافته تا زمانیکه کل مجموعه یادگیری را شامل شود . کارائی MLP توسط 11.941کاراکتر برای حروف بزرگ و 58.536 کاراکتر برای اعداد ، بررسی شده است . نتیجه حاصل از تست سیستم با توابع مختلف در مرحله پیش پردازش ، به صورت زیر می باشد .

جدول4)کارائی روش MLP
شبکة عصبی حروف بزرگ اعداد
MLP-1 93.4 /
MLP-2 94.82 96.45
MLP-3 96.2 97.02

[mzjahromi]

این مبحث روشی را جهت شناسائی کاراکترها ارائه می دهد که دارای سرعت بالا و دقت کافی بوده و با استفاده از تقسیمات چند مرحله ای و ویژگیهای سلسله مراتبی عملیات خود را انجام می دهد. ویژگیها در دسته های مختلف از کم دقت تا با دقت توسط مفاهیم بازگشتی دسته بندی می شوند . سیستم های شناسائی با توجه به منابع محاسباتی از قبیل میزان حافظه و زمان پردازش میزان استفاده از ویژگیها را در مراحل مختلف کنترل می کنند . در این مبحث روشی مطرح شده است که میزان مراحل لازم جهت دسته بندی الگوی ورودی را مشخص می کند این مورد باعث استفاده بهینه از منابع محاسباتی می شود .
OCR سلسله مراتبی ، به صورت پویا فاکتوهائی مثل کیفیت الگوی ورودی تشابهات و اختلافات یک گروه از الگوها با گرهی دیگر ، و زمان لازم جهت پیش پردارزش را نیز در نظر می گیرد. زمانیکه عملیات تست این روش، با مجموعه اطلاعات NIST انجام شد ، این روش حدود 300 بار سریعتر از روشهای K- neakest – neigbor و ده بار سریعتر از روشهای شبکه های عصبی بود . در حالیکه کارائی این روش در حدود 96% بوده است که این مقدار معادل مقادیر حاصل شده با دو روش دیگر می باشد.


شکل7 ) نمونه ای از تصویرها و زیر تصویرها


آزمایشات با استفاده از اعداد جدا سازی شده و تصاویر کاراکترهای موجود در پایگاه داده CEDAR و NIST که از آدرسهای پستی جمع آوری شده اند انجام گرفته است. نمونه ها به دو دسته یادگیری و تست و به صورت مجموعه های مختلف تقسیم بندی شده اند و بطور جداگانه مورد بررسی قرار گرفته اند نتابج این بررسی در جدول 5 مشاهده می شود .



جدول 5 ) کارائی روش سلسله مراتبی
Testingset Traning Set Image Source Testing Image Traning Image No. Of Classes Data Set
Top2 Top1 Top2 Top1
98.8 96.2 99.9 99.5 Postal +NIST 12242 25656 10 1
99.5 98.2 99.7 98.6 NIST Digit 53301 159228 10 2
98.8 96.4 99.9 99.2 NIST Alpha Uppercase 11481 34961 26 3
97.1 90.4 99.8 98.7 NIST Alpha lowercase 9623 29059 26 4
94.7 78.2 98.7 93.4 NIST Alpha foll class 21104 64020 52 5
97.1 92.4 99.5 97.5 NIST Alpha folding 21104 64020 52 6

[amir_pro]

سلام
می خواستم بدونم از چه الگوریتمی باید استفاده کرد که عکسی را که در اختیار داریم بتوان به نواحی فعالی تبدیل کرد که هر کدام حکم عکس را داشته باشد.
با تشکر

[mzjahromi]

هر کدوم از این روشهلائی که دیدید و صدها روش دیگه از الگوریتم خاص خودشونن استفاده می کنن.
فکر می کنم منظور شما جدا سازی هست.
جدا سازی خودش یه مقوله مهم در OCR هست و برای زبانهای مختلف فرق میکنه. مثلا برای متون تایپی انگلیسی نسبتا راحت تر هست و برای متون به هم پیوسته فارسی خیلی مشکلتره
شما شباهت ش و ثب رو در نظر بگیرید.
ولی خوب کل این مراحل هست که OCR رو ایجاد میکنه
1- حذف نویزها
2- نازک سازی
3- جدا سازی
4- تشخیص

البته بسته به روش انتخابی شما ممکنه مرحله 2 و 3 جابجا بشن یا 2 حذف بشه.

تو یه سری از روشها هم میان و کلمات رو شناسائی میکنن. تو این گونه روشها معمولا جداسازی ساده تره چون معمولا بین کلمات فاصله وجود داره

[amir_pro]

سلام
ببینید ما شرط می کنیک که همه ویژگی های اون نوشته که به عکس تبدیل شده ثابت باشد مثلا سایز آن 14 و فونت استایل آن رگولار باشد. خوب، بعد چطور می شود این عکس را به نواحی تقسیم کنیم که در آن بیاید قسمتهای بالا و پایین و چپ و راست آن را که سفید است و امون ثابت بوده را حذف کنیم و اون عکسی را که به این شکل تبدیل شده را به قسمتهایی تبدیل کنیم که هر قسمت آن اندازه حروف باشد که آن حروف هم انگلیسی هستند. بعد آن عکسی را که کوچک است را با 26 عکسی که حروف انگلیسی دارند مقایسه کرد البته باید بگم که برنامه ای نوشتم که می آید دو تا عکس با پسوند بی ام پی را مقایسه می کند. ممنون میشم اگه ککمک کنید

[mzjahromi]

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

[amir_pro]

سلام
ممنون از راهنماییتون.سعی می کنم برنامه سطرشا بنویسم اما اسکن دلفی تا اونجایی که من بلدم (کمی بلدم) عمودی انجام می شه و نمیدونم باید چیکار کرد

[mzjahromi]

سلام
مگه با چه ابزاری از دلفی کار میکنید؟
من خودم با TImage کار کردم.

[amir_pro]

سلام
مگه با چه ابزاری از دلفی کار میکنید؟
من خودم با TImage کار کردم.

سلام
ممنون از کمکاتون
Timage ببخشید ولی امتحان کردم و عنصر
ویژگی اسکن را نداشت، شما چه جوری این کار را انجام دادید

[mzjahromi]

مگه چطوری اسکن میکنید؟

Function Picture.GetPixel2(image:TImage;x,y:Integer):Byte;

Begin                 //read a 2 color bitmap pixels from file

   if Image.Canvas.Pixels[x,y]=0 then

     GetPixel2:=NcColor

   else

     GetPixel2:=BackColor;

End;

[mzjahromi]

function Picture.NextRow(i:Integer;var down:Integer):Boolean;

var

  x,y,count:Integer;

  flag:Boolean;

begin

   y:=i+1;

   Flag:=False;

   repeat

    count:=0;

    for x:=0 to w-1 do

      if getpixel(X,y)<>BackColor then

        Count:=Count+1;

    if count>0 then

      flag:=True;

    y:=Y+1;

   until ((Flag and(count=0))or(y=h));

   down:=y;

   if Y>=h then

     NextRow:=False

   Else

     NextRow:=True;

End;

function Picture.Nextcol(top,down,i:Integer;var Right:Integer):Boolean;

var

  x,y,count:Integer;

  flag:Boolean;

begin

   X:=i+1;

   Flag:=False;

   repeat

    count:=0;

    for y:=top to down do

      if getpixel(X,y)<>BackColor then

        Count:=Count+1;

    if count>0 then

      flag:=True;

    X:=X+1;

   until ((Flag and(count=0))or(X>=W));

   Right:=X;

   if X>=W then

     Nextcol:=False

   Else

     Nextcol:=True;

End;

[aakh1361]

سلام مقاله خوبی بود
اما چرا ادامه ندادید ؟

[mzjahromi]

سلام مقاله خوبی بود
اما چرا ادامه ندادید ؟

باشه ادامه میدم.

[mzjahromi]

ادامه از پست 10

استفاده ازمحاسبات نرم افزاری جهت شناسائی اعداد دست نویس
اینگونه روشها با استفاده از تئوریهای منطق فازی شبکه های عصبی و تئوری احتمالات سعی در شناسائی ویژگیهای قابل استخراج به همراه ضریب خطاهائی ازقبیل ضریب اطمینان میزان صحت و… دارند. دراین مبحث نمونه ای از این روشها جهت دسته بندی اطلاعات مورد استفاده قرار گرفته اند. در این روش از منطق فازی جهت شناسائی و استخراج ویژگیها و از تئوری احتمالات جهت دسته بندی اطلاعات استفاده شده است.
روشهای آماری متعارف که در موضوعات مختلف شناسائی کاراکترها مورد استفاده قرار می گیرند با اعمال محدودیتها وقوانینی ، عملیات دسته بندی نمونه ها را انجام می دهند اینگونه روشها با یک مشکل نه چندان ساده مواجه هستند و آن برخورد دسته های مختلف با یکدیگر می باشد یکی از راه حلهائی که برای این مشکل می توان مطرح کرد تعیین درجه عضویت است از این طریق می توان عملیات شناسائی را ساده تر انجام داد. روشی که در اینجا انتخاب شده است جهت دسته بندی ارقام دست نویس طراحی شده است . این روش بجای اینکه اطلاعات را به 62 دسته مختلف ( جهت شناسائی ارقام و حروف ) دسته بندی کند آنها را به ده دسته تقسیم می کند ( تنها ارقام را شناسائی می کند ) این کار نمونه مورد بررسی را ساده تر خواهد کرد در حالیکه کلیه مشکلات حالت قبلی را ( از قبیل برخورد دسته های مختلف با یکدیگر ، نویز، … ) دارا است.
سیستمهای موجود جهت شناسائی کاراکترها روشها و راههای مختلفی را پیشنهاد می کنند به طور کلی در سیستمهای شناسائی می توان دو مرحله را در نظر گرفت : اول طراحی روشی جهت استخراج ویژگیها. و دوم دسته بندی ویژگیها. کلیه فعالیتهای این روش بر روی دو بخش فوق متمرکز می شود یک بخش مربوط به استخراج اتوماتیک ویژگیها که مبتنی بر شبکه های عصبی است و بخش دیگر جهت دسته بندی ویژگیها که مبتنی بر احتمالات و منطق فازی می باشد.
سالهای زیادی است که شبکه های عصبی دارای اهمیت زیادی ازنظر تحقیقات شده است . هدف از این تحقیقات پیوسته شبیه ساختن عملیات ماشین به انسان می باشد SOM که توسط کوهونن پیشنهاد شده است یک ساختار شبکه ای جهت استفاده در سیستم های شناسائی الگومی باشد از این سیستم نیز جهت استخراج ویژگیها استفاده شده است و نتایج را بهبود بخشیده است .
این سیستم در یک زبان برنامه نویسی منطقی با نام فریل ( Fril ) پیاده سازی شده است . زبان برنامه نویسی فریل امکانات لازم جهت پیاده سازی این سیستم و اهدافی از قبیل مجموعه های فازی احتمالات ، ضریب اطمینان و … را پشتیبانی می کند این سیستم عملیات یادگیری را با سرعت نسبتاً پائینی انجام می دهد ( حداکثر ده ساعت برای سیستمهای عادی ) اما بدون اعمال هیچگونه عملیات بهینه سازی قادر به شناسائی و دسته بندی سریع ارقام با سرعتی در حدود 5 الی 15 رقم در ثانیه می باشد . این سیستم برای هر الگو ضریب تشابهی را با هر ده رقم ارائه می دهد نمونه ای از این ضرایب در شکل زیر مشاهده می شود .



شکل 5) نمونه ای از کاراکتر،نازکسازی و نرمالسازی آن و ضریب تشابه آن با هر ده کاراکتر

جهت شناسائی، الگوئی که دارای بالاترین ضریب تشابه است ارائه می شود. نتیجه مجموعه های یادگیری و تست در جدول 2 مشاهده می شود این جدول نتایج بیشترین در صد تشابهات برای هر دسته را نشان می دهد که مقادیری استاندارد در سیستمهای شناسائی کاراکترها می باشند مقادیر 60.2 % , 73.2% در مجموعه های یادگیری و تست بدین معنی است که ویژگیهای استخراج شده از بهترینها نبوده اند . جهت افزایش کارائی سیستم از ویژگیهائی که توسط سیستم SOM استخراج شده اند استفاده می کنیم. جدول 1 نتیجه حاصل شده با اعمال 14 ویژگی کلی را نشان می دهد .





جدول 1) نتیجه ویژگی های ساده
مجموعه دسته بندی
0 1 2 3 4 5 6 7 8 9 مجموع
یادگیری 66.2 79.8 70.4 69.2 81.2 71.5 66.3 63.4 77.4 82.2 73.2
تست 51.0 67.6 55.9 51.4 82.1 39.7 68.1 54.1 45.6 49.6 60.2


جدول 2)نتیجه ویژگی های ساده و ترکیبی
مجموعه دسته بندی
0 1 2 3 4 5 6 7 8 9 مجموع
یادگیری 80.3 83.2 90.9 75.4 94.6 89.5 83.0 66.5 93.3 91.4 84.6
تست 73.7 77.6 80.8 61.4 92.5 49.1 78.1 64.2 55.6 59.7 71.9


استفاده از ترکیب ساختاری ویژگیها ، باعث افزایش کارائی سیستم به 71.9% و 84.6% برای مجموعه های یادگیری و تست شده است . در اینحالت عملیات محاسباتی اضافه ای که انجام می شود عبارتند از : استفاده از قوانین با ویژگیهای بیشتر و مجموعه های فازی بزرگتر . ولی می توان آنها را با حذف ویژگیهائی که دارای تأثیر کمتری ( وزن کمتر ) هستند کاهش داد . این مورد را می توان با اعمال یک مقدار آستانه جهت حداقل وزن برای هر چهارده ویژگی انجام داد .
1/14=0.036
در اینصورت باید وزن ویژگیهای باقیمانده را دوباره نرمالسازی کنیم . با اعمال این موارد ، بازدهی سیستم به82.3% و 70.8% کاهش می یابد ولی سرعت پردازش تا حدود دو برابر افزایش خواهد یافت.
با استفاده از ترکیب ویژگیها می توان نتیجه مناسبتری بدست آورد. همانطور که در جدول 3 دیده می شود ترکیب تنها سه نوع ویژگی نتیجه مناسبتری را ارائه می دهد . ( 89.6% و 82.5% ) این مجموعه اطلاعات با ویژگیهای تولید شده توسط سیستم SOM بدست آورده شده است .

جدول 3)نتیجه ترکیب سه نمونه از ویژگیها
مجموعه دسته بندی
0 1 2 3 4 5 6 7 8 9 مجموع
یادگیری 88.6 85.3 96.2 79.0 98.3 88.6 86.6 83.2 98.7 95.4 89.6
تست 81.6 82.6 85.8 65.5 97.5 69.1 84.1 70.1 61.6 61.7 82.5

[mzjahromi]

شناسائی فونتها با استفاده از ویژگیهای گرافیکی و تایپی
تاکنون منابع قابل توجهی درزمینه شناسائی متون تایپی ارائه شده است. سیستمهای جدید OCR که سیستمهای تک فونت نامیده می شوند ، قادر به خواندن یک فونت واحد و در بعضی موارد یک فونت ویژه ، که برای آن طراحی شده اند می باشند. ( Ocra ocrb fonts ) تحقیقات و پیشرفتهای انجام شده اخیر در این زمینه ، به منظور طراحی سیستمی جهت شناسائی کلیه فونتها می باشد. که سعی در شناسائی کاراکترهای کلیه فونتها دارد. تعدادی از سیستمهای موجود OCR تنها قادر به شناسائی دو یا سه حالت از یک فونت مثل Sanserif ,seriffed , boldItolic می باشند. در این زمینه می توان به دو روش مکمل اشاره کرد.
1-پیش روش: که کاراکترهای تحلیل شده متن هنوز شناسائی نشده اند
2-پس روش: که محتویات متن نیز در شناسائی کاراکترها کمک می کنند.
موریس توانائی مدلهای بینائی انسان را جهت تشخیص متون تایپی بررسی کرده است. او از تبدیلات فوریه جهت استخراج ویژگیهای کلی بردارها و روش کلاس بندی بیز استفاده کرده است. خوبیاری و هال نیز روشی را ارائه داده اند که فونت اصلی در یک متن را مشخص می کند.
در این مبحث پیش روشی از (Optical font Recognition) ارائه شده است که هدف آن تفاوت قائل شدن بین فونتها ئی که در بخش خاصی از متن واقع شده اند و مجموعه بیشماری از صدها فونت شناخته شده، می باشد. دراین سیستم که Apofis ( ( A priori optical font Identification system نامیده می شود، ویژگیهای گرافیکی متون تایپی از تصویر متن استخراج می شود و توسط تئوری کلاس بندی بیز مورد استفاده قرار می گیرد.


شکل 8 )دسته بندی قطعات متصل به هم




نتایج حاصل از این الگوریتم به صورت زیر می باشد.

جدول 6)نتیجه شناسائی فونتها
FONT
Seriffed Typefaces
97.46 PL Palatino
96.92 NC New-century-schlbk
95.27 LB Lucida-bright
92.87 TN Times
SanSeriffed Typefaces
99.84 HB Helvetica-black
99.58 AG Avant-Grade
99.44 HV Helvetica
91.26 LS Lucida-Sans
TypeWriter TypeFaces
99.30 CR Courier
97.16 LT Lucida-Sans-TypeWriter
96.91 Average

[mzjahromi]

بازشناسی کاراکترها به روش VDHMM
روش HMM ((Hidden Markov Model یکی از موفق ترین روشهائی است که تاکنون ارائه شده است این روش سعی می کند با شکستن کلمات به اجزاء کوچکتر آنها را شناسائی کند VDHMM که دراین مبحث مطرح شده است روش PDHMM موفقی جهت شناسائی کلمات دست نویسی می باشد . در این روش توسط یک مدل ، کل نمونه مدلسازی می شود . بنابراین 26 حالت مختلف که به 26 حرف مختلف در الفبا مربوط می شوند وجود دارد.قبل از شناسائی، کلمات به قطعات کوچکتری شکسته می شوند. فرض می شود که حداقل یک نقطه انقطاع بین دو کلمه دست نویس مجاور وجود دارد . به منظور تأمین این احتیاجات مجبور به استفاده از الگوریتمها ی جداسازی می باشیم ولی این الگوریتمها نقاطی قلابی نیز به عنوان نقاط انقطاع معرفی می کنند. معقول ترین راه حل، برطرف ساختن ابهامات جدا سازی با شناسائی نقاط قلابی می باشد . مهمترین سؤالی که در اینجا مطرح می شود این است که : آیا می توان مدلی برای یک کلمه ارائه داد(MD-HMM)که کلیه پارامترهای سیستم برای این مدل جدید از پارامترهای VD- HMM نتیجه شود ؟ برای درک بهتر این مدل از VD-HMM مدلی با نام NE-HMM (Non – Ergodic ) ارائه شده است. که در این مدل وضعیت هر نوع کاراکترتنها می تواند از چپ به راست بدست آید و مدل کلمات باید از اتصال مدل کاراکترهای مورد نیاز حاصل شوند . NE-HMM نیاز به مرحله دشوار یادگیری ندارد و همچنین مشکلات ویژه روش MD-HMM را نیز ندارد.

شکل 9 ) a)تصویر اصلی b)تصویر جداسازی شده c)بلوکهای تصویر
با توجه به اینکه روش VD-HMM از احتمال تکرار حروف نیز در شناسائی استفاده می کند ، مشکل دیگری که برای این روش و کلیه سیستمهای مشتق شده از آن وجود دارد ، نیاز به قابل اطمینان بودن احتمال تکرار می باشد. این احتمالات در زمان اجرا محاسبه می شود.
مرحله دوم این روش، ارائه راه حلی جهت اجتناب از محاسبه احتمال تکرار حروف می باشد. با توجه به ایتکه جداسازیهای اضافی ، توسط الگوریتمهای جداسازی تولید می شوند مجموعه های متعددی از نقاط انقطاع در نظر گرفته می شود که هر مجموعه ، با یک روش جداسازی مخصوص به خود ارائه شده است . بخش شناسائی بهترین جداسازی را انتخاب می کند. این بخش مجموعه ای را انتخاب می کند که شامل نقاط صحیح انقطاع باشند و دارای بهترین ترتیب از نظر موقعیت حروف در کلمه باشد . این فلسفه شبیه به VDHMM است ولی با استفاده از یک پیش فرض ساده دیگر به محاسبات پیچیده احتمال رخداد نیازی نیست . این مفروضات می توانند به صورت زیر باشند .
فرض کنید یک کاراکتر می تواند حداکثر به چهار کاراکتر شکسته شود. بدین ترتیب چهار احتمال تکرار برای هر وضعیت وجود خواهد داشت. پس از تخصیص دادن احتمال تکرارهای از پیش تعیین شده برای هر وضعیت ، تنها برنده انتخاب می شود. هنگام شناسائی ، با بررسی یک ، دو ، سه و یا چهار قطعه مجاور به عنوان یک نماد ، می توان بیشترین احتمال یکی از نمادها را یافت و سپس احتمال تکرار این نماد در متن را بررسی کرد . در این روش از محاسبه احتمال تکرار یک نماد در هر وضعیت، جلو گیری می شود. کارائی این روش همانطوری که انتظار می رود مانند روش VD-HMM است . این روش جدید VSL-HMM نام دارد (Variable Sequence length ) نتیجه آزمایشات انجام شده بر روی سیستمها در جداول زیر مشاهده می شود.

جدول 7) نتیجه روشهای HMM

1000 کلمه 100 کلمه 10 کلمه
VD-HMM
PD-HMM NE-HMM
MD-HMM VD-HMM
PD-HMM NE-HMM
MD-HMM VD-HMM
PD-HMM NE-HMM
MD-HMM نوع سیستم
21.27 - 24.47 - 63.82 - مستقیم
45.74 74.47 69.15 88.29 88.29 96.80 Top1
- - 82.98 95.74 98.93 100 Top5

67.02 92.55 - - - - Top10

[mzjahromi]

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

[aakh1361]

واقعا مقاله خوب و کاربردی هست

موفق باشی

[mzjahromi]

ممنون از لطفتون.

[mzjahromi]

با فرض اینکه کاراکتر یا الگوی ورودی به صورت نازکسازی شده است، ابتدا نقاط بحرانی تصویر را جستجو می کنیم. این نقاط عبارتند از نقاط اتصال ، نقاط انحراف و نقاط ابتدائی و انتهائی کاراکترها. بدین ترتیب هر گونه تغیر مسیر ، انشعابات و انقطاع را به عنوان یک نقطه بحرانی علامتگذاری می کنیم
نمونه ای از اینگونه نقاط را در شکل 1 مشاهده می کنید.


شکل 1 ) نمونه هائی از نقاط بحرانی


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


شکل 2) نمونه ای از گرافهای تولید شده

حال درون گراف ، هشت نمونه یال مختلف به صورتهای زیر وجود دارد .


شکل 3) نمونه هائی از یالهای موجود در گراف

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

شکل 4 ) تشابه گرافهای یک کاراکتر در فونتهای مختلف

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


شکل 5 ) جهت پیمایش و ترتیب شناسائی
یالها در یک گره از گراف

پس از پیمایش کامل گراف،رشته ای از جهتهای پیموده شده بدست خواهد آمد که با مقایسه این رشته ها با یکدیگر، قادر به شناسائی کاراکترها می باشیم.

شکل 6 ) نتیجه پیمایش گراف


در صورتیکه شکل ساختاری یا فونت دو کاراکتر یکسان باشد، رشته بدست آمده در قسمت فوق نیز یکسان خواهد بود و می توان با مقایسه مستقیم رشته ها با یکدیگر، کاراکتر را شناسائی کرد. اما در صورتیکه مانند شکل 4 زائده های اضافی در یک کاراکتر ظاهر شود، این زوائد درون رشته نیز وجود خواهد داشت ونتیجه کاملا یکسان نخواهد بود. بدین ترتیب شناسائی باید هوشمندانه تر انجام شود. در این حالت اگر با توجه به نتیجه ای که از پیمایش اول سطح حاصل می شود، عملیات شناسائی را انجام دهیم ، قسمتهای اضافی کاراکتر به ابتدای و انتهای رشته منتقل می شوند. مشاهده می شود که در اینجا نیز شناسائی نسبتا ساده است. اما در حالتهایی که شکل کاراکتر کمی پیچیده باشد ( مانند B ) باز هم با مشکلاتی مواجه خواهیم شد. این مشکلات در شناسائی قسمتهای نیم دایره مانند تصویر می باشد. جهت شناسائی اینگونه قسمتها نیاز به اندازه گیری میزان چرخش و قضاوت بر روی این مقدار داریم، بدین منظور نمی توانیم از الگوریتم پیمایش اول سطح استفاده کنیم، زیرا در این الگوریتم، همانطور که مشاهده می شود لزوما قسمتهای خطی تصویر، پشت سر هم پیمایش نمی شود و در رشته نهائی نمی توان نتیجه گرفت که قسمتهای پشت سر هم ، مربوط به خطوط پیوسته است بنابراین باید از روش اول عمق استفاده کنیم.
با توجه به ویژگیهای این روش، می توان نتیجه گرفت که برای انجام این کار مناسب است ( اندازه گیری میزان چرخش ) .اما نباید فراموش کرد که در این روش کلیه زوائد متن در لابلای رشته تولید شده ظاهر می شوند. و این مورد عملیات شناسائی را تا حدود زیادی مشکل می سازد.
برای حل این مشکل می توان از روش جدیدی جهت پیمایش گراف استفاده کرد. این روش ترکیبی از روشهای اول سطح و اول عمق می باشد. بدین صورت که هنگام پیمایش گراف و در زمانیکه یک سطح را پیمایش می کنیم ، در هر یک از مسیرهای موجود ، عملیات پیشروی را تا زمانیکه به یک تقاطع برسیم ادامه می دهیم. بدین ترتیب باز هم خطوط ممتد را بصورت یکپارچه خواهیم داشت و شناسائی کاراکتر نیز ساده تر از قبل خواهد بود. شکل زیر این نوع پیمایش را نشان می دهد.


شکل 7 ) نحوه پیمایش گراف به روش ترکیبی

با استفاده از روشهای فوق و شناساندن چند نمونه از فونتهای مختلف به سیستم، می توان عملیات شناسائی کاراکترها را با کارائی نسبتا مناسبی انجام داد. اما با افزودن امکانات اضافه تری به سیستم فوق ، باز هم می توان کارائی سیستم را بالا برد .
نمونه ای از اینگونه امکانات عبارتند از :
1-استفاده از روشهای آماری و همچنین استفاده از احتمالات جهت تطبیق دو الگو با یکدیگر. بدین ترتیب تطبیق دو رشته مختلف کمی پیچیده تر از یک مقایسه ساده می باشد ولی کارائی سیستم به مقدار زیادی بالا خواهد رفت.
2-یافتن روشهای مناسبتری جهت پیمایش گراف . همانطور که مشاهده شد کارائی سیستم با استفاده از روشهای مختلف پیمایش ، تغییر می کند ممکن است بتوانیم روشی بهتر و مناسب تر جهت پیمایش گراف یافته و توسط آن کارائی سیستم را بالا ببریم .
بطور کلی مراحل مختلف طی شده در این الگوریتم به صورت زیر می باشند
1-نازک ساختن خطوط تصویر ویافتن تصویر ناکسازی شده (Skeleton Image )
2-یافتن نقاط بحرانی در حداقل تعداد ممکن
3-یافتن گراف مربوط به کاراکتر ، با استفاده از نقاط بحرانی و اتصالات بین آنها
4-پیمایش گراف و یافتن رشته مربوط به پیمایش
5-جستجوی رشته حاصل شده در بانک اطلاعاتی و یافتن الگو ، با استفاده از اطلاعاتی که در مرحله یادگیری یه سیستم داده شده است .
شکل زیر تا حدودی بیانگر مراحل فوق می باشد .

[mzjahromi]

3-2-1)الگوریتم نازکسازی
اولین مرحله از این الگوریتم ناکسازی است. با توجه به اینکه استخراج نقاط بحرانی و تشخیص ارتباطات بین آنها ، در یک تصویر عادی بسیار مشکل است ، نیاز یه یک الگوریتم نازکسازی می باشد. در اینجا از الگوریتم Zang – suen جهت نازکسازی تصاویر استفاده شده است. این الگوریتم در هر مرحله یک لایه از قسمتهای مرزی تصویر را برمی دارد، و این کار را تا زمانیکه ضخامت کلیه خطوط تصویر یک شود ادامه می دهد و تضمین می کند که تصویر نازکسازی شده ، در وسط تصویر اصلی قرار بگیرد ، و نقاطی که به یکدگیر متصل بوده اند ، اتصال خود را حفظ کرده و نقاط انتهائی خطوط نیز تغییری نکنند. در حذف نقاط مرزی باید به سه نکته توجه کنیم . اولا تعداد نقاط رنگی اطراف یک نقطه باید ثبت شوند . زیرا نباید نقاط انتهائی یک خط حذف شود . همچنین نقاط بحرانی که با حذف آنها اتصالات قطع خواهد شد ، نباید حذف شوند . دوم اینکه اگر در جهت عقربه ساعت به دور نقطه مورد نظر حرکت کنیم باید دو نقطه از نقاط همسایه یکدیگر ، دارای مقادیر متفاوتی باشند ( تغییر رنگ وجود داشته باشد ) بدین ترتیب می توان اطمینان داشت که نقطه درحال حذف شدن از نقاط مرزی می باشد. و همچنین باید مواظب باشیم که نقاط بحرانی تصویر حذف نشوند. با استفاده از الگویتم فوق می توان یک تصویر نازکسازی شده و مناسب جهت انجام عملیات مورد نظر به دست آورد.

3-2-2)گراف
همانطور که گفته شد در این روش کاراکترها را به صورت یک گراف مدلسازی می کنیم وسپس با پیمایش این گراف عملیات شناسائی را انجام می دهیم. بنابراین نیاز به یک الگوریتم مناسب جهت پیاده سازی گرافها داریم. بدین منظور می توان از ماتریس همسایگی استفاده کرد. ماتریس همسایگی ، یکی از روشهای پیاده سازی گراف است که توسط یک ماتریس دو بعدی ارتباطات بین گرهها را مشخص می کند. هر سطر و هر ستون از ماتریس مربوط به یک گره می باشد و در صورتی که یالی بین دو گره موجود باشد محتوای خانه مربوط به سطر گره اول و ستون گره دوم و همچنین محتوای خانه مربوط به ستون گره اول و سطر گره دوم ، علامتگذاری می شود. بدین ترتیب کلیه همسایه های هر گره مشخص می شود و ساختار کلی گراف ظاهر می شود. بدیهی است که برای پیاده سازی یک گراف با n گره ، نیاز به یک ماتریس n*n داریم .

3-2-3)صف
همانطور که می دانیم برای پیمایش گراف به روش اول سطح نیاز به یک صف جهت نگهداری گرههائی که باید پیمایش شوند داریم. در اینجا از صف دایره ای با اندازة ثابت استفاده شده است.
همانطور که می دانیم صف دایره ای نمونه ای از صف است که از یک طرف عناصر وارد آن می شوند و از طرف دیگر خارج می شوند و همچنین ابتدا و انتهای صف نیز به هم متصل هستند .



شکل 9 ) صف دایره ای

3-2-4 ) صف اولویت
با توجه به اینکه عملیات پیمایش یالهای یک گره را همیشه باید با یک ترتیب خاص انجام دهیم به یک صف اولویت نیز نیاز داریم. این صف،یالهائی را که دارای زاویه کمتری نسبت به خط عمود هستند را در ابتدا خارج می سازد. با توجه به اینکه این مسئله در هر دو روش اول عمق و اول سطح اهمیت زیادی دارد، بنابراین در هر دو روش باید از صف اولویت استفاده کنیم همانطور که می دانیم صف اولویت چیزی جز یک صف عادی که مرتبا اعضای آن اولویت بندی می شوند نیست.
همچنین ما نمی خواهیم که اعضای درون صف مرتبا اولویت بندی شوند چون بدین ترتیب باز هم ترتیب پیمایش گرهها به هم می خورد تنها چیزی که باید در نظر گرفته شود این است که در هر گره یالها به ترتیب خاصی پیمایش شوند بدین منظور کافی است که یالهای هر گره را به ترتیب خاصی وارد یک صف معمولی نمائیم بنابراین ابتدا باید یالها را مرتب نموده و سپس آنها را وارد صف نمائیم.
برای مرتب سازی ، در اینجا از الگوریتم حبابی استفاده شده است و قبل از اینکه یالهای یک گره را پیمایش کنیم آنها را مرتب نموده و سپس وارد صف می کنیم.
همانطور که مشاهده می شود از ساده ترین الگوریتمها جهت پیاده سازی این سیستم استفاده شده است. این کار به منظور ساده نمودن پیاده سازی و عیب یابی سیستم انجام شده است و پس از دستیابی به نتایج نهائی می توان الگوریتمهای مناسبتری را در نظر گرفت.

[mzjahromi]

اولین مرحله پیاده سازی سیستم نازکسازی تصاویر استفاده شده است. همانطور که گفته شد از الگوریتم zong- sunen جهت نازکسازی تصاویر استفاده شده است. این الگوریتم دارای توابع زیر است.
1-Range : این تابع بررسی می کند که آیا نقطه در حال بررسی در محدوده مجاز تصویر می باشد یا خیر بدیهی است . نقاطی با طول و عرض منفی و یا نقاطی با طول و عرض بزرگتر از طول و عرض تصویر از نقاط غیر مجاز شمرده می شوند.

Function Picture.range(n,m:Integer):Integer;

Begin

  if(n<0) OR (n>=w)then

    range:=0

  else if(m<0) OR (m>=h)then

    range:=0

  else

    range:=1;

End;

2-Nay8 : این تابع با چرخش حول یک نقطه خاص ، تعداد نقاط رنگی اطراف آن را مشخص می کند.

Function Picture.nay8(i,j,val:Integer):Integer;

var

  n,m,k:Integer;

Begin

  if(GetPixel(i,j)<>val)then

  Begin

   Nay8:=0;

   Exit;

  End;

  k:=0;

  for n:=-1 to 1 do

  Begin

    for m:=-1 to 1 do

    Begin

      if(range(i+n,j+m)<>0)then

	if(GetPixel(i+n,j+m)=val)then k:=K+1;

    End;

  End;

  Nay8:=k-1;

End;

3-crossing-index : این تابع مشخص می کند که نواحی اطراف یک نقطه به چند دسته تقسیم می شوند. بدین ترتیب که در جهت حرکت عقربه های ساعت به دور نقطه مورد نظر می چرخد و به محظ اینکه تغییر رنگی احساس کند شمارگر خود را یکی اضافه نموده و عملیات را تا اتمام یک دور کامل ادامه می دهد با توجه به اینکه تعداد نواحی همیشه ضریبی از دو می باشد، در نهایت مقدار بدست آمده تقسیم بردو شده و برگردانده می شود .
4-thinezs : این تابع عملیات اصلی نازکسازی را انجام می دهد عملیات این تابع به صورت زیر است .
4-1)یک نقطه را در نظر گرفته و مشخص می کند که آیا این نقطه رنگی است یا خیر .

for j:=1 to y.h-2 do

      for i:=1 to y.w-2 do

      Begin

	 if(y.GetPixel(i,j)<>val)then continue;

	 n:=y.nay8(i,j,val);

4-2) به دنبال آن بررسی می کند که نقطه مورد نظر از نقاط انتهائی تصویر نباشد و از نقاطی که در وسط تصویر نیز نباشد .

	 if((n>=2) And (n<=6))Then

	 Begin

4-3)و سپس بررسی می کند که آیا این نقطه از نقاط مرزی است یا خیر.

	   if(y.crossing_index(i,j,error_code)=1)then

	   Begin

4-4) و در نهایت مشخص می کند که آیا با حذف این نقطه خطوط پیوسته تصویر منقطع نمی شوند .

if((y.GetPixel(i-1,j)=BackColor) OR    

y.GetPixel(i,j+1)=BackColor) OR (y.GetPixel(i+1,j)=BackColor))then

 	Begin

if((y.GetPixel(i,j+1)=BackColor) OR (y.GetPixel(i+1,j)=BackColor) OR (y.GetPixel(i,j-1)=BackColor))Then

	       Begin

			 SetPixel(i,j,BackColor);

			 again:=1;

	       End

	End

4-5) در صورتیکه کلیه شرایط فوق برقرار باشند نقطه مذکور حذف خواهد شد .
4-6)عملیات فوق برای کلیه نقاط تصویر انجام می شود .
4-7) کلیه مراحل فوق را آنقدر تکرار می کند که دیگر هیچیک از نقاط تصویر قابل حذف نباشد .
همانطور که مشاهده می شود الگوریتم فوق ، عملیات نازکسازی را با روشی کاملا ساده انجام می دهد حال تصویر حاصل آماده شناسائی می باشد .

[mzjahromi]

این الگوریتم جهت آشکار ساختن نقاط بحرانی مورد استفاده قرار می گیرد و به صورت زیر عمل می کند.
فرض کنید چهار جهت اصلی وجود دارد که عبارتند از بالا به پائین ، چپ به راست ، بالا چپ به پائین راست و بالا راست به پائین چپ ابتدا مشخص می کنیم که سه نقطه متوالی با کدامیک از الگوهای فوق تطابق دارد. حال اگر نقطه چهارم نیز در این مسیر قرار گیرد هیچگونه نقطه بحرانی وجود نخواهد داشت ولی در صورتیکه نقطه چهارم در مسیری متفاوت با مسیر قبلی قرار گیرد نقطه سوم به عنوان نقطه بحرانی علامتگذاری خواهد شد. در هر صورت عملیات فوق را با نقاط 4,3,2 ادامه می دهیم تا اینکه کلیه نقاط شناسائی شوند اما در صورتیکه سه نقطه انتخاب شده هیچکدام از مسیرهای فوق را نتواند تشکیل دهند باز هم نقطه وسط بحرانی خواند بود همچنین نقاط ابتدائی و انتهائی و نقاطی که در تقاطعها وجود دارند نیز بحرانی می باشند .
4-3) کاهش نقاط بحرانی
با استفاده از روش فوق تعدا زیادی از نقاط کنار هم به صورت نقاط بحرانی علامتگذاری می شوند بدین ترتیب در تشکیل گراف نقاط زیادی وجود خواهند داشت که نیازی به آنها نمی باشد و پیچیدگی گراف را هم بالا می برد. به همین دلیل سعی می شود که تا حد امکان نقاط بحرانی کاهش داده شوند و به حداقل تعداد ممکن برسند جهت دستیابی به این هدف درون تصویر جستجو کرده و به دنبال نقاط بحرانی کنار هم می گردیم. حال تنها نقطه ای را نگه می داریم که موقعیت آن از سایرین بحرانی تر باشد و بقیه نقاط بحرانی مجاور را به نقاط عادی تبدیل می کنیم.
عملیات فوق را در طی مراحل زیر انجام می دهیم .
1-در ابتدا بررسی می کنیم که آیا نقطه در حال بررسی از نقاط بحرانی است یا خیر در صورتیکه این نقطه از نقاط بحرانی باشد عملیات زیر را انجام می دهد.

if(GetBufPixel(i,j)=NcColor)then

      exit;

    Repeat

2- در بین نقاط اطراف نقطه مورد نظر جستجو می کند که آیا نقطه ای بحرانی تر از نقطه جاری وجود دارد یا خیر؟ در صورت وجود، عملیات را با آن نقطه انجام می دهد.

flag:=True;

     if(getBufpixel(i,j)=CColor)then

     Begin

      i1:=i;j1:=j;

if((getbufpixel(i,j+1)=CColor)And(crossing_Index(i  ,j+1,Road11)>crossing_Index(i1,j1,Road11)))then

      Begin

	j1:=j+1;

        i1:=i;

	flag:=False;

      End;



……





if((getbufpixel(i-1,j-1)=CColor)And(crossing_Index(i-1,j-1,Road11)>crossing_Index(i1,j1,Road11)))then

       Begin

	 i1:=i-1;j1:=j-1;

	flag:=False;

       End;

       i:=i1;j:=j1;

     End

   until flag;

   

3- و به دنبال آن عملیات کاهش نقاط بحرانی را با نقاط اطراف نقطه جاری ادامه می دهد تابع getfriend مشخص می کند که اطراف این نقطه چه نقاطی وجود دارند و متغیر Road مشخص می
کند قبلا چه مسیر هائی طی شده است و هم اکنون نباید تکرار شود .

while(GetFriend1(i,j,i1,j1,Road1))do

      Begin

         DecreaseCritical(i1,j1,Road1);

         Road:=Road and GetRoad(i-i1,j-j1);

         Road1:=Road;

      End;

   

4- پس از انجام عملیات بر روی نقاط اطراف نوبت به نقطه جاری می رسد و در صورتیکه اطراف این نقطه نقاطی بحرانی وجود داشته باشد این نقاط حذف خواهند شد تابع Round pixel مشخص می کند که در اطراف یک نقطه خاص چند نقطه رنگی وجود دارد.

if((getbufpixel(i,j+1)=CColor)And(RoundPixel2(i,j+  1,BackColor,255)<>1))then

         putpixel(i,j+1,NcColor);

…..

   

[mzjahromi]

همانطور که گفته شد نقاط بحرانی گرهها و ارتباطات بین آنها یالهای گراف را تشکیل می دهند. بنابراین برای یافتن گراف عملیات زیر انجام می دهیم .
1-یافتن گرههای گراف بدیهی است که هر نقطه بحرانی یک گره از گراف را تشکیل می دهد بنابراین کافی است نقاط بحرانی را یافته و موقعیت هر یک از آنها را به عنوان یک گره از گراف ثبت کنیم.

for j:=y1 to y2 do

    for i:=x1 to x2 do

     if(GetBufPixel(i,j)=CColor)then

      Begin

	G.SetInfo(index,i,j);

	index:=Index+1;

      End;

2- یافتن یالها : برای هر گره با توجه به نقاط اطراف آن یالهائی که به گره وارد شده یا از آن خارج می شوند را جستجو می کنیم بدین منظور از تابع Findedge استفاده شده است .

for k:=0 to index-1 do

  Begin

    G.GetInfo(k,i,j);

    Road:=255;Road1:=255;

    while(GetFriend1(i,j,i1,j1,Road))do

    Begin

	FindEdgs(i1,j1,k,Road,G);

	Road1:=Road1 And GetRoad(i-i1,j-j1);

	Road:=Road1;

    End

  End

2-1) findedge: این تابع که یک تابع بازگشتی است ، از یک نقطه شروع کرده و در یک مسیر مشخص آنقدر جلو می رود تا به یک نقطه بحرانی برسد سپس یال بین این نقطه و نقطه مبدا را علامتگذاری کرده و باز می گردد این عملیات طی مراحل زیر انحام می شود .
2-1-1) بررسی می شود که آیا نقطه بحرانی است یا خیر؟ واگر این نقطه یک نقطه بحرانی است و همان نقطه مبدا نیست ارتباط بین این گره و گره مبدا را برقرار می کنیم .

if(GetBufPixel(i,j)=CColor)then

   Begin

     indx:=G.GetIndex(i,j);

     if(indx<>index)then

	G.SetEdge(indx,index);

     FindEdgs:=indx;

     Exit;

   End;

2-1-2) همچنین در صورتیکه در اطراف نقطه جاری، نقطه ای بحرانی وجود داشته باشد، عملیات فوق را با آن انجام می دهیم.

if(GetFriend(i,j,i1,j1,CColor,Road))then

   Begin

     indx:=G.GetIndex(i1,j1);

     if(indx<>index)then

	G.SetEdge(indx,index);

     FindEdgs:=indx;

     Exit;

   End

2-1-3) و در انتها در صورتیکه نقطه جاری از نقاط بحرانی نباشد عملیات فوق را با نقاط اطراف آن انجام می دهیم و گره بازگردانده شده را به عنوان یکی از همسایه های گره جاری در نظر می گیریم .

else if(GetBufPixel(i,j)=NcColor)then

   Begin

     putpixel(i,j,BackColor);

     Road1:=Road;

     indx:=index;

     while(GetFriend1(i,j,i1,j1,Road))do

     Begin

	indx:=FindEdgs(i1,j1,index,Road{Road1&Road},G);

	Road1:=Road1 and GetRoad(i-i1,j-j1);

	Road:=Road1;

	if(indx<>index)then

	Begin

	  G.SetEdge(indx,index);

	  if(GetFriend1(i,j,i1,j1,Road))then

	    putpixel(i,j,NcColor);

	  FindEdgs:=indx;

          exit;

	End

     End;

     putpixel(i,j,NcColor);

     FindEdgs:=indx;

     Exit;

   End;

[mzjahromi]

با وجود اینکه نقاط بحرانی یافته شده، در یک مرحله کاسته می شوند، اما باز هم ممکن است نقاطی وجود داشته باشند که نیازی به آنها نیست. این مرحله از برنامه سعی در حذف گرههای اضافی گراف دارد این عملیات به عهده تابع DecreaseEdge می باشد این تابع یک زاویه را به عنوان آرگومان گرفته و کلیه خطوطی که زاویه بین آنها از این مقدار آستانه کمتر باشد را با هم ادغام می کند این عملیات به ترتیب زیر انجام می شود :
1-بررسی می شود که آیا یک گره از گراف قابل حذف شدن است یا خیر. تنها گرههائی قابل حذف شدن هستند که دو یال بیشتر نداشته باشند.

for i:=0 to v-1 do

      if(EdgeNum(i)=2)then

      Begin

2- هر دو یال متصل به این گره در نظر گرفته می شود و زاویه بین آن دو محاسبه می شود.

x1:=v-1;

	 for j:=0 to v-1 do

	  if(GetEdge(i,j) And (i<>j))then

          Begin

            x1:=j;

	    break;

          End;

         x2:=v-1;

	 for j:=x1+1 to v do

	   if(GetEdge(i,j) And (i<>j))then

           Begin

   	     x2:=j;

	     break;

           End;

	 j:=Degree(x[x1],y[x1],x[i],y[i],x[x2],y[x2]);

3- در صورتیکه این زاویه از مقدار آستانه کمتر باشد گره مذکور حذف خواهدشد.

	 if((j<DTelorance) And (j>-DTelorance))then

	 Begin

	   ReSetEdge(i,x1);

	   ReSetEdge(i,x2);

	   SetEdge(x1,x2);

	   flag:=True;

	 End

4- عملیات فوق را تا زمانیکه هیچ گره قابل حذفی وجود نداشته باشد تکرار می کنیم .

Until(not flag);

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

[M.GhanaatPisheh]

اصلا دوست ندارم با فرستادن پست تشکر اینجا رو بیخود شلوغ کنم.
ولی مقاله بسیار جالبی هست.
منتظر ادامه داستان هستم.

[sjj]

عالیه لطفا ادامه بدید

[ermia1384]

سلام:
این قسمت crossing index نامفهومهه

[mzjahromi]

از کدوم قسمت ؟ نازکسازی؟؟
کجاش نا مفهومه؟

[ermia1384]

از کدوم قسمت ؟ نازکسازی؟؟
کجاش نا مفهومه؟

بله.همون قسمت نازک سازی.
اولا من متوجه نشدم کدش کدومه. ثانیا در قسمت thinezs نفهمیدم "y "چیست.

[mzjahromi]

در اولین فرصت سورس کامل پیاده سازی نازکسازی رو خواهم گذاشت

[samir1987]

در اولین فرصت سورس کامل پیاده سازی نازکسازی رو خواهم گذاشت

با سلام :
لطفا در صورت امکان هرچه سریعتر راجع به قسمت نازک سازی توضیح بیشتری بفرمایید.
باتشکر.