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

מתוך המכלול, האנציקלופדיה היהודית
קפיצה לניווט קפיצה לחיפוש

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

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

המשפט

הגדרת הפרמטר

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

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

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

רעיון להוכחה

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

Proof discrete green.png

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

דוגמה

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

Discrete green illustration.png

אזי

הכללות

פאם ושותפיו הציעו הכללה לתחומים פוליגוניים על ידי תכנון דינמי[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. קישור למאמר
Logo hamichlol 3.png
הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0