3. Transformácia obrazu

3.1 Geometrické transformácie

Geometrické transformácie vypočítavajú súradnice bodu vo vstupnom obraze na základe súradníc bodu vo vstupnom obraze. Pre väčšinu úloh digitálneho spracovania obrazu stačia geometrické transformácie v rovine.
Vektorová funkcia T je geometrickou transformáciou, ktorá zobrazuje bod (x,y) do bodu (x₁,y₁) a je definovaná dvoma rovnicami:

                                                                                                            (1)

Kde T_x a T_y sú transformačné rovnice, ktoré môžu byť známe dopredu, alebo sa dajú vypočítať pomocou pôvodného a transformovaného bodu.
Geometrické transformácie sa skladajú z dvoch častí:

-         Transformácia súradníc, k bodu vo vstupnom obraze s diskrétnymi súradnicami sa nájde bod vo výstupnom obraze. Transformácia súradníc sa obvykle aproximuje polynómom  m-tého stupňa:

                                                                                      (2)

V praxi sa táto rovnica nahradzuje bilineárnou transformáciou, alebo afinnou transformáciou. Bilineárna transformácia má tvar:

                                                                           (3)

Na jeho určenie potrebujeme štyri dvojice vstupných a výstupných bodov.
Na určenie afinnej transformácie stačia tri dvojice bodov, a má tvar:

                                                                                      (4)

Pomocou homogénnych súradníc môžeme afinné transformácie vyjadriť v maticovom tvare:

                                                                             (5)

-         Aproximácia jasovej funkcie, výpočet najvhodnejšej jasovej hodnoty pre výstupný bod. Táto úloha sa rieši aproximáciou jasovej funkcie vo vstupnom obraze. Predpokladajme, že chceme  vypočítať hodnotu v celočíselnom bode (x1,y1) výstupného obrazu. Bod (x,y) vstupného obrazu, prislúchajúci k bodu (x1,y1) môžeme vypočítať inverznou transformáciou.

                                                                                       (6)

Bod (x,y) má reálne súradnice, ktoré sa nemusia zhodovať s celočíselným rastrom. Aby sme získali hodnotu jasu v bode (x,y), aproximujeme vstupnú obrazovú funkciu f(x,y).
Najznámejšie aproximačné metódy:

·        Metóda najbližšieho suseda priradí k bodu (x,y) hodnotu najbližšieho bodu v diskrétnej mriežke.

                                                   (7)

round() je zaokrúhlovacia  funkcia.
Chyba interpolačnej metódy je nanajvýš pól pixla. Táto chyba sa prejaví na líniách, ktoré sú natočené šikmo proti rastru, ktoré sú schodovité.

·        Lineárna interpolácia využije štyri okolné body na výpočet novej hodnoty. Vypočíta ju ako lineárnu kombináciu týchto bodov. Vplyv jednotlivých bodov je úmerný ich blízkosti k spracovanému bodu.

       (8)

kde x´ resp. y´ je dolná celá časť x resp. y,  Dx = x – x´  Dy = y – y´.
Tento vzťah môžeme zapísať aj maticovo:

      (9)

Táto metóda odstraňuje nedostatky predošlej metódy, ale v malej miere rozmazáva obraz.

·        Bikubická interpolácia,

3.1.1 Škálovanie

                                                                                                         (10)

kde s_x a s_y sú škálovacie faktory v jednotlivých smeroch. Ďalej uvádzam transformačnú maticu T v homogénnych súradniciach a maticu pre inverznú transformáciu.

                                          (11)

3.1.2 Otočenie

Otočenie o uhol j okolo bodu (x₀,y₀)

                                                      (12)

                                       (13)

3.1.3 Posunutie

 Posunutie o vektor (t_x,t_y)

                                                                                                      (14)

                                                   (15)

 Stredová súmernosť, nech (x₀,y₀) je stred súmernosti.

                                                                                                          (16)

                                     (17)

 Súmernosť podľa priamky, nech je priamka definovaná bodom (x₀,y₀) a uhlom j. Potom transformácia súmernosti podľa priamky je daná vzťahom:

                                     (18)

                              (19)

  Súmernosť podľa vertikálnej priamky p: x=x₀ je daná:

                                                                                                             (20)

Súmernosť podľa horizontálnej priamky p: y=y₀ je daná:

                                                                                                            (21)

 Skosenie, kde koeficienty SH_x, Sh_y udávajú mieru skosenia v smere osy x resp. osy y.

                                                                                               (22)
 

      (23)

3.2 Fourierová transformácia

3.2.1 Definície

Nech f(x) je spojitá integrovatelná funkcia reálnej premennej x. Fourierovú transformáciu funkcie f(x) definujeme, ako

                                                               (1)

Nech F(u) je integrovatelná funkcia, potom pre inverznú Fourierovú transformáciu platí:

                                                              (2)

Funkcia F(u) získaná Fourierovou transformáciou je komplexná funkcia. Môžeme ju zapísať v tvare

                                                                                                (3)

kde R(u) je reálna a I(u) je imaginárna zložka funkcie F(u).
Amplitúdové frekvenčné spektrum funkcie F(u) je

                                                                                         (4)

frekvenčné spektrum je

                                                                                                 (5)

a výkonové spektrum je

                                                                               (6)

Pripomeňme,  že výraz exp[-j2pux] podľa Eulerovej formuly môžeme rozpísať ako rozdiel cos a sin, z čoho vyplýva, že Fourierova transformácia patrí medzi goniometrické transformácie.

                                                                  (7)

Fourierovú transformáciu môžeme rozšíriť na dvojrozmernú. Nech f(x,y) je spojitá integrovatelná funkcia, a nech F(u,v) je integrovatelná potom platí:

                                               (8)

                                   (9)

Frekvenčné, fázové a výkonové spektrum môžeme definovať aj pre dvojrozmernú funkciu F(u,v):

                                                                               (10)

                                                                                          (11)

                                                                  (12)

  
Obrázok a amplitúdové frekvenčné spektrum Fourierovej transformácie.

Obraz je reprezentovaný diskrétnou obrazovou funkciou. Ak na obraze chceme aplikovať Fourierovú transformáciu, tak tiež musí byť v diskrétnom tvare. Jednorozmerná diskrétna Fourierová transformácia je definovaná rovnicou:

                                                                            (13)

pre u = 0, 1, ..., N-1.

Diskrétna inverzná Fourierova transformácia je definovaná vzťahom:

                                                                               (14)

pre x = 0, 1, ..., N-1.
V dvojrozmernom prípade platí:

                                                (15)

pre u = 0, 1, ..., M-1  a v = 0, 1, ..., N-1.

                                                   (16)

pre x = 0, 1, ..., M-1  a y = 0, 1, ..., N-1.
Kde M a N udávajú veľkosť obrazu.
Ak platí, že M = N, potom Fourierova transformácia má tvar:

                                                    (17)

pre u, v = 0, 1, ..., N-1

                                                       (18)

pre x,y = 0, 1, ..., N-1.
Frekvenčné, fázové a výkonové spektrum je definované ako v spojitom prípade, teda s rovnicami (4-6) pre jednorozmerný prípad a (10-12) pre dvojrozmerný prípad. Diskrétna Fourierová transformácia, na rozdiel  od spojitej, vždy existuje.    

3.2.2 Vlastnosti

Vlastnosti diskrétnej Fourierovej transformácie:

• oddeliteľnosť

                           (19)

                                 (20)

Účelom tejto vlastnosti je, že dvojrozmernú Fourierovú funkciu vieme vyjadriť dvoma jednorozmernými transformáciami.

                                                        (21)

                                                 (22)

V rovnici (22) máme jednorozmernú transformáciu pre v = 0, 1, ..., N-1. F(x,v) získame transformovaním každého riadku f(x,y). Výslednú funkciu F(u,v) získame jednorozmernou Fourierovou transformáciou z F(x,v) podľa (21).

·        Posunutie

                                        (23)

                                     (24)

Rovnica (23) znamená, že ak f(x,y) vynásobíme daným exponenciálnym výrazom, potom transformovaná funkcia bude posunutá o vektor (u₀,v₀). Rovnica (24) sa vzťahuje na inverznú transformáciu.
Posunutie nemá vplyv na magnitúdu:

                                                    (25)

Pri zobrazovaní Fourierovej transformácie sa používa posunutie u₀ = v₀ = N/2, ktorá posunie stred Fourierovej transformácie do stredu zobrazovaného okna. Pre toto posunutie platí:

a z (23) dostávame

.

• Periodicita

Diskrétna Fourierova transformácia má periódu N:

                               (26)

• Konjugovaná symetria (conjugate symetry)  

Ak f(x,y) je reálna, potom F(u,v) je konjugovane symetrická:

                                                                                    (27)

Pre frekvenčné spektrum platí:

                                                                                  (28)

Z vlastnosti symetrie vyplýva, že magnitúda transformácie je v bode (0, 0). Kvôli lepšej vizualizácie sa stred posúva do bodu (N/2, N/2).

• Transformácia zloženej funkcie

Pre funkcie f₁, f₂ platí:

                                       (29)

                                             (30)

nech a, b sú konštanty, potom platí:

                                                                                    (31)

                                                                            (32)

• Konvolúcia

Konvolúcia funkcií f(x,y) a g(x,y) je daná vzťahom

                                   (33)

Nech F(u,v) je Fourierovou transformáciou funkcie f(x,y) a nech G(u,v) je transformáciou g(x,y). Potom F(u,v).G(u,v) je Fourierovou transformáciou funkcie f(x,y)*g(x,y).

                                                             (34)

                                                             (35)

Rovnice (34), (35) sú známe ako konvolučné teorémy.

3.2.3 FFT - Rýchla Fourierová transformácia

Intuitívny algoritmus počítajúci diskrétnu Fourierovú transformáciu potrebuje čas rádovo N². Algoritmus FFT oproti tomu vystačí s časom NlogN. Princíp algoritmu uvedieme v jednorozmernom prípade. Pre dvojrozmerný prípad stačí využiť vlastnosť oddelitelnosti, rovnice (19) – (22).
Nech

                                                                                                   (36)

potom z (13) dostávame

                                                                                           (37)

Predpokladajme, že N = 2ⁿ, kde n je prirodzené číslo. Potom existuje prirodzené číslo M také, že N = 2M. Potom z (37) dostávame:

(38)

Pričom platí:

                                                                                                            (39)

Z (38) pomocou (39) dostávame:

                                      (40)

Definujme F_EVEN(u) a F_ODD(u)

                                                                                  (41)

                                                                              (42)

pre u = 0, 1, ..., M-1.
Po dosadení (41), (42) do (40) dostaneme

                                                                         (43)

pre u = 0, 1, ..., M-1.
Ďalej platí:

                                                                                                         (44)

Teda

                                                                 (45)

Ako výsledok dostávame, že na výpočet N bodovej transformácie prvých N/2 bodov vypočítame pomocou (43) a druhú polovicu pomocou (45). Na výpočet prvej polovice bodov potrebujeme vypočítať F_EVEN(u) a F_ODD(u) pre u = 0, 1, ..., N/2-1, ktoré môžeme využiť aj na výpočet druhej polovice bodov. Pri implementácií si treba uvedomiť, že vstupnú postupnosť je možné usporiadať tak, aby sme mohli ľahšie použiť (41), (42). Uvedieme jednoduchý príklad pre N = 8. Nech je vstupná postupnosť {f(0), f(1), ..., f(7)}. Rovnosť (41) využíva párne členy, {f(0),f(2),f(4),f(6)}, a (42) nepárne {f(1),f(3),f(5),f(7)}. Prvú postupnosť ďalej rozdeľujeme na {f(0), f(4)} a {f(2), f(6)}, druhú na {f(1), f(5)} a {f(3), f(7)}. Tieto postupnosti sa už ďalej nečlenia, lebo majú už len jeden párny a jeden nepárny člen. Výsledné usporiadanie postupnosti bude {f(0), f(4), f(2), f(6), f(1), f(5),f(3), f(7)}.  

Usporiadanie vstupnej postupnosti a metóda výpočtu FFT alg.

Našťastie toto usporiadanie môžeme ľahko zabezpečiť bit-reversom na argumente funkcie f. Nasledujúca tabulka ilustruje tento postup.