نویسه‌خوانی به عملیات تشخیص متن در عکس و تبدیل آن می‌باشد. در این پروژه از شما انتظار می‌رود تا متن انگلیسی را در تصاویر حاوی متون تایپ شده انگلیسی تشخیص دهید.

۱. مقدمه

مدتی پیش در ادارات و سازمان‌های اداری، تجاری مثل بانک‌ها تمام اسناد و مدارک بصورت دست‌نویس بود وبه صورت کاغذ بایگانی می‌شد، برای بایگانی آن اسناد و هم‌چنین نگه داری آن‌ها مکانی بزرگ مورد نیاز بود، حتی دستیابی به سند مورد نظر زمانبر بود. با پیشرفت تکنولوژی پس از مدتی تصمیم گرفته شد تا تمام آن اسناد بصورت متن‌های قابل ویرایش و قابل جستجو در رایانه‌ها ذخیره شوند، اما با این حجم عظیم اسناد، چگونه؟
نابینایان نیاز به کتاب‌هایی داشتند که یا صوتی باشد و یا به خط مخصوصشان نوشته شده باشد، اما با این تعداد زیاد کتاب‌ها، چگونه ؟
این‌گونه نیازها باعث شد تا مفهومی به نام OCR¹ معرفی شود، OCR به فرایند تبدیل اسناد تایپ شده، متون داخل تصاویر، دست‌نوشته‌ها و ... به متن قابل ویرایش و جستجو برای دستگاه می‌باشد.
امروزه مثال‌هایی این چنین که از OCR استفاده می‌شود را در اطرافمان زیاد می‌بینیم، از بارکد‌ خوان‌های فروشگاه، اسکنرهای بانک برای اسکن قبوض و چک‌ها، ... تا اپلیکیشن‌هایی چون QRCode خوان‌ها که در تلفن‌های هوشمند خود و اطرافیان به کرات مشاهده کرده‌ایم.

۱.۱. پیش پردازش

تصاویرمورد نظر ممکن است دارای مشکلاتی باشد که فرایند تشخیص متن را به خطا بیاندازد، برخی مشکلات و راه حل آن‌ها و پیش پردازش‌های دیگر عبارتند از:

• اصلاح زاویه‌ی تصاویر² : ممکن است تصویر ورودی زاویه مناسبی نداشته باشه،باید با روش‌هایی تصویر را چرخاند تا زاویه‌اش با خط افق صفر شود!

• حذف نویز موجود در تصاویر: ممکن است به دلیل قدیمی بودن، کیفیت پایین دوربین و دلایلی دیگر تصویر ورودی دارای مقداری نویز (نقاط سیاه یا رنگی اضافی در تصویر) باشد که باید در از بین بردن یا حداقل کاهش آن‌ها کوشید تا تشخیص اشتباهی نداشته باشیم.[1,2]

• سیاه و سفید کردن تصاویر: البته این مورد جزء مشکلات نمی‌باشد ولی اگر تصاویر رنگی بود، نیاز است که به دلیل تشخیص راحت تر و جدا کردن متن از پس زمینه‌ی تصویر از این کار استفاده شود(به عبارتی دیگر تضاد رنگی بین نوشته و پس‌زمینه به وجود بیاید). برای این کار، روش‌های گوناگونی از قبیل otsu، markov، global fixed و ... وجود دارد که بعداً برخی از روش‌هایش را توضیح خواهم داد.[1,2,3]

• حذف خطوط اضافی: برخی از نوشته‌ها دارای خطوط (بردارهایی) در اطرافشان یا زیر‌خط³ و ... هستند که جزء خود متن نیستند.[2]

• چسبیدگی یا جداشدن حروف: در برخی تصاویر ممکن است قسمتی از یک حرف جدا شده باشد و یا ممکن است چند حرف به‌هم چسبیده باشند، مانند تصویر زیر[2]
  

  

۱.۱.۱. روش‌های سیاه و سفید کردن تصاویر⁴

در این‌ قسمت چند مورد از روش‌های سیاه و سفید کردن تصاویر با هدف جدا کردن متن از پس‌زمینه اشاره می‌کنیم.
* در این‌جا هر رنگ پیکسل -براساس مقدار سیاه یا سفید بودن⁵- تصویر ورودی را x و هر پیکسل تصویر نهایی را b می‌نامیم.

• روش Global Fixed Threshold : در این روش که از ساده‌ترین روش‌هاست اگر x_i\ge 0.5 باشد b_i را یک می‌گذاریم، در غیر این صورت صفر می‌گذاریم(فرض بر این است که x_i بین صفر تا یک و b_i فقط یک یا صفر می‌توانند باشند).[3]

• روش Otsu Threshold : تقریبا همانند روش قبلی می‌باشد با این تفاوت که به جای مقدار 0.5 مقدار t را در‌نظر می‌گیریم، این مقدار باید به گونه‌ای
  انتخاب شود که به بهترین نتیجه منجر شود. اگر رنگ پیکسل‌ها را بر اساس مقدار سیاه یا سفید بودنشان مقدار‌دهی کنیم مقادیر این‌گونه می‌باشد که کلاس مورد نظر {G={0,1,…,L-1 می باشد و بر اساس t این به دو کلاس {0,1,…,t} و {t+1,t+2,…,L-1} تقسیم می‌شود که باید مقدار واریانس داخل کلاسی به حداقل و واریانس بین کلاسی به حداکثر برسد، یعنی اگر واریانس داخلی را به صورت زیر تعریف کنیم، باید t به گونه ای باشد که این واریانس به حداقل برسد .
  

  {\sigma_W}^2(t) = W_1(t){\sigma_1}^2(t) + W_2(t){\sigma_2}^2(t)
  
  که در این جا Wها احتمال دو کلاس مجزا شده توسط t می باشد و اگر واریانس بین کلاسی را به صورت زیر تعریف کنیم، باید مقدارش به حداکثر برسد.
  
  {\sigma_B}^2(t) = {\sigma}^2 - {\sigma_W}^2(t) = W_1(t)W_2(t) [\mu_1(t) - \mu_2(t) ]^2
  
  و داریم[4]
  
  W_1(t) = {\Sigma}_0^t p_i(t)
  
  
  \mu_1(t) = {\Sigma}_0^t p_i(t) x_i(t)

• روش Markov Model : در این روش علاوه بر پیکسل فعلی، پیکسل‌های قبلی هم مورد بررسی قرار میگیرد، در این‌جا بطور مثال پیکسل قبلی یعنی پیکسل‌های بالا و سمت چپ پیکسل مورد نظر هستند که تصمیم برای این که پیکسل کنونی سیاه است یا سفید به پیکسل‌های قبلی وابسته است، علاوه بر برتری این روش نسبت به روش‌های دیگر به خاطر تشخیص بهتر انحنا و زواید حروف، معایبی هم دارد بطور مثال در تصویر شماره 3 در نمونه شماره 2 می‌بینید که پیکسل اضافه‌تری هم سیاه شده است.[3]
  

  

  
  

  

۱.۲. پردازش

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

۱.۳. پس پردازش

پس از این که متن را تشخیص دادیم، ممکن است برخی از حروف به درستی تشخیص داده نشده باشند یا حتی ممکن است خود دست‌نوشته غلط املایی داشته باشد، پس برای بالا بردن دقت نتیجه‌ی کار می‌توان از واژه‌نامه‌ها⁶ استفاده کرد که برای زبان‌های برنامه نویسی مختلف ارائه شده اند. واژه‌نامه‌ها می‌توانند عمومی یا تخصصی برای زمینه خاصی مثلا ورزشی، مهندسی، ... باشند.[1,7]

۲. کارهای مرتبط

مواردی که در مقدمه ذکر شد، کارهایی است که برای بهبود نتایج انجام داده می‌شود. برای تشخیص و تبدیل متن از تصاویر، روش های متفاوتی وجود دارد که برخی از آن‌ها شامل چند مورد زیر می‌باشد:

۲.۱. الگوریتم‌ها

• تطبیق الگو⁷ به روش شیار-قطاع : در این روش به تولید ماتریس مخصوص هر حرف می‌پردازیم و سپس ماتریس را با ماتریس‌های نمونه‌هایی که از قبل داشته‌ایم و مقدار آن را می‌دانیم مقایسه می‌کنیم و سپس تصمیم می‌گیریم. پس از طی نمودن مراحل پیش پردازش‌ها برای نرمال‌سازی تصویر مورد نظر، باید ابتدا متن را به صورت سطر به سطر جدا کرده و در هر سطر هر یک از حروف را مورد پردازش قرار دهیم و پس از اتمام پردازش بر روی یک حرف، سراغ حروف بعدی رفته و در انتها از در کنار هم گذاشتن اطلاعات بدست آمده، متن را تشکیل می‌دهیم. پس از این که تصویر را محدود به حروف مورد نظر کردیم، تصویر حرف کنونی را به صورت صفر و یک درون یک ماتریس n \times n ذخیره می‌کنیم(به‌طور مثال ماتریس 15 \times 15)، بدین صورت که به‌جای قسمت‌های سیاه رنگ 1 گذاشته و قسمت‌های سفید رنگ را صفر می‌گذاریم.
  در ادامه ماتریس به دست آمده را به 5 شیار⁸ و 8 قطاع⁹ تقسیم می‌کنیم، برای این کار ابتدا درایه‌ی مرکزی ماتریس را یافته و سپس دورترین درایه از نظر فاصله نسبت به درایه‌ی مرکزی می‌یابیم، با تقسیم مقدار به دست آمده-شعاع-به تعداد شیارها می‌توان شیارهای مختلف ماتریس را به دست آورد.
  

  

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

• تطبیق الگو به روش نزدیک‌ترین همسایگی¹⁰ : در این روش هم اساس کار بر تقسیم‌بندی تصویر و تبدیل آن به ماتریس متناظر می‌باشد با این تفاوت که یک مرحله‌ی پیش پردازش اضافی دارد و روش تقسیم‌بندی و دسته‌بندی کردن¹¹ از روش قبل متفاوت است.
  ابتدا به توضیح مختصری در ارتباط با الگوریتم نزدیک‌ترین همسایگی(K-NN) می‌پردازم. هدف این الگوریتم دسته‌بندی ورودی‌ها بر اساس دسته‌بندی‌های داده‌هایی از قبل دسته‌بندی شده‌اند، می‌باشد. اگر D را مجموعه داده هایی در نظر بگیریم که قبلا دسته‌بندی شده و x را داده‌ای که قصد دسته‌بندی کردنشان را داریم، که x = ( x\prime , y\prime ) که در اینجا x\prime داده‌ی مورد بررسی می‌باشد و y\prime هم نام دسته‌اش. ابتدا به محاسبه‌ی فاصله‌ی بین داده‌ی مورد بررسی و کل داده‌های پیشین می‌پردازیم که به تشکیل آرایه‌ی k عضوی از نزدیک‌ترین دسته‌ها به نام D_Z منجر می‌شود. حال، با در نظر گرفتن رأی اکثریت¹² اقدام به انتخاب دسته‌ی مورد نظر می‌کنیم، که رأی اکثریت را می‌توان از روش زیر به دست آورد.
  

  y' = _v^{argmax} \Sigma _{(x_i,y_i) \in D_z} I( v = x_i )
  
  *در این‌جا i ، منظور i امین نزدیک‌ترین همسایه می‌باشد و v هم نام دسته‌ می‌باشد و هم‌چنین تابع I هم تابعی است که در صورت درستی عبارت داخلش 1 برمی‌گرداند و در غیر این‌صورت صفر برمی‌گرداند.
  تصویر زیر مثالی از این الگوریتم می‌باشد، بدین صورت که اگر دو دسته‌ی مربع‌های آبی و دسته‌ی دایره‌های سبز در نظر بگیریم در صورتی که K=3 باشد، سه تا از نزدیک‌ترین‌ها دارای دو مربع آبی و یک دایره‌ی سبز می‌باشد که دسته‌ی مربع‌های آبی را برمی‌گزیند.
  

  

  
  در ادامه پس ازاین که توسط روش خاص خود به نازک سازی¹³ حروف (پیش پردازش) -که در [5] توضیح بیشتری داده شده- پرداخت، نوبت به توضیح چگونگی تقسیم‌بندی و تشکیل ماتریس متناظر می‌رسد. اگر تصویر ورودی را X بگیریم و پیکسل‌های پس‌زمینه را یک بگذاریم و پیکسل‌های پیش زمینه را صفر بگذاریم، ابتدا x و y بیشینه و کمینه را به‌دست آورده تا تصویر را محدود به حرف مورد نظر کنیم. سپس از تصویر به دست آمده به تشکیل ماتریس X_E می‌پردازیم.
  سپس به تقسیم‌بندی ماتریس بدست آمده به خانه‌های هم اندازه می‌پردازیم که خانه‌های به دست آمده C_i نام‌گذاری می‌کنیم، اگر در هر کدام از این خانه‌ها نسبت مقادیر یک به مقادیر صفر را بدست بیاوریم، به ازای هر خانه داریم، P_i .
  
  P_i = \frac {n_w}{n_B}
  
  اگر نسبت‌های بدست آمده را در یک آرایه به نام R_X بگذاریم، حال آرایه‌ای داریم که مشخصه‌ی هر حرف می‌باشد، که هر کدام را می‌توان به نام حروف مورد نظر نام گذاری کرد مثلا آرایه‌ی A،B،C، ... .
  از این پس، پس از دریافت ورودی به ساخت ماتریس آن مطابق آن‌چه در بالا ذکر شد، پرداخته و سپس با استفاده از الگوریتم نزدیک‌ترین همسایگی اقدام به دسته‌بندی آن می‌کنیم.البته فاصله را بر اساس فرمول اقلیدس می‌توان به دست آورد، به طوری که X_S ماتریس داده مورد بررسی و X_T داده‌هایی که قبلا دسته‌بندی شده‌اند و Q همان مقدار P برای داده‌ی مورد بررسی می‌باشد.
  
  Distance_{Euclidean}(X_{T1} , X_{S1}) = D_1 = \sqrt{\Sigma_{j=1}^N (P_{1,j} - Q_{1,j})^2}
  
  در پیاده‌سازی این روش از نرم‌افزار متلب استفاده شده و مقدار K=5 در نظر گرفته شده که در آزمایش‌های مختلف مطابق تصویر شماره 7 به تقریبا 95 درصد تشخیص درست دست یافته‌اند.[5]
  

  

  
  

  

۲.۲. ابزارهای موجود

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

  

  
  سپس از نقاط مختلف برش را انجام می‌دهد تا به بهترین حالت دست یابد. بعد از این، نوبت دسته‌بندی می‌باشد، در Tesseract دسته‌بندی‌ها بر اساس شکل چندضلعی‌ها و خطوط ایجاده شده‌ی اطراف حروف می‌باشد و پس از مقایسه با داده‌هایی که قبلا دسته‌بندی شده‌اند با روشی مشابه K-NN دسته‌ی متناسب را برمی‌گزیند. تفاوت Tesseract با ابزار و روش‌های دیگر نحوه‌ی دسته‌بندی آن می‌باشد که فونت های مختلف را می‌تواند شناسایی کند و ویژگی‌های دیگر آن، به استفاده از واژه‌نامه‌ها به عنوان پس پردازش می‌توان اشاره کرد.[7]

• کتابخانه OpenCV : این کتابخانه علاوه بر تشخیص متن، کارهایی چون تشخیص چهره، تشخیص حرکت در دوربین و فیلم، خواندن پلاک خودرو و کارهای زیادی که مربوط به پردازش تصویر می‌شود را انجام می‌دهد و ادعا شده که دارای 2500 الگوریتم بهینه برای کارهای مختلفش می‌باشد. این کتابخانه برای تشخیص متن از الگوریتم‌هایی چون K-NN و SVM¹⁴ استفاده می‌کند و برای زبان‌های برنامه نویسی سی، سی پلاس پلاس، پایتون، جاوا و متلب نوشته شده است.

• ابزارهای آنلاین : وبسایت‌های مختلفی وجود دارند که هر کدام از آن‌ها با الگوریتم خودشان می‌توانند تصاویری را که ما بارگذاری می‌کنیم به متن تبدیل کنند، وبسایت‌هایی چون onlineocr ، free-ocr ، newocr و ... ، البته خیلی از آن‌ها از الگوریتم‌های پیچیده‌ای استفاده نکرده‌اند که به همین دلیل گاهی اوقات جواب نادرست می‌دهند. تصویر زیر نمونه‌ی تست شده می‌باشد که هر سه وبسایت جواب متفاوتی داده‌اند و فقط یکی از آن‌ها کاملا درست بوده است.
  

  

۳. آزمایش‌ها

۴. کارهای آینده

۵. مراجع

[1] http://en.wikipedia.org/wiki/Optical_character_recognition
[2] http://www.nicomsoft.com/optical-character-recognition-ocr-how-it-works
[3] Maya R. Gupta, Nathaniel P. Jacobson, Eric K. Garcia "OCR binarization and image pre-processing for searching
historical documents"
[4] EUGEN-DUMITRU TĂUTU and FLORIN LEON "OPTICAL CHARACTER RECOGNITION SYSTEM
USING SUPPORT VECTOR MACHINES"
[5] Mohammad Imrul Jubair, Prianka Banik "A Simplified Method for Handwritten Character Recognition from Document Image"
[6] Faisal Mohammad, Jyoti Anarase, Milan Shingote, Pratik Ghanwat "Optical Character Recognition Implementation
Using Pattern Matching"
[7] Ray Smith "An Overview of the Tesseract OCR Engine"