به نام خداوند بخشنده مهربان

۱. چکیده

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

۲. مقدمه

در گذشته داده های ورودی رایانه ها به صورت متنی و عددی بود. با گذشت زمان و پیشرفت رایانه ها، استفاده از آن ها در زمینه های مختلف گسترش یافت. همزمان با گسترش این کاربردها، نیاز به داده های ورودی غیر متنی و عددی به ویژه داده های صوتی و تصویری حس گردید. بدین ترتیب فعالیت های مختلفی در بخش های گوناگون جهت پردازش چنین داده هایی توسط رایانه ها، آغاز گردید.
امروزه کاربرد های فراوان پردازش تصویر را در زمینه های مختلف شاهد هستیم. از جمله کاربرد های پردازش تصویر می توان به سرعت سنجی خودرو ها، تشخیص پلاک خودرو ها، تشخیص چهره و ... اشاره نمود.
در این پژوهش قصد داریم نمونه ای از کاربرد های پردازش تصویر را در حل جدول سودوکو به کار گیریم.
سودوکو به جدول اعدادی گفته می‌شود که امروزه یکی از سرگرمی های رایج در کشورهای مختلف جهان به شمار می‌آید.
این معمای عددی- منطقی نخستین بار توسط Howard Garns در قرن 18 اختراع گردید و پس از مدتی در ژاپن از آن رونمایی شد.
سودوکو مخفف یک عبارت ژاپنی (数字は独身に限る ) می باشد که به صورت SUUJI WA DOKUSHIN NI KAGIRU خوانده می شود. سودوکو در لغت به معنای "ارقام باید تنها باشند" می باشد.
امروزه جدول سودوکو در انواع مختلفی وجود دارد اما متداول ترین نوع آن یک جدول 81 خانه ای9 *9 می باشد که شامل 9 خانه ی3*3 می باشد. برخی از خانه های این جدول در ابتدا حاوی اعدادی از 1 تا 9 بوده و بقیه خانه های جدول خالی می باشند. برای پر کردن خانه دیگر جدول بایستی به نحوی عمل نماییم که سه قانون زیر رعایت گردند:
1- در هر سطر جدول، اعداد 1 الی 9 بدون تکرار قرار گیرند.
2- در هر ستون جدول، اعداد 1 الی 9 بدون تکرار قرار گیرند.
3- در هر ناحیه3*3جدول، اعداد 1 الی 9 بدون تکرار قرار گیرند.
وجود روابط فوق بین خانه های جدول سودوکو، سبب به کارگیری روابط منطقی در حل این جدول شده و آن را به یک سرگرمی و معمای لذت بخش تبدیل نموده است.
جداول سودوکو یکی از بخش های جدایی ناپذیر روزنامه های امروزی می باشند. اکثر مخاطبان این جداول پس از حل جدول بایستی تا روز بعد منتظر بمانند تا درستی جدول حل شده خود را بررسی نمایند.
در این پژوهش قصد داریم تا با استفاده از مبانی نظری که ارائه می گردد، برنامه ای برای تلفن های همراه توسعه دهیم تا بتواند تصویر جدول سودوکو را گرفته و جدول حل شده را به صورت خروجی ارائه دهد.
با توجه به این که تصویر ورودی به توسط دوربین گرفته می شود در نتیجه این تصویر در مقایسه با تصویر اسکن شده، دارای ضعف هایی می باشد.
چالش های اصلی که در این مسیر با آنها رو به رو هستیم عبارتند از:[3]
1 - کیفیت دوربین ها متفاوت است و برای یک صحنه مشخص، عکس هایی با کیفیت های متفاوت بدست می آید.
2- شرایط نوری محیط تغییر می کند.
3- زاویه عکس گرفته شده از تصویری به تصویر دیگر تغییر می کند.
4- صفحه روزنامه ها اغلب مسطح نمی باشد و در نتیجه تصویری غیر مسطح گرفته می شود.
5- فونت های متفاوت در روزنامه های مختلف به کار می رود.

۳. طرح کلی

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

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

در این بخش قصد داریم تا راه حل های ارائه شده در مقالات مختلف، برای هر یک از مراحل طرح کلی را مطرح و بررسی نماییم.

1. تبدیل به عکس سیاه و سفید:
تمامی برنامه های بصری رایانه ای جهت پردازش تصویر، ابتدا تصویر ورودی را تک رنگ می کنند. البته ممکن است در آینده روش هایی برای پردازش تصاویر به صورت رنگی نیز پیدا شود اما تمامی پردازش های تصویری کنونی مبتنی بر تک رنگ می باشند.[8]
در این مرحله ابتدا تصویر ورودی را برش می دهیم و اندازه آن را کوچکتر می کنیم. دلیل این برش نیز آن است که ممکن است تصویر ورودی یه همراه ناحیه های دیگری باشد که مرتبط با جدول سودوکو نمی باشد و تنها زمان پردازش را طولانی تر می کنند.[1]
پس از برش تصویر ورودی، فیلتر پایین گذر گاشن را بر روی آن اعمال می کنیم. با اعمال این فیلتر اجزایی از تصویر که دارای فرکانس بالا می باشند، هموار تر می شوند و همین امر سبب می گردد تا در مراحل بعد به ویژه تشخیص اعداد خطای کمتری داشته باشیم.[2]
حال تصویر فیلتر شده را به یک تصویر دودویی تبدیل می کنیم. روش های مختلفی برای این تبدیل وجود دارد. از جمله این روش ها، روش استفاده از آستانه سراسری و آستانه انطباقی می باشد.[8]
در روش آستانه سراسری یک حد آستانه به صورت سراسری برای کل تصویر استفاده می شود. با توجه به این که گستره شدت رنگی از 0 تا 255 می باشد، این آستانه 128=2/256 در نظر گرفته می شود. چنانچه شدت رنگی یک پیکسل در تصویر، بیشتر از این آستانه باشد، تبدیل به رنگ سفید می شود و در غیر این صورت تبدیل به رنگ سیاه می شود.
استفاده از حد آستانه سراسری برای کل تصویر اغلب نتایج مناسبی را نمی دهد. به عنوان مثال چنانچه سایه ای بر روی تصویر وجود داشته باشد، استفاده از آستانه سراسری سبب حذف جزئیات گشته و تشخیص اعداد را ناممکن می سازد.[1] [9]
برای رفع مشکل آستانه سراسری از روش آستانه انطباقی استفاده می کنیم. در روش آستانه انطباقی برای هر پیکسل یک آستانه به صورت محلی بدست می آید و با توجه به این آستانه تبدیل صورت می گیرد. ناحیه ای از تصویر که از روی آن این آستانه محاسبه می شود، 30% اندازه یک بلوک 1*1 از جدول در نظر گرفته می شود.[2]

2. حذف نویز های تصویر:
در این مرحله نویز های تصویر دودویی حاصل از مرحله قبل را از بین می بریم تا بتوانیم نتایج بهتری را در مراحل بعد بدست آوریم.

3. تعیین خطوط مرزی جدول:
برای تعیین خطوط مرزی جدول این فرض را در نظر می گیریم که بزرگترین جزء متصل در تصویر ورودی همان ناحیه مرزی جدول می باشد. در نظر داشتن این فرض در اکثر موارد نتایج درستی به دنبال داشته است البته در مواردی نیز موجب شکست شده است.[2]
روشی که برای تعیین خطوط مرزی استفاده می شود بدین صورت می باشد که ناحیه در برگرفته شده توسط هر یک از اجزا متصل را بدست می آوریم و با توجه فرض گفته شده، بزرگترین مقدار برای ناحیه ها همان ناحیه ای است که توسط خطوط مرزی در بر گرفته شده است. در نتیجه خطوط تشکیل دهنده این ناحیه همان خطوط مرزی می باشند.[1]
استفاده از روش فوق سبب می شود تا زاویه دار بودن تصویر باعث خطا در تشخیص خطوط مرزی نگردد.

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

5. تعیین خطوط داخلی جدول:
سوالی که در اینجا مطرح می گردد این است که چه نیازی به تعیین خطوط داخلی داریم؟ در پاسخ به این سوال بایستی به این نکته توجه داشته باشیم که خطوط داخلی اغلب در مرحله حذف نویز های تصویر از بین می روند، این در حالی است که ما برای تعیین مکان اعداد جدول به آن ها نیاز داریم. به همین دلیل بایستی در این مرحله این خطوط را به صورت مجازی دوباره ایجاد نماییم.[1]
روشی که در اینجا برای تعیین خطوط از آن استفاده می کنیم بدین صورت می باشد که ابتدا با استفاده از الگوریتم کنی لبه ها را مشخص می کنیم و پس از آن تکه خطوط را به وسیله تبدیل احتمال تکاملی حاق بر روی لبه های تشخیص داده شده، مشخص می کنیم. دلیل استفاده از تبدیل احتمالی به جای نوع استاندارد، آن است که تبدیل احتمالی توانایی تشخیص تکه ها را علاوه بر خطوط کامل دارا می باشد.
پس از آن که تکه ها مشخص گردید، با استفاده از تحلیل جزء متصل، تکه ها را خوشه بندی می نماییم و تنها بزرگترین خوشه ها را نگه می داریم. در انتها نیز تکه هایی که بر روی یک خط قرار می گیرند را به یکدیگر متصل می کنیم.[3]
مشکلی که در اینجا ممکن است با آن مواجه شویم آن است که تعداد خطوط تشخیص داده شده ممکن است بیش از تعداد واقعی باشد.
در این صورت از دو فیلتر زیر برای تشخیص خطوط واقعی استفاده می کنیم:
1- با توجه به این که خطوط واقعی جدول با یکدیگر موازی هستند، خطوطی که دارای زاویه ی متفاوت هستند را حذف می کنیم.
2- خطوطی که در فاصله دور تری نسبت به همسایه خود هستند را حذف می کنیم.

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

6. تعیین خانه ها:
در این مرحله از خطوطی که در مرحله قبل بدست آمدند استفاده می نماییم. برای تعیین خانه های جدول از اشتراک میان ناحیه میان خطوط استفاده می کنیم و اشتراکاتی که بسیار به هم نزدیک می باشند را به یکدیگر متصل می کنیم. در صورتی که این کار درست انجام شده باشد بایستی در این مرحله 100 ناحیه اشتراکی تشخیص داده شده باشد در غیر این صورت از الگوریتم تشخیص کانتور برای تشخیص بزرگترین کانتور تصویر استفاده می کنیم.[3]
چنانچه از روش دوم برای تعیین خطوط استفاده شود، در همان مرحله خانه های جدول بدست می آید.[1]
در انتها اعدادی به هر خانه نسبت داده می شود تا بتوانیم در مراحل بعد برای تعیین مکان اعداد جدول از آنها استفاده کنیم.

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

8. تعیین مقدار عدد:
روش های مختلفی برای تشخیص اعداد از روی تصاویر موجود می باشد. از جمله این روش ها می توان روش های SVM[11] ،K-NearestNeighbour[10] ، Template Matching و[Deep Belief Network [3 را نام برد.
تمامی الگوریتم های تشخیص دارای مراحل زیر می باشند:[8]
1- تعیین ویژگی ها
2- آموزش (مرحله یادگیری)
3- دسته بندی (اجرا تشخیص)
در مرحله تعیین ویژگی ها، ویژگی های متمایز کننده مشخص می شوند. به عنوان مثال برای عدد 1 ویژگی بلند بودن و لاغری در نظر گرفته می شود و برای عدد 8 این ویژگی که از دو دایره روی هم تشکیل شده است در نظر گرفته می شود. این مرحله یکی از دشوار ترین مراحل می باشد.[8]
در مرحله آموزش از یک مجموعه داده برای یادگیری سیستم استفاده می شود. با توجه به این که داده های مورد نظر ما عدد می باشند و تعداد آن ها برای یادگیری سیستم زیاد می باشد، برای کاهش حجم و افزایش سرعت یادگیری اندازه این مجموعه داده را کوچک می کنیم.
پس از تغییر اندازه، این مجموعه داده نرمال سازی شده و در یک آرایه استاتیک به صورت زیر ذخیره می شوند:

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

روش دیگری که از آن برای تعیین ویژگی اعداد استفاده می شود، بهره گیری از ویژگی های طولی و عرضی اعداد می باشد. روش کار به این صورت می باشد که ابتدا با استفاده از یک ضریب مقیاس تصویر ورودی را هم اندازه تصاویری که برای آموزش سیستم به کار برده شده است، می کنیم. سپس با در نظر گرفتن ارتفاع یکسان برای تمام اعداد، با استفاده از ویژگی های عرضی میان آنها تمایز قائل می شویم.[1] [8]

در مرحله دسته بندی نیز از روش k-nearest neighbor با K=1 استفاده می کنیم یعنی نزدیک ترین خانه را در تشخیص به کار می بریم.

9. تشکیل جدول و حل آن:
پس از آن که اعداد و مکان آنها مشخص گردید، آرایه ای از اعداد به صورت ورودی برای بخش حل جدول ارسال می شوند. در این آرایه برای خانه های خالی جدول عدد صفر را در نظر می گیریم.
در اینجا این نکته را یادآوری می نماییم که مکان اعداد از روی اعداد نسبت داده شده به خانه های جدول در مرحله تشخیص خانه ها بدست می آید.
حال به الگوریتم های موجود برای حل جدول سودوکو می پردازیم.
روش های مختلفی برای حل جدول ارائه شده اند که از آن جمله می توان به Brute force ، Backtracking ، Rule-based ، Boltzmann Machine Genetic Algorithm ، Dancing List اشاره نمود.
Brute force : در این روش همان طور که از نامش پیداست تمامی حالت ها را بررسی می کنیم. این روش با توجه به این که تمامی حالت ها را بررسی می کند، سرعت پایینی داشته و روش کارآمدی نمی باشد.
Backtracking: این روش پایه ای ترین روش حل سودوکو می باشد. این روشی نیز نوعی Brute force می باشد که اعداد مختلف را آزمایش می کند با این تفاوت که هنگامی که شکست می خورد، عقبگرد کرده و عدد دیگری را آزمایش می کند.[5]
Rule-based: این روش شامل تعدادی قاعده می باشد که بر اساس این قواعد اثبات می نماید که آیا عددی مشخص می تواند در خانه ای از جدول باشد یا خیر. این روش همان روشی است که انسان ها برای حل جدول سودوکو از آن استفاده می کنند. این روش یک روش اکتشافی می باشد و به همین دلیل نمی توان تمامی مسائل را با آن حل نمود. برای رفع این مشکل می توان از ترکیب اکتشاف و Brute force استفاده نمود. [5]
همان طور که در مقدمه گفته شد، تمرکز اصلی این پژوهش بر روی پردازش تصویر می باشد. از این رو برای کسب اطلاعات درباره روش Boltzmann Machine به مرجع [5] و Genetic Algorithm به مرجع [6] و Dancing List به مرجع [7] می توانید رجوع نمایید.

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

پس از تعیین مرکز خانه ها، اعداد حاصل از حل جدول را در خانه های خود قرار داده و نتیجه را بر روی تصویر اولیه نمایش می دهیم.

۵. آزمایش‌ها

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

۷. مراجع

[1] P. Simha, K. Suraj, and T. Ahobala, “Recognition of numbers and position using image processing techniques for solving sudoku puzzles,” in Advances in Engineering, Science and Management (ICAESM), 2012. IEEE, 2012
[2]Divya Sagar, Ujwal Adhav, Pruthvijadhav and Anupam Bhatt Under the guidance of Prof. Shiburaj Pappu "A synopsis report on smart sudokusolver using image processing" Department of Computer Engineering Rizvi 2013-2014
[3] Baptiste Wicht, Jean Hennebert "Camera-based Sudoku recognition with Deep Belief Network" Soft Computing and Pattern Recognition (SoCPaR), 2014 6th International Conference
[4] Yixin Wang "Sudoku Solver " , Stanford University
[5] Patrik Berggren, David Nilsson "A study of Sudoku solving algorithms" Bachelor’s Thesis at NADA,Supervisor: Alexander Baltatzis
[6] Timo Mantere and Janne Koljonen "Solving, Rating and Generating Sudoku Puzzles with GA" Evolutionary Computation, CEC 2007. IEEE Congress on 2007
[7] Mattias Harrysson, Hjalmar Laestander "Solving Sudoku efficiently with Dancing Links", Degree Project in Computer Science , Supervisor: Vahid Mosavat

+پیوند های مفید:
[8] http://www.codeproject.com/Articles/238114/Realtime-Webcam-Sudoku-Solver
[9] http://docs.opencv.org/master/d7/d4d/tutorial_py_thresholding.html#gsc.tab=0
[10] http://www.boute.ir/iust-ai-92/sudoku-solver
[11] http://www.boute.ir/iust-pr-93/handwritten-digit-classification