IMAGE COMPLETION WITH LOW-RANK MODEL APPROXIMATION METHODS

Tomasz Sadowski

tomasz.sadowski@pwr.edu.pl
Politechnika Wrocławska, Wydział Elektroniki (Poland)

Rafał Zdunek


Politechnika Wrocławska, Wydział Elektroniki (Poland)

Abstract

The paper is concerned with the task of reconstructing missing pixels in images perturbed with impulse noise in a transmission channel. Such a task can be formulated in the context of image interpolation on an irregular grid or by approximating an incomplete image by low-rank factor decomposition models. We compared four algorithms that are based on the low-rank decomposition model: SVT, SmNMF-MC , FCSA-TC and SPC-QV. The numerical experiments are carried out for various cases of incomplete images, obtained by removing random pixels or regular grid lines from test images. The best performance is obtained if nonnegativity and smoothing constraints are imposed onto the estimated low-rank factors.


Keywords:

image completion, low-rank approximation, nonnegative matrix factorization, tensor decomposition, matrix completion

Ashikhmin M.: Synthesizing natural textures. I3D'01 Proceedings of the 2001 symposium on Interactive 3D graphics, 217–226, [doi: 10.1145/364338.364405].
  Google Scholar

Ballester C., Bertalm M., Caselles V., Sapiro G., Verdera .: Filling-in by joint interpolation of vector fields and gray levels. IEEE Transactions on Image Processing 8/2001, 1200–1211, [doi: 10.1109/83.935036].
  Google Scholar

Beck A., Teboulle M.: Fast Gradient-Based Algorithms for Constrained Total Variation Image Denoising and Deblurring Problems. IEEE Trans. Image Process. 11/2009, [doi: 10.1109/TIP.2009.2028250].
  Google Scholar

Bertalmio M., Sapiro G., Caselles V., Ballester C.: Image inpainting. SIGGRAPH'00 Proceedings of the 27th annual conference on Computer graphics and interactive techniques, 2000, 417–424, [doi: 10.1145/344779.344972].
  Google Scholar

Bertalmio M., Bertozzi A., Sapiro G.: Navier-Stokes, fluid dynamics, and image and video inpainting. CVPR 1, 2001, 355–362, [doi: 10.1109/CVPR.2001.990497].
  Google Scholar

Bertalmio M., Vese L., Sapiro G., Osher S.: Simultaneous structure and texture image inpainting. CVPR 8, 2003, 707–712, [doi: 10.1109/TIP.2003.815261].
  Google Scholar

Bonet J.: Multiresolution sampling procedure for analysis and synthesis of texture images. Computer Graphics, Annual Conference Series, 1997, 361–368, [doi: 10.1145/258734.258882].
  Google Scholar

Cai J.-F., Candes E., Shen Z.: A singular value thresholding algorithm for matrix completion. SIAM J. Optim 4/2010, 1956–1982, [doi: 10.1137/080738970].
  Google Scholar

Chan T., Shen J.: Non-texture inpaintings by curvature-driven diffusions. J. Visual Comm. Image Rep. 4/2001, 436–449, [doi: 10.1006/jvci.2001.0487].
  Google Scholar

Chen Y-L., Hsu C.-T., Liao H.-Y.: Simultaneous tensor decomposition and completion using factor priors. IEEE Transactions on Pattern Analysis and Machine Intelligence 3/2014, 577–591, [doi: 10.1109/TPAMI.2013.164].
  Google Scholar

Cichocki A., Zdunek R., Phan A., Amari S.: Nonnegative Matrix and Tensor Factorizations: Applications to Exploratory Multi-way Data Analysis and Blind Source Separation. Wiley and Sons, Chichester 2009.
  Google Scholar

Efros A., Leung T.: Texture synthesis by non-parametric sampling. Proc. IEEE Int. Conf. Comput. Vis., 1999, 1033–1038, [doi: 10.1109/ICCV.1999.790383].
  Google Scholar

Gandy S., Recht B., Yamada I.: Tensor completion and low-n-rank tensor recovery via convex optimization. Inverse Problems 27, 2011, 025010, [doi: 10.1088/0266-5611/27/2/025010].
  Google Scholar

Guo X., Ma Y.: Generalized Tensor Total Variation Minimization for Visual Data Recovery. IEEE Conference on Computer Vision and Pattern Recognition (CVPR) 2015, 3603–3611, [doi: 10.1109/CVPR.2015.7298983].
  Google Scholar

Han X., Wu J., Wang L., Chen Y.,Senhadji L., Shu H.: Linear Total Variation Approximate Regularized Nuclear Norm Optimization for Matrix Completion. Abstract & Applied Analysis 2014, 765782, [doi: 10.1155/2014/765782].
  Google Scholar

Heeger D., Bergen J.: Pyramid-based texture analysis/synthesis. SIGGRAPH'95 Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, 229–238, [doi: 10.1145/218380.218446].
  Google Scholar

Herman G.: Fundamentals of computerized tomography: Image reconstruction from projection (2nd edition). Springer, New York 2009.
  Google Scholar

Hertzmann A., Jacobs C., Oliver N., Curless B., Salesin D.: Image analogies. SIGGRAPH '01 Proceedings of the 28th annual conference on Computer graphics and interactive techniques, 327–340, [doi: 10.1145/383259.383295].
  Google Scholar

Huang J., Zhang, S., Dimitris Metaxas D.: Fast Optimization for Mixture Prior Models. Computer Vision – ECCV 2010. ECCV 2010. Lecture Notes in Computer Science 6313, 2010, 607–620, [doi: 10.1007/978-3-642-15558-1_44].
  Google Scholar

Ji H., Liu C., Shen Z., Xu Y.: Robust video denoising using low rank matrix completion. Proceedings of IEEE Conference on Computer Vision and Pattern Recognition (CVPR) 2010, 1791–1798, [doi: 10.1109/CVPR.2010.5539849].
  Google Scholar

Komodakis N., Tziritas G.: Image completion using global optimization. CVPR 2006, 442–452, [doi: 10.1109/CVPR.2006.141 ].
  Google Scholar

Kwatra V., Schödl A., Essa I., Turk G., Bobick A.: Graphcut textures: Image and video synthesis using graph cuts. SIGGRAPH 2003, 277–286, [doi: 10.1145/1201775.882264].
  Google Scholar

Levin A., Zomet A., Weiss Y.: Learning how to inpaint from global image statistics. Proc. 9th IEEE Int. Conf. Comput. Vis. 2003, 305–312, [doi: 10.1109/ICCV.2003.1238360].
  Google Scholar

Li W., Zhao L., Lin Z., Xu D., Lu D.: Non-local image inpainting using low-rank matrix completion. Computer Graphics Forum 2014, 111–122, [doi: 10.1111/cgf.12521].
  Google Scholar

Liang L., Liu C., Xu Y., Guo B., Shum H.: Real-time texture synthesis by patch-based sampling. ACM Tran. Graph. 3/2001, 127–150, [doi: 10.1145/501786.501787].
  Google Scholar

Liu J., Musialski P., Wonka P., Ye J.: Tensor completion for estimating missing values in visual data. IEEE Transactions on Pattern Analysis and Machine Intelligence 1/2013, 208–220, [doi: 10.1145/501786.501787]
  Google Scholar

Phan A., Cichocki A., Tichavsky P., Luta G., Brockmeier A.: Tensor Completion Through Multiple Kronecker Product Decomposition. ICASSP, 2013, 3233–3237, [doi: 10.1109/ICASSP.2013.6638255].
  Google Scholar

Portilla J., Simoncelli E.: A parametric texture model based on joint statistics of complex wavelet coefficients. IJCV, 1/2000, 49–70, [doi: 10.1023/A:1026553619983].
  Google Scholar

Roth S., Black M.: Fields of experts: A framework for learning image priors. Proc. IEEE Comput. Vis. Pattern Recog., 2005, 860–867, [doi: 10.1109/CVPR.2005.160].
  Google Scholar

Sikora J., Wójtowicz S. (eds): Industrial and Biological Tomography: Theoretical Basis and Applications. Wydawnictwo Książkowe Instytutu Elektrotechniki, Warszawa 2010.
  Google Scholar

Troyanskaya O., Cantor M., Sherlock G., Brown P., Hastie T., Tibshirani R., D. Botstein, Altman R.: Missing value estimation methods for DNA microarrays. Bioinformatics 6/2001, 520–525, [doi: 10.1186/1471-2105-7-32].
  Google Scholar

Wei L., Levoy M.: Fast texture synthesis using tree-structured vector quantization. SIGGRAPH'00 Proceedings of the 27th annual conference on Computer graphics and interactive techniques, 479–488, [doi: 10.1145/344779.345009].
  Google Scholar

Wu Q., Yu Y.: Feature matching and deformation for texture synthesis. ACM Trans. Graph. 3/2004, 364–367, [doi: 10.1145/1186562.1015730].
  Google Scholar

Yokota T., Zhao Q., Cichocki A.: Smooth PARAFAC Decomposition for Tensor Completion. IEEE Transactions on Signal Processing 64(20), 2016, 5423–5436, [doi: 10.1109/TSP.2016.2586759].
  Google Scholar

Zdunek R.: Nieujemna faktoryzacja macierzy i tensorów: zastosowanie do klasyfikacji i przetwarzania sygnałów. Oficyna Wydawnicza Politechniki Wrocławskiej, Wrocław 2014.
  Google Scholar

http://perception.csl.illinois.edu/matrix-rank/sample_code.html#MC, [25.04.2016].
  Google Scholar

http://ranger.uta.edu/~huang/R_LSI.htm, [25.04.2016].
  Google Scholar

https://sites.google.com/site/yokotatsuya/home/software/smooth-parafac-decomposition-for-tensor-completion, [25.04.2016].
  Google Scholar


Published
2017-12-21

Cited by

Sadowski, T., & Zdunek, R. (2017). IMAGE COMPLETION WITH LOW-RANK MODEL APPROXIMATION METHODS. Informatyka, Automatyka, Pomiary W Gospodarce I Ochronie Środowiska, 7(4), 44–48. https://doi.org/10.5604/01.3001.0010.7259

Authors

Tomasz Sadowski 
tomasz.sadowski@pwr.edu.pl
Politechnika Wrocławska, Wydział Elektroniki Poland

Authors

Rafał Zdunek 

Politechnika Wrocławska, Wydział Elektroniki Poland

Statistics

Abstract views: 192
PDF downloads: 83