ज्यामितीय हैशिंग

Not to be confused with जियोहाशिंग.

कंप्यूटर विज्ञान में, ज्यामितीय हैशिंग दो आयामी वस्तुओं को कुशलता से पता लगाने के लिए विधि है जो सतत बिंदुओं द्वारा प्रस्तुत की जाती है, जो परिशोधित परिवर्तन से हुई है, चूँकि एक्सटेंशन अन्य ऑब्जेक्ट प्रस्तुतियों एवं परिवर्तनों के लिए उपस्थित हैं। ऑफलाइन चरण में, प्रत्येक जोड़ी बिंदुओं को ज्यामितीय आधार (रैखिक बीजगणित) के रूप में मानकर वस्तुओं को एन्कोड किया जाता है। शेष बिंदुओं को दो मापदंडों का उपयोग करके इस आधार के संबंध में अपरिवर्तनीय (गणित) प्रचलन में प्रदर्शित किया जा सकता है। प्रत्येक बिंदु के लिए, इसके क्वांटिज़ेशन (सिग्नल प्रोसेसिंग) रूपांतरित निर्देशांक को हैश तालिका में कुंजी के रूप में संग्रहीत किया जाता है, एवं आधार बिंदुओं के मान के रूप में होते हैं। फिर आधार बिंदुओं की नई जोड़ी का चयन किया जाता है एवं प्रक्रिया को दोहराया जाता है। ऑनलाइन (मान्यता) चरण में, डेटा बिंदुओं के चयनित जोड़े को प्रत्याशी के आधार के रूप में माना जाता है। प्रत्येक प्रत्याशी के आधार पर, शेष डेटा बिंदुओं को आधार के अनुसार एन्कोड किया गया है एवं वस्तु से संभावित पत्राचार पूर्व निर्मित तालिका में पाए जाते हैं। प्रत्याशी के आधार को स्वीकार किया जाता है यदि पर्याप्त रूप से बड़ी संख्या में डेटा बिंदु सुसंगत वस्तु आधार को अनुक्रमित करते हैं।

जियोमेट्रिक हैशिंग मूल रूप से 2डी एवं 3डी में वस्तु मान्यता के लिए कंप्यूटर दृष्टि में दर्शायी गई थी, तत्पश्चात प्रोटीन के संरचनात्मक संरेखण जैसी विभिन्न समस्याओं पर प्रारम्भ किया गया।

कंप्यूटर दृष्टि में ज्यामितीय हैशिंग

ज्यामितीय हैशिंग वस्तु पहचान के लिए उपयोग की जाने वाली विधि है। मान लीजिए कि हम यह पता करना चाहते हैं कि इनपुट इमेज में मॉडल इमेज देखी जा सकती है या नहीं। यह ज्यामितीय हैशिंग के साथ पूर्ण किया जा सकता है। विधि का उपयोग, आधार में एकाधिक वस्तुओं को पहचानने के लिए किया जा सकता है, इस स्तिथि में हैश तालिका को न केवल मुद्रा जानकारी जबकि आधार में ऑब्जेक्ट मॉडल की अनुक्रमणिका भी संग्रहित करनी चाहिए।

उदाहरण

सरलता के लिए, यह उदाहरण अत्यधिक बिंदु विशेषताओं का उपयोग नहीं करेगा एवं यह मान लेगा कि उनके विवरणकर्ता केवल उनके निर्देशांक द्वारा दिए गए हैं (व्यवहार में स्थानीय वर्णनकर्ता जैसे कि स्केल का उपयोग अनुक्रमण के लिए किया जा सकता है)।

प्रशिक्षण चरण

छवि समन्वय प्रणाली में वस्तु के अंक, एवं आधार के लिए समन्वय प्रणाली के लिए अक्ष (P2,P4)

मॉडल के विशेष बिन्दुओ की जानकारी प्राप्त करे। मान लें कि मॉडल छवि में निर्देशांक के साथ 5 विशेष बिंदु पाए जाते हैं $(12,17);$$(45,13);$$(40,46);$$(20,35);$$(35,25)$, चित्र को देखें।

1. सुविधा बिंदुओं के स्थानों का वर्णन करने के लिए आधार का परिचय दें। 2D स्थान एवं अफिन (Affine) परिवर्तन के लिए आधार को बिंदुओं की जोड़ी द्वारा परिभाषित किया गया है। उत्पत्ति के बिंदु को दो बिंदुओं (हमारे उदाहरण में P2, P4) को जोड़ने वाले खंड के मध्य में रखा गया है $x'$ अक्ष उनमें से एक की ओर निर्देशित है, द $y'$ ओर्थोगोनल है एवं मूल से होकर जाता है। स्तर का चयन इस प्रकार किया जाता है कि का निरपेक्ष मान $x'$ दोनों आधार बिंदुओं के लिए 1 है।
2. उस आधार के संबंध में विशेष स्थानों का वर्णन करें, अर्थात अनुमानों को नए समन्वय अक्षों पर गणना करें। हम बिन आकार 0.25 लेते हैं। इस प्रकार हम निर्देशांक प्राप्त करते हैं $(-0.75,-1.25);$$(1.00,0.00);$$(-0.50,1.25);$$(-1.00,0.00);$$(0.00,0.25)$
3. सुविधाओं द्वारा अनुक्रमित हैश तालिका में आधार को एकत्र करें (इस स्तिथि में केवल रूपांतरित निर्देशांक)। यदि मिलान करने के लिए वस्तुएँ हैं, तो हमें आधार जोड़ी के साथ वस्तु संख्या भी संग्रहित करनी चाहिए।
4. भिन्न आधार जोड़ी (चरण 2) के लिए प्रक्रिया को दोहराएं। व्यवधान को आरक्षित करने के लिए इसकी आवश्यकता है। आदर्श रूप से, सभी असंरेखता युग्मों की गणना की जानी चाहिए। हम दो पुनरावृत्तियों के पश्चात् हैश तालिका प्रदान करते हैं, जोड़ी (P1, P3) को दूसरे के लिए चयनित किया जाता है।

हैश तालिका:

वेक्टर ($x'$, $y'$)	आधार
$(-0.75,-1.25);$	(P2,P4)
$(1.00,0.00);$	(P2,P4)
$(-0.50,1.25);$	(P2,P4)
$(-1.00,0.00);$	(P2,P4)
$(0.00,0.25)$	(P2,P4)
$(1.00,0.00);$	(P1,P3)
$(0.00,1.25);$	(P1,P3)
$(-1.00,0.00);$	(P1,P3)
$(0.00,-0.25);$	(P1,P3)
$(0.00,0.50)$	(P1,P3)

अधिकांश हैश तालिकाओं में भिन्न-भिन्न मानों के लिए मैप की गई समान कुंजियाँ नहीं हो सकती हैं। तो वास्तविक जीवन में हैश तालिका में आधार कुंजी (1.0, 0.0) एवं (-1.0, 0.0) को एन्कोड नहीं किया जाएगा।

मान्यता चरण

1. इनपुट छवि में रुचिकर विशेषता का बिंदु शोध करे।
2. इच्छानुसार आधार का चयन करे। यदि उपयुक्त इच्छानुसार आधार नहीं है, तो यह संभावना है कि इनपुट छवि में लक्षित वस्तु नहीं है।
3. नए आधार में विशेषता बिंदुओं के निर्देशांक का वर्णन करें। प्राप्त निर्देशांक को परिमाणित करें जैसा कि पूर्व में किया गया था।
4. हैश तालिका के साथ इनपुट छवि में सभी रूपांतरित बिंदु सुविधाओं की तुलना करें। यदि बिंदु विशेषताएं समान हैं, तो संबंधित आधार (एवं वस्तु का प्रकार, यदि कोई हो) के लिए गिनती बढ़ाएं।
5. प्रत्येक आधार के लिए जैसे कि गिनती निश्चित सीमा से अधिक है, परिकल्पना को सत्यापित करें कि यह चरण 2 में चयन किये गए छवि आधार से मिलती है। छवि समन्वय प्रणाली को मॉडल (माना वस्तु के लिए) में स्थानांतरित करें एवं उनका मिलान करने का प्रयास करें। सफल होने पर वस्तु मिल जाती है। अन्यथा, चरण 2 पर वापस जाएँ।

प्रतिबिंबित पैटर्न ढूँढना

ऐसा प्रतीत होता है कि यह विधि केवल स्केलिंग, ट्रांसलेशन एवं रोटेशन को आरक्षित करने में सक्षम है। चूँकि, इनपुट छवि में दर्पण परिवर्तन में वस्तु हो सकती है। इसलिए, ज्यामितीय हैशिंग को भी वस्तु का शोध करने में सक्षम होना चाहिए। प्रतिबिंबित वस्तुओं की जानकारी प्राप्त करने के दो उपाए हैं।

1. वेक्टर ग्राफ के लिए, बाईं ओर सकारात्मक एवं दाईं ओर नकारात्मक बनाएं। x स्थिति को -1 से गुणा करने पर वही परिणाम मिलेगा।
2. आधार के लिए 3 बिंदुओं का प्रयोग करें। यह दर्पण छवियों (या वस्तुओं) का पता लगाने की अनुमति देता है। दरअसल, आधार के लिए 3 बिंदुओं का उपयोग करना ज्यामितीय हैशिंग के लिए एक एवं तरीका है।

उच्च-आयामों में ज्यामितीय हैशिंग

ऊपर दिए गए उदाहरण के समान, हैशिंग उच्च-आयामी डेटा पर लागू होती है। त्रि-आयामी डेटा बिंदुओं के लिए, आधार के लिए तीन बिंदुओं की भी आवश्यकता होती है। पहले दो बिंदु x-अक्ष को परिभाषित करते हैं, एवं तीसरा बिंदु y-अक्ष (पहले बिंदु के साथ) को परिभाषित करता है। z-अक्ष दाएँ हाथ के नियम का उपयोग करके बनाए गए अक्ष के लंबवत है। ध्यान दें कि अंकों का क्रम परिणामी आधार को प्रभावित करता है

यह भी देखें

• अवधारणात्मक हैशिंग

संदर्भ

• Wolfson, H.J. & Rigoutsos, I (1997). Geometric Hashing: An Overview. IEEE Computational Science and Engineering, 4(4), 10-21.