Graph cuts in computer vision
কম্পিউটার দৃষ্টি ক্ষেত্রে যেমন প্রয়োগ করা হয়, গ্রাফ কাট অপ্টিমাইজেশানকে বিভিন্ন ধরনের নিম্ন-স্তরের কম্পিউটার দৃষ্টি সমস্যা (প্রাথমিক দৃষ্টি) দক্ষতার সাথে সমাধান করার জন্য নিযুক্ত করা যেতে পারে, যেমন ইমেজ স্মুথিং, স্টেরিও চিঠিপত্রের সমস্যা, ইমেজ সেগমেন্টেশন, অবজেক্ট কো-সেগমেন্টেশন, এবং অন্যান্য অনেক কম্পিউটার দৃষ্টি সমস্যা যা শক্তি হ্রাসের ক্ষেত্রে প্রণয়ন করা যেতে পারে। এই শক্তি হ্রাসকরণ সমস্যাগুলির মধ্যে অনেকগুলি একটি গ্রাফে সর্বাধিক প্রবাহের সমস্যা সমাধান করে আনুমানিক করা যেতে পারে (এবং এইভাবে, সর্বাধিক-প্রবাহের ন্যূনতম-কাট উপপাদ্য দ্বারা, গ্রাফের একটি ন্যূনতম কাট সংজ্ঞায়িত করা হয়)। কম্পিউটার দৃষ্টিতে এই ধরনের সমস্যাগুলির বেশিরভাগ গঠনের অধীনে, ন্যূনতম শক্তি সমাধান একটি সমাধানের সর্বাধিক পরবর্তী অনুমানের সাথে মিলে যায়। যদিও অনেক কম্পিউটার ভিশন অ্যালগরিদম একটি গ্রাফ কাটা জড়িত (উদাহরণস্বরূপ, স্বাভাবিক কাটা), "গ্রাফ কাট" শব্দটি বিশেষভাবে সেই মডেলগুলির জন্য প্রয়োগ করা হয় যা একটি সর্বোচ্চ-প্রবাহ/ন্যূনতম-কাট অপ্টিমাইজেশন নিয়োগ করে (অন্যান্য গ্রাফ কাটিং অ্যালগরিদমগুলি গ্রাফ পার্টিশনিং অ্যালগরিদম হিসাবে বিবেচিত হতে পারে)। "বাইনারি" সমস্যাগুলি (যেমন একটি বাইনারি ইমেজকে ডিনোইজ করা) ঠিক এই পদ্ধতিটি ব্যবহার করে সমাধান করা যেতে পারে; যে সমস্যাগুলিতে পিক্সেলগুলিকে দুটির বেশি ভিন্ন লেবেল দিয়ে লেবেল করা যেতে পারে (যেমন স্টেরিও চিঠিপত্র, বা একটি গ্রেস্কেল ইমেজকে ডিনোইজ করা) সেগুলি সঠিকভাবে সমাধান করা যায় না, তবে উত্পাদিত সমাধানগুলি সাধারণত বিশ্বব্যাপী সর্বোত্তমের কাছাকাছি থাকে। ইতিহাস একটি অপ্টিমাইজেশন পদ্ধতি হিসাবে ব্যবহৃত গ্রাফ কাটের তত্ত্বটি প্রথম ডারহাম বিশ্ববিদ্যালয়ের গ্রেগ, পোর্টিয়াস এবং সেহল্ট দ্বারা সেমিনাল পেপারে কম্পিউটার ভিশনে প্রয়োগ করা হয়েছিল। অ্যালান সেহল্ট এবং ব্রুস পোর্টিয়াস সেই সময়ের ডারহামের প্রশংসিত পরিসংখ্যান গোষ্ঠীর সদস্য ছিলেন, যার নেতৃত্বে ছিলেন জুলিয়ান বেসাগ এবং পিটার গ্রিন, অপ্টিমাইজেশন বিশেষজ্ঞ মার্গারেট গ্রেগ ডারহাম গাণিতিক বিজ্ঞান বিভাগের প্রথম মহিলা কর্মী হিসাবে উল্লেখযোগ্য। কোলাহলপূর্ণ (বা দূষিত) চিত্রগুলিকে মসৃণ করার বায়েসিয়ান পরিসংখ্যানগত প্রসঙ্গে, তারা দেখিয়েছেন যে কীভাবে একটি বাইনারি চিত্রের পোস্টেরিয়োরি অনুমান একটি সংশ্লিষ্ট চিত্র নেটওয়ার্কের মাধ্যমে প্রবাহকে সর্বাধিক করে সঠিকভাবে প্রাপ্ত করা যেতে পারে, যার মধ্যে একটি উৎস এবং সিঙ্কের প্রবর্তন জড়িত। তাই সমস্যাটি দক্ষতার সাথে সমাধানযোগ্য বলে প্রমাণিত হয়েছিল। এই ফলাফলের আগে, আনুমানিক কৌশল যেমন সিমুলেটেড অ্যানিলিং (জেম্যান ভাইদের দ্বারা প্রস্তাবিত), বা পুনরাবৃত্ত শর্তাধীন মোড (জুলিয়ান বেসাগ দ্বারা প্রস্তাবিত এক ধরনের লোভী অ্যালগরিদম) এই ধরনের চিত্র মসৃণ সমস্যা সমাধানের জন্য ব্যবহার করা হত। যদিও গ্রেগের পদ্ধতির জন্য সাধারণ-রঙের সমস্যাটি অমীমাংসিত রয়ে গেছে, পোর্টিয়াস এবং সেহল্ট সাধারণ কম্পিউটার দৃষ্টি সমস্যায় ব্যাপকভাবে প্রযোজ্য বলে প্রমাণিত হয়েছে। গ্রেগ, পোর্টিয়াস এবং সেহল্টের পন্থা প্রায়শই বাইনারি সমস্যার একটি ক্রমের জন্য পুনরাবৃত্তিমূলকভাবে প্রয়োগ করা হয়, যা সাধারণত প্রায় সর্বোত্তম সমাধান দেয়। 2011 সালে, সি. কুপরি এবং অন্যান্যরা। "পাওয়ার ওয়াটারশেড" নামে একটি সাধারণ চিত্র বিভাজন কাঠামো প্রস্তাব করা হয়েছিল, যা একটি গ্রাফের উপর [0,1] থেকে একটি বাস্তব-মূল্যবান সূচক ফাংশনকে ন্যূনতম করে, ব্যবহারকারী বীজ (বা ইউনারি পদ) দ্বারা সীমাবদ্ধ 0 বা 1 সেট করে, যেখানে সূচকের ন্যূনতমকরণ গ্রাফের উপর ফাংশন একটি সূচকের সাপেক্ষে অনুকূলিত হয়। যখন, পাওয়ার ওয়াটারশেড গ্রাফ কাট দ্বারা অনুকূলিত হয়, যখন পাওয়ার ওয়াটারশেড সংক্ষিপ্ততম পথ দ্বারা অনুকূলিত হয়, র্যান্ডম ওয়াকার অ্যালগরিদম দ্বারা অনুকূলিত হয় এবং ওয়াটারশেড অ্যালগরিদম দ্বারা অনুকূলিত হয়। এইভাবে, পাওয়ার ওয়াটারশেডকে গ্রাফ কাটের সাধারণীকরণ হিসাবে দেখা যেতে পারে যা অন্যান্য শক্তি অপ্টিমাইজেশন বিভাগ/ক্লাস্টারিং অ্যালগরিদমের সাথে একটি সহজ সংযোগ প্রদান করে। চিত্রের বাইনারি বিভাজন স্বরলিপি চিত্রঃ আউটপুটঃ বিভাজন (অস্বচ্ছতাও বলা হয়) (নরম বিভাজন)। শক্ত বিভাজনের জন্য শক্তি ফাংশনঃ যেখানে সি হল রঙের পরামিতি এবং λ হল সঙ্গতি পরামিতি। অপ্টিমাইজেশানঃ বিভাজনকে এস-এর উপর একটি বিশ্বব্যাপী ন্যূনতম হিসাবে অনুমান করা যেতে পারেঃ বিদ্যমান পদ্ধতি স্ট্যান্ডার্ড গ্রাফ কাটঃ বিভাজনের উপর শক্তি ফাংশনকে অনুকূল করুন (অজানা এস মান)। পুনরাবৃত্ত গ্রাফ কাটঃ প্রথম ধাপটি কে-মিন ব্যবহার করে রঙের পরামিতিগুলির উপর অনুকূল করে তোলে। দ্বিতীয় ধাপটি স্বাভাবিক গ্রাফ কাট অ্যালগরিদম সম্পাদন করে। এই দুটি ধাপ অভিসরণ না হওয়া পর্যন্ত পুনরাবৃত্তিমূলকভাবে পুনরাবৃত্তি করা হয়। গতিশীল গ্রাফ কাটঃ সমস্যাটি সংশোধন করার পরে অ্যালগরিদমটিকে আরও দ্রুত পুনরায় চালানোর অনুমতি দেয় (যেমন। একজন ব্যবহারকারীর দ্বারা নতুন বীজ যোগ করার পরে)। শক্তি ফাংশন যেখানে শক্তি দুটি ভিন্ন মডেল (এবং) দ্বারা গঠিত হয়ঃ সম্ভাব্যতা/রঙ মডেল/আঞ্চলিক শব্দ-প্রতিটি রঙের সম্ভাবনা বর্ণনা করে একক শব্দ। এই শব্দটি বিভিন্ন স্থানীয় (যেমন) ব্যবহার করে মডেল করা যেতে পারে। বা গ্লোবাল (যেমন। হিস্টোগ্রাম, জি. এম. এম, অ্যাডাবুস্ট সম্ভাবনা) পদ্ধতি যা নীচে বর্ণনা করা হয়েছে। হিস্টোগ্রাম আমরা বস্তু (অগ্রভূমি) এবং পটভূমির তীব্রতা বিতরণের জন্য হিস্টোগ্রাম পেতে বীজ হিসাবে চিহ্নিত পিক্সেলের তীব্রতা ব্যবহার করিঃ পি (I|O) এবং পি (I|B)। তারপর, আমরা এই হিস্টোগ্রামগুলি ব্যবহার করে আঞ্চলিক পেনাল্টিগুলিকে নেতিবাচক লগ-লাইক্লিহুড হিসাবে নির্ধারণ করি। জিএমএম (গাউসিয়ান মিক্সচার মডেল) আমরা সাধারণত দুটি ডিস্ট্রিবিউশন ব্যবহার করিঃ একটি ব্যাকগ্রাউন্ড মডেলিংয়ের জন্য এবং অন্যটি ফোরগ্রাউন্ড পিক্সেলের জন্য। এই দুটি ডিস্ট্রিবিউশনের মডেল তৈরি করতে একটি গাউসিয়ান মিশ্রণ মডেল (5-8টি উপাদান সহ) ব্যবহার করুন। লক্ষ্যঃ এই দুটি বিভাজনকে আলাদা করার চেষ্টা করুন। টেক্সোন এ (বা) পিক্সেলের একটি সেট যার নির্দিষ্ট বৈশিষ্ট্য রয়েছে এবং একটি ছবিতে পুনরাবৃত্তি করা হয়। পদক্ষেপঃ টেক্সচার উপাদানগুলির জন্য একটি ভাল প্রাকৃতিক স্কেল নির্ধারণ করুন। মডেল-অভ্যন্তরের অ-প্যারামেট্রিক পরিসংখ্যান গণনা করুন, হয় তীব্রতার উপর বা গ্যাবর ফিল্টার প্রতিক্রিয়াগুলির উপর। উদাহরণস্বরূপঃ বিকৃত-মডেল ভিত্তিক টেক্সচার অবজেক্ট সেগমেন্টেশন কনট্যুর এবং ইমেজ সেগমেন্টেশনের জন্য টেক্সচার বিশ্লেষণ পূর্ববর্তী/সঙ্গতিপূর্ণ মডেল/সীমানা শব্দ-প্রতিবেশী পিক্সেলের মধ্যে সঙ্গতি বর্ণনা করে বাইনারি শব্দ। বাস্তবে, পিক্সেলগুলিকে প্রতিবেশী হিসাবে সংজ্ঞায়িত করা হয় যদি তারা অনুভূমিকভাবে, উল্লম্বভাবে বা তির্যকভাবে সংলগ্ন থাকে (4-মুখী সংযোগ বা 2ডি চিত্রের জন্য 8-মুখী সংযোগ)। খরচ স্থানীয় তীব্রতা গ্রেডিয়েন্ট, ল্যাপলেসিয়ান শূন্য-ক্রসিং, গ্রেডিয়েন্ট দিক, রঙ মিশ্রণ মডেলের উপর ভিত্তি করে হতে পারে। বিভিন্ন শক্তি ফাংশন সংজ্ঞায়িত করা হয়েছেঃ স্ট্যান্ডার্ড মার্কভ র্যান্ডম ক্ষেত্রঃ তাদের বিভাজন লেবেলের (সীমানার দৈর্ঘ্যের অপরিশোধিত পরিমাপ) মধ্যে পার্থক্য মূল্যায়ন করে পিক্সেলগুলির সাথে একটি পেনাল্টি যুক্ত করুন। বয়কভ এবং কোলমোগোরভ আইসিসিভি 2003 শর্তসাপেক্ষ র্যান্ডম ফিল্ড দেখুনঃ যদি রঙটি খুব আলাদা হয়, তবে এটি একটি সীমানা রাখার জন্য একটি ভাল জায়গা হতে পারে। ল্যাফার্টি এবং অন্যান্যদের দেখুন। 2001; কুমার এবং হেবার্ট 2003 সমালোচনা গ্রাফ কাট পদ্ধতিগুলি একটি কনট্যুরের অবস্থানকে অনুকূল করার জন্য স্তর সেট-ভিত্তিক পদ্ধতির জনপ্রিয় বিকল্প হয়ে উঠেছে (একটি বিস্তৃত তুলনার জন্য দেখুন)। যাইহোক, গ্রাফ কাট পদ্ধতির বিভিন্ন বিষয়ের জন্য সাহিত্যে সমালোচনা করা হয়েছেঃ পরিমাপ শিল্পকর্মঃ যখন একটি চিত্র 4-সংযুক্ত জাল দ্বারা প্রতিনিধিত্ব করা হয়, গ্রাফ কাট পদ্ধতিগুলি অবাঞ্ছিত "বাধা" শিল্পকর্ম প্রদর্শন করতে পারে। এই সমস্যা সমাধানের জন্য বিভিন্ন পদ্ধতি প্রস্তাব করা হয়েছে, যেমন অতিরিক্ত প্রান্ত ব্যবহার করা বা অবিচ্ছিন্ন স্থানে সর্বোচ্চ-প্রবাহের সমস্যা তৈরি করা। সঙ্কুচিত পক্ষপাতঃ যেহেতু গ্রাফ কাটগুলি ন্যূনতম কাট খুঁজে পায়, তাই অ্যালগরিদমটি একটি ছোট কনট্যুর তৈরির দিকে পক্ষপাতদুষ্ট হতে পারে। উদাহরণস্বরূপ, অ্যালগরিদমটি রক্তনালীর মতো পাতলা বস্তুর বিভাজনের জন্য উপযুক্ত নয় (একটি প্রস্তাবিত সংশোধন দেখুন)। একাধিক লেবেলঃ গ্রাফ কাট শুধুমাত্র বাইনারি লেবেলিং (অর্থাৎ, দুটি লেবেল) সমস্যার জন্য বিশ্বব্যাপী সর্বোত্তম খুঁজে পেতে সক্ষম, যেমন অগ্রভূমি/পটভূমি চিত্র বিভাজন। এমন এক্সটেনশন প্রস্তাব করা হয়েছে যা মাল্টিলেবেল গ্রাফ কাট সমস্যার আনুমানিক সমাধান খুঁজে পেতে পারে। মেমরিঃ ছবির আকার বাড়ার সাথে সাথে গ্রাফ কাটের মেমরি ব্যবহার দ্রুত বৃদ্ধি পায়। উদাহরণস্বরূপ, বয়কভ-কোলমোগোরভ ম্যাক্স-ফ্লো অ্যালগরিদম v2.2 বাইট্স বরাদ্দ করে (এবং যথাক্রমে গ্রাফের নোড এবং প্রান্তের সংখ্যা)। তা সত্ত্বেও, সর্বাধিক-প্রবাহ গণনার আগে গ্রাফগুলি হ্রাস করার জন্য সম্প্রতি এই দিকে কিছু পরিমাণ কাজ করা হয়েছে। অ্যালগরিদম মিনিমাইজেশন একটি স্ট্যান্ডার্ড মিনিমাম কাট অ্যালগরিদম ব্যবহার করে করা হয়। ম্যাক্স-ফ্লো মিন-কাট উপপাদ্যের কারণে আমরা নেটওয়ার্কের উপর প্রবাহকে সর্বাধিক করে শক্তি হ্রাসের সমাধান করতে পারি। সর্বাধিক-প্রবাহের সমস্যাটি একটি নির্দেশিত গ্রাফ নিয়ে গঠিত যার প্রান্তগুলি সক্ষমতার সাথে লেবেলযুক্ত এবং দুটি স্বতন্ত্র নোড রয়েছেঃ উৎস এবং সিঙ্ক। স্বজ্ঞাতভাবে, এটি সহজেই দেখা যায় যে সর্বাধিক প্রবাহ বাধা দ্বারা নির্ধারিত হয়। বাস্তবায়ন (সঠিক) বয়কভ-কোলমোগোরভ অ্যালগরিদম কম্পিউটার দৃষ্টি-সম্পর্কিত গ্রাফের জন্য সর্বাধিক প্রবাহ গণনা করার একটি কার্যকর উপায়। বাস্তবায়ন (আনুমানিক) সিম কাট অ্যালগরিদম ন্যূনতম গ্রাফ কাটকে আনুমানিক করে। অ্যালগরিদম একটি বৈদ্যুতিক নেটওয়ার্কের অনুকরণের মাধ্যমে একটি সমাধান প্রয়োগ করে। এই পদ্ধতিটি সিডারবাউমের সর্বাধিক প্রবাহ উপপাদ্য দ্বারা প্রস্তাবিত। সমান্তরাল গণনার মাধ্যমে অ্যালগরিদমের ত্বরণ সম্ভব। সফ্টওয়্যার http://pub.ist.ac.at ~ ভিএনকে/সফ্টওয়্যার. এইচটিএমএল-ভ্লাদিমির কোলমোগোরভের "অ্যান এক্সপেরিমেন্টাল কম্প্যারিশন অফ মিন-কাট/ম্যাক্স-ফ্লো অ্যালগরিদমস ফর এনার্জি মিনিমাইজেশন ইন কম্পিউটার ভিশন"-এ বর্ণিত ম্যাক্সফ্লো অ্যালগরিদমের একটি বাস্তবায়ন-কিছু গ্রাফ কাট লাইব্রেরি এবং ম্যাটল্যাব র্যাপার http://gridcut.com-দ্রুত মাল্টি-কোর ম্যাক্স-ফ্লো/মিন-কাট সমাধানকারী যা গ্রিডের মতো গ্রাফের জন্য অপ্টিমাইজ করা হয়েছে http://virtualscalpel.com-সিম কাটের একটি বাস্তবায়ন; ব্যাপকভাবে সমান্তরাল পদ্ধতিতে ন্যূনতম এস-টি কাটের আনুমানিক সমাধান গণনা করার জন্য একটি অ্যালগরিদম। তথ্যসূত্র বায়েসিয়ান পরিসংখ্যান গ্রাফ তত্ত্বে কম্পিউটার দৃষ্টি গণনামূলক সমস্যা চিত্র বিভাজন