
Previous Article
Use of an optimized spatial prior in Dbar reconstructions of EIT tank data
 IPI Home
 This Issue

Next Article
Inverse acoustic scattering using highorder smallinclusion expansion of misfit function
Recursive reconstruction of piecewise constant signals by minimization of an energy function
Ecole Nationale Supérieure d'Arts et Métiers, Meknès, Morocco 
The problem of denoising piecewise constant signals while preserving their jumps is a challenging problem that arises in many scientific areas. Several denoising algorithms exist such as total variation, convex relaxation, Markov random fields models, etc. The DPS algorithm is a combinatorial algorithm that excels the classical GNC in term of speed and SNR resistance. However, its running time slows down considerably for large signals. The main reason for this bottleneck is the size and the number of linear systems that need to be solved. We develop a recursive implementation of the DPS algorithm that uses the conditional independence, created by a confirmed discontinuity between two parts, to separate the reconstruction process of each part. Additionally, we propose an accelerated Cholesky solver which reduces the computational cost and memory usage. We evaluate the new implementation on a set of synthetic and real world examples to compare the quality of our solver. The results show a significant speed up, especially with a higher number of discontinuities.
References:
[1] 
A. Blake, Comparison of the efficiency of deterministic and stochastic algorithms for visual reconstruction, IEEE Transactions on Pattern Analysis and Machine Intelligence, (1989), 212. 
[2] 
A. J. Aguirre, C. Brennan, G. Bailey, R. Sinha, B. Feng, C. Leo, Y. Zhang, J. Zhang, J. D. Gans, N. Bardeesy, C. Cauwels, C. CordonCardo, M. S. Redston, R. A. DePinho and L. Chin, Highresolution characterization of the pancreatic adenocarcinoma genome, Proceedings of the National Academy of Sciences, 101 (2004), 90679072. 
[3] 
D. M. G. Anderson, Z. Ablonczy, Y. Koutalos, J. Spraggins, R. K. Crouch, R. M. Caprioli and K. L. Schey, High Resolution MALDI Imaging Mass Spectrometry of Retinal Tissue Lipids, Journal of The American Society for Mass Spectrometry, 25 (2014), 13941403. 
[4] 
J. Besag, Statistical analysis of dirty pictures, Journal of Applied Statistics, 20 (1993), 6387. 
[5] 
M. J. Black and A. Rangarajan, On the unification of line processes outlier rejection, and robust statistics with applications in early vision, International Journal of Computer Vision, 19 (1996), 5791. 
[6] 
A. Blake and A. Zisserman, Visual Reconstruction, MIT Press, Cambridge, MA, USA, 1987. 
[7] 
C. Bouman and K. Sauer, A generalized Gaussian image model for edgepreserving MAP estimation, IEEE Transactions on Image Processing, 2 (1993), 296310. 
[8] 
Y. Boykov, O. Veksler and R. Zabih, Fast approximate energy minimization via graph cuts, IEEE Transactions on Pattern Analysis and Machine Intelligence, 23 (2001), 12221239. 
[9] 
P. Charbonnier, L. BlancFeraud, G. Aubert and M. Barlaud, Deterministic edgepreserving regularization in computed imaging, IEEE Transactions on Image Processing, 6 (1997), 298311. 
[10] 
L. Condat, A direct algorithm for 1D total variation denoising, IEEE Signal Processing Letters, 20 (2013), 10541057. 
[11] 
M. Dangkulwanich, T. Ishibashi, S. Liu, M. L. Kireeva, L. Lubkowska, M. Kashlev and C. J. Bustamante, Complete dissection of transcription elongation reveals slow translocation of rna polymerase ⅱ in a linear ratchet mechanism, Biophysical Journal, 2 (2014), 485a486a. 
[12] 
C.A. Deledalle, S. Vaiter, G. Peyré, J. Fadili and C. Dossal, Unbiased risk estimation for sparse analysis regularization, In Image Processing (ICIP), 2012 19th IEEE International Conference on, IEEE, (2012), 30533056. 
[13] 
L. Demaret, M. Storath and A. Weinmann, Reconstruction of piecewise constant signals by minimization of the l1potts functional, arXiv: 1207.4642 (2012). 
[14] 
P. Djuric, J.K. F. J.K. Fwu, S. Jovanovic and K. Lynn, On the processing of piecewiseconstant signals by hierarchical models with application to single ion channel currents, 1996 IEEE International Conference on Acoustics, Speech, and Signal Processing Conference Proceedings, 5 (1996), 27622765. 
[15] 
M. Douimi and H. Cherifi, Cutting enumerative algorithm for the minimizing of energy function, GRETSI, Trait. Signal, 15 (1998), 6778. 
[16] 
C. G. Farquharson, Constructing piecewiseconstant models in multidimensional minimumstructure inversions, Geophysics, 73 (2007), K1K9. 
[17] 
D. Geiger and F. Girosi, Parallel and deterministic algorithms from mrfs: Surface reconstruction and integration, Computer VisionECCV, 90 (1990), 8998. 
[18] 
S. Geman and D. Geman, Stochastic relaxation, gibbs distributions and the bayesian restoration of images, IEEE Trans. on PAMI, 6 (1984), 721741. 
[19] 
R. HORST and P. M. Pardalos, Handbook of Global Optimization, vol. 2 of Nonconvex optimization and its applications, Kluwer Academic Publishers, Dordrecht; Boston, 1995. doi: 10.1007/9781461520252. 
[20] 
B. Jackson, B. Stevens and G. Hurlbert, Research problems on Gray codes and universal cycles, Discrete Mathematics, 309 (2009), 53415348. doi: 10.1016/j.disc.2009.04.002. 
[21] 
M. A. Little, N. S. Jones and N. S. Jones, Generalized methods and solvers for noise removal from piecewise constant signals. Ⅱ. New methods, Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 467 (2011), 31153140. 
[22] 
M. A. Little, N. S. Jones and N. S. Jones, Generalized methods and solvers for noise removal from piecewise constant signals. Ⅱ. New methods, Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 467 (2011), 31153140. 
[23] 
E. Pappalardo, B. A. Ozkok and P. M. Pardalos, Combinatorial optimization algorithms, In Handbook of Combinatorial Optimization, Springer New York, 2013, 559593. 
[24] 
R. Ramlau and W. Ring, A MumfordShah levelset approach for the inversion and segmentation of Xray tomography data, Journal of Computational Physics, 221 (2007), 539557. doi: 10.1016/j.jcp.2006.06.041. 
[25] 
J. Rosskopf, K. PaulYuan, M. B. Plenio and J. Michaelis, Energybased scheme for reconstruction of piecewise constant signals observed in the movement of molecular machines, Physical Review E, 94 (2016). 
[26] 
A. Weinmann, M. Storath and L. Demaret, The $L^1$potts functional for robust jumpsparse reconstruction, SIAM Journal on Numerical Analysis, 53 (2015), 644673. doi: 10.1137/120896256. 
[27] 
G. Winkler, O. Wittich, V. Liebscher and A. Kempe, Don't shed tears over breaks, Jahresber. Deutsch. Math.Verein, 107 (2005), 5787. 
show all references
References:
[1] 
A. Blake, Comparison of the efficiency of deterministic and stochastic algorithms for visual reconstruction, IEEE Transactions on Pattern Analysis and Machine Intelligence, (1989), 212. 
[2] 
A. J. Aguirre, C. Brennan, G. Bailey, R. Sinha, B. Feng, C. Leo, Y. Zhang, J. Zhang, J. D. Gans, N. Bardeesy, C. Cauwels, C. CordonCardo, M. S. Redston, R. A. DePinho and L. Chin, Highresolution characterization of the pancreatic adenocarcinoma genome, Proceedings of the National Academy of Sciences, 101 (2004), 90679072. 
[3] 
D. M. G. Anderson, Z. Ablonczy, Y. Koutalos, J. Spraggins, R. K. Crouch, R. M. Caprioli and K. L. Schey, High Resolution MALDI Imaging Mass Spectrometry of Retinal Tissue Lipids, Journal of The American Society for Mass Spectrometry, 25 (2014), 13941403. 
[4] 
J. Besag, Statistical analysis of dirty pictures, Journal of Applied Statistics, 20 (1993), 6387. 
[5] 
M. J. Black and A. Rangarajan, On the unification of line processes outlier rejection, and robust statistics with applications in early vision, International Journal of Computer Vision, 19 (1996), 5791. 
[6] 
A. Blake and A. Zisserman, Visual Reconstruction, MIT Press, Cambridge, MA, USA, 1987. 
[7] 
C. Bouman and K. Sauer, A generalized Gaussian image model for edgepreserving MAP estimation, IEEE Transactions on Image Processing, 2 (1993), 296310. 
[8] 
Y. Boykov, O. Veksler and R. Zabih, Fast approximate energy minimization via graph cuts, IEEE Transactions on Pattern Analysis and Machine Intelligence, 23 (2001), 12221239. 
[9] 
P. Charbonnier, L. BlancFeraud, G. Aubert and M. Barlaud, Deterministic edgepreserving regularization in computed imaging, IEEE Transactions on Image Processing, 6 (1997), 298311. 
[10] 
L. Condat, A direct algorithm for 1D total variation denoising, IEEE Signal Processing Letters, 20 (2013), 10541057. 
[11] 
M. Dangkulwanich, T. Ishibashi, S. Liu, M. L. Kireeva, L. Lubkowska, M. Kashlev and C. J. Bustamante, Complete dissection of transcription elongation reveals slow translocation of rna polymerase ⅱ in a linear ratchet mechanism, Biophysical Journal, 2 (2014), 485a486a. 
[12] 
C.A. Deledalle, S. Vaiter, G. Peyré, J. Fadili and C. Dossal, Unbiased risk estimation for sparse analysis regularization, In Image Processing (ICIP), 2012 19th IEEE International Conference on, IEEE, (2012), 30533056. 
[13] 
L. Demaret, M. Storath and A. Weinmann, Reconstruction of piecewise constant signals by minimization of the l1potts functional, arXiv: 1207.4642 (2012). 
[14] 
P. Djuric, J.K. F. J.K. Fwu, S. Jovanovic and K. Lynn, On the processing of piecewiseconstant signals by hierarchical models with application to single ion channel currents, 1996 IEEE International Conference on Acoustics, Speech, and Signal Processing Conference Proceedings, 5 (1996), 27622765. 
[15] 
M. Douimi and H. Cherifi, Cutting enumerative algorithm for the minimizing of energy function, GRETSI, Trait. Signal, 15 (1998), 6778. 
[16] 
C. G. Farquharson, Constructing piecewiseconstant models in multidimensional minimumstructure inversions, Geophysics, 73 (2007), K1K9. 
[17] 
D. Geiger and F. Girosi, Parallel and deterministic algorithms from mrfs: Surface reconstruction and integration, Computer VisionECCV, 90 (1990), 8998. 
[18] 
S. Geman and D. Geman, Stochastic relaxation, gibbs distributions and the bayesian restoration of images, IEEE Trans. on PAMI, 6 (1984), 721741. 
[19] 
R. HORST and P. M. Pardalos, Handbook of Global Optimization, vol. 2 of Nonconvex optimization and its applications, Kluwer Academic Publishers, Dordrecht; Boston, 1995. doi: 10.1007/9781461520252. 
[20] 
B. Jackson, B. Stevens and G. Hurlbert, Research problems on Gray codes and universal cycles, Discrete Mathematics, 309 (2009), 53415348. doi: 10.1016/j.disc.2009.04.002. 
[21] 
M. A. Little, N. S. Jones and N. S. Jones, Generalized methods and solvers for noise removal from piecewise constant signals. Ⅱ. New methods, Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 467 (2011), 31153140. 
[22] 
M. A. Little, N. S. Jones and N. S. Jones, Generalized methods and solvers for noise removal from piecewise constant signals. Ⅱ. New methods, Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 467 (2011), 31153140. 
[23] 
E. Pappalardo, B. A. Ozkok and P. M. Pardalos, Combinatorial optimization algorithms, In Handbook of Combinatorial Optimization, Springer New York, 2013, 559593. 
[24] 
R. Ramlau and W. Ring, A MumfordShah levelset approach for the inversion and segmentation of Xray tomography data, Journal of Computational Physics, 221 (2007), 539557. doi: 10.1016/j.jcp.2006.06.041. 
[25] 
J. Rosskopf, K. PaulYuan, M. B. Plenio and J. Michaelis, Energybased scheme for reconstruction of piecewise constant signals observed in the movement of molecular machines, Physical Review E, 94 (2016). 
[26] 
A. Weinmann, M. Storath and L. Demaret, The $L^1$potts functional for robust jumpsparse reconstruction, SIAM Journal on Numerical Analysis, 53 (2015), 644673. doi: 10.1137/120896256. 
[27] 
G. Winkler, O. Wittich, V. Liebscher and A. Kempe, Don't shed tears over breaks, Jahresber. Deutsch. Math.Verein, 107 (2005), 5787. 
[1] 
Tom Goldstein, Xavier Bresson, Stan Osher. Global minimization of Markov random fields with applications to optical flow. Inverse Problems & Imaging, 2012, 6 (4) : 623644. doi: 10.3934/ipi.2012.6.623 
[2] 
M. Montaz Ali. A recursive topographical differential evolution algorithm for potential energy minimization. Journal of Industrial & Management Optimization, 2010, 6 (1) : 2946. doi: 10.3934/jimo.2010.6.29 
[3] 
Mario Roy, Mariusz Urbański. Random graph directed Markov systems. Discrete & Continuous Dynamical Systems  A, 2011, 30 (1) : 261298. doi: 10.3934/dcds.2011.30.261 
[4] 
Rainer Buckdahn, Ingo Bulla, Jin Ma. Pathwise Taylor expansions for Itô random fields. Mathematical Control & Related Fields, 2011, 1 (4) : 437468. doi: 10.3934/mcrf.2011.1.437 
[5] 
Xavier Dubois de La Sablonière, Benjamin Mauroy, Yannick Privat. Shape minimization of the dissipated energy in dyadic trees. Discrete & Continuous Dynamical Systems  B, 2011, 16 (3) : 767799. doi: 10.3934/dcdsb.2011.16.767 
[6] 
Johnathan M. Bardsley. Gaussian Markov random field priors for inverse problems. Inverse Problems & Imaging, 2013, 7 (2) : 397416. doi: 10.3934/ipi.2013.7.397 
[7] 
Manfred Denker, Yuri Kifer, Manuel Stadlbauer. Thermodynamic formalism for random countable Markov shifts. Discrete & Continuous Dynamical Systems  A, 2008, 22 (1&2) : 131164. doi: 10.3934/dcds.2008.22.131 
[8] 
Felix X.F. Ye, Yue Wang, Hong Qian. Stochastic dynamics: Markov chains and random transformations. Discrete & Continuous Dynamical Systems  B, 2016, 21 (7) : 23372361. doi: 10.3934/dcdsb.2016050 
[9] 
Manfred Denker, Yuri Kifer, Manuel Stadlbauer. Corrigendum to: Thermodynamic formalism for random countable Markov shifts. Discrete & Continuous Dynamical Systems  A, 2015, 35 (1) : 593594. doi: 10.3934/dcds.2015.35.593 
[10] 
Rainer Hegselmann, Ulrich Krause. Opinion dynamics under the influence of radical groups, charismatic leaders, and other constant signals: A simple unifying model. Networks & Heterogeneous Media, 2015, 10 (3) : 477509. doi: 10.3934/nhm.2015.10.477 
[11] 
Nicolay M. Tanushev, Luminita Vese. A piecewiseconstant binary model for electrical impedance tomography. Inverse Problems & Imaging, 2007, 1 (2) : 423435. doi: 10.3934/ipi.2007.1.423 
[12] 
Marat Akhmet. Quasilinear retarded differential equations with functional dependence on piecewise constant argument. Communications on Pure & Applied Analysis, 2014, 13 (2) : 929947. doi: 10.3934/cpaa.2014.13.929 
[13] 
Xiaoping Fang, Youjun Deng. Uniqueness on recovery of piecewise constant conductivity and inner core with one measurement. Inverse Problems & Imaging, 2018, 12 (3) : 733743. doi: 10.3934/ipi.2018031 
[14] 
Krzysztof Frączek, M. Lemańczyk, E. Lesigne. Mild mixing property for special flows under piecewise constant functions. Discrete & Continuous Dynamical Systems  A, 2007, 19 (4) : 691710. doi: 10.3934/dcds.2007.19.691 
[15] 
Marat Akhmet, Duygu Aruğaslan. LyapunovRazumikhin method for differential equations with piecewise constant argument. Discrete & Continuous Dynamical Systems  A, 2009, 25 (2) : 457466. doi: 10.3934/dcds.2009.25.457 
[16] 
Adil Bagirov, Sona Taheri, Soodabeh Asadi. A difference of convex optimization algorithm for piecewise linear regression. Journal of Industrial & Management Optimization, 2019, 15 (2) : 909932. doi: 10.3934/jimo.2018077 
[17] 
Łukasz Struski, Jacek Tabor, Tomasz Kułaga. Conefields without constant orbit core dimension. Discrete & Continuous Dynamical Systems  A, 2012, 32 (10) : 36513664. doi: 10.3934/dcds.2012.32.3651 
[18] 
Shengtian Yang, Thomas Honold. Good random matrices over finite fields. Advances in Mathematics of Communications, 2012, 6 (2) : 203227. doi: 10.3934/amc.2012.6.203 
[19] 
Riccardo Adami, Diego Noja, Nicola Visciglia. Constrained energy minimization and ground states for NLS with point defects. Discrete & Continuous Dynamical Systems  B, 2013, 18 (5) : 11551188. doi: 10.3934/dcdsb.2013.18.1155 
[20] 
Qiuying Li, Lifang Huang, Jianshe Yu. Modulation of firstpassage time for bursty gene expression via random signals. Mathematical Biosciences & Engineering, 2017, 14 (5&6) : 12611277. doi: 10.3934/mbe.2017065 
2017 Impact Factor: 1.465
Tools
Metrics
Other articles
by authors
[Back to Top]