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.

[2]

A. J. AguirreC. BrennanG. BaileyR. SinhaB. FengC. LeoY. ZhangJ. ZhangJ. D. GansN. BardeesyC. CauwelsC. Cordon-CardoM. S. RedstonR. A. DePinho and L. Chin, High-resolution characterization of the pancreatic adenocarcinoma genome, Proceedings of the National Academy of Sciences, 101 (2004), 9067-9072.

[3]

D. M. G. AndersonZ. AblonczyY. KoutalosJ. SpragginsR. K. CrouchR. 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.

[4]

J. Besag, Statistical analysis of dirty pictures, Journal of Applied Statistics, 20 (1993), 63-87.

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

[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 edge-preserving MAP estimation, IEEE Transactions on Image Processing, 2 (1993), 296-310.

[8]

Y. BoykovO. Veksler and R. Zabih, Fast approximate energy minimization via graph cuts, IEEE Transactions on Pattern Analysis and Machine Intelligence, 23 (2001), 1222-1239.

[9]

P. CharbonnierL. Blanc-FeraudG. Aubert and M. Barlaud, Deterministic edge-preserving regularization in computed imaging, IEEE Transactions on Image Processing, 6 (1997), 298-311.

[10]

L. Condat, A direct algorithm for 1-D total variation denoising, IEEE Signal Processing Letters, 20 (2013), 1054-1057.

[11]

M. DangkulwanichT. IshibashiS. LiuM. L. KireevaL. LubkowskaM. 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.

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

[13]

L. Demaret, M. Storath and A. Weinmann, Reconstruction of piecewise constant signals by minimization of the l1-potts functional, arXiv: 1207.4642 (2012).

[14]

P. DjuricJ.-K. F. J.-K. FwuS. 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.

[15]

M. Douimi and H. Cherifi, Cutting enumerative algorithm for the minimizing of energy function, GRETSI, Trait. Signal, 15 (1998), 67-78.

[16]

C. G. Farquharson, Constructing piecewise-constant models in multidimensional minimum-structure inversions, Geophysics, 73 (2007), K1-K9.

[17]

D. Geiger and F. Girosi, Parallel and deterministic algorithms from mrfs: Surface reconstruction and integration, Computer Vision-ECCV, 90 (1990), 89-98.

[18]

S. Geman and D. Geman, Stochastic relaxation, gibbs distributions and the bayesian restoration of images, IEEE Trans. on PAMI, 6 (1984), 721-741.

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

[20]

B. JacksonB. 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.

[21]

M. A. LittleN. 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.

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

[23]

E. Pappalardo, B. A. Ozkok and P. M. Pardalos, Combinatorial optimization algorithms, In Handbook of Combinatorial Optimization, Springer New York, 2013, 559-593.

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

[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).

[26]

A. WeinmannM. 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.

[27]

G. WinklerO. WittichV. Liebscher and A. Kempe, Don't shed tears over breaks, Jahresber. Deutsch. Math.-Verein, 107 (2005), 57-87.

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.

[2]

A. J. AguirreC. BrennanG. BaileyR. SinhaB. FengC. LeoY. ZhangJ. ZhangJ. D. GansN. BardeesyC. CauwelsC. Cordon-CardoM. S. RedstonR. A. DePinho and L. Chin, High-resolution characterization of the pancreatic adenocarcinoma genome, Proceedings of the National Academy of Sciences, 101 (2004), 9067-9072.

[3]

D. M. G. AndersonZ. AblonczyY. KoutalosJ. SpragginsR. K. CrouchR. 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.

[4]

J. Besag, Statistical analysis of dirty pictures, Journal of Applied Statistics, 20 (1993), 63-87.

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

[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 edge-preserving MAP estimation, IEEE Transactions on Image Processing, 2 (1993), 296-310.

[8]

Y. BoykovO. Veksler and R. Zabih, Fast approximate energy minimization via graph cuts, IEEE Transactions on Pattern Analysis and Machine Intelligence, 23 (2001), 1222-1239.

[9]

P. CharbonnierL. Blanc-FeraudG. Aubert and M. Barlaud, Deterministic edge-preserving regularization in computed imaging, IEEE Transactions on Image Processing, 6 (1997), 298-311.

[10]

L. Condat, A direct algorithm for 1-D total variation denoising, IEEE Signal Processing Letters, 20 (2013), 1054-1057.

[11]

M. DangkulwanichT. IshibashiS. LiuM. L. KireevaL. LubkowskaM. 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.

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

[13]

L. Demaret, M. Storath and A. Weinmann, Reconstruction of piecewise constant signals by minimization of the l1-potts functional, arXiv: 1207.4642 (2012).

[14]

P. DjuricJ.-K. F. J.-K. FwuS. 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.

[15]

M. Douimi and H. Cherifi, Cutting enumerative algorithm for the minimizing of energy function, GRETSI, Trait. Signal, 15 (1998), 67-78.

[16]

C. G. Farquharson, Constructing piecewise-constant models in multidimensional minimum-structure inversions, Geophysics, 73 (2007), K1-K9.

[17]

D. Geiger and F. Girosi, Parallel and deterministic algorithms from mrfs: Surface reconstruction and integration, Computer Vision-ECCV, 90 (1990), 89-98.

[18]

S. Geman and D. Geman, Stochastic relaxation, gibbs distributions and the bayesian restoration of images, IEEE Trans. on PAMI, 6 (1984), 721-741.

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

[20]

B. JacksonB. 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.

[21]

M. A. LittleN. 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.

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

[23]

E. Pappalardo, B. A. Ozkok and P. M. Pardalos, Combinatorial optimization algorithms, In Handbook of Combinatorial Optimization, Springer New York, 2013, 559-593.

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

[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).

[26]

A. WeinmannM. 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.

[27]

G. WinklerO. WittichV. Liebscher and A. Kempe, Don't shed tears over breaks, Jahresber. Deutsch. Math.-Verein, 107 (2005), 57-87.

Figure 1.  (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
Figure 2.  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
Figure 3.  (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
Figure 4.  Number of solved matrices as a function of their size. The example restores a signal of size 1024 with 8 regularly distributed discontinuities
Figure 5.  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
Figure 6.  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
Figure 7.  Mean Square Error as a function of $\lambda$ and $h$
Figure 8.  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
Figure 9.  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
Figure 10.  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]

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

[4]

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

[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) : 767-799. doi: 10.3934/dcdsb.2011.16.767

[6]

Adil Bagirov, Sona Taheri, Soodabeh Asadi. A difference of convex optimization algorithm for piecewise linear regression. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-24. doi: 10.3934/jimo.2018077

[7]

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

[8]

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

[9]

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

[10]

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

[11]

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

[12]

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

[13]

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

[14]

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

[15]

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

[16]

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

[17]

Ł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

[18]

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

[19]

Jie Huang, Xiaoping Yang, Yunmei Chen. A fast algorithm for global minimization of maximum likelihood based on ultrasound image segmentation. Inverse Problems & Imaging, 2011, 5 (3) : 645-657. doi: 10.3934/ipi.2011.5.645

[20]

Sanming Liu, Zhijie Wang, Chongyang Liu. Proximal iterative Gaussian smoothing algorithm for a class of nonsmooth convex minimization problems. Numerical Algebra, Control & Optimization, 2015, 5 (1) : 79-89. doi: 10.3934/naco.2015.5.79

2017 Impact Factor: 1.465

Article outline

Figures and Tables

[Back to Top]