IMAGE COMPLETION WITH LOW-RANK MODEL APPROXIMATION METHODS


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].

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].

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].

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].

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].

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].

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].

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].

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].

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].

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.

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].

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].

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].

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].

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].

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

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].

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].

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].

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

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].

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].

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].

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].

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]

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].

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].

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].

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

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].

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].

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

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].

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

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

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

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


Published : 2017-12-21


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

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