Diskretna Fourierova transformacija je ključna pri analizi in obdelavi slik, saj omogoča prepoznavanje struktur, odkrivanje vzorcev, filtriranje ter stiskanje slik. V tej nalogi se bomo osredotočili na zaznavanje robov, ki je osnovni postopek računalniškega vida in pogosto služi kot predpriprava za naprednejše naloge, kot je zaznavanje objektov na slikah.

Diskretna Fourierova transformacija

Diskretna Fourierova transformacija (DFT) preslika diskreten signal iz časovne domene v frekvenčno domeno:

X_n = \sum_{k=0}^{N-1} x_k \cdot e^{-i 2 \pi \frac{n}{N} k}, \quad n \in [0, N-1],

kjer je $x_k$ vrednost signala v časovni domeni, $X_n$ pa koeficient v frekvenčni domeni, ki vsebuje informacije o amplitudi in fazi posamezne frekvenčne komponente.

Obratno, inverzna diskretna Fourierova transformacija (IDFT) prevede signal nazaj iz frekvenčne domene v časovno:

x_k = \frac{1}{N} \sum_{n=0}^{N-1} X_n \cdot e^{i 2 \pi \frac{k}{N} n}, \quad k \in [0, N-1].

Dvodimenzionalna diskretna Fourierova transformacija in njen inverz

Dvodimenzionalna diskretna Fourierova transformacija (2D DFT) preslika 2D mrežo sivinskih vrednosti slike iz prostorske domene v frekvenčno domeno. Koeficienti v Fourierovi domeni predstavljajo jakost in pogostost gradnikov slike, podobno kot frekvence v zvočnem signalu izražajo višino tonov.

2D DFT je definirana kot:

F_{n,m} = \sum_{k=0}^{M-1} \sum_{l=0}^{N-1} f_{k,l} \cdot e^{-i 2 \pi \left(\frac{n}{N} k + \frac{m}{M} l\right)},

kjer $f_{k,l}$ predstavlja vrednost slikovne točke na koordinatah $(k,l)$ , $N$ je višina slike, $M$ širina, $F_{n,m}$ pa koeficient v frekvenčni domeni.

Izračun 2D DFT je možno razdeliti na zaporedje dveh 1D DFT:

F_{n,m} = \sum_{k=0}^{N-1} \left( \sum_{l=0}^{M-1} f_{k,l} \cdot e^{-i 2 \pi \frac{m}{M} l} \right) e^{-i 2 \pi \frac{n}{N} k},

kar omogoča učinkovito implementacijo s hitro Fourierovo transformacijo (FFT).

Obratna transformacija (2D IDFT) je definirana kot:

f_{k,l} = \frac{1}{NM} \sum_{n=0}^{N-1} \sum_{m=0}^{M-1} F_{n,m} \cdot e^{i 2 \pi \left(\frac{k}{N} n + \frac{l}{M} m\right)}.

Za lažjo analizo se koeficiente pogosto prestavi tako, da je DC komponenta na sredini slike, kar je običajno izvedeno s premikom (angl. shift) Fourierove transformiranke, na primer z numpy funkcijo roll.

Odstranjevanje anomalij v sliki

Po uporabi IDFT se lahko v izhodni sliki pojavijo kompleksne vrednosti, ker Fourierova transformacija uporablja kompleksna števila. Spreminjanje koeficientov v Fourierovi domeni (npr. z uporabo filtrov) lahko povzroči, da se imaginarne komponente prenesejo nazaj v prostorsko domeno. Dodatno se zaradi omejene natančnosti pri računanju lahko pojavijo napake, prav tako pa filtri lahko premaknejo vrednosti slikovnih točk izven dovoljenega območja $[0, 1]$ .

Za odpravo teh anomalij obdržimo le realni del slikovnih točk, imaginarni del zavržemo. Nato vrednosti omejimo na dovoljeni interval s funkcijo:

\text{clip}(f_{k,l}, a, b) = \begin{cases} a, & \text{če } f_{k,l} < a \\\\ f_{k,l}, & \text{če } a \leq f_{k,l} \leq b \\\\ b, & \text{če } f_{k,l} > b \end{cases}

V tem primeru nastavimo $a = 0$ in $b = 1$ , saj morajo intenzitete slikovnih točk ostati v intervalu $[0, 1]$ .

Visokoprepustni filter

Visokoprepustni filter (high-pass filter) odstrani počasne spremembe v sliki in ohrani hitre prehode, kot so robovi. Filter v Fourierovi domeni definiramo kot:

H_{n,m} = \begin{cases} 1, & \text{če} \ \left( \frac{n}{N} \right)^2 + \left( \frac{m}{M} \right)^2 \geq h^2 \\\\ 0, & \text{drugače} \end{cases}

Tukaj $n/N$ in $m/M$ predstavljata stopnjo spremembe v stolpcu oziroma vrstici, $h$ pa je prag, ki določa, katere frekvence ohranimo. Nizek prag ohrani več podrobnosti, visok prag poudari le izrazite robove.

Filter ima enake dimenzije kot slika ( $N \times M$ ) in je centriran v točki $\left( \left\lfloor \frac{N}{2} \right\rfloor , \left\lfloor \frac{M}{2} \right\rfloor \right)$ . Upoštevamo premik proti središču slike:

\left( \frac{n - \left\lfloor \frac{N}{2} \right\rfloor}{N} \right)^2 + \left( \frac{m - \left\lfloor \frac{M}{2} \right\rfloor}{M} \right)^2 \geq h^2

Tako zgradimo filter za vse točke $n \in [0, N - 1]$ in $m \in [0, M - 1]$ .

Merjenje podobnosti med slikami

Pri filtriranju slike se del informacij izgubi. Podobnost med vhodno in obdelano sliko lahko ovrednotimo z medsebojno informacijo, ki meri, koliko informacije ostane po obdelavi. Večja vrednost pomeni večjo podobnost.

Medsebojna informacija med vhodno sliko $S_V$ in obdelano sliko $S_O$ je podana z:

I(S_V ; S_O) = H(S_V) + H(S_O) - H(S_V, S_O)

Verjetnosti za izračun entropije ocenimo iz histogramov sivinskih vrednosti. Slike običajno vsebujejo $G = 256$ odtenkov sive. Verjetnost, da ima točka v sliki $S_V$ sivino v intervalu $\left[\frac{v}{G}, \frac{v+1}{G}\right)$ , ocenimo z:

p_v = \frac{I_v}{\sum_{r=0}^{G - 1} I_r}

Na enak način določimo verjetnosti na obdelani sliki. Vezane verjetnosti, ki upoštevajo sočasno pojavitev sivinskih vrednosti na obeh slikah, so:

p_{v o} = \frac{I_{v o}}{\sum_{r=0}^{G - 1} \sum_{s=0}^{G - 1} I_{r s}}

kjer $I_{v o}$ predstavlja število točk, ki imajo sivino v intervalu $v$ na vhodni sliki in v intervalu $o$ na obdelani sliki.

Funkcija za detekcijo robov z uporabo Fourierove transformacije

Uvod

Funkcija detect_edges_fft implementira detekcijo robov z uporabo Fourierove transformacije in visokoprepustnega filtriranja. Vrne medsebojno informacijo med vhodno in obdelano sliko.

Uvoz knjižnice

import numpy as np

Za obdelavo slike in računanje Fourierove transformacije uporabimo knjižnico numpy.

Definicija funkcije

def detect_edges_fft(slika: np.array, prag: int) -> float:

Funkcija detect_edges_fft sprejme sivinsko sliko in prag za visokoprepustni filter ter vrne medsebojno informacijo med vhodno in obdelano sliko.

Dimenzije in normalizacija slike

N, M = slika.shape
slika = slika / 255.0

Določimo dimenzije slike in jo normaliziramo na interval $[0, 1]$ .

Fourierova transformacija in premik v središče

F = np.fft.fft2(slika)
x_center = N // 2
y_center = M // 2
F_shifted = np.roll(F, (x_center, y_center), (0, 1))

Izvedemo 2D diskretno Fourierovo transformacijo. Po transformaciji premaknemo počasne komponente iz robov v središče slike z uporabo funkcije np.roll.

Definicija visokoprepustnega filtra

filter_fft = np.zeros((N, M))
for n in range(N):
    for m in range(M):
        if ((((n - N // 2) / N) ** 2 + ((m - M // 2) / M) ** 2) >= prag ** 2):
            filter_fft[n][m] = 1

Zgradimo visokoprepustni filter velikosti slike. Pogoj:

$\left( \frac{n - \frac{N}{2}}{N} \right)^2 + \left( \frac{m - \frac{M}{2}}{M} \right)^2 \geq h^2$

ohrani hitre spremembe, počasne pa odstrani.

Filtriranje v Fourierovi domeni

F_shifted_filtered = F_shifted * filter_fft

Fourierovo predstavitev slike pomnožimo s filtrom, s čimer odstranimo počasne komponente.

Obraten premik Fourierove predstavitve

F_filtered = np.roll(F_shifted_filtered, (-x_center, -y_center), (0, 1))

Po filtriranju Fourierovo predstavitev premaknemo nazaj v začetni položaj.

Inverzna Fourierova transformacija

slika_obdelana = np.fft.ifft2(F_filtered)

Izvedemo inverzno Fourierovo transformacijo, da dobimo obdelano sliko v prostorski domeni.

Odstranjevanje anomalij

slika_obdelana = np.real(slika_obdelana)
slika_obdelana = np.clip(slika_obdelana, 0, 1)

Ohranimo le realne komponente in omejimo intenzitete slikovnih točk na interval $[0, 1]$ .

Entropija vhodne slike

G = 256
I_v, _ = np.histogram(slika.ravel(), bins=G, range=(0, 1))
total = N * M
P_v = I_v / total
P_v_nonzero = P_v[P_v > 0]
H_v = -np.sum(P_v_nonzero * np.log2(P_v_nonzero))

Izračunamo entropijo vhodne slike:

$H(S_V) = - \sum_{v} p_v \log_2 p_v$

pri čemer je $p_v$ verjetnost posamezne sivinske ravni.

Entropija obdelane slike

I_o, _ = np.histogram(slika_obdelana.ravel(), bins=G, range=(0, 1))
P_o = I_o / total
P_o_nonzero = P_o[P_o > 0]
H_o = -np.sum(P_o_nonzero * np.log2(P_o_nonzero))

Na enak način izračunamo entropijo obdelane slike:

$H(S_O) = - \sum_{o} p_o \log_2 p_o$

Vezana entropija

I_vo, _, _ = np.histogram2d(slika.ravel(), slika_obdelana.ravel(), bins=G, range=[[0, 1], [0, 1]])
P_vo = I_vo / total
P_vo_nonzero = P_vo[P_vo > 0]
H_vo = -np.sum(P_vo_nonzero * np.log2(P_vo_nonzero))

Izračunamo vezano entropijo:

$H(S_V, S_O) = - \sum_{v,o} p_{v o} \log_2 p_{v o}$

Medsebojna informacija

MI = H_v + H_o - H_vo
return MI

Končni rezultat je medsebojna informacija:

$I(S_V; S_O) = H(S_V) + H(S_O) - H(S_V, S_O)$

ki meri podobnost med vhodno in obdelano sliko.

Sklep

Predstavljena metoda za odkrivanje robov z diskretno Fourierovo transformacijo učinkovito izkorišča frekvenčni pristop k obdelavi slik. Ključne prednosti te metode vključujejo:

Globalni pristop: Fourierova transformacija omogoča obdelavo celotne slike naenkrat, za razliko od lokalnih metod, ki obdelujejo posamezne dele slike
Kontroliran način filtriranja: Visokoprepustni filter z nastavljenim pragom omogoča natančno kontrolo nad tem, katere frekvence ohranimo
Kvantitativno vrednotenje: Uporaba medsebojne informacije omogoča objektivno merjenje uspešnosti filtriranja

Metoda je posebej primerna za slike z izrazitimi robovi in strukurami, kjer frekvenčni pristop omogoča jasno ločevanje med počasnimi spremembami (ozadje) in hitrimi prehodi (robovi). Čeprav je računsko nekoliko zahtevnejša od enostavnih prostorskih filtrov, ponuja večjo fleksibilnost in boljši nadzor nad procesom filtriranja.

Odkrivanje robov v slikah z diskretno Fourierovo transformacijo