Periodic spline-based frames for image restoration

Previous Article
Stability and uniqueness for a two-dimensional inverse boundary value problem for less regular potentials
IPI Home
This Issue
Next Article
Determining a distributed conductance parameter for a neuronal cable model defined on a tree graph

August 2015, 9(3): 661-707. doi: 10.3934/ipi.2015.9.661

Periodic spline-based frames for image restoration

Amir Averbuch ^1, , Pekka Neittaanmäki ^2, and Valery Zheludev ^1,

1.	School of Computer Science, Tel Aviv University, Tel Aviv 69978, Israel, Israel
2.	Dept. of Mathematical Information Technology, Faculty of Information Technology, Agora, P.O. Box 35, FI-40014, University of Jyväskylä

Received November 2011 Revised July 2014 Published July 2015

Abstract
Related Papers

We present a design scheme that generates tight and semi-tight frames in discrete-time periodic signals space originated from four-channel perfect reconstruction periodic filter banks. Filter banks are derived from interpolating and quasi-interpolating polynomial and discrete splines. Each filter bank comprises one linear phase low-pass filter (in most cases interpolating) and one high-pass filter, whose magnitude's response mirrors that of a low-pass filter. These filter banks comprise two band-pass filters. We introduce local discrete vanishing moments (LDVM). When the frame is tight, analysis framelets coincide with their synthesis counterparts. However, for semi-tight frames, we swap LDVM between synthesis and analysis framelets. The design scheme is generic and it enables us to design framelets with any number of LDVM. The computational complexity of the the framelet transforms, which consists of calculating the forward and the inverse FFTs, does not depend on the number of LDVM and does depend on the size of the the impulse response filters. The designed frames are used for image restoration tasks, which were degraded by blurring, random noise and missing pixels. The images were restored by the application of the Split Bregman Iterations method. The frames performances are evaluated. A potential application of this methodology is the design of a snapshot hyperspectral imager that is based on a regular digital camera. All these imaging applications are described.

Keywords: vanishing moments, interpolating and quasi-interpolating polynomial, split Bregman iterations, tight and semi-tight frames, image restoration., Spline frames.

Mathematics Subject Classification: Primary: 65D07, 06D22, 42C40, 94A0.

Citation: Amir Averbuch, Pekka Neittaanmäki, Valery Zheludev. Periodic spline-based frames for image restoration. Inverse Problems and Imaging, 2015, 9 (3) : 661-707. doi: 10.3934/ipi.2015.9.661

References:

[1]	O. Amrani, A. Averbuch, T. Cohen and V. A. Zheludev, Symmetric interpolatory framelets and their error correction properties, International Journal of Wavelets, Multiresolution and Information Processing, 5 (2007), 541-566. doi: 10.1142/S0219691307001896.
[2]	A. Averbuch and V. Zheludev, Construction of biorthogonal discrete wavelet transforms using interpolatory splines, Applied and Comp. Harmonic Analysis, 12 (2002), 25-56. doi: 10.1006/acha.2001.0367.
[3]	A. Averbuch and V. Zheludev, Wavelet transforms generated by splines, International Journal of Wavelets, Multiresolution and Information Processing, 5 (2007), 257-291. doi: 10.1142/S0219691307001756.
[4]	A. Z. Averbuch, A. B. Pevnyi and V. A. Zheludev, Biorthogonal Butterworth wavelets derived from discrete interpolatory splines, IEEE Trans. on Sign. Proc., 49 (2001), 2682-2692. doi: 10.1109/78.960415.
[5]	A. Z. Averbuch, A. B. Pevnyi and V. A. Zheludev, Butterworth wavelet transforms derived from discrete interpolatory splines: Recursive implementation, Signal Processing, 81 (2001), 2363-2382.
[6]	A. Z. Averbuch, V. A. Zheludev and T. Cohen, Interpolatory frames in signal space, IEEE Trans. Sign. Proc., 54 (2006), 2126-2139. doi: 10.1109/TSP.2006.870562.
[7]	A. Z. Averbuch, V. A. Zheludev and T. Cohen, Tight and sibling frames originated from discrete splines, Sign. Proc. J., 86 (2006), 1632-1647. doi: 10.1016/j.sigpro.2005.09.007.
[8]	H. Bölcskei, F. Hlawatsch and H. G. Feichtinger, Frame-theoretic analysis of oversampled filter banks, IEEE Transactions on Sign. Proc., 46 (1998), 3256-3268.
[9]	C. K. Chui and W. He, Compactly supported tight frames associated with refinable functions, Applied and Comp. Harmonic Analysis, 8 (2000), 293-319. doi: 10.1006/acha.2000.0301.
[10]	C. K. Chui, W. He and J. Stöckler, Compactly supported tight and sibling frames with maximum vanishing moments, Applied and Comp. Harmonic Analysis, 13 (2002), 224-262. doi: 10.1016/S1063-5203(02)00510-9.
[11]	Z. Cvetković and M. Vetterli, Oversampled filter banks, IEEE Transactions on Signal Processing, 46 (1998), 1245-1255.
[12]	I. Daubechies, B. Han, A. Ron and Z. Shen, Framelets: Mra-based constructions of wavelet frames, Applied and Computational Harmonic Analysis, 14 (2003), 1-46. doi: 10.1016/S1063-5203(02)00511-0.
[13]	B. Dong and Z. Shen, Pseudo-splines, wavelets and framelets, Applied and Computational Harmonic Analysis, 22 (2007), 78-104. doi: 10.1016/j.acha.2006.04.008.
[14]	D. H. Foster, K. Amano, S. M. C. Nascimento and M. J. Foster, Frequency of metamerism in natural scenes, Journal of the Optical Society of America A, 23 (2006), 2359-2372.
[15]	T. Goldstein and S. Osher, The split {Bregman} method for l1-regularized problems, SIAM J. Imaging Sciences, 2 (2009), 323-343. doi: 10.1137/080725891.
[16]	M. Golub, M. Nathan, A. Averbuch, A. Kagan, V. A. Zheludev and R. Malinsky, Snapshot spectral imaging based on digital cameras, US Patent Application Publication Golub et al., No.13/762,560, US 2013/0194481 A1, 2013.
[17]	V. K. Goyal, J. Kovacevic and J. A. Kelner, Quantized frame expansions with erasures, Appl. and Comput. Harmonic Analysis, 10 (2001), 203-233. doi: 10.1006/acha.2000.0340.
[18]	V. K. Goyal, M. Vetterli and N. T. Thao, Quantized overcomplete expansions in $\mathbbR^n$: Analysis, synthesis and algorithms, IEEE Trans. on Information Theory, 44 (1998), 16-31. doi: 10.1109/18.650985.
[19]	B. Han, S. Song Goh and Z. Shen, Tight periodic wavelet frames and approximation orders, Applied and Computational Harmonic Analysis, 31 (2011), 228-248. doi: 10.1016/j.acha.2010.12.001.
[20]	C. Herley and M. Vetterli, Wavelets and recursive filter banks, IEEE Trans. Signal Proc., 41 (1993), 2536-2556. doi: 10.1109/78.229887.
[21]	J. Kovacevic, P. L. Dragotti and V. K. Goyal, Filter bank frame expansions with erasures, IEEE Trans. Inform, 48 (2002), 1439-1450. doi: 10.1109/TIT.2002.1003832.
[22]	A. V. Oppenheim and R. W. Schafer, Discrete-time Signal Processing, New York, Prentice Hall, 2010.
[23]	S. Osher, J. Cai, B. Dong and Z. Shen, Image restoration: Total variation, wavelet frames, and beyond, Journal of the American Mathematical Society, 25 (2012), 1033-1089. doi: 10.1090/S0894-0347-2012-00740-1.
[24]	G. Polya and G. Szegö, Aufgaben und Lehrsätze aus der Analysis, Vol. II, Springer, Berlin, 1971.
[25]	J. Romberg, E. Candes and T. Tao, Stable signal recovery from incomplete and inaccurate measurements, Communications on Pure and Applied Mathematics, 59 (2006), 1207-1223. doi: 10.1002/cpa.20124.
[26]	A. Ron and Z. Shen, Compactly supported tight affine spline frames in$ l^2(\mathbbR)$, Mathematics of Computation, 67 (1998), 191-207. doi: 10.1090/S0025-5718-98-00898-9.
[27]	I. J. Schoenberg, Contribution to the problem of approximation of equidistant data by analytic functions, Quart. Appl. Math., 4 (1946), 45-99, 112-141.
[28]	Z. Shen, Wavelet frames and image restorations, in Proc. Int. Congress of Mathematicians. Vol. IV (eds. Rajendra Bhatia), Hindustan Book Agency, New Delhi, 2010, 2834-2863.
[29]	Z. Shen, J. Cai and S. Osher, Split Bregman methods and frame based image restoration, Multiscale Modeling and Simulation: A SIAM Interdisciplinary Journal, 8 (2009), 337-369. doi: 10.1137/090753504.
[30]	Z. Shen H. Ji and Y. Xu, Wavelet frame based image restoration with missing/damaged pixels, East Asia Journal on Applied Mathematics, 1 (2011), 108-131.
[31]	G. Strang and G. Fix, A Fourier analysis of the finite element variational method, Construct. Asp. Funct. Anal., 57 (2011), 793-840. doi: 10.1007/978-3-642-10984-3_7.
[32]	V. A. Zheludev, V. N. Malozemov and A. B. Pevnyi, Filter banks and frames in the discrete periodic case, in Proceedings of the St. Petersburg Mathematical Society. Vol. XIV, AMS Translations, Ser. 2, 228, Amer. Math. Soc., Providence, RI, 2009, 1-11.
[33]	V. A. Zheludev, Local spline approximation on a uniform grid, Zh. Vychisl. Mat. i Mat. Fiz., 27 (1987), 1296-1310, 1437.
[34]	V. A. Zheludev, Periodic splines and the fast Fourier transform, Comput. Math. & Math Phys., 32 (1992), 149-165.
[35]	V. A. Zheludev, Interpolatory subdivision schemes with infinite masks originated from splines, Advances in Comp. Math., 25 (2006), 475-506. doi: 10.1007/s10444-004-4149-6.

show all references

References:

[1]	O. Amrani, A. Averbuch, T. Cohen and V. A. Zheludev, Symmetric interpolatory framelets and their error correction properties, International Journal of Wavelets, Multiresolution and Information Processing, 5 (2007), 541-566. doi: 10.1142/S0219691307001896.
[2]	A. Averbuch and V. Zheludev, Construction of biorthogonal discrete wavelet transforms using interpolatory splines, Applied and Comp. Harmonic Analysis, 12 (2002), 25-56. doi: 10.1006/acha.2001.0367.
[3]	A. Averbuch and V. Zheludev, Wavelet transforms generated by splines, International Journal of Wavelets, Multiresolution and Information Processing, 5 (2007), 257-291. doi: 10.1142/S0219691307001756.
[4]	A. Z. Averbuch, A. B. Pevnyi and V. A. Zheludev, Biorthogonal Butterworth wavelets derived from discrete interpolatory splines, IEEE Trans. on Sign. Proc., 49 (2001), 2682-2692. doi: 10.1109/78.960415.
[5]	A. Z. Averbuch, A. B. Pevnyi and V. A. Zheludev, Butterworth wavelet transforms derived from discrete interpolatory splines: Recursive implementation, Signal Processing, 81 (2001), 2363-2382.
[6]	A. Z. Averbuch, V. A. Zheludev and T. Cohen, Interpolatory frames in signal space, IEEE Trans. Sign. Proc., 54 (2006), 2126-2139. doi: 10.1109/TSP.2006.870562.
[7]	A. Z. Averbuch, V. A. Zheludev and T. Cohen, Tight and sibling frames originated from discrete splines, Sign. Proc. J., 86 (2006), 1632-1647. doi: 10.1016/j.sigpro.2005.09.007.
[8]	H. Bölcskei, F. Hlawatsch and H. G. Feichtinger, Frame-theoretic analysis of oversampled filter banks, IEEE Transactions on Sign. Proc., 46 (1998), 3256-3268.
[9]	C. K. Chui and W. He, Compactly supported tight frames associated with refinable functions, Applied and Comp. Harmonic Analysis, 8 (2000), 293-319. doi: 10.1006/acha.2000.0301.
[10]	C. K. Chui, W. He and J. Stöckler, Compactly supported tight and sibling frames with maximum vanishing moments, Applied and Comp. Harmonic Analysis, 13 (2002), 224-262. doi: 10.1016/S1063-5203(02)00510-9.
[11]	Z. Cvetković and M. Vetterli, Oversampled filter banks, IEEE Transactions on Signal Processing, 46 (1998), 1245-1255.
[12]	I. Daubechies, B. Han, A. Ron and Z. Shen, Framelets: Mra-based constructions of wavelet frames, Applied and Computational Harmonic Analysis, 14 (2003), 1-46. doi: 10.1016/S1063-5203(02)00511-0.
[13]	B. Dong and Z. Shen, Pseudo-splines, wavelets and framelets, Applied and Computational Harmonic Analysis, 22 (2007), 78-104. doi: 10.1016/j.acha.2006.04.008.
[14]	D. H. Foster, K. Amano, S. M. C. Nascimento and M. J. Foster, Frequency of metamerism in natural scenes, Journal of the Optical Society of America A, 23 (2006), 2359-2372.
[15]	T. Goldstein and S. Osher, The split {Bregman} method for l1-regularized problems, SIAM J. Imaging Sciences, 2 (2009), 323-343. doi: 10.1137/080725891.
[16]	M. Golub, M. Nathan, A. Averbuch, A. Kagan, V. A. Zheludev and R. Malinsky, Snapshot spectral imaging based on digital cameras, US Patent Application Publication Golub et al., No.13/762,560, US 2013/0194481 A1, 2013.
[17]	V. K. Goyal, J. Kovacevic and J. A. Kelner, Quantized frame expansions with erasures, Appl. and Comput. Harmonic Analysis, 10 (2001), 203-233. doi: 10.1006/acha.2000.0340.
[18]	V. K. Goyal, M. Vetterli and N. T. Thao, Quantized overcomplete expansions in $\mathbbR^n$: Analysis, synthesis and algorithms, IEEE Trans. on Information Theory, 44 (1998), 16-31. doi: 10.1109/18.650985.
[19]	B. Han, S. Song Goh and Z. Shen, Tight periodic wavelet frames and approximation orders, Applied and Computational Harmonic Analysis, 31 (2011), 228-248. doi: 10.1016/j.acha.2010.12.001.
[20]	C. Herley and M. Vetterli, Wavelets and recursive filter banks, IEEE Trans. Signal Proc., 41 (1993), 2536-2556. doi: 10.1109/78.229887.
[21]	J. Kovacevic, P. L. Dragotti and V. K. Goyal, Filter bank frame expansions with erasures, IEEE Trans. Inform, 48 (2002), 1439-1450. doi: 10.1109/TIT.2002.1003832.
[22]	A. V. Oppenheim and R. W. Schafer, Discrete-time Signal Processing, New York, Prentice Hall, 2010.
[23]	S. Osher, J. Cai, B. Dong and Z. Shen, Image restoration: Total variation, wavelet frames, and beyond, Journal of the American Mathematical Society, 25 (2012), 1033-1089. doi: 10.1090/S0894-0347-2012-00740-1.
[24]	G. Polya and G. Szegö, Aufgaben und Lehrsätze aus der Analysis, Vol. II, Springer, Berlin, 1971.
[25]	J. Romberg, E. Candes and T. Tao, Stable signal recovery from incomplete and inaccurate measurements, Communications on Pure and Applied Mathematics, 59 (2006), 1207-1223. doi: 10.1002/cpa.20124.
[26]	A. Ron and Z. Shen, Compactly supported tight affine spline frames in$ l^2(\mathbbR)$, Mathematics of Computation, 67 (1998), 191-207. doi: 10.1090/S0025-5718-98-00898-9.
[27]	I. J. Schoenberg, Contribution to the problem of approximation of equidistant data by analytic functions, Quart. Appl. Math., 4 (1946), 45-99, 112-141.
[28]	Z. Shen, Wavelet frames and image restorations, in Proc. Int. Congress of Mathematicians. Vol. IV (eds. Rajendra Bhatia), Hindustan Book Agency, New Delhi, 2010, 2834-2863.
[29]	Z. Shen, J. Cai and S. Osher, Split Bregman methods and frame based image restoration, Multiscale Modeling and Simulation: A SIAM Interdisciplinary Journal, 8 (2009), 337-369. doi: 10.1137/090753504.
[30]	Z. Shen H. Ji and Y. Xu, Wavelet frame based image restoration with missing/damaged pixels, East Asia Journal on Applied Mathematics, 1 (2011), 108-131.
[31]	G. Strang and G. Fix, A Fourier analysis of the finite element variational method, Construct. Asp. Funct. Anal., 57 (2011), 793-840. doi: 10.1007/978-3-642-10984-3_7.
[32]	V. A. Zheludev, V. N. Malozemov and A. B. Pevnyi, Filter banks and frames in the discrete periodic case, in Proceedings of the St. Petersburg Mathematical Society. Vol. XIV, AMS Translations, Ser. 2, 228, Amer. Math. Soc., Providence, RI, 2009, 1-11.
[33]	V. A. Zheludev, Local spline approximation on a uniform grid, Zh. Vychisl. Mat. i Mat. Fiz., 27 (1987), 1296-1310, 1437.
[34]	V. A. Zheludev, Periodic splines and the fast Fourier transform, Comput. Math. & Math Phys., 32 (1992), 149-165.
[35]	V. A. Zheludev, Interpolatory subdivision schemes with infinite masks originated from splines, Advances in Comp. Math., 25 (2006), 475-506. doi: 10.1007/s10444-004-4149-6.

[1]	Song Li, Junhong Lin. Compressed sensing with coherent tight frames via $l_q$-minimization for $0 < q \leq 1$. Inverse Problems and Imaging, 2014, 8 (3) : 761-777. doi: 10.3934/ipi.2014.8.761
[2]	Aihua Li. An algebraic approach to building interpolating polynomial. Conference Publications, 2005, 2005 (Special) : 597-604. doi: 10.3934/proc.2005.2005.597
[3]	Chengxiang Wang, Li Zeng, Yumeng Guo, Lingli Zhang. Wavelet tight frame and prior image-based image reconstruction from limited-angle projection data. Inverse Problems and Imaging, 2017, 11 (6) : 917-948. doi: 10.3934/ipi.2017043
[4]	Radu Balan, Peter G. Casazza, Christopher Heil and Zeph Landau. Density, overcompleteness, and localization of frames. Electronic Research Announcements, 2006, 12: 71-86.
[5]	Manuel V. C. Vieira. Derivatives of eigenvalues and Jordan frames. Numerical Algebra, Control and Optimization, 2016, 6 (2) : 115-126. doi: 10.3934/naco.2016003
[6]	C. A. Micchelli, Q. Sun. Interpolating filters with prescribed zeros and their refinable functions. Communications on Pure and Applied Analysis, 2007, 6 (3) : 789-808. doi: 10.3934/cpaa.2007.6.789
[7]	Frédéric Bourgeois, Kai Cieliebak, Tobias Ekholm. A note on Reeb dynamics on the tight 3-sphere. Journal of Modern Dynamics, 2007, 1 (4) : 597-613. doi: 10.3934/jmd.2007.1.597
[8]	Hanbing Liu, Yongdong Huang, Chongjun Li. Weaving K-fusion frames in hilbert spaces. Mathematical Foundations of Computing, 2020, 3 (2) : 101-116. doi: 10.3934/mfc.2020008
[9]	Mike Crampin, Tom Mestdag. Reduction of invariant constrained systems using anholonomic frames. Journal of Geometric Mechanics, 2011, 3 (1) : 23-40. doi: 10.3934/jgm.2011.3.23
[10]	Ting Chen, Fusheng Lv, Wenchang Sun. Uniform Approximation Property of Frames with Applications to Erasure Recovery. Communications on Pure and Applied Analysis, 2022, 21 (3) : 1093-1107. doi: 10.3934/cpaa.2022011
[11]	P. Cerejeiras, M. Ferreira, U. Kähler, F. Sommen. Continuous wavelet transform and wavelet frames on the sphere using Clifford analysis. Communications on Pure and Applied Analysis, 2007, 6 (3) : 619-641. doi: 10.3934/cpaa.2007.6.619
[12]	Igor Averbakh, Shu-Cherng Fang, Yun-Bin Zhao. Robust univariate cubic $L_2$ splines: Interpolating data with uncertain positions of measurements. Journal of Industrial and Management Optimization, 2009, 5 (2) : 351-361. doi: 10.3934/jimo.2009.5.351
[13]	Mehdi Bastani, Davod Khojasteh Salkuyeh. On the GSOR iteration method for image restoration. Numerical Algebra, Control and Optimization, 2021, 11 (1) : 27-43. doi: 10.3934/naco.2020013
[14]	Darko Dimitrov, Hosam Abdo. Tight independent set neighborhood union condition for fractional critical deleted graphs and ID deleted graphs. Discrete and Continuous Dynamical Systems - S, 2019, 12 (4&5) : 711-721. doi: 10.3934/dcdss.2019045
[15]	Kumiko Hattori, Noriaki Ogo, Takafumi Otsuka. A family of self-avoiding random walks interpolating the loop-erased random walk and a self-avoiding walk on the Sierpiński gasket. Discrete and Continuous Dynamical Systems - S, 2017, 10 (2) : 289-311. doi: 10.3934/dcdss.2017014
[16]	Nicolas Lermé, François Malgouyres, Dominique Hamoir, Emmanuelle Thouin. Bayesian image restoration for mosaic active imaging. Inverse Problems and Imaging, 2014, 8 (3) : 733-760. doi: 10.3934/ipi.2014.8.733
[17]	Ying Zhang, Xuhua Ren, Bryan Alexander Clifford, Qian Wang, Xiaoqun Zhang. Image fusion network for dual-modal restoration. Inverse Problems and Imaging, 2021, 15 (6) : 1409-1419. doi: 10.3934/ipi.2021067
[18]	Ruiqiang He, Xiangchu Feng, Xiaolong Zhu, Hua Huang, Bingzhe Wei. RWRM: Residual Wasserstein regularization model for image restoration. Inverse Problems and Imaging, 2021, 15 (6) : 1307-1332. doi: 10.3934/ipi.2020069
[19]	Antonella Falini, Francesca Mazzia, Cristiano Tamborrino. Spline based Hermite quasi-interpolation for univariate time series. Discrete and Continuous Dynamical Systems - S, 2022 doi: 10.3934/dcdss.2022039
[20]	Xiaoman Liu, Jijun Liu. Image restoration from noisy incomplete frequency data by alternative iteration scheme. Inverse Problems and Imaging, 2020, 14 (4) : 583-606. doi: 10.3934/ipi.2020027

2020 Impact Factor: 1.639

Tools

Metrics

Other articles
by authors

on AIMS
Amir Averbuch Pekka Neittaanmäki Valery Zheludev
on Google Scholar
Amir Averbuch Pekka Neittaanmäki Valery Zheludev

[Back to Top]