Formule z dovoljenega lista

Vse formule z obeh strani lista, ki ga dobiš na izpitu — urejene po poglavjih, z razlago vsake oznake. Na koncu je seznam tega, česar na listu ni in se moraš zato naučiti.

⚠️ Kaj list dejansko je in kaj ni

List da zapis formule, ne postopka. Primer: na listu piše $T_{k+1} = \frac{\mu_{T_k} + \gamma_{T_k}}{2}$, ni pa napisano, da je to iterativni postopek, ki potrebuje začetni približek $T_0$ in pogoj za ustavitev.

Zato je edino smiselno delo z listom: vedeti, kje je katera formula, in vedeti, kaj pomeni vsaka oznaka v njej. Iskanje po listu med izpitom stane minute, ki jih nimaš.

1. Uvod in zajemanje slik

na listu
Največja sivina
$$Q = 2^8 - 1 = 255 \quad \text{nivoji sivine}$$
na listu
Širina razreda pri A/D pretvorbi
$$\triangle = \frac{U_{\max} - U_{\min}}{256}$$
💡 Kar na listu manjka

Formule za samo pretvorbo napetosti v sivino na listu ni. Uporabi: $g = \left\lfloor \dfrac{U - U_{\min}}{U_{\max} - U_{\min}} \cdot Q \right\rceil$, kjer se napetosti nad $U_{\max}$ porežejo na $Q$.

2. Model kamere

na listu
Perspektivna projekcija
$$P = [x, y, z], \quad P' = [x', y', z'], \quad z' = f' \qquad\Longrightarrow\qquad x' = f'\frac{x}{z}, \quad y' = f'\frac{y}{z}$$
na listu
Enačba leče
$$\frac{1}{z'} - \frac{1}{z} = \frac{1}{f}, \qquad f \text{ je goriščna razdalja}$$
na listu
Notranji parametri: α, β, u₀, v₀, θ
$$p = \frac{1}{z}\mathsf{M}P, \qquad \mathsf{M}_{3\times4} = [\mathsf{K}, 0], \qquad \mathsf{K} = \begin{bmatrix} \alpha & -\alpha\cot\theta & u_0 \\[2pt] 0 & \frac{\beta}{\sin\theta} & v_0 \\[2pt] 0 & 0 & 1 \end{bmatrix}$$ $$p = [u, v, 1]^T, \qquad P = [x, y, z, 1]$$
na listu
Kaj sta α in β
$$\alpha = kf, \qquad \beta = lf$$

$k, l$ določata velikost piksla (v px/m); $u_0, v_0$ pa premik izhodišča koordinatnega sistema iz $C$ v $C_0$.

na listu
Zunanji parametri
$$p = \frac{1}{z}\mathsf{M}P, \qquad \mathsf{M}_{3\times4} = \mathsf{K}[\mathsf{R}, t]$$ $$u = \frac{m_1 P}{m_3 P}, \qquad v = \frac{m_2 P}{m_3 P}$$

$\mathsf{R}_{3\times3}$ je rotacijska matrika, $t_{3\times1}$ stolpični vektor; $m_i$ so vrstice matrike $\mathsf{M}$.

na listu
Rotacijske matrike
$$\mathsf{R}_x = \begin{bmatrix}1&0&0\\0&\cos\alpha&\sin\alpha\\0&-\sin\alpha&\cos\alpha\end{bmatrix},\; \mathsf{R}_y = \begin{bmatrix}\cos\beta&0&-\sin\beta\\0&1&0\\\sin\beta&0&\cos\beta\end{bmatrix},\; \mathsf{R}_z = \begin{bmatrix}\cos\gamma&\sin\gamma&0\\-\sin\gamma&\cos\gamma&0\\0&0&1\end{bmatrix}$$
na listu
Kalibracija
$$(m_1 - u_i m_3)P_i = 0 \qquad (m_2 - v_i m_3)P_i = 0$$ $$\mathsf{P}_{2n\times12} = \begin{bmatrix} P_1^T & 0^T & -u_1 P_1^T \\ 0^T & P_1^T & -v_1 P_1^T \\ \vdots & \vdots & \vdots \\ P_n^T & 0^T & -u_n P_n^T \\ 0^T & P_n^T & -v_n P_n^T \end{bmatrix}, \quad m_{12\times1} = \begin{bmatrix} m_1^T \\ m_2^T \\ m_3^T \end{bmatrix}, \quad \mathsf{P}m = 0_{2n\times1}$$

3. Predobdelava slik

na listu
Linearizacija
$$g' = \frac{Q}{\max - \min}(g - \min)$$

$g'$ je nova sivina piksla; $\max$ in $\min$ sta največja in najmanjša sivina v sliki; $Q$ je največja sivina po transformaciji.

na listu
Histogram in izenačitev
$$h = [h_0, h_1, \dots, h_Q] \qquad\qquad g' = \frac{Q}{MN}\sum_{i=0}^{g} h_i$$

$h_i$ je število pikslov z enako sivino $i$; $MN$ je število pikslov v sliki.

na listu
Prenosne funkcije (primer)
$$g' = \frac{1}{16}\sqrt{g}$$
na listu
Sita in Gauss
$$H_{\text{nizko}} = \frac{1}{9}\begin{bmatrix}1&1&1\\1&1&1\\1&1&1\end{bmatrix},\qquad H_{\text{visoko}} = \begin{bmatrix}1&-2&1\\-2&5&-2\\1&-2&1\end{bmatrix},\qquad G_\sigma = \frac{1}{2\pi\sigma^2}e^{-\frac{x^2+y^2}{2\sigma^2}}$$ $$H(i,j) = \frac{1}{2\pi\sigma^2}e^{-\frac{(i-k-1)^2+(j-k-1)^2}{2\sigma^2}} \quad \text{za masko } (2k+1)\times(2k+1)$$
na listu
Detektor robov — gradient
$$|\operatorname{grad} I(x,y)| = \sqrt{\left(\frac{\partial I}{\partial x}\right)^2 + \left(\frac{\partial I}{\partial y}\right)^2} \qquad \psi = \arctan\!\left(\frac{\partial I}{\partial y}\Big/\frac{\partial I}{\partial x}\right)$$
na listu
Aproksimacije odvoda
$$\frac{\partial I(i,j)}{\partial x} \approx \frac{I(i,j) - I(i-\triangle x, j)}{\triangle x} \quad\text{— nazaj}$$ $$\frac{\partial I(i,j)}{\partial x} \approx \frac{I(i+\triangle x, j) - I(i,j)}{\triangle x} \quad\text{— naprej}$$ $$\frac{\partial I(i,j)}{\partial x} \approx \frac{I(i+\triangle x, j) - I(i-\triangle x, j)}{2\triangle x} \quad\text{— simetrična}$$
na listu
Laplace in Sobel
$$H_{\text{Laplace}} = \begin{bmatrix}1&1&1\\1&-8&1\\1&1&1\end{bmatrix} \qquad H_1 = \begin{bmatrix}1&2&1\\0&0&0\\-1&-2&-1\end{bmatrix} \qquad H_2 = \begin{bmatrix}1&0&-1\\2&0&-2\\1&0&-1\end{bmatrix}$$ $$Y = I * H_1, \quad X = I * H_2 \qquad\Longrightarrow\qquad \sqrt{X^2+Y^2}, \qquad \arctan\!\left(\frac{Y}{X}\right)$$

$H_1$ poudari horizontalne robove, $H_2$ vertikalne.

4. Segmentacija

na listu
Pragovne operacije
$$S(i,j) = \begin{cases}1, & I(i,j) \geq T \\ 0, & \text{else}\end{cases} \qquad S(i,j) = \begin{cases}1, & I(i,j) \geq T(i,j) \\ 0, & \text{else}\end{cases}$$
na listu
Večpragovna
$$S(i,j) = \begin{cases}0, & I(i,j) < T_1 \\ 1, & T_1 \leq I(i,j) < T_2 \\ 2, & T_2 \leq I(i,j) < T_3 \\ \vdots & \\ n-1, & T_{n-1} \leq I(i,j) < T_n \\ n, & \text{else}\end{cases}$$
na listu
Pomožni izrazi in metode za pragove
$$T = \frac{\min+\max}{2}, \qquad A_k = \sum_{i=0}^{k}h_i, \qquad B_k = \sum_{i=0}^{k}i\,h_i, \qquad A_Q = MN, \qquad B_Q = \sum_i\sum_j I(i,j)$$ $$T_{\text{MEAN}} = \frac{B_Q}{A_Q} \qquad\qquad T_{\text{MEDIAN}}: \; \frac{A_T}{A_Q} \approx 0{,}5$$
na listu
OPTIMAL
$$\mu_{T_k} = \frac{B_{T_k}}{A_{T_k}}, \qquad \gamma_{T_k} = \frac{B_Q - B_{T_k}}{A_Q - A_{T_k}}, \qquad T_{k+1} = \frac{\mu_{T_k}+\gamma_{T_k}}{2}, \qquad |T_{k+1}-T_k| < \epsilon$$

$\mu_{T_k}$ je povprečna sivina trenutnega ozadja, $\gamma_{T_k}$ povprečje trenutnega objekta(ov).

na listu
KAPUR
$$\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$$
na listu
Ujemanje šablon
$$C_1(i,j) = \left[\max_{(u,v)\in H}|I(i+u,j+v)-H(u,v)|\right]^{-1}$$ $$C_2(i,j) = \left[\sum_{(u,v)\in H}|I(i+u,j+v)-H(u,v)|^p\right]^{-1}, \qquad p=\{1,2\}$$

5. Zaporedje slik in gibanje

na listu
Zaporedje in čas
$$\mathcal{I} = \{I_0, I_1, \dots, I_{K-1}\}, \qquad \mathcal{I} = I(x,y,t)$$ $$t_{k+1} = t_k + \triangle t \qquad\text{oz.}\qquad t_{k+1} = t_0 + (k+1)\triangle t$$
na listu
Slike razlik in statično ozadje
$$\triangle I_k = I_{k+1} - I_k, \qquad S(p) = \begin{cases}\text{gibajoči se}, & |\triangle I_k(p)| \geq T \\ 0, & \text{else}\end{cases}$$ $$\triangle I_k = I_k - I_{\text{ozadje}}$$
na listu
Optični pretok
$$U(p) = [u_x, u_y], \qquad \frac{dI}{dt} = 0 \quad\text{oz.}\quad [I_x, I_y]\begin{bmatrix}u_x\\u_y\end{bmatrix} + I_t = 0$$ $$\mathsf{A} = \begin{bmatrix}I_x(p_1)&I_y(p_1)\\ \vdots&\vdots\\ I_x(p_Q)&I_y(p_Q)\end{bmatrix},\quad b = \begin{bmatrix}I_t(p_1)\\ \vdots\\ I_t(p_Q)\end{bmatrix},\quad u = -\mathsf{A}^{-g}b, \quad \mathsf{A}^{-g} = (\mathsf{A}^T\mathsf{A})^{-1}\mathsf{A}^T$$

6. Geometrija več pogledov

na listu
Umerjene razmere
$$p^T\mathsf{E}p' = 0, \qquad \mathsf{E} = [t_\times]\mathsf{R}, \qquad [a_\times] = \begin{bmatrix}0&-a_3&a_2\\a_3&0&-a_1\\-a_2&a_1&0\end{bmatrix}$$ $$\mathsf{E}p' = [a,b,c] \quad\Longrightarrow\quad l: \; au + bv + c = 0$$
na listu
Neumerjene razmere
$$p^T\mathsf{F}p' = 0, \qquad \mathsf{F} = \mathsf{K}^{-T}\mathsf{E}\mathsf{K}'^{-1}, \qquad F_{33} = 1$$
na listu
Vrstica pri algoritmu osmih točk
$$\big[\,u u' \;\; u v' \;\; u \;\; v u' \;\; v v' \;\; v \;\; u' \;\; v'\,\big] \cdot F = -1$$

Normaliziranje: 1) podatke premaknemo tako, da je center v koordinatnem izhodišču; 2) podatke skaliramo (povprečna razdalja $\sqrt{2}$ px).

na listu
Stereo — paralelni kameri
$$u = u', \qquad d = v' - v, \qquad z = \frac{fB}{d}, \qquad P = zp = -\frac{fB}{d}p$$

$d$ je dispariteta, $z$ absolutna oddaljenost, $B$ (osnovnica) razdalja med luknjicama $OO'$.

na listu
Rekonstrukcija (2. rešitev)
$$\begin{bmatrix}[p_\times]\mathsf{M}\\ [p'_\times]\mathsf{M}'\end{bmatrix}P = 0_{4\times1}$$
💡 Kar na listu manjka

Pri treh kamerah na listu piše samo besedilo »za vsak par uporabimo postopek za 2 kameri; P določimo kot težišče trikotnika«. Formule za uteženo težišče ni — moraš znati sam: $P = \frac{\sum w_i P_i}{\sum w_i}$.

7. Razpoznavanje vzorcev

na listu
Razdalji
$$d(x_i, x_j) = \sqrt{\sum_{k=1}^{n}(x_{i,k}-x_{j,k})^2} \qquad\qquad d(x_i, x_j) = \sum_{k=1}^{n}|x_{i,k}-x_{j,k}|$$
na listu
Predobdelava množice vzorcev
$$\mu_j = \frac{1}{N}\sum_{i=1}^{N}x_{i,j}, \qquad \sigma_j^2 = \frac{1}{N}\sum_{i=1}^{N}(x_{i,j}-\mu_j)^2, \qquad \Upsilon_j = \frac{\frac{1}{N}\sum_{i=1}^{N}(x_{i,j}-\mu_j)^3}{\sigma_j^3}$$
na listu
Normiranje — simetrična porazdelitev
$$x_{i,j} = \frac{x^*_{i,j}-\mu_j}{\sigma_j} \qquad\qquad x'_{i,j} = s_{\min} + \frac{x_{i,j}-x_j^{\min}}{x_j^{\max}-x_j^{\min}}(1-s_{\min})$$

$s_{\min}$ = 0 za interval $[0,1]$ oz. −1 za interval $[-1,1]$.

na listu
Normiranje — asimetrična porazdelitev
$$z_{i,j} = \frac{x^*_{i,j}-\mu_j}{r\sigma_j} \qquad\qquad x_{i,j} = \frac{1}{1+e^{-z_{i,j}}}$$
na listu
Najbližji sosed
$$x \in C_i \;\text{ če }\; \min_k d(x, x_{ik}) < \min_l d(x, x_{jl}) \qquad\qquad x \in C_i \;\text{ če }\; d(x, c_i) < d(x, c_j)$$ $$c_j = \frac{1}{N_j}\sum_k x_{jk}$$
na listu
Odločitvene funkcije
$$\varphi(x) = w_0 + w_1x_1 + \dots + w_nx_n \qquad\qquad \varphi_{ij}(x) = \varphi_i(x) - \varphi_j(x) = 0$$
na listu
Preizkušanje — zgornja meja napake
$$\hat{P}_e = \frac{1}{N}\sum_i \hat{P}_e^{(x_i)}, \qquad \hat{P}_{ei} = \frac{n_i}{N_i^T}$$
💡 Kar na listu manjka

Pravila (k, l) najbližjih sosedov na listu ni — samo osnovno pravilo najbližjega soseda. Zapomni si: pogledaš $k$ najbližjih, razred zmaga, če jih ima vsaj $l$.

8.–9. Perceptroni

na listu
Prenosni funkciji
$$y = f(s) = k_1 s + k_0 \qquad\qquad y = f(s) = \frac{1}{1+e^{-s}}$$
na listu
Srednja kvadratna napaka in gradientni sestop
$$E = \frac{1}{2}\sum_{x_i \in S_N}\sum_{j=1}^{n_3}\big(t_j(x_i)-y_j(x_i)\big)^2, \qquad \triangle w = -\epsilon\nabla E(w)$$ $$\triangle w_i = -\epsilon\frac{\partial E}{\partial w_i} = \sum_{x_k}\sum_j \epsilon\big(t_j(x_k)-y_j(x_k)\big)\frac{\partial y_j}{\partial w_i}$$
na listu
Enonevronski perceptron
$$s(x_i) = \hat{x}\hat{w} = \sum_{j=0}^{n}w_jx_{i,j}, \qquad E = \frac{1}{2}\sum_{x_i}\big(t(x_i)-y(x_i)\big)^2$$ $$\triangle w_j = \epsilon\sum_{x_i}\big(t(x_i)-y(x_i)\big)\frac{df}{ds}x_{i,j}, \qquad \triangle\hat{w} = \epsilon\sum_{x_i}\big(t(x_i)-y(x_i)\big)\frac{df}{ds}\hat{x}_i$$
na listu
Trinevronski dvoplastni perceptron
$$y_3 = f_3(s_3), \; s_3 = w_{30}+w_{31}y_1+w_{32}y_2$$ $$y_1 = f_1(s_1), \; s_1 = w_{10}+w_{11}x_1+w_{12}x_2 \qquad y_2 = f_2(s_2), \; s_2 = w_{20}+w_{21}x_1+w_{22}x_2$$
na listu
Označevanje — ena in nič / dvojni prag / enojni prag
$$t(x)=1 \;\forall x \in S_A, \quad t(x)=0 \;\forall x \in S_B$$ $$t(x) \geq a \; (0{,}5 0{,}5 \;\forall x \in S_A, \qquad t(x) \leq 0{,}5 \;\forall x \in S_B$$
na listu
Metoda momenta
$$\triangle\hat{w}_{\text{nov}}(k) = \triangle\hat{w}(k) + \alpha\,\triangle\hat{w}(k-1), \qquad \alpha \in [0,1]$$
💡 Odvod sigmoide — ni na listu, a ga vedno potrebuješ

$\dfrac{df}{ds} = f(s)\big(1-f(s)\big) = y(1-y)$. Pri linearni $f(s)=s$ je odvod 1.

10. Samoorganizirajoče se mreže

na listu
Obteženi vhod in izhod
$$s_r(t) = \sum_j w_{rj}(t)x_j(t) + \sum_k \gamma_{rk}y_k(t) \qquad\qquad y_r(t+\triangle) = \lambda_r\big(s_r(t)\big)$$
na listu
Pravilo Hebba in normalizacija
$$w_{r,\text{nov}}(t) = w_{r,\text{star}}(t) + \epsilon(t)y_r(t)x(t) \qquad\qquad \sum_j w_{rj} = 1$$
na listu
Ekvivalentni algoritem
$$d\big(w_s(t), x(t)\big) = \min_r d\big(w_r(t), x(t)\big)$$ $$w_r(t+1) = w_r(t) + g(r,s,t)\big(x(t)-w_r(t)\big)$$ $$g(r,s,t) = \epsilon(t)\cdot h(r,s,t), \qquad h(r,s,t) = e^{-\frac{d_L^2(u_r,u_s)}{\sigma^2(t)}}, \qquad \sigma(t) = \frac{\sigma_0}{\sqrt{1+t}}$$
na listu
Energija kvantizacijskega šuma
$$E_{\text{kvant\_šum}} = \frac{1}{N}\sum_{w_s}\sum_{x_i \in R_s}\|x_i - w_s\|^2$$

Česa na listu NI — in se moraš naučiti

⚠️ To je najbolj donosen del te strani

Vsak od spodnjih postopkov je na izpitu, a ga na listu ne najdeš.

PostopekNalogaKaj moraš znati
Pretvorba napetosti v sivino1$g = \frac{U-U_{\min}}{U_{\max}-U_{\min}}\cdot Q$, napetosti nad $U_{\max}$ se porežejo
Označevanje regij8Cel algoritem: pregled levo→desno navzdol, že pregledani sosedi, nova oznaka le če noben ni objekt
Sledenje notranji meji10Cel algoritem: dir = 7, (dir+7) mod 8 pri lihem, proti urna smer, štetje od $p_0$
Postopki tvorjenja statičnega ozadja13Tri variante; še posebej postopek 2 (izloči odstopajoče, nato povpreči)
Uteženo težišče pri 3 kamerah16$P = \frac{\sum w_iP_i}{\sum w_i}$; »2× natančnejša« pomeni utež 2
Pretvorba disparitete v metre17$d_{[\text{m}]} = d_{[\text{px}]} / \text{ločljivost}_{[\text{px/m}]}$
Pravilo (k, l) najbližjih sosedov20Pogledaš $k$ najbližjih; razred zmaga, če jih ima vsaj $l$; sicer nerazvrščljivo
Metoda izpusti enega — postopek21Po vsakem izpustu preračunaj tipičnega predstavnika razreda
Linearna ločljivost / XOR22En nevron ne more rešiti XOR — preveri, preden računaš
Odvod sigmoide22, 23$f'(s) = y(1-y)$
Kdaj je prispevek k E enak nič23Pri dvojnem pragu: $y_3 \geq a$ (za A) oz. $y_3 \leq b$ (za B) → prispevek 0
$d_L$ se meri v rešetki24Po indeksih vrstice/stolpca nevronov, ne med vektorjema uteži
Prenosna funkcija ne vpliva na zmagovalca25V ekvivalentnem algoritmu šteje samo $d(w, x)$

Originalni list s formulami

Za primerjavo — kako izgleda list, ki ga dobiš na izpitu:

Del 1 (2 strani) in Del 2 (2 strani)

Datoteke so v mapi formule/ tvojega projekta: URVRV_formule_2024_del1 (1).pdf in URVRV_formule_2024_del2 (1).pdf. Odpri ju ob tej strani — zgoraj so iste formule, le razložene in urejene po poglavjih.