डायनामिक मिलान ग्राफ़ का उपयोग करके छवियों के बीच झूठे मेल को फ़िल्टर करना

कई आधुनिक कंप्यूटर दृष्टि एल्गोरिदम दृश्य छवियों के विशिष्ट बिंदुओं का पता लगाने और तुलना पर आधारित हैं। इस विषय पर Habré (उदाहरण के लिए, SURF , SIFT ) पर बहुत सारे लेख लिखे गए थे। लेकिन अधिकांश कार्य इस तरह के एक महत्वपूर्ण चरण पर ध्यान नहीं देते हैं क्योंकि छवियों के बीच झूठे मैचों को फ़िल्टर करना है। सबसे अधिक बार, RANSAC पद्धति का उपयोग इन उद्देश्यों के लिए किया जाता है और वे यहां रुकते हैं। लेकिन यह इस समस्या को हल करने का एकमात्र तरीका नहीं है।
यह लेख झूठे मैचों को छानने के लिए वैकल्पिक तरीकों में से एक पर केंद्रित है।

समस्या का बयान

मान लें कि हमारे पास क्रमशः n _p और n _q अंकों के साथ दो छवियों P और Q से प्राप्त एकवचन बिंदुओं के दो सेट हैं। प्रत्येक एकवचन बिंदु एक जोड़ी p = {p _d , p _c } है। p _d - बिंदु की एक स्थानीय विशेषता है (उदाहरण के लिए, एक SURF विवरणक), और p _c = {x, y} सुविधा बिंदु का निर्देशांक है।
हमारे पास कई पत्राचार M = {c _i = (i, i ') | c _i ∈ C, i, P, i 'constructed Q} का निर्माण कुछ मीट्रिक (उदाहरण के लिए, यूक्लिडियन मीट्रिक के निकटतम डिस्क्रिप्टर के साथ अंक के रूप में) किया गया है। प्रत्येक पत्राचार के लिए, हम एक गैर-नकारात्मक आकलन फ़ंक्शन S _{c i} = f ₁ (i _d , i ' _d ) का निर्माण करते हैं।

दो पत्राचारों c _i = (i, i ') और c _j = (j, j') के लिए, हम मानते हैं कि पहली छवि में बिंदुओं में i और j के बीच की दूरी और बिंदुओं में i 'और' j 'और दूसरी छवि में l _ij और l _{i' j ',} क्रमशः। जाहिर है, अगर ये दोनों मैच सच हैं, तो हम पी के साथ छवि क्यू को एल के साथ जोड़ सकते हैं, जिसमें एल फैज फ्रैक्शनल होगा; l _{i'j '} , और हम कहते हैं कि इस जोड़ी ने स्केल l _ij फ्रैस्ल के लिए वोटों का मिलान किया; l _{i'j '} । अब मान लीजिए कि इसके अनुरूप n सही मैचों के साथ एक दृश्य छवि है, तो इनमें से प्रत्येक जोड़ी के लिए स्केल फैक्टर लगभग समान होना चाहिए। इस तरह के पैमाने को ज्यामितीय स्थिरता का पैमाना कारक कहा जाएगा और इसे एस द्वारा निरूपित किया जाएगा। मैचों की जोड़ी c = (i, i ') और c _j = (j, j') की ज्यामितीय संगति का पैमाना कारक निम्नानुसार व्यक्त किया जाता है:
S _{c i c j} (s) = f ₂ (| l _ij - s * l _{i'j '} |), जहां f ₂ (x) एक गैर-नकारात्मक एकात्मक रूप से घटता कार्य है।

बता दें कि सेट M में m पत्राचार M = {c ₁ , ..., c _m } है। हम एम कोने के साथ एक ग्राफ जी का निर्माण करते हैं, जिनमें से प्रत्येक शीर्ष पर एम से एक पत्राचार का प्रतिनिधित्व करता है। कोने I और जम्मू के बीच एक किनारे का वजन निम्नानुसार परिभाषित किया गया है:
w _ij (s) = S _{c i} * S _{c j} * S _{c i c j} (s)।
इस तरह से निर्मित ग्राफ को डायनेमिक कॉरेस्पोंडेंस ग्राफ (इसके बाद डीजीएस के रूप में संदर्भित) कहा जाएगा।

हम डीजीएस द्वारा ए (एस) के लिए भारित आसन्न मैट्रिक्स को निरूपित करते हैं और इसे निम्नानुसार बनाते हैं:

A (s) ^m R ^{m * m} - सममित और गैर-नकारात्मक।

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

यदि हम T को एक संकेतक वेक्टर y के रूप में दर्शाते हैं जैसे कि , तब औसत इंट्रा-क्लस्टर अनुमान को द्विघात रूप में फिर से लिखा जा सकता है:
जहाँ । ।

जैसा कि ज्ञात है, मोत्ज़किन-स्ट्रॉस प्रमेय इस तरह के द्विघात रूप के अधिकतम गुच्छे और स्थानीय अधिकतम के बीच संबंध स्थापित करता है:
जहाँ आर ^एम में मानक सिम्प्लेक्स है। सीधे शब्दों में कहें, प्रमेय कहता है कि एक ग्राफ G के एक सबसेट टी का एक सबसेट टी एक ऐसा समलिंगी समरूप होता है यदि और केवल इसकी विशेषता वेक्टर x ^T मानक सिम्प्लेक्स में द्विघात फ़ंक्शन f (x) का स्थानीय अधिकतम है, जहाँ x ^T = 1⁄ T। अगर मैं, टी, एक्स _मैं ^टी = 0 अन्यथा।

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

स्वीकृत मानदंड l ₁ के कई फायदे हैं। सबसे पहले, इसका एक सरल संभाव्य अर्थ है: x _i इस संभावना का प्रतिनिधित्व करता है कि एक पूर्ण उपसमूह में शीर्ष i होता है। दूसरे, समाधान x विरल है, और केवल एक ही सबग्राफ में कुछ घटक बहुत महत्व के हैं, शेष घटक काफी छोटे हैं, जो हमें शोर करने वाले उन कोने को त्यागकर एक क्लस्टर का चयन करने की अनुमति देता है, जो शोर हैं।

इस प्रकार, व्यक्तिगत दृश्य चित्रों का प्रतिनिधित्व करने वाले पत्राचार के समूहों को खोजने की समस्या के लिए पत्राचार को फ़िल्टर करने का कार्य कम हो जाता है। बदले में, ऐसे समूहों को खोजने के लिए, ऊपर वर्णित अनुकूलन समस्या को हल करना आवश्यक है।

एल्गोरिथम विवरण

स्केल s _{0 के लिए} , अनुकूलन समस्या कई स्थानीय मैक्सिमा हो सकते हैं। प्रत्येक बड़ा स्थानीय अधिकतम अक्सर सही दृश्य छवि से मेल खाता है, और छोटा स्थानीय अधिकतम अक्सर शोर के परिणामस्वरूप होता है।

जब x (1) को इनिशियलाइज़ किया जाता है, तो तत्संबंधी स्थानीय सॉल्यूशन x को पहले क्रम के सेल्फ-असेंबली समीकरण का उपयोग करके प्रभावी रूप से प्राप्त किया जा सकता है:


यह ध्यान दिया जा सकता है कि सिंप्लेक्स Δ ऐसी गतिशीलता के संबंध में अपरिवर्तनीय है, जिसका अर्थ है कि Δ में शुरू होने वाला कोई भी प्रक्षेप ory में रहेगा। इसके अलावा, यह साबित हो गया कि जब ए (एस ₀ ) सममित और गैर-नकारात्मक तत्वों के साथ होता है, तो उद्देश्य फ़ंक्शन स्व-विधानसभा समीकरण के किसी भी गैर-निरंतर प्रक्षेपवक्र के साथ सख्ती बढ़ जाती है, और ये विषम रूप से स्थिर बिंदु एक द्विघात फ़ंक्शन के स्थानीय समाधान के साथ सख्त एक-से-एक पत्राचार में हैं।

मोटे तौर पर, एक्स के सभी बड़े स्थानीय मैक्सिमा खोजने के लिए, वे कई प्रारंभिक इनिशियलाइज़ेशन लेते हैं और इस तरह गारंटी देते हैं कि किसी दिए गए सिम्प्लेक्स में सभी बड़े स्थानीय मैक्सिमा को ध्यान में रखा जाएगा। जैसा कि ऊपर उल्लेख किया गया है, हमारे कार्य के लिए, प्रत्येक स्थानीय अधिकतम एक दृश्य छवि से मेल खाती है, तो इसमें दो गुण होने चाहिए:

1. स्थानीय संपत्ति। एक दृश्य छवि के एकवचन बिंदु कुछ छोटे पड़ोस में स्थित हैं, इसलिए हमें एक्सवी (1) को केवल जीवीडी के प्रत्येक शीर्ष के आसपास के क्षेत्र में शुरू करने की आवश्यकता है।
2. गैर-चौराहे की संपत्ति। विभिन्न दृश्य छवियां, एक नियम के रूप में, जी में सामान्य कोने नहीं होते हैं, जिसका अर्थ है कि यदि दो स्थानीय मैक्सिमा x और y दो अलग-अलग दृश्य छवियों के अनुरूप हैं, तो (x, y) ~ 0।

चूँकि हमने DGS के प्रत्येक शीर्ष के लिए x (1) को इनिशियलाइज़ किया है और एक ही विज़ुअल इमेज के वर्टिकल का इनिशियलाइज़ेशन लगभग एक स्थानीय अधिकतम में परिवर्तित होता है, इसलिए हमें उसी विज़ुअल इमेज के अनुरूप स्थानीय मैक्सिमा को मर्ज करना होगा। इस तरह के डेटा अतिरेक के कारण, अतिरिक्त शोर प्रतिरक्षा हासिल की जाती है। शोर से संबंधित सभी छोटी स्थानीय मैक्सीमा भी त्याग दी जाती हैं।

अंत में, प्रत्येक स्थानीय अधिकतम x के लिए दृश्य छवि को पुनर्स्थापित करना आवश्यक है। क्योंकि x _i दृश्य छवि x में प्रवेश करने वाले शीर्ष की संभावना का प्रतिनिधित्व करता है x, हम केवल उन शीर्षों का चयन कर सकते हैं जिनकी दृश्य छवि में होने की संभावना सबसे अधिक है।

एल्गोरिदम मापदंडों

जैसा कि उपरोक्त विवरण से देखा जा सकता है, एल्गोरिथ्म में बड़ी संख्या में विन्यास योग्य पैरामीटर हैं जैसे:

• S _{c i} = f ₁ (i _d , i ' _d ) - अनुरूपता मूल्यांकन कार्य
• S _{c i c j j} (s) = f ₂ (| l _ij - s * l _{i'j '} |) - पत्राचारों की ज्यामितीय संगति का मूल्यांकन करने के लिए कार्य करता है।
• Ization - आरंभीकरण के पड़ोस से संबंधित, पसली के वजन का अनुमान लगाने के लिए मूल्य
• Neighborhood पड़ोस का त्रिज्या है जिसके लिए आरंभीकरण x (1) लिया जाता है
• Value - स्थानीय अधिकतम की लघुता का आकलन करने के लिए सीमा मूल्य
• S - पड़ोस के विलय के लिए सीमा मूल्य
• Of - दृश्य छवि में प्रवेश करने वाले शीर्ष की संभावना का दहलीज मूल्य

प्रयोगों

एल्गोरिथ्म के विशिष्ट परिणाम नीचे प्रस्तुत किए गए हैं।

निष्कर्ष

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

साहित्य

• सामान्य दृश्य पैटर्न डिस्कवरी के माध्यम से स्थानिक रूप से सुसंगत संवाददाता हेयरॉन्ग लियू, शुइचेंग यान, इलेक्ट्रिकल और कंप्यूटर इंजीनियरिंग विभाग, नेशनल यूनिवर्सिटी ऑफ सिंगापुर, सिंगापुर
• टी। मोटज़किन और ई। स्ट्रॉस। रेखांकन के लिए मैक्सिमा और तूरान के एक प्रमेय का एक नया प्रमाण। Canad। जे। मठ, 1965।
• 10. एम। पेलिलो, के। सिद्दीकी और एस। जुकर। एसोसिएशन ग्राफ़ का उपयोग करके पदानुक्रमित संरचनाओं का मिलान करना। TPAMI, 1999।

UPD विधि स्रोतों के लिए लिंक: dl.dropbox.com/u/15642384/src.7z