Vandenskyros transformacija

Vandenskyros transformacija – vaizdų segmentavimo algoritmas, imituojantis vandenskyros linijų radimą pagal vietovės reljefą.^[1]

Praktiškai vandenskyros transformacija paprastai naudojama ne pačiam vaizdui, o jo gradientui.^[1]^[2] Tačiau kartais naudojama ir vaizdo atstumo funkcija.^[2]

Neformalus požiūris redaguoti

Žiūrint neformaliai, vaizdas, kuriam taikoma vandenskyros transformacija, atitinka vietovės reljefą. Vandenskyros linijų jame gali būti ieškoma dviem pagrindiniais būdais. Istoriškai pirmu būdu imituojamas lietaus lašų tekėjimas nuo bet kurio vaizdo taško žemyn (link atitinkamo lokalinio minimumo). Tokiu atveju taškai, nuo kurių vanduo teka link to paties lokalaus minimumo, vadinami baseinu, o baseinų ribos – vandenskyros linijomis. Pagal kitą interpretaciją laikoma, kad reljefas nardinamas į vandenį, kuris gali prasiskverbti į paviršių per lokalinius minimumus. Tokiu atveju vandenskyros linijos atskiria skirtingų minimumų užtvindomus baseinus. Laikoma, kad pastaroji interpretacija leidžia algoritmą realizuoti paprasčiau.^[3]

Tolydusis atvejis redaguoti

Tolydžiu atveju vandenskyros transformacija apibrėžiama pagal atstumo funkcijas.^[1] Viena iš tokių atstumo funkcijų yra topografinis atstumas, kuris yra apibrėžiamas kaip mažiausias (infimumo prasme) gradiento kreivinis integralas per galimus kelius nuo vieno taško iki kito:

T_{f}(p,q)=\inf _{\gamma \in D,\gamma (0)=p,\gamma (1)=q}\int _{\gamma }{\lVert \nabla f(\gamma (s))\rVert }ds,

kur p ir q – atitinkami taškai, f – tolydi, bent du kartus diferencijuojama funkcija, apibrėžta srityje D.^[1]

Tada, jei {m_k} yra funkcijos lokalių minimumų aibė, kurios indeksai k sudaro aibę I, minimumo baseinas apibrėžiamas kaip^[1]

B(m_{i})=\{x\in D|\forall k\in I/\{i\}:f(m_{i})+T_{f}(x,m_{i})<f(m_{j})+T_{f}(x,m_{j})\}.

Savo ruožtu, vandenskyros linijos tokiu atveju apibrėžiamos kaip aibė taškų, kurie nepriklauso jokiam baseinui:^[1]

W(f)=D/\bigcup _{i\in I}B(m_{i}).

Pati vandenskyros transformacija gali būti laikoma funkcija, kurios apibrėžimo sritis yra D:^[1]

\lambda :D\to I\cup \{W\},~W\notin I.

Ji priskiria kiekvienam taškui, priklausančiam kuriam nors baseinui, atitinkamo baseino numerį, o kiekvienam taškui, priklausančiam vandenskyros linijai, numerį, nesutampantį su jokio baseino numeriu:^[1]

\lambda (p)={\begin{cases}i,~p\in B(m_{i}),\\W,~p\in W(f).\end{cases}}

Diskretusis atvejis redaguoti

Diskrečiuoju atveju vandenskyros transformacijos radimas apsunkinamas dėl to, kad diskrečiame vaizde gali būti didelų vientisų plotų su pastoviomis pikselių reikšmėmis.^[1]

Pagal vieną iš apibrėžimų, vandenskyros transformacija atliekama imituojant nardinimą į vandenį. Tokiu atveju vaizdą apibrėžus funkcija f, kuri kiekvienam pikseliui grąžina jo reikšmę, baseinai randami rekursiškai:^[1]

X_{h}={\begin{cases}\{p\in D|f(p)=h_{min}\},~h=h_{min},\\MIN_{h}\cup IZ_{T_{h}}(X_{h-1}),~h>h_{min}.\end{cases}}

Čia MIN_h yra aibė lokalinių minimumų, kurių reikšmės yra h, T_h – aibė pikselių, kurių reikšmės neviršija h, o IZ atitinka užtvindytą plotą:^[1]

IZ_{A}(B)=\bigcup _{i=1}^{k}iz_{A}(B_{i}),

kur iz – geodezinė įtakos zona:

iz_{A}(B_{i})=\{p\in A|\forall j\in [1;k]/\{j\}:d_{A}(p,B_{i})<d_{A}(p,B_{j})\}.

Kitaip tariant, jei A poaibis B yra sudarytas iš k sričių, tai kiekvieną jų atitinka geodezinė įtakos zona, sudaryta iš taškų, kurie yra arčiau šios srities, nei bet kurios iš likusių sričių.

Algoritmai redaguoti

Esama įvairių algoritmų, realizuojančių vandenskyros transformaciją.

Pagal Mejerio algoritmą prieš skaičiavimus yra duotas paveikslėlis ir pradiniai žymekliai su skirtingomis žymėmis. Visi gretimi žymekliams žymės neturintys pikseliai įtraukiami į prioritetinę eilę, kurioje prioritetas nustatomas pagal pikselio reikšmę (mažesnė reikšmė – aukštesnis prioritetas). Po to iš šios eilės vis imami pikseliai. Jei pažymėtų paimto pikselio kaimynų žymės sutampa, šiam pikseliui irgi priskiriama ta žymė ir į eilę įtraukiami nepažymėti jo kaimynai. Galiausiai visi vienam baseinui priklausantys pikseliai gauna tas pačias žymes, o vandenskyros linijoms priklausantys pikseliai lieka nepažymėti. Yra žinoma, kad šiuo algoritmu gaunamos vandenskyros linijos visada yra plonos (vieno pikselio pločio).^[4]

Pagal Vincento-Soilo algoritmą prieš skaičiavimą yra duotas tik pats paveikslėlis. Skaičiavimai jame atliekami dviem etapais. Pirmajame etape vaizdo pikseliai yra surikiuojami reikšmės didėjimo tvarka. Kitame etape vis imami mažiausią reikšmę turintys neapdoroti pikseliai. Jiems priskiriama pradinė žymė. Tokie pikseliai, turintys kaimynų, apdorotų ankstesniuose žingsniuose, rašomi į eilę. Po to iš šios eilės vis imami pikseliai, į ją dedant pradinę žymę turinčius jų kaimynus. Tie paimti iš eilės pikseliai, kurių neapdoroti kaimynai priklauso skirtingiems baseinams, priskiriami vandenskyros linijai, tuo tarpu turintys kaimynus tik iš vieno baseino, gauna jo žymę (pikseliai, kurių visi neapdoroti kaimynai priklauso vandenskyros linijai taip pat jai priskiriami, nors tokią žymę kitame žingsnyje leidžiama pakeisti į baseino žymę). Pikseliai, kurie ir po tokio apdorojimo turi pradinę žymę, laikomi naujais lokaliais minimumais ir gauna naują žymę. Nustatyta, kad tokio algoritmo laikinis sudėtingumas yra tiesinis.^[1]

Taip pat esama algoritmų, kurie atlieka vandenskyros transformaciją pagal topografinį atstumą.^[1]

Vandenskyros transformacijos radimas išlygiagretinamas dviem pagrindiniais būdais. Pagal vieną iš jų vaizdas yra skaidomas į dalis, kurios paskirstomos procesoriams ir apdorojamos, o tada gauti rezultatai suliejami. Pagal kitą procesoriams paskirstomos ne vaizdo dalys, o lokaliniai minimumai.^[1]

Dažnesni patobulinimai redaguoti

Kadangi vandenskyros transformacija paprastai randa daugiau plotų, negu iš tikro esama (kitaip tariant, stebima perteklinė segmentacija), naudojami įvairūs metodai randamų plotų kiekiui sumažinti. Vienas iš jų – žymekliais valdoma vandenskyros transformacija.^[2] Pagal šį metodą yra parenkami pikseliai, kurie priklauso objektams (objektų žymekliai) ir pikseliai, kurie priklauso fonui (fono žymekliai).^[2] Tada gradientinis vaizdas modifikuojamas taip, kad jame liktų tik ribos tarp žymeklių.^[2] Tam gali būti pritaikoma morfologinė rekonstrukcija.^[5]

Šaltiniai redaguoti

↑ ^1,00 ^1,01 ^1,02 ^1,03 ^1,04 ^1,05 ^1,06 ^1,07 ^1,08 ^1,09 ^1,10 ^1,11 ^1,12 ^1,13 Jos B. T. M. Roerdink, Arnold Meijster „The watershed transform: definitions, algorithms, and parallellization strategies“, Fundamenta Informaticae, vol. 41, pp. 187–228, 2000. [1][2] Archyvuota kopija 2009-11-23 iš Wayback Machine projekto.
↑ ^2,0 ^2,1 ^2,2 ^2,3 ^2,4 Serge Beucher, „The watershed transformation applied to image segmentation“ Scanning Microscopy Supplement 6:299–314, 1992. [3] Archyvuota kopija 2008-11-22 iš Wayback Machine projekto.
↑ R. Beare „A locally constrained watershed transform“, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 28, issue 7, p. 1063–1074, doi 10.1109/TPAMI.2006.132, [4]
↑ Michel Couprie, Gilles Bertrand „Topological Grayscale Watershed Transformation“, SPIE Vision Geometry V Proceedings, 3168, 1997, 136–146 [5]
↑ Luc Vincent „Morphological grayscale reconstruction in image analysis: Applications and efficient algorithms“, IEEE Transactions on Image Processing, 1993, Vol. 2, No. 2, pp. 176–201, [6]

Papildomam skaitymui redaguoti

Lamia Jaafar Belaid, Walid Mourou, „Image segmentation: a watershed transformation algorithm“, Image Analysis and Stereology, June 2009, vol. 28, p. 93-102, [7]^{[neveikianti nuoroda]}
Corinne Vachier, Fernand Meyer, „The Viscous Watershed Transform“, Journal of Mathematical Imaging and Vision, 2005, Vol. 22, Nr. 2-3, p. 251–267, doi 10.1007/s10851-005-4893-3, [8]^{[neveikianti nuoroda]}
Romaric Audigier, Roberto de Alencar Lotufo, „Watershed by Image Foresting Transform, Tie-Zone, and Theoretical Relationships with Other Watershed Definitions“, Proceedings of the 8th International Symposium on Mathematical Morphology (ISMM’07), 2007, Rio de Janeiro (RJ), Brazil, [9] Archyvuota kopija 2016-03-09 iš Wayback Machine projekto.
Erlend Hodneland, Xue-Cheng Tai, Joachim Weickert, Nickolay V. Bukoreshtliev, Arvid Lundervold, Hans-Hermann Gerdes, „Level Set Methods for Watershed Image Segmentation“, Lecture Notes in Computer Science, vol. 4485/2010, p. 178–190 Juodraštis^{[neveikianti nuoroda]}
Serge Beucher, C. Lantuejoul, „Use of watersheds in contour detection“ International Workshop on image processing, real-time edge and motion detection/estimation, Rennes, France, Sept. 1979. [10] Archyvuota kopija 2011-09-27 iš Wayback Machine projekto.

Šis straipsnis yra tapęs savaitės straipsniu.

[RoerdinkMeijster_2000-1] 1,00 ^1,01 ^1,02 ^1,03 ^1,04 ^1,05 ^1,06 ^1,07 ^1,08 ^1,09 ^1,10 ^1,11 ^1,12 ^1,13 Jos B. T. M. Roerdink, Arnold Meijster „The watershed transform: definitions, algorithms, and parallellization strategies“, Fundamenta Informaticae, vol. 41, pp. 187–228, 2000. [1][2] Archyvuota kopija 2009-11-23 iš Wayback Machine projekto.

[Beucher_1992-2] 2,0 ^2,1 ^2,2 ^2,3 ^2,4 Serge Beucher, „The watershed transformation applied to image segmentation“ Scanning Microscopy Supplement 6:299–314, 1992. [3] Archyvuota kopija 2008-11-22 iš Wayback Machine projekto.

[Beare_2006-3] R. Beare „A locally constrained watershed transform“, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 28, issue 7, p. 1063–1074, doi 10.1109/TPAMI.2006.132, [4]

[Couprie_Bertrand_1997-4] Michel Couprie, Gilles Bertrand „Topological Grayscale Watershed Transformation“, SPIE Vision Geometry V Proceedings, 3168, 1997, 136–146 [5]

[Vincent_1993-5] Luc Vincent „Morphological grayscale reconstruction in image analysis: Applications and efficient algorithms“, IEEE Transactions on Image Processing, 1993, Vol. 2, No. 2, pp. 176–201, [6]

[1]

[2]

[3]

[4]

[5]