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

جدول مساحت تجمعی یک ساختمان ذخیرهٔ داده و الگوریتمی برای تولید سریع و کارآمد مجموع مقادیر در مساحت زیرمستطیل‌هایی از یک جدول است. در حوزه پردازش تصویر ، به عنوان یک تصویر انتگرالی نیز شناخته می شود. این الگوریتم ابتدا در سال ۱۹۸۴ توسط فرانک پینتر در گرافیک کامپیوتری برای استفاده با Mipmap ها معرفی شد. در شاخه بینایی کامپیوتر توسط لوئیس وارد شد و سپس با نام تصویر انتگرالی با کاربرد بجایی در چارچوب تشخیص اشیا ویولا-جونز در سال ۲۰۰۱ مورد استفاده قرار گرفت. از لحاظ تاریخی، اصول این روش در محاسبهٔ توابع توزیع احتمال چند بعدی، به ویژه در محاسبه احتمالات دو بعدی یا چند بعدی (مساحت زیر نمودار تابع توزیع احتمال) با استفاده از توابع توزیع تجمعی بسیار شناخته شده است.

استفاده از یک جدول مساحت تجمعی ( 2. ) برای جمع کردن یک مستطیل فرعی از مقادیر یک مربع جادویی مرتبه 6 ( 1. ). هر نقطه رنگی مجموع داخل مستطیل آن رنگ را برجسته می کند.

الگوریتم

همانطور که نام جدول مساحت تجمعی پیشنهاد می‌کند، مقدار ذخیره شده در هر پیکسل (x، y) در جدول برابر است با مجموع تمام پیکسل های بالا و سمت چپ آن پیکسل به علاوه مقدار خود آن پیکسل:  

$$I(x,y)=\sum _{\begin{smallmatrix}x'\leq x\\y'\leq y\end{smallmatrix}}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 را با استفاده از رابطه‌ی زیر محاسبه کرد:

$$\sum _{\begin{smallmatrix}x_{0}<x\leq x_{1}\\y_{0}<y\leq y_{1}\end{smallmatrix}}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})$$

بسط

این روش خیلی راحت قابل بسط به دامنه‌ی مقادیر پیوسته است. همچنین می توان این روش را به تصاویر با ابعاد بالاتر نیز بسط داد. اگر گوشه‌های مستطیل ${\textstyle x^{p}}$ که $p$ زیر دامنه‌‌ٔ $\{0,1\}^{d}$ باشد، مجموع مقادیر تصویر محدود به یک مستطیل با فرمول زیر محاسبه می شود

$$\sum _{p\in \{0,1\}^{d}}(-1)^{d-\|p\|_{1}}I(x^{p})\,$$

که در آن $I(x)$ تصویر انتگرالی در $x$ است و $d$ بعد تصویر. نماد گذاری $x^{p}$ در حالت $d=2$ متناظر است با $A=x^{(0,0)}$ ، $B=x^{(1,0)}$ ، $C=x^{(1,1)}$ و $D=x^{(0,1)}$ به عنوان مثال در تصویربرداری عصبی، وقتی از واکسل یا واسلکهایی با برچسب زمان استفاده شود بعد تصویر برابر است با $d=3$ یا $d=4$.

این روش در کارهایی چون مقاله‌ی Phan و همکاران به تصویر انتگرال مراتب بالاتر بسط پیدا کرده است. در این مقاله دو، سه یا چهار تصویر انتگرالی برای محاسبهٔ سریع و کارآمد انحراف معیار (واریانس) ، چولگی و کشیدگی بلوک محلی در تصویر ارائه شده‌ است که در ادامه شرح داده می‌شود:

برای محاسبه واریانس یا انحراف معیار یک بلوک، ما به دو تصویر انتگرالی نیاز داریم:

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

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

واریانس با این فرمول محاسبه می‌شود:

$$\operatorname {Var} (X)={\frac {1}{n}}\sum _{i=1}^{n}(x_{i}-\mu )^{2}.$$

اگر $S_{1}$ و $S_{2}$ به ترتیب مجموع بلوک $ABCD$ از $I$ و $I^{2}$ را نشان دهد، $S_{1}$ و $S_{2}$ به سرعت توسط تصویر انتگرال محاسبه می شوند. حال معادلهٔ واریانس را به صورت زیر تغییر می‌دهیم:

$$\operatorname {Var} (X)={\frac {1}{n}}\sum _{i=1}^{n}(x_{i}^{2}-2\cdot \mu \cdot x_{i}+\mu ^{2})={\frac {1}{n}}(\sum _{i=1}^{n}(x_{i})^{2}-2\cdot \sum _{i=1}^{n}(\mu \cdot x_{i})+\sum _{i=1}^{n}(\mu ^{2}))$$$$={\frac {1}{n}}(\sum _{i=1}^{n}(x_{i})^{2}-2\cdot \sum _{i=1}^{n}(\mu \cdot x_{i})+n\cdot (\mu ^{2}))$$$$={\frac {1}{n}}(\sum _{i=1}^{n}(x_{i})^{2}-2\cdot \mu \cdot \sum _{i=1}^{n}(x_{i})+n\cdot (\mu ^{2}))$$$$={\frac {1}{n}}(S_{2}-2\cdot S_{1}/n\cdot S_{1}+n\cdot ((S_{1}/n)^{2}))$$$$={\frac {1}{n}}(S_{2}-(S_{1})^{2}/n)$$

که در آن $\mu =S_{1}/n$ و $S_{2}=\sum _{i=1}^{n}(x_{i}^{2})$.

همان طور که برای برآورد میانگین ($\mu$) و واریانس ($Var$) به ترتیب به تصاویر انتگرالی درجه اول و دوم تصویر نیاز است (یعنی $I^{2}(x,y),I(x,y)$)؛ می‌توان نشان داد که با استفاده از تصاویر درجه سوم و چهارم (یعنی $I^{3}(x,y),I^{4}(x,y)$) می‌توان مقادیر چولگی و کشیدگی را به دست آورد.

سرریز

یکی از جزئیات مهم پیاده سازی که باید در مورد روشهای فوق در نظر داشت این است که همانطور که توسط Shafait و همکاران اشاره شده است برای تصاویر انتگرالی مرتبه بالاتر اگر از اعداد ۳۲ بیتی صحیح استفاده شود ممکن است سرریز اتفاق بیفتد.