جدول مساحت تجمعی
جدول مساحت تجمعی یک ساختمان ذخیرهٔ داده و الگوریتمی برای تولید سریع و کارآمد مجموع مقادیر در مساحت زیرمستطیل‌هایی از یک جدول است. در حوزه پردازش تصویر ، به عنوان یک تصویر انتگرالی نیز شناخته می شود. این الگوریتم ابتدا در سال ۱۹۸۴ توسط فرانک پینتر در گرافیک کامپیوتری برای استفاده با ها معرفی شد. در شاخه بینایی کامپیوتر توسط لوئیس وارد شد و سپس با نام تصویر انتگرالی با کاربرد بجایی در چارچوب تشخیص اشیا ویولا-جونز در سال ۲۰۰۱ مورد استفاده قرار گرفت. از لحاظ تاریخی، اصول این روش در محاسبهٔ توابع توزیع احتمال چند بعدی، به ویژه در محاسبه احتمالات دو بعدی یا چند بعدی (مساحت زیر نمودار تابع توزیع احتمال) با استفاده از توابع توزیع تجمعی بسیار شناخته شده است.
همانطور که نام جدول مساحت تجمعی پیشنهاد می‌کند، مقدار ذخیره شده در هر پیکسل ("x"، "y") در جدول برابر است با مجموع تمام پیکسل های بالا و سمت چپ آن پیکسل به علاوه مقدار خود آن پیکسل:
که در آن formula_2 مقدار پیکسل در نقطه‌ٔ (x ، y) است.
جدول مساحت تجمعی را می توان تنها با یک بار عبور از روی تک تک خانه‌های تصویر محاسبه کرد، چرا که مقدار پیکسل ("x"، "y") در جدول مساحت تجمعی برابر است با:
اگر محاسبهٔ ماتریس تجمعی را از گوشهٔ بالا سمت چپ تصویر شروع کنیم با پیمایش هر سطر برای محاسبهٔ هر پیکسل کافی است از مقدار پیکسل‌های سمت چپ، بالا و بالا سمت چپ آن پیکسل که قبلا محاسبه شده‌اند استفاده کرده مقادیر کل جدول را محاسبه‌ کنیم. پس از محاسبه‌‌ٔ جدول مساحت تجمعی، ارزیابی مجموع مقادیر در مساحت هر ناحیه مستطیلی مستلزم جمع تنها چهار عنصر جدول صرف نظر از اندازه مساحت مورد نظر است. یعنی همان طور که در شکل نمایش داده شده است، با داشتن مقادیر A و B و C می‌توان مقدار D را با استفاده از رابطه‌ی زیر محاسبه کرد:
این روش خیلی راحت قابل بسط به دامنه‌ی مقادیر پیوسته است. همچنین می توان این روش را به تصاویر با ابعاد بالاتر نیز بسط داد. اگر گوشه‌های مستطیل formula_6 که formula_7 زیر دامنه‌‌ٔ formula_8 باشد، مجموع مقادیر تصویر محدود به یک مستطیل با فرمول زیر محاسبه می شود
که در آن formula_10 تصویر انتگرالی در formula_11 است و formula_12 بعد تصویر. نماد گذاری formula_13 در حالت formula_14 متناظر است با formula_15 ، formula_16 ، formula_17 و formula_18 به عنوان مثال در تصویربرداری عصبی، وقتی از واکسل یا واسلکهایی با برچسب زمان استفاده شود بعد تصویر برابر است با formula_19 یا formula_20.
این روش در کارهایی چون مقاله‌ی Phan و همکاران به تصویر انتگرال مراتب بالاتر بسط پیدا کرده است. در این مقاله دو، سه یا چهار تصویر انتگرالی برای محاسبهٔ سریع و کارآمد انحراف معیار (واریانس) ، چولگی و کشیدگی بلوک محلی در تصویر ارائه شده‌ است که در ادامه شرح داده می‌شود:
برای محاسبه واریانس یا انحراف معیار یک بلوک، ما به دو تصویر انتگرالی نیاز داریم:
واریانس با این فرمول محاسبه می‌شود:
اگر formula_24 و formula_25 به ترتیب مجموع بلوک formula_26 از formula_27 و formula_28 را نشان دهد، formula_24 و formula_25 به سرعت توسط تصویر انتگرال محاسبه می شوند. حال معادلهٔ واریانس را به صورت زیر تغییر می‌دهیم:
که در آن formula_36 و formula_37.
همان طور که برای برآورد میانگین (formula_38) و واریانس (formula_39) به ترتیب به تصاویر انتگرالی درجه اول و دوم تصویر نیاز است (یعنی formula_40)؛ می‌توان نشان داد که با استفاده از تصاویر درجه سوم و چهارم (یعنی formula_41) می‌توان مقادیر چولگی و کشیدگی را به دست آورد.
یکی از جزئیات مهم پیاده سازی که باید در مورد روشهای فوق در نظر داشت این است که همانطور که توسط Shafait و همکاران اشاره شده است برای تصاویر انتگرالی مرتبه بالاتر اگر از اعداد ۳۲ بیتی صحیح استفاده شود ممکن است سرریز اتفاق بیفتد.