Lineární algebra rekonstrukce obrazu

Lineární algebra rekonstrukce obrazu Prezentace práce pro matematický seminář

Matyáš „

´T 0

Mdx” Theuer

20. října 2011

´ Matyáš „ 0T Mdx” Theuer

()

Lineární algebra rekonstrukce obrazu

20. října 2011

1 / 19

Obsah

Matematická reprezentace obrazu


()


20. října 2011

2 / 19

Obsah

Matematická reprezentace obrazu Popis lineárního modelu rozostření


()


20. října 2011

2 / 19

Obsah

Matematická reprezentace obrazu Popis lineárního modelu rozostření Odvození a realizace vybraných metod


()


20. října 2011

2 / 19

Obsah

Matematická reprezentace obrazu Popis lineárního modelu rozostření Odvození a realizace vybraných metod Testování na příkladech


()


20. října 2011

2 / 19

Obsah

Matematická reprezentace obrazu Popis lineárního modelu rozostření Odvození a realizace vybraných metod Testování na příkladech Současná práce


()


20. října 2011

2 / 19



()


20. října 2011

3 / 19


   f (x, y ) =  

f (1, 1) f (2, 1) .. . f (m, 1)


f (1, 2) f (2, 2) .. . f (m, 2)

()

··· ··· .. . ···

f (1, n) f (2, n) .. . f (m, n)





    ⇒ X=  


x1,1 x2,1 .. . xm,1

x1,2 x2,2 .. . xm,2

··· ··· .. . ···

20. října 2011

x1,n x2,n .. . xm,n

    

3 / 19


   f (x, y ) =  

f (1, 1) f (2, 1) .. . f (m, 1)

f (1, 2) f (2, 2) .. . f (m, 2)

··· ··· .. . ···

f (1, n) f (2, n) .. . f (m, n)





    ⇒ X=  

x1,1 x2,1 .. . xm,1

x1,2 x2,2 .. . xm,2

··· ··· .. . ···

x1,n x2,n .. . xm,n

    

x = vec( X). ´ Matyáš „ 0T Mdx” Theuer

()


20. října 2011

3 / 19

Lineární model rozostření

Předpokládáme existenci přesného obrazu x


()


20. října 2011

4 / 19


Předpokládáme existenci přesného obrazu x Vlivem různých podmínek dochází k rozostření a vzniku neostrého obrazu b


()


20. října 2011

4 / 19


Předpokládáme existenci přesného obrazu x Vlivem různých podmínek dochází k rozostření a vzniku neostrého obrazu b Proces rozostření modelujeme jako násobení maticí A Ax = b


()


20. října 2011

4 / 19


Předpokládáme existenci přesného obrazu x Vlivem různých podmínek dochází k rozostření a vzniku neostrého obrazu b Proces rozostření modelujeme jako násobení maticí A Ax = b Ax + n = b


()


20. října 2011

4 / 19

Kvazi-Newtonovy metody


()


20. října 2011

5 / 19

Kvazi-Newtonovy metody Řešíme systém AT A x = AT b,


()


20. října 2011

5 / 19

Kvazi-Newtonovy metody Řešíme systém AT A x = AT b, jehož řešení odpovídá minimalizaci minf ( x) =


()

1 T T x A A x − xT A b, 2


20. října 2011

5 / 19

Kvazi-Newtonovy metody Řešíme systém AT A x = AT b, jehož řešení odpovídá minimalizaci minf ( x) =

1 T T x A A x − xT A b, 2

což vede k předpisu xk+1 = xk − αk M k gk = xk + αk M k rk


()


20. října 2011

5 / 19

Metody bez omezení Landweberova metoda α ∈ (0, 2ρ(AT A)−1 )


()


20. října 2011

6 / 19


Residual Norm Steepest Descent - RNSD αk = minα>0 f ( xk − α gk )


()


20. října 2011

6 / 19


Residual Norm Steepest Descent - RNSD αk = minα>0 f ( xk − α gk )


()


20. října 2011

6 / 19

Metody s omezením

Minimalizační úloha min f ( x),

x∈ΩB

kde ΩB = { x ∈ Rn : x ≥ 0}, f ( x) =


()

1 2

xT AT A x − xT A b.


20. října 2011

7 / 19

Metody s omezením

Minimalizační úloha min f ( x),

x∈ΩB

kde ΩB = { x ∈ Rn : x ≥ 0}, f ( x) =

1 2

xT AT A x − xT A b.

Projekce Nechť je ΩB je neprázdná konvexní podmnožina euklidovského prostoru Rn a x prvkem tohoto prostoru. Projekce PΩB ( x) do ΩB je dána [PΩB ( x)]i = max{0, xi }, i = 1, 2, ..., n


()


20. října 2011

7 / 19

Metody s omezením FSGP

Fixed Steplength Gradient Projection - FSGP α ∈ (0, 2ρ(AT A)−1 ) xk+1 = PΩB ( xk − α gk )


()


20. října 2011

8 / 19

Metody s omezením FSGP

Fixed Steplength Gradient Projection - FSGP α ∈ (0, 2ρ(AT A)−1 ) xk+1 = PΩB ( xk − α gk )


()


20. října 2011

8 / 19

Metody s omezením RNSDP

Residual Norm Steepest Descent with Projection - RNSDP


()


20. října 2011

9 / 19


Residual Norm Steepest Descent with Projection - RNSDP αBO - ideální délka kroku bez omezení, která je stejná jako v případě RNSD αBO = minα>0 f ( xk − αBO gk )


()


20. října 2011

9 / 19


Residual Norm Steepest Descent with Projection - RNSDP αBO - ideální délka kroku bez omezení, která je stejná jako v případě RNSD αBO = minα>0 f ( xk − αBO gk ) αO - délka omezeného kroku αO = min{ g >0

xi |i ∈ / A}, gi

je taková délka kroku ve směru − g, který by vedl právě na hranici.


()


20. října 2011

9 / 19


Residual Norm Steepest Descent with Projection - RNSDP αBO - ideální délka kroku bez omezení, která je stejná jako v případě RNSD αBO = minα>0 f ( xk − αBO gk ) αO - délka omezeného kroku αO = min{ g >0

xi |i ∈ / A}, gi

je taková délka kroku ve směru − g, který by vedl právě na hranici. αFS - pevná délka kroku αFS ∈ (0, 2ρ(AT A)−1 ) ´ Matyáš „ 0T Mdx” Theuer

()


20. října 2011

9 / 19



()


20. října 2011

10 / 19

Metody s omezením MRNSD

Modified Residual norm Steepest Descent - MRNSD x = ez


()


20. října 2011

11 / 19


Modified Residual norm Steepest Descent - MRNSD x = ez 1 minf ( x) = e z AT Ae z − e z A b 2


()


20. října 2011

11 / 19


Modified Residual norm Steepest Descent - MRNSD x = ez 1 minf ( x) = e z AT Ae z − e z A b 2 pro kterou platí:

∇f (z) =

x ∇f ( x)

Iterační předpis: xk+1 = xk − α xk ∇f ( x) ´ Matyáš „ 0T Mdx” Theuer

()


20. října 2011

11 / 19

Metody s omezením Konvergence


()


20. října 2011

12 / 19

Testování na příkladech Testovací data


()


20. října 2011

13 / 19

Testování na příkladech Výsledky

Obrázek: RNSDP a MRNSD


()


20. října 2011

14 / 19

Současná práce MPRGP - náhled

Modified Proportioning with Reduced Gradient Projections - MPRGP Je dáno 0

x ∈ Ω, αFS


()

T −1 ∈ 0, A A , Γ > 0,


20. října 2011

15 / 19



x ∈ Ω, αFS

T −1 ∈ 0, A A , Γ > 0,

pro k ≥ 0 a známé xk generujeme xk+1 podle následujících pravidel: Pokud je ν xk = 0: xk+1 = xk .


()


20. října 2011

15 / 19



x ∈ Ω, αFS

T −1 ∈ 0, A A , Γ > 0,

pro k ≥ 0 a známé xk generujeme xk+1 podle následujících pravidel: Pokud je ν xk = 0: xk+1 = xk . Pokud je xk strictly proportional a ν xk 6= 0, zkusíme generovat xk+1 jako conjugate gradient step. Pokud xk+1 ∈ Ω, přijmeme jej, jinak generujeme xk+1 pomocí expansion step.


()


20. října 2011

15 / 19



x ∈ Ω, αFS

T −1 ∈ 0, A A , Γ > 0,

pro k ≥ 0 a známé xk generujeme xk+1 podle následujících pravidel: Pokud je ν xk = 0: xk+1 = xk . Pokud je xk strictly proportional a ν xk 6= 0, zkusíme generovat xk+1 jako conjugate gradient step. Pokud xk+1 ∈ Ω, přijmeme jej, jinak generujeme xk+1 pomocí expansion step. Pokud xk není strictly proportional, provedeme proportioning, čímž získáme xk+1 . ´ Matyáš „ 0T Mdx” Theuer

()


20. října 2011

15 / 19

Současná práce MPRGP

MPRGP - Conjugate Gradient Step V každé iteraci testujeme podmínku

2 T

ϕ xk

β xk ≤ Γϕ˜ xk


()


20. října 2011

16 / 19



2 T

ϕ xk

β xk ≤ Γϕ˜ xk pokud je splněna, zkusíme conjugate gradient step xk+1 = xk − αCG pk , kde pk je směr sdružených gradientů, který je generován postupně. Generování začíná z ps = ϕ( xs ) kdykoli je xs získán z expansion step nebo proportioning step.


()


20. října 2011

16 / 19



2 T

ϕ xk

β xk ≤ Γϕ˜ xk pokud je splněna, zkusíme conjugate gradient step xk+1 = xk − αCG pk , kde pk je směr sdružených gradientů, který je generován postupně. Generování začíná z ps = ϕ( xs ) kdykoli je xs získán z expansion step nebo proportioning step. Pokud je xk+1 přípustné, přijmeme jej, jinak provedeme expansion step. ´ Matyáš „ 0T Mdx” Theuer

()


20. října 2011

16 / 19


MPRGP - Expansion Step Expansion step je krok s pevnou délkou a projekcí: xk+1 = PΩ ( xk − αFS ϕ( xk ))


()


20. října 2011

17 / 19


MPRGP - Expansion Step Expansion step je krok s pevnou délkou a projekcí: xk+1 = PΩ ( xk − αFS ϕ( xk )) Tento krok může rozšířit aktivní množinu.


()


20. října 2011

17 / 19



MPRGP - Proportioning Step Proportioning step je krok restartování sdružených gradientů: xk+1 = x − αCG β( xk )


()


20. října 2011

17 / 19



MPRGP - Proportioning Step Proportioning step je krok restartování sdružených gradientů: xk+1 = x − αCG β( xk ) Tento krok naopak odebírá indexy z aktivní množiny. ´ Matyáš „ 0T Mdx” Theuer

()


20. října 2011

17 / 19

Současná práce Aktuální stav


()


20. října 2011

18 / 19


Jednotlivé algoritmy jsem přepsal s využitím knihovny RestoreTools, kterou vyvíjí James Nagy a jeho tým.


()


20. října 2011

18 / 19


Jednotlivé algoritmy jsem přepsal s využitím knihovny RestoreTools, kterou vyvíjí James Nagy a jeho tým. Implementoval jsem MPRGP pro nesymetrické matice obrazu.


()


20. října 2011

18 / 19


Jednotlivé algoritmy jsem přepsal s využitím knihovny RestoreTools, kterou vyvíjí James Nagy a jeho tým. Implementoval jsem MPRGP pro nesymetrické matice obrazu. Nepodařilo se mi dosáhnout výrazného zlepšení předchozích algoritmů.


()


20. října 2011

18 / 19

Závěr

Otázky?


()


20. října 2011

19 / 19

Závěr

Otázky? Děkuji za pozornost


()


20. října 2011

19 / 19

Lineární algebra rekonstrukce obrazu

Recommend Documents