Тікелей эфирді сегментациялау әдісі - Livewire Segmentation Technique

Сәбидің фотосуретіндегі тірі сымдарды сегментациялау мысалы

Livewire, бұл сегменттеу әдісі, бұл пайдаланушыға тінтуірдің қарапайым шертуін қолдана отырып, қызығушылық тудыратын аймақтарды тез және дәл алуға мүмкіндік береді.[1] Ол негізделеді ең төменгі шығындар алгоритмі, арқылы Эдсгер В. Дейкстра. Алдымен кескінді а Sobel сүзгісі шеттерін шығару үшін. Алынған кескіннің әрбір пикселі графиктің шыңы болып табылады және оның айналасында жоғары, төмен, солға, оңға қарай 4 пикселге бар шеттері бар. Шекті шығындар шығын функциясы негізінде анықталады. 1995 жылы Эрик Н.Мортенсен және Уильям А.Барретт интеллектуалды қайшылар деп аталатын livewire сегменттеу құралы бойынша кеңейту жұмыстарын жүргізді.[2]

Livewire сегментациясы

Пайдаланушы зәкір ретінде белгілі кескіннің пикселін басу арқылы бастапқы нүктені қояды. Содан кейін, ол тінтуірді басқа нүктелер бойынша жылжытуды бастағанда, зәкірден тінтуір аяқталған пиксельге дейінгі ең аз шығындар жолы қолданылады, егер пайдаланушы тінтуірді жылжытса, өзін өзгертеді. Егер ол көрсетілетін жолды таңдағысы келсе, ол суретті қайтадан басады.

Оң жақ кескінде пайдаланушының қалаған қызығушылық аймағын белгілеу үшін басқан жерлері кішкене квадратпен белгіленгенін оңай көруге болады. Тікелей эфирдің кескіннің шекарасына түсіп кеткенін де байқау қиын емес.

Livewire алгоритмі

Шеттерін шығару үшін кескінді Sobel сүзгісімен біріктіріңіз. Осы сүзгіден өткен кескіннің көмегімен пиксельдерді төрт бағытта (жоғары, төмен, сол жақта) шеттері бар түйіндер ретінде қолданып график құрыңыз.[1] Шеттер Sobel сүзгісінен алынған ерекшеліктермен өлшенеді, олар шет жағында тұруға арзан емес. Бірнеше түрлі шығын әдісі мүмкін, бірақ ең маңыздысы - градиент шамасы[1]

Псевдокодтағы Live-Wire 2-D DP графикалық іздеу алгоритмі [2]

алгоритм Livewire болып табылады    енгізу:        с                       {Пикселді бастау (немесе себу). L (q, r) Q және r пиксельдері арасындағы сілтеме үшін жергілікті шығындар функциясы.} деректер құрылымы:        L {Белсенді пикселдердің жалпы құны бойынша сұрыпталған тізімі (бастапқыда бос).} N (q) {Q көршілес жиыны (пиксельдің 8 көршісінен тұрады).} E (q) Q функциясы кеңейтілген / өңделгенін көрсететін логикалық функция.} G (q) {Тұқымдық нүктеден q-ға дейінгі жалпы шығындар функциясы.} шығу:        б                       {Минималды шығын жолын көрсететін әр пикселден көрсеткіштер.} G (s) ← 0; L ← s; {Белсенді тізімді инициалдаңыз, құны нөлдік тұқым пикселімен.} уақыт L ≠ ∅ бастаңыз      {Әлі де кеңейту керек.} q ← мин (L); {Минималды шығын пикселін q белсенді тізімнен алып тастаңыз.} E (q← ШЫН; {Q-ны кеңейтілген деп белгілеңіз (яғни өңделген).} әрқайсысы үшін r∈N (q) осындай Ескерту(р) бастаңыз            gtmp ← g (q) + л (q, r); {Көршісіне жалпы құнын есептеу.} егер р∈L және gtmp р) содан кейін  {Тізімнен қымбат тұратын көршілерді алып тастаңыз.}                r ← L; егер r∉L содан кейін бастаңыз            {Егер көршіңіз тізімде болмаса,} g (р← gtmp; {көршінің жалпы құнын тағайындаңыз,} p (р) ← q; {артқы көрсеткішті орнатыңыз (немесе қалпына келтіріңіз), L L р; {және белсенді тізімге қойыңыз (немесе оларға оралыңыз). Соңы                                        Соңы    Соңы

3D-ге дейін кеңейту

2010 жылы Лео Греди Livewire алгоритмін 3D-ге дейін кеңейтті.[3] Бұл кеңейтім 2D Livewire алгоритмін пайдаланушыға 0-өлшемді шекараны (екі нүкте) анықтауға және сол нүктелерді байланыстыратын минималды 1-өлшемді координатты (қисықты) табуға мүмкіндік береді, мұнда минимум кескін қасиеттері бойынша анықталады. Алгоритмді 3D-ге дейін кеңейту үшін оның орнына пайдаланушыдан бір немесе бірнеше 1-өлшемді шекараларды (тұйық қисықтар) көрсетуді сұрайды, ал алгоритм 1-өлшемді қисықтармен шектелген ең аз 2-өлшемді шекараны (бетті) табады, мұнда минималды бет кескін қасиеттері бойынша анықталады. Livewire-дің бұл 3D кеңеюі концепцияларға қатты сүйенеді сыртқы дискретті есептеу 2D Livewire алгоритмін шекаралық / кобедиялық операторлар тұрғысынан қайта түсіндіру, содан кейін осы ұғымдарды 3D форматында қолдану. 3D минималды бетін есептеудің тиімді алгоритмі Grady қағазында да берілген.

Сондай-ақ қараңыз

Әдебиеттер тізімі

  1. ^ а б c БАЖИО, Даниэль Лелис. GPGPU негізінде кескінді сегментациялау тірі алгоритмін жүзеге асыру. 2007. 108f. Ғылым магистрінің диссертациясы - технологиялық аэронавтика институты, Сан-Хосе-дос Кампос. http://gpuwire.googlecode.com/files/Master%20Thesis%20-%20Updated%20February%2015th.pdf Мұрағатталды 2010-12-17 Wayback Machine
  2. ^ а б МОРТЕНСЕН, Е. Н .; BARRETT, W. A. ​​Кескін құруға арналған ақылды қайшы. SIGGRAPH ’95: Компьютерлік графика және интерактивті әдістер бойынша 22-ші жыл сайынғы конференция материалдары. Нью-Йорк, Нью-Йорк, АҚШ: ACM Press, 1995. б. 191–198. ISBN  0-89791-701-4.
  3. ^ Лео Греди, «Минималды беттер қысқа жолды сегменттеу әдістерін 3D-ге дейін кеңейтеді ”, IEEE Transaction on Pattern талдау және машиналық интеллект, т. 32, No2, 321-334 б., 2010 жылғы ақпан

Сыртқы сілтемелер