Суайрық (кескінді өңдеу) - Watershed (image processing)

Зерттеуінде кескінді өңдеу, а су алабы а-да анықталған түрлендіру болып табылады сұр реңк сурет. Атау метафоралық тұрғыдан геологиялық мағынаны білдіреді су алабы немесе көршілес дренаждық бассейндерді бөлетін дренажды бөлу. Су бөлігінің трансформациясы жұмыс істейтін кескінді а-ға ұқсатады топографиялық карта, әр нүктенің жарықтығымен оның биіктігін бейнелейді және жоталардың шыңдары бойымен өтетін сызықтарды табады.

Су алабы туралы әр түрлі техникалық анықтамалар бар. Жылы графиктер, суайрық сызықтары түйіндерде, шеттерде немесе түйіндер мен шеттерде гибридтік сызықтармен анықталуы мүмкін. Суайрықтар үздіксіз доменде де анықталуы мүмкін.[1] Сонымен қатар әртүрлі алгоритмдер суайрықтарын есептеу. Су алқаптарының алгоритмдері кескінді өңдеу кезінде негізінен қолданылады сегменттеу мақсаттары.

Анықтамалар

Геологияда а су алабы іргелес су жинау бассейндерін бөліп тұрған бөлініс.

Су тасқыны арқылы суайрық

Идеяны 1979 жылы С.Бучер мен К.Лантуйоль енгізген.[2] Негізгі идея әр аймақтық минимумға су көзін рельефке орналастырудан, барлық рельефті қайнар көздерден тасып кетуден және әртүрлі су көздері тоғысқанда тосқауылдардан тұрудан тұрды. Алынған тосқауылдар жиынтығы су тасқыны болып табылады. Осы алгоритмге «Басымдық-су тасқыны» деп аталатын бірқатар жақсартулар енгізілді.[3]

Топографиялық арақашықтық бойынша су бөлгіш

Топографиялық рельефке түсетін су тамшысы интуитивті түрде «ең жақын» минимумға қарай ағып жатыр. «Жақын» минимум - ең төмен түсу жолының соңында болатын минимум. Топография тұрғысынан, егер бұл нүкте сол минималды су жиналатын бассейнде болса, пайда болады. Алдыңғы анықтама бұл шартты тексермейді.

Су тамшысының принципі бойынша су бөлгіш

Су айдыны интуитивті түрде аймақ минимумдарының бөлінуі болып табылады, одан судың тамшысы айқын минимумдарға қарай төмен қарай ағуы мүмкін. Осы интуитивті идеяны ресімдеу ұсынылды [4] жиектелген графиктің су бөлгішін анықтау үшін.

Пиксель аралық суайрық

С.Бучер мен Ф.Мейер су бөлу әдісін алгоритмдік пиксель аралық енгізуді енгізді,[5] келесі рәсім берілген:

  1. Әрбір минималды нақты белгімен белгілеңіз. Жинақты бастаңыз S белгіленген түйіндермен.
  2. Шығару S түйін х минималды биіктік F, бұл дегеніміз F(х) = мин {F(ж)|ж ∈ S}. Белгісін төлсипатқа қосыңыз х әрбір белгісіз түйінге ж іргелес хжәне енгізіңіз ж жылыS.
  3. 2-қадамды дейін қайталаңыз S бос.

Топологиялық суайрық

Алдыңғы түсініктер су жинау бассейндеріне назар аударады, бірақ өндірілген бөлу сызығына емес. Топологиялық су бөлгішті М.Купри мен Г.Бертран 1997 жылы енгізген,[6] және келесі негізгі қасиеттерді пайдаланушы: W функциясы - бұл F функциясының суайрығы егер және егер болса W ≤ F және W аймақтық минимумдар арасындағы контрастты сақтайды; мұнда екі аймақтық минимум арасындағы контраст М1 және М.2 М-ден өту үшін ең төменгі биіктікке көтерілу керек1 М2.[7] Тиімді алгоритм қағазда егжей-тегжейлі көрсетілген.[8]

Су алқабы алгоритмі

Су айдыны принципін пайдалану үшін әртүрлі тәсілдерді қолдануға болады кескінді сегментациялау.

  • Маркер ретінде кескін градиентінің жергілікті минимумдарын таңдауға болады, бұл жағдайда артық сегментация жасалады және екінші қадам аймақтың бірігуін қамтиды.
  • Су айдынын түрлендіру негізінде пайдаланушы нақты анықтаған немесе автоматты түрде морфологиялық операторлармен немесе басқа тәсілдермен анықтаған арнайы маркерлер позицияларын қолданады.

Мейердің су басу алгоритмі

Су алқаптарының ең кең таралған алгоритмдерінің бірін Ф.Мейер 1990 жылдардың басында енгізді, дегенмен осы алгоритмге «Приоритет-Тасқын» деп аталатын бірқатар жақсартулар енгізілді,[9] триллион пикселден тұратын мәліметтер жиынтығына жарамды нұсқаларын қоса.[10]

Алгоритм сұр масштабты кескін бойынша жұмыс істейді. Сұр түсті рельефтің кезекті тасқыны кезінде іргелес су жиналатын бассейндері бар су айдындары салынады. Бұл су басу процесі градиент кескінінде орындалады, яғни бассейндер жиектер бойымен пайда болуы керек. Әдетте бұл кескіннің тым сегментациясына әкеледі, әсіресе шулы сурет материалы үшін, мысалы. медициналық КТ мәліметтері. Немесе кескін алдын-ала өңделуі керек немесе кейіннен ұқсастық критерийі негізінде аймақтар біріктірілуі керек.

  1. Су тасқыны басталатын маркерлер жиынтығы, пикселдер таңдалды. Әрқайсысына әртүрлі затбелгі беріледі.
  2. Әрбір белгіленген аймақтың көршілес пиксельдері пикселдің градиент шамасына сәйкес келетін басымдылық деңгейіне ие кезекке енгізіледі.
  3. Басымдылық деңгейі ең жоғары пиксел басымдылық кезегінен шығарылады. Егер шығарылған пиксельдің таңбаланған көршілерінің барлығында бірдей белгі болса, онда пиксел олардың белгілерімен белгіленеді. Басымдылық кезегінде әлі белгіленбеген барлық көршілер басымдық кезегіне қойылады.
  4. 3-қадамды басымдылық кезегі бос болғанша қайталаңыз.

Белгіленбеген пикселдер - бұл суайрық сызықтары.

Фармацевтикалық түйіршіктер популяциясы үшін су маршруты маркермен қолдау трансформациясының мысалы. Суайрық сызықтары КТ кескін стекіне қара түспен орналастырылған [11].

Оңтайлы орман алгоритмдері (суайрықтарды кесу)

Су бөлгіштерді оңтайлы орман ретінде Жан Кусти және басқалар енгізген.[12] Олар осы су айдындарының дәйектілігін анықтайды: оларды «су жинау бассейндерімен» (ең төмен түсу қасиеті арқылы) немесе осы су жинау бассейндерін бөлетін «бөлу сызықтарымен» (су принципінің төмендеуі арқылы) эквивалентті түрде анықтауға болады. Содан кейін олар эквиваленттік теорема арқылы минималды созылатын ормандар бойынша олардың оңтайлылығын дәлелдейді. Содан кейін олар есептеу үшін сызықтық уақыт алгоритмін енгізеді. Ұқсас қасиеттер басқа құрылымдарда расталмағандығын және ұсынылған алгоритм теорияда да, практикада да бар тиімді алгоритм болып табылатындығын атап өткен жөн.

Компьютерлік көріністегі басқа алгоритмдермен сілтемелер

Графикалық кесінділер

2007 жылы C. Allène және басқалар.[13] қатысты сілтемелер Графикалық кесінділер кеңейтілген ормандарға дейін. Дәлірек айтсақ, олар графиктің салмағының қуаты белгілі бір саннан жоғары болған кезде, графиктің минимизацияланатын кесіндісі энергияны қысқартатын максималды орманмен кесілгенін көрсетеді.

Ең қысқа ормандар

The кескін орманды трансформациясы (IFT) Falcao et al.[14] бұл ең қысқа орманды есептеу процедурасы. Мұны Дж.Кусти және басқалар дәлелдеген.[15] егер IFT маркерлері салмақ функциясының экстремаларына сәйкес келсе, орман тудыратын кесінді су айдыны болып табылады.

Кездейсоқ жүру

The кездейсоқ жүру алгоритм - комбинаторлықты шешетін сегментация алгоритмі Дирихле мәселесі, 2006 жылы Л.Греди кескінді сегментациялауға бейімделген.[16]2011 жылы C. Couprie және басқалар. Графтың салмақ күші шексіздікке жақындаған кезде кездейсоқ жүргінші энергиясын минимизациялайтын кесу максималды орманмен кесу болатындығын дәлелдеді.[17]

Иерархиялар

Су ағынының иерархиялық трансформациясы нәтижені графикалық дисплейге айналдырады (яғни сегменттелген аймақтардың көршілес қатынастары анықталады) және одан әрі су ағындарының трансформацияларын рекурсивті түрде қолданады. Қараңыз [18] толығырақ ақпарат алу үшін. Су бөлгішті иерархиялық сегментациямен байланыстыратын теория жасалды[19]

Ескертулер

  1. ^ Л.Найман және М.Шмитт. Үздіксіз жұмыс істейтін су айдыны. Сигналды өңдеуде (Математикалық морфологияның арнайы шығарылымы), т. 38 (1994), 99–112 беттер
  2. ^ Серж Бучер мен Кристиан Лантуэй суреттерді өңдеу, нақты уақыт режимінде және қозғалысты анықтау бойынша семинар (1979). http://cmm.ensmp.fr/~beucher/publi/watershed.pdf
  3. ^ Барнс, Р., Леман, С., Мулла, Д., 2014. Су тасқыны басымдығы: сандық биіктік модельдері үшін оңтайлы депрессияны толтыру және су айдынын белгілеу алгоритмі. Компьютерлер және геоғылымдар 62, 117–127. дои:10.1016 / j.cageo.2013.04.024
  4. ^ Дж.Кусти, Г.Бертран, Л.Найман және М.Купри. Су алқабын кесу: ең аз созылатын ормандар және судың тамшысы принципі, Үлгіні талдау және машиналық интеллект бойынша IEEE транзакциялары 31 (8) 1362-1374 бет, 2009,
  5. ^ Серж Бучер және Фернанд Мейер. Сегменттеудің морфологиялық тәсілі: су алабының трансформациясы. Жылы Суреттерді өңдеудегі математикалық морфология (Ред. E. R. Dougherty), 433-481 беттер (1993).
  6. ^ М.Купри, Г.Бертран. Топологиялық сұр масштабтағы суайрық өзгерісі. Proc. ofSPIE Vision Geometry V, 3168 том, 136–146 беттер (1997). http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.3.7654&rep=rep1&type=pdf
  7. ^ Г.Бертран. Топологиялық суайрықтарда. Математикалық бейнелеу және көру журналы, 22 (2-3), 217–230 беттер (2005).
  8. ^ Мишель Купри, Лоран Найман, Джиллес Бертран. Топологиялық су алабының квазисызықтық алгоритмдері. Математикалық бейнелеу және пайымдау журналы, Springer Verlag, 2005, 22 (2-3), б.231-249.
  9. ^ Барнс, Р., Леман, С., Мулла, Д., 2014. Су тасқыны басымдығы: сандық биіктік модельдері үшін оңтайлы депрессияны толтыру және су айдынын белгілеу алгоритмі. Компьютерлер және геоғылымдар 62, 117–127. дои:10.1016 / j.cageo.2013.04.024
  10. ^ Барнс, Р., 2016. Триллиондық ұяшықтардың жұмыс үстелдерінде немесе кластерлерде сандық биіктікке көтерілуіне параллельді басымдылық-тасқын депрессия. Компьютерлер және геоғылымдар. дои:10.1016 / j.cageo.2016.07.001
  11. ^ Doerr, F. J. S., & Florence, A. J. (2020). Микробөлшекті капсула формулаларын сипаттауға арналған микро-XRT кескінді талдау және машиналық оқыту әдістемесі. Халықаралық фармацевтика журналы: X, 2, 100041. https://doi.org/10.1016/j.ijpx.2020.100041
  12. ^ Жан Кусти, Джилл Бертран, Лоран Найман және Мишель Купри. Су алқабын кесу: ең аз созылатын ормандар және судың тамшысы принципі. Үлгіні талдау және машиналық интеллект бойынша IEEE транзакциялары. 31 (8). Тамыз 2009. 1362–1374 бб.
  13. ^ Седрик Аллен, Жан-Ив Аудиберт, Мишель Купри және Рено Керивен: «Минималды кесінділер, ормандар мен суайрықтардың оңтайлы бөлігі арасындағы кейбір байланыстар «, Image and Vision Computing, 2009 ж.
  14. ^ Фалькао, А.Х. Столфи, Дж. Де Аленкар Лотуфо, Р.: «Кескінді орманды түрлендіру: теория, алгоритмдер және қосымшалар «, ПАМИ-де, 2004 ж
  15. ^ Жан Кусти, Джилл Бертран, Лоран Найман және Мишель Купри. Суайрықтарды кесу: жұқару, ең қысқа ормандар және топологиялық суайрықтар. Үлгіні талдау және машиналық интеллект бойынша IEEE транзакциялары. 32 (5). 2010. 925–939 бб.
  16. ^ Греди, Л. «Кескінді сегментациялау үшін кездейсоқ жүру «. PAMI, 2006
  17. ^ Камилла Купри, Лео Греди, Лоран Найман және Хьюг Талбот »Суайрықтардағы қуат: оңтайландырудың бірыңғай графикалық негізі ”, IEEE Transaction on Pattern талдау және машиналық интеллект, т. 33, No7, 1384-1399 б., 2011 жылғы шілде
  18. ^ Лоран Найман, Мишель Шмитт. Суайрық контурларының геодезиялық анықтылығы және иерархиялық сегментация. IEEE Transaction on Pattern Analysis and Machine Intelligence, Institute of Electric and Electronics Engineers, 1996, 18 (12), pp163-1173.
  19. ^ Лоран Найман. Иерархиялық сегментация мен ультраметриялық суайрық арасындағы эквиваленттілік туралы. Математикалық бейнелеу және пайымдау журналы, Springer Verlag, 2011, 40 (3), б.231-247.

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

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