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

ऑर्डर -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')$$

जहाँ (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₁) है, कुल मिलाकर A, B, C, और D द्वारा फैले आयत पर i(x,y) का योग है:

$$\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}$ है और $\{0,1\}^{d}$ में $p$ है , तो आयत में निहित छवि मानों के योग की गणना सूत्र के साथ की जाती है:

$$\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

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

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

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

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