Regularizarea variației totale

Regularizarea la variația totală (cunoscută și sub denumirea de variație totală) este o metodă de reducere a zgomotului utilizată în procesarea digitală a imaginilor , bazată pe principiul că prezența zgomotului determină o creștere a variației totale a semnalului . Din acest motiv, o reducere a variației totale a unui semnal, efectuată sub constrângerea menținerii similarității cu semnalul original, poate fi utilizată pentru a elimina zgomotul și, în același timp, pentru a păstra conținut semnificativ. Metoda a fost introdusă de Rudin, Osher și Fatemi în 1992, motiv pentru care este cunoscută și ca model ROF . ^[1] ^[2]

Comparativ cu tehnicile de reducere a zgomotului, cum ar fi aplicarea unui filtru gaussian sau a unui filtru median , metoda are avantajul de a fi deosebit de eficientă în eliminarea zgomotului și, în același timp, păstrarea mai bună a contururilor, chiar și în cazul unui raport scăzut . / zgomot . ^[3]

Caz unidimensional

Exemplu unidimensional: semnalul original în gri, semnalul rezultat în negru ^[4]

Variația totală a unui semnal digital $y_{n}:\mathbb {N} \to \mathbb {R}$ ${\ displaystyle y_ {n}: \ mathbb {N} \ to \ mathbb {R}}$ ${\ displaystyle y_ {n}: \ mathbb {N} \ to \ mathbb {R}}$ poate fi exprimat ca

V(y)=\sum _{n}|y_{n+1}-y_{n}|.

{\ displaystyle V (y) = \ sum _ {n} | y_ {n + 1} -y_ {n} |.}

{\ displaystyle V (y) = \ sum _ {n} | y_ {n + 1} -y_ {n} |.}

Având un semnal $X$ ${\ displaystyle x}$ $X$ care conține o componentă de zgomot, scopul este de a determina un semnal $y$ ${\ displaystyle y}$ $y$ care este similar cu $X$ ${\ displaystyle x}$ $X$ dar cu variație totală minimă. Disimilitatea dintre semnale poate fi exprimată în sensul celor mai mici pătrate

\operatorname {E} (x,y)={\frac {1}{n}}\sum _{n}(x_{n}-y_{n})^{2}.

{\ displaystyle \ operatorname {E} (x, y) = {\ frac {1} {n}} \ sum _ {n} (x_ {n} -y_ {n}) ^ {2}.}

{\ displaystyle \ operatorname {E} (x, y) = {\ frac {1} {n}} \ sum _ {n} (x_ {n} -y_ {n}) ^ {2}.}

Problema devine atunci minimizarea funcționalității

\operatorname {E} (x,y)+\lambda V(y).

{\ displaystyle \ operatorname {E} (x, y) + \ lambda V (y).}

{\ displaystyle \ operatorname {E} (x, y) + \ lambda V (y).}

Abordarea utilizată inițial de către autori este de a diferenția funcționalul față de $y$ ${\ displaystyle y}$ $y$ și derivă o ecuație Euler-Lagrange corespunzătoare, care poate fi integrată numeric prin plasarea semnalului original $X$ ${\ displaystyle x}$ $X$ ca o condiție de graniță . ^[1] Alternativ, fiind funcțional convex , este posibil să se aplice metode de optimizare convexe pentru a determina o soluție optimă. ^[4]

Parametrul $\lambda$ ${\ displaystyle \ lambda}$ $\ lambda$ controlează regularizarea și joacă un rol fundamental. Cand $\lambda =0$ ${\ displaystyle \ lambda = 0}$ $\ lambda = 0$ nu există regularizare și problema este echivalentă doar cu cele mai mici pătrate și crește $\lambda$ ${\ displaystyle \ lambda}$ $\ lambda$ importanța termenului de regularizare crește și cerința de asemănare cu semnalul original este slăbită.

Caz bidimensional

Un caz obișnuit este cel al unui semnal digital bidimensional, cum ar fi o imagine digitală . Expresia variației totale propusă inițial de autori este

V(y)=\sum _{i,j}{\sqrt {|y_{i+1,j}-y_{i,j}|^{2}+|y_{i,j+1}-y_{i,j}|^{2}}}

{\ displaystyle V (y) = \ sum _ {i, j} {\ sqrt {| y_ {i + 1, j} -y_ {i, j} | ^ {2} + | y_ {i, j + 1 } -y_ {i, j} | ^ {2}}}}

{\ displaystyle V (y) = \ sum _ {i, j} {\ sqrt {| y_ {i + 1, j} -y_ {i, j} | ^ {2} + | y_ {i, j + 1 } -y_ {i, j} | ^ {2}}}}

care este o funcție izotropă și nediferențiată . Uneori se folosește o variantă anizotropă, deoarece poate fi mai ușor de optimizat

V_{\operatorname {aniso} }(y)=\sum _{i,j}{\sqrt {|y_{i+1,j}-y_{i,j}|^{2}}}+{\sqrt {|y_{i,j+1}-y_{i,j}|^{2}}}=\sum _{i,j}|y_{i+1,j}-y_{i,j}|+|y_{i,j+1}-y_{i,j}|.

{\ displaystyle V _ {\ operatorname {aniso}} (y) = \ sum _ {i, j} {\ sqrt {| y_ {i + 1, j} -y_ {i, j} | ^ {2}} } + {\ sqrt {| y_ {i, j + 1} -y_ {i, j} | ^ {2}}} = \ sum _ {i, j} | y_ {i + 1, j} -y_ { i, j} | + | y_ {i, j + 1} -y_ {i, j} |.}

{\ displaystyle V _ {\ operatorname {aniso}} (y) = \ sum _ {i, j} {\ sqrt {| y_ {i + 1, j} -y_ {i, j} | ^ {2}} } + {\ sqrt {| y_ {i, j + 1} -y_ {i, j} | ^ {2}}} = \ sum _ {i, j} | y_ {i + 1, j} -y_ { i, j} | + | y_ {i, j + 1} -y_ {i, j} |.}

Problema are încă forma

\min _{y}[\operatorname {E} (x,y)+\lambda V(y)],

{\ displaystyle \ min _ {y} [\ operatorname {E} (x, y) + \ lambda V (y)],}

{\ displaystyle \ min _ {y} [\ operatorname {E} (x, y) + \ lambda V (y)],}

unde este $ȘI$ ${\ displaystyle E}$ $ȘI$ este norma L2 printre semnale. Spre deosebire de cazul unidimensional, soluția acestei probleme de optimizare non-convexă este netivială. Pentru soluția sa se poate aplica metoda punctelor interne . ^[5]

Ecuația Rudin-Osher-Fatemi

În cazul general, dat un semnal $f$ ${\ displaystyle f}$ $f$ supus zgomotului, pentru a determina un semnal $tu$ ${\ displaystyle u}$ $tu$ cu zgomot redus, Rudin, Osher și Fatemi au propus următoarea problemă de optimizare ^[6]

\min _{u\in \operatorname {BV} (\Omega )}\;\|u\|_{\operatorname {TV} (\Omega )}+{\lambda  \over 2}\int _{\Omega }(f-u)^{2}\,dx

{\ displaystyle \ min _ {u \ in \ operatorname {BV} (\ Omega)} \; \ | u \ | _ {\ operatorname {TV} (\ Omega)} + {\ lambda \ over 2} \ int _ {\ Omega} (fu) ^ {2} \, dx}

{\ displaystyle \ min _ {u \ in \ operatorname {BV} (\ Omega)} \; \ | u \ | _ {\ operatorname {TV} (\ Omega)} + {\ lambda \ over 2} \ int _ {\ Omega} (fu) ^ {2} \, dx}

unde este ${\textstyle \operatorname {BV} (\Omega )}$ ${\ textstyle \ operatorname {BV} (\ Omega)}$ ${\ textstyle \ operatorname {BV} (\ Omega)}$ este setul de funcții cu variație mărginită a domeniului în $\Omega$ ${\ displaystyle \ Omega}$ $\Omega$ , ${\textstyle \operatorname {TV} (\Omega )}$ ${\ textstyle \ operatorname {TV} (\ Omega)}$ ${\ textstyle \ operatorname {TV} (\ Omega)}$ este modificarea totală a funcției în $\Omega$ ${\ displaystyle \ Omega}$ $\Omega$ Și ${\textstyle \lambda }$ ${\ textstyle \ lambda}$ ${\ textstyle \ lambda}$ este un coeficient de regularizare . De sine ${\textstyle u}$ ${\ textstyle u}$ ${\ textstyle u}$ este o funcție lină , variația totală este dată de

\|u\|_{\operatorname {TV} (\Omega )}=\int _{\Omega }\|\nabla u\|\,dx

{\ displaystyle \ | u \ | _ {\ operatorname {TV} (\ Omega)} = \ int _ {\ Omega} \ | \ nabla u \ | \, dx}

{\ displaystyle \ | u \ | _ {\ operatorname {TV} (\ Omega)} = \ int _ {\ Omega} \ | \ nabla u \ | \, dx}

unde este ${\textstyle \|\cdot \|}$ ${\ textstyle \ | \ cdot \ |}$ ${\ textstyle \ | \ cdot \ |}$ este norma euclidiană . Funcția obiectivă devine

\min _{u\in \operatorname {BV} (\Omega )}\;\int _{\Omega }\left[\|\nabla u\|+{\lambda  \over 2}(f-u)^{2}\right]\,dx

{\ displaystyle \ min _ {u \ in \ operatorname {BV} (\ Omega)} \; \ int _ {\ Omega} \ left [\ | \ nabla u \ | + {\ lambda \ over 2} (fu) ^ {2} \ dreapta] \, dx}

{\ displaystyle \ min _ {u \ in \ operatorname {BV} (\ Omega)} \; \ int _ {\ Omega} \ left [\ | \ nabla u \ | + {\ lambda \ over 2} (fu) ^ {2} \ dreapta] \, dx}

și, presupunând că nu există dependență de timp, este posibil să derivăm pentru această funcțională următoarea ecuație Euler-Lagrange , care este o ecuație diferențială parțială eliptică

{\begin{cases}\nabla \cdot \left({\nabla u \over {\|\nabla u\|}}\right)+\lambda (f-u)=0\quad &u\in \Omega \\{\partial u \over {\partial n}}=0\quad &u\in \partial \Omega .\end{cases}}

{\ displaystyle {\ begin {cases} \ nabla \ cdot \ left ({\ nabla u \ over {\ | \ nabla u \ |}} \ right) + \ lambda (fu) = 0 \ quad & u \ in \ Omega \\ {\ partial u \ over {\ partial n}} = 0 \ quad & u \ in \ partial \ Omega. \ End {cases}}}

{\ displaystyle {\ begin {cases} \ nabla \ cdot \ left ({\ nabla u \ over {\ | \ nabla u \ |}} \ right) + \ lambda (fu) = 0 \ quad & u \ in \ Omega \\ {\ partial u \ over {\ partial n}} = 0 \ quad & u \ in \ partial \ Omega. \ End {cases}}}

Notă

^ ^a ^b LI Rudin, S. Osher și E. Fatemi, algoritmi neliniari de variație totală bazată pe eliminarea zgomotului , în Physica D , vol. 60, 1-4, 1992, pp. 259-268, DOI : 10.1016 / 0167-2789 (92) 90242-f .
^ (EN) Modelul Rudin-Osher-Fatemi Captures Infinity and Beyond , de la IPAM, 15 aprilie 2019. Adus pe 4 august 2019.
^ D. Strong și T. Chan, proprietăți de păstrare a marginilor și proprietăți dependente de scară ale regularizării variației totale , în Inverse Problems , vol. 19, nr. 6, 2003, pp. S165 - S187, DOI : 10.1088 / 0266-5611 / 19/6/059 .
^ ^a ^b MA Little și Nick S. Jones, Sparse Bayesian Step-Filtering for High-Throughput Analysis of Molecular Machine Dynamics ( PDF ), în ICASSP 2010 Proceedings , 2010 IEEE International Conference on Acoustics, Speech and Signal Processing , 2010.
^ A. Chambolle,Un algoritm pentru minimizarea variației totale și aplicații , în Journal of Mathematical Imaging and Vision , vol. 20, 2004, pp. 89–97, DOI : 10.1023 / B: JMIV.0000011325.36760.1e .
^ Pascal Getreuer, Rudin - Osher - Fatemi Total Variation Denoising folosind Split Bregman ( PDF ), pe ipol.im , 2012.

Portal IT

Portalul de matematică

[rof92-1] LI Rudin, S. Osher și E. Fatemi, algoritmi neliniari de variație totală bazată pe eliminarea zgomotului , în Physica D , vol. 60, 1-4, 1992, pp. 259-268, DOI : 10.1016 / 0167-2789 (92) 90242-f .

[note2-2] (EN) Modelul Rudin-Osher-Fatemi Captures Infinity and Beyond , de la IPAM, 15 aprilie 2019. Adus pe 4 august 2019.

[strong-3] D. Strong și T. Chan, proprietăți de păstrare a marginilor și proprietăți dependente de scară ale regularizării variației totale , în Inverse Problems , vol. 19, nr. 6, 2003, pp. S165 - S187, DOI : 10.1088 / 0266-5611 / 19/6/059 .

[little10-4] MA Little și Nick S. Jones, Sparse Bayesian Step-Filtering for High-Throughput Analysis of Molecular Machine Dynamics ( PDF ), în ICASSP 2010 Proceedings , 2010 IEEE International Conference on Acoustics, Speech and Signal Processing , 2010.

[chambolle04-5] A. Chambolle,Un algoritm pentru minimizarea variației totale și aplicații , în Journal of Mathematical Imaging and Vision , vol. 20, 2004, pp. 89–97, DOI : 10.1023 / B: JMIV.0000011325.36760.1e .

[note1-6] Pascal Getreuer, Rudin - Osher - Fatemi Total Variation Denoising folosind Split Bregman ( PDF ), pe ipol.im , 2012.

[1]

[2]

[3]

[4]

[5]

[6]