ध्रुवीय के लिए फास्ट एल्गोरिदम -> कार्टेशियन रूपांतरण

Question

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

मिनट {(th_vec - theta)^2 + (रेंज - आर)^2}

यह बाहरी नेस्टेड फॉर-लूप के अंदर एक नेस्टेड फॉर-लूप देता है, इसलिए मेरे पास ओ (एन^4) की जटिलता है। एक 512x512 छवि पूर्ण करने के लिए पूरे मिनट का उपयोग करती है। बेशक, इस तरह की जटिलता का उपयोग नहीं किया जा सकता है, इसलिए मुझे आश्चर्य है कि अगर कोई ऐसा करने के लिए किसी भी तेजी से एल्गोरिदम के बारे में जानता है?

मेरे पास छवि है, और दो वैक्टर हैं। छवि का एक्स-अक्ष कोण है, जबकि छवि का वाई-अक्ष केंद्र से लंबाई है। कोण 0-2pi से हमेशा होता है, और सीमा 0 से r_max तक जाती है।

अग्रिम धन्यवाद।

संपादित करें: सीमा 0 से r_max तक जाती है, नहीं -r_max से r_max जैसा कि यह पहले खड़ा था। मैं देखता हूं कि कुछ गलतफहमी हैं। मैंने सामान्य, व्यस्त, रूपांतरण का उपयोग किया है;

 

r=sqrt(x^2 + y^2); 
theta=atan2(y,x); 
 

समस्या मैं पहली बार, एक्स और एक्स के लिए y मान 'और वाई' मान परिवर्तित करने के लिए के बाद से ग्रिड जिसके परिणामस्वरूप छवि में r_max को -r_max से है कि है, लेकिन डेटा में पिक्सेल में। तो मेरे पास 512x512 छवि है, लेकिन r_max 3.512 की तरह कुछ हो सकता है। इसलिए मुझे प्रत्येक पिक्सेल मान को ग्रिड मान में परिवर्तित करना है, फिर आर और थेटा मान खोजें। जब मुझे आर और थेटा मान मिलते हैं तो मुझे दो छवियों, रेंज और th_vec को चलाने के लिए, मूल छवि में पिक्सेल खोजने के लिए,

मिनट {(रेंज - आर)^2 + (th_vec - theta)^2}

यह मैं हूँ, O (n^4) की एक जटिलता देता है के बाद से th_vec और सीमा वैक्टर छवि के रूप में एक ही आकार के होते हैं। तो अगर मेरे पास 512x512 तत्वों का स्क्वायर मैट्रिक्स है, तो मुझे 68 6819196 636 तत्वों को चलाने की ज़रूरत है, जो कि धीमा है। तो मैं सोच रहा हूं कि एक तेज एल्गोरिदम है या नहीं? मैं इनपुट डेटा को बदल सकते हैं नहीं है, इसलिए जहाँ तक मुझे पता है, यह यह करने के लिए यदि आप ट्राईऐन्ग्युलेशंस और सामान के साथ शुरू नहीं करते हैं एक ही रास्ता है, लेकिन इस स्मृति के समय में महंगा है।

Answer 1

के बारे में

x=r*cos(angle) 
y=r*sin(angle) 

यह ध्रुवीय से कार्तीय को परिवर्तित करने का मानक तरीका है, और जब तक आप तालिका देखने के कुछ प्रकार का उपयोग करने के लिए जा रहे हैं, वहाँ वास्तव में एक तेजी से विकल्प नहीं है कैसे।

संपादित करें: wrang wrang का एक अच्छा बिंदु है। आप कार्तीय में एक छवि के लिए ध्रुवीय निर्देशांक I(angle, r) में एक छवि को बदलने के लिए प्रयास कर रहे हैं निर्देशांक I_new(x, y), आप निश्चित रूप से उलटा परिवर्तन का उपयोग कर बेहतर कर रहे हैं, इस प्रकार है:

for x=1,...,width 
    for y=1,...,height 
     angle=atan2(y, x) 
     r=sqrt(x^2+y^2) 
     I_new(x, y)=I(angle, r) 
    end 
end 

एक नियम के रूप में, angle और r नहीं पूर्णांक होना है, तो आप छवि I में प्रक्षेप किसी तरह का क्या करना है। ऐसा करने का सबसे आसान तरीका बस angle और r के दौर में है; यह आपको nearest-neighbour interpolation देगा। आप बेहतर गुणवत्ता की जरूरत है, प्रक्षेप जैसे bilinear या bicubic प्रक्षेप की और अधिक परिष्कृत प्रकार की कोशिश करो।

Answer 2

यदि आपको चिकनाई की परवाह नहीं है, तो आप प्रत्येक गंतव्य कार्टेशियन पिक्सेल समन्वय के लिए ध्रुवीय समन्वय की गणना क्यों नहीं करते हैं और रंग मान पढ़ते हैं? http://en.wikipedia.org/wiki/Polar_coordinate_system#Converting_between_polar_and_Cartesian_coordinates देखें यदि आपको ऐसा करने में मदद की ज़रूरत है।

Answer 3

यदि आपके ग्रिड को ध्रुवीय निर्देशांक के संबंध में समान रूप से विभाजित किया गया है तो आपके एल्गोरिदम को ओ (एन^2) में घटाया जा सकता है यदि आप इस तथ्य का लाभ उठाते हैं कि निकटतम बिंदु (आर, थेटा) एक होगा ग्रिड तत्व के चार कोनों जिसमें यह निहित है।

अधिक सामान्य मामले में जहां ग्रिड आर और थेटा आयामों के मनमाने ढंग से विभाजन का उत्पाद है, जो ओ ((एन लॉग एन)^2 में बढ़ सकता है) यदि आपको बिंदु के स्थान की खोज करना है प्रत्येक विभाजन में। हालांकि, अगर विभाजन व्यवस्थित रूप से निर्मित किए गए थे, तो आप ओ (एन^2) पर वापस जाने में सक्षम होना चाहिए।

Answer 4

आप ध्रुवीय छवि मानचित्र में प्रत्येक पिक्सेल से अधिक लूप और फिर कार्तीय छवि विमान में जिसके परिणामस्वरूप चाप खंड प्रस्तुत करना सकता है:

polar to cartesian conversion http://img24.imageshack.us/img24/4635/polartocartesian.png

const float dR = 2*r_max/polar_image_height; 
const float dA = 2*pi/polar_image_width; 

float angle; 
float radius; 
for (int polar_x = 0; polar_x < polar_image_width; polar_x++) 
{ 
    for (int polar_y = 0; polar_y < polar_image_height; polar_y++) 
    { 
     angle = polar_x * dA; 
     radius = polar_y * dR - r_max; 
     DrawArcSection(radius, radius+dR, angle, angle+dA); 
    } 
} 

कई ड्राइंग पुस्तकालयों में निर्मित ड्राइंग के लिए कार्य करता है कि चाप खंड, लेकिन आप हमेशा सिर्फ यह एक साधारण बहुभुज के साथ अनुमानित सकता है:

void DrawArcSection(float minRadius, float maxRadius, 
        float minAngle, float maxAngle) 
{ 
    point P1 = MakePoint(minRadius * cos(minAngle) + image_width/2, 
         minRadius * sin(minAngle) + image_height/2); 
    point P2 = MakePoint(minRadius * cos(maxAngle) + image_width/2, 
         minRadius * sin(maxAngle) + image_height/2); 
    point P3 = MakePoint(maxRadius * cos(minAngle) + image_width/2, 
         maxRadius * sin(minAngle) + image_height/2); 
    point P3 = MakePoint(maxRadius * cos(maxAngle) + image_width/2, 
         maxRadius * sin(maxAngle) + image_height/2); 

    DrawPolygon(P1, P2, P3, P4); 
} 

Answer 5

मेमोरी में विफल रहता है, लेकिन हो सकता है इस एल्गोरिदम का एक तेज़ संस्करण जिसमें एफएफटी शामिल है। एक बार एक समय पर मैंने मेडिकल इमेजिंग पर एक कक्षा ली और ऐसा लगता है कि इस तरह की चीजें पॉप-अप की गई हैं जब सीटी स्कैन को अप्रतिबंधित/रास्टराइजिंग करते हैं। खोज करने के लिए कुछ खोजशब्द रेडॉन ट्रांसफॉर्म, फ़िल्टर किए गए बैकप्रोजेक्शन एल्गोरिदम और सीटी स्कैन होंगे। मैंने इसे विकिपीडिया पर संक्षेप में देखा और कुछ भी बाहर नहीं निकला, लेकिन शायद एक और गहन समीक्षा कुछ सोने को बदल देगी।

Answer 6

हे (एन लॉग (एन)) कलन विधि:

• सरणी एस निकटतम स्रोत (ध्रुवीय) कार्तीय coord प्रति coord के लिए इस्तेमाल किया जाएगा।
• एस "प्रारंभिक अभी तक" मान से भरा प्रारंभ नहीं होता है। (पायथन: कोई नहीं, हास्केल: कुछ भी नहीं, आदि)
• ओ (एन) - अपने सभी ध्रुवीय निर्देशांक Iterate।
  • अनुवाद कार्तीय coord को
  • अपने गंतव्य छवि में निकटतम कार्तीय coord का पता लगाएं।(गोलाई और लागू करने के सीमाओं से) इस के साथ एस में प्रासंगिक सेल में
  • भरण समन्वय
• हे (एन लॉग (एन)) - एक संशोधित डिज्कस्ट्रा एल्गोरिथ्म के लिए नीचे बताए करें:
  • एस की सभी कोशिकाओं नोड्स
  • सेल की पड़ोसियों उन शतरंज करने के लिए स्थानांतरित कर सकते हैं में राजा रहे हैं:
  • "ग्राफ़" हमारे खोज एल्गोरिथ्म के लिए इस प्रकार है यह
  • को ध्रुवीय coord इसकी ओर इशारा करते के अछूते कार्तीय coord से एक सेल के "स्कोर" अगर यह प्रारंभ नहीं किया गया है अनंत है, और दूरी सेल के एक पड़ोसी को अपडेट करते समय से एन हम (डिज्कस्ट्रा में लेकिन की तरह, सिर्फ अगर यह अपनी वर्तमान स्कोर की तुलना में अपने स्कोर को बेहतर बनाता है) उस में सेल एन से मूल्य डाल
  • प्रारंभिक बिंदु के रूप में ऊपर

Answer 7

तो वर्णित सरणी प्रारंभ s है आपके सभी छवियां 512x512 हैं तो मैं एक लुकअप टेबल का उपयोग करूंगा जो आपकी ध्रुवीय छवि में पिक्सेल के भारित सेट को कार्टेशियन छवि में मानचित्रित करे। यह बहुत काम है, लेकिन आपकी अंतिम गणना ओ (एन^2) बनाता है। एक lut एक विकल्प नहीं है, तो मैं का उपयोग करेंगे:

x=r*cos(angle) 
y=r*sin(angle) 

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