कई बिंदुओं के लिए फास्ट प्लेन फिटिंग

Question

मैं ~ 6-10k 3 डी पॉइंट्स के सेट पर एक विमान फिट करने के लिए देख रहा हूं। मैं जितनी जल्दी हो सके इसे करने की कोशिश कर रहा हूं, और सटीकता सबसे ज्यादा चिंता नहीं है (स्पष्ट रूप से विमान किसी भी कार्डिनल अक्ष में + -10 डिग्री से बंद हो सकता है)।

मेरा वर्तमान दृष्टिकोण सबसे अच्छा फिट का उपयोग करना है, लेकिन यह अविश्वसनीय रूप से धीमा है (मैं एल्गोरिदम चलाने पर हर बार लगभग 10-50k बार की दर से विमान निकालने की उम्मीद कर रहा हूं, और इस दर पर यह खत्म हो जाएगा हफ्तों में, घंटों के विपरीत) क्योंकि यह 6000 अंक के सभी संभावित संयोजनों पर काम करता है, इसलिए ~ 35,000,000,000 पुनरावृत्तियों, और स्पष्ट रूप से इसकी आवश्यकता से मुझे बहुत अधिक सटीकता है।

क्या कोई भी कमजोर विमान-फिटिंग तकनीकों के बारे में जानता है जो मेरे एल्गोरिदम को काफी तेज़ी से बढ़ा सकते हैं?

संपादित करें:

मैं हर संभव 3 डी कोण पर विमानों बनाकर ~ 42k के लिए नीचे पुनरावृत्तियों की संख्या पाने में कामयाब रहे है (5 डिग्री प्रत्येक समय के माध्यम से कदम) और खोजने के लिए इन के खिलाफ मौजूदा अंक का परीक्षण मेरे पास बिंदुओं के लिए विमानों को फिट करने के बजाय सबसे अच्छा विमान है।

मुझे यकीन है कि विभाजित और जीतने से यहां कुछ हासिल किया जा सकता है, हालांकि मुझे चिंता है कि मैं सीधे सबसे अच्छे विमान से कूद सकता हूं।

Answer 1

का प्रयोग करें, और एक आव्यूह गुणन के रूप में समीकरण लिखें:

griddata से उदाहरण लें। P है अपने अज्ञात 4x1 [A;B;C;D]

g = [x y z 1]; % represent a point as an augmented row vector 
g*P = 0;  % this point is on the plane 

अब आपके सभी वास्तविक अंक, एक Nx4 मैट्रिक्स G को यह का विस्तार करें। नतीजा अब बिल्कुल 0 नहीं है, यह वह त्रुटि है जिसे आप कम करने की कोशिश कर रहे हैं।

G*P = E; % E is a Nx1 vector 

तो क्या आप चाहते हैं जी के अशक्त अंतरिक्ष, SVD से पाया जा सकता है के लिए निकटतम वेक्टर है। आइए परीक्षण करें:

% Generate some test data 
A = 2; 
B = 3; 
C = 2.5; 
D = -1; 

G = 10*rand(100, 2); % x and y test points 
% compute z from plane, add noise (zero-mean!) 
G(:,3) = -(A*G(:,1) + B*G(:,2) + D)/C + 0.1*randn(100,1); 

G(:,4) = ones(100,1); % augment your matrix 

[u s v] = svd(G, 0); 
P = v(:,4);    % Last column is your plane equation 

ठीक है, याद रखें कि पी स्केलर द्वारा भिन्न हो सकता है। तो बस पता चलता है कि हम से मेल खाते हैं:

scalar = 2*P./P(1); 
P./scalar 

ans = 2,0000 3,0038 2,5037 -0,9997

Answer 2

ऐसा लगता है कि griddata आप जो चाहते हैं हो सकता है। लिंक में इसका एक उदाहरण है।

यदि यह काम नहीं करता है, तो MATLAB फ़ाइल एक्सचेंज पर gridfit देखें। यह griddata से अधिक सामान्य मामले से मेल खाता है।

शायद आप अपनी खुद की सतह फिटिंग रोलिंग नहीं करना चाहते हैं, क्योंकि वहाँ कई अच्छी तरह से प्रलेखित उपकरण हैं। मानक विमान समीकरण Ax + By + Cz + D = 0

x = % some values 
y = % some values 
z = % function values to fit to 

ti = % this range should probably be greater than or equal to your x,y test values 
[xq,yq] = meshgrid(ti,ti); 
zq = griddata(x,y,z,xq,yq,'linear'); % NOTE: linear will fit to a plane! 
Plot the gridded data along with the scattered data. 

mesh(xq,yq,zq), hold 
plot3(x,y,z,'o'), hold off 

Answer 3

आप जॉन डी 'Errico द्वारा consolidator कोशिश कर सकते हैं। यह किसी दिए गए सहिष्णुता के भीतर बिंदुओं को जोड़ता है, इससे डेटा की मात्रा को कम करने और गति में वृद्धि करने की अनुमति मिल जाएगी।आप जॉन के gridfit फ़ंक्शन को भी देख सकते हैं जो आमतौर पर griddata

Answer 4

कंप्यूटर दृष्टि में आपके मामले में RANSAC या MSAC का उपयोग करने का एक मानक तरीका है;

1. विमान है कि विमान को अंक के सभी के लिए 3 अंक
2. योग त्रुटियों (विमान के लिए दूरी) द्वारा परिभाषित की गणना आबादी
3. से 3 यादृच्छिक अंक ले लो।
4. 3 अंक रखें जो सबसे छोटी त्रुटियों को दिखाते हैं (और सीमा के भीतर गिरते हैं)। //www.mathworks:
5. दोहराएँ एन पुनरावृत्तियों (? देख RANSAC सिद्धांत एन चयन करने के लिए, मेरा सुझाव हो सकता है 50)

http://en.wikipedia.org/wiki/RANSAC