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

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

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

الگوریتم

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

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

که در آن ${\displaystyle i(x,y)}$ مقدار پیکسل در نقطه‌ٔ (x ، y) است.

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

$${\displaystyle I(x,y)=i(x,y)+I(x,y-1)+I(x-1,y)-I(x-1,y-1)\,}$$

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

نمایش محاسبه مجموع در ساختمان داده/الگوریتم جدول مساحت تجمعی

پس از محاسبه‌‌ٔ جدول مساحت تجمعی، ارزیابی مجموع مقادیر در مساحت هر ناحیه مستطیلی مستلزم جمع تنها چهار عنصر جدول صرف نظر از اندازه مساحت مورد نظر است. یعنی همان طور که در شکل نمایش داده شده است، با داشتن مقادیر A و B و C می‌توان مقدار D را با استفاده از رابطه‌ی زیر محاسبه کرد:

$${\displaystyle \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)}$$$${\displaystyle A=(x_{0},y_{0}),B=(x_{1},y_{0}),C=(x_{0},y_{1}),D=(x_{1},y_{1})}$$

بسط

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

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

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

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

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

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

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

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

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

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

$${\displaystyle \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}))}$$$${\displaystyle ={\frac {1}{n}}(\sum _{i=1}^{n}(x_{i})^{2}-2\cdot \sum _{i=1}^{n}(\mu \cdot x_{i})+n\cdot (\mu ^{2}))}$$$${\displaystyle ={\frac {1}{n}}(\sum _{i=1}^{n}(x_{i})^{2}-2\cdot \mu \cdot \sum _{i=1}^{n}(x_{i})+n\cdot (\mu ^{2}))}$$$${\displaystyle ={\frac {1}{n}}(S_{2}-2\cdot S_{1}/n\cdot S_{1}+n\cdot ((S_{1}/n)^{2}))}$$$${\displaystyle ={\frac {1}{n}}(S_{2}-(S_{1})^{2}/n)}$$

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

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

سرریز

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

منابع

1. Lewis, J.P. (1995). Fast template matching. Proc. Vision Interface. pp. 120–123.
2. Finkelstein, Amir; neeratsharma (2010). "Double Integrals By Summing Values Of Cumulative Distribution Function". Wolfram Demonstration Project
3. Tapia, Ernesto (January 2011). "A note on the computation of high-dimensional integral images". Pattern Recognition Letters. 32 (2): 197–201. doi:10.1016/j.patrec.2010.10.007.
4. Phan, Thien; Sohoni, Sohum; Larson, Eric C.; Chandler, Damon M. (22 April 2012). Performance-analysis-based acceleration of image quality assessment بایگانی‌شده در ۲۴ مه ۲۰۱۴ توسط Wayback Machine (PDF). 2012 IEEE Southwest Symposium on Image Analysis and Interpretation. pp. 81–84. CiteSeerX 10.1.1.666.4791. doi:10.1109/SSIAI.2012.6202458. ISBN 978-1-4673-1830-3.
5. Shafait, Faisal; Keysers, Daniel; M. Breuel, Thomas (January 2008). "Efficient implementation of local adaptive thresholding techniques using integral images" (PDF). Electronic Imaging. Document Recognition and Retrieval XV. 6815: 681510–681510–6. CiteSeerX 10.1.1.109.2748. doi:10.1117/12.767755. Archived from the original (PDF) on 15 December 2014. Retrieved 15 August 2021.