זיהוי ממוחשב של כתב יד

מתוך ויקיפדיה, האנציקלופדיה החופשית
(הופנה מהדף זיהוי כתב)
קפיצה אל: ניווט, חיפוש
Gnome-colors-edit-find-replace.svg יש לשכתב ערך זה. הסיבה לכך היא: פרטים טפלים, דרושה עריכה וויקיזציה מקיפה, נראה כי מועתק מעיתון.
אתם מוזמנים לסייע ולתקן את הבעיות, אך אנא אל תורידו את ההודעה כל עוד לא תוקן הדף. אם אתם סבורים כי אין בדף בעיה, ניתן לציין זאת בדף השיחה.

זיהוי כתב הוא טכנולוגיה המאפשרת למחשב לזהות תווים שנכתבו בכתב יד אנושי ולתרגמם לתווים דיגיטאליים. במחשבי כף היד של חברת פאלם תכונה זו ידועה בשם גרפיטי.

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

הטכנולוגיה קשה ליישום בשל העובדה שבני אדם כותבים בצורות שונות מאוד, והתוכנה לזיהוי כתב היד נדרשת למצוא מאפיינים משותפים לאותן אותיות הנכתבות בידי בני אדם שונים.

שיטות לזיהוי כתב:

  • התאמת הקו הדו ממדי לרצוי (נרמול) ומציאת הקרוב
  • זיהוי סמנטי של אותיות (עיגול, קו, גזרה ומיקומם)
  • מציאת מאפיינים כמו ב-OCR

מבוא[עריכת קוד מקור | עריכה]

שימוש בכתב יד[עריכת קוד מקור | עריכה]

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

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

בנוסף, חומר יקר ועתיק עדיין טמון בספרים עתיקים הכתובים בכתב יד ולא בדפוס.

הצורך בזיהוי[עריכת קוד מקור | עריכה]

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

יישום[עריכת קוד מקור | עריכה]

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

זיהוי כתב יד מתחלק לשתי טכנולוגיות עיקריות:

  1. זיהוי מקוון
  2. זיהוי לא מקוון

זיהוי מקוון[עריכת קוד מקור | עריכה]

היסטוריית זיהוי הכתב המקוון[עריכת קוד מקור | עריכה]

זיהוי כתב יד מקוון החל במחשבי כף היד הראשונים. תחילה הוציאה חברת אפל מחשב כף יד עם יכולת זיהוי כתב מקוונת, שיצרה רושם ראשוני רע, וגם הגרסה הבאה והמשופרת מאוד שלה, שכללה תיקון שגיאות כתיב, לא הצליחה לתקן את הרושם הראשוני[דרוש מקור]. מאוחר יותר במערכת ההפעלה PenPoint (שפעלה במחשבי לוח של IBM ושל NCR), נכללה צורת זיהוי שהועברה גם לחלונות של מיקרוסופט, אך גם תוכנות אלו לא הצליחו[דרוש מקור]. ההצלחה היחסית הראשונה הייתה של מחשבי פאלם, עם תכנת ה- Graffiti שלהם, שאפיינה סדרת משיכות עט לכל תו בהתאם למשתמש, דבר שהקטין את השגיאות, אך הגדיל את עקומת הלמידה של המכשיר. צורה מוצלחת יותר, לדעתם רבים, קיימת בגרסה של מיקרוסופט לזיהוי כתב יד במחשבים ניידים בעלי לוח כתיבה ועט המצוידים בחלונות XP, חלונות ויסטה, ו- חלונות 7, כאשר השינוי המרכזי שהפך את התוכנה לטובה יותר, הוא שהיא אינה מנסה ללמוד את הצורה בה המשתמש כותב, אלא משווה את הכתיבה לבסיס נתונים המכיל בתוכו אלפי צורות כתיבה של כל אות בנפרד. צורה זו, אינה דומה לגרסה המותקנת במחשבי כף היד המבוססים על חלונות. למרות אלו, חוסר של רווחים שווים, כתיבה מחוץ לקו, כתיבה בכתב מחובר ואותיות בעלות גדלים לא שווים מבלבלים את התוכנה.

דרך זיהוי הכתב המקוון[עריכת קוד מקור | עריכה]

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

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

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

פיתוח אלגוריתמים ושיטות שונות לזיהוי כתב יד הוא נושא מאוד מרכזי ומושקע בו מאמץ מחקרי ופיתוחי רב. קיימים גם ארגונים שונים לקידום הנושא, המקיימים כנסים מסוגים שונים כמו ה-International Workshop on Frontiers in Handwriting Recognition הנערך מדי שנה.

זיהוי לא מקוון[עריכת קוד מקור | עריכה]

זיהוי לא מקוון של תמונה שלמה המכילה בתוכה טקסט, מורכב מניתוח התמונה וזיהוי המקטעים המכילים בתוכם מילים, ואחר כך המרתם לאותיות הניתנות לעריכה.

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

המחקרים נעשים על ידי ארגונים כמו IAPR (The International Association for Pattern Recognition – האיגוד הבינ"ל לזיהוי תבניות), IWFHR (The International Workshop for Handwriting Recognition – האיגוד הבינ"ל לזיהוי כתב), IEEE ועוד.

צורת הזיהוי[עריכת קוד מקור | עריכה]

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

  1. פירוק לחלקים, או (Dissection):
    1. זיהוי מקטעים של כתב (פסקאות). לעתים מתבצע גם זיהוי פונקציונאלי, כלומר זיהוי של סוג הפיסקה – כותרת, תקציר וכו'. האלגוריתמים לביצוע המשימה משתמשים במיקום הכתב יחסית לרקע הלבן, ומיישמים קונבולוציית מסיכה, חתימה פרקטלית, התמרת wavelet ועוד. זיהוי זה דומה יותר לזיהוי מרקם ופחות לזיהוי תמונה ממשית, כיוון שכל אות היא שונה והמרקם אינו חוזר על עצמו בצורה קבועה.
    2. זיהוי שורות וכיוונן. כך למשל שורה שנכתבה בצורה עקומה תיושר תחילה. הדבר קורה פעמים רבות בכתב יד שנכתב על גבי דף ללא סימון שורות. הכתיבה "עולה" או "יורדת". לשם כך משתמשים באלגוריתמי יישור. (ייתכן ויש ליישר גם כל אות בנפרד, כיוון שישנם אנשים הכותבים לעתים אותיות בצורה מוטה, בהתאם לתנוחת היד שלהם. על נושא זה נרחיב בהמשך). כמובן, יש למצוא תחילה את הקו עליו הייתה אמורה להיכתב השורה עצמה. זיהוי נכון של קו השורה העקום חיוני גם כדי להבחין בין סימנים זהים, למשל האות העברית ו והספרה 1, או האות הלועזית g והספרה 9 (שלא לדבר על ס' בכתב יד או האות o, הזהים בכתיבתם לספרה 0). זיהוי כיוון השורה המדויק נעשה בעזרת אלגוריתמים שונים המשתמשים בשיטות של קורלציה, זיהוי אותיות שכנות, טרנספורמציות שונות ועוד. קיימים מאמרים שלמים על כל שיטה לזיהוי ותיקון יישור של שורה.
    3. הפרדת השורות למילים, על פי הרווחים ביניהן (הגדולים יחסית לאלו שבין האותיות במקרה שהכתב אינו כתב מחובר). כאן קיימת כמובן בעיה בזיהוי הרווחים המתאימים – על התכנה ללמוד את ההפרש בין הרווחים מהסוגים השונים. הבעיה תחמיר אם הכותב רגיל לכתוב בלי הפרשים גדולים בין סוגי הרווחים.
    4. הפרדת המילים לאותיות, לפי רווחים בין האותיות. בדרך כלל הדבר נעשה על ידי העברת חלון בגודל משתנה ומציאת מיקום האות על התמונה, ולא על ידי חיפוש הרווחים עצמם.
    5. אם הכתב מחובר, לא ניתן למצוא את האותיות לפי רווחים ביניהן, ולכן נדרשת חשיבה נוספת. קיימים אלגוריתמים מורכבים שמנסים, לכן, להבין את המילה השלמה, או חלקי מילים נפוצים (עם למידה מתמשכת של המחשב והוספת חלקי מילים וצירופי אותיות בכתב מחובר כל הזמן). אלגוריתמים אלו נדרשים ליכולת חישוב גבוהה. שיטה אחרת היא למצוא את הקו העובר בין האותיות. בדרך כלל מזהים אותו על ידי חישוב הקו האנכי או המשופע מעט החותך כמה שפחות את הקווים השחורים, ושהוא הקצר ביותר שאינו מכיל שינויי כיוון רבים מדי.
  2. נרמול האותיות. יש לשנות את גודלן של האותיות לגודל שניתן יהיה להשוות אותו לבסיס הנתונים, של צורת האותיות או חלוקתן למקטעים, הקיים בתכנה. נרמול של מילים שלמות נעשה בעיקר לגובה ולא לרוחב, כדי לשמור על הרווחים בין המילים. חלק זה אינו הכרחי כשמשתמשים בסעיף 5 בהתמרה שאינה רגישה לגודל.
  3. ניקוי והחלקת גבולות המילים. ביצוע החלקה משפר את צורת האות, מנקה את האות מרעשים ומגביר מאוד את הסיכוי לזיהוי נכון. זה השלב המקביל ל"השלמת אזורים": שיפור צורת התמונה כדי להימנע ככל האפשר מטעויות הנובעות מרעשים (יש לנו מספיק בעיות גם עם תמונה חלקה, כפי שנראה בהמשך).
  4. לעתים מבוצע סוג של דחיסה, כדי לעבד את האותיות יותר בקלות. דחיסה זו חייבת לשמור על צורת האותיות, ולכן היא לא כוללת יותר מהעברת מסנן סף, שיסנן רעשים וישאיר תמונה בת שני ביט בלבד לכל פיקסל. לפעמים הסף נקבע, באלגוריתמים מתקדמים יותר, לכל מילה או אות בפני עצמן, בהתאם לרקע ולערכים הממוצעים באות. בנוסף קיים אלגוריתם ל"הרזיה" של האות, או thinning, וכך אנו נפטרים ממידע עודף על עובי הקו – מידע שאינו קובע לגבי צורת האות (אלא בשפות ספורות בלבד).
  5. לעתים מבוצע גם ייצוג מחדש של האותיות. האות מועברת התמרה כלשהי, אם כדי לדחוס כנ"ל ואם כדי לנצל תכונות מסוימות של ההתמרה. למשל, ניתן לבצע התמרת פורייה על האותיות בדף, וכך למנוע בעיות של מיקום האות בתמונה – התמרת פורייה היא אינווריינטית למיקום התמונה, אם אנחנו מבטלים את ייצוג הפאזה כמובן. משתמשים גם בהתמרת wavelet ובמומנטים, שהם חסינים להזזות, הטיות והגדלות.
    סוג נוסף של ייצוג מחדש הוא ייצוג סטטיסטי. בשיטה זו מחשבים את ההיסטוגרמה של מיקום צמתים וקווים בצורות שונות באותיות, צורת הגבולות, פיצולים משולשים ועוד. מחושבת גם השכיחות של מעבר קווים מחוץ לגבול מסוים שנקבע מראש או שיפועים מיוחדים של האות. שכיחויות אלו נרשמות בוקטורים או מטריצות שעליהן ניתן לבצע פעולות הקשורות לניתוח האות.
    הייצוג האחרון הוא ייצוג לפי טופולוגיה. תחילה מפעילים אלגוריתם הדקה (Thinning) ואז סופרים את הצמתים, העיקולים, הפיצולים ומודדים את המיקום היחסי שלהם, דבר היוצר אפיון ייחודי לכל אות. משתמשים גם ביחסי אורך – רוחב, שינוי בעיקול האות, יציאה מחוץ לשורה ועוד. ייצוג טופולוגיה נעשה גם בשיטה הנפוצה של קידוד שרשרת – זוהי בעצם חלוקה של האות לשרשרת של וקטורים בסיסיים, באורכים קבועים ובכיוונים שונים, לפי שושנת הרוחות. כך אות הופכת לשרשרת של מספרים, שכל אחד מציין וקטור אחר.
    השיטות כיום עובדות ברובן על תמונות בינאריות, אך הכרה בחשיבות ההפרש בגווני האפור הנובע מלחצים שונים של היד בשעת הכתיבה מביאה לפיתוח מואץ של אלגוריתמים לניתוח של כתב היד בצורתו המקורית.
  6. זיהוי האותיות. נעשה על ידי כמה שיטות, שרובן קשורות אחת בשנייה ומהוות למעשה תת-שיטה אחת של השנייה:
    1. השוואה לבסיס נתונים מוכן של אותיות. הבעיה היא, כמובן, שקשה מאוד להציג בסיס נתונים המכיל בתוכו את כל האפשרויות לכתיבה של כל אות. כל נקודה מיותרת שאינה צפויה להופיע באות, עלולה לבלבל את התכנה; ולהיפך, נקודות שהן כן קריטיות (כמו הקו הקטן המהווה את ההבדל בין ה-ת' ל-ח' בכתב יד) עלולות להיזנח. מלבד זאת, שיטה זו רגישה מאוד לרעשים, המשנים את התמונה שהמחשב אמור לקבל. זיהוי בעזרת בסיס נתונים נקרא גם זיהוי פרמטרי.
      קיימות גם שיטות המעוותות את צורת האות בכמה אפשרויות, כדי לנסות להתאים אותה לבסיס נתונים קיים. יש להיזהר כמובן מעיוות יתר, שהרי עם מספיק עיוות נוכל להגיע לכל אות אחרת שהיא... לכן מגדירים מראש את כללי העיוות בצורה שתצמצם את שאר האפשרויות, ולא תגרום לאות אחת להפוך לשנייה.
      יש לציין כי קיימות שיטות המנתחות את המילה השלמה. שיטות אלו עוקפות את הבעיה של חלוקת המילה לאותיות, משימה קשה במיוחד ומבטיחה טעויות בכתב יד, אך הן תלויות בגודלו של אוצר המילים המוגבל בהכרח של בסיס הנתונים, ודורשות יכולת חישוב גבוהה, במיוחד במילים ארוכות. לשיטות אלו יש בדרך כלל אחוזי הצלחה נמוכים מאחוזי ההצלחה של השיטות המנתחות אות – אות.
      השוואת תבניות מול השוואה ישירה: השוואת תבניות היא סוג של השוואה לפי וקטורים ופיקסלים הקיימים באות. השוואה מלאה היא השוואה שבה אנחנו משווים כל פיקסל ופיקסל בתמונת המקור לפיקסלים המקבילים להם בתמונת היעד (או לחלק גדול מהם).
      כאשר משתמשים בשיטות סטטיסטיות, אנחנו מחפשים תכונות של האות או המילה המופיעים בהתפלגות אחידה, נורמאלית או גיאוסיאנית. נדרשת כמובן תכונה שיש מספיק מופעים ממנה (אחרת קשה להסתמך עליה) וכן תכונות המייצגות את האות כמה שיותר.
    2. ניתוח טופולוגי: ניתוח האורכים, הכיוונים והצמתים המחברים את הקווים מהם עשויות האותיות. בשל העובדה שכתב יד מכיל בתוכו קווים מעוגלים רבים, נדרשת תשומת לב מיוחדת לניתוח של קווים כאלה, במיוחד בשל העובדה שגם קווים שאמורים להיות ישרים בכתב יד נכתבים לפעמים בצורה מעוגלת מעט או שהם מוטים באלכסון, הכל לפי נטיית ידו של הכותב. טופולוגיות נוספות קשורות במיקום הקווים, כלומר אם הקווים נמצאים מעל או מתחת לשורה וכו'. לעתים משתמשים ב"עץ החלטות" הבוחן ומשווה כל וקטור ווקטור באות או פיקסלים נבחרים.
    3. השוואה עצבית. שיטה זו מנסה לדמות את הצורה בה קוראת העין האנושית. העין שלנו מגובה בכמות עצומה של אינטליגנציה, ולכן מספיק לה לראות כמה צורות שונות של האות כדי לזהות אותה בצורות חדשות. במוח שלנו התאים הקשורים לזיהוי האות בצורה אחת יקושרו בסינפסה נוספת (קשר עצבי נוסף) לתאים המזהים את האות בצורה השנייה. תכנה הפועלת על בסיס של רשתות עצביות פועלת בשיטה המזכירה את השיטה הזו. למעשה, ברשת עצבית קיימים צמתים רבים, שבכל אחד מהם קיימת פונקציה מסוימת הבודקת את הנתון אותו היא קבלה, בתוספת מידע כלשהו מהצומת הקודמת. הנתון עובר מצומת לצומת עד להגעה לצומת שתסיק מסקנה כלשהי.
      את התכנה "מלמדים" (מראש וגם תוך כדי פעולה שלה) איך נראית כל אות באלפי דרכים שונות, והיא תיצור קשרים הדומים לקשרים עצביים בין הצורות הדומות של אותה אות. כאשר התכנה תפגוש צורה חדשה של האות היא תשווה אותה לכל הצורות שיש בידה (כלומר, תעביר אותה דרך כל הצמתים לבדיקה של מה הם מכירים) ותקבע מה האותיות הדומות ביותר, ובנוסף, תוסיף את האות החדשה לאוסף של האותיות הקודמות בקשר חלש. ככל שהתכנה תראה יותר אותיות דומות לכך, הקשרים שלה לאותן אותיות יתחזקו, כמו שקורה ברשתות של הנוירונים במוח. אגב, אם אות זוהתה בטעות, לא ניתן לגשת לקרבי התכנה ולתקן זאת. יש להראות לתכנה אותיות דומות לה הכתובות בצורה שדומה מעט יותר לאות האמיתית, וכך לחזק את הקשר לאות האמיתית. כלומר, הגישה החישובית היא מקבילית, מאחר שהאות תעבור דרך כל הצמתים, אך במשקלים שונים הניתנים לה על ידי כל צומת. ניתן להשוות זאת לווקטור העובר דרך כל הצמתים והוא משתנה לאחר מעבר בכל "עמודה" של הצמתים.
      מורכבות הרשת תלויה, כמובן, במספר הצמתים הנמצאים בה, היוצרים מספר רב של עמודות. קיימים מחקרים המשתמשים גם ברשתות תלת ממדיות, והם טוענים לעקומת למידה מהירה וכן לתוצאות טובות יותר. מחקרים נוספים הראו כי למעשה, למרות השוני בגישה, רשתות עצביות פועלות כמו שיטות לזיהוי מרקמים (מבחינת פעולתו הסופית של המחשב).
    4. שיטת HMM: מהנפוצות ביותר. למעשה זהו אלגוריתם הפועל בשיטת מכונת מצבים. כל מצב במכונה מפעיל פונקציה אחרת על האות, המילה או המקטע, ובעזרת תוצאת הפונקציה אנחנו מופנים למצב הבא, עד להגעה למצב המייצג אות באחוזי ביטחון מסוימים. כל מודל בכל שפה מתבסס על תכונות שונות, המתאימות לאופי הכתיבה בשפה. הבעיה המרכזית בכתיבת אלגוריתם כזה היא החלטה על התכונות עליהן הוא יתבסס. בדרך כלל השיטה משתמשת בכמה צורות של תווים, המפורקים לייצוג וקטורי או מטריציוני מסוים (הכולל לעתים גם את גודלו ומיקומו של כל וקטור).
      במחקרים מסוימים, שבהם נתגלה כי שיטת HMM לפעמים "קשוחה מדי" עם האותיות והיא אינה מזהה תווים שאינם דומים מאוד לדוגמאות שיש בידה, מחברים כמה מצבים ביחד ליצירת מצבים חדשים וכך מוסיפים גמישות מסוימת לשיטה. ניתוחים שנערכו מגלים כי אכן משתפרים בהרבה סיכויי ההצלחה של זיהוי התו. לא ניתן לחבר יותר מעשרים דוגמאות של תווים מבלי להגביר מאוד את כוח החישוב הנדרש, אך בדרך כלל לא צריך יותר מעשרה כדי לקבל תוצאות טובות מאוד (מעל 95%).
      לימוד התכנה לזהות תווים בצורה הטובה ביותר כולל בחירה של קבוצת דוגמאות מסוימת, המייצגת את התו בצורה הטובה ביותר. דוגמאות אלו ישמשו ליצירת הפונקציות בהם נשתמש בכל מצב.
    5. שימוש בלוגיקה מעורפלת. אלגוריתמים רבים משתמשים בשיטות לוגיקה מעורפלת, שבה נותנים לכל סימן הסתברות שהוא אות מסוימת. תכונות מסוימות באותיות נבדקות בעזרת אינטגרלים מעורפלים (כמו Choquet Fuzzy Integral), במחקרים מסוגים שונים.
  7. באלגוריתמים שאין להם שכבת זיהוי של מילה שלמה (כלומר, הם אינם בודקים את המילה הסופית), האות בעלת הציון הגבוה ביותר נשמרת. באלגוריתמים שיש להם שכבה כזו, אזי לאחר שהוחלט על מספר קטן של אפשרויות לכל אות, האפשרויות נשמרות וממשיכים לאות הבאה.
  8. באלגוריתמים בעלי שכבת מילים בלבד: הרכבה מחדש של המילים האפשריות מכל צירוף אותיות ובדיקת התכנות של כל מילה, לפי מילון. אם אכן המילה מופיעה במילון כמילה אפשרית, אזי היא תקבל ציון גבוה, אחרת תקבל ציון נמוך. המילה בעלת הציון הגבוה ביותר מבחינת התאמה היא זו שתבחר. לעתים משתמשים גם בניתוח סטטיסטי של צמדי אותיות במקום מילון – משתמשים בידע הנרחב של השכיחות למציאת צמדי אותיות בשפה ולפי זה מחליטים. כך נמנעים מהאפשרות להבין לא נכון מילה שאינה מופיעה במילון. ידע רב נוסף המבוסס על דקדוק ותחבירי משפט קיים בכל שפה, וגם בו אפשר להשתמש כדי לוודא זיהוי נכון; למשל, האות נ' לא תופיע בסוף מילה, והאות ף' לא תופיע בתחילתה או באמצעה. השימוש נעשה בכל הרמות – תו, מילה, משפט ופסקה.
  9. אלגוריתם טוב חייב לזהות גם סימנים שאינם אותיות, כמו סימנים מתמטיים, צורות גאומטריות, חיצים ומחברים כלליים וכו'. עליו לדעת להפריד בין קו תחתון, הבא לציין השלמת מילה (כמו בטפסים) לבין מקף, שבה לציין סמיכות בין מילים, וזאת בהתחשב בעובדה שכל ההבדל ביניהם הוא המיקום בשורה: הקו התחתון נמצא בגובה של חצי אות מתחת למקף. אם האלגוריתם אינו מזהה אותם, הוא עלול לפרש אותם בטעות כאותיות. יש לציין כי קיימים כיום אלגוריתמים בהם מזוהים גם התווים, ובצורה טובה יחסית.
  10. הצגת האות. האות תרשם בקובץ תוצאה או שתוצג כבר על המסך. מאחר שאין אלגוריתמים שאחוז השגיאות שלהם הוא אפס אחוז, נדרשת עבודה של בן אדם כדי לתקן את התוצאה.

בסיסי נתונים מוכרים[עריכת קוד מקור | עריכה]

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

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

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

דרך לבחירת שיטה לזיהוי כתב יד[עריכת קוד מקור | עריכה]

כחלק מעבודת הגמר לקורס כתבתי קריטריונים לא מחייבים לבחירת הדרך לזיהוי כתב יד. מאחר שכפי שראינו, קיימות דרכים רבות למימוש אלגוריתם לזיהוי כתב יד, נדרשת דרך כלשהי לבחור ביניהן. יש לקבוע קריטריונים גם למפתח, שרוצה לבחור אלגוריתם יעיל שיביא לתוצאות הטובות ביותר בזמן הקצר ביותר, בהתאם לכוח החישוב הנתון, וגם למשתמש, שרוצה לדעת איזו מערכת קיימת לקנות. זיהוי כתב יד – בחירת שיטה למפתח
מפתח הרוצה לבחור שיטה בה הוא ישתמש לזיהוי כתב יד, חייב לקבוע קודם כל את תכונות הזיהוי הכלליות:
1. המשאבים הנתונים בידו: עוצמת מחשוב (מקום, מהירות וזיכרון).
2. אופי בסיס הנתונים: האם התכנה תלמד את כתב היד של המשתמש או שתהייה כללית.
3. דרך ההפעלה: מקוונת או לא.
4. אופי ניתוח הטקסט: מלמטה למעלה (אותיות > מילים) או ההיפך.
5. צורת השפה: כתב מחובר או לא, צורות האותיות.
6. זמן הפיתוח: כמה זמן מוכן המפתח להשקיע (בשנות אדם) כדי לפתח את האלגוריתם.
7. מספר השפות: כמה שפות מתוכננות לעבוד בעזרת אותו אלגוריתם.
נפרט כל אחד מהנושאים:
1. משאבים: אם עצמת המחשוב גבוהה מאוד (הכוונה למחשב שולחני ומעלה), ניתן יהיה להשתמש ברשתות עצביות המבוססות על צמתים רבים, כך שהן יכולות להיעזר בבסיס נתונים רחב מאוד ובעצמת חישוב מסובכת. אם עצמת החישוב נמוכה, אפשר יהיה להתפשר על בסיס נתונים קטן יותר ועל אלגוריתם המבוסס על ניתוח הצורה.
2. אופי בסיס הנתונים: כדי להשיג אחוזי הצלחה גבוהים (במיוחד במכשירים בעלי משאבים מועטים) כדאי להשתמש בתכנה שתלמד את כתב היד של המשתמש. אם בסיס הנתונים של התכנה הוא מוכוון משתמש, גם אלגוריתם פשוט יחסית יוכל לפענח את הכתב בקלות יחסית. לעומת זאת, אם משתמשים בבסיס נתונים מוכן מראש, נוכל אמנם להגיע למשתמשים רבים במהירות, אך נדרש לבסיס נתונים גדול ולמשאבים גדולים כדי להגיע לאחוזי הצלחה גבוהים. ככל שהתכנה תתאים ליותר אנשים, היא תצטרך אלגוריתם חזק יותר (למשל, להגדיל את מספר הצמתים באלגוריתם HMM, או, אם האלגוריתם שלנו הוא אלגוריתם השוואה פשוט, להגדיל את מספר האפשרויות להגמשת ההשוואה).
3. דרך ההפעלה: כאן אנחנו צריכים להחליט אם דרך ההפעלה תהיה מקוונת או לא. אם ההפעלה מקוונת, אנחנו צריכים בעצם לפענח כל אות מיד עם כתיבתה. למעשה, זיהוי כתב יד מקוון שבו אנחנו רושמים כל אות בנפרד אינו מסובך – הזמן שלוקח לנו לכתוב גדול מזה שלוקח לרוב האלגוריתמים לפענח אות אחת (0.3 שניות במחשב כף יד, נכון להיום). עם זאת, מפתחים רבים כיום רוצים לפענח מילה שלמה בבת אחת, כך שיוכלו להפעיל גם בדיקות דקדוקיות מסוימות (או אפילו תחביריות). אמנם טרם ראיתי זאת במפורש, אבל אני מניח שכבר כותבים אלגוריתמים המפענחים אות – אות, אולם עושים בדיקות מהירות אחורה של כל המילה ומוודאים שהתכנה לא כתבה שטות כלשהי.
לזיהוי כתב יד בצורה מקוונת אפשרות להשתמש לא רק באות המוגמרת, אלא גם בצורת הכתיבה עצמה. כלומר, אנחנו יכולים לדעת איך המשתמש כתב כל קו – מימין לשמאל, מלמטה למעלה, הפעיל לחץ חזק יותר על האזור הזה של האות וכו' (הפעלת לחץ חזק יותר על אזור מסוים בקו פירושה שהקו כאן יותר חשוב מהמשכו, שנכתב רק כדי לצאת ידי חובה. למשל, סוף הקו התחתון של "ך" (כ' סופית) לא חייבת להיגמר בנקודה מסוימת). יכולת זו יכולה לחולל פלאים באחוזי הזיהוי הנכון אם משתמשים בה בתבונה, ובלבד שמשתמשים בה בצורה נבונה. נראה שהצורה הטובה ביותר להשתמש ביכולת זו היא בתוכנות הלומדות את אופי הכתיבה של כל משתמש.
אין לשכוח כי תכנה המשתמשת בקריאה כזו דורשת חומרה מיוחדת, המסוגלת לקלוט את הכתיבה בצורה מקוונת; חומרה כזו קיימת ונפוצה כבר, ולמפתח נותר אך ורק להשתמש בנתונים שבידו (וכמובן ללמוד איך משתמשים בחומרה, בהנחה והוא לא רוצה לפתח אותה בעצמו על ידי תכנות מיקרו בקרים או אלטרות).
4. אופי ניתוח הטקסט: אם אנחנו מפענחים מילים שלמות, הרי שבסיס הנתונים צריך להיות עצום בגודלו ואמור להכיל את כל המילים בשפה על הטיותיהן, אלא אם כן זהו מנגנון זיהוי כתב יד ייעודי לתפקיד מסוים. בסיס נתונים בגודל כזה רצוי מאוד לרכוש ולא לפתח בעצמנו, אלא אם יש לנו צוות שלם של קלדנים. בנוסף, הוא ידרוש עצמת חישוב גדולה שתצליח לזהות מילה גם כאשר היא כתובה בכמה דרכים שונות. במילים אחרות, אלא אם כן יש לנו מחשב טוב מאוד והרבה זמן לפענוח המילה, כדאי לבנות אלגוריתם המבוסס על זיהוי אותיות ולא מילים.
5. צורת השפה: שפה בעלת כתב מחובר תעדיף אולי לזהות את המילה השלמה (או חלקי מילים נפוצים) ואילו שפה שבה אין כתב מחובר תעדיף לזהות כל אות בנפרד. שפה, המורכבת מתווים מסובכים הדומים זה לזה, כמו השפות האסיאתיות, נדרשת לאלגוריתם המייצג את האות מחדש בצורה שבה מאפייני כל אות ואות יגיעו לכדי מיצוי מקסימלי של ההבדלים. מציאת האלגוריתם המתאים דורשת מחקר מעמיק של אופי השפה.
6. זמן הפיתוח: פיתוח של אלגוריתם המבוסס על לימוד המשתמש, שבו העבודה כוללת השואה די פשוטה לבסיס הנתונים הנבנה, ייקח פחות זמן מאחד המבוסס על בסיס נתונים רחב. בנוסף, אלגוריתם מתמטי הכולל התמרה מתקדמת מסובך יותר לפיתוח מאשר אחד המכיל פירוק לוקטורים (אם כי ייתכן בהחלט שהעיבוד הנוסף יהיה מסובך אף יותר).
7. מספר השפות: אם התכנה תצטרך לעבוד עם יותר משפה אחת, כדאי מאוד למפתח לעבוד על אלגוריתם המפענח את האותיות ולא את המילים. הפענוח יהיה תואם לצורות שניתן יהיה להזין למחשב, כלומר, רצוי אלגוריתם בצורת רשת עצבית עם דחיסה לפי צורה ופירוק לוקטורים ולא דחיסה לפי דקדוק. כך יהיה קל יותר להוסיף שפות עתידיות.

זיהוי כתב יד – בחירת שיטה למשתמש[עריכת קוד מקור | עריכה]

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

ראו גם[עריכת קוד מקור | עריכה]