3 डी ऊंचाईमैप में सैडल पॉइंट ढूंढना

Question

एक 3 डी ऊंचाईमैप (लेजर स्कैनर से) को देखते हुए, मुझे saddle points कैसे मिल सकता है?

आईई। कुछ इस तरह दिया:

मैं सभी बिंदुओं जहां वक्रता एक ही दिशा में सकारात्मक और अन्य में नकारात्मक है के लिए देख रहा हूँ।

(इन दिशाओं को एक्स और वाई अक्ष के साथ गठबंधन करने की आवश्यकता नहीं है। मुझे पता है कि एक्स दिशा में वक्रता वाई दिशा में वक्रता के विपरीत विपरीत संकेत है या नहीं, लेकिन इसमें सभी मामलों को शामिल नहीं किया गया है । मामले को बदतर बनाने के लिए, X में संकल्प

आदर्श रूप में मैं एक एल्गोरिथ्म कि शोर की कुछ राशि बर्दाश्त कर सकते हैं और केवल "महत्वपूर्ण" काठी बिंदुओं को चिह्नित रहा हूँ Y में संकल्प से अलग है)।

Answer 1

प्रत्येक उम्मीदवार बिंदु है, उदा के चारों ओर एक छोटे पैच में सतह के लिए एक द्विघात फ़िट (गणित पर एक अनुमान के बजाय व्यावहारिक अनुभव से) कम से कम वर्गों के साथ। पैच कितना बड़ा शोर को नियंत्रित करने का एक तरीका है, और आप उम्मीदवार बिंदु से उनकी दूरी के आधार पर भारोत्तोलन बिंदुओं से लाभ प्राप्त कर सकते हैं। मैट्रिक्स नोटेशन में, आप वर्ग 'x'Ax + b'x + c के रूप में प्रतिनिधित्व कर सकते हैं, जहां ए सममित है।

वर्गवार x = (ए^-1) बी/2 पर शून्य ढाल होगा। यदि यह पैच के भीतर नहीं है, तो इसे छोड़ दें।

यदि ए में दोनों हैं और -वे eigenvalues ​​आपके पास एक्स पर एक सैडल बिंदु है। चूंकि ए केवल 2x2 है और इसलिए अधिकतम दो eigenvalues ​​है, तो आप शून्य eigenvalue के रूप में इस मामले को अनदेखा कर सकते हैं और इसलिए आप इसे पिछले चरण में उलटा नहीं कर सका।

Answer 2

मैं कम्प्यूटेशनल टोपोलॉजी क्लास के लिए एक समान समस्या की खोज कर रहा हूं और नीचे उल्लिखित विधि के साथ कुछ सफलता मिली है।

सबसे पहले आपको तुलनात्मक फ़ंक्शन की आवश्यकता होगी जो दो इनपुट बिंदुओं पर ऊंचाई का मूल्यांकन करेगी और किसी भी इनपुट के लिए < या> (बराबर नहीं) लौटाएगी। ऐसा करने का एक तरीका यह है कि यदि अंक बराबर ऊंचाई हैं तो आप अधिक बिंदु खोजने के लिए कुछ स्थिति-आधारित या यादृच्छिक अनुक्रमणिका का उपयोग करते हैं। आप इस बारे में सोच सकते हैं कि ऊंचाई पर एक infinitesimal परेशानी जोड़ना।

अब, प्रत्येक बिंदु के लिए, आप आसपास के पड़ोसियों की ऊंचाई की तुलना करेंगे (2 डी आयताकार ग्रिड पर 8 पड़ोसी होंगे)। एक बिंदु के लिए निचला लिंक उन सभी पड़ोसियों का सेट होगा जिनके लिए ऊंचाई बिंदु से कम है।

यदि सभी पड़ोसी मूल्य निम्न लिंक में हैं, तो आप स्थानीय अधिकतम पर हैं। यदि निचले लिंक में कोई भी अंक नहीं है तो आप स्थानीय न्यूनतम पर हैं। अन्यथा, यदि निचला लिंक एक एकल कनेक्टेड सेट है, तो आप एक ढलान पर नियमित बिंदु पर हैं। लेकिन यदि निचला लिंक दो अनकनेक्टेड सेट है, तो आप एक सैडल पर हैं।

2 डी में आप जिस बिंदु की जांच कर रहे हैं उसके आसपास चक्रीय क्रम में 8 पड़ोसी बिंदु की एक सूची बना सकते हैं। आप अपने तुलनात्मक कार्य के आधार पर प्रत्येक पड़ोसी के लिए +/- 1 का मान असाइन करते हैं। फिर आप उस सूची के माध्यम से कदम उठा सकते हैं (दो अंत बिंदुओं की तुलना करना याद रखें) और निचले लिंक में जुड़े घटकों की संख्या निर्धारित करने के लिए साइन कितनी बार बदलते हैं।

निर्धारित करना कि कौन सा सैडल "महत्वपूर्ण" एक कठिन विश्लेषण है। आप कुछ दिशानिर्देशों के लिए इसे देख सकते हैं: http://www.cs.jhu.edu/~misha/ReadingSeminar/Papers/Gyulassy08.pdf।

-माइकल