🏩 📩 ◀️ दूसरे रास्ते से घूमना। कन्वर्ट करने के लिए GPU 💺 🎬 😘

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

सीपीयू के लिए एल्गोरिदम

सबसे पहले, हम समीकरण द्वारा वांछित आंकड़ा का वर्णन करते हैं। उदाहरण के लिए, एक पंक्ति के लिए, यह y = Ax + B हो सकता है।
फिर हम तथाकथित संचायक शुरू करते हैं: समीकरण में मापदंडों की संख्या के बराबर माप की संख्या के साथ एक सरणी। हमारे मामले में - दो आयामी। हमारे पास हाफ स्पेस (इसका कम से कम हिस्सा) होगा - इसमें लाइनों को उनके मापदंडों द्वारा दर्शाया जाएगा। उदाहरण के लिए, A क्षैतिज है और B लंबवत है। साधारण स्थान में एक सीधी रेखा = हाफ स्पेस में एक बिंदु।

हम मूल छवि को द्विआधारी करते हैं, और प्रत्येक गैर-खाली बिंदु (x ₀ , y ₀ ) के लिए हम उन रेखाओं के समूह को परिभाषित करते हैं जो इस बिंदु से गुजर सकती हैं: y ₀ = Ax ₀ + B. यहाँ x ₀ और y ₀ स्थिरांक हैं, A और B चर हैं, और यह समीकरण Hough स्थान में एक रेखा को परिभाषित करता है। हमें अपनी बैटरी में इस रेखा को "आकर्षित" करने की आवश्यकता है - प्रत्येक तत्व को 1 जोड़ दें जिसके माध्यम से यह गुजरता है। इस प्रक्रिया को मतदान कहा जाता है: उन लाइनों के लिए एक डॉट वोट जो इसके माध्यम से गुजर सकती है।

नतीजतन, यह पता चलता है कि सभी बिंदुओं से सभी वोट बैटरी में एकत्र किए जाते हैं, और हम यह मान सकते हैं कि "वोट के विजेता" मूल छवि में मौजूद हैं। यहाँ, निश्चित रूप से, थ्रेशोल्ड फ़िल्टरिंग और अन्य तरीकों को लागू किया जा सकता है और अधिक से अधिक हाफ़ स्पेस में खोजने के लिए लागू किया जाना चाहिए, लेकिन मुख्य और सबसे अधिक समय लेने वाला कार्य बैटरी को भरना है।

विकिपीडिया चित्रण:

GPU मुद्दों

जीपीयू को साझा मेमोरी के साथ छोटे प्रोसेसर के कई (हजारों तक) माना जा सकता है, और, आमतौर पर, एल्गोरिदम बस साझा करते हैं: प्रत्येक प्रोसेसर को काम का एक टुकड़ा आवंटित करना। ऐसा लगता है कि हम मूल छवि को टुकड़ों में विभाजित करते हैं, प्रत्येक प्रोसेसर को अपना टुकड़ा देते हैं - और आपका काम हो गया। लेकिन नहीं, हम बैटरी को अलग नहीं कर सकते हैं: मूल छवि के प्रत्येक टुकड़े में, होफ स्पेस में किसी भी स्थान पर प्रोजेक्टिंग बिंदु दिखाई दे सकते हैं। प्रोसेसर साझा मेमोरी में नहीं लिख सकते, बस पढ़ सकते हैं - अन्यथा सिंक्रनाइज़ेशन के साथ समस्याएं होंगी। आउटपुट प्रत्येक प्रोसेसर को अपनी बैटरी देने के लिए होगा, और प्रसंस्करण के बाद, बैटरी को एक साथ जोड़ देगा। लेकिन, आपको याद है, हजारों प्रोसेसर हैं। यहां तक कि अगर बहुत स्मृति है, तो इसे आवंटित करने और संसाधित करने का समय एल्गोरिदम के समानांतर निष्पादन के लाभों को अवरुद्ध करेगा।

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

GPU के लिए एल्गोरिथ्म संशोधन

मेरा प्रारंभिक विचार यह था: क्यों न "प्रभाव के क्षेत्रों" में विभाजित किया जाए, बल्कि मूल छवि नहीं, बल्कि हाफ़ स्पेस? यही है, आइए अलग-अलग Hough स्थान में प्रत्येक बिंदु के लिए मान की गणना करें। पहली नज़र में, यह मूर्खतापूर्ण लगता है: स्रोत छवि का कोई भी बिंदु "आवाज़" दे सकता है, जिसका अर्थ है कि हमें उन सभी की जांच करनी होगी। कुल, पढ़ने के संचालन की संख्या = [मूल छवि के बिंदुओं की संख्या] x [बैटरी कोशिकाओं की संख्या] , जबकि पारंपरिक विधि में यह केवल [मूल छवि के अंकों की संख्या] है ।

लेकिन दूसरी ओर, लिखने के संचालन की संख्या संभावित रूप से कम हो जाती है - [बैटरी कोशिकाओं की संख्या] बनाम [गैर-खाली बिंदुओं की संख्या ] x [हूप स्थान में एक बिंदु की छवि की औसत लंबाई] । यदि कई गैर-खाली बिंदु हैं, तो अंतर महत्वपूर्ण है।

कुल में, अधिक रीड, कम रिकॉर्ड होते हैं, और यह अधिक सुव्यवस्थित हो जाता है। अब याद रखें कि GPU की शक्ति और क्या है। पढ़ने की गति में! वीडियो कार्ड तेज मेमोरी से लैस हैं, इसका उपयोग सीमा तक "सीधा" किया गया है - यह सब जल्द से जल्द बनावट के लक्ष्य के साथ है। सच है, यह विलंबता के अवरोध के लिए है - अनियंत्रित पढ़ा अनुरोध धीमी गति से चलता है। लेकिन हमारे पास ऐसा नहीं होगा।

दूसरा विचार। यदि हाफ़ स्पेस में "ड्रा" करना आवश्यक है - तो वीडियो कार्ड की "ड्राइंग" प्रतिभाओं का उपयोग क्यों न करें? चलो एक बनावट के रूप में आधे स्थान पर मूल छवि को ओवरले करते हैं।

यह इस तथ्य की ओर जाता है कि मेरी पद्धति में न तो OpenCL या CUDA कोड और न ही shaders की आवश्यकता है। Hough स्पेस की छवि प्राप्त करने के लिए वीडियो कार्ड को उनका समर्थन करने की आवश्यकता नहीं है। इसके लिए मूल्य गैर-सार्वभौमिकता है: व्यवहार में, ये दो अनिवार्य रूप से अलग-अलग तरीके हैं: एक सर्कल के लिए और दूसरा लाइनों के लिए। ऐसा लगता है कि "सर्कल" की विधि किसी भी बंद लाइनों और समीकरण में तीन या अधिक मापदंडों के साथ किसी भी आंकड़े पर लागू की जा सकती है, लेकिन दक्षता अलग हो सकती है।

"मंडलियों" की विधि

सर्कल को तीन मापदंडों के साथ एक समीकरण द्वारा वर्णित किया गया है - (xx ₀ ) ² + (yy ₀ ) ² = R ² । यहाँ (x ₀ , y ₀ ) केंद्र के निर्देशांक हैं, और R त्रिज्या है। हफ़ स्पेस में तीन आयाम होने चाहिए, लेकिन अब हम अपने आप को दो तक सीमित करेंगे और आर को ठीक करेंगे (उदाहरण के लिए, हम इसे जानते हैं)। इस मामले में, हम सभी को खोजने के लिए केंद्र (एस) के निर्देशांक हैं।

ऐसी प्रारंभिक छवि लें (सभी एक ही त्रिज्या के वृत्त)

और, इसे लगभग पारदर्शी बनाते हुए, हम खुद को इस प्रकार लगाते हैं:

सभी चित्र सर्कल के त्रिज्या द्वारा मूल से ऑफसेट हैं। आसन्न विस्थापन रेडी के बीच का कोण समान है। यही है, उदाहरण के लिए, छवियों के ऊपरी बाएं कोनों को वांछित के रूप में एक ही त्रिज्या के एक चक्र के चारों ओर वितरित किया जाता है।

स्पष्टता के लिए, मैंने नीचे मूल छवि का उलटा रखा और महत्वपूर्ण स्थानों को लाल रंग में चिह्नित किया।

प्रत्येक छवि का प्रत्येक सर्कल मूल छवि के संबंधित सर्कल के केंद्र से गुजरता है। इन बिंदुओं पर, वे एक-दूसरे को ओवरलैप करते हैं और एक अधिकतम चमक प्राप्त की जाती है।

यदि आप इस ऑपरेशन को 32 बार करते हैं तो क्या होता है:

और दहलीज छानने के बाद:

इस प्रकार, हमने Hough अंतरिक्ष के दो आयाम भरे। अब, त्रिज्या को अलग करके, आप आसानी से तीसरे को भर सकते हैं। और आप स्मृति में सभी 3 आयामों को जमा करने की कोशिश नहीं कर सकते हैं, लेकिन परिणामी छवि को संसाधित करते हैं, केंद्र और त्रिज्या की स्थिति को संरक्षित करते हैं और स्मृति को मुक्त करते हैं।

कोड (प्रबंधित DirectX, पूर्ण संस्करण - नीचे दिए गए लिंक से) सही ढंग से स्थित आयतों का निर्माण:

float r = (float)rAbs / targetSize; for (int i = 0; i < n; i++) { double angle = 2 * Math.PI / n * i; rectangles.Add(new TexturedRect(new Vector2(1f, 1f), new Vector2((float)(Math.Cos(angle) * r), (float)(Math.Sin(angle) * r)), new Vector2(1f, 1f), new Vector2(0f, 0f), 0)); }

सही तरीके से अल्फा पारदर्शिता सेट करने वाला कोड:

 device.RenderState.AlphaBlendEnable = true, device.RenderState.BlendFactor = (byte)(256.0 * brightness / n) device.RenderState.BlendOperation = BlendOperation.Add; device.RenderState.SourceBlend = Blend.BlendFactor; device.RenderState.DestinationBlend = Blend.One;

यहाँ rAbs वांछित त्रिज्या, brightness - चमक, n - परतों की संख्या rAbs करता है।

आप बनावट में सब कुछ प्रस्तुत कर सकते हैं

 new Microsoft.DirectX.Direct3D.Texture(device, targetSize, targetSize, 1, Usage.RenderTarget, cbGray.Checked ? Format.L8 : Format.X8R8G8B8, Pool.Default); dxPanel.RenderToTexture(new Options() { AlphaBlendEnable = true, BlendFactor = (byte)(256.0 * (tbBrightness.Value / 100.0) / n) }, rectangles);

और आप एक 3 डी बनावट और परतों के कई सेटों का उपयोग कर सकते हैं ताकि ब्याज की सभी राडियों को रेंडर किया जा सके और एक समय में तीन आयामी होफ स्पेस मिल सके (मैंने ऐसा करने की कोशिश नहीं की)।

पारदर्शिता के साथ ऐसी बारीकियां हैं कि यदि आप 8-बिट रंग और पर्याप्त रूप से बड़ी संख्या में परतों का उपयोग करते हैं, तो ब्लेंडफैक्टर 10 से कम हो जाएगा, 1 तक। यह बड़ी गोलाकार त्रुटियों को जन्म दे सकता है, और यदि आप ब्लेंडफ़ैक्टर का उपयोग करके समग्र चमक को समायोजित करते हैं, तो चमक में एक सौतेला व्यवहार बदल जाता है। हालांकि, यदि आप चमक को समायोजित नहीं करते हैं, तो समान गोलाई त्रुटियों के कारण सभी को फ़िल्टर करने के लिए थ्रेशोल्ड मान का चयन करना मुश्किल होगा। इसके अलावा, यदि आप एक छवि को ग्रे के रंगों के साथ उपयोग करते हैं, तो रंगों को नुकसान होगा, और यहां तक कि ब्लेंडफैक्टर = 1 के साथ खो जाएगा।

रेंडर टारगेट (उदाहरण के लिए, 16 या 32 बिट्स) के लिए बड़ी रंग की गहराई का उपयोग करके इस समस्या को हल किया जा सकता है, अगर वीडियो कार्ड इसका समर्थन करता है।

यहाँ एक शोर छवि पर काम करने का एक और उदाहरण है। प्रारंभिक:

परिणाम (64 परतें):

आप देख सकते हैं कि एल्गोरिथ्म सबसे अधिक संभावना उन सभी बिंदुओं पर पूछताछ नहीं करता है जो सर्कल बनाते हैं (जब तक कि सर्कल बहुत छोटा न हो)। परतों की संख्या में वृद्धि के साथ, मतदान बिंदुओं का प्रतिशत और निर्धारण की सटीकता बढ़ जाती है, लेकिन परिचालन समय भी बढ़ता है और ऊपर वर्णित समस्याएं दिखाई देती हैं।

प्रत्यक्ष विधि

अनिसोट्रोपिक फ़िल्टरिंग

स्वयं विधि के वर्णन के लिए आगे बढ़ने से पहले, आपको वीडियो कार्डों में अनीसोट्रोपिक फ़िल्टरिंग के बारे में और विस्तार से बात करने की जरूरत है। बनावट लागू करते समय, यह हो सकता है कि एक स्क्रीन पिक्सेल का रंग कई बनावट बिंदुओं (टेक्सल्स) द्वारा निर्धारित किया जाना चाहिए। यह आमतौर पर या तो तब होता है जब बहुभुज दर्शक से बहुत दूर होता है या जब बहुभुज दृढ़ता से झुका होता है (सड़क की बनावट अच्छी होती है)। और अगर पहले मामले में आप बनावट को कई प्रस्तावों के लिए पहले से स्केल कर सकते हैं, और फिर वांछित विकल्प (एमआईपी मैपिंग) ले सकते हैं, तो दूसरे में आप ऐसा नहीं कर सकते क्योंकि बनावट को "दर्शक की ओर" दोनों तरफ से बदल दिया जा सकता है।

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

अनिसोट्रोपिक फ़िल्टरिंग का अधिकतम पारंपरिक रूप से बनाए रखा स्तर 16 (जाहिरा तौर पर टेक्सल्स) है।

विधि के बारे में ही

हमारी छवि और इसे "समतल" लें, उदाहरण के लिए, लंबवत। यानी इसे पूरी तरह से एक आयत 1 पिक्सेल उच्च पर प्रस्तुत करें। आदर्श रूप से, ऊर्ध्वाधर रेखाएं बिंदुओं (मैक्सिमा) में बदल जाएंगी। बाकी सबकुछ धूमिल हो जाएगा। इस प्रकार, हमें पहले से ही एक पैरामीटर का मूल्य मिला है - यह छवि के बाएं किनारे से बिंदु (मूल छवि में लाइन तक) से दूरी है।

अब चलो छवि की एक नई प्रति लेते हैं, लेकिन चपटे होने से पहले, हम इसे एक निश्चित छोटे कोण पर घुमाते हैं, जो चित्र के केंद्र में स्थित होता है। फिर चपटा हो गया। कुछ लाइनें बिंदुओं पर जाती हैं। ये वो लाइनें होंगी जो छवि के रोटेशन के एक ही कोण पर झुकी होती हैं।

इस प्रकार, 0 से पाई तक सभी कोणों से गुजरते हुए, हमें दूसरे पैरामीटर के मान मिलते हैं - चित्र के रोटेशन का कोण। इन दो मापदंडों का उपयोग करके, आप किसी भी मूल सीधी रेखा को पुनर्स्थापित कर सकते हैं।

यह सब बनी हुई छवि का ठीक से समतल करने का प्रश्न है। यदि आप इसे सिर पर करते हैं, तो केवल शोर रहता है - अनिसोट्रोपिक फ़िल्टरिंग काम करेगा, लेकिन इसमें केवल 16 टेक्सल्स (मूल छवि के पिक्सेल) होंगे। यह बहुत कम संभावना है।

आप छवि को 16 पिक्सेल चौड़ा, प्रत्येक अलग से समतल कर सकते हैं,

और फिर उन्हें एक दूसरे के ऊपर खींचें, जैसा कि हमने सर्कल विधि में किया था। यह काम करेगा, और परिणामस्वरूप, प्रत्येक पिक्सेल को ध्यान में रखा जाएगा।

(हम मान सकते हैं कि चित्र 4 बार बढ़े हैं ताकि विवरण देखा जा सके)

यदि छवि 16 * 256 = 4096 पिक्सेल से अधिक है, तो आप इसे अधिक ऊंचाई के आयतों में काट सकते हैं, या अधिक रंग की गहराई का उपयोग कर सकते हैं। लेकिन, सबसे अधिक संभावना है, ऐसी छवि बस बनावट में फिट नहीं होती है।

कोनों में स्थित लाइनों को खोने के लिए नहीं, या एक गैर-वर्ग छवि के छोटे पक्षों के पास, आपको मूल छवि के विकर्ण के बराबर चौड़ाई के साथ रेंडर टारगेट लेने की आवश्यकता है।

वह कोड जो टेक्सचर सैंपलर सेट करता है (मैं टेक्सचर कोऑर्डिनेट्स को रोटेट करके रोटेशन करता हूं, इसलिए मुझे सैंपलर की जरूरत है ब्लैक को वापस करने के लिए अगर रोटेशन की वजह से कहीं कोई टेक्सचर नहीं है)।

 device.SamplerState[0].MinFilter = TextureFilter.Anisotropic; device.SamplerState[0].MaxAnisotropy = 16; device.SamplerState[0].AddressU = TextureAddress.Border; device.SamplerState[0].AddressV = TextureAddress.Border; device.SamplerState[0].AddressW = TextureAddress.Border; device.SamplerState[0].BorderColor = Color.Black;

आयतें बनाना

 double sourceRectPixelWidth = sourceSize / n; double targetRectPixelWidth = Math.Ceiling(sourceRectPixelWidth / anizotropy); int angleValues = (int)Math.Floor(targetSize / targetRectPixelWidth); float sourceRectWidth = (float)(sourceRectPixelWidth / sourceSize); float tarectRectWidth = (float)(targetRectPixelWidth / targetSize); for (int angleNumber = 0; angleNumber < angleValues; angleNumber++) { double angle = Math.PI / angleValues * angleNumber; float targetShift = tarectRectWidth * angleNumber; for (int sliceNumber = 0; sliceNumber < n; sliceNumber++) { float sourceShift = sourceRectWidth * sliceNumber; rectangles.Add(new TexturedRect( new Vector2(tarectRectWidth, 1f), new Vector2(targetShift, 0f), new Vector2(sourceRectWidth, 1f), new Vector2(sourceShift, 0f), (float)angle)); } }

पिछले अनुभाग की तरह ही शोर वाली छवि, लेकिन अब हम लाइनों (32 परतों, रोटेशन कोण के 512 चरणों) की तलाश कर रहे हैं:

"सर्कल" विधि का विस्तार

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

फिर, क्रमिक रूप से अंक 1, ए 2 का चयन करते हुए, समोच्च पर हम वैक्टर एओ द्वारा छवि परतों को स्थानांतरित करते हैं। यह पता चला है कि छवियों का कोण इस तरह से एक आकृति का वर्णन करता है।

इस स्थिति में, छवि के सभी भालू मिल जाएंगे - अधिकतम बिंदु मूल समोच्च के बिंदु O के अनुरूप बिंदु पर होंगे।

पारंपरिक पद्धति पर अतिरिक्त लाभ

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

उत्पादकता

सीपीयू और जीपीयू के बीच शुद्ध गिनती के प्रदर्शन की तुलना करना बहुत उचित नहीं होगा, क्योंकि जीपीयू के साथ काम करने वाले हार्ड पार्ट्स में से एक डेटा लोड और अनलोडिंग है। यह शायद ही सीपीयू में कच्चे परिणाम अपलोड करने लायक है। आप उन्हें केवल कॉम्पैक्ट करने की कोशिश कर सकते हैं, केवल पाए गए आकार के मापदंडों को उतारने के लिए, अंक नहीं। हालाँकि, डेटा संकलन भी बहुत ही चालाकी से GPU पर लागू किया जाता है, इसलिए मैं इसे अभी तक पूरा नहीं कर पाया हूं।

शुद्ध कठिन रूपांतरण प्रदर्शन। प्रवेश और निकास - 2048 * 2048, GPU - GeForce GTS250:

तुलना के लिए, OpenCV का उपयोग करके लाइन डिटेक्शन के परिणाम। इनपुट - 2048 * 2048, लाइनों के बीच 2048 चरणों का उत्पादन, सीपीयू - कोर i5 750 @ 3700Mhz।

इस समय से, 50-80 एमएस कैनी सीमा डिटेक्टर (जिसके बाद दो-रंग की छवि पहले से ही संसाधित है) पर जाती है।

निष्कर्ष: छोटी संख्या में विवरण के साथ छवियों पर लाइनों का पता लगाने में, GPU 5-20 गुना तेज है। शोर / विस्तृत छवियों पर, गति में वृद्धि 100 - 300 बार हो सकती है।

सर्किलों की पहचान की गति की तुलना करना संभव नहीं था, क्योंकि ओपनसीवी सामान्य उपयोग नहीं करता है, लेकिन पर्याप्त ढाल विधि ।

दूसरे रास्ते से घूमना। कन्वर्ट करने के लिए GPU