सारांशित क्षेत्र तालिका

ऑर्डर -6 जादू वर्ग (1.) के योग-क्षेत्र तालिका (2.) का उपयोग करके इसके मानों के एक उप-आयत का योग करना; प्रत्येक रंगीन स्थान उस रंग के आयत के अंदर योग को हाइलाइट करता है।

एक योग-क्षेत्र तालिका एक ग्रिड के एक आयताकार उपसमुच्चय में मूल्यों के योग को जल्दी और कुशलता से उत्पन्न करने के लिए एक डेटा संरचना और कलन विधि है। मूर्ति प्रोद्योगिकी डोमेन में, इसे इंटीग्रल इमेज के रूप में भी जाना जाता है। यह 1984 में फ्रैंकलिन सी. क्रो द्वारा मिपमैप्स के साथ उपयोग के लिए कंप्यूटर चित्रलेख के लिए प्रस्तुत किया गया था। कंप्यूटर दृष्टि में इसे लुईस द्वारा लोकप्रिय बनाया गया था और उसके बाद अभिन्न छवि नाम दिया गया और 2001 में वियोला-जोन्स ऑब्जेक्ट डिटेक्शन फ्रेमवर्क के अंदर प्रमुखता से उपयोग किया गया। ऐतिहासिक रूप से, यह सिद्धांत बहु-आयामी संभाव्यता वितरण कार्यों के अध्ययन में बहुत अच्छी तरह से जाना जाता है, अर्थात् 2D (या ND) संभावनाओं की गणना में ( संभाव्यता वितरण के अनुसार क्षेत्र) संबंधित संचयी वितरण कार्यों से।

एल्गोरिथम

जैसा कि नाम से पता चलता है, सारांशित क्षेत्र तालिका में किसी भी बिंदु (x, y) पर मान ऊपर और (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 = (x₀, y₀), B = (x₁, y₀), C = (x₀, y₁) और D = (x₁, y₁), कुल मिलाकर i(x,y) 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)$$

एक्सटेंशन

यह विधि स्वाभाविक रूप से निरंतर डोमेन तक विस्तारित है।

विधि को उच्च-आयामी छवियों तक भी बढ़ाया जा सकता है। यदि आयत के कोने हैं $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$, टाइम-स्टैम्प के साथ वॉक्सेल या वोक्सल्स का उपयोग करते समय।

फान एट अल के काम के रूप में इस पद्धति को उच्च-क्रम की अभिन्न छवि तक बढ़ा दिया गया है। जिन्होंने छवि में स्थानीय ब्लॉक के मानक विचलन (विचरण), तिरछापन और कर्टोसिस की त्वरित और कुशलता से गणना करने के लिए दो, तीन, या चार अभिन्न छवियां प्रदान कीं। यह नीचे विस्तृत है:

किसी ब्लॉक के प्रसरण या मानक विचलन की गणना करने के लिए, हमें दो अभिन्न छवियों की आवश्यकता होती है:

$$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}$ अभिन्न छवि द्वारा जल्दी से गणना की जाती है। अब, हम विचरण समीकरण में हेरफेर करते हैं:

$${\begin{aligned}\operatorname {Var} (X)&={\frac {1}{n}}\sum _{i=1}^{n}\left(x_{i}^{2}-2\mu x_{i}+\mu ^{2}\right)\\[1ex]&={\frac {1}{n}}\left[\sum _{i=1}^{n}x_{i}^{2}-2\sum _{i=1}^{n}\mu x_{i}+\sum _{i=1}^{n}\mu ^{2}\right]\\[1ex]&={\frac {1}{n}}\left[\sum _{i=1}^{n}x_{i}^{2}-2\sum _{i=1}^{n}\mu x_{i}+n\mu ^{2}\right]\\[1ex]&={\frac {1}{n}}\left[\sum _{i=1}^{n}x_{i}^{2}-2\mu \sum _{i=1}^{n}x_{i}+n\mu ^{2}\right]\\[1ex]&={\frac {1}{n}}\left[S_{2}-2{\frac {S_{1}}{n}}S_{1}+n\left({\frac {S_{1}}{n}}\right)^{2}\right]\\[1ex]&={\frac {1}{n}}\left[S_{2}-{\frac {S_{1}^{2}}{n}}\right]\end{aligned}}$$

कहाँ $\mu =S_{1}/n$ और ${\textstyle S_{2}=\sum _{i=1}^{n}x_{i}^{2}}$

माध्य के अनुमान के समान ($\mu$) और विचरण ($\operatorname {Var}$), जिसके लिए क्रमशः छवि की पहली और दूसरी शक्ति की अभिन्न छवियों की आवश्यकता होती है (अर्थात $I,I^{2}$); ऊपर उल्लिखित के समान हेरफेर छवियों की तीसरी और चौथी शक्तियों के लिए किया जा सकता है (अर्थात। $I^{3}(x,y),I^{4}(x,y)$ तिरछापन और कर्टोसिस प्राप्त करने के लिए। किन्तु एक महत्वपूर्ण कार्यान्वयन विवरण जिसे उपरोक्त विधियों के लिए ध्यान में रखा जाना चाहिए, जैसा कि एफ शाफेट एट अल द्वारा उल्लेख किया गया है। 32-बिट पूर्णांकों का उपयोग किए जाने की स्थिति में उच्च क्रम की अभिन्न छवियों के लिए पूर्णांक अतिप्रवाह होता है।

यह भी देखें

• उपसर्ग राशि

बाहरी संबंध

• Summed table implementation in object detection

व्याख्यान वीडियो

• इंटीग्रल इमेज एल्गोरिदम के पीछे के सिद्धांत का परिचय
• वोल्फ्राम डिमॉन्स्ट्रेशन प्रोजेक्ट से इंटीग्रल इमेज एल्गोरिद्म के निरंतर संस्करण का एक प्रदर्शन

श्रेणी:डिजिटल ज्यामिति

श्रेणी:कंप्यूटर ग्राफ़िक्स डेटा संरचनाएँ