# American Institute of Mathematical Sciences

August  2018, 12(4): 903-920. doi: 10.3934/ipi.2018038

## Recursive reconstruction of piecewise constant signals by minimization of an energy function

 Ecole Nationale Supérieure d'Arts et Métiers, Meknès, Morocco

* Corresponding author: a.belcaid@edu.umi.ac.ma

Received  May 2017 Revised  January 2018 Published  June 2018

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.

Citation: Anass Belcaid, Mohammed Douimi, Abdelkader Fassi Fihri. Recursive reconstruction of piecewise constant signals by minimization of an energy function. Inverse Problems & Imaging, 2018, 12 (4) : 903-920. doi: 10.3934/ipi.2018038
##### 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), 2-12.   Google Scholar [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. Cordon-Cardo, M. S. Redston, R. A. DePinho and L. Chin, High-resolution characterization of the pancreatic adenocarcinoma genome, Proceedings of the National Academy of Sciences, 101 (2004), 9067-9072.   Google Scholar [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), 1394-1403.   Google Scholar [4] J. Besag, Statistical analysis of dirty pictures, Journal of Applied Statistics, 20 (1993), 63-87.   Google Scholar [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), 57-91.   Google Scholar [6] A. Blake and A. Zisserman, Visual Reconstruction, MIT Press, Cambridge, MA, USA, 1987.  Google Scholar [7] C. Bouman and K. Sauer, A generalized Gaussian image model for edge-preserving MAP estimation, IEEE Transactions on Image Processing, 2 (1993), 296-310.   Google Scholar [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), 1222-1239.   Google Scholar [9] P. Charbonnier, L. Blanc-Feraud, G. Aubert and M. Barlaud, Deterministic edge-preserving regularization in computed imaging, IEEE Transactions on Image Processing, 6 (1997), 298-311.   Google Scholar [10] L. Condat, A direct algorithm for 1-D total variation denoising, IEEE Signal Processing Letters, 20 (2013), 1054-1057.   Google Scholar [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), 485a-486a.   Google Scholar [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), 3053-3056. Google Scholar [13] L. Demaret, M. Storath and A. Weinmann, Reconstruction of piecewise constant signals by minimization of the l1-potts functional, arXiv: 1207.4642 (2012). Google Scholar [14] P. Djuric, J.-K. F. J.-K. Fwu, S. Jovanovic and K. Lynn, On the processing of piecewise-constant 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), 2762-2765.   Google Scholar [15] M. Douimi and H. Cherifi, Cutting enumerative algorithm for the minimizing of energy function, GRETSI, Trait. Signal, 15 (1998), 67-78.   Google Scholar [16] C. G. Farquharson, Constructing piecewise-constant models in multidimensional minimum-structure inversions, Geophysics, 73 (2007), K1-K9.   Google Scholar [17] D. Geiger and F. Girosi, Parallel and deterministic algorithms from mrfs: Surface reconstruction and integration, Computer Vision-ECCV, 90 (1990), 89-98.   Google Scholar [18] S. Geman and D. Geman, Stochastic relaxation, gibbs distributions and the bayesian restoration of images, IEEE Trans. on PAMI, 6 (1984), 721-741.   Google Scholar [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/978-1-4615-2025-2.  Google Scholar [20] B. Jackson, B. Stevens and G. Hurlbert, Research problems on Gray codes and universal cycles, Discrete Mathematics, 309 (2009), 5341-5348.  doi: 10.1016/j.disc.2009.04.002.  Google Scholar [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), 3115-3140.   Google Scholar [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), 3115-3140. Google Scholar [23] E. Pappalardo, B. A. Ozkok and P. M. Pardalos, Combinatorial optimization algorithms, In Handbook of Combinatorial Optimization, Springer New York, 2013, 559-593. Google Scholar [24] R. Ramlau and W. Ring, A Mumford-Shah level-set approach for the inversion and segmentation of X-ray tomography data, Journal of Computational Physics, 221 (2007), 539-557.  doi: 10.1016/j.jcp.2006.06.041.  Google Scholar [25] J. Rosskopf, K. Paul-Yuan, M. B. Plenio and J. Michaelis, Energy-based scheme for reconstruction of piecewise constant signals observed in the movement of molecular machines, Physical Review E, 94 (2016). Google Scholar [26] A. Weinmann, M. Storath and L. Demaret, The $L^1$-potts functional for robust jump-sparse reconstruction, SIAM Journal on Numerical Analysis, 53 (2015), 644-673.  doi: 10.1137/120896256.  Google Scholar [27] G. Winkler, O. Wittich, V. Liebscher and A. Kempe, Don't shed tears over breaks, Jahresber. Deutsch. Math.-Verein, 107 (2005), 57-87.   Google Scholar

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), 2-12.   Google Scholar [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. Cordon-Cardo, M. S. Redston, R. A. DePinho and L. Chin, High-resolution characterization of the pancreatic adenocarcinoma genome, Proceedings of the National Academy of Sciences, 101 (2004), 9067-9072.   Google Scholar [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), 1394-1403.   Google Scholar [4] J. Besag, Statistical analysis of dirty pictures, Journal of Applied Statistics, 20 (1993), 63-87.   Google Scholar [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), 57-91.   Google Scholar [6] A. Blake and A. Zisserman, Visual Reconstruction, MIT Press, Cambridge, MA, USA, 1987.  Google Scholar [7] C. Bouman and K. Sauer, A generalized Gaussian image model for edge-preserving MAP estimation, IEEE Transactions on Image Processing, 2 (1993), 296-310.   Google Scholar [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), 1222-1239.   Google Scholar [9] P. Charbonnier, L. Blanc-Feraud, G. Aubert and M. Barlaud, Deterministic edge-preserving regularization in computed imaging, IEEE Transactions on Image Processing, 6 (1997), 298-311.   Google Scholar [10] L. Condat, A direct algorithm for 1-D total variation denoising, IEEE Signal Processing Letters, 20 (2013), 1054-1057.   Google Scholar [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), 485a-486a.   Google Scholar [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), 3053-3056. Google Scholar [13] L. Demaret, M. Storath and A. Weinmann, Reconstruction of piecewise constant signals by minimization of the l1-potts functional, arXiv: 1207.4642 (2012). Google Scholar [14] P. Djuric, J.-K. F. J.-K. Fwu, S. Jovanovic and K. Lynn, On the processing of piecewise-constant 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), 2762-2765.   Google Scholar [15] M. Douimi and H. Cherifi, Cutting enumerative algorithm for the minimizing of energy function, GRETSI, Trait. Signal, 15 (1998), 67-78.   Google Scholar [16] C. G. Farquharson, Constructing piecewise-constant models in multidimensional minimum-structure inversions, Geophysics, 73 (2007), K1-K9.   Google Scholar [17] D. Geiger and F. Girosi, Parallel and deterministic algorithms from mrfs: Surface reconstruction and integration, Computer Vision-ECCV, 90 (1990), 89-98.   Google Scholar [18] S. Geman and D. Geman, Stochastic relaxation, gibbs distributions and the bayesian restoration of images, IEEE Trans. on PAMI, 6 (1984), 721-741.   Google Scholar [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/978-1-4615-2025-2.  Google Scholar [20] B. Jackson, B. Stevens and G. Hurlbert, Research problems on Gray codes and universal cycles, Discrete Mathematics, 309 (2009), 5341-5348.  doi: 10.1016/j.disc.2009.04.002.  Google Scholar [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), 3115-3140.   Google Scholar [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), 3115-3140. Google Scholar [23] E. Pappalardo, B. A. Ozkok and P. M. Pardalos, Combinatorial optimization algorithms, In Handbook of Combinatorial Optimization, Springer New York, 2013, 559-593. Google Scholar [24] R. Ramlau and W. Ring, A Mumford-Shah level-set approach for the inversion and segmentation of X-ray tomography data, Journal of Computational Physics, 221 (2007), 539-557.  doi: 10.1016/j.jcp.2006.06.041.  Google Scholar [25] J. Rosskopf, K. Paul-Yuan, M. B. Plenio and J. Michaelis, Energy-based scheme for reconstruction of piecewise constant signals observed in the movement of molecular machines, Physical Review E, 94 (2016). Google Scholar [26] A. Weinmann, M. Storath and L. Demaret, The $L^1$-potts functional for robust jump-sparse reconstruction, SIAM Journal on Numerical Analysis, 53 (2015), 644-673.  doi: 10.1137/120896256.  Google Scholar [27] G. Winkler, O. Wittich, V. Liebscher and A. Kempe, Don't shed tears over breaks, Jahresber. Deutsch. Math.-Verein, 107 (2005), 57-87.   Google Scholar
(Grey line) log normalized DNA copy-number ratios against genome order micro-array based comparative genomic hybridization, data from [21]. (Red line) PWC restoration by the DPS algorithm
DPS search space and its pruning process. (Figure 2a) shows the search space (an Hypercube) structured in levels where each level regroups the set of LP with equal number of 1 bits. (Figure 2b) illustrates DPS pruning process which only considers the neighbors of the previous optimal solution. As an example, in the second level, we already found the optimal LP $(0100)$ in the first level. By this information, DPS will only consider its neighbors (red and blue nodes) and will prune the rest (empty nodes). Additionally, DPS will stop the search if the energy did not decrease from a level to another. In the example, we stop the search at the second level (red dashed line) since the energy increased from the first level to the second one
(a): The decomposition binary tree, for restroing a signal with three discontinuities $I = \{i_1, i_2, i_3\}$, (b) the recursive process where the final solution is obtained by regrouping the leaves of the tree
Number of solved matrices as a function of their size. The example restores a signal of size 1024 with 8 regularly distributed discontinuities
Restoration of a synthetic simulated data of the movement of a molecular motor. the initial data contains $10^4$ data points regularly distributed in $t\in[0, 2s]$. Left (5a) we remark that DPS exactly recovers all parts except for the hard jump at $t\approx 1.7$. In the right (5b), the restored signal by EBS algorithm with several missed jumps
Restoration quality of DPS and $l_2$-Potts for a signal with size $256$ and values $x_i \in [0, 1]$ corrupted by a white noise with standard deviation $\sigma = 0.2$. Figure (6a) represents the initial signal, (6b) shows the reconstructed signal with DPS with no false discontinuities, but with some errors in the height of some plateaus. Finally, the figure (6c) plots the optimal solution for the $l_2$-Potts solver which also detect all the discontinuities
Mean Square Error as a function of $\lambda$ and $h$
Mean square error as a function of the noise standard deviation $\sigma$. We remark the curve of DPS increases slowly compared to the other algorithms
The figure plots the difference $T_b -T_r$, in seconds, between the classical implementation time $T_b$ and the recursive implementation $T_r$. The difference varies depending on two factors : the signal size $n$ and the number of discontinuities $k$. From this figure it can be seen that the reduction is important especially with a higher number of discontinuities
The figure presents the running time in a logarithmic scale as a function of the signal size with fixed number of discontinuities $k = 15$ (a) and as a function of the number of discontinuities with fixed size $n = 10^3$ (b). As shown in the both figures, the recursive implementation offers a lower time and the deviation, from the classical DPS, becomes more compelling with higher number of discontinuities
 [1] Tom Goldstein, Xavier Bresson, Stan Osher. Global minimization of Markov random fields with applications to optical flow. Inverse Problems & Imaging, 2012, 6 (4) : 623-644. 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) : 29-46. doi: 10.3934/jimo.2010.6.29 [3] Christophe Profeta, Frédéric Vrins. Piecewise constant martingales and lazy clocks. Probability, Uncertainty and Quantitative Risk, 2019, 4 (0) : 2-. doi: 10.1186/s41546-019-0036-4 [4] Mario Roy, Mariusz Urbański. Random graph directed Markov systems. Discrete & Continuous Dynamical Systems - A, 2011, 30 (1) : 261-298. doi: 10.3934/dcds.2011.30.261 [5] Rainer Buckdahn, Ingo Bulla, Jin Ma. Pathwise Taylor expansions for Itô random fields. Mathematical Control & Related Fields, 2011, 1 (4) : 437-468. doi: 10.3934/mcrf.2011.1.437 [6] 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) : 767-799. doi: 10.3934/dcdsb.2011.16.767 [7] 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) : 477-509. doi: 10.3934/nhm.2015.10.477 [8] Nicolay M. Tanushev, Luminita Vese. A piecewise-constant binary model for electrical impedance tomography. Inverse Problems & Imaging, 2007, 1 (2) : 423-435. doi: 10.3934/ipi.2007.1.423 [9] Marat Akhmet. Quasilinear retarded differential equations with functional dependence on piecewise constant argument. Communications on Pure & Applied Analysis, 2014, 13 (2) : 929-947. doi: 10.3934/cpaa.2014.13.929 [10] Xiaoping Fang, Youjun Deng. Uniqueness on recovery of piecewise constant conductivity and inner core with one measurement. Inverse Problems & Imaging, 2018, 12 (3) : 733-743. doi: 10.3934/ipi.2018031 [11] 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) : 691-710. doi: 10.3934/dcds.2007.19.691 [12] Marat Akhmet, Duygu Aruğaslan. Lyapunov-Razumikhin method for differential equations with piecewise constant argument. Discrete & Continuous Dynamical Systems - A, 2009, 25 (2) : 457-466. doi: 10.3934/dcds.2009.25.457 [13] Adil Bagirov, Sona Taheri, Soodabeh Asadi. A difference of convex optimization algorithm for piecewise linear regression. Journal of Industrial & Management Optimization, 2019, 15 (2) : 909-932. doi: 10.3934/jimo.2018077 [14] Johnathan M. Bardsley. Gaussian Markov random field priors for inverse problems. Inverse Problems & Imaging, 2013, 7 (2) : 397-416. doi: 10.3934/ipi.2013.7.397 [15] Manfred Denker, Yuri Kifer, Manuel Stadlbauer. Thermodynamic formalism for random countable Markov shifts. Discrete & Continuous Dynamical Systems - A, 2008, 22 (1&2) : 131-164. doi: 10.3934/dcds.2008.22.131 [16] Felix X.-F. Ye, Yue Wang, Hong Qian. Stochastic dynamics: Markov chains and random transformations. Discrete & Continuous Dynamical Systems - B, 2016, 21 (7) : 2337-2361. doi: 10.3934/dcdsb.2016050 [17] Manfred Denker, Yuri Kifer, Manuel Stadlbauer. Corrigendum to: Thermodynamic formalism for random countable Markov shifts. Discrete & Continuous Dynamical Systems - A, 2015, 35 (1) : 593-594. doi: 10.3934/dcds.2015.35.593 [18] Łukasz Struski, Jacek Tabor, Tomasz Kułaga. Cone-fields without constant orbit core dimension. Discrete & Continuous Dynamical Systems - A, 2012, 32 (10) : 3651-3664. doi: 10.3934/dcds.2012.32.3651 [19] Shengtian Yang, Thomas Honold. Good random matrices over finite fields. Advances in Mathematics of Communications, 2012, 6 (2) : 203-227. doi: 10.3934/amc.2012.6.203 [20] Qiuying Li, Lifang Huang, Jianshe Yu. Modulation of first-passage time for bursty gene expression via random signals. Mathematical Biosciences & Engineering, 2017, 14 (5&6) : 1261-1277. doi: 10.3934/mbe.2017065

2019 Impact Factor: 1.373