डायनेमिक प्रोग्रामिंग में उस विधि की प्रतिष्ठा होती है जिसे आप विश्वविद्यालय में पढ़ते हैं, और फिर केवल साक्षात्कार के दौरान याद करते हैं। लेकिन वास्तव में, विधि कई स्थितियों में लागू होती है। वास्तव में, यह समस्याओं को प्रभावी ढंग से हल करने के लिए एक तकनीक है जिसे कई अत्यधिक दोहराए जाने वाले उप-प्रकारों में विभाजित किया जा सकता है ।

लेख में मैं गतिशील प्रोग्रामिंग का एक वास्तविक वास्तविक अनुप्रयोग दिखाऊंगा - सीम नक्काशी कार्य। कार्य और कार्यप्रणाली को विस्तार से वर्णित किया गया है कि एव्डन और शमीर के काम "सामग्री के आधार पर छवियों के आकार बदलने के लिए सीम काटना" (मुफ्त पहुंच लेख)।

यह डायनामिक प्रोग्रामिंग पर लेखों की एक श्रृंखला है। यदि आप विधियों पर ब्रश करना चाहते हैं, तो गतिशील प्रोग्रामिंग का सचित्र परिचय देखें।

सामग्री के आधार पर आकार बदलें

गतिशील प्रोग्रामिंग का उपयोग करके एक वास्तविक समस्या को हल करने के लिए, आपको इसे सही ढंग से तैयार करने की आवश्यकता है। यह अनुभाग चयनित कार्य के लिए आवश्यक प्रीसेट का वर्णन करता है।

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


शांत सागर के बीच में एक सर्फर का शीर्ष दृश्य, दाईं ओर अशांत लहरों के साथ। फोटो: पिक्साबे पर किरिल डोबरेव

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


बाईं ओर ट्रिमिंग और ब्लॉक को बीच से काटकर चौड़ाई कम करने का प्रयास। बाद वाला दृश्यमान सीम छोड़ता है।

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

सर्फर की तस्वीर में, सबसे कम ऊर्जा सीम छवि के मध्य से चलती है, जहां पानी सबसे शांत है। यह हमारे अंतर्ज्ञान के अनुरूप है।


सर्फर की छवि में पाए जाने वाले सबसे कम-ऊर्जा सीम को दृश्यता के लिए लाल रेखा के साथ पांच पिक्सेल चौड़ा दिखाया गया है, हालांकि वास्तव में सीम केवल एक पिक्सेल चौड़ा है।

सीम को कम से कम ऊर्जा के साथ निर्धारित किया है, और फिर इसे हटाकर, हम एक पिक्सेल द्वारा छवि की चौड़ाई कम कर देते हैं। इस प्रक्रिया को बार-बार दोहराने से पूरी फोटो की चौड़ाई कम हो जाती है।


1024 पिक्सेल द्वारा चौड़ाई में कमी के बाद सर्फ़र छवि

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

इमेज एनर्जी परिभाषा

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

वैज्ञानिक लेख कई ऊर्जा कार्यों और उनके मतभेदों पर चर्चा करता है। आइए इसे जटिल न करें और एक फ़ंक्शन लें जो बस प्रत्येक पिक्सेल के आसपास रंग परिवर्तन की मात्रा को कैप्चर करता है। तस्वीर को पूरा करने के लिए, मैं ऊर्जा फ़ंक्शन का वर्णन और अधिक विस्तार से करूँगा जब आप इसे स्वयं लागू करना चाहते हैं, लेकिन यह बाद की गतिशील प्रोग्रामिंग गणनाओं के लिए एक पूर्व निर्धारित है।


बाईं ओर अंधेरे से प्रकाश तक तीन पिक्सेल हैं। पहले और आखिरी के बीच का अंतर बहुत अच्छा है। रंग की तीव्रता में मामूली अंतर के साथ दाईं ओर तीन गहरे पिक्सेल

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

$$

$$| \ Delta x | ^ 2 = (\ Delta r_x) ^ 2 + (\ Delta g_x) ^ 2 + (\ Delta b_x) ^ 2$$

$$

$$| \ Delta y | ^ 2 = (\ Delta r_y) ^ 2 + (\ Delta g_y) ^ 2 + (\ Delta b_y) ^ 2$$

$$

$$e (x, y) = | \ डेल्टा x | ^ 2 + | \ डेल्टा वाई | ^ 2$$

एकमात्र चेतावनी - कहते हैं, यदि कोई पिक्सेल बाएं किनारे पर है, तो बाईं तरफ कोई पड़ोसी नहीं है। इस मामले में, हम केवल सही पिक्सेल के साथ तुलना करते हैं। समान चेक ऊपरी, दाएँ और निचले किनारों पर पिक्सेल के लिए किए जाते हैं।

यदि पड़ोसी पिक्सेल रंग में बहुत भिन्न हैं, और यदि वे समान हैं, तो ऊर्जा कार्य बहुत अच्छा है।


एक सर्फर की तस्वीर में प्रत्येक पिक्सेल की ऊर्जा: हल्का - जितना अधिक होता है। जैसा कि अपेक्षित था, सर्फर के दाईं ओर मध्य और अशांत तरंगों में सबसे अधिक ऊर्जा होती है

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

गतिशील प्रोग्रामिंग के साथ कम ऊर्जा वाले सीम की खोज करें

प्रत्येक पिक्सेल की ऊर्जा की गणना करके, हम छवि के शीर्ष से नीचे तक सबसे कम ऊर्जा के साथ सीम पा सकते हैं। मूल छवि की ऊंचाई को कम करने के लिए एक ही विश्लेषण क्षैतिज सीम पर लागू होता है। हालांकि, हम ऊर्ध्वाधर लोगों पर ध्यान केंद्रित करेंगे।

आइए परिभाषा के साथ शुरू करें:

• सीम पिक्सल का एक क्रम है, प्रति पंक्ति एक पिक्सेल। आवश्यकता यह है कि लगातार दो लाइनों के बीच समन्वय हो $$$x$ एक से अधिक पिक्सेल से परिवर्तन नहीं। यह सीवन अनुक्रम को संरक्षित करता है।
  
• सबसे कम ऊर्जा वाला सीम वह है जिसकी सीम में सभी पिक्सल पर कुल ऊर्जा कम से कम हो।

यह ध्यान रखना महत्वपूर्ण है कि सबसे कम ऊर्जा वाला संयुक्त जरूरी नहीं कि सभी पिक्सल सबसे कम ऊर्जा से गुजरता हो। सभी की कुल ऊर्जा, व्यक्तिगत पिक्सेल नहीं, को ध्यान में रखा जाता है।


लालची दृष्टिकोण काम नहीं करता है। प्रारंभिक स्तर पर कम-ऊर्जा पिक्सेल का चयन, हम छवि के उच्च-ऊर्जा क्षेत्र (दाईं ओर लाल पथ) में फंस जाते हैं

जैसा कि आप देख सकते हैं, आप केवल अगली पंक्ति में सबसे कम ऊर्जा पिक्सेल का चयन नहीं कर सकते।

हम समस्या को उपशीर्षक में तोड़ते हैं

लालची दृष्टिकोण के साथ समस्या यह है कि अगले चरण पर निर्णय लेते समय, हम आगे के बाकी सीम को ध्यान में नहीं रखते हैं। हम भविष्य में नहीं देख सकते हैं, लेकिन हम उन सभी चीजों को ध्यान में रखते हैं जो हम पहले से जानते हैं।

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


प्रत्येक पिक्सेल के लिए, हम ऊपर की पंक्ति में तीन पिक्सेल का अध्ययन करते हैं। मौलिक विकल्प - जारी रखने के लिए कौन सी सीटें?

यह छवि में प्रत्येक पिक्सेल के लिए एक उपमा मानता है। उपस्करों को एक विशिष्ट पिक्सेल के लिए सबसे अच्छा रास्ता मिलना चाहिए, इसलिए प्रत्येक पिक्सेल को उस पिक्सेल में समाप्त होने वाली कम-ऊर्जा सीम की ऊर्जा के साथ जोड़ना एक अच्छा विचार है।

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

पुनरावृत्ति संबंध की परिभाषा

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

एक फ़ंक्शन को परिभाषित करें $$$M (x, y)$ , जो कम से कम ऊर्जा के साथ ऊर्ध्वाधर सीम की ऊर्जा का प्रतिनिधित्व करता है। यह छवि के शीर्ष पर शुरू होता है और एक पिक्सेल में समाप्त होता है $$$(x, y)$ । नाम $$$एम$ मूल वैज्ञानिक लेख में के रूप में चयनित।

सबसे पहले, आपको एक मूल संस्करण की आवश्यकता है। शीर्ष पंक्ति पर समाप्त होने वाले सभी सीमों की लंबाई केवल एक पिक्सेल है। इस प्रकार, न्यूनतम ऊर्जा वाला सीम न्यूनतम ऊर्जा वाला एक पिक्सेल है:

$$

$$M (x, 0) = e (x, 0)$$

शेष पंक्तियों में पिक्सेल के लिए, शीर्ष पर पिक्सेल देखें। चूंकि सीम निरंतर होना चाहिए, हम शीर्ष बाईं ओर स्थित केवल तीन पिक्सेल को ध्यान में रखते हैं, शीर्ष और शीर्ष दाएं। उनमें से हम सबसे कम ऊर्जा के साथ सीम का चयन करते हैं, जो इन पिक्सेल में से एक में समाप्त होता है, और वर्तमान पिक्सेल की ऊर्जा को जोड़ता है:

$$

$$M (x, y) = e (x, y) + \ min \ _ {मामले} M (x - 1, y - 1) \\ M (x, y - 1) \\ M (x + 1) y - 1) \ end {मामले}$$

सीमा रेखा की स्थिति के रूप में, उस स्थिति पर विचार करें जब वर्तमान पिक्सेल छवि के बाएं या दाएं किनारे पर हो। इन मामलों में, हम चूक करते हैं $$$M (x-1, y-1)$ बाएं किनारे पर पिक्सेल के लिए या $$$M (x + 1, y-1)$ दाहिने किनारे पर।

अंत में, आपको कम-ऊर्जा सीम की ऊर्जा निकालने की जरूरत है, जो छवि की पूरी ऊंचाई को कवर करती है। इसका मतलब है कि हम छवि की निचली रेखा को देखते हैं और सबसे कम-ऊर्जा सीम का चयन करते हैं जो इन पिक्सेल में से एक पर समाप्त होता है। फोटो विस्तृत के लिए $$$डब्ल्यू$ और लंबा $$$ज$ पिक्सल:

$$

$$\ min_ {0 \ le x <W} M (x, H - 1)$$

इसलिए, हमें सभी आवश्यक गुणों के साथ पुनरावृत्ति संबंध मिल गया:

• पुनरावृत्ति संबंध में पूर्णांक इनपुट होते हैं।
  
• अंतिम उत्तर संबंध से निकालना आसान है।
  
• अनुपात स्वयं पर निर्भर करता है।

डीएजी उपवाक्य का सत्यापन (उन्मुख चक्रीय ग्राफ)

प्रत्येक उपमा के बाद से $$$M (x, y)$ मूल छवि के एक पिक्सेल से मेल खाती है, निर्भरता ग्राफ को कल्पना करना बहुत आसान है। बस उन्हें दो-आयामी ग्रिड पर रखें, जैसा कि मूल छवि में है!


उप-प्रकार मूल छवि में पिक्सेल की तरह दो-आयामी ग्रिड में स्थित हैं

पुनरावृत्ति संबंध के आधार परिदृश्य से निम्नानुसार, उप-रेखाओं की शीर्ष रेखा को व्यक्तिगत पिक्सल के ऊर्जा मूल्यों के साथ आरंभ किया जा सकता है।


शीर्ष पंक्ति अन्य उप-प्रकारों से स्वतंत्र है। कोशिकाओं की शीर्ष पंक्ति से तीरों की अनुपस्थिति पर ध्यान दें

दूसरी पंक्ति में, निर्भरताएं दिखाई देने लगती हैं। सबसे पहले, दूसरी पंक्ति में सबसे बाईं सेल में हम एक सीमा स्थिति के साथ सामना कर रहे हैं। चूंकि बाईं ओर कोशिकाएं नहीं हैं, कोशिका $$$(1,0)$ केवल इसके ऊपर और सीधे ऊपर स्थित कोशिकाओं पर निर्भर करता है। यही बात बाद में तीसरी पंक्ति के सबसे बाएं सेल के साथ भी होगी।


बाएं किनारे पर उप-मुखौटे उनके ऊपर केवल दो उप-मुखौटे पर निर्भर करते हैं

दूसरी पंक्ति (1,1) के दूसरे सेल में, हम पुनरावृत्ति संबंध की सबसे विशिष्ट अभिव्यक्ति देखते हैं। यह कोशिका तीन कोशिकाओं पर निर्भर करती है: ऊपर बाईं ओर, इसके ठीक ऊपर और ऊपर दाईं ओर। यह निर्भरता संरचना दूसरी और बाद की पंक्तियों में सभी "मध्य" कोशिकाओं पर लागू होती है।


बाएं और दाएं किनारों के बीच उप-मुखौटे शीर्ष पर तीन उप-मुखौटे पर निर्भर करते हैं

अंत में, दाहिने किनारे पर स्थित सेल दूसरी सीमा रेखा की स्थिति का प्रतिनिधित्व करता है। चूँकि दाईं ओर अधिक कोशिकाएँ नहीं हैं, यह केवल शीर्ष पर और ऊपर बाईं ओर की कोशिकाओं पर निर्भर करता है।


दाहिने किनारे पर उपशीर्षक शीर्ष पर केवल दो कोशिकाओं पर निर्भर करते हैं

प्रक्रिया को बाद की सभी लाइनों के लिए दोहराया जाता है।


चूँकि निर्भरता ग्राफ में कई तीर हैं, यह एनीमेशन बदले में प्रत्येक उपप्रकार के लिए निर्भरता दिखाता है

एक पूर्ण निर्भरता ग्राफ आपको बड़ी संख्या में तीरों से डराता है, लेकिन उन्हें एक बार में देखने से स्पष्ट पैटर्न स्थापित करने में मदद मिलती है।

नीचे के कार्यान्वयन

इस विश्लेषण को करने के बाद, हमें प्रोसेसिंग ऑर्डर मिला:

• छवि के ऊपर से नीचे तक जाएं।
  
• प्रत्येक पंक्ति किसी भी क्रम में कार्य कर सकती है। प्राकृतिक विकल्प बाएं से दाएं जाना है।

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

निम्नलिखित पायथन कोड में, इनपुट लाइनों की एक सूची है, जहां प्रत्येक पंक्ति में उस रेखा में व्यक्तिगत पिक्सेल ऊर्जा का प्रतिनिधित्व करने वाली संख्याओं की एक सूची होती है। इनपुट को pixel_energies कहा जाता है, और pixel_energies[y][x] निर्देशांक में पिक्सेल ऊर्जा का प्रतिनिधित्व करता है $$$(x, y)$ ।

चलो ऊपरी पंक्ति के सीम की ऊर्जा की गणना करके शुरू करते हैं, बस ऊपरी पंक्ति में व्यक्तिगत पिक्सेल ऊर्जा की प्रतिलिपि बनाकर:

 previous_seam_energies_row = list(pixel_energies[0]) 

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

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

 # Skip the first row in the following loop. for y in range(1, len(pixel_energies)): pixel_energies_row = pixel_energies[y] seam_energies_row = [] for x, pixel_energy in enumerate(pixel_energies_row): # Determine the range of x values to iterate over in the previous # row. The range depends on if the current pixel is in the middle of # the image, or on one of the edges. x_left = max(x - 1, 0) x_right = min(x + 1, len(pixel_energies_row) - 1) x_range = range(x_left, x_right + 1) min_seam_energy = pixel_energy + \ min(previous_seam_energies_row[x_i] for x_i in x_range) seam_energies_row.append(min_seam_energy) previous_seam_energies_row = seam_energies_row 

नतीजतन, पिछली_seam_energies_row में निचली रेखा के लिए सीम ऊर्जा होती है। हम इस सूची में न्यूनतम मूल्य पाते हैं - और यह उत्तर है!

 min(seam_energy for seam_energy in previous_seam_energies_row) 

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

 ENERGIES = [ [9, 9, 0, 9, 9], [9, 1, 9, 8, 9], [9, 9, 9, 9, 0], [9, 9, 9, 0, 9], ] print(min_seam_energy(ENERGIES)) 

स्थानिक और लौकिक जटिलता

मूल छवि में प्रत्येक पिक्सेल एक उपमा से मेल खाती है। प्रत्येक उपकेंद्र के लिए, तीन से अधिक निर्भरताएं नहीं हैं, इसलिए उनमें से प्रत्येक को हल करने के लिए लगातार काम करना शामिल है। अंतिम पंक्ति दो बार आयोजित की जाती है। तो इमेज वाइड के लिए $$$डब्ल्यू$ और लंबा $$$ज$ पिक्सेल समय जटिलता है $$$O (W × H + W)$ ।

समय के प्रत्येक क्षण में, हमारे पास दो सूचियाँ हैं: पिछली पंक्ति के लिए एक और वर्तमान के लिए एक। पहले में $$$डब्ल्यू$ तत्व, और दूसरा धीरे-धीरे बढ़ता है $$$डब्ल्यू$ । इस प्रकार, स्थानिक जटिलता के बराबर है $$$O (2W)$ वह बस है $$$O (w)$ ।

ध्यान दें कि यदि हमने वास्तव में पिछली पंक्ति के डेटा तत्वों को छोड़ दिया है, तो हम पिछली पंक्ति के तत्वों की सूची को उसी गति से कम कर देंगे जैसे कि वर्तमान पंक्ति की सूची बढ़ती है। इस प्रकार स्थानिक जटिलता बनी रहेगी $$$O (w)$ । हालांकि चौड़ाई भिन्न हो सकती है, यह आमतौर पर इतना महत्वपूर्ण नहीं है।

लो एनर्जी बैकवर्ड पॉइंटर्स

तो, हमने निम्न-ऊर्जा सीम का अर्थ पाया, लेकिन इस जानकारी के साथ क्या करना है? आखिरकार, वास्तव में, हम ऊर्जा के महत्व के बारे में चिंतित नहीं हैं, लेकिन खुद सीम! समस्या यह है कि अंतिम पिक्सेल से शेष सीम पर लौटने का कोई रास्ता नहीं है।

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

बैक पॉइंटर्स का प्रतिनिधित्व

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

सबसे पहले, ऊर्जा और बैक पॉइंटर्स को संचय करने के लिए एक वर्ग बनाएं। उपकेंद्रों की गणना के लिए ऊर्जा का उपयोग किया जाएगा। चूँकि बैकवर्ड पॉइंटर यह निर्धारित करता है कि पिछली लाइन में कौन सा पिक्सेल वर्तमान ऊर्जा देता है, हम इसे केवल x निर्देशांक के रूप में कल्पना कर सकते हैं।

 class SeamEnergyWithBackPointer(): def __init__(self, energy, x_coordinate_in_previous_row=None): self.energy = energy self.x_coordinate_in_previous_row = x_coordinate_in_previous_row 

प्रत्येक उपशीर्षक के लिए गणना परिणाम केवल एक संख्या नहीं होगी, बल्कि इस वर्ग का एक उदाहरण होगा।

पिछड़े सूचक भंडारण

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

ऐसा करने के लिए, हम बस सभी उप-प्रकारों के पूर्ण परिणाम को बचाते हैं, हालांकि पिछली पंक्तियों के सीम की संख्यात्मक ऊर्जा को छोड़ना तकनीकी रूप से संभव है। परिणाम दो-आयामी सरणी में संग्रहीत होते हैं, जो इनपुट सरणी के समान दिखता है।

आइए पहली पंक्ति से शुरू करें, जिसमें केवल व्यक्तिगत पिक्सेल ऊर्जाएं हैं। चूंकि कोई पिछली पंक्ति नहीं है, सभी बैक SeamEnergyWithBackPointers गायब हैं, लेकिन स्थिरता के लिए, हम अभी भी SeamEnergyWithBackPointers इंस्टेंस स्टोर करेंगे:

 seam_energies = [] # Initialize the top row of seam energies by copying over the top row of # the pixel energies. There are no back pointers in the top row. seam_energies.append([ SeamEnergyWithBackPointer(pixel_energy) for pixel_energy in pixel_energies[0] ]) 

मुख्य लूप मूल रूप से पिछले कार्यान्वयन के समान काम करता है, जिसमें निम्नलिखित अंतर हैं:

• पिछली पंक्ति के डेटा में SeamEnergyWithBackPointer उदाहरण हैं, इसलिए पुनरावृत्ति अनुपात के मूल्य की गणना करते समय, आपको इन वस्तुओं के अंदर सीम की ऊर्जा की तलाश करनी चाहिए।
  
• वर्तमान पिक्सेल के लिए डेटा सहेजना, आपको SeamEnergyWithBackPointer का एक नया उदाहरण बनाने की SeamEnergyWithBackPointer । यहां हम वर्तमान पिक्सेल के लिए सीम ऊर्जा को संग्रहीत करेंगे, साथ ही साथ पिछली सीम से x समन्वय करते हैं, जिसका उपयोग वर्तमान सीम ऊर्जा की गणना के लिए किया जाता है।
  
• प्रत्येक पंक्ति के अंत में, पिछली पंक्ति के डेटा को छोड़ने के बजाय, हम वर्तमान पंक्ति के डेटा को seam_energies ।

 # Skip the first row in the following loop. for y in range(1, len(pixel_energies)): pixel_energies_row = pixel_energies[y] seam_energies_row = [] for x, pixel_energy in enumerate(pixel_energies_row): # Determine the range of x values to iterate over in the previous # row. The range depends on if the current pixel is in the middle of # the image, or on one of the edges. x_left = max(x - 1, 0) x_right = min(x + 1, len(pixel_energies_row) - 1) x_range = range(x_left, x_right + 1) min_parent_x = min( x_range, key=lambda x_i: seam_energies[y - 1][x_i].energy ) min_seam_energy = SeamEnergyWithBackPointer( pixel_energy + seam_energies[y - 1][min_parent_x].energy, min_parent_x ) seam_energies_row.append(min_seam_energy) seam_energies.append(seam_energies_row) 

संकेतों का पालन करें

अब उप-मुखौटे की पूरी तालिका भर गई है और हम सीम को कम से कम ऊर्जा के साथ बहाल कर सकते हैं। हम नीचे की पंक्ति में x समन्वय की तलाश करके शुरू करते हैं, जो कम से कम ऊर्जा के साथ संयुक्त से मेल खाती है:

 # Find the x coordinate with minimal seam energy in the bottom row. min_seam_end_x = min( range(len(seam_energies[-1])), key=lambda x: seam_energies[-1][x].energy ) 

अब छवि के नीचे से ऊपर तक जाएं, बदलते हुए $$$य$ len(seam_energies) - 1 से शून्य। प्रत्येक पुनरावृत्ति पर, वर्तमान जोड़ी जोड़ें $$$(x, y)$ हमारे सीम का प्रतिनिधित्व करने वाली सूची में, और फिर मूल्य निर्धारित करें $$$x$ ऑब्जेक्ट के लिए जो SeamEnergyWithBackPointer वर्तमान पंक्ति में इंगित SeamEnergyWithBackPointer है।

 # Follow the back pointers to form a list of coordinates that form the # lowest-energy seam. seam = [] seam_point_x = min_seam_end_x for y in range(len(seam_energies) - 1, -1, -1): seam.append((seam_point_x, y)) seam_point_x = \ seam_energies[y][seam_point_x].x_coordinate_in_previous_row seam.reverse() 

तो सीम को ऊपर की ओर बनाया गया है, सूची को फिर रिवर्स ऑर्डर में पढ़ा जा सकता है, यदि आपको ऊपर से नीचे तक निर्देशांक की आवश्यकता होती है।

स्थानिक और लौकिक जटिलता

समय जटिलता पिछले एक के समान है, क्योंकि हमें अभी भी प्रत्येक पिक्सेल को एक बार संसाधित करने की आवश्यकता है। अंतिम पंक्ति को देखने और कम से कम ऊर्जा के साथ संयुक्त को खोजने के बाद, हम फिर संयुक्त को पुनर्स्थापित करने के लिए छवि की पूरी ऊंचाई तक जाते हैं। तो छवि के लिए $$$W × H$ समय जटिलता बराबर होती है $$$O (W × H + W + H)$ ।

वॉल्यूम के लिए, हम अभी भी प्रत्येक सबटस्क के लिए एक निरंतर मात्रा में डेटा रखते हैं, लेकिन अब हम किसी भी डेटा को नहीं छोड़ते हैं। इसलिए हम वॉल्यूम का उपयोग करते हैं $$$O (W × H)$ ।

कम ऊर्जा सीम हटाने

जैसे ही सबसे कम ऊर्जा वाला ऊर्ध्वाधर जोड़ पाया जाता है, हम बस मूल छवि से पिक्सेल को एक नए में कॉपी कर सकते हैं। नई छवि की प्रत्येक पंक्ति में मूल छवि की संगत रेखा से सभी पिक्सेल होते हैं, जिसमें सबसे कम ऊर्जा के साथ सीम से पिक्सेल का अपवाद होता है। चूंकि हम प्रत्येक पंक्ति में एक पिक्सेल हटाते हैं, छवि से शुरू $$$W × H$ तब हमें छवि मिलती है $$$(W - 1) × H$ ।

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


सीम हटाने की प्रक्रिया का एनीमेशन। सीम के एक स्पष्ट दृश्य के लिए पूर्ण स्क्रीन में देखने के लिए बेहतर है

वीडियो का प्रत्येक फ्रेम कम से कम ऊर्जा के साथ सीम के सुपरिम्पोज्ड विज़ुअलाइज़ेशन के साथ प्रत्येक पुनरावृत्ति पर एक छवि है।

एक और उदाहरण

लेख में बहुत सारी विस्तृत व्याख्याएं थीं, इसलिए चलो सुंदर तस्वीरों की एक श्रृंखला के साथ समाप्त करें! निम्नलिखित तस्वीर आर्चेस नेशनल पार्क में एक रॉक फॉर्मेशन दिखाती है:


आर्चेस नेशनल पार्क में एक छेद के साथ रॉक का निर्माण। फोटो: फ़्लिकर पर माइक गोआद

इस छवि के लिए ऊर्जा कार्य:


फोटो में प्रत्येक पिक्सेल की ऊर्जा: हल्का - जितना अधिक होगा। छेद के किनारे के आसपास उच्च ऊर्जा पर ध्यान दें।

गणना के परिणामस्वरूप, सबसे कम ऊर्जा वाला एक सीम प्राप्त किया जाता है। ध्यान दें कि यह दाईं ओर चट्टान से होकर गुजरता है, सीधे चट्टान के रूप में प्रवेश करता है जहां चट्टान के शीर्ष पर प्रकाशित भाग आकाश के रंग से मेल खाता है। शायद आपको एक बेहतर ऊर्जा फ़ंक्शन चुनना चाहिए!


छवि में पाया जाने वाला सबसे कम-ऊर्जा सीम दृश्यता के लिए लाल रेखा के साथ पांच पिक्सेल चौड़ा दिखाया गया है, हालांकि वास्तव में सीम केवल एक पिक्सेल चौड़ा है।

आखिरकार, आकार बदलने के बाद मेहराब की छवि:


1024 पिक्सल पर संपीड़न के बाद आर्क

परिणाम निश्चित रूप से सही नहीं है: मूल छवि से पहाड़ के कई किनारे विकृत हैं। सुधारों में से एक वैज्ञानिक लेख में सूचीबद्ध अन्य ऊर्जा कार्यों में से एक का कार्यान्वयन हो सकता है।

---

यद्यपि गतिशील प्रोग्रामिंग आमतौर पर सिद्धांत रूप में चर्चा की जाती है, यह जटिल समस्याओं को हल करने के लिए एक उपयोगी व्यावहारिक तरीका है। इस लेख में, हमने गतिशील प्रोग्रामिंग के अनुप्रयोगों में से एक की जांच की: सीम काटकर सामग्री को फिट करने के लिए छवियों का आकार बदलना।

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