Graph cuts in computer vision
जैसा कि कंप्यूटर दृष्टि के क्षेत्र में लागू किया जाता है, ग्राफ कट अनुकूलन को निम्न-स्तरीय कंप्यूटर दृष्टि समस्याओं (प्रारंभिक दृष्टि) की एक विस्तृत विविधता को कुशलता से हल करने के लिए नियोजित किया जा सकता है, जैसे कि छवि सुचारू, स्टीरियो पत्राचार समस्या, छवि विभाजन, वस्तु सह-विभाजन, और कई अन्य कंप्यूटर दृष्टि समस्याएं जिन्हें ऊर्जा न्यूनतम के संदर्भ में तैयार किया जा सकता है। इनमें से कई ऊर्जा न्यूनीकरण समस्याओं को एक ग्राफ में अधिकतम प्रवाह समस्या को हल करके अनुमानित किया जा सकता है (और इस प्रकार, अधिकतम-प्रवाह न्यूनतम-कटौती प्रमेय द्वारा, ग्राफ के न्यूनतम कटौती को परिभाषित करें)। कंप्यूटर दृष्टि में ऐसी समस्याओं के अधिकांश सूत्रीकरणों के तहत, न्यूनतम ऊर्जा समाधान एक समाधान के अधिकतम पश्च अनुमान से मेल खाता है। हालांकि कई कंप्यूटर दृष्टि एल्गोरिदम में एक ग्राफ को काटना शामिल है (जैसे, सामान्यीकृत कटौती), "ग्राफ कटौती" शब्द विशेष रूप से उन मॉडलों पर लागू किया जाता है जो अधिकतम-प्रवाह/न्यूनतम-कटौती अनुकूलन को नियोजित करते हैं (अन्य ग्राफ काटने के एल्गोरिदम को ग्राफ विभाजन एल्गोरिदम के रूप में माना जा सकता है)। "द्विआधारी" समस्याओं (जैसे कि द्विआधारी छवि को निरूपित करना) को इस दृष्टिकोण का उपयोग करके ठीक से हल किया जा सकता है; ऐसी समस्याएं जहां पिक्सेल को दो से अधिक अलग-अलग लेबलों (जैसे स्टीरियो पत्राचार, या ग्रेस्केल छवि को निरूपित करना) के साथ लेबल किया जा सकता है, ठीक से हल नहीं किया जा सकता है, लेकिन उत्पादित समाधान आमतौर पर वैश्विक इष्टतम के करीब होते हैं। एक अनुकूलन विधि के रूप में उपयोग किए जाने वाले ग्राफ कट के सिद्धांत को पहली बार डरहम विश्वविद्यालय के ग्रेग, पोर्टियस और सेहल्ट द्वारा मौलिक पेपर में कंप्यूटर दृष्टि में लागू किया गया था। एलन सेहल्ट और ब्रूस पोर्टियस जूलियन बेसाग और पीटर ग्रीन के नेतृत्व में डरहम के उस समय के प्रशंसित सांख्यिकी समूह के सदस्य थे, जिसमें अनुकूलन विशेषज्ञ मार्गरेट ग्रेग डरहम गणितीय विज्ञान विभाग की पहली महिला कर्मचारी के रूप में उल्लेखनीय थीं। शोर (या दूषित) छवियों को चिकना करने के बायेसियन सांख्यिकीय संदर्भ में, उन्होंने दिखाया कि कैसे एक द्विआधारी छवि का अधिकतम पश्च अनुमान एक संबद्ध छवि नेटवर्क के माध्यम से प्रवाह को अधिकतम करके प्राप्त किया जा सकता है, जिसमें एक स्रोत और सिंक का परिचय शामिल है। इसलिए समस्या को कुशलता से हल करने योग्य दिखाया गया था। इस परिणाम से पहले, इस तरह की छवि को सुचारू बनाने की समस्याओं को हल करने के लिए नकली एनीलिंग (जैसा कि गेमन भाइयों द्वारा प्रस्तावित), या पुनरावृत्त सशर्त मोड (जूलियन बेसाग द्वारा सुझाए गए लालची एल्गोरिदम का एक प्रकार) जैसी अनुमानित तकनीकों का उपयोग किया जाता था। हालाँकि ग्रेग के दृष्टिकोण के लिए सामान्य-रंग समस्या अनसुलझी है, लेकिन सामान्य कंप्यूटर दृष्टि समस्याओं में पोर्टियस और सेहल्ट की व्यापक प्रयोज्यता पाई गई है। ग्रेग, पोर्टियस और सेहल्ट के दृष्टिकोण को अक्सर द्विआधारी समस्याओं के एक क्रम पर बार-बार लागू किया जाता है, जो आमतौर पर लगभग इष्टतम समाधान देते हैं। 2011 में, सी. कूपरी और अन्य। एक सामान्य छवि विभाजन ढांचे का प्रस्ताव किया, जिसे "पावर वाटरशेड" कहा जाता है, जो एक ग्राफ पर [0,1] से एक वास्तविक-मूल्यवान संकेतक फ़ंक्शन को न्यूनतम करता है, जो उपयोगकर्ता बीज (या यूनरी शब्दों) द्वारा 0 या 1 पर सेट किया जाता है, जिसमें ग्राफ पर संकेतक फ़ंक्शन का न्यूनतमकरण एक प्रतिपादक के संबंध में अनुकूलित किया जाता है। जब, पावर वाटरशेड को ग्राफ कट द्वारा अनुकूलित किया जाता है, जब पावर वाटरशेड को सबसे छोटे रास्तों द्वारा अनुकूलित किया जाता है, तो यादृच्छिक वॉकर एल्गोरिदम द्वारा अनुकूलित किया जाता है और वाटरशेड एल्गोरिदम द्वारा अनुकूलित किया जाता है। इस तरह, पावर वाटरशेड को ग्राफ कट के सामान्यीकरण के रूप में देखा जा सकता है जो अन्य ऊर्जा अनुकूलन विभाजन/क्लस्टरिंग एल्गोरिदम के साथ एक सीधा संबंध प्रदान करता है। छवियों का द्विआधारी विभाजन संकेतन छविः आउटपुटः विभाजन (जिसे अपारदर्शिता भी कहा जाता है) (नरम विभाजन)। कठिन विभाजन ऊर्जा फलन के लिएः जहाँ C रंग पैरामीटर है और λ सुसंगतता पैरामीटर है। अनुकूलन-विभाजन का अनुमान एस पर वैश्विक न्यूनतम के रूप में लगाया जा सकता हैः मौजूदा तरीके मानक ग्राफ में कटौतीः विभाजन पर ऊर्जा कार्य का अनुकूलन (अज्ञात एस मूल्य)। पुनरावृत्त ग्राफ कटः पहला चरण के-मीन्स का उपयोग करके रंग मापदंडों पर अनुकूलित करता है। दूसरा चरण सामान्य ग्राफ कट एल्गोरिदम का प्रदर्शन करता है। इन 2 चरणों को अभिसरण तक पुनरावर्ती रूप से दोहराया जाता है। गतिशील ग्राफ कटौतीः समस्या को संशोधित करने के बाद एल्गोरिथ्म को बहुत तेजी से फिर से चलाने की अनुमति देता है (जैसे। एक उपयोगकर्ता द्वारा नए बीज जोड़े जाने के बाद)। ऊर्जा फलन जहाँ ऊर्जा दो अलग-अलग मॉडलों (और) से बनी होती हैः संभावना/रंग मॉडल/क्षेत्रीय शब्द-प्रत्येक रंग की संभावना का वर्णन करने वाला एक शब्द। इस शब्द को विभिन्न स्थानीय (जैसे) का उपयोग करके मॉडल किया जा सकता है। या वैश्विक (जैसे। हिस्टोग्राम, जी. एम. एम., एडाबोस्ट संभावना) दृष्टिकोण जो नीचे वर्णित हैं। हिस्टोग्राम हम वस्तु (अग्रभूमि) और पृष्ठभूमि तीव्रता वितरण के लिए हिस्टोग्राम प्राप्त करने के लिए बीज के रूप में चिह्नित पिक्सेल की तीव्रता का उपयोग करते हैंः पी (I|O) और पी (I|B)। फिर, हम इन हिस्टोग्राम का उपयोग क्षेत्रीय दंड को नकारात्मक लॉग-लाइक्लिहुड्स के रूप में निर्धारित करने के लिए करते हैं। जी. एम. एम. (गौसी मिश्रण मॉडल) हम आमतौर पर दो वितरणों का उपयोग करते हैंः एक पृष्ठभूमि मॉडलिंग के लिए और दूसरा अग्रभूमि पिक्सेल के लिए। उन 2 वितरणों को मॉडल करने के लिए एक गौसी मिश्रण मॉडल (5-8 घटकों के साथ) का उपयोग करें। लक्ष्यः उन दोनों वितरणों को अलग करने का प्रयास करें। टेक्सॉन ए (या) पिक्सेल का एक समूह है जिसमें कुछ विशेषताएँ होती हैं और इसे एक छवि में दोहराया जाता है। कदमः बनावट तत्वों के लिए एक अच्छा प्राकृतिक पैमाना निर्धारित करें। मॉडल-आंतरिक के गैर-पैरामीट्रिक आंकड़ों की गणना करें, या तो तीव्रता पर या गैबर फ़िल्टर प्रतिक्रियाओं पर। उदाहरण के लिएः विकृत-मॉडल आधारित बनावट वस्तु विभाजन समोच्च और छवि विभाजन के लिए बनावट विश्लेषण पूर्व/सुसंगतता मॉडल/सीमा शब्द-द्विआधारी शब्द जो पड़ोस पिक्सेल के बीच सुसंगतता का वर्णन करता है। व्यवहार में, पिक्सेल को पड़ोसियों के रूप में परिभाषित किया जाता है यदि वे क्षैतिज रूप से, ऊर्ध्वाधर रूप से या विकर्ण रूप से (2 डी छवियों के लिए 4-तरफा संपर्क या 8-तरफा संपर्क) आसन्न हैं। लागत स्थानीय तीव्रता प्रवणता, लाप्लासियन शून्य-पार, प्रवणता दिशा, रंग मिश्रण मॉडल पर आधारित हो सकती है। विभिन्न ऊर्जा कार्यों को परिभाषित किया गया हैः मानक मार्कोव यादृच्छिक क्षेत्रः उनके विभाजन लेबल (सीमाओं की लंबाई का कच्चा माप) के बीच अंतर का मूल्यांकन करके असंतुष्ट पिक्सेल के लिए एक दंड को संबद्ध करें। बॉयकोव और कोल्मोगोरोव आईसीसीवी 2003 सशर्त यादृच्छिक क्षेत्रः यदि रंग बहुत अलग है, तो यह सीमा लगाने के लिए एक अच्छी जगह हो सकती है। लाफर्टी एट अल को देखें। 2001; कुमार और हेबर्ट 2003 आलोचना ग्राफ कटौती विधियाँ एक समोच्च के स्थान को अनुकूलित करने के लिए स्तर सेट-आधारित दृष्टिकोणों के लिए लोकप्रिय विकल्प बन गई हैं (एक व्यापक तुलना के लिए देखें)। हालांकि, कई मुद्दों के लिए साहित्य में ग्राफ कट दृष्टिकोण की आलोचना की गई हैः मापन कलाकृतियाँः जब एक छवि को 4-जुड़े जाली द्वारा दर्शाया जाता है, तो ग्राफ कट विधियाँ अवांछित "अवरोध" कलाकृतियों को प्रदर्शित कर सकती हैं। इस मुद्दे को हल करने के लिए विभिन्न विधियों का प्रस्ताव किया गया है, जैसे कि अतिरिक्त किनारों का उपयोग करना या निरंतर स्थान में अधिकतम-प्रवाह समस्या तैयार करना। सिकुड़ता पक्षपातः चूंकि ग्राफ में कटौती एक न्यूनतम कटौती पाती है, इसलिए एल्गोरिथ्म को एक छोटे समोच्च के उत्पादन की दिशा में पक्षपाती माना जा सकता है। उदाहरण के लिए, एल्गोरिथ्म रक्त वाहिकाओं जैसी पतली वस्तुओं के विभाजन के लिए अच्छी तरह से अनुकूल नहीं है (एक प्रस्तावित सुधार के लिए देखें)। कई लेबलः ग्राफ कट केवल द्विआधारी लेबलिंग (यानी, दो लेबल) समस्याओं के लिए एक वैश्विक इष्टतम खोजने में सक्षम है, जैसे कि अग्रभूमि/पृष्ठभूमि छवि विभाजन। ऐसे विस्तार प्रस्तावित किए गए हैं जो बहु-लेबल ग्राफ कटौती समस्याओं के लिए अनुमानित समाधान ढूंढ सकते हैं। मेमोरीः जैसे-जैसे छवि का आकार बढ़ता है, ग्राफ कट की मेमोरी का उपयोग तेजी से बढ़ता है। एक उदाहरण के रूप में, बॉयकोव-कोल्मोगोरोव मैक्स-फ्लो एल्गोरिथ्म v2.2 बाइट्स आवंटित करता है (और ग्राफ में क्रमशः नोड्स और किनारों की संख्या है)। फिर भी, अधिकतम प्रवाह गणना से पहले ग्राफ को कम करने के लिए हाल ही में इस दिशा में कुछ काम किया गया है। एल्गोरिदम मिनिमाइजेशन एक मानक न्यूनतम कट एल्गोरिदम का उपयोग करके किया जाता है। अधिकतम-प्रवाह न्यूनतम-कटौती प्रमेय के कारण हम नेटवर्क पर प्रवाह को अधिकतम करके ऊर्जा न्यूनतमकरण को हल कर सकते हैं। अधिकतम-प्रवाह समस्या में क्षमताओं के साथ लेबल किए गए किनारों के साथ एक निर्देशित ग्राफ होता है, और दो अलग-अलग नोड्स होते हैंः स्रोत और सिंक। सहज रूप से, यह देखना आसान है कि अधिकतम प्रवाह बाधा द्वारा निर्धारित किया जाता है। कार्यान्वयन (सटीक) बॉयकोव-कोल्मोगोरोव एल्गोरिथ्म कंप्यूटर दृष्टि से संबंधित ग्राफ के लिए अधिकतम प्रवाह की गणना करने का एक कुशल तरीका है। कार्यान्वयन (अनुमान) सिम कट एल्गोरिदम न्यूनतम ग्राफ कट का अनुमान लगाता है। एल्गोरिथ्म एक विद्युत नेटवर्क के अनुकरण द्वारा एक समाधान लागू करता है। यह सीडरबाम के अधिकतम प्रवाह प्रमेय द्वारा सुझाया गया दृष्टिकोण है। समानांतर गणना के माध्यम से एल्गोरिथ्म का त्वरण संभव है। सॉफ्टवेयर http://pub.ist.ac.at ~ vnk/सॉफ्टवेयर. एच. टी. एम. एल.-व्लादिमीर कोल्मोगोरोव http://vision.csd.uwo.ca/code द्वारा "कंप्यूटर दृष्टि में ऊर्जा न्यूनतमकरण के लिए न्यूनतम-कटौती/अधिकतम-प्रवाह एल्गोरिदम की एक प्रयोगात्मक तुलना" में वर्णित अधिकतम प्रवाह एल्गोरिदम का कार्यान्वयन-कुछ ग्राफ कट पुस्तकालय और MATLAB रैपर http://gridcut.com-ग्रिड जैसे ग्राफ http://virtualscalpel.com के लिए अनुकूलित तेज बहु-कोर अधिकतम-प्रवाह/न्यूनतम-कटौती समाधानकर्ता-सिम कट का कार्यान्वयन; बड़े पैमाने पर समानांतर तरीके से न्यूनतम एस-टी कटौती के अनुमानित समाधान की गणना करने के लिए एक एल्गोरिदम। संदर्भ बायेसियन सांख्यिकी ग्राफ सिद्धांत में कंप्यूटर दृष्टि कम्प्यूटेशनल समस्याएं छवि विभाजन