Patch Complexity, Finite Pixel Correlations and Optimal Denoising
Image restoration tasks are ill-posed problems, typically solved with priors. Since the optimal prior is the exact unknown density of natural images, actual priors are only approximate and typically restricted to small patches. This raises several questions: How much may we hope to improve current r...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Springer Nature
2021
|
| Online Access: | https://hdl.handle.net/1721.1/137556 |
| _version_ | 1826197740895338496 |
|---|---|
| author | Levin, Anat Nadler, Boaz Durand, Fredo Freeman, William T. |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Levin, Anat Nadler, Boaz Durand, Fredo Freeman, William T. |
| author_sort | Levin, Anat |
| collection | MIT |
| description | Image restoration tasks are ill-posed problems, typically solved with priors. Since the optimal prior is the exact unknown density of natural images, actual priors are only approximate and typically restricted to small patches. This raises several questions: How much may we hope to improve current restoration results with future sophisticated algorithms? And more fundamentally, even with perfect knowledge of natural image statistics, what is the inherent ambiguity of the problem? In addition, since most current methods are limited to finite support patches or kernels, what is the relation between the patch complexity of natural images, patch size, and restoration errors? Focusing on image denoising, we make several contributions. First, in light of computational constraints, we study the relation between denoising gain and sample size requirements in a non parametric approach. We present a law of diminishing return, namely that with increasing patch size, rare patches not only require a much larger dataset, but also gain little from it. This result suggests novel adaptive variable-sized patch schemes for denoising. Second, we study absolute denoising limits, regardless of the algorithm used, and the converge rate to them as a function of patch size. Scale invariance of natural images plays a key role here and implies both a strictly positive lower bound on denoising and a power law convergence. Extrapolating this parametric law gives a ballpark estimate of the best achievable denoising, suggesting that some improvement, although modest, is still possible. © 2012 Springer-Verlag. |
| first_indexed | 2024-09-23T10:52:43Z |
| format | Article |
| id | mit-1721.1/137556 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T10:52:43Z |
| publishDate | 2021 |
| publisher | Springer Nature |
| record_format | dspace |
| spelling | mit-1721.1/1375562022-09-27T15:38:18Z Patch Complexity, Finite Pixel Correlations and Optimal Denoising Levin, Anat Nadler, Boaz Durand, Fredo Freeman, William T. Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Image restoration tasks are ill-posed problems, typically solved with priors. Since the optimal prior is the exact unknown density of natural images, actual priors are only approximate and typically restricted to small patches. This raises several questions: How much may we hope to improve current restoration results with future sophisticated algorithms? And more fundamentally, even with perfect knowledge of natural image statistics, what is the inherent ambiguity of the problem? In addition, since most current methods are limited to finite support patches or kernels, what is the relation between the patch complexity of natural images, patch size, and restoration errors? Focusing on image denoising, we make several contributions. First, in light of computational constraints, we study the relation between denoising gain and sample size requirements in a non parametric approach. We present a law of diminishing return, namely that with increasing patch size, rare patches not only require a much larger dataset, but also gain little from it. This result suggests novel adaptive variable-sized patch schemes for denoising. Second, we study absolute denoising limits, regardless of the algorithm used, and the converge rate to them as a function of patch size. Scale invariance of natural images plays a key role here and implies both a strictly positive lower bound on denoising and a power law convergence. Extrapolating this parametric law gives a ballpark estimate of the best achievable denoising, suggesting that some improvement, although modest, is still possible. © 2012 Springer-Verlag. 2021-11-05T18:13:34Z 2021-11-05T18:13:34Z 2012 2019-05-28T15:16:32Z Article http://purl.org/eprint/type/ConferencePaper 0302-9743 1611-3349 https://hdl.handle.net/1721.1/137556 Levin, Anat, Nadler, Boaz, Durand, Fredo and Freeman, William T. 2012. "Patch Complexity, Finite Pixel Correlations and Optimal Denoising." en 10.1007/978-3-642-33715-4_6 Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Springer Nature other univ website |
| spellingShingle | Levin, Anat Nadler, Boaz Durand, Fredo Freeman, William T. Patch Complexity, Finite Pixel Correlations and Optimal Denoising |
| title | Patch Complexity, Finite Pixel Correlations and Optimal Denoising |
| title_full | Patch Complexity, Finite Pixel Correlations and Optimal Denoising |
| title_fullStr | Patch Complexity, Finite Pixel Correlations and Optimal Denoising |
| title_full_unstemmed | Patch Complexity, Finite Pixel Correlations and Optimal Denoising |
| title_short | Patch Complexity, Finite Pixel Correlations and Optimal Denoising |
| title_sort | patch complexity finite pixel correlations and optimal denoising |
| url | https://hdl.handle.net/1721.1/137556 |
| work_keys_str_mv | AT levinanat patchcomplexityfinitepixelcorrelationsandoptimaldenoising AT nadlerboaz patchcomplexityfinitepixelcorrelationsandoptimaldenoising AT durandfredo patchcomplexityfinitepixelcorrelationsandoptimaldenoising AT freemanwilliamt patchcomplexityfinitepixelcorrelationsandoptimaldenoising |