दूरी परिवर्तन के लिए सबसे तेज़ उपलब्ध एल्गोरिदम

Question

मैं दूरी परिवर्तन के लिए सबसे तेज़ उपलब्ध एल्गोरिदम खोज रहा हूं।

इस साइट http://homepages.inf.ed.ac.uk/rbf/HIPR2/distance.htm के अनुसार, यह बताता है: "दूरी को बदलने केवल दो गुजरता (जैसे Rosenfeld और Pfaltz 1968) में चतुर एल्गोरिदम का उपयोग करते अधिक कुशलता से गणना की जा सकती।"

चारों ओर खोजना, मैंने पाया: "रोसेनफेल्ड, ए और पफॉल्टज़, जे एल। 1 9 68. डिजिटल पिक्चर्स पर दूरस्थ कार्य। पैटर्न पहचान, 1, 33-61।"

लेकिन मेरा मानना ​​है कि हमारे पास 1 9 68 में पहले से बेहतर और तेज़ एल्गोरिदम होना चाहिए? वास्तव में, मुझे 1 9 68 से स्रोत नहीं मिला, इसलिए किसी भी मदद की अत्यधिक सराहना की जाती है।

Answer 1

दूरी कार्यों की गणना करने पर बहुत से नए काम हैं।

• Fast marching algorithms that originally came from Tsitsiklis (not Sethian like Wikipedia says). इसके लिए कार्यान्वयन के टन उपलब्ध हैं।
• Fast sweeping algorithms from Zhao
• O(n) (approximate) fast marching by Yatziv

वैसे, अगर तुम सच में Rosenfeld द्वारा काम के बजाय इन उपयोग करने के लिए, विशेष रूप से जब आप बाधाओं की उपस्थिति में दूरी की गणना करना चाहते हैं चाहते हैं।

Answer 2

ओपनसीवी लाइब्रेरी इसके अनुमानित cv::distanceTransform के लिए उपयोग करता है एक एल्गोरिदम कार्य करता है जो छवि को ऊपर बाएं से नीचे दाएं और पीछे से गुजरता है। एल्गोरिदम का वर्णन "डिजिटल छवियों में दूरी परिवर्तनों" में गनिला बोरफोर्स (कम्प्यूट। विजन ग्राफ। छवि प्रक्रिया 34 3, पीपी 344-371, 1 9 86) से वर्णित है।

एल्गोरिदम कुछ मूल कूद (क्षैतिज, लंबवत, विकर्ण और नाइट चाल) के संयोजन के माध्यम से दूरी की गणना करता है। प्रत्येक कूद लागत खर्च करता है। निम्नलिखित तालिका विभिन्न कूदों के लिए लागत दिखाती है।

+------+------+------+------+------+ 
| 2.8 |2.1969| 2 |2.1969| 2.8 | 
+------+------+------+------+------+ 
|2.1969| 1.4 | 1 | 1.4 |2.1969| 
+------+------+------+------+------+ 
| 2 | 1 | 0 | 1 | 2 | 
+------+------+------+------+------+ 
|2.1969| 1.4 | 1 | 1.4 |2.1969| 
+------+------+------+------+------+ 
| 2.8 |2.1969| 2 |2.1969| 2.8 | 
+------+------+------+------+------+ 

एक पिक्सेल से दूसरी दूरी की दूरी आवश्यक कूदों की लागत का योग है। निम्न छवि 0-कोशिकाओं से दूरी को एक दूसरे सेल तक दिखाती है। तीर कुछ कोशिकाओं के लिए रास्ता दिखा रहे हैं। रंगीन संख्याएं सटीक (यूक्लिडियन) दूरी को प्रतिबिंबित करती हैं।

एल्गोरिथ्म इस तरह काम करता है: के बाद मुखौटा

+------+------+------+ 
| 0 | 1 | 2 | 
+------+------+------+ 
| 1 | 1.4 |2.1969| 
+------+------+------+ 
| 2 |2.1969| 2.8 | 
+------+------+------+ 

नीचे सही करने के लिए छवि के शीर्ष बाएं से ले जाया जाता है। इस पास के दौरान, मास्क की सीमाओं के अंदर स्थित कोशिकाएं या तो अपना मान रखती हैं (यदि यह ज्ञात और छोटी है) या वे मास्क-वैल्यू और सेल-वैल्यू (यदि यह ज्ञात है) को सेल से जोड़कर गणना की जाती है मास्क -0-सेल के नीचे। उसके बाद, नीचे दाएं से ऊपर बाईं ओर एक दूसरा पास (एक लंबवत और क्षैतिज फ़्लिप मास्क के साथ) किया जाता है। दूसरे पास के बाद दूरी की गणना की जाती है।

Answer 3

इस पत्र की समीक्षा में जाना जाता सटीक दूरी एल्गोरिदम को बदलने:

"2 डी इयूक्लिडियन दूरी को बदलने एल्गोरिदम: एक तुलनात्मक सर्वेक्षण"
http://liu.diva-portal.org/smash/get/diva2:23335/FULLTEXT01

सबसे तेजी से सटीक दूरी को बदलने Meijster से है:

" रैखिक समय में कंप्यूटिंग दूरी परिवर्तन के लिए एक सामान्य एल्गोरिदम। "
http://fab.cba.mit.edu/classes/S62.12/docs/Meijster_distance.pdf

एल्गोरिदम का डिज़ाइन समानांतर गणना के लिए विशेष रूप से उपयुक्त है। उनके कागज "में

https://github.com/vinniefalco/LayerEffects

Answer 4

Felzenszwalb और Huttenlocher एक सुरुचिपूर्ण एल्गोरिथ्म सही है कि मौजूद है और हे (एन):

यह जो फ़ोटोशॉप के" परत शैली "का अनुकरण करने की कोशिश करता है मेरी खुला स्रोत पुस्तकालय में कार्यान्वित किया जाता है नमूना कार्यों के दूरस्थ परिवर्तन "उपलब्ध here। वे इस तथ्य का फायदा उठाते हैं कि यूक्लिडियन दूरी परिवर्तन का वर्ग एक पैराबोला है जिसे प्रत्येक आयाम में स्वतंत्र रूप से मूल्यांकन किया जा सकता है।

स्रोत कोड भी available है।

Answer 5

मैंने विनी के जवाब में उद्धृत मीजस्टर ओ (एन) विधि लागू की है। "रैखिक समय में कंप्यूटिंग दूरी परिवर्तन के लिए एक सामान्य एल्गोरिदम।" http://fab.cba.mit.edu/classes/S62.12/docs/Meijster_distance.pdf

अच्छी बात यह है कि इसे प्रत्येक पिक्सेल लाइन को स्वतंत्र रूप से कंप्यूटिंग करने के लिए बहुत ही कुशलतापूर्वक समांतर किया जा सकता है (यह एक अलग करने योग्य विधि है)। 12 सीपीयू कोर पर चल रहा है, कुछ सेकंड में 1000^3 वॉल्यूमेट्रिक छवि गणना का दूरी क्षेत्र।

2012 से डेटिंग (बीडब्ल्यू 1024 के उत्तर में उद्धृत) फ़ेलज़ेंज़वाल और हटनटेलर "सैंपल फ़ंक्शंस के दूरस्थ रूपांतरण" का समाधान बिल्कुल उसी विचार पर आधारित है। दिलचस्प बात यह है कि वे 12 साल पहले मेजस्टर के काम का हवाला देते नहीं हैं।