טבלת שטח מסוכם

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

האלגוריתם

חישוב שטח בתחום מלבני

כפי שניתן לנחש משמו של האלגוריתם, הערך בכל נקודה (x, y) בטבלת שטח מסוכם הוא בפשטות סכום כל הפיקסלים מעל ומשמאל לנקודה (x, y), כולל:

${\text{sum}}(x,y)=\sum _{\begin{smallmatrix}x'\leq x\\y'\leq y\end{smallmatrix}}i(x',y')$

יש לציין כי טבלת שטח מסוכם עשויה להיות מחושבת באופן יעיל על ידי מעבר יחיד על התמונה, תוך שימוש בעובדה שהערך בטבלה בנקודה (x, y) הוא למעשה:

${\text{sum}}(x,y)=i(x,y)+{\text{sum}}(x-1,y)+{\text{sum}}(x,y-1)-{\text{sum}}(x-1,y-1)\,$

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

$\sum _{\begin{smallmatrix}A(x)<x'\leq C(x)\\A(y)<y'\leq C(y)\end{smallmatrix}}i(x',y')={\text{sum}}(A)+{\text{sum}}(C)-{\text{sum}}(B)-{\text{sum}}(D).$

הרחבות

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