arrow
Volume 1, Issue 2
A Convex and Exact Approach to Discrete Constrained TV-L1 Image Approximation

Jing Yuan, Juan Shi & Xue-Cheng Tai

East Asian J. Appl. Math., 1 (2011), pp. 172-186.

Published online: 2018-02

Export citation
  • Abstract

We study the TV-L1 image approximation model from primal and dual perspective, based on a proposed equivalent convex formulations. More specifically, we apply a convex TV-L1 based approach to globally solve the discrete constrained optimization problem of image approximation, where the unknown image function $u(x)∈\{f_1 ,... , f_n\}$, $∀x ∈ Ω$. We show that the TV-L1 formulation does provide an exact convex relaxation model to the non-convex optimization problem considered. This result greatly extends recent studies of Chan et al., from the simplest binary constrained case to the general gray-value constrained case, through the proposed rounding scheme. In addition, we construct a fast multiplier-based algorithm based on the proposed primal-dual model, which properly avoids variability of the concerning TV-L1 energy function. Numerical experiments validate the theoretical results and show that the proposed algorithm is reliable and effective.

  • AMS Subject Headings

  • Copyright

COPYRIGHT: © Global Science Press

  • Email address
  • BibTex
  • RIS
  • TXT
@Article{EAJAM-1-172, author = {}, title = {A Convex and Exact Approach to Discrete Constrained TV-L1 Image Approximation}, journal = {East Asian Journal on Applied Mathematics}, year = {2018}, volume = {1}, number = {2}, pages = {172--186}, abstract = {

We study the TV-L1 image approximation model from primal and dual perspective, based on a proposed equivalent convex formulations. More specifically, we apply a convex TV-L1 based approach to globally solve the discrete constrained optimization problem of image approximation, where the unknown image function $u(x)∈\{f_1 ,... , f_n\}$, $∀x ∈ Ω$. We show that the TV-L1 formulation does provide an exact convex relaxation model to the non-convex optimization problem considered. This result greatly extends recent studies of Chan et al., from the simplest binary constrained case to the general gray-value constrained case, through the proposed rounding scheme. In addition, we construct a fast multiplier-based algorithm based on the proposed primal-dual model, which properly avoids variability of the concerning TV-L1 energy function. Numerical experiments validate the theoretical results and show that the proposed algorithm is reliable and effective.

}, issn = {2079-7370}, doi = {https://doi.org/10.4208/eajam.220310.181110a}, url = {http://global-sci.org/intro/article_detail/eajam/10902.html} }
TY - JOUR T1 - A Convex and Exact Approach to Discrete Constrained TV-L1 Image Approximation JO - East Asian Journal on Applied Mathematics VL - 2 SP - 172 EP - 186 PY - 2018 DA - 2018/02 SN - 1 DO - http://doi.org/10.4208/eajam.220310.181110a UR - https://global-sci.org/intro/article_detail/eajam/10902.html KW - Convex optimization, primal-dual approach, total-variation regularization, image processing. AB -

We study the TV-L1 image approximation model from primal and dual perspective, based on a proposed equivalent convex formulations. More specifically, we apply a convex TV-L1 based approach to globally solve the discrete constrained optimization problem of image approximation, where the unknown image function $u(x)∈\{f_1 ,... , f_n\}$, $∀x ∈ Ω$. We show that the TV-L1 formulation does provide an exact convex relaxation model to the non-convex optimization problem considered. This result greatly extends recent studies of Chan et al., from the simplest binary constrained case to the general gray-value constrained case, through the proposed rounding scheme. In addition, we construct a fast multiplier-based algorithm based on the proposed primal-dual model, which properly avoids variability of the concerning TV-L1 energy function. Numerical experiments validate the theoretical results and show that the proposed algorithm is reliable and effective.

Jing Yuan, Juan Shi & Xue-Cheng Tai. (1970). A Convex and Exact Approach to Discrete Constrained TV-L1 Image Approximation. East Asian Journal on Applied Mathematics. 1 (2). 172-186. doi:10.4208/eajam.220310.181110a
Copy to clipboard
The citation has been copied to your clipboard