משפט גרין דיסקרטי

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

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

המשפטעריכה

 
הגדרת הפרמטר  

תהי f פונקציה אינטגרבילית במישור, ותהי:

 

הפונקציה הקדומה שלה. יהי D תחום מלבני מוכלל במישור R2. אזי ניסוח המשפט הוא:

 

כאשר   היא קבוצת הפינות של התחום הנתון D, ו -   הוא פרמטר דיסקרטי עם ערכים אפשריים {0, ±1, ±2}, אשר נקבע על פי סוג הפינה, בהתאם לציור משמאל.

רעיון להוכחהעריכה

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

 

כפי שניתן לראות בתמונה לעיל, מקדמי הפונקציה הקדומה (+\-) מקזזים זה את לאורך המרובעים, מלבד פינות התחום המקורי.

דוגמהעריכה

בהינתן פונקציה f שמוגדרת ב - R2, תהי F הפונקציה הקדומה שלה. יהי D התחום שצבוע בירוק בתמונה הבאה:

 

אזי טענת המשפט לגבי התחום המלבני, היא:

 

הכללותעריכה

פאם ושותפיו הציעו הכללה לתחומים פוליגוניאליים על ידי תכנון דינמי[2].

ראו גםעריכה

לקריאה נוספתעריכה

הערות שולייםעריכה

  1. ^ X. Wang, G. Doretto, T. Sebastian, J. Rittscher, and P. Tu. “Shape and appearance context modeling”. In Proc. IEEE Int. Conf. on Computer Vision (ICCV), pages 1–8, 2007. קישור למאמר
  2. ^ M. Pham, Y. Gao, V. D. Hoang, T. Cham. “Fast Polygonal Integration and Its Application in Extending Haar-like Features to Improve Object Detection”. In Proc. of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), San Francisco, CA, 2010. קישור למאמר