Truncated Nuclear Norm Minimization for HDR Imaging
Abstract
Matrix completion is a rank minimization problem to recover a low-rank data matrix from a small subset of its entries. Since the matrix rank is nonconvex and discrete, many existing approaches approximate the matrix rank as the nuclear norm. However, the truncated nuclear norm is known to be a better approximation to the matrix rank than the nuclear norm, exploiting a priori target rank information about the problem in rank minimization. In this work, we propose a computationally efficient truncated nuclear norm minimization algorithm for matrix completion, which we call TNNM-ALM. We reformulate the original optimization problem by introducing slack variables and considering noise in the observation. The central contribution of this work is to solve it efficiently via the augmented Lagrange multiplier (ALM) method, where the optimization variables are updated by closed-form solutions.We apply the proposed TNNMALM algorithm to ghost-free high dynamic range (HDR) imaging by exploiting the low-rank structure of irradiance maps from low dynamic range (LDR) images. Experimental results on both synthetic and real visual data show that the proposed algorithm achieves significantly lower reconstruction errors and superior robustness against noise than the conventional approaches, while providing substantial improvement in speed, thereby applicable to a wide range of imaging applications.
Experimental Results
 |
Fig. 1. Comparison of normalized reconstruction errors for synthetic data with varying rank $r_0$ and observation ratio $|\Omega|/(mn)$. (a) OptSpace [1], (b) LMaFit [2], (c) IALM-MC [3], (d) TNNR-ADMM [4], (e) IRNN-TNN [5], (f) PSSV-MC [6], and (g) TNNM-ALM. The color magnitude represents the normalized reconstruction error.
 |
Fig. 2. Comparison of execution times for synthetic data with varying rank $r_0$ and observation ratio $|\Omega|/(mn)$. (a) OptSpace [1], (b) LMaFit [2], (c) IALM-MC [3], (d) TNNR-ADMM [4], (e) IRNN-TNN [5], (f) PSSV-MC [6], and (f) TNNM-ALM. The color magnitude represents the execution time in second.
 |
Fig. 3. Convergence behavior of TNNM-ALM. (a) Normalized reconstruction error and (b) stopping criterion.
 |
Fig. 4. Synthesized results of the SculptureGarden image set by (a) Heo et al.'s algorithm [7], (b) Hu et al.'s algorithm [8], (c) Lee et al.'s algorithm [9], (d) PSSV-RPCA [10], (e) PSSV-MC [6], and (f) the proposed algorithm.
 |
Fig. 5. Synthesized results of the Arch image set by (a) Heo et al.'s algorithm [7], (b) Hu et al.'s algorithm [8], (c) Lee et al.'s algorithm [9], (d) PSSV-RPCA [10], (e) PSSV-MC [6], and (f) the proposed algorithm.
 |
Fig. 6. Synthesized results of the AmusementPark image set at $\sigma = 20$. The images are synthesized by (a) Heo et al.'s algorithm [7], (b) Hu et al.'s algorithm [8], (c) Lee et al.'s algorithm [9], (d) PSSV-RPCA [10], (e) PSSV-MC [6], and (f) the proposed algorithm.
Table 1. The computation times of Heo et al.'s algorithm [7], Hu et al.'s algorithm [8], Lee et al.'s algorithm [9], PSSV-RPCA [10], PSSV-MC [6], and the proposed algorithm for the test sets.
| Heo et al. [7] | Hu et al. [8] | Lee et al. [9] | PSSV-RPCA [10] | PSSV-MC [6] | Proposed | |
| SculptureGarden | 390 | 392 | 91 | 40 | 149 | 52 |
| Arch | 303 | 232 | 154 | 37 | 200 | 51 |
References
R. H. Keshavan, A. Montanari, and S. Oh, “Matrix completion from a few entries,” IEEE Trans. Inf. Theory, vol. 56, no. 6, pp. 2980–2998, Jun. 2010.
Z. Wen, W. Yin, and Y. Zhang, “Solving a low-rank factorization model for matrix completion by a nonlinear successive over-relaxation algorithm,” Math. Program. Comput., vol. 4, no. 4, pp. 333–361, Dec. 2012.
Z. Lin, M. Chen, L. Wu, and Y. Ma, “The augmented Lagrange multiplier method for exact recovery of corrupted low-rank matrices,” University of Illinois, Urbana-Champaign, Tech. Rep. UILU-ENG-09-2215, Nov. 2009
Y. Hu, D. Zhang, J. Ye, X. Li, and X. He, “Fast and accurate matrix completion via truncated nuclear norm regularization,” IEEE Trans. Pattern Anal. Mach. Intell., vol. 35, no. 9, pp. 2117–2130, Sep. 2013.
C. Lu, J. Tang, S. Yan, and Z. Lin, “Generalized nonconvex nonsmooth low-rank minimization,” in Proc. IEEE Conf. Comput. Vis. Pattern Recognit., Jun. 2014, pp. 4130–4137.
T.-H. Oh, Y.-W. Tai, J.-C. Bazin, H. Kim, and I. S. Kweon, “Partial sum minimization of singular values in robust PCA: Algorithm and applications,” IEEE Trans. Pattern Anal. Mach. Intell., vol. 38, no. 4, pp. 744–758, Apr. 2016.
Y. S. Heo, K. M. Lee, S. U. Lee, Y. Moon, and J. Cha, “Ghost-free high dynamic range imaging,” in Proc. Asian Conf. Comput. Vis., Nov. 2010, pp. 486–500.
J. Hu, O. Gallo, K. Pulli, and X. Sun, “HDR deghosting: How to deal with saturation?” in Proc. IEEE Conf. Comput. Vis. Pattern Recognit., Jun. 2013, pp. 1163–1170.
C. Lee, Y. Li, and V. Monga, “Ghost-free high dynamic range imaging via rank minimization,” IEEE Signal Process. Lett., vol. 21, no. 9, pp. 1045–1049, Sep. 2014.
T.-H. Oh, J.-Y. Lee, Y.-W. Tai, and I. S. Kweon, “Robust high dynamic range imaging by rank minimization,” IEEE Trans. Pattern Anal. Mach. Intell., vol. 37, no. 6, pp. 1219–1232, Jun. 2015.
Publication
Chul Lee and Edmund Y. Lam, “Computationally efficient truncated nuclear norm minimization for high dynamic range imaging,” IEEE Transactions on Image Processing, vol. 25, no. 9, pp. 4145–4157, Sep. 2016.