Graph cuts in computer vision
கணினி பார்வைத் துறையில் பயன்படுத்தப்படுவது போல, பட மென்மையாக்கம், ஸ்டீரியோ கடிதப் பிரச்சினை, படப் பிரிவு, பொருள் இணைப் பிரிவு மற்றும் ஆற்றல் குறைப்பு அடிப்படையில் வடிவமைக்கக்கூடிய பல கணினி பார்வை சிக்கல்கள் போன்ற பல்வேறு வகையான குறைந்த அளவிலான கணினி பார்வை சிக்கல்களை (ஆரம்பகால பார்வை) திறம்பட தீர்க்க வரைபட வெட்டு உகப்பாக்கம் பயன்படுத்தப்படலாம். இந்த ஆற்றல் குறைப்பு சிக்கல்களில் பலவற்றை ஒரு வரைபடத்தில் அதிகபட்ச ஓட்ட சிக்கலைத் தீர்ப்பதன் மூலம் தோராயமாக மதிப்பிட முடியும் (இதனால், அதிகபட்ச-ஓட்ட குறைந்தபட்ச-வெட்டு தேற்றத்தால், வரைபடத்தின் குறைந்தபட்ச வெட்டு வரையறுக்கப்படுகிறது). கணினி பார்வையில் இத்தகைய சிக்கல்களின் பெரும்பாலான சூத்திரங்களின் கீழ், குறைந்தபட்ச ஆற்றல் தீர்வு ஒரு தீர்வின் அதிகபட்ச பிந்தைய மதிப்பீட்டிற்கு ஒத்திருக்கிறது. பல கணினி பார்வை வழிமுறைகள் ஒரு வரைபடத்தை வெட்டுவதை உள்ளடக்கியிருந்தாலும் (எ. கா., இயல்பாக்கப்பட்ட வெட்டுக்கள்), "வரைபட வெட்டுக்கள்" என்ற சொல் குறிப்பாக அதிகபட்ச-ஓட்டம்/குறைந்தபட்ச-வெட்டு உகப்பாக்கத்தை பயன்படுத்தும் மாதிரிகளுக்கு பயன்படுத்தப்படுகிறது (பிற வரைபட வெட்டு வழிமுறைகள் வரைபட பகிர்வு வழிமுறைகளாக கருதப்படலாம்). "பைனரி" சிக்கல்களை (பைனரி படத்தைக் குறிவைப்பது போன்றவை) இந்த அணுகுமுறையைப் பயன்படுத்தி சரியாக தீர்க்க முடியும்; பிக்சல்களை இரண்டுக்கும் மேற்பட்ட வெவ்வேறு லேபிள்களால் பெயரிடக்கூடிய சிக்கல்களை (ஸ்டீரியோ கடிதங்கள் அல்லது கிரேஸ்கேல் படத்தை குறிவைப்பது போன்றவை) சரியாக தீர்க்க முடியாது, ஆனால் தயாரிக்கப்படும் தீர்வுகள் பொதுவாக உலகளாவிய உகந்த நிலைக்கு அருகில் இருக்கும். ஒரு உகப்பாக்கம் முறையாக பயன்படுத்தப்படும் வரைபட வெட்டுக்களின் கோட்பாடு முதன்முதலில் கணினி பார்வையில் டர்ஹாம் பல்கலைக்கழகத்தின் கிரேக், போர்டியஸ் மற்றும் செஹல்ட் ஆகியோரால் பயன்படுத்தப்பட்டது. ஜூலியன் பெசாக் மற்றும் பீட்டர் கிரீன் தலைமையிலான அக்காலத்தின் டர்ஹாமின் பாராட்டப்பட்ட புள்ளிவிவரக் குழுவில் ஆலன் செஹல்ட் மற்றும் புரூஸ் போர்டியஸ் ஆகியோர் உறுப்பினர்களாக இருந்தனர், உகப்பாக்கம் நிபுணர் மார்கரெட் கிரேக் டர்ஹாம் கணித அறிவியல் துறையின் முதல் பெண் ஊழியராக குறிப்பிடத்தக்கவர். சத்தமான (அல்லது சிதைந்த) படங்களை மென்மையாக்கும் பேய்சியன் புள்ளிவிவர சூழலில், ஒரு பைனரி படத்தின் அதிகபட்ச பின்புற மதிப்பீட்டை ஒரு தொடர்புடைய பட நெட்வொர்க் வழியாக ஓட்டத்தை அதிகரிப்பதன் மூலம் எவ்வாறு பெற முடியும் என்பதை அவர்கள் காட்டினர், இதில் ஒரு மூலத்தின் அறிமுகம் மற்றும் மூழ்கி அடங்கும். எனவே இந்தப் பிரச்சினை திறம்பட தீர்க்கக்கூடியது என்று நிரூபிக்கப்பட்டது. இந்த முடிவுக்கு முன்னர், உருவகப்படுத்தப்பட்ட அனீலிங் போன்ற தோராயமான நுட்பங்கள் (ஜெமான் சகோதரர்களால் முன்மொழியப்பட்டது), அல்லது மறு செய்கை நிபந்தனை முறைகள் (ஜூலியன் பெசாக் பரிந்துரைத்த ஒரு வகை பேராசை வழிமுறை) போன்ற பட மென்மையாக்கும் சிக்கல்களைத் தீர்க்க பயன்படுத்தப்பட்டன. கிரேக்கின் அணுகுமுறைக்கு பொதுவான-வண்ணப் பிரச்சினை தீர்க்கப்படாமல் இருந்தபோதிலும், போர்டியஸ் மற்றும் செஹல்ட் பொதுவான கணினி பார்வை சிக்கல்களில் பரந்த பயன்பாட்டைக் கொண்டுள்ளன. கிரேக், போர்டியஸ் மற்றும் செஹெல்ட்டின் அணுகுமுறைகள் பெரும்பாலும் பைனரி சிக்கல்களின் வரிசைக்கு மீண்டும் மீண்டும் பயன்படுத்தப்படுகின்றன, பொதுவாக உகந்த தீர்வுகளை வழங்குகின்றன. 2011 ஆம் ஆண்டில், சி. கூப்ரி மற்றும் பலர். "பவர் வாட்டர்ஷெட்" என்று அழைக்கப்படும் ஒரு பொதுவான படப் பிரிவு கட்டமைப்பை முன்மொழிந்தது, இது ஒரு வரைபடத்தின் மீது [0,1] இருந்து ஒரு உண்மையான மதிப்புள்ள காட்டி செயல்பாட்டைக் குறைத்தது, பயனர் விதைகள் (அல்லது யூனரி சொற்கள்) 0 அல்லது 1 ஆக அமைக்கப்பட்டது, இதில் குறைந்தபட்சம் வரைபடத்தின் மீது காட்டி செயல்பாடு ஒரு அடுக்கைப் பொறுத்து உகந்ததாக இருக்கும். பவர் வாட்டர்ஷெட் வரைபட வெட்டுக்கள் மூலம் உகந்ததாக இருக்கும்போது, பவர் வாட்டர்ஷெட் குறுகிய பாதைகளால் உகந்ததாக இருக்கும்போது, சீரற்ற வாக்கர் வழிமுறையால் உகந்ததாக இருக்கும் மற்றும் வாட்டர்ஷெட் வழிமுறையால் உகந்ததாக இருக்கும். இந்த வழியில், பவர் வாட்டர்ஷெட் வரைபட வெட்டுக்களின் பொதுமைப்படுத்தலாகக் கருதப்படலாம், இது மற்ற ஆற்றல் உகப்பாக்கம் பிரிவு/கிளஸ்டரிங் வழிமுறைகளுடன் நேரடியான தொடர்பை வழங்குகிறது. படங்களின் பைனரி பிரிவு குறிப்பு படம்ஃ வெளியீடுஃ பிரிவு (ஒளிபுகா தன்மை என்றும் அழைக்கப்படுகிறது) (மென்மையான பிரிவு). கடினமான பிரிவினைக்கு ஆற்றல் செயல்பாடுஃ இங்கு சி என்பது வண்ண அளவுரு மற்றும் λ என்பது ஒத்திசைவு அளவுரு ஆகும். உகப்பாக்கம்ஃ பிரிவினையை எஸ் மீது உலகளாவிய குறைந்தபட்சமாக மதிப்பிடலாம்ஃ தற்போதுள்ள முறைகள் நிலையான வரைபட வெட்டுக்கள்ஃ பிரிவினையின் மீது ஆற்றல் செயல்பாட்டை மேம்படுத்துதல் (அறியப்படாத எஸ் மதிப்பு). தொடர்ச்சியான வரைபட வெட்டுக்கள்ஃ முதல் படி கே-வழிமுறைகளைப் பயன்படுத்தி வண்ண அளவுருக்களை உகந்ததாக்குகிறது. இரண்டாவது படி வழக்கமான வரைபட வெட்டுக்கள் வழிமுறையை செய்கிறது. இந்த 2 படிகளும் ஒருங்கிணைக்கும் வரை மீண்டும் மீண்டும் செய்யப்படுகின்றன. மாறும் வரைபட வெட்டுக்கள்ஃ சிக்கலை மாற்றியமைத்த பிறகு வழிமுறையை மிக வேகமாக மீண்டும் இயக்க அனுமதிக்கிறது (எ. கா. ஒரு பயனரால் புதிய விதைகள் சேர்க்கப்பட்ட பிறகு). ஆற்றல் செயல்பாடு இரண்டு வெவ்வேறு மாதிரிகளால் ஆனது (மற்றும்): சாத்தியக்கூறு/வண்ண மாதிரி/பிராந்திய சொல்-ஒவ்வொரு நிறத்தின் சாத்தியக்கூறையும் விவரிக்கும் ஒற்றை சொல். இந்த சொல் வெவ்வேறு உள்ளூர் (எ. கா.) பயன்படுத்தி மாதிரியாக இருக்கலாம். அல்லது உலகளாவிய (எ. கா. ஹிஸ்டோகிராம்கள், ஜிஎம்எம்கள், அடபூஸ்ட் சாத்தியக்கூறுகள்) அணுகுமுறைகள் கீழே விவரிக்கப்பட்டுள்ளன. ஹிஸ்டோகிராம் பொருள் (முன்புறம்) மற்றும் பின்னணி தீவிரம் விநியோகங்களுக்கான ஹிஸ்டோகிராம்களைப் பெற விதைகளாக குறிக்கப்பட்ட பிக்சல்களின் தீவிரங்களைப் பயன்படுத்துகிறோம்ஃ பி (I|O) மற்றும் பி (I|B). பின்னர், பிராந்திய அபராதங்களை எதிர்மறை பதிவு-வாய்ப்புகளாக அமைக்க இந்த ஹிஸ்டோகிராம்களைப் பயன்படுத்துகிறோம். GMM (காஸியன் கலவை மாதிரி) நாம் வழக்கமாக இரண்டு விநியோகங்களைப் பயன்படுத்துகிறோம்ஃ ஒன்று பின்னணி மாடலிங்கிற்கும் மற்றொன்று முன்புற பிக்சல்களுக்கும். அந்த 2 விநியோகங்களை மாதிரியாக்க ஒரு காஸியன் கலவை மாதிரியைப் பயன்படுத்தவும் (5-8 கூறுகளுடன்). குறிக்கோள்ஃ அந்த இரண்டு விநியோகங்களையும் பிரிக்க முயற்சிக்கவும். டெக்சான் ஏ (அல்லது) என்பது சில பண்புகளைக் கொண்ட பிக்சல்களின் தொகுப்பாகும், மேலும் இது ஒரு படத்தில் மீண்டும் மீண்டும் செய்யப்படுகிறது. படிகள்ஃ அமைப்பு கூறுகளுக்கு ஒரு நல்ல இயற்கை அளவை தீர்மானிக்கவும். மாதிரி-உட்புறத்தின் அளவுரு அல்லாத புள்ளிவிவரங்களை, தீவிரத்திலோ அல்லது கபோர் வடிகட்டி பதில்களிலோ கணக்கிடுங்கள். எடுத்துக்காட்டுகள்ஃ சிதைக்கக்கூடிய-மாதிரி அடிப்படையிலான கட்டமைக்கப்பட்ட பொருள் பிரிவு கான்டூர் மற்றும் படப் பிரிவிற்கான அமைப்பு பகுப்பாய்வு முன்/ஒத்திசைவு மாதிரி/எல்லை சொல்-அருகிலுள்ள பிக்சல்களுக்கு இடையிலான ஒத்திசைவை விவரிக்கும் பைனரி சொல். நடைமுறையில், பிக்சல்கள் கிடைமட்டமாகவோ, செங்குத்தாகவோ அல்லது மூலைவிட்டமாகவோ (4 வழி இணைப்பு அல்லது 2டி படங்களுக்கு 8 வழி இணைப்பு) அருகில் இருந்தால் அவை அண்டை நாடுகளாக வரையறுக்கப்படுகின்றன. உள்ளூர் தீவிரம் சாய்வு, லாப்லாசியன் பூஜ்ஜிய-குறுக்கீடு, சாய்வு திசை, வண்ண கலவை மாதிரி ஆகியவற்றை அடிப்படையாகக் கொண்டு செலவுகள் இருக்கலாம். வெவ்வேறு ஆற்றல் செயல்பாடுகள் வரையறுக்கப்பட்டுள்ளனஃ நிலையான மார்கோவ் சீரற்ற புலம்ஃ அவற்றின் பிரிவு லேபிளுக்கு (எல்லைகளின் நீளத்தின் கச்சா அளவீடு) இடையிலான வேறுபாட்டை மதிப்பிடுவதன் மூலம் பிக்சல்களை ஏற்காததற்கு அபராதத்தை இணைக்கவும். பாய்கோவ் மற்றும் கோல்மோகோரோவ் ஐசிசிவி 2003 நிபந்தனை சீரற்ற புலத்தைப் பார்க்கவும்ஃ நிறம் மிகவும் வித்தியாசமாக இருந்தால், ஒரு பவுண்டரி வைக்க இது ஒரு நல்ல இடமாக இருக்கலாம். லாஃபெர்டி மற்றும் பலரைப் பார்க்கவும். 2001; குமார் மற்றும் ஹெபர்ட் 2003 விமர்சனம் வரைபட வெட்டு முறைகள் ஒரு விளிம்பின் இருப்பிடத்தை மேம்படுத்துவதற்கான நிலை தொகுப்பு அடிப்படையிலான அணுகுமுறைகளுக்கு பிரபலமான மாற்றாக மாறிவிட்டன (விரிவான ஒப்பீட்டிற்கு பார்க்கவும்). இருப்பினும், வரைபட வெட்டு அணுகுமுறைகள் பல சிக்கல்களுக்காக இலக்கியத்தில் விமர்சிக்கப்பட்டுள்ளனஃ அளவீட்டு கலைப்பொருட்கள்ஃ ஒரு படம் 4-இணைக்கப்பட்ட ஜாலத்தால் குறிப்பிடப்படும்போது, வரைபட வெட்டு முறைகள் தேவையற்ற "அடைப்பு" கலைப்பொருட்களை வெளிப்படுத்தலாம். கூடுதல் விளிம்புகளைப் பயன்படுத்துவது அல்லது தொடர்ச்சியான இடத்தில் அதிகபட்ச-ஓட்ட சிக்கலை உருவாக்குவது போன்ற பல்வேறு முறைகள் இந்த சிக்கலை தீர்க்க முன்மொழியப்பட்டுள்ளன. சார்பு சுருங்குகிறதுஃ வரைபட வெட்டுக்கள் குறைந்தபட்ச வெட்டுக்களைக் கண்டறிவதால், வழிமுறை ஒரு சிறிய விளிம்பை உருவாக்குவதில் சார்பு காட்டலாம். எடுத்துக்காட்டாக, இரத்த நாளங்கள் போன்ற மெல்லிய பொருட்களின் பிரிவினைக்கு வழிமுறை நன்கு பொருந்தாது (முன்மொழியப்பட்ட திருத்தத்தைப் பார்க்கவும்). பல லேபிள்கள்ஃ முன்/பின்னணி படப் பிரிவு போன்ற பைனரி லேபிளிங் (அதாவது, இரண்டு லேபிள்கள்) சிக்கல்களுக்கு மட்டுமே கிராஃப் வெட்டுக்கள் உலகளாவிய உகந்ததைக் கண்டறிய முடியும். மல்டி லேபிள் கிராஃப் வெட்டு சிக்கல்களுக்கு தோராயமான தீர்வுகளைக் கண்டறியக்கூடிய நீட்டிப்புகள் முன்மொழியப்பட்டுள்ளன. நினைவகம்ஃ படத்தின் அளவு அதிகரிக்கும் போது வரைபட வெட்டுக்களின் நினைவக பயன்பாடு விரைவாக அதிகரிக்கிறது. ஒரு எடுத்துக்காட்டாக, பாய்கோவ்-கொல்மோகோரோவ் அதிகபட்ச-ஓட்ட வழிமுறை v2.2 பைட்டுகளை ஒதுக்குகிறது (மேலும் அவை முறையே வரைபடத்தில் உள்ள முனைகள் மற்றும் விளிம்புகளின் எண்ணிக்கை). ஆயினும்கூட, அதிகபட்ச ஓட்டக் கணக்கீட்டிற்கு முன் வரைபடங்களைக் குறைப்பதற்கான இந்த திசையில் சமீபத்தில் சில பணிகள் செய்யப்பட்டுள்ளன. அல்காரிதம் மினிமைசேஷன் ஒரு நிலையான குறைந்தபட்ச வெட்டு அல்காரிதம் பயன்படுத்தி செய்யப்படுகிறது. அதிகபட்ச-ஓட்ட குறைந்தபட்ச-வெட்டு தேற்றம் காரணமாக, நெட்வொர்க்கில் ஓட்டத்தை அதிகரிப்பதன் மூலம் ஆற்றலைக் குறைப்பதை நாம் தீர்க்க முடியும். அதிகபட்ச-ஓட்ட சிக்கல் திறன்களுடன் பெயரிடப்பட்ட விளிம்புகளுடன் ஒரு இயக்கிய வரைபடத்தைக் கொண்டுள்ளது, மேலும் இரண்டு தனித்துவமான முனைகள் உள்ளனஃ மூல மற்றும் மூழ்கி. உள்ளுணர்வாக, அதிகபட்ச ஓட்டம் தடையால் தீர்மானிக்கப்படுகிறது என்பதைப் பார்ப்பது எளிது. செயல்படுத்தல் (துல்லியமான) பாய்கோவ்-கொல்மோகோரோவ் வழிமுறை என்பது கணினி பார்வை தொடர்பான வரைபடங்களுக்கான அதிகபட்ச ஓட்டத்தை கணக்கிடுவதற்கான ஒரு திறமையான வழியாகும். செயலாக்கம் (தோராயமாக) சிம் கட் வழிமுறை குறைந்தபட்ச வரைபடக் குறைப்பை தோராயமாக மதிப்பிடுகிறது. இந்த வழிமுறை ஒரு மின் வலையமைப்பை உருவகப்படுத்துவதன் மூலம் ஒரு தீர்வை செயல்படுத்துகிறது. இது செடெர்பாமின் அதிகபட்ச ஓட்டக் கோட்பாட்டால் பரிந்துரைக்கப்பட்ட அணுகுமுறையாகும். இணையான கணக்கீடு மூலம் வழிமுறையின் முடுக்கம் சாத்தியமாகும். மென்பொருள் http://pub.ist.ac.at ~ விஎன்கே/மென்பொருள். எச். டி. எம். எல்-விளாடிமிர் கோல்மோகோரோவ் எழுதிய "கணினி பார்வையில் ஆற்றல் குறைப்புக்கான குறைந்தபட்ச-வெட்டு/அதிகபட்ச-பாய்வு வழிமுறைகளின் ஒரு சோதனை ஒப்பீடு" இல் விவரிக்கப்பட்டுள்ள அதிகபட்ச ஓட்ட வழிமுறையின் அமலாக்கம்-சில வரைபட வெட்டு நூலகங்கள் மற்றும் மேட் லேப் ரேப்பர்கள் http://gridcut.com-கட்டம் போன்ற வரைபடங்களுக்கு உகந்த வேகமான மல்டி-கோர் அதிகபட்ச-ஓட்டம்/குறைந்தபட்ச-வெட்டு தீர்வு http://virtualscalpel.com-சிம் வெட்டு செயல்படுத்தல்; குறைந்தபட்ச எஸ்-டி வெட்டுக்கான தோராயமான தீர்வை பெருமளவில் இணையான முறையில் கணக்கிடுவதற்கான ஒரு வழிமுறை. குறிப்புகள் பேய்சியன் புள்ளியியல் கணினி பார்வை வரைபடக் கோட்பாட்டில் கணக்கீட்டு சிக்கல்கள் படப் பிரிவு