Transformace obrazu. Pavel Strachota. 16. listopadu FJFI ČVUT v Praze

Interpolace

Geometrické transformace obrazu

Alpha-blending, warping, morphing

Transformace obrazu Pavel Strachota ˇ FJFI CVUT v Praze

16. listopadu 2012

Literatura

Interpolace



Obsah

1

Interpolace

2


3


Literatura

Interpolace



Obsah

1

Interpolace

2


3


Literatura

Interpolace



Literatura

Interpolace v 1D množina n diskrétních vzorku˚ hodnot funkce (signálu) f : [a, b] 7→ R na intervalu [a, b]: n o (xi , f (xi )) i ∈ Nn , xi ∈ [a, b] interpolace - konstrukce funkce ˜f : [a, b] 7→ R pouze ze znalosti (xi , f (xi )) tak, aby ˜f (xi ) = f (xi ) ∀i ∈ Nn význam: snaha rekonstruovat pˇribližnou hodnotu f (x) pro každé x ∈ [a, b] pomocí ˜f (x) aproximace - obecná rekonstrukce hodnot funkce f bez podmínky (1) Poznámka: Nn = { k ∈ Z| 0 ≤ k < n} = {0, 1, 2, . . . , n − 1}

(1)

Interpolace



Interpolace v 1D Interpolace nejbližším sousedem

ˇ jinak též po cástech konstantní interpolace ˇ obvykle ekvidistantní rozdelení intervalu xi = a + ih kde h=

(b − a) n−1

definujeme ˜f (x) = f (xi ) ! ! h h ∀x ∈ xi − , xi + ∩ [a, b] 2 2

Literatura

Interpolace




ˇ jinak též po cástech konstantní interpolace ˇ obvykle ekvidistantní rozdelení intervalu xi = a + ih kde h=

(b − a) n−1

definujeme ˜f (x) = f (xi ) ! ! h h ∀x ∈ xi − , xi + ∩ [a, b] 2 2

Literatura

Interpolace



Interpolace v 1D Lineární interpolace

dva sousední body spojeny úseˇckou

definujeme ˜f (x) = xi+1 − x f (xi ) + x − xi f (xi+1 ) xi+1 − xi xi+1 − xi ∀x ∈ [xi , xi+1 ]

Literatura

Interpolace



Interpolace v 1D Lineární interpolace

dva sousední body spojeny úseˇckou

definujeme ˜f (x) = f (xi ) + x − xi (f (xi+1 ) − f (xi )) xi+1 − xi ∀x ∈ [xi , xi+1 ]

Literatura

Interpolace



Literatura

Interpolace v 1D Polynomiální interpolace 1/2

úseˇckou mužeme ˚ interpolovat 2 body (lineární interpolace) n bodu˚ lze interpolovat polynomem L (x) stupneˇ n − 1 definujeme n Q

Φi (x) =

k =1 k ,i n Q

(x − xk ) , (xi − xk )

k =1 k ,i

potom Φi xj = δij Lagrangeuv ˚ interpolaˇcní polynom má potom tvar ˜f (x) = Ln (x) =

n X i=1

f (xi ) Φi (x)

Interpolace



Interpolace v 1D Polynomiální interpolace 2/2

Lagrangeuv ˚ polynom se nekonstruuje pˇrímo, ale efektivneˇ pomocí diferenˇcního schématu (viz Numerická matematika) extrémní hodnoty funkce ˜f (x) mohou ležet výrazneˇ mimo interval ! ) (x ) (x min f i , max f i i∈Nn

i∈Nn

=⇒ tzv. overshoot

Literatura

Interpolace



Interpolace v 1D Interpolace kubikou

kubika, kubický spline - kˇrivka popsaná parametricky: x = x (t), y = y (t) x (t), y (t) jsou polynomy 3. stupneˇ interpolace po segmentech (spojení každých dvou bodu) ˚ koeficienty polynomu˚ lze nalézt tak, aby výsledná kˇrivka ˇ napˇr. spojitou derivaci mela ! x˙ (t) y˙ (t) v bodech navazování segmentu˚ segment kˇrivky lze definovat pomocí tzv. rˇídících bodu˚ mezi ˇrídící body budou patˇrit i body [xi , f (xi )] detaily viz letní semestr, pˇrednáška Kˇrivky a plochy

Literatura

Interpolace




pravidelná mˇrížka s ˇ rozestupem (velikostí oka síte) h=1 vzorky funkce f (x, y ), tj. napˇr. hodnoty intenzity pixelu˚ [i, j]: fi,j = f (i, j)

interpolace: ˜f (x, y ) = fi,j ! ! 1 1 1 1 ∀ (x, y ) ∈ i − , i + × j − , j + 2 2 2 2

Literatura

Interpolace



Literatura

Interpolace v 2D Bilineární interpolace

separabilní procedura nejprve lineární interpolace ve ˇ osy x: smeru

fx,j

f0,1

fx ,1

f1,1

= fi,j + (x − i) fi+1,j − fi,j

fx,j+1 = fi,j+1

fx ,y = f˜(x , y )

+ (x − i) fi+1,j+1 − fi,j+1 poté lineární interpolace ˇ y získaných hodnot ve smeru

y

f0,0

˜f (x, y ) = fx,j + (y − j) fx,j+1 − fx,j

x , y ∈ [0, 1]

x

fx ,0

f1,0

Interpolace



Interpolace v 2D Bilineární interpolace

separabilní procedura nejprve lineární interpolace ve ˇ osy x: smeru

fx,j

= fi,j + (x − i) fi+1,j − fi,j

fx,j+1 = fi,j+1 + (x − i) fi+1,j+1 − fi,j+1 poté lineární interpolace ˇ y získaných hodnot ve smeru

˜f (x, y ) = fx,j + (y − j) fx,j+1 − fx,j

Literatura

Interpolace



Literatura

Interpolace v 2D Bikubická interpolace

interpolace bikubickou plochou mezi 4 body [i, j],[i + 1, j],[i, j + 1],[i + 1, j + 1] obecneˇ 3 3 X X ˜f (x, y ) = akl x k y l k =0 l=0

16 koeficientu˚ akl lze odvodit z 4 × 4 podmínek pro 4 krajní body rovnost funkˇcních hodnot ˜f (i, j) = f (i, j), ˜f (i + 1, j) = f (i + 1, j) atd. ˇ x: ∂x ˜f (i, j) = ∂x f (i, j), atd. rovnost derivací ve smeru ˇ y : ∂y ˜f (i, j) = ∂y f (i, j), atd. rovnost derivací ve smeru rovnost smíšených derivací: ∂2xy ˜f (i, j) = ∂2xy f (i, j), atd.

pokud derivace nejsou známy, lze je aproximovat koneˇcnými diferencemi

Interpolace



Interpolace v 2D

Bilineární interpolace

Bikubická interpolace

ˇ bikubická interpolace je nároˇcnejší, ale generuje hladší funkci

Literatura

Interpolace



Interpolace barev

neinterpolujeme skalární funkci, ale barvu ˇ scítat ˇ musíme umet barvy, násobit bravy skalárem barva má 3 parametry - lze uvažovat jako vektor s vektory pracujeme standardneˇ - po složkách vyjádˇrení v ruzných ˚ barevných prostorech + interpolace parametru˚ po složkách =⇒ ruzný ˚ výsledek viz pˇrednáška Vnímání a reprezentace barev

obvykle si vystaˇcíme s prostorem RGB

Literatura

Interpolace



Obsah

1

Interpolace

2


3


Literatura

Interpolace



Základní transformace ˇ zmena velikosti obrazu rotace zrcadlení

Dva zpusoby ˚ implementace transformace transformace obrazu˚ T : A 7→ B dopˇredné mapování: procházíme obrázek A pixelech, hledáme polohu transformovaného pixelu v obraze B (hledáme obraz bodu pˇri zobrazení T ) ˇ zpetné mapování: procházíme obrázek B po pixelech, hledáme polohu vzoru daného pixelu v obraze A pˇri zobrazení T =⇒ obvykle potˇrebujeme najít T −1

Literatura

Interpolace



Literatura

ˇ Zmena velikosti obrazu problémy: 1 ˇ se poˇcet pixelu˚ zmení 2

pixely mají po transformaci neceloˇcíselné souˇradnice

ˇrešení: 1

procházíme pouze pixely cílového obrazu - použijeme ˇ zpetné mapování

na puvodní ˚ obrázek A použijeme interpolaci =⇒ intenzita obrazu je definována všude ˇ interpolaˇcního algoritmu: výber 2

ˇ nejbližším sousedem - nejrychlejší, ale pˇri zvetšení je obraz kostrbatý, pˇri zmenšení se ztrácí tenké objekty (ˇcáry apod.) = aliasing ˇ ˇ bilineární - ve vetšin eˇ pˇrípadu˚ dostaˇcující, pˇri zvetšení rozmazává hrany bikubická - dostaˇcující hladkost, lépe zachovává hrany

Interpolace



Literatura

Rotace obrazu rotace o násobky 90◦ triviální ˇ rotace bodu kolem poˇcátku o úhel α proti smeru hodinových ruˇciˇcek x 0 = x cos α − ysinα y 0 = y cos α + xsinα ˇ zpetná transformace je otoˇcení o −α x

= x 0 cos α + y 0 sinα

y

= y 0 cos α − x 0 sinα

ˇ použijeme interpolaci opet ˇ „plátno“ než obraz rotovaný obraz se vejde na vetší puvodní ˚ ˇ plátna: pomocí rotace rohu˚ obrazu nutnost vypoˇcítat rozmer ˇ pˇri zpetném mapování nutnost ošetˇrit souˇradnice vzoru pixelu mimo obraz A

Interpolace



Obsah

1

Interpolace

2


3


Literatura

Interpolace



Prolnutí obrazu˚ alfa-míchání (alpha-blending) dvou obrazu˚ A1 , A2 do jednoho obrazu B lineární interpolace barev (intenzit) pixelu˚ na totožných pozicích B (i, j) = A1 (i, j) + α (A2 (i, j) − A1 (i, j)) parametr α je pruhlednost ˚ obrazu A2 (A1 je pozadí, A2 popˇredí): α = 0 =⇒ zcela pruhledný, ˚ α = 1 =⇒ nepruhledný ˚ v grafických akcelerátorech implementováno hardwaroveˇ prolnutí (cross dissolve) - animace sekvence n obrazu, ˚ kde k Bk (i, j) = A1 (i, j) + (A2 (i, j) − A1 (i, j)) n k = 0, 1, 2, . . . , n

Literatura

Interpolace



Alfa míchání

Literatura

Interpolace



Cross-dissolve efekt

Slideshow fotografií s efektem dissolve

Spustit video

Literatura

Interpolace



Literatura

Warping

deformace obrazu - nelineární transformace sít’ový warping - k obrazu je „pˇrilepena“ sít’. pohybem uzlových bodu˚ síteˇ deformujeme obraz v každém oku síteˇ zustává ˚ stále stejná cˇ ást obrázku vhodný pro globální deformace

ˇ úseckový warping (feature based warping) - místo síteˇ je v obraze množina nezávislých úseˇcek, které k sobeˇ váží své okolí ˇ pˇremístením úseˇcek deformujeme obraz ˇ pro lokální zmeny ˇ vhodnejší

Interpolace



Sít’ový warping na obraz položíme pomyslnou sít’ spojnice uzlových bodu˚ síteˇ mohou být pˇrímky, kubické kˇrivky (spliny) apod. ˇ zmeníme sít’ editací uzlových, resp. (v pˇrípadeˇ kˇrivek) ˇrídících bodu˚

Literatura

Interpolace



Literatura

Sít’ový warping Algoritmus

algoritmus je separabilní na dva kroky 1-2, 3-4: 1

urˇcíme pruseˇ ˚ cíky každého ˇrádku vstupního obrazu A s ˇ cˇ arami ve svislém smeru

2

ˇ získané intervaly se (lineárne) pˇrevzorkují na nový rozsah na modifikované síti =⇒ vznikne obraz B 0

3

4

urˇcíme pruseˇ ˚ cíky každého sloupce obrazu B 0 s cˇ arami ve ˇ vodorovném smeru získané intervaly pˇrevzorkujeme =⇒ vznikne výsledný obraz B

A

´ ı mapovan´

B′

Interpolace



Sít’ový warping Algoritmus

A

B′

Dvoupruchodové ˚ zpracování síteˇ

B

Literatura

Interpolace



Literatura

Úseˇckový warping Transformace jedním párem úseˇcek 1/2

ˇ používáme zpetné mapování bodu X v B na bod X 0 v A

A

B Q

úseˇcka PQ definuje v obraze B souˇradný systém:

Q

u - poloha XPQ podél úseˇcky škálovaná tak, že v bodeˇ P je u = 0, v bodeˇ Q je u = 1 v - vzdálenost od pˇrímky PQ

bod X 0 v A najdeme jako bod o souˇr. (u, v ) vzhledem k P 0 Q 0

′

XP′ ′ Q ′

X v

u P′

X′

v

XPQ u

P

Interpolace



Úseˇckový warping Transformace jedním párem úseˇcek 2/2

ˇ (Q − P) souˇradnice u: projekce vektoru (X − P) do smeru u=

(X − P) · (Q − P)

2

Q − P

analogicky souˇradnice v : v=

(X − P) · (Q − P)⊥

Q − P

kde vektor v ⊥ = (−y , x) je kolmý k vektoru v = (x, y ) souˇradnice bodu X 0 pak dostaneme snadno jako (Q 0 − P 0 )⊥

X 0 = P 0 + u (Q 0 − P 0 ) + v

Q 0 − P 0

X 0 nemá celoˇcíselné souˇradnice =⇒ interpolujeme

Literatura

Interpolace



Literatura

Úseˇckový warping Transformace více páry úseˇcek 1/4

transformace jedním párem úseˇcek: posunutí, rotace, ˇ ˇ rítka (afinní transformace) zmena meˇ více páru˚ úseˇcek =⇒ více bodu˚ X 0 je-li Xi0 vzor bodu X pˇri použití i-tého páru úseˇcek a D i = Xi0 − X je odpovídající posunutí bodu Xi0 , vypoˇcítáme n P

X0 = X +

n P

wi D i

i=1 n P i=1

, resp. pˇrímo X 0 = wi

wi Xi0

i=1 n P

,

wi

i=1

kde wi je váha i-tého bodu Xi0 závislá na vzdálenosti X od i-té úseˇcky

Interpolace



Literatura


A

B Q2 ′

Q1 Q1

u1

X1′

P1 ′

P2

v2

u2

′

P2 u1

X2′ u2

v2

v1 X

′

X

X

v1

P1 ′

Q2

Interpolace




váha wi se urˇcí jako b  0  Q − P 0 p  i i  , wi =  (a + di )  ˇ kde di je vzdálenost bodu X od úsecky Pi Qi , tj.    u ∈ [0, 1] |v |     di =  kP − X k u < 0  

  

Q − X

u > 1 a a, b, p jsou parametry zadané uživatelem

Literatura

Interpolace




parametr a > 0 urˇcuje vliv úseˇcky na nejbližší okolí. pokud a ≈ 0, váha bodu pˇrímo na úseˇcce je hodneˇ velká ˇ na bod na úseˇcce =⇒ bod na úseˇcce se zobrazí opet (pˇresná kontrola) ˇ pokud a bude vetší, warping bude hladší za cenu menší kontroly lze napˇr. a = 0.001.

parametr b urˇcuje rychlost slábnutí vlivu úseˇcky se vzdáleností vhodné je b ∈ [0.5, 2]

parametr p ∈ [0, 1] urˇcuje vliv délky úseˇcky na váhu p = 0 =⇒ stejný vliv nezávisle na délce ˇ vliv p = 1 =⇒ cˇ ím delší, tím silnejší

Literatura

Interpolace



Literatura

Úseˇckový warping ˇ úseˇcek Správné rozmístení

ˇ kˇrížit, jinak vzniknou artefakty úseˇcky by se nemely („bubliny“) - tzv. Ghostbustering effect Ghostbusters: - „Don’t cross the streams!“ - „Why?“ - „It would be bad.“

ˇ dotýkat pouze na koncích, a to v obou úseˇcky by se mely obrázcích pokud nechceme, aby se X 0 mapovalo i mimo zdrojový obraz, mužeme ˚ definovat páry úseˇcek na okrajích obrázku˚ A, B v opaˇcném pˇrípadeˇ dodefinujeme okolí obrázku A napˇr. cˇ ernou

Interpolace



Literatura

Úseˇckový warping ˇ úseˇcek Správné rozmístení

ˇ kˇrížit, jinak vzniknou artefakty úseˇcky by se nemely („bubliny“) - tzv. Ghostbustering effect Ghostbusters: - „Don’t cross the streams!“ - „Why?“ - „It would be bad.“

ˇ dotýkat pouze na koncích, a to v obou úseˇcky by se mely obrázcích pokud nechceme, aby se X 0 mapovalo i mimo zdrojový obraz, mužeme ˚ definovat páry úseˇcek na okrajích obrázku˚ A, B v opaˇcném pˇrípadeˇ dodefinujeme okolí obrázku A napˇr. cˇ ernou

Interpolace



Úseˇckový warping - pˇríklady

Spustit demo

Literatura

Interpolace




Spustit demo

Literatura

Interpolace




Spustit demo

Literatura

Interpolace




Spustit demo

Literatura

Interpolace




Spustit demo

Literatura

Interpolace




Spustit demo

Literatura

Interpolace



Literatura

Morphing ˇ pˇremena obrazu A v obraz B pomocí warpingu a prolnutí deformace obrazu obecneˇ popsána systémem ˇrídících ˇ bodu˚ (koncové body úseˇcek, uzlové body síte) m m v obrazech A, B systémy bodu˚ TA = piA , TB = piB i =1

Tvorba Mk (k -tého snímku animace), k = 0, 1, 2, . . . , n 1

2

3

Vytvoˇr systém Tk : ∀i lineárneˇ interpoluj souˇradnice ˇrídících bodu˚ k pik = piA + piB − piA n warpuj A 7→ MkA pˇrechodem od TA k Tk B 7→ MkB pˇrechodem od TB k Tk proved’ cross-dissolve Mk = MkA +

k B Mk − MkA n

i =1

Interpolace



Morphing - pˇríklady

ˇrídící body pro warping vymezují analogické objekty ve zdrojovém a cílovém obrázku ˇ eˇ obliˇceju: pˇri pˇremen ˚ oˇci, nos, ústa, uši, brada atd.

Video „Brangelina“

Spustit video

Video „Michael Jackson“

Spustit video

Video „Michael Jackson: Black or White“

Spustit video

Literatura

Interpolace



Literatura

T. Beier, S. Neely: Feature-based image metamorphosis. Computer graphics (SIGGRAPH ’92 Proceedings) (1992), 35-42. Žára, Beneš, Sochor, Felkel: Moderní poˇcítaˇcová grafika. Computer Press, 2005. ISBN: 80-251-0454-0

Literatura

Transformace obrazu. Pavel Strachota. 16. listopadu FJFI ČVUT v Praze

Recommend Documents