SpringerLink
Log in

A Unified View on Patch Aggregation

  • Published:
Journal of Mathematical Imaging and Vision Aims and scope Submit manuscript

Abstract

Patch-based methods are widely used in various topics of image processing, such as image restoration or image editing and synthesis. Patches capture local image geometry and structure and are much easier to model than whole images: in practice, patches are small enough to be represented by simple multivariate priors. An important question arising in all patch-based methods is the one of patch aggregation. For instance, in image restoration, restored patches are usually not compatible, in the sense that two overlap** restored patches do not necessarily yield the same values to their common pixels. A standard way to overcome this difficulty is to see the values provided by different patches at a given pixel as independent estimators of a true unknown value and to aggregate these estimators. This aggregation step usually boils down to a simple average, with uniform weights or with weights depending on the trust we have on these different estimators. In this paper, we propose a probabilistic framework aiming at a better understanding of this crucial and often neglected step. The key idea is to see the aggregation of two patches as a fusion between their models rather than a fusion of estimators. The proposed fusion operation is pretty intuitive and generalizes previous aggregation methods. It also yields a novel interpretation of the Expected Patch Log Likelihood (EPLL) proposed in Zoran and Weiss (in: 2011 IEEE international conference on computer vision (ICCV), 2011).

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
EUR 32.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or Ebook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Spain)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13
Fig. 14
Fig. 15

Similar content being viewed by others

Notes

  1. For example, patches of size l of a 1D-signal \(x=(x_1, \ldots , x_n)\) are of the form \((x_i,\ldots ,x_{i+l})\), for \(i\in \llbracket 1,n-l \rrbracket \).

  2. The precision matrix is the inverse of the covariance matrix.

References

  1. Aguerrebere, C., Almansa, A., Delon, J., Gousseau, Y., Musé, P.: A bayesian hyperprior approach for joint image denoising and interpolation, with an application to hdr imaging. IEEE Trans. Comput. Imaging 3(4), 633–646 (2017)

    Article  MathSciNet  Google Scholar 

  2. Aharon, M., Elad, M., Bruckstein, A.: \(K\)-SVD: an algorithm for designing overcomplete dictionaries for sparse representation. IEEE Trans. Signal Process. 54(11), 4311–4322 (2006)

    Article  Google Scholar 

  3. Buades, A., Coll, B., Morel, J.-M.: A review of image denoising algorithms, with a new one. Multiscale Model. Simul. 4(2), 490–530 (2005)

    Article  MathSciNet  Google Scholar 

  4. Carrera, D., Boracchi, G., Foi, A., Wohlberg, B.: Sparse overcomplete denoising: aggregation versus global optimization. IEEE Signal Process. Lett. 24(10), 1468–1472 (2017)

    Article  Google Scholar 

  5. Cho, T.S., Butman, M., Avidan, S., Freeman, W.T.: The patch transform and its applications to image editing. In: IEEE Conference on Computer Vision and Pattern Recognition, 2008. CVPR 2008. IEEE, pp. 1–8 (2008)

  6. Dabov, K., Foi, A., Katkovnik, V., Egiazarian, K.: Image denoising by sparse 3-d transform-domain collaborative filtering. IEEE Trans. Image Process. 16(8), 2080–2095 (2007)

    Article  MathSciNet  Google Scholar 

  7. Danielyan, A., Katkovnik, V., Egiazarian, K.: BM3D frames and variational image deblurring. IEEE Trans. Image Process. 21(4), 1715–1728 (2012)

    Article  MathSciNet  Google Scholar 

  8. Deledalle, C.-A., Duval, V., Salmon, J.: Non-local methods with shape-adaptive patches (NLM-SAP). J. Math. Imaging Vis. 43(2), 103–120 (2012)

    Article  MathSciNet  Google Scholar 

  9. Dengwen, Z., **aoliu, S.: Image denoising using weighted averaging. In: WRI International Conference on Communications and Mobile Computing, 2009. CMC’09. IEEE, vol. 1, pp. 400–403 (2009)

  10. Efros, A.A., Freeman, W.T.: Image quilting for texture synthesis and transfer. In: Proceedings of the 28th Annual Conference on Computer Graphics and Interactive Techniques, ACM, pp. 341–346 (2001)

  11. Efros, A.A., Leung, T.K.: Texture synthesis by non-parametric sampling. In: Computer Vision, 1999. IEEE, vol. 2, pp. 1033–1038 (1999)

  12. Elad, M., Aharon, M.: Image denoising via sparse and redundant representations over learned dictionaries. IEEE Trans. Image Process. 15(12), 3736–3745 (2006)

    Article  MathSciNet  Google Scholar 

  13. Elad, M., Milanfar, P.: Style transfer via texture synthesis. IEEE Trans. Image Process. 26(5), 2338–2351 (2017)

    Article  MathSciNet  Google Scholar 

  14. Feng, J., Song, L., Huo, X., Yang, X., Zhang, W.: An optimized pixel-wise weighting approach for patch-based image denoising. IEEE Signal Process. Lett. 22(1), 115–119 (2015)

    Article  Google Scholar 

  15. Frigo, O., Sabater, N., Delon, J., Hellier, P.: Split and match: example-based adaptive patch sampling for unsupervised style transfer. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 553–561 (2016)

  16. Guleryuz, O.G.: Weighted averaging for denoising with overcomplete dictionaries. IEEE Trans. Image Process. 16(12), 3020–3034 (2007)

    Article  MathSciNet  Google Scholar 

  17. HaCohen, Y., Shechtman, E., Goldman, D.B., Lischinski, D.: Non-rigid dense correspondence with applications for image enhancement. In: ACM Transactions on Graphics (TOG), ACM, vol. 30, pp. 70 (2011)

    Article  Google Scholar 

  18. Hoeting, J.A., Madigan, D., Raftery, A.E., Volinsky, C.T.: Bayesian model averaging: a tutorial. Stat. Sci. 382–401 (1999)

  19. Houdard, A., Bouveyron, C., Delon, J.: High-dimensional mixture models for unsupervised image denoising (HDMI). SIAM J. Imaging Sci. 11(4), 2815–2846 (2018)

    Article  MathSciNet  Google Scholar 

  20. Kervrann, C.: PEWA: Patch-based exponentially weighted aggregation for image denoising. In: Advances in Neural Information Processing Systems, pp. 2150–2158 (2014)

  21. Kervrann, C., Boulanger, J.: Optimal spatial adaptation for patch-based image denoising. IEEE Trans. Image Process. 15(10), 2866–2878 (2006)

    Article  Google Scholar 

  22. Kwatra, V., Essa, I., Bobick, A., Kwatra, N.: Texture optimization for example-based synthesis. ACM Trans. Gr. (ToG) 24(3), 795–802 (2005)

    Article  Google Scholar 

  23. Lebrun, M., Buades, A., Morel, J.-M.: A nonlocal bayesian image denoising algorithm. SIAM J. Imaging Sci. 6(3), 1665–1688 (2013)

    Article  MathSciNet  Google Scholar 

  24. Lebrun, M., Colom, M., Buades, A., Morel, J.-M.: Secrets of image denoising cuisine. Acta Numer. 21, 475–576 (2012)

    Article  MathSciNet  Google Scholar 

  25. Newson, A., Almansa, A., Fradet, M., Gousseau, Y., Pérez, P.: Video inpainting of complex scenes. SIAM J. Imaging Sci. 7(4), 1993–2019 (2014)

    Article  MathSciNet  Google Scholar 

  26. Paulino, I.F.R.: PACO: Signal restoration via patch consensus. ar**v preprint ar**v:1808.06942 (2018)

  27. Pierazzo, N., Morel, J.-M., Facciolo, G.: Multi-scale DCT denoising. Image Process. On Line 7, 288–308 (2017)

    Article  MathSciNet  Google Scholar 

  28. Raad, L., Desolneux, A., Morel, J.-M.: A conditional multiscale locally gaussian texture synthesis algorithm. J. Math. Imaging Vis. 56(2), 260–279 (2016)

    Article  MathSciNet  Google Scholar 

  29. Romano, Y., Elad, M.: Boosting of image denoising algorithms. SIAM J. Imaging Sci. 8(2), 1187–1219 (2015)

    Article  MathSciNet  Google Scholar 

  30. Roth, S., Lempitsky, V., Rother, C.: Discrete-continuous optimization for optical flow estimation. In: Statistical and Geometrical Approaches to Visual Motion Analysis, Springer, pp. 1–22 (2009)

  31. Salmon, J., Strozecki, Y.: From patches to pixels in non-local methods: Weighted-average reprojection. In: 2010 17th IEEE International Conference on Image Processing (ICIP). IEEE, pp. 1929–1932 (2010)

  32. Sezer, O.G., Altunbasak, Y.: Weighted average denoising with sparse orthonormal transforms. In: 2009 16th IEEE International Conference on Image Processing (ICIP), IEEE, pp. 3849–3852 (2009)

  33. Tabti, S., Deledalle, C-A., Denis, L., Tupin, F.: Modeling the distribution of patches with shift-invariance: application to SAR image restoration. In: 2014 IEEE International Conference on Image Processing (ICIP), IEEE, pp. 96–100 (2014)

  34. Talebi, H., Zhu, X., Milanfar, P.: How to SAIF-ly boost denoising performance. IEEE Trans. Image Process. 22(4), 1470–1485 (2013)

    Article  MathSciNet  Google Scholar 

  35. Teodoro, A.M., Almeida, M.S.C., Figueiredo, M.A.T.: Single-frame image denoising and inpainting using gaussian mixtures. In: ICPRAM (2), pp. 283–288 (2015)

  36. Van De Ville, D., Kocher, M.: SURE-based non-local means. IEEE Signal Process. Lett. 16(11), 973–976 (2009)

    Article  Google Scholar 

  37. Wang, Y.-Q., Morel, J.-M.: SURE guided Gaussian mixture image denoising. SIAM J. Imaging Sci. 6(2), 999–1034 (2013)

    Article  MathSciNet  Google Scholar 

  38. Guoshen, Y., Sapiro, G., Mallat, S.: Solving inverse problems with piecewise linear estimators: from Gaussian mixture models to structured sparsity. IEEE Trans. Image Process. 21(5), 2481–2499 (2012)

    Article  MathSciNet  Google Scholar 

  39. Zontak, M., Mosseri, I., Irani, M.: Separating signal from noise using patch recurrence across scales. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 1195–1202 (2013)

  40. Zoran, D., Weiss, Y.: From learning models of natural image patches to whole image restoration. In: 2011 IEEE International Conference on Computer Vision (ICCV), IEEE, pp. 479–486 (2011)

Download references

Acknowledgements

We would like to thank Arthur Leclaire and Pablo Arias for their insightful comments. We also would like to thank the three reviewers of this paper, whose comments and remarks have greatly helped to improve this work. This work has been partially funded by the French Research Agency (ANR) under Grant No ANR-14-CE27-001 (MIRIAM).

Author information

Authors and Affiliations

  1. MAP5, Université Paris Descartes, 12 Rue de l’École de Médecine, 75006, Paris, France

    Alexandre Saint-Dizier & Julie Delon

  2. Laboratoire J.A. Dieudonné, Université Côte d’Azur, Parc Valrose, 28 Avenue Valrose, 06108, Nice, France

    Charles Bouveyron

Authors
  1. Alexandre Saint-Dizier
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Julie Delon
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Charles Bouveyron
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Julie Delon.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Saint-Dizier, A., Delon, J. & Bouveyron, C. A Unified View on Patch Aggregation. J Math Imaging Vis 62, 149–168 (2020). https://doi.org/10.1007/s10851-019-00921-z

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10851-019-00921-z

Keywords

Search

Navigation