यर्क - हास्केल में डेटाफ्लो-फ्रेमवर्क (इमेज प्रोसेसिंग)

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

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

दिल

फ्रेम प्रकार के एक परिवार को परिभाषित करता है - सरणी निरूपण ( UArray )। प्रतिनिधियों को 2 प्रकारों में विभाजित किया जाता है:

• स्पष्ट रूप से , ऐसे अभ्यावेदन में सरणी तत्व वास्तव में स्मृति में कहीं स्थित हैं। मॉलॉक से कच्ची मेमोरी के टुकड़ों के आधार पर निम्न-स्तरीय जीएचसी सरणियों के आधार पर अभ्यावेदन होते हैं - केवल स्टॉटल क्लास के तत्वों के लिए।
• निहित प्रतिनिधित्व एक फ़ंक्शन (इंडेक्स -> तत्व) को एनकैप्सुलेट करते हैं।

तीन मुख्य क्षेत्रों में भी बड़ी संख्या में कार्य होते हैं:

• मैपिंग (मानचित्र), संयोजन कार्य (zipWith), और कर्नेल (कनवल्शन) द्वारा संलयन एक या अधिक सरणियों को इनपुट के रूप में लेते हैं और एक निहित सरणी वापस करते हैं ।
• कम्प्यूटिंग ( Load ) फ़ंक्शंस एक स्पष्ट में निहित सरणी का अनुवाद करते हैं, अर्थात, किसी रूप में, पहले को स्मृति में लिखें।
• सरणी के माध्यम से मार्ग ( Walk ) के कार्य, राज्य के साथ - दृढ़ संकल्प (गुना)।

रेपा पुस्तकालय से परिचित लोग यह देख सकते हैं कि यार इसके समान है। मुख्य अंतर:

• अधिकांश फ़ंक्शन में "घटक-वार" विकल्प होते हैं, जो वैक्टर के सरणियों के साथ काम करते समय सुविधाजनक होता है, उदाहरण के लिए, आरजीबी प्रारूप में छवियां।
• तह (तह) की संभावनाओं का दृढ़ता से विस्तार किया।
• यारा अक्सर रेपा की तुलना में तेज़ होता है। उदाहरण के लिए, येर पर कैनी सीमा डिटेक्टर रेपा डिटेक्टर की तुलना में लगभग 2 गुना तेज है।

उदाहरण

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

हल्कापन द्वारा हिस्टोग्राम की गणना समीकरण के चरणों में से एक है (ऊपरी तस्वीर में पहला तीर)।

 import Data.Yarr import Data.Yarr.Walk import Data.Yarr.Shape as S import Data.Yarr.Repr.Foreign ... computeHist :: UArray FS L Dim2 Float -> IO (UArray FL Dim1 Int) computeHist pixelValues = walkP caps (mutate (S.unrolledFill n8 noTouch) incHist) (newEmpty 256) joinHists pixelValues where incHist :: UArray FL Dim1 Int -> Float -> IO () incHist hist value = do let level = truncate (value * 255.99) c <- index hist level write hist level (c + 1) joinHists h1 h2 = do loadS S.fill (dzip2 (+) h1 h2) h1 return h1 

यह आलेख विभिन्न प्रकार के थ्रेड्स पर छवि के प्रति पिक्सेल , प्रारंभ की एक किस्म से न्यूनतम रनटाइम का माप प्रदान करता है। माप की इकाई प्रोसेसर चक्र है। यर संस्करण 1.2.3, परीक्षण विन्यास , सामान्य मेकफाइल , परीक्षण छवि (2560 × 1600, 6 एमबी) है।


एक चिकनी काले और सफेद छवि से एक बिंदु पर ढाल की दिशा और शक्ति की गणना सीमाओं का पता लगाने के चरणों में से एक है (शीर्ष चित्र में दूसरा तीर)।



पूरी तरह से योर और ओपनसीवी पर बॉर्डर डिटेक्टरों के प्रदर्शन की तुलना, सबसे लोकप्रिय इमेज प्रोसेसिंग लाइब्रेरी है। Yarr कोड, OpenCV कोड । OpenCV एकल छवि के समानांतर प्रसंस्करण का समर्थन नहीं करता है।

निष्कर्ष: बड़ी संख्या में साधारण छवियों पर सीमाओं को उजागर करने से ओपनसीवी (यदि आप धाराओं में छवियों को तितर बितर करते हैं) पर तेजी से निकल जाएंगे, और एक विशाल पर, गीगापिक्सल के एक जोड़े, फोटो - हास्केल पर तेजी से।

मूल्यवान अनुकूलन

स्वचालित समानांतरकरण

ऊपर दिए गए उदाहरणों में, आप प्रत्यय के साथ कार्यों पर ध्यान दे सकते हैं - और पहला तर्क caps : walkP , loadP । यह वह है जो प्रक्रिया के लिए उपलब्ध कोर की एक अलग संख्या को सांत्वना के माध्यम से सेट करते समय "जादू" कार्यक्रमों के त्वरण के लिए जिम्मेदार हैं। caps getNumCapabilities लिए getNumCapabilities , मानक Control.Concurrent मॉड्यूल से एक फ़ंक्शन। caps बजाय caps आप स्पष्ट परिणाम के साथ, उदाहरण के लिए, (threads 2) लिख सकते हैं।

किसी विशेष प्रोसेसर की शक्ति को अधिकतम करने के लिए उपकरण

यदि तत्व पर गणना काफी सरल है, और लक्ष्य प्रोसेसर पर पाइप लाइन विस्तृत है, तो आप पाइपलाइन को बेहतर ढंग से बंद करने के लिए कई पुनरावृत्तियों को तैनात कर सकते हैं । एक उदाहरण computeHist फ़ंक्शन की 1 पंक्ति में है (हिस्टोग्राम गणना 8 पुनरावृत्तियों के लिए तैनात है)। अन्य परिनियोजन मापदंडों के साथ इस गणना का प्रदर्शन, और इसके बिना बिल्कुल (पैमाना थोड़ा सा लघुगणक है):

जैसा कि आप देख सकते हैं, इस मामले में, तैनाती आपको कार्यक्रम को लगभग तीन बार गति देने की अनुमति देती है। सहज रूप से, यह इसलिए है क्योंकि मेरे प्रोसेसर की पाइपलाइन में 3 पाइपलाइन हैं। लंबे रोलआउट के साथ, वे पूरी गति से काम करते हैं, और रोलआउट के बिना, 3 में से 2 निष्क्रिय हैं।

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

इसके विपरीत, जब वैक्टर के प्रसंस्करण सरणियों, यदि व्यक्तिगत घटकों की गणना स्वतंत्र होती है और एक ही समय में बहुत अधिक अंकगणित होते हैं, तो आप पाइपलाइन और रजिस्टर फ़ाइल को अनलोड करने के लिए अलग-अलग समय में घटकों को अलग-अलग गणना करने की कोशिश कर सकते हैं (समानांतर में, उन्हें अलग-अलग धाराओं में भी वितरित किया जाएगा)। उदाहरण के लिए, मेरे प्रोसेसर पर यह एक 5 × 5 कोर ( blur.hs ) के साथ एक रंगीन छवि के गॉसियन चौरसाई के साथ 15% का प्रदर्शन लाभ देता है। गणना और पुनरावृत्ति कार्यों के घटक संस्करणों में -Slices- या -SlicesSeparate- ।

पढ़ने के संचालन को कम करने के लिए कर्नेल कनवल्शन कैलकुलेशन के 2 डी रोल-अप

उदाहरण के लिए, 3 × 3 कर्नेल के साथ एक काले और सफेद छवि के गौसियन स्मूदी को लें:



यदि हम एक पंक्ति में 4 पड़ोसी पिक्सल के मूल्यों की गणना करते हैं, तो एलएलवीएम यह साबित कर सकता है कि दोहराया रीडिंग के साथ, मूल पिक्सेल मान बदल नहीं सकते हैं (क्योंकि उनके बीच कोई लेखन कार्य नहीं हैं) और बाद का पुन: उपयोग करें।



ऊपर पिक्सेल तीव्रता की मूल द्वि-आयामी सरणी है, निर्देशांक (y = 2, x = 2), (2, 3), (3, 2) और (3) में चिकने पिक्सेल मानों की गणना के लिए लाल, नीला, पीला और हरा आयताकार गुठली है। 3) क्रमशः। कर्नेल में गुणक केवल पहले पिक्सेल के लिए लिखे गए हैं।

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

उदाहरण क्षैतिज और लंबवत रूप से 2 अनुक्रमितों के विस्तार का उपयोग करता है। बेशक, यह हमेशा इष्टतम नहीं है। तैनाती चरणों के आधार पर इस तरह की चौरसाई की गति:

फ्रेमवर्क में दोनों आयामों के लिए दो आयामी सरणियों की गणना के पैरामीट्रिज्ड विस्तार के लिए एक फ़ंक्शन है, dim2BlockFill ।

कमियों

लूप वेक्टर नहीं होते हैं। तैनाती के साथ, एलएलवीएम वादे करता है, लेकिन वास्तव में कुछ भी नहीं करता है। LLVM 3.3 ने इस दिशा में सुधार की घोषणा की है , इसलिए भविष्य के भविष्य में हम रूपरेखा के और भी तेज होने की उम्मीद कर सकते हैं। जीएचसी 7.6.1 का स्थिर बैकएंड वर्तमान में एलएलवीएम 3.1 माना जाता है।

स्ट्रीम फ़िल्टरिंग और स्ट्रीमिंग के लिए कोई समर्थन नहीं है। यह सुविधा रेपा 4 (विकास में संस्करण) में होगी। यह येर में लागू नहीं किया जाएगा, क्योंकि इसके लिए आपको लाइब्रेरी को स्क्रैच से फिर से लिखना होगा, जिसके लिए कोई भी व्यक्ति नहीं चाहता है। वर्तमान वास्तुकला के साथ पक्ष को कसने से काम नहीं चलता है। हालाँकि, बेन लिपिमीयर भी रेपा 3 को खरोंच से लिखता है, इसलिए प्रेरणा मिली :)

कार्यान्वयन

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

यह एक प्रकार का स्टैटिक ड्यूल प्रेषण है। विषय को पाठ्यक्रम में अधिक विस्तार से वर्णित किया गया है , यह अधिकतर नोट को दिया गया है ।

एक अलग पोस्ट जीएचसी सुस्ती का मुकाबला करने के बारे में है ।

अनफॉलो किए गए लूप के साथ फ़ंक्शंस, उदाहरण के लिए, unrolledFill , एक नंबर को अनफॉलो करने के कदम के रूप में नहीं एक साधारण ( Int ), लेकिन प्रकारों के स्तर तक उठाया गया। computeHist फ़ंक्शन (ऊपर के उदाहरण से) में, N8 प्रकार N8 का एक मूल्य है, जो निश्चित-वेक्टर लाइब्रेरी से Arity वर्ग का है। सामान्य तौर पर, रूपरेखा वास्तव में इस पुस्तकालय पर आधारित है, इसका उपयोग बहुत सक्रिय रूप से किया जाता है।

unrolledFill जैसे कार्यों के अंदर, किसी दिए गए एरिटी के कार्यों का एक वेक्टर बनता है । जीएचसी पूरी तरह से वेक्टर को कम कर देता है, संकलन के बाद क्रियाओं का एक सपाट अनुक्रम रहता है, अर्थात् बस खुलासा। आश्चर्यजनक रूप से, GHC यहां तक ​​कि डबल नेस्टिंग के वैक्टर की कमी के साथ मुकाबला करता है, जिसकी मदद से फ़ंक्शन dim2BlockFill कार्यान्वित किया जाता है !

डिज़ाइन

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

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

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