Vandenskyros transformacija

Vandenskyros transformacija – vaizdų segmentavimo algoritmas, imituojantis vandenskyros linijų radimą pagal vietovės reljefą.
Praktiškai vandenskyros transformacija paprastai naudojama ne pačiam vaizdui, o jo gradientui. Tačiau kartais naudojama ir vaizdo atstumo funkcija.

Neformalus požiūris

Ž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.

Algoritmai

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).
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.
Taip pat esama algoritmų, kurie atlieka vandenskyros transformaciją pagal topografinį atstumą.
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.

Dažnesni patobulinimai

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. Pagal šį metodą yra parenkami pikseliai, kurie priklauso objektams (objektų žymekliai) ir pikseliai, kurie priklauso fonui (fono žymekliai). Tada gradientinis vaizdas modifikuojamas taip, kad jame liktų tik ribos tarp žymeklių. Tam gali būti pritaikoma morfologinė rekonstrukcija.