HeadlinesBriefing favicon HeadlinesBriefing.com

N स्क्वायर्ड पिज्जा समस्या: 3D स्कैन मैचिंग मेमोरी खतरे

Towards Data Science •
×

एक 12 इंच पिज्जा 8 इंच वाले पिज्जे से आधा अधिक नहीं होता। यह 2.25 गुना अधिक होता है। ऐसा इसलिए है क्योंकि पिज्जा का क्षेत्रफल उसकी त्रिज्या के वर्ग का अनुसरण करता है। लोगों को आम तौर पर क्षेत्रफल, या किसी भी चीज़ जो उसकी रैखिक सीमाओं से तेज़ी से बढ़ती है, के बारे में खराब अंतर्ज्ञान होता है। यही कारण है कि पिज्जेरिया व्यास के अनुसार मूल्य निर्धारित करते हैं और ग्राहक विश्वसनीय रूप से ऐसे पिज्जे खरीदते हैं जो वे खत्म नहीं कर सकते। अंतर्ज्ञान की यही विफलता एक ग्राहक के 3D स्कैन-मैचिंग पाइपलाइन में लगभग एक वर्ष तक मौजूद थी। इसने उन्हें बेड़े में हर वर्कर पर मेमोरी दोगुनी खर्च करवाई। स्कोरिंग कोड में कहीं एक ऐसी तालिका थी जिसमें प्रत्येक तत्व के लिए एक पंक्ति और एक कॉलम था। उस कोड को पढ़ने वाला हर कोई एक सूची देखता था जब उन्हें एक वर्ग देखना चाहिए था। पाइपलाइन दो सतह स्कैन को संरेखित करती है, एक को दूसरे से घटाती है, और जो बचता है उसकी जांच करती है। यदि दोनों स्कैन एक ही वस्तु के हैं तो बचा हुआ कुछ नहीं होता। स्कैनर के एक वर्ग की एक ज्ञात विफलता मोड है: जहां वस्तु का एक सपाट चेहरा होता है, स्कैनर कभी-कभी इसके बजाय एक उथला पिरामिड रिकॉर्ड करता है। डेटा में छोड़ दिए जाने पर, वे पिरामिड वास्तविक ज्यामितीय अंतर की तरह दिखते हैं और एक सच्चे मैच को अस्वीकार कर देते हैं। इसलिए इससे पहले कि हम दो वस्तुओं को मैचिंग के रूप में चिह्नित करें, हम जांचते हैं कि बचा हुआ शेल पिरामिड के आकार का है या नहीं। यदि है, तो पिरामिड के टुकड़ों को वस्तुओं से हटा दिया जाता है, बजाय इसे मैच के साक्ष्य के रूप में माने जाने के। पिरामिड का पता लगाने का अर्थ इसके सपाट आधार को खोजना है, और स्कोरर सतह अभिविन्यास को देखकर आधार को पाता है। मेश पर प्रत्येक त्रिभुज का एक नॉर्मल (त्रिभुज के तल के लंबवत दिशा की एक इकाई) होता है और सपाट आधार के सभी त्रिभुज लगभग एक ही दिशा में मुख करते हैं। स्कोरर नॉर्मल को क्लस्टर में समूहबद्ध करता है। फिर यह मापता है कि प्रत्येक क्लस्टर कितना फैला हुआ है। सबसे कसा हुआ क्लस्टर आधार उम्मीदवार है, और यदि इसका फैलाव एक सीमा से नीचे है तो आधार स्वीकार कर लिया जाता है। फैलाव वह जगह थी जहां वर्ग निवास करता था। इसे क्लस्टर में हर जोड़ी के नॉर्मल के बीच कोसाइन के विचरण के रूप में परिभाषित किया गया था। यह फैलाव का एक बिल्कुल उचित माप है, और कोसाइन का नियमित रूप से वेक्टर की तुलना के लिए उपयोग किया जाता है क्योंकि वे तेज़, गणना में आसान और स्केल अपरिवर्तनीय हैं। हालांकि प्रत्येक क्लस्टर के लिए कॉल ने कोसाइन की एक N * N तालिका बनाई। यदि क्लस्टर बड़े हैं, जैसे सपाट अतिव्यापी सतहों पर, तो इसके परिणामस्वरूप एक घनी तालिका बनती है जो संभावित रूप से प्रत्येक संगत नॉर्मल की तुलना करती है। सबसे खराब स्थिति में, तालिका एक वर्ग आव्यूह बन जाती है। यह एक समस्या है क्योंकि इसके लिए बहुत अधिक मेमोरी की आवश्यकता होती है, और सबसे खराब स्थिति में आवश्यक मेमोरी एकल कोसाइन तुलना के लिए आवश्यक मेमोरी का N^2 गुना है। इसका क्या मतलब था अधिकांश तुलनाओं में N छोटा था और किसी ने ध्यान नहीं दिया। एक ही वस्तु के दो स्कैन के बीच बचा हुआ शेल पतला होता है। यह कई छोटे टुकड़ों में टूट जाता है, और प्रत्येक टुकड़े में कुछ सौ नॉर्मल होते हैं। कुछ सौ का वर्ग कुछ भी नहीं है। अपवाद वह स्थिति थी जिसे पाइपलाइन सबसे अधिक सही पाना चाहता था: अलग-अलग स्कैनर द्वारा लिए गए एक ही वस्तु के दो स्कैन। घटाव कई शेल के बजाय एक सतत पतला शेल छोड़ता है। चीजों को और खराब बनाते हुए, शेल सतहें लगभग समानांतर थीं। इसके परिणामस्वरूप एक क्लस्टर और उच्च समानता की एक घनी फैलाव तालिका बनी। प्रति प्रविष्टि आठ बाइट्स पर, उच्च दसियों हज़ार में एक क्लस्टर पर एक तालिका अपने आप में कई गीगाबाइट है। उनमें से दो, साथ ही रास्ते में लाइब्रेरी द्वारा ली गई कार्य प्रतियां, हमारे द्वारा प्रोफाइल की गई सबसे खराब तुलना में लगभग पंद्रह गीगाबाइट तक पहुंचीं। उस एक तुलना ने बेड़े में हर वर्कर के लिए मेमोरी की न्यूनतम सीमा निर्धारित कर दी। हर संरेखण कार्य को इसे जीवित रहने के लिए पर्याप्त बड़े स्लॉट में प्रावधानित किया गया, जो लगभग विशिष्ट कार्य की आवश्यकता से दोगुना था।