Chambolle–Pock algorithm: Difference between revisions

Revision as of 06:23, 3 December 2023

Revision as of 08:21, 13 December 2024

Line 11:

| caption2 = Example of application of the Chambolle-Pock algorithm to image reconstruction.

}}

In [[mathematics]], the '''Chambolle-Pock algorithm''' is an [[algorithm]] used to solve [[convex optimization]] problems. It was introduced by Antonin Chambolle and Thomas Pock<ref name=":0">{{Cite journal |last1=Chambolle |first1=Antonin |last2=Pock |first2=Thomas |date=2011-05-01 |title=A First-Order Primal-Dual Algorithm for Convex Problems with Applications to Imaging |url=https://doi.org/10.1007/s10851-010-0251-1 |journal=Journal of Mathematical Imaging and Vision |language=en |volume=40 |issue=1 |pages=120–145 |doi=10.1007/s10851-010-0251-1 |bibcode=2011JMIV...40..120C |s2cid=207175707 |issn=1573-7683}}</ref> in 2011 and has since become a widely used method in various fields, including [[Digital image processing|image processing]],<ref name=":1" /><ref name=":2" /><ref name=":3" /> [[computer vision]],<ref>{{Cite book |last1=Pock |first1=Thomas |last2=Cremers |first2=Daniel |last3=Bischof |first3=Horst |last4=Chambolle |first4=Antonin |title=2009 IEEE 12th International Conference on Computer Vision |chapter=An algorithm for minimizing the Mumford-Shah functional |date=2009 |chapter-url=https://ieeexplore.ieee.org/document/5459348 |pages=1133–1140 |doi=10.1109/ICCV.2009.5459348|isbn=978-1-4244-4420-5 |s2cid=15991312 }}</ref> and [[signal processing]].<ref>{{Cite journal |date=2014 |title=A Generic Proximal Algorithm for Convex Optimization—Application to Total Variation Minimization |url=https://ieeexplore.ieee.org/document/6810809 |journal=IEEE Signal Processing Letters |volume=21 |issue=8 |pages=985–989 |doi=10.1109/LSP.2014.2322123 |bibcode=2014ISPL...21..985. |s2cid=8976837 |issn=1070-9908}}</ref>

The Chambolle-Pock algorithm is specifically designed to efficiently solve convex optimization problems that involve the minimization of a non-smooth [[Loss function|cost function]] composed of a data fidelity term and a regularization term.<ref name=":0" /> This is a typical configuration that commonly arises in ill-posed imaging [[Inverse problem|inverse problems]] such as [[image reconstruction]],<ref name=":1">{{Cite journal |last1=Sidky |first1=Emil Y |last2=Jørgensen |first2=Jakob H |last3=Pan |first3=Xiaochuan |date=2012-05-21 |title=Convex optimization problem prototyping for image reconstruction in computed tomography with the Chambolle–Pock algorithm |journal=Physics in Medicine and Biology |volume=57 |issue=10 |pages=3065–3091 |doi=10.1088/0031-9155/57/10/3065 |issn=0031-9155 |pmc=3370658 |pmid=22538474|arxiv=1111.5632 |bibcode=2012PMB....57.3065S }}</ref> [[Noise reduction|denoising]]<ref name=":2">{{Cite journal |last1=Fang |first1=Faming |last2=Li |first2=Fang |last3=Zeng |first3=Tieyong |date=2014-03-13 |title=Single Image Dehazing and Denoising: A Fast Variational Approach |url=http://epubs.siam.org/doi/10.1137/130919696 |journal=SIAM Journal on Imaging Sciences |language=en |volume=7 |issue=2 |pages=969–996 |doi=10.1137/130919696 |issn=1936-4954}}</ref> and [[inpainting]].<ref name=":3">{{Cite journal |last1=Allag |first1=A. |last2=Benammar |first2=A. |last3=Drai |first3=R. |last4=Boutkedjirt |first4=T. |date=2019-07-01 |title=Tomographic Image Reconstruction in the Case of Limited Number of X-Ray Projections Using Sinogram Inpainting |url=https://doi.org/10.1134/S1061830919070027 |journal=Russian Journal of Nondestructive Testing |language=en |volume=55 |issue=7 |pages=542–548 |doi=10.1134/S1061830919070027 |s2cid=203437503 |issn=1608-3385}}</ref>

Line 104:

| caption2 = Application of the Chambolle-Pock algorithm to the test image with noise.

}}

A typical application of this algorithm is in the image [[Noise reduction|denoising]] framework, based on total variation.<ref name=":2" /> It operates on the concept that signals containing excessive and potentially erroneous details exhibit a high total variation, which represents the integral of the absolute value gradient of the image.<ref name=":2" /> By adhering to this principle, the process aims to decrease the total variation of the signal while maintaining its similarity to the original signal, effectively eliminating unwanted details while preserving crucial features like edges. In the classical bi-dimensional discrete setting,<ref>{{Cite journal |last=Chambolle |first=Antonin |date=2004-01-01 |title=An Algorithm for Total Variation Minimization and Applications |url=https://doi.org/10.1023/B:JMIV.0000011325.36760.1e |journal=Journal of Mathematical Imaging and Vision |language=en |volume=20 |issue=1 |pages=89–97 |doi=10.1023/B:JMIV.0000011325.36760.1e |bibcode=2004JMIV...20...89C |issn=1573-7683 |s2cid=207622122}}</ref> consider <math>\mathcal{X} = \mathbb{R}^{NM}</math>, where an element <math> u\in\mathcal{X} </math> represents an image with the pixels values collocated in a Cartesian grid <math>N\times M</math>.<ref name=":0" />

Define the inner product on <math> \mathcal{X} </math> as<ref name=":0" />