American Institute of Mathematical Sciences

Advanced
  • 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

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 fi lters. 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 & 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, 5 (2007), 541.  doi: 10.1142/S0219691307001896.  Google Scholar

[2]

A. Averbuch and V. Zheludev, Construction of biorthogonal discrete wavelet transforms using interpolatory splines,, Applied and Comp. Harmonic Analysis, 12 (2002), 25.  doi: 10.1006/acha.2001.0367.  Google Scholar

[3]

A. Averbuch and V. Zheludev, Wavelet transforms generated by splines,, International Journal of Wavelets, 5 (2007), 257.  doi: 10.1142/S0219691307001756.  Google Scholar

[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.  doi: 10.1109/78.960415.  Google Scholar

[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.   Google Scholar

[6]

A. Z. Averbuch, V. A. Zheludev and T. Cohen, Interpolatory frames in signal space,, IEEE Trans. Sign. Proc., 54 (2006), 2126.  doi: 10.1109/TSP.2006.870562.  Google Scholar

[7]

A. Z. Averbuch, V. A. Zheludev and T. Cohen, Tight and sibling frames originated from discrete splines,, Sign. Proc. J., 86 (2006), 1632.  doi: 10.1016/j.sigpro.2005.09.007.  Google Scholar

[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.   Google Scholar

[9]

C. K. Chui and W. He, Compactly supported tight frames associated with refinable functions,, Applied and Comp. Harmonic Analysis, 8 (2000), 293.  doi: 10.1006/acha.2000.0301.  Google Scholar

[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.  doi: 10.1016/S1063-5203(02)00510-9.  Google Scholar

[11]

Z. Cvetković and M. Vetterli, Oversampled filter banks,, IEEE Transactions on Signal Processing, 46 (1998), 1245.   Google Scholar

[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.  doi: 10.1016/S1063-5203(02)00511-0.  Google Scholar

[13]

B. Dong and Z. Shen, Pseudo-splines, wavelets and framelets,, Applied and Computational Harmonic Analysis, 22 (2007), 78.  doi: 10.1016/j.acha.2006.04.008.  Google Scholar

[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.   Google Scholar

[15]

T. Goldstein and S. Osher, The split {Bregman} method for l1-regularized problems,, SIAM J. Imaging Sciences, 2 (2009), 323.  doi: 10.1137/080725891.  Google Scholar

[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., (2013).   Google Scholar

[17]

V. K. Goyal, J. Kovacevic and J. A. Kelner, Quantized frame expansions with erasures,, Appl. and Comput. Harmonic Analysis, 10 (2001), 203.  doi: 10.1006/acha.2000.0340.  Google Scholar

[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.  doi: 10.1109/18.650985.  Google Scholar

[19]

B. Han, S. Song Goh and Z. Shen, Tight periodic wavelet frames and approximation orders,, Applied and Computational Harmonic Analysis, 31 (2011), 228.  doi: 10.1016/j.acha.2010.12.001.  Google Scholar

[20]

C. Herley and M. Vetterli, Wavelets and recursive filter banks,, IEEE Trans. Signal Proc., 41 (1993), 2536.  doi: 10.1109/78.229887.  Google Scholar

[21]

J. Kovacevic, P. L. Dragotti and V. K. Goyal, Filter bank frame expansions with erasures,, IEEE Trans. Inform, 48 (2002), 1439.  doi: 10.1109/TIT.2002.1003832.  Google Scholar

[22]

A. V. Oppenheim and R. W. Schafer, Discrete-time Signal Processing,, New York, (2010).   Google Scholar

[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.  doi: 10.1090/S0894-0347-2012-00740-1.  Google Scholar

[24]

G. Polya and G. Szegö, Aufgaben und Lehrsätze aus der Analysis, Vol. II,, Springer, (1971).   Google Scholar

[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.  doi: 10.1002/cpa.20124.  Google Scholar

[26]

A. Ron and Z. Shen, Compactly supported tight affine spline frames in$ l^2(\mathbbR)$,, Mathematics of Computation, 67 (1998), 191.  doi: 10.1090/S0025-5718-98-00898-9.  Google Scholar

[27]

I. J. Schoenberg, Contribution to the problem of approximation of equidistant data by analytic functions,, Quart. Appl. Math., 4 (1946), 45.   Google Scholar

[28]

Z. Shen, Wavelet frames and image restorations,, in Proc. Int. Congress of Mathematicians. Vol. IV (eds. Rajendra Bhatia), (2010), 2834.   Google Scholar

[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.  doi: 10.1137/090753504.  Google Scholar

[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.   Google Scholar

[31]

G. Strang and G. Fix, A Fourier analysis of the finite element variational method,, Construct. Asp. Funct. Anal., 57 (2011), 793.  doi: 10.1007/978-3-642-10984-3_7.  Google Scholar

[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, (2009), 1.   Google Scholar

[33]

V. A. Zheludev, Local spline approximation on a uniform grid,, Zh. Vychisl. Mat. i Mat. Fiz., 27 (1987), 1296.   Google Scholar

[34]

V. A. Zheludev, Periodic splines and the fast Fourier transform,, Comput. Math. & Math Phys., 32 (1992), 149.   Google Scholar

[35]

V. A. Zheludev, Interpolatory subdivision schemes with infinite masks originated from splines,, Advances in Comp. Math., 25 (2006), 475.  doi: 10.1007/s10444-004-4149-6.  Google Scholar

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, 5 (2007), 541.  doi: 10.1142/S0219691307001896.  Google Scholar

[2]

A. Averbuch and V. Zheludev, Construction of biorthogonal discrete wavelet transforms using interpolatory splines,, Applied and Comp. Harmonic Analysis, 12 (2002), 25.  doi: 10.1006/acha.2001.0367.  Google Scholar

[3]

A. Averbuch and V. Zheludev, Wavelet transforms generated by splines,, International Journal of Wavelets, 5 (2007), 257.  doi: 10.1142/S0219691307001756.  Google Scholar

[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.  doi: 10.1109/78.960415.  Google Scholar

[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.   Google Scholar

[6]

A. Z. Averbuch, V. A. Zheludev and T. Cohen, Interpolatory frames in signal space,, IEEE Trans. Sign. Proc., 54 (2006), 2126.  doi: 10.1109/TSP.2006.870562.  Google Scholar

[7]

A. Z. Averbuch, V. A. Zheludev and T. Cohen, Tight and sibling frames originated from discrete splines,, Sign. Proc. J., 86 (2006), 1632.  doi: 10.1016/j.sigpro.2005.09.007.  Google Scholar

[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.   Google Scholar

[9]

C. K. Chui and W. He, Compactly supported tight frames associated with refinable functions,, Applied and Comp. Harmonic Analysis, 8 (2000), 293.  doi: 10.1006/acha.2000.0301.  Google Scholar

[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.  doi: 10.1016/S1063-5203(02)00510-9.  Google Scholar

[11]

Z. Cvetković and M. Vetterli, Oversampled filter banks,, IEEE Transactions on Signal Processing, 46 (1998), 1245.   Google Scholar

[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.  doi: 10.1016/S1063-5203(02)00511-0.  Google Scholar

[13]

B. Dong and Z. Shen, Pseudo-splines, wavelets and framelets,, Applied and Computational Harmonic Analysis, 22 (2007), 78.  doi: 10.1016/j.acha.2006.04.008.  Google Scholar

[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.   Google Scholar

[15]

T. Goldstein and S. Osher, The split {Bregman} method for l1-regularized problems,, SIAM J. Imaging Sciences, 2 (2009), 323.  doi: 10.1137/080725891.  Google Scholar

[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., (2013).   Google Scholar

[17]

V. K. Goyal, J. Kovacevic and J. A. Kelner, Quantized frame expansions with erasures,, Appl. and Comput. Harmonic Analysis, 10 (2001), 203.  doi: 10.1006/acha.2000.0340.  Google Scholar

[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.  doi: 10.1109/18.650985.  Google Scholar

[19]

B. Han, S. Song Goh and Z. Shen, Tight periodic wavelet frames and approximation orders,, Applied and Computational Harmonic Analysis, 31 (2011), 228.  doi: 10.1016/j.acha.2010.12.001.  Google Scholar

[20]

C. Herley and M. Vetterli, Wavelets and recursive filter banks,, IEEE Trans. Signal Proc., 41 (1993), 2536.  doi: 10.1109/78.229887.  Google Scholar

[21]

J. Kovacevic, P. L. Dragotti and V. K. Goyal, Filter bank frame expansions with erasures,, IEEE Trans. Inform, 48 (2002), 1439.  doi: 10.1109/TIT.2002.1003832.  Google Scholar

[22]

A. V. Oppenheim and R. W. Schafer, Discrete-time Signal Processing,, New York, (2010).   Google Scholar

[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.  doi: 10.1090/S0894-0347-2012-00740-1.  Google Scholar

[24]

G. Polya and G. Szegö, Aufgaben und Lehrsätze aus der Analysis, Vol. II,, Springer, (1971).   Google Scholar

[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.  doi: 10.1002/cpa.20124.  Google Scholar

[26]

A. Ron and Z. Shen, Compactly supported tight affine spline frames in$ l^2(\mathbbR)$,, Mathematics of Computation, 67 (1998), 191.  doi: 10.1090/S0025-5718-98-00898-9.  Google Scholar

[27]

I. J. Schoenberg, Contribution to the problem of approximation of equidistant data by analytic functions,, Quart. Appl. Math., 4 (1946), 45.   Google Scholar

[28]

Z. Shen, Wavelet frames and image restorations,, in Proc. Int. Congress of Mathematicians. Vol. IV (eds. Rajendra Bhatia), (2010), 2834.   Google Scholar

[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.  doi: 10.1137/090753504.  Google Scholar

[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.   Google Scholar

[31]

G. Strang and G. Fix, A Fourier analysis of the finite element variational method,, Construct. Asp. Funct. Anal., 57 (2011), 793.  doi: 10.1007/978-3-642-10984-3_7.  Google Scholar

[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, (2009), 1.   Google Scholar

[33]

V. A. Zheludev, Local spline approximation on a uniform grid,, Zh. Vychisl. Mat. i Mat. Fiz., 27 (1987), 1296.   Google Scholar

[34]

V. A. Zheludev, Periodic splines and the fast Fourier transform,, Comput. Math. & Math Phys., 32 (1992), 149.   Google Scholar

[35]

V. A. Zheludev, Interpolatory subdivision schemes with infinite masks originated from splines,, Advances in Comp. Math., 25 (2006), 475.  doi: 10.1007/s10444-004-4149-6.  Google Scholar

[1]

Song Li, Junhong Lin. Compressed sensing with coherent tight frames via $l_q$-minimization for $0 < q \leq 1$. Inverse Problems & 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 & 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 & 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 & 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]

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
[9]

P. Cerejeiras, M. Ferreira, U. Kähler, F. Sommen. Continuous wavelet transform and wavelet frames on the sphere using Clifford analysis. Communications on Pure & Applied Analysis, 2007, 6 (3) : 619-641. doi: 10.3934/cpaa.2007.6.619
[10]

Igor Averbakh, Shu-Cherng Fang, Yun-Bin Zhao. Robust univariate cubic $L_2$ splines: Interpolating data with uncertain positions of measurements. Journal of Industrial & Management Optimization, 2009, 5 (2) : 351-361. doi: 10.3934/jimo.2009.5.351
[11]

Wei Gao, Darko Dimitrov, Hosam Abdo. Tight independent set neighborhood union condition for fractional critical deleted graphs and ID deleted graphs. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 711-721. doi: 10.3934/dcdss.2019045
[12]

Nicolas Lermé, François Malgouyres, Dominique Hamoir, Emmanuelle Thouin. Bayesian image restoration for mosaic active imaging. Inverse Problems & Imaging, 2014, 8 (3) : 733-760. doi: 10.3934/ipi.2014.8.733
[13]

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 & Continuous Dynamical Systems - S, 2017, 10 (2) : 289-311. doi: 10.3934/dcdss.2017014
[14]

Alina Toma, Bruno Sixou, Françoise Peyrin. Iterative choice of the optimal regularization parameter in TV image restoration. Inverse Problems & Imaging, 2015, 9 (4) : 1171-1191. doi: 10.3934/ipi.2015.9.1171
[15]

Jing Xu, Xue-Cheng Tai, Li-Lian Wang. A two-level domain decomposition method for image restoration. Inverse Problems & Imaging, 2010, 4 (3) : 523-545. doi: 10.3934/ipi.2010.4.523
[16]

Bartomeu Coll, Joan Duran, Catalina Sbert. Half-linear regularization for nonconvex image restoration models. Inverse Problems & Imaging, 2015, 9 (2) : 337-370. doi: 10.3934/ipi.2015.9.337
[17]

Moulay Rchid Sidi Ammi, Ismail Jamiai. Finite difference and Legendre spectral method for a time-fractional diffusion-convection equation for image restoration. Discrete & Continuous Dynamical Systems - S, 2018, 11 (1) : 103-117. doi: 10.3934/dcdss.2018007
[18]

Petteri Harjulehto, Peter Hästö, Juha Tiirola. Point-wise behavior of the Geman--McClure and the Hebert--Leahy image restoration models. Inverse Problems & Imaging, 2015, 9 (3) : 835-851. doi: 10.3934/ipi.2015.9.835
[19]

C. M. Elliott, B. Gawron, S. Maier-Paape, E. S. Van Vleck. Discrete dynamics for convex and non-convex smoothing functionals in PDE based image restoration. Communications on Pure & Applied Analysis, 2006, 5 (1) : 181-200. doi: 10.3934/cpaa.2006.5.181
[20]

Jia Li, Zuowei Shen, Rujie Yin, Xiaoqun Zhang. A reweighted $l^2$ method for image restoration with Poisson and mixed Poisson-Gaussian noise. Inverse Problems & Imaging, 2015, 9 (3) : 875-894. doi: 10.3934/ipi.2015.9.875

2018 Impact Factor: 1.469

Tools

Metrics

  • PDF downloads (10)
  • HTML views (0)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2019 American Institute of Mathematical Sciences