केवल अनुवाद और रोटेशन का उपयोग करके 2 डी अंकों के एक सेट को संरेखित करें

Question

मैं ओपनसीवी में काम कर रहा हूं लेकिन मुझे नहीं लगता कि इसके लिए कोई फ़ंक्शन है। मैं एफ़िन ट्रांसफॉर्मेशन खोजने के लिए एक फ़ंक्शन पा सकता हूं, लेकिन एफ़िन ट्रांसफॉर्मेशन में स्केलिंग शामिल है, और मैं केवल रोटेशन + अनुवाद पर विचार करना चाहता हूं।

कल्पना कीजिए कि मेरे पास 2 डी में अंक के दो सेट हैं - मान लें कि प्रत्येक सेट में बिल्कुल 50 अंक हैं।

उदा। सेट ए = {x1, y1, x2, y2, ..., x50, y50}

सेट बी = {x1 ', y1', x2 ', y2', ..., x50 ', y50'}

मैं रोटेशन और अनुवाद संयोजन ढूंढना चाहता हूं जो सेट बी पर सेट ए मैप करने के सबसे नज़दीकी हो जाता है। मुझे लगता है कि मैं बी में बी और संबंधित बिंदुओं के बीच औसत दूरी को कम करने के रूप में "निकटतम" परिभाषित करता हूं, औसत को कम करता है दूरी (x1, y1) और (x1 ', y1'), आदि

मुझे लगता है कि मैं सभी संभावित अनुवादों और घूर्णनों का परीक्षण करने के लिए ब्रूट फोर्स का उपयोग कर सकता हूं लेकिन यह बेहद अक्षम होगा। क्या किसी को एक आसान तरीका पता है?

धन्यवाद!

Answer 1

यह समस्या निकटता मैट्रिक्स (बिंदुओं के जोड़ों के बीच दूरी) के एकवचन मूल्य अपघटन के संदर्भ में एक बहुत ही सुरुचिपूर्ण समाधान है। इस नाम का नाम orthogonal Procrustes problem है, ग्रीक किंवदंती के बाद एक ऐसे साथी के बारे में जिसने यात्रियों को एक बिस्तर दिया जो किसी के लिए फिट होगा।

समाधान निकटतम ऑर्थोगोनल मैट्रिक्स को किसी दिए गए (आवश्यक रूप से ऑर्थोगोनल) मैट्रिक्स में खोजने से आता है।

Answer 2

जिस तरह से मैं एक्सेल में ऐसा करता हूं वह बिंदुओं का प्रतिनिधित्व करने वाले कुछ कॉलम बनाना है। एक सेट के घूर्णन/अनुवाद का प्रतिनिधित्व करने वाले कक्ष (घुमाए जाने और उनमें से दोनों का अनुवाद करने की आवश्यकता नहीं है)। फिर उन बिंदुओं का प्रतिनिधित्व करने वाले कॉलम घूर्णन/अनुवादित होते हैं।
फिर घूर्णन/अनुवादित बिंदुओं के बिंदुओं के बीच की दूरी के लिए एक और कॉलम।
फिर अंक के बीच की दूरी के योग का एक सेल। अंत में, रोटेशन और अनुवाद कक्षों को अनुकूलित करने के लिए सॉल्वर का उपयोग करें।

Answer 3

यदि आप कुछ रोटेशन को ठीक करते हैं तो आप ternary search का उपयोग कर उत्तर प्राप्त कर सकते हैं। एक्स में खोज चलाएं और प्रत्येक परीक्षण एक्स के लिए सर्वोत्तम मूल्य प्राप्त करने के लिए इसे y में चलाएं। यह आपको सही उत्तर देगा क्योंकि फ़ंक्शन (संबंधित दूरी का योग) उत्तल है (यह किसी भी पंक्ति में फ़ंक्शन का प्रतिबंध एक आयामी उत्तल कार्य है, और अंतिम मानक तथ्य है: यह एक मानक तथ्य है: कई उत्तल कार्यों का योग उत्तल है)। कोण पर बलपूर्वक बल के बजाय मैं टर्नरी खोज के आधार पर ऐसी विधि का प्रस्ताव दे सकता हूं। कुछ बहुत बड़े चरण एस चुनें। प्रत्येक कोण के लिए लक्ष्य फ़ंक्शन की गणना करें (0, एस, 2 एस, ...)। फिर, यदि एस पर्याप्त छोटा है, तो हम कुछ सेगमेंट (iS, (i + 1) एस) को विचार से बाहर कर सकते हैं। अर्थात् कोणों के साथ काम के अपेक्षाकृत बड़े मूल्य वाले आईएस और (i + 1) एस। ध्यान से लागू किया जा रहा है यह एक जवाब दे सकता है और इसे बलपूर्वक बल से तेज कर सकता है।