תכנות וזיהוי/אלגורתמים סטטיסטיים לזיהוי

קובץ טקסט בו נשמרות התכונות אחרי שנלמדו מבסיס הנתונים המורכב מתמונות

יש כמה שלבים בריצת התוכנית בממשק עם המשתמש:

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

בשלב הלימוד התוכנית עוברת על קובץ מפת הסיביות

המכיל את בסיס הנתונים של התמונות.

ובודקת במה שונה תמונה שמייצגת עצם, מתמונה המייצגת עצם אחר.

היא יוצרת קובץ טקסט בו לכל זוג עצמים שונים יש שלישיית מספרים :

( מספר התכונה , הציון עבור העצם , הציון עבור העצם המושווה)

כך נראה קובץ התכונות עבור 6 עצמים.

לכל עצם יש 10 שורות :

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

לשם קריאוּת הקוד בקובץ יש כאן כמה תוספות:

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

0    0    0    0    0    0
-1  101    9  473  101 1292
0    5    5    0    5    6
0    7    3    3    7    2
-1  177  198 2109  176  638
0    0    3    3    0    3
0    2    5    0    2    0
-1  349  634  102  349  979
0    0    5    5    0    3
0    2    3    7    2    0

1    1    1    1    1    1
101   -1   11 2109  808  638
7    0    5    3    5    3
5    0    3    0    3    0
177   -1   47   95 1299 2150
2    0    2    3    4    3
0    0    0    5    6    0
349   -1  351  560 1456 2536
2    0    2    5    2    3
0    0    0    3    0    0

2    2    2    2    2    2
9   11   -1  846    3  939
3    3    0    0    0    3
5    5    0    3    2    0
198   47   -1 2109   18 2109
5    0    0    3    3    3
3    2    0    0    5    0
634  351   -1    2  252 2449
3    0    0    0    2    3
5    2    0    2    4    0

3    3    3    3    3    3
473 2109  846   -1 2241  473
3    0    3    0    0    3
0    3    0    0    3    0
2150   95 2150   -1   53 1020
0    5    0    0    5    3
3    3    3    0    3    0
101  560    2   -1  452 2449
7    3    2    0    8    3
5    5    0    0    6    0

4    4    4    4    4    4
101  808    3 2241   -1  638
7    3    2    3    0    3
5    5    0    0    0    0
176 1299   18   53   -1  979
2    6    5    3    0    3
0    4    3    5    0    0
349 1456  252  452   -1 2492
2    0    4    6    0    3
0    2    2    8    0    0

5    5    5    5    5    5
1292  638  939  473  638   -1
2    0    0    0    0    0
6    3    3    3    3    0
981 2109 2109 1020  979   -1
0    0    0    0    0    0
3    3    3    3    3    0
2150 2536 2449 2449 2492   -1
0    0    0    0    0    0
3    3    3    3    3    0

בסיס הנתונים כטבלה של תמונות

לכל עצם לא מספיקה תמונה אחת, כי יכולות להימצא תכונות מכשילות:

תכונות המבדילות בין כל העצמים לעצם בתמונה הזאת, אבל אם היו מנסים

לזהות תמונה שונה (מופע אחר) של אותו עצם , בעזרת התכונות שנלמדו

מאותה תמונה לא היו מצליחים לזהות את העצם.

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

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

אם מוצאים מופע שונה מאד מהמופעים האחרים( שבגללו יהיה קשה למחשב למצוא תכונה ,

בה כל המופעים של העצם שונים ממופעי עצם אחר), מוסיפים לתמונת בסיס הנתונים שורה

של מופעי העצם הדומים למופע המיוחד , וזוכרים שיש לנו שתי שורות לאותו עצם:

1. שורה של 10 המופעים הרגילים של העצם.
2. שורה של מופעים הדומים למופע מיוחד.

אלגוריתם למציאת תכונות טובות

התוכנה מנסה למצוא תכונות בהן :

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

האלגוריתם

לשם מציאת תכונה טובה בשלבי הלימוד והזיהוי :

1. שלב ראשון התוכנית דוגמת למערך דו ממדי(מטריצה), מכל תמונה 16 נקודות לרוחב התמונה ו - 16 נקודות לאורכה , יחד 256 נקודות: $256=16^{2}$
2. הופכת את צבעי הנקודות לשחור לבן על פי סקלה (המשתמש בוחר אחד מהמספרים בין 0 ל - 7 המשמש גבול בהירות).

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

למה לדגום תמונה ?

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

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

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

נכון - אבל התוכנית נכתבה בעיקרון לתמונת מפת סיביות בחלונות 98, ושם לא היה אפשר למתוח תמונות מפת סיביות כל כך בקלות

כמו בגרסאות מתקדמות של חלונות.

איך דוגמים תמונה ?

דגימת נקודה מתמונה

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

נגדיר משתנים לדגימת תמונה X וקבלת תמונה Y , כאשר נקודה המסומנת ב- A

הנמצאת בתוך התמונה,סומנת על ידי ערכי קואורדינטות הרוחב ( Width )

והגובה ( Hight ) שלה ביחס לתמונה כך: $A_{\mathrm {Width,Hight} }$

נקודה ב :	מספר נקודות	מיקום הנקודה	הסבר
רוחב התמונה הנדגמת	N	n	אפשרות ערכי רוחב למשתנה n נעים בין 0 ל - N
אורך התמונה הנדגמת	M	m	תחום ערכי אורך למשתנה m הם בין 0 ל - M
רוחב התמונה המתקבלת	P	p	אפשרות ערכי רוחב למשתנה p נעים בין 0 ל - P
אורך התמונה המתקבלת	Q	q	תחום ערכי אורך למשתנה q הם בין 0 ל - Q

בשימוש בחישוב על פי יחס רוחב ואורך בין התמונות X ו- Y מתקבל:

הנקודה $Y_{\mathrm {p,q} }$בתמונה המתקבלת היא הנקודה $X_{\mathrm {{\frac {P\times p}{N}},{\frac {Q\times q}{M}}} }$ בתמונה הנדגמת.

צריך לקרוא את זה כך : הנקודה ווי ( פי, קיו) בתמונה המתקבלת,

היא הנקודה אקס (פי גדול כפול פי קטן חלקי אן גדול, קיו גדול כפול קיו קטן חלקי אם גדול).

נראה כאילו אם יוצרים שבר נשארת שארית , איך מוצאים נקודה על פי מספר לא שלם ?

לא נשארת שארית כי החלוקה במספרים שלמים.

אם החלוקה במספרים שלמים, אם P יהיה קטן מ - N , לא משנה באיזה p התוצאה תוכפל, בסופו של דבר התוצאה תהיה 0 !

לכן בנוסחה קודם מכפילים את p ב - P ורק אחר כך מחלקים ב - N .

היינו חושבים שלא יכול להיות מקרה ש - P קטן מ - N , כי הדגימה לא יכולה להיות קטנה מהמקור , זה לא נכון , כי נניח

שאות מצוירת במחשב בעזרת 100 נקודות : 10 לרוחב ו - 10 לאורך , חייבים לזהות אותה ולכן חייבים לטעון אותה בתוכנה

במערך שהגדרנו שגודלו 16 על 16 נקודות .

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

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

אבל בכל זאת התוכנה מצליחה להפעיל את הנוסחה בעזרת GetPixel מתמונות שנשמרו בתיקייה.

הפיכת תמונה צבעונית לתמונה עם 8 גווני אפור

בפרקים הקודמים כתוב איך לפרק צבע נקודה לשלשה מרכיבים : (אדום ירוק וכחול)

רעיון איך להפוך צבע של נקודה ל - 8 גווני אפור נובע מהטבלה :

טקסט הכותרת	אדום	ירוק	כחול	תוצאה
הערך הגבוה ביותר	255	255	255	לבן
הערך הנמוך ביותר	0	0	0	שחור

הטבלה מרמזת שבהירות הצבע עומדת ביחס ישר לממוצע 3 המרכיבים ,

אם נסמן את סכום (sum) שלושת המרכיבים ( מרכיב = Component) כך :

$sum=\sum _{i=1}^{3}{Component_{i}}$

ולכן בהירות נקודה על פי סולם של 8 גווני אפור היא :

${\frac {8}{3\times {255}}}\times {\sum _{i=1}^{3}{Component_{i}}}$

שזה שווה לסכום המרכיבים כפול 0.010457 .

בעיית הרעשים

קודם התוכנה הופכת את צבעי התמונה ל - 8 גווני אפור . כשהתוכנה מנסה לזהות אותיות בתמונה היא הופכת את התמונה לשני גוונים :

כפתורים למציאת גבול הבהירות

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

אבל זה יוצר בהרבה מקרים כישלון בזיהוי (לאלגוריתם לא מדויק כזה קוראים כלל אצבע).

כי נניח שבתמונה יש נקודה אחת בצבע שחור , והאותיות כתובות בצבע אפור עם בהירות ממוצעת ,

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

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

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

למה שיטת באכ"ך כל כך טובה

3 חיצים חותכים 2 גרסאות שונות של האות 'א'

שיטת באכ"ך לזיהוי כתב מוגדרת בפרקים הקודמים, בהמשך הראה את יתרונותיה ,

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

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

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

בתמונה משמאל יש שתי גרסאות של האות 'א' בכתב , נניח שמהראשונה המחשב לומד מה היא האות 'א' בכתב ,ואת השנייה

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

אם נבצע את אותו מהלך בשיטת באכ"ך , יהיו הרבה יותר הצלחות , הרי שלושת החיצים הצבעוניים בשתי הגרסאות חותכים

את האות אותו מספר פעמים.