Graph cuts in computer vision
جیسا کہ کمپیوٹر وژن کے میدان میں لاگو کیا جاتا ہے، گراف کٹ آپٹیمائزیشن کو مختلف قسم کے نچلے درجے کے کمپیوٹر وژن کے مسائل (ابتدائی وژن) کو مؤثر طریقے سے حل کرنے کے لیے استعمال کیا جا سکتا ہے، جیسے کہ امیج ہموار کرنا، سٹیریو خط و کتابت کا مسئلہ، امیج سیگمنٹشن، آبجیکٹ کو-سیگمنٹشن، اور کمپیوٹر وژن کے بہت سے دوسرے مسائل جنہیں توانائی کو کم کرنے کے لحاظ سے وضع کیا جا سکتا ہے۔ ان میں سے بہت سے توانائی کو کم کرنے کے مسائل کا تخمینہ گراف میں زیادہ سے زیادہ بہاؤ کے مسئلے کو حل کرکے لگایا جا سکتا ہے (اور اس طرح، میکس فلو من کٹ تھیوریم کے ذریعہ، گراف کے کم سے کم کٹ کی وضاحت کریں)۔ کمپیوٹر وژن میں اس طرح کے مسائل کی زیادہ تر فارمولیشن کے تحت، کم از کم توانائی کا حل کسی حل کے زیادہ سے زیادہ پوسٹرری تخمینے سے مطابقت رکھتا ہے۔ اگرچہ بہت سے کمپیوٹر وژن الگورتھم میں گراف کو کاٹنا شامل ہوتا ہے (مثال کے طور پر، نارملائزڈ کٹس)، اصطلاح "گراف کٹس" کا اطلاق خاص طور پر ان ماڈلز پر ہوتا ہے جو میکس فلو/منٹ کٹ آپٹیمائزیشن کا استعمال کرتے ہیں (گراف کاٹنے والے دوسرے الگورتھم کو گراف پارٹیشننگ الگورتھم سمجھا جا سکتا ہے)۔ "بائنری" مسائل (جیسے کہ بائنری امیج کو ڈی نوائز کرنا) کو بالکل اس نقطہ نظر کا استعمال کرتے ہوئے حل کیا جا سکتا ہے ؛ ایسے مسائل جہاں پکسلز کو دو سے زیادہ مختلف لیبلز کے ساتھ لیبل کیا جا سکتا ہے (جیسے کہ سٹیریو خط و کتابت، یا گرے اسکیل امیج کو ڈی نوائز کرنا) کو بالکل حل نہیں کیا جا سکتا، لیکن تیار کردہ حل عام طور پر عالمی زیادہ سے زیادہ کے قریب ہوتے ہیں۔ اصلاح کے طریقہ کار کے طور پر استعمال ہونے والے گراف کٹ کے نظریہ کا اطلاق سب سے پہلے کمپیوٹر وژن میں بنیادی مقالے میں ڈرہم یونیورسٹی کے گریگ، پورٹیئس اور سیہلٹ نے کیا تھا۔ ایلن سیہلٹ اور بروس پورٹیئس ڈرہم کے اس وقت کے سراہی جانے والے شماریاتی گروپ کے رکن تھے، جس کی قیادت جولین بیساگ اور پیٹر گرین کر رہے تھے، جس میں اصلاحاتی ماہر مارگریٹ گریگ ڈرہم ریاضیاتی علوم کے شعبہ کے عملے کی پہلی خاتون رکن کے طور پر قابل ذکر تھیں۔ شور (یا خراب) تصاویر کو ہموار کرنے کے بایسیائی شماریاتی تناظر میں، انہوں نے دکھایا کہ کس طرح بائنری امیج کا زیادہ سے زیادہ پوسٹرری تخمینہ ایک متعلقہ امیج نیٹ ورک کے ذریعے بہاؤ کو زیادہ سے زیادہ کرکے حاصل کیا جاسکتا ہے، جس میں ماخذ اور سنک کا تعارف شامل ہوتا ہے۔ اس لیے یہ مسئلہ مؤثر طریقے سے حل کرنے کے قابل ثابت ہوا۔ اس نتیجے سے پہلے، امیج کو ہموار کرنے کے اس طرح کے مسائل کو حل کرنے کے لیے تخمینی تکنیکیں جیسے مصنوعی اینیلنگ (جیسا کہ جیمن برادران نے تجویز کیا تھا)، یا تکرار شدہ مشروط طریقے (جولین بیساگ کے تجویز کردہ لالچی الگورتھم کی ایک قسم) استعمال کیے جاتے تھے۔ اگرچہ گریگ کے نقطہ نظر کے لیے عام رنگ کا مسئلہ حل نہیں ہوا ہے، لیکن پورٹیئس اور سیہلٹ عام کمپیوٹر وژن کے مسائل میں وسیع پیمانے پر قابل اطلاق ثابت ہوئے ہیں۔ گریگ، پورٹیئس اور سیہلٹ کے نقطہ نظر کو اکثر بائنری مسائل کے سلسلے میں بار بار لاگو کیا جاتا ہے، جو عام طور پر قریب ترین حل فراہم کرتے ہیں۔ 2011 میں، سی۔ کوپری اور دیگر۔ ایک عام امیج سیگمنٹشن فریم ورک کی تجویز پیش کی، جسے "پاور واٹرشیڈ" کہا جاتا ہے، جس نے گراف پر [0,1] سے ایک حقیقی قدر والے اشارے کے فنکشن کو کم سے کم کیا، جو صارف کے بیج (یا یونری اصطلاحات) کے ذریعہ 0 یا 1 پر سیٹ کیا گیا ہے، جس میں گراف پر اشارے کے فنکشن کو کم سے کم کرنا ایک ایکسپوینٹ کے حوالے سے بہتر بنایا گیا ہے۔ جب پاور واٹرشیڈ کو گراف کٹ کے ذریعے بہتر بنایا جاتا ہے، جب پاور واٹرشیڈ کو مختصر ترین راستوں کے ذریعے بہتر بنایا جاتا ہے، تو اسے بے ترتیب واکر الگورتھم کے ذریعے بہتر بنایا جاتا ہے اور واٹرشیڈ الگورتھم کے ذریعے بہتر بنایا جاتا ہے۔ اس طرح، پاور واٹرشیڈ کو گراف کٹ کی عمومی شکل کے طور پر دیکھا جا سکتا ہے جو دیگر توانائی کی اصلاح کی تقسیم/کلسٹرنگ الگورتھم کے ساتھ سیدھا رابطہ فراہم کرتا ہے۔ تصاویر کی بائنری سیگمنٹشن نوٹیشن امیج: آؤٹ پٹ: سیگمنٹشن (جسے اوپیسیٹی بھی کہا جاتا ہے) (سافٹ سیگمنٹشن)۔ ہارڈ سیگمنٹشن انرجی فنکشن کے لیے: جہاں C رنگ کا پیمانہ ہے اور λ ہم آہنگی کا پیمانہ ہے۔ اصلاح: تقسیم کا تخمینہ ایس پر عالمی کم از کم کے طور پر لگایا جا سکتا ہے: موجودہ طریقے معیاری گراف میں کٹوتی: تقسیم پر توانائی کے فنکشن کو بہتر بنانا (نامعلوم ایس ویلیو)۔ تکرار شدہ گراف کٹس: پہلا مرحلہ K-کا استعمال کرتے ہوئے رنگ کے پیرامیٹرز کو بہتر بناتا ہے۔ دوسرا مرحلہ معمول کے گراف کٹ الگورتھم کو انجام دیتا ہے۔ ان 2 مراحل کو ہم آہنگی تک بار بار دہرایا جاتا ہے۔ متحرک گراف میں کٹوتی: مسئلہ میں ترمیم کرنے کے بعد الگورتھم کو بہت تیزی سے دوبارہ چلانے کی اجازت دیتا ہے (جیسے۔ ایک صارف کی طرف سے نئے بیج شامل کرنے کے بعد)۔ توانائی فنکشن جہاں توانائی دو مختلف ماڈلز (اور) پر مشتمل ہوتی ہے: امکان/رنگین ماڈل/علاقائی اصطلاح-ہر رنگ کے امکان کو بیان کرنے والی یک اصطلاح۔ اس اصطلاح کو مختلف مقامی (مثال کے طور پر) کا استعمال کرتے ہوئے بنایا جا سکتا ہے۔ یا عالمی (مثال کے طور پر۔ ہسٹوگرام، جی ایم ایم، ایڈابوسٹ امکان) نقطہ نظر جو ذیل میں بیان کیے گئے ہیں۔ ہسٹوگرام ہم آبجیکٹ (فور گراؤنڈ) اور پس منظر کی شدت کی تقسیم کے لیے ہسٹوگرام حاصل کرنے کے لیے بیج کے طور پر نشان زد پکسلز کی شدت کا استعمال کرتے ہیں: P (I|O) اور P (I|B)۔ پھر، ہم ان ہسٹوگرامز کا استعمال علاقائی جرمانوں کو منفی لاگ لائکلیہوڈز کے طور پر مقرر کرنے کے لیے کرتے ہیں۔ جی ایم ایم (گاؤسی مرکب ماڈل) ہم عام طور پر دو تقسیمات استعمال کرتے ہیں: ایک پس منظر ماڈلنگ کے لیے اور دوسرا فور گراؤنڈ پکسلز کے لیے۔ ان 2 تقسیموں کا نمونہ بنانے کے لیے گوسی مرکب ماڈل (5-8 اجزاء کے ساتھ) استعمال کریں۔ مقصد: ان دونوں تقسیم کو الگ کرنے کی کوشش کریں۔ ٹیکسان اے (یا) پکسلز کا ایک مجموعہ ہے جس میں کچھ خصوصیات ہوتی ہیں اور اسے تصویر میں دہرایا جاتا ہے۔ اقدامات: ساخت کے عناصر کے لیے ایک اچھے قدرتی پیمانے کا تعین کریں۔ ماڈل کے اندرونی حصے کے غیر پیرامیٹرک اعداد و شمار کا حساب لگائیں، یا تو شدت پر یا گابر فلٹر کے ردعمل پر۔ مثال: ڈیفارمیبل ماڈل پر مبنی ٹیکسٹورڈ آبجیکٹ سیگمنٹشن کنٹور اور امیج سیگمنٹشن کے لیے ٹیکسٹور تجزیہ پری/کوہرینس ماڈل/باؤنڈری ٹرم-بائنری ٹرم جو پڑوس کے پکسلز کے درمیان ہم آہنگی کو بیان کرتی ہے۔ عملی طور پر، پکسلز کو پڑوسیوں کے طور پر بیان کیا جاتا ہے اگر وہ افقی، عمودی یا اخترن طور پر ملحقہ ہوں (2 ڈی امیجز کے لیے 4 وے کنیکٹوٹی یا 8 وے کنیکٹوٹی)۔ لاگت مقامی شدت کے میلان، لیپلاسیئن صفر کراسنگ، میلان کی سمت، رنگین مرکب ماڈل، پر مبنی ہو سکتی ہے۔ مختلف توانائی کے افعال کی وضاحت کی گئی ہے: معیاری مارکوف بے ترتیب فیلڈ: ان کے سیگمنٹشن لیبل (حدود کی لمبائی کی خام پیمائش) کے درمیان فرق کا اندازہ لگا کر متضاد پکسلز پر جرمانہ لگائیں۔ بوئکوف اور کولموگوروف آئی سی سی وی 2003 مشروط بے ترتیب میدان دیکھیں: اگر رنگ بہت مختلف ہے، تو یہ باؤنڈری لگانے کے لیے اچھی جگہ ہو سکتی ہے۔ دیکھیں Lafferty et al. 2001 ؛ کمار اور ہیبرٹ 2003 تنقید گراف کٹ کے طریقے کنٹور کے مقام کو بہتر بنانے کے لیے سطح سیٹ پر مبنی طریقوں کے مقبول متبادل بن گئے ہیں (ایک وسیع موازنہ کے لیے دیکھیں)۔ تاہم، گراف کٹ کے طریقوں کو ادب میں کئی مسائل کے لیے تنقید کا نشانہ بنایا گیا ہے: پیمائش کے نمونے: جب کسی تصویر کی نمائندگی 4 منسلک جالی سے کی جاتی ہے، تو گراف کٹ کے طریقے ناپسندیدہ "بلاکنیس" نمونوں کی نمائش کر سکتے ہیں۔ اس مسئلے کو حل کرنے کے لیے مختلف طریقے تجویز کیے گئے ہیں، جیسے کہ اضافی کناروں کا استعمال کرنا یا مسلسل جگہ میں زیادہ سے زیادہ بہاؤ کا مسئلہ وضع کرنا۔ سکڑتا ہوا تعصب: چونکہ گراف میں کٹوتیوں میں کم سے کم کٹوتی ہوتی ہے، اس لیے الگورتھم ایک چھوٹی سی شکل پیدا کرنے کی طرف متعصبانہ ہو سکتا ہے۔ مثال کے طور پر، الگورتھم خون کی وریدوں جیسی پتلی اشیاء کی تقسیم کے لیے مناسب نہیں ہے (مجوزہ فکس کے لیے دیکھیں)۔ متعدد لیبلز: گراف کٹ صرف بائنری لیبلنگ (یعنی دو لیبلز) کے مسائل، جیسے فور گراؤنڈ/بیک گراؤنڈ امیج سیگمنٹشن کے لیے عالمی سطح پر زیادہ سے زیادہ تلاش کرنے کے قابل ہے۔ ایسی توسیعات تجویز کی گئی ہیں جو ملٹی لیبل گراف کٹ کے مسائل کا تخمینہ حل تلاش کر سکتی ہیں۔ میموری: جیسے جیسے تصویر کا سائز بڑھتا ہے گراف کٹ کا میموری کا استعمال تیزی سے بڑھتا ہے۔ مثال کے طور پر، بوئکوو-کولموگوروف میکس فلو الگورتھم v2.2 بائٹس مختص کرتا ہے (اور گراف میں بالترتیب نوڈس اور کناروں کی تعداد ہے)۔ اس کے باوجود، زیادہ سے زیادہ بہاؤ کے حساب سے پہلے گراف کو کم کرنے کے لیے اس سمت میں حال ہی میں کچھ کام کیا گیا ہے۔ الگورتھم کو کم سے کم کرنا ایک معیاری کم سے کم کٹ الگورتھم کا استعمال کرتے ہوئے کیا جاتا ہے۔ میکس فلو من کٹ تھیوریم کی وجہ سے ہم نیٹ ورک پر بہاؤ کو زیادہ سے زیادہ کرکے کم سے کم توانائی کو حل کر سکتے ہیں۔ زیادہ سے زیادہ بہاؤ کا مسئلہ ایک ہدایت شدہ گراف پر مشتمل ہوتا ہے جس کے کناروں کو صلاحیتوں کے ساتھ لیبل کیا جاتا ہے، اور اس میں دو الگ الگ نوڈس ہوتے ہیں: ماخذ اور سنک۔ بدیہی طور پر، یہ دیکھنا آسان ہے کہ زیادہ سے زیادہ بہاؤ کا تعین رکاوٹ سے ہوتا ہے۔ نفاذ (عین مطابق) بوائکوو-کولموگوروف الگورتھم کمپیوٹر وژن سے متعلق گرافوں کے لیے زیادہ سے زیادہ بہاؤ کا حساب لگانے کا ایک موثر طریقہ ہے۔ نفاذ (تخمینہ) سم کٹ الگورتھم کم از کم گراف کٹ کا تخمینہ لگاتا ہے۔ الگورتھم برقی نیٹ ورک کے تخروپن کے ذریعے حل کو لاگو کرتا ہے۔ یہ وہ نقطہ نظر ہے جو سیڈربام کے زیادہ سے زیادہ بہاؤ کے نظریہ کے ذریعہ تجویز کیا گیا ہے۔ متوازی کمپیوٹنگ کے ذریعے الگورتھم میں تیزی لانا ممکن ہے۔ سافٹ ویئر http://pub.ist.ac.at ~ وی این کے/سافٹ ویئر. ایچ ٹی ایم ایل-ولادیمیر کولموگوروف http://vision.csd.uwo.ca/code کے ذریعہ "کمپیوٹر ویژن میں توانائی کو کم سے کم کرنے کے لیے من کٹ/میکس فلو الگورتھم کا ایک تجرباتی موازنہ" میں بیان کردہ میکس فلو الگورتھم کا نفاذ-کچھ گراف کٹ لائبریریاں اور ایم اے ٹی ایل اے بی ریپرز http://gridcut.com-تیز رفتار ملٹی کور میکس فلو/من کٹ سولور جو گرڈ جیسے گرافز http://virtualscalpel.com کے لیے بہتر بنایا گیا ہے-سم کٹ کا نفاذ ؛ بڑے پیمانے پر متوازی انداز میں کم سے کم ایس ٹی کٹ کے تخمینہ حل کو کمپیوٹ کرنے کے لیے ایک الگورتھم۔ حوالہ جات بایسیائی اعداد و شمار گراف تھیوری میں کمپیوٹر وژن کمپیوٹیشنل مسائل تصویر کی تقسیم