💻 computer science

A Dynamic Programming Framework for Discovering Count and Values of Multilevel Image Thresholding

यह शोध पत्र MET-DP प्रस्तुत करता है, जो एक नवीन डायनेमिक प्रोग्रामिंग फ्रेमवर्क है जो एक संशोधित मिनिमम एरर थ्रेशोल्डिंग मानदंड का उपयोग करके मल्टीलेवल इमेज सेगमेंटेशन के लिए थ्रेशोल्ड की इष्टतम संख्या को स्वचालित रूप से निर्धारित करता है, जो पारंपरिक तरीकों की तुलना में बेहतर कम्प्यूटेशनल दक्षता और स्वचालित थ्रेशोल्ड डिटेक्शन क्षमताओं का प्रदर्शन करता है, हालांकि इसके इमेज क्वालिटी मेट्रिक्स (SSIM और PSNR) यूजर-स्पेसिफाइड दृष्टिकोणों की तुलना में थोड़े कम हैं।

मूल लेखक: Eslam Hegazy, Mohamed Gabr

प्रकाशित 2026-05-27

📖 6 मिनट में पढ़ें🧠 गहराई से पढ़ें

CC BY 4.0

मूल लेखक: Eslam Hegazy, Mohamed Gabr

मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। ✨ नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें

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

कंप्यूटर विजन की दुनिया में, इस छंटनी की प्रक्रिया को इमेज थ्रेशोल्डिंग (image thresholding) कहा जाता है। "थ्रेशोल्ड्स" (thresholds) वे अदृश्य रेखाएं हैं जिन्हें आप रंगों के बीच खींचते हैं ताकि यह तय किया जा सके कि एक समूह कहाँ समाप्त होता है और अगला कहाँ से शुरू होता है।

इस शोध पत्र (paper) का एक सरल विवरण यहाँ दिया गया है, जिसमें रोजमर्रा के उदाहरणों का उपयोग किया गया है:

समस्या: "कितने?" की दुविधा

इन कंचों को छाँटने के पारंपरिक तरीकों के अधिकांश तरीके एक सख्त लाइब्रेरियन की तरह हैं, जिसे आपको काम शुरू करने से पहले यह बताना पड़ता है कि कितने शेल्फ (समूह) बनाने हैं।

उपयोगकर्ता का बोझ: आपको अनुमान लगाना पड़ता है: "क्या मुझे 2 समूह बनाने चाहिए? 5? 10?" यदि आपका अनुमान गलत निकला, तो छंटनी अव्यवस्थित दिखेगी।
धीमा तरीका: सही संख्या में समूह खोजने के लिए, पुराना तरीका 1 शेल्फ, फिर 2, फिर 3, और ऐसे ही 15 तक बनाने की कोशिश करता है, और प्रत्येक की गुणवत्ता की जांच करता है। यह 15 अलग-अलग जूतों की जोड़ी आज़माने जैसा है—यह काम तो करता है, लेकिन इसमें बहुत समय लगता है।
रैंडम तरीका: कुछ नए तरीके "अनुमान और जांच" (जैसे पासा फेंकने वाले एल्गोरिदम) का उपयोग करते हैं। वे तेज़ हैं लेकिन कभी-कभी किसी खराब स्थिति में फंस जाते हैं या हर बार चलाने पर अलग परिणाम देते हैं।

समाधान: "स्मार्ट सॉर्टर" (MET-DP)

इस शोध पत्र के लेखकों ने एक नई विधि बनाई है जिसे MET-DP कहा जाता है। इसे एक "स्मार्ट सॉर्टर" रोबोट के रूप में सोचें जिसे आपको यह बताने की आवश्यकता नहीं है कि कितने शेल्फ बनाने हैं। यह कंचों के जार को देखता है और अपने आप समूहों की सही संख्या का पता लगा लेता है।

यह कैसे काम करता है (जादुई ट्रिक):

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

परिणाम: गति बनाम पूर्णता

लेखकों ने इस "स्मार्ट सॉर्टर" का परीक्षण तीन प्रकार के "जारों" (इमेज) पर किया:

प्रकृति की तस्वीरें (लैंडस्स्केप, जानवर)।
सैटेलाइट तस्वीरें (शहरों और खेतों के मानचित्र)।
मेडिकल तस्वीरें (त्वचा के घाव और मस्तिष्क के स्कैन)।

यहाँ उन्हें क्या पता चला:

गति: स्मार्ट सॉर्टर गति का बादशाह है। क्योंकि यह एक ही बार में समूहों की संख्या का पता लगा लेता है, इसलिए यह पुराने तरीकों की तुलना में बहुत तेज़ है जिन्हें 1, फिर 2, फिर 3 समूह अलग-अलग आज़माना पड़ता है। यदि आपको बड़ी संख्या में कंचों को जल्दी छाँटना है, तो यह विजेता है।
सही संख्या खोजना: यह डेटा में प्राकृतिक समूहों को पहचानने में बहुत अच्छा है। उदाहरण के लिए, यदि किसी तस्वीर में गहरा आसमान, एक ग्रे इमारत और एक सफेद बादल है, तो यह सही ढंग से पहचान लेता है कि वहाँ 3 मुख्य समूह हैं।
"ओवर-स्प्लिटिंग" (ज्यादा विभाजन) की खामी: कभी-कभी, रोबोट थोड़ा अधिक उत्साहित हो जाता है। यदि कंचों के रंग में छोटे, रैंडम उभार (noise) हैं, तो रोबोट उन उभारों को महत्वपूर्ण मान सकता है और बहुत अधिक समूह बना सकता है। यह कंचों को छाँटने और यह तय करने जैसा है कि एक थोड़ा गहरे लाल रंग के कंचे को भी अपने अलग शेल्फ की ज़रूरत है, भले ही वह बाकी कंचों जैसा ही हो।
"अंडर-स्प्लिटिंग" (कम विभाजन) की खामी: इसके विपरीत, कभी-कभी यह छोटे लेकिन महत्वपूर्ण विवरणों को अनदेखा कर देता है, जिससे दो अलग-अलग समूह एक ही बड़े बाल्टी में मिल जाते हैं।
तस्वीर की गुणवत्ता: जब लेखकों ने मानक मेट्रिक्स (SSIM और PSNR) का उपयोग करके अंतिम चित्र की गुणवत्ता को मापा, तो पुराने तरीकों (जहाँ आप समूहों की संख्या बताते हैं) ने आमतौर पर थोड़ा अधिक शार्प और "पिक्सेल-परफेक्ट" इमेज बनाई। स्मार्ट सॉर्टर संरचना (structure) खोजने में बेहतरीन है, लेकिन पुराने तरीके सटीक पिक्सेल विवरणों को बनाए रखने में थोड़े बेहतर हैं यदि आप पहले से जानते हैं कि आपको कितने समूह चाहिए।

निष्कर्ष (Bottom Line)

यह शोध पत्र एक ऐसे टूल को पेश करता है जो स्वचालित रूप से तय करता है कि एक इमेज को कितने समूहों की आवश्यकता है, बिना किसी मानवीय सहायता के।

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

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

तकनीकी सारांश: मल्टीलेवल इमेज थ्रेशोल्डिंग के काउंट और वैल्यूज की खोज के लिए एक डायनेमिक प्रोग्रामिंग फ्रेमवर्क

समस्या विवरण
मल्टीलेवल इमेज थ्रेशोल्डिंग कंप्यूटर विज़न में एक मौलिक प्रीप्रोसेसिंग चरण है, जिसे अक्सर एक क्लस्टरिंग समस्या के रूप में देखा जाता है जहाँ पिक्सेल की तीव्रता को अलग-अलग समूहों में विभाजित किया जाता है। जबकि अत्याधुनिक विधियाँ आमतौर पर एक ऑब्जेक्टिव फंक्शन (जैसे ओत्सु, कपुर, किटलर) और एक सर्च स्ट्रैजी पर निर्भर करती हैं ताकि इष्टतम थ्रेशोल्ड खोजा जा सके, एक महत्वपूर्ण सीमा बनी हुई है: अधिकांश विधियों के लिए उपयोगकर्ता को इनपुट के रूप में थ्रेशोल्ड की संख्या ( $n$ ) को मैन्युअल रूप से निर्दिष्ट करना आवश्यक होता है। उपयुक्त $n$ का निर्धारण करना गैर-तुच्छ कार्य है, क्योंकि SSIM और PSNR जैसे समानता मेट्रिक्स स्वाभाविक रूप से इमेज फिडेलिटी को अधिकतम करने के लिए उच्च थ्रेशोल्ड काउंट की ओर झुकाव रखते हैं, जिससे वे स्वचालित रूप से इष्टतम $n$ चुनने के लिए अनुपयुक्त हो जाते हैं। इसके विपरीत, डायनेमिक प्रोग्रामिंग (DP) जैसी सटीक खोज रणनीतियाँ एक निश्चित $n$ के लिए इष्टतम समाधानों की गारंटी देती हैं, लेकिन जब उपयोगकर्ता कई संभावित $n$ मानों के माध्यम से पुनरावृत्ति करके सर्वश्रेष्ठ $n$ खोजने का प्रयास करता है, तो वे घातीय रनटाइम वृद्धि से ग्रस्त होती हैं। इसके विपरीत, अनुमानित मेटाहेयुरिस्टिक विधियाँ गति प्रदान करती हैं लेकिन स्टोकेस्टिसिटी (stochasticity) और स्थानीय ऑप्टिमा (local optima) के जोखिम के कारण विश्वसनीयता की कमी रखती हैं।

कार्यप्रणाली (Methodology)
लेखक एक नवीन विधि, MET-DP का प्रस्ताव करते हैं, जो एक संशोधित मिनिमम एरर थ्रेशोल्डिंग (MET) मानदंड को डायनेमिक प्रोग्रामिंग एल्गोरिदम के एक विशिष्ट संस्करण के साथ एकीकृत करती है। कार्यप्रणाली के मुख्य योगदान हैं:

संशोधित MET मानदंड: लेखक देखते हैं कि पारंपरिक ऑब्जेक्टिव फंक्शन्स (ओत्सु, कपुर) थ्रेशोल्ड की संख्या बढ़ने के साथ मान में निरंतर वृद्धि (monotonic increase) प्रदर्शित करते हैं, जो उन्हें स्वचालित थ्रेशोल्ड काउंट चयन के लिए अप्रभावी बनाता है। इसके विपरीत, किटलर (MET) मानदंड बढ़ते थ्रेशोल्ड के साथ सख्ती से कम नहीं होता है। लेखक MET मानदंड को संशोधित करते हैं ताकि लागत गणना के दौरान थ्रेशोल्ड मानों को निचले और ऊपरी दोनों वर्गों में शामिल किया जा सके (एक "ओवरलैपिंग" फॉर्मूलेशन), जबकि अंतिम इमेज सेगमेंटेशन के लिए पारंपरिक विलगित (disjoint) असाइनमेंट को बनाए रखा जाए। यह संशोधन एक ऐसा कॉस्ट लैंडस्स्केप बनाता है जहाँ न्यूनतम मान उच्च काउंट के प्रति पक्षपात के बिना, थ्रेशोल्ड की इष्टतम संख्या को इंगित कर सकता है।
डायनेमिक प्रोग्रामिंग वेरिएंट: पारंपरिक DP (एल्गोरिदम 1) के विपरीत जो $n$ को इनपुट के रूप में लेता है और $j$ स्थिति पर $i$ -वें थ्रेशोल्ड के लिए टेबल $dp[i][j] $कंप्यूट करता है, प्रस्तावित एल्गोरिदम (एल्गोरिदम 2)$ [i, j]$ इंटरवल पर पुनरावर्ती (recursively) रूप से कार्य करता है। यह एक अंतराल को एकल क्लास के रूप में या एक इष्टतम बिंदु $k$ पर विभाजित करके सेगमेंट करने की न्यूनतम लागत निर्धारित करता है। रिकरेंस रिलेशन को इस प्रकार परिभाषित किया गया है:
$J(i, j) = \min \left( Q(i, j), \min_{k=i+1}^{j-1} \{ Q(i, k) + J(k, j) \} \right)$
जहाँ $Q$ एक एकल क्लास की लागत है और $J$ कुल लागत है। यह संरचना एल्गोरिदम को एक ही पास में थ्रेशोल्ड मानों के इष्टतम सेट और थ्रेशोल्ड की इष्टतम संख्या को एक साथ खोजने की अनुमति देती है।
जटिलता (Complexity): प्रस्तावित एल्गोरिदम की टाइम कॉम्प्लेक्सिटी $O(L^3)$ और स्पेस कॉम्प्लेक्सिटी $O(L^2)$ है, जहाँ $L$ तीव्रता स्तरों (जैसे 256) की संख्या है। लेखक नोट करते हैं कि जबकि पारंपरिक DP का एक निश्चित $n$ के लिए टाइम कॉम्प्लेक्सिटी $O(n \cdot L^2)$ होती है, प्रस्तावित विधि का रनटाइम थ्रेशोल्ड की संख्या के सापेक्ष प्रभावी रूप से स्थिर रहता है क्योंकि इसे विभिन्न $n$ मानों के लिए पुनरावृत्त रन की आवश्यकता नहीं होती है।

मुख्य परिणाम
MET-DP का मूल्यांकन 15 छवियों (प्राकृतिक, उपग्रह और चिकित्सा) के विविध डेटासेट और सांख्यिकीय विश्लेषण के लिए 718 छवियों के बड़े सेट पर किया गया।

स्वचालित थ्रेशोल्ड चयन: MET-DP ने विभिन्न प्रकार की छवियों के लिए उपयुक्त थ्रेशोल्ड काउंट निर्धारित करने में सफलता प्राप्त की। उदाहरण के लिए, इसने एक ट्राई-मोडल हिस्टोग्राम (इमेज 326085) के लिए 3 थ्रेशोल्ड्स को सही ढंग से पहचाना जहाँ पारंपरिक विधियाँ मोड को सही ढंग से अलग करने में विफल रहीं। हालाँकि, विधि ने हिस्टोग्राम के मामूली उतार-चढ़ाव के प्रति संवेदनशीलता दिखाई, जिससे कुछ मेडिकल इमेजेस (जैसे इमेज 007-Flair-60 में 25 थ्रेशोल्ड) में "ओवर-थ्रेशोल्डिंग" और अन्य में (जैसे Tile-8-Part-008 में अलग-अलग पीक्स को मर्ज करना) "अंडर-थ्रेशोल्डिंग" हुई।
रनटाइम दक्षता: 1 से 15 तक के थ्रेशोल्ड काउंट के लिए पारंपरिक विधियों को पुनरावृत्त रूप से चलाने वाले तुलनात्मक परीक्षणों में, MET-DP ने काफी कम कुल CPU रनटाइम प्रदर्शित किया। जहाँ पारंपरिक विधियों का रनटाइम टेस्ट किए गए काउंट्स की संख्या के साथ बहुपद रूप से ( $O(m^2 \cdot L^2)$ ) बढ़ता है, वहीं MET-DP का रनटाइम केवल $L$ पर निर्भर एक स्थिर रनटाइम बनाए रखता है।
सेगमेंटेशन गुणवत्ता:
- SSIM: MET-DP ने प्रतिस्पर्धी स्ट्रक्चरल सिमिलरिटी इंडेक्स मेजर (SSIM) मान प्राप्त किए, जो अक्सर जटिल मल्टीमॉडल हिस्टोग्राम वाली छवियों (जैसे प्राकृतिक इमेज 147091 और 77200701) पर पारंपरिक विधियों से बेहतर प्रदर्शन करते हैं।
- PSNR: विधि आम तौर पर ओत्सु और कपुर की तुलना में कम पीक सिग्नल-टू-नॉइज़ रेशियो (PSNR) मान उत्पन्न करती है। लेखक इस प्रभाव को विधि की सूक्ष्म उतार-चढ़ाव को अलग करने की प्रवृत्ति के कारण बताते हैं, जो पारंपरिक विधियों द्वारा उत्पादित स्मूथ सेगमेंटेशन की तुलना में पिक्सेल-स्तरीय फिडेलिटी को कम करता है।

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

लेखक विनम्रतापूर्वक निष्कर्ष निकालते हैं कि हालांकि MET-DP कम्प्यूटेशनल दक्षता और स्वचालित पैरामीटर चयन के मामले में श्रेष्ठ है, लेकिन यह कच्चे इमेज रिकंस्ट्रक्शन की गुणवत्ता (PSNR) के मामले में पारंपरिक विधियों से सार्वभौमिक रूप से बेहतर प्रदर्शन नहीं करता है। वे सुझाव देते हैं कि यह विधि उन अनुप्रयोगों के लिए विशेष रूप से उपयुक्त है जिनमें स्वचालित थ्रेशोल्ड चयन की आवश्यकता होती है और जहाँ सूक्ष्म तीव्रता भिन्नताओं को अलग करना महत्वपूर्ण है, जबकि पारंपरिक विधियाँ उन कार्यों के लिए बेहतर हो सकती हैं जो उच्च PSNR या शोर-सहिष्णु (noise-tolerant), मोटे सेगमेंटेशन को प्राथमिकता देते हैं। यह पेपर नए अनुप्रयोगों का प्रस्ताव नहीं करता है बल्कि MET-DP को अनसुपरवाइज्ड थ्रेशोल्ड काउंट निर्धारण की विशिष्ट समस्या के लिए एक मजबूत विकल्प के रूप में स्थापित करता है।

समस्या: "कितने?" की दुविधा

समाधान: "स्मार्ट सॉर्टर" (MET-DP)

परिणाम: गति बनाम पूर्णता

निष्कर्ष (Bottom Line)

इसी तरह के और पेपर