बड़े पैमाने पर समानांतर छवि स्थिरीकरण

प्रस्तावना

आपका दिन शुभ हो! आज मैंने आपके साथ मेरे सबसे पसंदीदा साइकिलों में से एक अंतरतम को साझा करने का फैसला किया।

मैं दूर से शुरू करूँगा - काफी समय तक मैंने चेल्याबिंस्क में एक रेडियो कारखाने में काम किया, और हमारे पास (सामान्य तौर पर, और अब एक है, मेरे पास अभी नहीं है) एक मेगा-प्रोजेक्ट था: भौतिक वस्तुओं की सुरक्षा के लिए एक ऑप्टिकल-इलेक्ट्रॉनिक मॉड्यूल। यह रोटरी इंस्टॉलेशन पर एक स्वस्थ चीज है, जिसमें सभी अवसरों के लिए तीन कैमरे हैं (रंग - दिन के उजाले, बीडब्ल्यू फोटोसेंसिटिव - गोधूलि के लिए, और एक थर्मल इमेजर - रात के अवलोकन के लिए)। ऐसा एक मॉड्यूल लिया जाता है, जिसे 50 मीटर ऊंचे टॉवर पर रखा जाता है - और आप दिन और रात में 4-5 किलोमीटर के दायरे में निगरानी रख सकते हैं। मैं विवरण नहीं लिखूंगा, उस पोस्ट के बारे में नहीं। कौन परवाह करता है - वे खुद के लिए पाएंगे।

बेशक, छवि प्रसंस्करण में कई दिलचस्प समस्याएं थीं। मैं इनमें से एक के बारे में बात करना चाहता हूं। अर्थात्, वास्तविक समय में कैमरा शेक की भरपाई के लिए बड़े पैमाने पर समानांतर कंप्यूटिंग का उपयोग कैसे करें, या SURF हमेशा उपयुक्त क्यों नहीं है। बिल्ली के लिए आपका स्वागत है।

समस्या का सार

जैसा कि मैंने पहले उल्लेख किया है - मॉड्यूल काफी उच्च टावरों पर रखे गए हैं। इतनी ऊंचाई पर तेज हवा के कारण, वे लगातार पतले झटके दे रहे हैं, और कैमरे के देखने के कोण जितना छोटा है, उतना ही ध्यान देने योग्य है। और ऑपरेटर को कैमरा छवि का निरीक्षण करना चाहिए, और लंबे समय तक (शिफ्ट)। यह बहुत कठिन है, यह तुच्छ हो सकता है। यही कारण है कि इस तरह की प्रणालियों के लिए मुख्य आवश्यकताओं में से एक तस्वीर की झटकों को कम करने के लिए एक तंत्र की उपस्थिति है। कहीं न कहीं gyro-stabilized platform इसके लिए इस्तेमाल किए जाते हैं, लेकिन हर जगह नहीं। सबसे अधिक बार, सॉफ्टवेयर स्थिरीकरण का उपयोग किया जाता है, और सबसे अधिक बार यह SURF है। लेकिन यह इसके लिए उपयुक्त नहीं है।

क्यों SURF और इसी तरह के एल्गोरिदम इसके लिए उपयुक्त नहीं हैं

क्रम में:

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

2 - प्रदर्शन। मैं विवरण में नहीं जाऊंगा, मैं केवल यह कह सकता हूं कि समय सीमा गंभीर है - एल्गोरिथ्म को 13 मिलीसेकंड से कम समय में अंतिम दो फ़्रेमों के बीच ऑफसेट खोजना चाहिए। जितना संभव हो उतना कम। SURF से, हम इसे प्राप्त करने के करीब भी नहीं थे।

3 - हस्तक्षेप। नियंत्रण बिंदुओं का विस्थापन, न कि पूरे फ्रेम का विश्लेषण किया जाता है। मिलान त्रुटियों के कारण, गलत मिलान को समाप्त करने में समस्याएं हैं, जिन्हें हल करना काफी कठिन है। एक जीवित चित्र में, यह एक दिशा या किसी अन्य में छवि के दुर्लभ "झटके" का कारण बनता है।

मेरी बाइक

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

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

मैंने एल्गोरिथ्म को "रैटल डेस्के" कहा, और इसमें 3 चरण शामिल हैं:
- एक नए फ्रेम की तैयारी
- एक खंड-अभिन्न प्रतिनिधित्व में फ्रेम का अनुवाद
- सबसे अच्छा मैच के लिए खोज

सभी तीन कदम बड़े पैमाने पर समानांतर प्रसंस्करण के लिए बहुत अच्छे हैं। मैंने इसे CUDA पर लागू किया, लेकिन, जैसा कि मैं इसे समझता हूं, यह सब FPGAs पर अच्छी तरह से लागू किया जा सकता है, उदाहरण के लिए।

नए फ्रेम की तैयारी

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

struct pixel { unsigned char R, G, B; } pixel Image[width, height]; unsigned int GSImage[width, height]; unsigned int processedImage[width, height]; for (int x = 0; x < width; x++) { for (int y = 0; y < height; y++) { GSImage[x, y] = Image[x, y].R + Image[x, y].G + Image[x, y].B; } } for (int x = 1; x < width; x++) { for (int y = 1; y < height; y++) { preprocessedImage[x, y] = 0; if (GSImage[x, y] - GSImage[x - 1, y] > threshold) preprocessedImage[x, y]++; if (GSImage[x, y] - GSImage[x, y - 1] > threshold) preprocessedImage[x, y]++; if (GSImage[x, y] - GSImage[x + 1, y] > threshold) preprocessedImage[x, y]++; if (GSImage[x, y] - GSImage[x, y + 1] > threshold) preprocessedImage[x, y]++; } } 

एक खंड-अभिन्न प्रतिनिधित्व में एक फ्रेम का अनुवाद

शायद सबसे दिलचस्प चरण। पहले आपको कुछ बिंदुओं को स्पष्ट करने की आवश्यकता है।

सबसे पहले, एक छवि का अभिन्न प्रतिनिधित्व क्या है। यह इस लेख को यहाँ पढ़कर समझा जा सकता है, अगर आपने ऊपर के लिंक से ऐसा नहीं किया है। संक्षेप में, यह एक द्वि-आयामी (हमारे मामले में) सरणी है, जिसमें निर्देशांक X और Y के साथ एक तत्व मूल सरणी के सभी तत्वों के योग के बराबर है [0..X, 0..Y]।

दूसरी बात - जिसे मैं खंड-अभिन्न प्रतिनिधित्व कहता हूं। मेरे एल्गोरिथ्म की विशेषताओं के कारण, हमें एक दो-आयामी सरणी की आवश्यकता होती है जिसमें एक निर्देशांक X और Y वाला तत्व समन्वय के साथ मूल सरणी के सभी तत्वों के योग के बराबर है [XN) .. X, (YM) .. Y], जहां N और M मनमानी संख्या हैं। एल्गोरिथ्म की गति / सटीकता अनुपात को प्रभावित करना। उदाहरण के लिए, मैंने मूल्य 15 और 15 का उपयोग किया, अर्थात्। परिणामी सरणी में तत्व मूल सरणी के 256 तत्वों (16x16 वर्ग) का योग था। हां, वास्तव में यह छवि का एक प्रकार का धुंधलापन है।

लेकिन छवि का अभिन्न प्रतिनिधित्व करने के लिए वापस। थोड़े विचार के साथ, आप समझ सकते हैं कि एक धागे में इसे निम्न प्रकार से गणना की जा सकती है:

 unsigned int Image[width, height]; unsigned int processedImage[width, height]; processedImage[0, 0] = Image[0, 0]; for (int x = 1; x < width; x++) { processedImage[x, 0] = Image[x, 0] + processedImage[x-1, 0]; } for (int y = 1; y < height; y++) { processedImage[0, y] = Image[0, y] + processedImage[0, y-1]; } for (int x = 1; x < width; x++) { for (int y = 1; y < height; y++) { processedImage[x, y] = Image[x,y]+processedImage[x-1,y]+processedImage[x,y-1]-processedImage[x-1,y-1]; } } 

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

 unsigned int Image[width, height]; unsigned int horizontalImage[width, height]; unsigned int processedImage[width, height]; //  for (int y = 0; y < height; y++) { horizontalImage[0, y] = Image[0, y]; for (int x = 1; x < width; x++) { horizontalImage[x, y] = Image[x, y] + horizontalImage[x-1, y]; } } //  for (int x = 0; x < width; x++) { processedImage[x, 0] = horizontalImage[x, 0]; for (int y = 1; y < height; y++) { processedImage[x, y] =horizontalImage[x, y] + processedImage[x, y-1]; } } 

और अब एक ही बात है, लेकिन एन = एम = 15 के साथ खंड-अभिन्न प्रतिनिधित्व के लिए:

 unsigned int Image[width, height]; unsigned int horizontalImage[width, height]; unsigned int processedImage[width, height]; //  for (int y = 0; y < height; y++) { horizontalImage[0, y] = Image[0, y]; for (int x = 1; x < 16; x++) { horizontalImage[x, y] = Image[x, y] + horizontalImage[x-1, y]; } for (int x = 16; x < width; x++) { horizontalImage[x, y] = Image[x, y] + horizontalImage[x-1, y] - Image[x-16, y]; } } //  for (int x = 0; x < width; x++) { processedImage[x, 0] = horizontalImage[x, 0] for (int y = 1; y < 16; y++) { processedImage[x, y] = horizontalImage[x, y] + processedImage[x, y-1]; } for (int y = 16; y < height; y++) { processedImage[x, y] = horizontalImage[x, y] + processedImage[x, y-1] - horizontalImage[x, y-16]; } } 

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

यह बिंदु भी विस्तार से बताने लायक है। तथ्य यह है कि इष्टतम मैच की खोज करते समय, नए के साथ पिछले फ्रेम का सटीक मिलान खोजा जाता है, और इसके विपरीत नहीं। एल्गोरिथ्म के पुनरावृत्ति को पारित करने के बाद - अगले पुनरावृत्ति के लिए, पिछले फ्रेम के बारे में डेटा रहता है, लेकिन सभी नहीं, लेकिन केवल कुछ निश्चित ब्लॉकों के मान (मेरे मामले में, 16x16 के आकार वाले)। यह गति / सटीकता अनुपात को प्रभावित करने वाला एक अन्य कारक है। कम ब्लॉक - अधिक गति, अधिक ब्लॉक - अधिक सटीकता।

विशेष रूप से, मेरे मामले में, छवि का आकार 704x576 पिक्सेल था। पिछले फ्रेम के खंड-अभिन्न प्रतिनिधित्व से, मैंने केवल 1140 खंडों (छवि के केंद्र से 38x30 ब्लॉक, अतिव्यापी नहीं, 4560 बाइट्स) के मूल्यों को छोड़ दिया। यह चित्र के रूप में स्पष्ट होगा:

यहां हमारे पास 256x256 पिक्सेल की काल्पनिक तस्वीर है। सुविधा के लिए, इसे 16x16 पिक्सल के व्यक्तिगत ब्लॉकों में विभाजित किया गया है (हालांकि खंडों के खंड-अभिन्न प्रतिनिधित्व में बहुत बड़ा है, और वे एक-दूसरे को ओवरलैप करते हैं)। केंद्र में, ब्लॉकों की एक सरणी आवंटित की जाती है, 10 से 10 टुकड़े। एल्गोरिथ्म के अगले पुनरावृत्ति में उपयोग के लिए इन ब्लॉकों के मूल्य को याद किया जाना चाहिए। कोड में, यह कुछ इस तरह दिखेगा:

 unsigned int IntegralImage[256, 256]; unsigned int NextIteration[10, 10]; for (int x = 0; x < 10; x++) { for (int y = 0; y < 10; y++) { NextIteration[x, y] = IntegralImage[(x+4)*16-1, (y+4)*16-1]; } } 

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

सबसे अच्छे मैच के लिए खोजें

लगभग सब कुछ, फिनिश लाइन। यदि एल्गोरिथ्म के माध्यम से केवल एक फ्रेम पारित किया गया था, तो इस चरण को छोड़ दिया जाना चाहिए (अब तक स्थिर करने के लिए कुछ भी नहीं है)। यदि यह पहला फ्रेम नहीं है, तो NextIteration सरणी को पिछले पुनरावृत्ति से रहना चाहिए। चूंकि यह पिछले पुनरावृत्ति से बना रहना चाहिए - इस स्तर पर इसे PrevIteration कहा जाएगा, इसे मिलाएं नहीं।

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

एक महत्वपूर्ण नोट - यह सभी संभावित पदों की जांच करने के लिए बहुत कम समझ में आता है, पिक्सल में अधिकतम अपेक्षित विचलन को स्थिर के रूप में सेट करना बेहतर होता है। उदाहरण के लिए, X और Y में प्लस या माइनस 30 पिक्सल्स।

सबसे पहले, हमें एक सरणी की आवश्यकता है जो एक या दूसरे ऑफसेट में अंतर प्रदर्शित करती है। वर्गों के साथ एक तस्वीर के लिए कोड में एक उदाहरण:

 unsigned int IntegralImage[256, 256]; unsigned int PrevIteration[10, 10]; unsigned int Differences[61, 61]; for (int X = 0; X < 61; X++) { for (int Y = 0; Y < 61; Y++) { Differences[X, Y] = 0; } } //     +-30      3721  for (int X = 0; X < 61; X++) { for (int Y = 0; Y < 61; Y++) { for (int x = 0; x < 10; x++) { for (int y = 0; y < 10; y++) { Differences[X, Y] += abs(PrevIteration[x,y]-IntegralImage[(x+4)*16-31+X,(y+4)*16-31+Y]; } } } } 

वह सब है। यह केवल सरणी अंतर में न्यूनतम तत्व खोजने के लिए बनी हुई है। यदि यह [0, 30] है - तो नया फ्रेम 30 पिक्सल को दाईं ओर स्थानांतरित कर दिया है। अगर [60, 30] - तो बाईं ओर 30 पिक्सेल।

परिणाम

इस लेख में, मैंने कुछ भी अभिनव या बहुत स्पष्ट नहीं कहा। लेकिन यह इस विषय पर मेरे अनुभव का एक महत्वपूर्ण हिस्सा है, और मुझे पूरी उम्मीद है कि यह किसी के लिए उपयोगी होगा। लेख लंबा और भ्रामक निकला, इसलिए कहीं न कहीं स्पष्ट गलतियाँ हैं, या मैंने स्पष्ट रूप से कुछ स्पष्ट नहीं किया है - मुझे प्रतिक्रिया, रचनात्मक आलोचना और किसी अन्य प्रतिक्रिया को प्राप्त करने में खुशी होगी। अंत में महारत हासिल करने वालों को बहुत धन्यवाद।

मेरे कार्यान्वयन के लिए, अधिक या कम काम करने वाला परीक्षण सॉफ्टवेयर निकला। GeForce GTX560 स्तर के एक वीडियो कार्ड पर, असाइन किए गए कार्य को करने के लिए संभव था - आकार 704x576 में 75 फ्रेम प्रति सेकंड संसाधित करने के लिए। और समय का एक अच्छा मार्जिन अभी भी था। बेशक, लेख में मैंने केवल सामान्य सिद्धांतों को निर्धारित किया है - यहां बहुत कुछ अनुकूलित किया जा सकता है। दुर्भाग्य से, परियोजना में CUDA का उपयोग नहीं करने का निर्णय लिया गया था, इसलिए मैंने इसे एक वर्ष से अधिक समय तक नहीं छुआ।

एक बार फिर, मैं एक उत्कृष्ट लेख के लिए कामरेड बिगऑफसुसेटर के प्रति आभार व्यक्त करता हूं, जिसके बिना मैं कम से कम कुछ अधिक व्यवहार्य होता।

कच्चा

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

एक अच्छा कोडिंग और अच्छे विचार रखें!