פרוייקט זה מציג אלגוריתם לזהוי מספרים מתוך מפת סיביות.
רעיון זה מיושם למספרים אשר נוצרו בעזרת מחשב אך ניתן להרחבה (אולי) לזהיוי סימנים אחרים (אותיות וסימנים מיוחדים). הרעיון ניתן למימוש גם לאפיון וזיהוי מספרים בכתב יד.
זיהוי מספרים בעזרת מחשב הנו חלק מתחום רחב יותר הקרוי OCR- Optical character recognition.
המטרה בתחום זה הנה להמיר מידע הנמצא בתמונה למידע הניתן לעריכה בעזרת מחשב. תחום זה, בדומה לכל פיתוח טכנולוגי, התחיל בממסד הבטחוני.לאחר מלחמת העולם השניה הסוכנות לביטחון לאומי של ארה"ב - הNSA ,פיתחה תוכנה לתירגום מסמכים מודפסים לפורמט מחשב. מאז התפתח התחום לתוכנות המתרגמות הדפסות מכל פונט, תרגום של כתב יד ולאחרונה ישנם נסיונות לתרגום של כתב מחובר. הקשיים, מלבד הזהוי עצמו, הם ברעש בתמונה או
הביטוי תרגום מופיע בהקשר זה במובן של העברת מידע המיוצג ע"י פיקסלים למידע המיוצג ע"י קוד ASCII. השימוש במונח תירגום מדגיש פן חשוב בפעולת ההמרה.
באפן תיאורטי ניתן לתרגם משפה אחת לשניה אך ורק בעזרת מילון (אם השפה היא פשוטה), לא תמיד יש צורך בהבנה מעמיקה של השפה.
מכאן פתוחה הדרך לחשוב בדרכים יצירתיות המפשטות את התהליך "ההבנה" של הסימנים ותרגומם.
נתאר כמה דרכים המשמשות לזהוי סימנים:

1. שיטות סטטיסטיות: 
   אפיון סיפרה ע"י כמות הצבע שהיא דורשת ביחס לשטח אותו היא תופסת. 
   אפיון סיפרה ע"י יחס הרוחב/גובה שלה, ע"י היסטוגרמה של התפלגות הפיקסלים בהטלה מסויימת וכד'.
   המעניין הוא כי בדרכים אלו איננו באמת "מבינים" את הסימן אותו אנו רוצים לתרגם אך אנו יודעים על מאפיין הנשאר קבוע, למטרת זהוי יתכן וזה מספיק. 
   
   
2. רשת נוירונים:
   מדמה פעילות של נוירונים במוח. דרך תשדורות ופונקציות סף "לומדת" תבניות.

הבעיה העיקרית של רשתות נוירונים היא הצורך בהתאמה של פיקסל לפיקסל לתבנית. הבעיה של יחסי גובה/רוחב היא למצוא את הכיון של הספרה. התפלגות ביון ההטלה צריכה לדעת את כיון ההטלה וכו'. אנו רצינו שיטה אשר לא תהיה תלויה בגודל או בכיון של הסיפרה. אולי במידת מה גם מאפשרת להתמודד עם כיוץ או הרחבה של הספרה.

השיטה לזהוי:

בגישה זו אנו נבנה מילון של הספרות ע"י מאפינים אשר נשמרים בעת סיבוב והגדלה של המספר. לאחר שנבנה את המילון נשתמש בו להתאמה לניתוח ספרה כלשהיא.
התאור של המספר יקרא "חתימה" והוא נבנה כך: מחפשים את המשיקים לסיפרה אשר נוגעים בה בשתי נקודות (או יותר, אם כי לרוב לא מתקיים מצב כזה).
בנקודות אלו נתיחס לסיפרה כחוט רציף ונשאל את עצמינו האם אנו משיקים לו בקצה (חיתוך אחד), באפן פשוט (שני חיתוכים) או במקום אחר (לדוגמא: הצטלבות- 4 חיתוכים).
הנה דוגמא לניתוח:



הוקטור המתאר את הספרה מכיל את מס' המשיקים ולאחריו רשימה של דרגות החיתוכים לכל משיק (הרישום הוא לפי כיון השעון, לכל משיק).
השיטה דורשת יצירה של מסד נתונים קטן של וקטורים המתארים ספרות משוגים שונים. ישנה ספרות ספציפיות אשר להם צורות שונות (לפי אפיון זה) בעיקר 7, 1,4.
הנה לדוגמא הספרה 4 בכמה גרסאות:



הנה מילון שלם לפונט אחד המיצג סוג אחד של ספרות (יצוין שלא צריך לדעת כל פונט אלא סוגים של פונטים)

אלגוריתם הזהוי:

כרגע הנחות המוצא הן:
    1. אין רעש, אנו מקבלים את הסיפרה במפת סביות (אין חשיבות למיקום).
    2. האלגוריתם מבחין בין ספרות שונות ומזהה ספרות שוות (בגדלים והטיות שונות)  אך לא בין ספרות לסימנים אחרים (דוגמא בהמשך).
        מכאן באה הנחה שלפנינו ספרה ולא סימן אחר.

זהוי ספרה מוצג בתרשים הבא:


צעד א':  מציאת משיקים דו-שיקיים
אנו מתחילים בנקודה הנמצאת על הספרה מצידה החיצוני. לא קשה למצוא נקודה זו. זו הנקודה הראשונה של הספרה בה פוגשים במעבר מלמעלה למטה על המטריצהץ אם רוצים ביעילות אפשר לחפש בשיטת החציה על אורך המטריצה. בציור רואים כי מתבצעת סריקה של כל הישרים המחברים את הנקודה הנוכחית והגבולות של מטרצת התמונה. אם מהמקום הנוכחי אנו פגשים קצת מספר והשאר רקע כנראה שעוד לא מצאנו משיק בשתי נקודות. אנו נתקדם על הקו "המשיק" (זהו לא ממש משיק מכיון שהוא קצת חותך את הספרה מצדה החיצוני, זאת כדי לקדם את הנקודה הסורקת את הספרה). אם הגענו לשוליים (בשביל יעילות אפשר לעצור בשולים המנימליים - לאחר crop). אנו צריכים להמשיך לסרוק בכיון השעון את הסיפרה. כאשר מצאנו מסלול של משיק בו "יצאנו", בילינו ברקע ו"נכנסנו" חזרה לספרה מצאנו משיק בשתי נקודות.
כל הכבוד לנו - את זה חיפשנו.

צעד ב':  קביעת דרגת החיתוכים
לאחר שסיימנו למצוא את כל המשיקים לשתייםת עלינו לבנות את העיגולים החותכים כפי המתואר בהתחלה על המספר 3.
מעיגולים אלו קל לקבוע את דרגת החיתוך - ספירת הכניסות (יציאות) לתוך (מתוך) פיקסלים של הספרהת על מסלול העיגול.

צעד ג':   השוואה עם ה DB.
כאן החוכמה היא למצוא דרך להשואה שתתן קרוב טוב אפילו אם יש שגיאה בחיתוך או שחסר קו.
מהסתכלות במילון הנ"ל ומקרים אחרים נראה כי המספרים הבעיתיים הם 1,4,7 לכן כאשר אנו נשווה ונקבל מרחק מתוצאה ידועה (אין התאמה מלאה) נבדוק האם ישר הרבה (3-4) קוים בספרה אותה אנו רוצים לזהות ? אם כן נעדיף מדד זה. אם בספרה שלנו יש מעט קוים נעדיף התאמה של וקטורי החיתוכים. חשוב לציין כי אפשר לסובב את הוקטורים בתוך ספרה העיקר לשמור על סדר החיתוכים בתוך כל משיק. לדוגמא:




יעילות:
שיפור חד ליעילות יתבצע בעזרת זיהוי כיון הספרה עצמה ע"י אלגוריתם המשרטט עיגול המכיל את כל רוחב קו הספרה ומוצא את אמצע רוחב הקו ע"י אמצע הקשת החותכת את הספרה (ע"י המעבר מרקע לאובייקט וחזרה). הבעיה בשיטה זו תהיה אולי במצב של רעש. (ראה בסיום רעיונות להתמודדות עם רעש). בציור רואים זאת ע"י המעבר מיד לקו הירוק לעומת הליכה סזיפית לאורך כל הקוים אשר בצבע טורכיז (לאורך שפת המטריצה).

בעיות:

לכאורה במילון שלנו ישנן שתי בעיות:



נראה כאילו אין דרך להבדיל בין 6-9 ו 1-7.
האמת שיש כאן טעות אופטית. עפ"י הנחת היסוד שלנו אנו לא מתחשבים בכיון. לפי זה 6 ו 9 הם באמת זהים ולא רק למחשב. אם אנו לא מגדירים כיון, 6 הוא סיבוב של 9 (לפחות בפונט הזת אם כי זה ברבים אחרים) ולהיפך.

פתרון נהדר לבעיית הזהוי של 6,9 :

לאחר שאמרנו שהבעיה לא קיימת תחת ההנחות שאין כיון. נאמר שקל מאד להבחין בין 6 ל 9. 
האחד נמצא משמאל למשיק והשני מימין.
הבחנה זו מתרגמת לבדיקה של ה Y של נקודת החיתוך מדרגה 1.
אם היא מעל קו אמצע הספרה (עכשיו בהנחה שהכיון חשוב) אזי לפנינו 6 אחרת לפנינו 9.

הבדלה בין 1 ל- 7.

כפי שאפשר לראות בפונטים מסוימים תחת ההנחה שאין כיון קשה גם לנולהבדיל בין 1 ל- 7.
נכון שיש מקרים בהם דרך זו לא תבדיל למרות שאנו נצליח להבדיל. לעומת זאת ישנם הרבה פונטים אחרים, קצת שונים שבהם יש כבר הבדל בין 7 ל- 1.
הנה שתי הדוגמאות:

רואים שבליטות אלו משנות את כל ה"חתימה". מסתבר שהן נמצאות בצורה זו או אחרת בפונטים רבים.

FALSE ALARM:
כפי שהצהרנו, האלגוריתם שלנו מבחין בין ספרות אך לא בין ספרות לתוים אחרים הנה דוגמא לכך:

תוצאות:

הנה כמה פלטים של התוכנית לזהוי המשיקים הדו-שיקיים:


כל המשיקים הם כמו המילון. לדוגמא ל- 0 אין משיקים.

מסקנות:

הרעיון עובד.
עיקר הדגש הנו על על מציאת קוטר העיגול האמור לחתוך את הספרה.
ההנחה היא שהספרות הן שלמות (כלפי חוץ) ופחות או יותר שומרות על פורמט דומה.

ארכיון:

•     Full Project Report
•     Power Point slide shows
•     Code    

      עיבוד סיפרתי של תמונות – או"פ
http://en.wikipedia.org/wiki/Optical_character_recognition
פרוייקטים משנה שעברה: hand write recognition , זיהו לוחות רישוי, זיהוי בשיטת PCA