लाप्लास ब्लर - क्या गॉस के बजाय लाप्लास को फोड़ना संभव है, कितनी बार तेज है, और क्या यह 1/32 सटीकता के नुकसान के लायक है

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

(लाप्लास ब्लर - प्रस्तावित मूल एल्गोरिथम नाम)

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

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


यह विवरण मेरे विचारों और अनुमानों के पाठ्यक्रम की व्याख्या करने के लिए यहाँ मौजूद है, जिसने मुझे परिणाम के लिए प्रेरित किया। उन लोगों के लिए जो रुचि लेंगे:

मूल गॉस फंक्शन:



g (x) = a * e ** (- ((xb) ** 2) / c), कहाँ
एक आयाम है (यदि हमारे पास प्रति चैनल आठ बिट्स रंग हैं, तो यह = 256)
ई यूलर स्थिरांक है ~ 2.7
बी - एक्स में ग्राफ बदलाव (हमें = 0 की आवश्यकता नहीं है)
c - इससे जुड़े ग्राफ की चौड़ाई को प्रभावित करने वाला पैरामीटर ~ w / 2.35 है

हमारा निजी कार्य (विभाजन द्वारा गुणन के साथ हटाए गए घातांक से ऋण):



g (x) = 256 / e ** (x * x / c)

गंदा सन्निकटन कार्रवाई शुरू करें:
ध्यान दें कि पैरामीटर सी आधी-चौड़ाई के करीब है और 8 सेट है (यह इस बात के कारण है कि आप कितने चरणों को एक 8-बिट चैनल को स्थानांतरित कर सकते हैं)।

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

तो अब हमारा कार्य निम्नानुसार है:
gg (x) = 256/2 ** (x * x / 8) या gg (x) = 2 ** (8 - x * x / 8)
ध्यान दें कि प्रतिपादक (x * x / 8) में मूल्य की समान सीमा [0-8] है, जो निचले क्रम के एब्स (x) के कार्य के रूप में है, इसलिए उत्तरार्द्ध प्रतिस्थापन के लिए एक उम्मीदवार है। हम यह देखकर तुरंत अनुमान लगा लेंगे कि ग्राफ के साथ परिवर्तन कैसे होता है gg (x) = 256 / (2 ** abs (x)):

गॉसब्लुर बनाम लाप्लाब्लूर:



विचलन बहुत बड़ा लगता है, इसके अलावा, समारोह, अपनी चिकनाई खो दिया है, अब एक चोटी है। लेकिन हे।

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

यह था:



यह बन गया:



प्रूफ, तैयार एल्गोरिथम से लिया गया, संयोग है:



(आगे देखते हुए, मैं कहूंगा कि गॉसियन x5 के सापेक्ष मेरे एल्गोरिथ्म की धब्बा त्रुटि केवल 3% थी)।

इसलिए, हम लाप्लास वितरण फ़ंक्शन के बहुत करीब आ गए हैं। किसने सोचा होगा, लेकिन वे 97% तस्वीरें खराब कर सकते हैं।

सबूत, गॉसियन ब्लुरा एक्स 5 और "लाप्लास ब्लुरा" एक्स 7 में अंतर:



(यह एक काली छवि नहीं है! आप संपादक में अध्ययन कर सकते हैं)

इस परिवर्तन की धारणा ने हमें पुनरावृत्ति फ़िल्टरिंग द्वारा मूल्य प्राप्त करने के विचार पर आगे बढ़ने की अनुमति दी, जिससे मैंने शुरुआत में कम करने की योजना बनाई।

एक विशिष्ट एल्गोरिदम को बताने से पहले, यह ईमानदार होगा यदि मैं आगे बढ़ता हूं और तुरंत इसकी एकमात्र खामी का वर्णन करता हूं (हालांकि कार्यान्वयन गति के नुकसान के साथ तय किया जा सकता है)। लेकिन यह एल्गोरिथ्म कतरनी अंकगणितीय का उपयोग करके लागू किया गया है, और 2 की शक्तियां इसकी सीमा हैं। तो मूल x7 को धुंधला करने के लिए बनाया गया है (जो गॉसियन x5 से संबंधित है निकटतम परीक्षणों में)। यह कार्यान्वयन सीमा इस तथ्य के कारण है कि आठ-बिट रंग के साथ, फ़िल्टर ड्राइव में मूल्य को प्रति बिट एक बिट से स्थानांतरित करना, बिंदु से कोई भी कार्रवाई अधिकतम 8 चरणों में समाप्त होती है। मैंने अनुपात और अतिरिक्त परिवर्धन के माध्यम से थोड़ा धीमा संस्करण भी लागू किया, जो 1.5 से एक त्वरित विभाजन को लागू करता है (परिणामस्वरूप x15 के त्रिज्या में)। लेकिन इस दृष्टिकोण के आगे के आवेदन के साथ, त्रुटि बढ़ जाती है, और गति गिर जाती है, जो इसे इस तरह उपयोग करने की अनुमति नहीं देती है। दूसरी ओर, यह ध्यान देने योग्य है कि x15 पहले से ही पर्याप्त है ताकि अंतर को नोटिस न किया जाए, परिणाम मूल से या डाउन-नमूना छवि से प्राप्त किया जाता है। यदि आप एक सीमित वातावरण में असाधारण गति की जरूरत है तो विधि काफी उपयुक्त है।

इसलिए, एल्गोरिथ्म का मूल सरल है, एक ही प्रकार के चार पास किए जाते हैं:

1. ड्राइव टी के मूल्य का आधा (शुरू में शून्य के बराबर) अगले पिक्सेल के आधे मूल्य में जोड़ा जाता है, परिणाम इसे सौंपा गया है। इस तरह से छवि रेखा के अंत तक जारी रखें। सभी लाइनों के लिए।

पहला पास पूरा होने पर, छवि एक दिशा में धुंधली हो जाती है।

2. दूसरे पास से हम सभी लाइनों के लिए विपरीत दिशा में समान करते हैं।
हमें एक छवि मिलती है जो पूरी तरह से क्षैतिज रूप से धुंधली होती है।

3-4। अब वही काम लंबवत करें।
हो गया!

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

वर्तमान चार-तरफा कार्यान्वयन विधि, मैंने पिछले एल्गोरिदम पर कलंक एल्गोरिदम पर हबेरा को देखा। habr.com/post/151157 मैं अपनी एकजुटता और उनके प्रति गहरी कृतज्ञता व्यक्त करने का अवसर लेता हूं।

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

buf32 [i] = t = (((t >> 1) & 0x7F7F7F) + ((buf32 [i] >> 1) & 0x7F7F7F);

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

buf32 [i] = t = (((((0x010101 + t) >> 1) और 0x7F7F7F) + ((buf32 [i] >> 1) & 0x7F7F7F);

वास्तव में, सूत्र सुधार को काफी अच्छी तरह से करता है, इसलिए जब आप बार-बार इस एल्गोरिदम को छवि पर लागू करते हैं, तो कलाकृतियां केवल दूसरे दस पास में दिखाई देने लगती हैं। (इस तथ्य को नहीं कि गाऊसी ब्लाउरा को दोहराने से इस तरह की कलाकृतियों का उत्पादन नहीं होगा)।

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



जो, आप देखते हैं, पहले से ही गौसियन के बहुत करीब है।

जाहिर है, मैंने पाया कि बड़े त्रिज्या के साथ संशोधनों का उपयोग जोड़े में अनुमेय है, क्योंकि ऊपर वर्णित संपत्ति त्रुटियों के लिए क्षतिपूर्ति करती है यदि अंतिम पास अधिक सटीक है (सबसे सटीक x7 कलंक एल्गोरिथ्म यहां वर्णित है)।

डेमो
खटखटाना
kodpen

शांत गणितज्ञों के लिए एक अपील:
यह जानना दिलचस्प होगा कि इस तरह के फिल्टर का अलग-अलग उपयोग करना कितना सही है, अगर कोई सममित वितरण चित्र है तो मुझे यकीन नहीं है। यद्यपि आंख की विषमता दिखाई नहीं देती है।

अपडेट: यहां मैं उपयोगी लिंक बढ़ाऊंगा, कृपया टिप्पणीकारों द्वारा प्रस्तुत किया गया है, और अन्य खब्रोविट्स से पाया गया है।
1. SSE की शक्ति के आधार पर इंटेल विजार्ड कैसे काम करते हैं - software.intel.com/en-us/articles/iir-gaussian-blur-filter-implementation-use-intel-advanced-vector-extensions (धन्यवाद vladimirovich )
2. इस विषय पर सैद्धांतिक आधार "फास्ट छवि संकल्प" + ईमानदार गॉसियन ब्लाउर के संबंध में अपने कुछ कस्टम अनुप्रयोग - blog.ivank.net/fastest-gaussian-blur.html (धन्यवाद ग्रॉक्स )

सुझावों, टिप्पणियों, रचनात्मक आलोचना का स्वागत है!