ग्राफ कट्स (Graph cuts) कंप्यूटर विज़न और कृत्रिम बुद्धिमत्ता में उत्पन्न होने वाली ऊर्जा न्यूनीकरण समस्याओं को हल करने के लिए उपयोग की जाने वाली संयोजनात्मक अनुकूलन विधियों का एक परिवार है। मूल विचार एक लेबलिंग या विभाजन समस्या को एक ग्राफ के रूप में प्रस्तुत करना है, जहाँ नोड्स पिक्सेल या डेटा बिंदुओं के अनुरूप होते हैं, और किनारे युग्म संबंधों को एन्कोड करते हैं। समस्या को हल करना तब ग्राफ में न्यूनतम कट खोजने तक सीमित हो जाता है, जो नोड्स को असंयुक्त समुच्चयों में विभाजित करता है जबकि लागत फलन को न्यूनतम करता है। यह दृष्टिकोण द्विआधारी लेबलिंग समस्याओं, जैसे अग्रभूमि-पृष्ठभूमि विभाजन, के लिए विशेष रूप से प्रभावी है, और इसे अल्फा-विस्तार जैसी तकनीकों के माध्यम से बहु-लेबल समस्याओं तक बढ़ाया जा सकता है।
ग्राफ कट्स की गणितीय नींव अधिकतम-प्रवाह न्यूनतम-कट प्रमेय में निहित है, जो बताती है कि नेटवर्क में स्रोत से सिंक तक अधिकतम प्रवाह उन्हें अलग करने वाले कट की न्यूनतम क्षमता के बराबर होता है। कंप्यूटर विज़न में, इस प्रमेय का उपयोग दो विशेष टर्मिनल नोड्स (स्रोत और सिंक) वाला ग्राफ बनाकर किया जाता है जो दो लेबलों का प्रतिनिधित्व करते हैं। प्रत्येक पिक्सेल दोनों टर्मिनलों से किनारों के साथ जुड़ा होता है जिनकी क्षमताएँ उस पिक्सेल को प्रत्येक लेबल निर्दिष्ट करने की एकल लागत को दर्शाती हैं। इसके अतिरिक्त, पड़ोसी पिक्सेल के बीच के किनारे चिकनाई दंड को एन्कोड करते हैं, जो सुसंगत क्षेत्रों को प्रोत्साहित करते हैं। न्यूनतम कट तब एक इष्टतम लेबलिंग उत्पन्न करता है जो डेटा निष्ठा को स्थानिक नियमितता के साथ संतुलित करता है।
ऐतिहासिक विकास
कंप्यूटर विज़न में ग्राफ कट्स का उपयोग 1990 के दशक के अंत और 2000 के दशक की शुरुआत में प्रमुखता प्राप्त हुई, जो संयोजनात्मक अनुकूलन में पहले के काम पर आधारित था। मुख्य योगदान यूरी बॉयकोव और व्लादिमीर कोलमोगोरोव जैसे शोधकर्ताओं से आए, जिन्होंने विज़न समस्याओं में न्यूनतम कट्स की गणना के लिए कुशल एल्गोरिदम पेश किए। उनका 2001 का इंटरैक्टिव छवि विभाजन पर पेपर, जो उपयोगकर्ताओं को अग्रभूमि और पृष्ठभूमि क्षेत्रों को चिह्नित करने की अनुमति देता था, अत्यधिक प्रभावशाली बन गया। लगभग उसी समय, ग्राफ कट्स और मार्कोव यादृच्छिक क्षेत्रों (MRFs) के बीच संबंध को औपचारिक रूप दिया गया, जिससे पता चला कि युग्म शब्दों वाले कई ऊर्जा फलनों को ग्राफ-आधारित विधियों का उपयोग करके सटीक या अनुमानित रूप से न्यूनतम किया जा सकता है।
कंप्यूटर विज़न में अनुप्रयोग
ग्राफ कट्स को विज़न कार्यों की एक विस्तृत श्रृंखला पर लागू किया गया है। छवि विभाजन में, उनका उपयोग वस्तुओं को पृष्ठभूमि से अलग करने के लिए किया जाता है, अक्सर प्रक्रिया को निर्देशित करने के लिए उपयोगकर्ता की सहभागिता के साथ। चिकित्सा इमेजिंग सीटी या एमआरआई स्कैन में अंग सीमांकन के लिए ग्राफ कट्स से लाभान्वित होती है, जहाँ सीमा और क्षेत्र की जानकारी को शामिल करने की विधि की क्षमता मूल्यवान है। स्टीरियो मिलान, जो दो छवियों से गहराई का अनुमान लगाता है, चिकनाई लागू करते हुए विस्थापन लेबल निर्दिष्ट करने के लिए भी ग्राफ कट्स का उपयोग करता है। अन्य अनुप्रयोगों में छवि शोर हटाना शामिल है, जहाँ लक्ष्य शोर अवलोकन से एक स्वच्छ छवि को पुनर्स्थापित करना है, और बहु-दृश्य पुनर्निर्माण, जहाँ ग्राफ कट्स कई कैमरा दृश्यों से 3D सतहों को जोड़ने में मदद करते हैं।
ऊर्जा न्यूनीकरण से संबंध
कृत्रिम बुद्धिमत्ता में, ग्राफ कट्स ऊर्जा-आधारित मॉडलों का एक विशिष्ट उदाहरण हैं, जहाँ लक्ष्य एक वैश्विक लागत को न्यूनतम करने वाला विन्यास खोजना है। ऊर्जा में आम तौर पर एक एकल शब्द होता है, जो एकल चर को लेबल निर्दिष्ट करने की लागत को मापता है, और एक युग्म शब्द, जो पड़ोसी चरों को लेबल निर्दिष्ट करने की लागत को मापता है। सबमॉड्यूलर युग्म क्षमता वाले द्विआधारी चर के लिए, न्यूनतम को ग्राफ कट्स का उपयोग करके बहुपद समय में सटीक रूप से पाया जा सकता है। बहु-लेबल समस्याओं के लिए, अल्फा-विस्तार और अल्फा-बीटा स्वैप जैसे अनुमानित एल्गोरिदम द्विआधारी उपसमस्याओं को पुनरावृत्त रूप से हल करके अच्छे समाधान प्रदान करते हैं। ये विधियाँ Machine learning में संरचित भविष्यवाणी कार्यों के लिए व्यापक रूप से उपयोग की जाती हैं, जैसे Deep learning पाइपलाइनों में अर्थ विभाजन।
आधुनिक संदर्भ और विकल्प
Neural network आधारित दृष्टिकोणों के उदय के साथ, विशेष रूप से U-Net आर्किटेक्चर और Residual Network (ResNet) मॉडल, एंड-टू-एंड लर्निंग में ग्राफ कट्स पहले की तुलना में कम प्रभावी हैं। हालाँकि, वे पोस्ट-प्रोसेसिंग चरणों या हाइब्रिड सिस्टम में विभेदन योग्य घटकों के रूप में प्रासंगिक बने हुए हैं। उदाहरण के लिए, ग्राफ कट्स स्थानिक सुसंगतता लागू करने के लिए Deep learning मॉडल के मोटे आउटपुट को परिष्कृत कर सकते हैं। उनका उपयोग Data Augmentation पाइपलाइनों में प्रशिक्षण लेबल उत्पन्न करने के लिए भी किया जाता है। आधुनिक अधिकतम-प्रवाह एल्गोरिदम की कम्प्यूटेशनल दक्षता, जैसे कि बॉयकोव-कोलमोगोरोव जैसी लाइब्रेरीज़ में लागू, उन्हें वास्तविक समय के अनुप्रयोगों के लिए व्यावहारिक बनाती है। जबकि Generative AI और Large language model सिस्टम ने उच्च-आयामी असतत समस्याओं पर ध्यान केंद्रित किया है, ग्राफ कट्स संरचित आउटपुट स्थानों में एक मौलिक उपकरण के रूप में काम करना जारी रखते हैं।
सीमाएँ और विस्तार
ग्राफ कट्स सटीक समाधानों के लिए सबमॉड्यूलरिटी पर अपनी निर्भरता से सीमित हैं। गैर-सबमॉड्यूलर ऊर्जाएँ, जो कुछ विज़न कार्यों में उत्पन्न होती हैं, के लिए वैकल्पिक विधियों की आवश्यकता होती है जैसे कि द्विघात छद्म-बूलियन अनुकूलन या मूव-मेकिंग एल्गोरिदम जो इष्टतमता की गारंटी नहीं दे सकते हैं। मेमोरी और समय की जटिलता भी छवि आकार के साथ बढ़ती है, हालाँकि GPU पर समानांतर कार्यान्वयन ने इसे कम किया है। विस्तार में वीडियो अनुक्रमों के लिए गतिशील ग्राफ कट्स शामिल हैं, जहाँ ग्राफ को वृद्धिशील रूप से अद्यतन किया जाता है, और उच्च-क्रम क्षमताएँ जो अधिक जटिल अंतःक्रियाओं को पकड़ती हैं। Reinforcement learning और अन्य AI प्रतिमानों के साथ ग्राफ कट्स को एकीकृत करने पर शोध जारी है, हालाँकि मूल तकनीक एक क्लासिक उदाहरण बनी हुई है कि कैसे संयोजनात्मक अनुकूलन धारणा के साथ प्रतिच्छेद करता है।