جدول مساحت تجمعی

جدول مساحت تجمعی یک ساختمان ذخیرهٔ داده و الگوریتمی برای تولید سریع و کارآمد مجموع مقادیر در مساحت زیرمستطیل هایی از یک جدول است. در حوزه پردازش تصویر ، به عنوان یک تصویر انتگرالی نیز شناخته می شود. این الگوریتم ابتدا در سال ۱۹۸۴ توسط فرانک پینتر در گرافیک کامپیوتری برای استفاده با Mipmap ها معرفی شد. در شاخه بینایی کامپیوتر توسط لوئیس[ ۱] وارد شد و سپس با نام تصویر انتگرالی با کاربرد بجایی در چارچوب تشخیص اشیا ویولا - جونز در سال ۲۰۰۱ مورد استفاده قرار گرفت. از لحاظ تاریخی، اصول این روش در محاسبهٔ توابع توزیع احتمال چند بعدی، به ویژه در محاسبه احتمالات دو بعدی یا چند بعدی ( مساحت زیر نمودار تابع توزیع احتمال ) با استفاده از توابع توزیع تجمعی بسیار شناخته شده است. [ ۲]
همانطور که نام جدول مساحت تجمعی پیشنهاد می کند، مقدار ذخیره شده در هر پیکسل ( x،   y ) در جدول برابر است با مجموع تمام پیکسل های بالا و سمت چپ آن پیکسل به علاوه مقدار خود آن پیکسل:  
I ( x , y ) = ∑ x ′ ≤ x y ′ ≤ y i ( x ′ , y ′ )
که در آن i ( x , y ) مقدار پیکسل در نقطه ٔ ( x ، y ) است.
جدول مساحت تجمعی را می توان تنها با یک بار عبور از روی تک تک خانه های تصویر محاسبه کرد، چرا که مقدار پیکسل ( x،   y ) در جدول مساحت تجمعی برابر است با:
I ( x , y ) = i ( x , y ) + I ( x , y − 1 ) + I ( x − 1 , y ) − I ( x − 1 , y − 1 )
اگر محاسبهٔ ماتریس تجمعی را از گوشهٔ بالا سمت چپ تصویر شروع کنیم با پیمایش هر سطر برای محاسبهٔ هر پیکسل کافی است از مقدار پیکسل های سمت چپ، بالا و بالا سمت چپ آن پیکسل که قبلا محاسبه شده اند استفاده کرده مقادیر کل جدول را محاسبه کنیم.
پس از محاسبه ٔ جدول مساحت تجمعی، ارزیابی مجموع مقادیر در مساحت هر ناحیه مستطیلی مستلزم جمع تنها چهار عنصر جدول صرف نظر از اندازه مساحت مورد نظر است. یعنی همان طور که در شکل نمایش داده شده است، با داشتن مقادیر A و B و C می توان مقدار D را با استفاده از رابطه ی زیر محاسبه کرد:
∑ x 0 < x ≤ x 1 y 0 < y ≤ y 1 i ( x , y ) = I ( D ) + I ( A ) − I ( B ) − I ( C )
A = ( x 0 , y 0 ) , B = ( x 1 , y 0 ) , C = ( x 0 , y 1 ) , D = ( x 1 , y 1 )