4. Segmentacija oz. razčlenjevanje slik

Od matrike števil do objektov: pragovne operacije, določanje pragov, označevanje regij, sledenje meji in ujemanje šablon. Daje izpitne naloge 8, 9, 10 in 11.

Kaj je segmentacija ključno

Segmentacija je proces, ki sliko razdeli (razčleni) na posamezne dele (regije), ki imajo močno korelacijo z objekti/področji iz realnega sveta, vsebovanega v sliki.

Glede na cilj ločimo dve vrsti segmentacije:

popolna segmentacija — rezultira v množici disjunktnih (tujih) regij, ki enolično ustrezajo objektom v vhodni sliki;
delna segmentacija — dobljene regije ne ustrezajo direktno objektom.

Pri delni segmentaciji sliko razdelimo na ločene regije, ki so homogene glede na izbrano lastnost (npr. sivina, barva, vsebina, tekstura). Delno segmentirano sliko še nadalje obdelamo, pri čemer vključimo znanje iz višjih nivojev (npr. znanje o naravi iskanih objektov, medsebojnih relacijah, lastnostih ozadja).

Segmentacijske metode so večinoma vezane na problem, ki ga rešujejo: problem definira način, po katerem se poudarjajo iskane lastnosti objektov, ter način, kako se uravnavajo in sklepajo kompromisi med želenimi lastnostmi.

Tri skupine segmentacijskih metod

Segmentacija z globalnim znanjem o sliki oz. njenih delih (npr. pragovna operacija) — znanje zbrano v raznih histogramih (npr. sivin).
Segmentacija na osnovi robov.
Segmentacija na osnovi regij.

Slednji dve pomenita dualni problem: vsaka regija je namreč lahko predstavljena s sklenjeno konturo in obratno.

Originalni prosojnici (str. 52–53)

Pragovna operacija ključno nalogi 8–9

Najpreprostejša in najhitrejša segmentacijska metoda.

Vhod: originalna slika (npr. slika sivin $I$)
Izhod: segmentirana slika $S$

Enopragovne operacije

na listu

1. S konstantnim pragom T

$$S(i,j) = \begin{cases} 1; & \text{IF } I(i,j) \geq T \\ 0, & \text{ELSE} \end{cases}$$

na listu

2. Z variabilnim pragom T(i, j)

$$S(i,j) = \begin{cases} 1; & \text{IF } I(i,j) \geq T(i,j) \\ 0, & \text{ELSE} \end{cases}$$

Enopragovne operacije, še predvsem z globalnim pragom, so primerne za segmentiranje preprostih scen — torej scen, kjer se sivine objektov bistveno razlikujejo od sivin ozadja.

Vrednost $S(i,j) \neq 0$ označuje piksle objekta(ov), vrednost $S(i,j) = 0$ pa piksle ozadja.

Večpragovne operacije

na listu

Večpragovna operacija

$$S(i,j) = \begin{cases} 0; & \text{IF } I(i,j) < T_1 \\ 1; & \text{IF } T_1 \leq I(i,j) < T_2 \\ 2; & \text{IF } T_2 \leq I(i,j) < T_3 \\ \vdots & \vdots \\ n-1; & \text{IF } T_{n-1} \leq I(i,j) < T_n \\ n; & \text{ELSE} \end{cases}$$

Metode za določanje globalnih pragov naloga 9

Prvi dve metodi ne potrebujeta pomožnih izrazov:

Eksperimentalno.
Polovica med minimalno in maksimalno sivino v sliki:

na listu $$T = \frac{\min + \max}{2}$$

Za izračun pragov po ostalih metodah moramo določiti nekaj pomožnih izrazov iz slike $I$:

na listu

Pomožni izrazi

$$h = [h_0, h_1, \dots, h_Q] \qquad A_k = \sum_{i=0}^{k} h_i \qquad B_k = \sum_{i=0}^{k} i\,h_i$$

Izraz	Pomen
$h$	histogram sivin
$A_k$	število pikslov, ki imajo sivino manjšo ali enako $k$
$B_k$	obtežena vsota pikslov do sivine $k$ — proporcionalna povprečni svetlosti, če upoštevamo zgolj piksle do sivine $k$
$A_Q$	število vseh pikslov v sliki, tj. $A_Q = MN$
$B_Q$	vsota vseh sivin v sliki, tj. $B_Q = \sum_i \sum_j I(i,j)$

3. Globalni povprečni prag (MEAN)

na listu$$T = \frac{B_Q}{A_Q}$$

4. Globalni prag določen z mediano (MEDIAN)

Prag $T$ izberemo tako, da velja:

na listu$$\frac{A_T}{A_Q} \approx 0{,}5$$

Torej: pri katerem $T$ kumulativa doseže polovico vseh pikslov.

5. Globalni optimalni prag (OPTIMAL)

Iterativni postopek. Potrebujemo začetni približek za prag v koraku 0, tj. $T_0$. V $k$-tem koraku izračunamo dva pomožna izraza:

na listu

Povprečji ozadja in objektov

$$\mu_{T_k} = \frac{B_{T_k}}{A_{T_k}} \qquad \text{in} \qquad \gamma_{T_k} = \frac{B_Q - B_{T_k}}{A_Q - A_{T_k}}$$

$\mu_{T_k}$ je povprečna sivina trenutnega ozadja, $\gamma_{T_k}$ je povprečje trenutnega objekta(ov). Nov prag v koraku $k+1$ določimo kot:

na listu $$T_{k+1} = \frac{\mu_{T_k} + \gamma_{T_k}}{2} \qquad\qquad \text{konec, ko } |T_{k+1} - T_k| < \epsilon$$

kjer je $\epsilon$ majhno realno število.

6. Globalni prag določen z entropijo (KAPUR)

Prag določimo tako, da maksimiziramo informacijo med ozadjem in objekti — poiščemo maksimum izraza:

na listu

Kapurjev kriterij

$$\max_T \big[ H_{\text{ozadje}}(T) + H_{\text{objekti}}(T) \big]$$ $$H_{\text{ozadje}}(T) = -\sum_{i=0}^{T} \frac{p_i}{P_T}\log\frac{p_i}{P_T} \qquad H_{\text{objekti}}(T) = -\sum_{i=T+1}^{Q} \frac{p_i}{1-P_T}\log\frac{p_i}{1-P_T}$$ $$p = \frac{1}{MN}h \qquad P_T = \sum_{i=0}^{T} p_i$$

kjer je $p = [p_0, p_1, \dots, p_Q]$ normiran histogram sivin.

Originalne prosojnice (str. 54–59)

Označevanje regij naloga 8

📎 Dopolnjeno iz zapiskov DOSIS

Postopka označevanja (labeliranja) regij v prosojnicah URVRV ni razdelano, je pa izpitna naloga 8. Postopek je opisan v dodatnem gradivu (DOSIS, poglavje 5.6.1 »Označevanje regij«) in gre takole.

Po pragovni operaciji dobimo binarno sliko. Regije označimo z enim prehodom čez sliko:

Sliko pregledujemo od levega zgornjega piksla, najprej desno do konca vrstice, nato navzdol.
Za vsak piksel objekta pogledamo že pregledane sosede — pri 8-sosedstvu so to: levo, zgoraj-levo, zgoraj, zgoraj-desno; pri 4-sosedstvu samo levo in zgoraj.
Če noben od njih ni objekt → pikslu dodelimo novo oznako (naslednje prosto število).
Če je vsaj eden objekt → pikslu dodelimo najmanjšo oznako med sosedi; če sta soseda imela različni oznaki, si zapomnimo, da sta ekvivalentni, in ju na koncu združimo.

Ozadje ima vedno oznako 0.

Pragovna operacija na sliki robov razumevanje

V sliki robov imajo »nepravi« robni piksli vrednosti zelo blizu 0 (vendar $\neq 0$!). Razlogi so: šum v podatkih, majhne nepravilnosti v osvetlitvi scene ipd.

Prave robne piksle (oz. močne robove) lahko dobimo s pragovno operacijo — uporabimo lahko vso znanje o pragovni operaciji!

A. Sledenje meji naloga 10

Vsaka regija ima definirano mejo (region border). Ločimo dve vrsti mej:

notranja meja — dejanska meja regije in je del regije (krivulja na skrajnem zunanjem delu regije);
zunanja meja — je meja ozadja in ni del regije (najbližja in najkrajša krivulja, ki oklepa opazovano regijo in ni del regije).

Algoritem sledenja meji deluje za regije večje od 1 piksla.
Pri sledenju se lahko včasih vrnemo v isto točko.
S tem algoritmom ni možno najti meje za luknje znotraj regij!

Algoritem sledenja notranji meji (za 8-sosedstvo)

Preiskuj segmentirano sliko od leve proti desni navzdol. Prvi najdeni piksel regije (z vrednostjo $\neq 0$) označi s $p_0$. To je prvi piksel meje. Spremenljivka dir hrani smer pomika vzdolž meje (od prejšnjega do trenutnega piksla meje). Priredi: dir = 7.
Preišči 3×3 okolico trenutnega piksla v proti urni smeri. Začni pri pikslu, ki je v smeri:
- (dir + 7) mod 8, IF dir je liho število;
- (dir + 6) mod 8, ELSE.
Prvi najdeni piksel, ki ima enako vrednost kot trenutni piksel, je novi element meje (označimo ga s $p_n$). Ažuriraj spremenljivko dir.
IF ($p_n = p_1$) AND ($p_{n-1} = p_0$) THEN Konec, ELSE Korak 2.
Notranja meja je določena s piksli $p_0, p_1, \dots, p_{n-2}$.

Problem za sledenje so področja, kjer je meja prekinjena (npr. zaradi šuma, prekrivanja objektov). Rešitev: uporabimo hevristične pristope — predvidimo potek meje na takšnih področjih.

Sledenje v sivinskih slikah je možno, vendar predstavlja težji problem kot na binarnih oz. že segmentiranih slikah.

⚠️ Kako šteti obiskane piksle

Prvi najdeni piksel je $p_0$ in šteje kot prvi obiskani. Če naloga vpraša »kateri piksel obiščemo 3. po vrsti«, je odgovor $p_2$ — ne $p_3$.

Originalni prosojnici (str. 60–61)

Ujemanje šablon naloga 11

Ujemanje rešuje naslednji problem: v sliki $I$ želimo poiskati znan objekt (lahko vzorec ipd.), pri čemer je objekt lahko tudi rotiran. Iskan objekt predstavimo v obliki podslike oz. šablone $H$.

Položaj iskanega objekta v sliki določimo kot tisti položaj, kjer izračunamo najboljše ujemanje med šablono in sliko, glede na nek kriterij ujemanja.

Algoritem

Izračunaj kriterij ujemanja $C$ za vsako možno lokacijo in rotacijo iskanega objekta (šablone $H$) v sliki $I$.
Lokalni maksimum kriterija $C$, pri čemer je $C \geq T$, določa položaj iskanega objekta v sliki.

Kriterij ujemanja $C$ lahko definiramo kot korelacijo med iskano šablono in sliko:

na listu

Dva kriterija ujemanja

$$C_1(i,j) = \left[ \max_{(u,v)\in H} \big| I(i+u,\, j+v) - H(u,v) \big| \right]^{-1}$$ $$C_2(i,j) = \left[ \sum_{(u,v)\in H} \big| I(i+u,\, j+v) - H(u,v) \big|^p \right]^{-1}, \qquad p = \{1, 2\}$$

⚠️ Zakaj je kriterij obrnjen (⁻¹)

Znotraj oklepaja je razlika — manjša je, boljše je ujemanje. Ker algoritem išče maksimum, celoten izraz obrnemo. Pri popolnem ujemanju je razlika 0 in $C \to \infty$. Odgovor na izpitu podaj kot položaj središča šablone, ne njenega vogala.

Originalni prosojnici (str. 62–63)

Preveri se

1Histogram 3-bitne slike z 20 piksli je h = [3, 4, 3, 4, 1, 4, 1, 0]. Kolikšen je globalni prag po metodi MEDIAN?

Razlaga

Kumulative: $A_0 = 3$ (0,15), $A_1 = 7$ (0,35), $A_2 = 10$ (0,50), $A_3 = 14$ (0,70)…

Iščemo $T$, pri katerem je $A_T/A_Q \approx 0{,}5$ — to je natanko $T = 2$. Odgovor c) je past: 10 je število pikslov, ne sivina.

2Pri algoritmu sledenja notranji meji je dir = 7. Pri kateri smeri začnemo preiskovati okolico?

Razlaga

Pravilo: če je dir liho število → začni pri (dir + 7) mod 8; sicer pri (dir + 6) mod 8. Ker je 7 liho, je začetna smer $(7+7) \bmod 8 = 14 \bmod 8 = \mathbf{6}$. Nato gremo v proti urni smeri, torej po naraščajočih številkah smeri: 6, 7, 0, 1, 2…

3Šablona velikosti 3×5 se popolnoma ujema s pikslami slike v vrsticah 5–7 in stolpcih 2–6. Kateri položaj navedemo kot rezultat?

Razlaga

Pri ujemanju šablon masko položimo tako, da je njeno središče na obravnavanem pikslu — enako kot pri konvoluciji. Središče šablone 3×5 je odmaknjeno za (1, 2) od njenega levega zgornjega kota.

Torej: $(5 + 1,\; 2 + 2) = \mathbf{(6, 4)}$.