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

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