Nonconvex Energy Minimization with Unsupervised Line Process Classifier for Efficient Piecewise Constant Signals Reconstruction
Abstract
In this paper, we focus on the problem of signal smoothing and step-detection for piecewise constant signals. This problem is central to several applications such as human activity analysis, speech or image analysis, and anomaly detection in genetics. We present a two-stage approach to minimize the well-known line process model which arises from the probabilistic representation of the signal and its segmentation. In the first stage, we minimize a TV least square problem to detect the majority of the continuous edges. In the second stage, we apply a combinatorial algorithm to filter all false jumps introduced by the TV solution. The performances of the proposed method were tested on several synthetic examples. In comparison to recent step-preserving denoising algorithms, the acceleration presents a superior speed and competitive step-detection quality.References
J. V. Braun, R. K. Braun, H. G. Muller, Multiple changepoint fitting via quasilikelihood, with application to dna sequence segmentation, Biometrika 87 (2) (2000) 301–314.
A. B. Olshen, E. S. Venkatraman, R. Lucito, M. Wigler, Circular binary segmentation for the analysis of array-based dna copy number data, Biostatistics 5 (4) (2004) 557–572.
M. A. Little, N. S. Jones, Sparse Bayesian step-filtering for high-throughput analysis of molecular machine dynamics, in: 2010 IEEE International Conference on Acoustics Speech and Signal Processing, IEEE, 2010.
Y. Zhang, M. Brady, S. Smith, Segmentation of brain MR images through a hidden Markov random field model and the expectation-maximization algorithm, IEEE Transactions on Medical Imaging 20 (1) (2001) 45–57.
E. Andreou, E. Ghysels, Detecting multiple breaks in financial market volatility dynamics, Journal of Applied Econometrics 17 (5) (2002) 579–600.
L. Meligkotsidou, E. Tzavalis, I. Vrontos, On Bayesian analysis and unit root testing for autoregressive models in the presence of multiple structural breaks, Econometrics and Statistics (May 2017).
R. Ramlau, W. Ring, A mumford–shah level-set approach for the inversion and segmentation of x-ray tomography data, Journal of Computational Physics 221 (2) (2007) 539–557.
S. I. Kabanikhin, Inverse and Ill-posed Problems, Theory and Applications, DE GRUYTER, Berlin, Boston, 2011.
K. Hohm, M. Storath, A. Weinmann, An algorithmic framework for Mumford–Shah regularization of inverse problems in imaging, Inverse Problems 31 (11) (2015) 115011.
M. Storath, A. Weinmann, J. Frikel, M. Unser, Joint image reconstruction and segmentation using the Potts model, Inverse Problems 31 (2) (2015) 025003.
R. Szeliski, R. Zabih, D. Scharstein, O. Veksler, V. Kolmogorov, A. Agarwala, M. Tappen, C. Rother, A comparative study of energy minimization methods for markov random fields, in: Computer Vision – ECCV 2006, Springer Berlin Heidelberg, 2006, pp. 16–29.
O. Veksler, Graph cut based optimization for MRFs with truncated convex priors, in: 2007 IEEE Conference on Computer Vision and Pattern Recognition, IEEE, 2007.
M. Nikolova, Energy minimization methods, in: Handbook of Mathematical Methods in Imaging, Springer New York, 2011, pp. 139–185.
C. Deledalle, S. Vaiter, G. Peyré, J. Fadili, C. Dossal, Unbiased risk estimation for sparse analysis regularization, in: 2012 19th IEEE International Conference on Image Processing, 2012, pp. 3053–3056.
V. Kolmogorov, R. Zabih, Computing visual correspondence with occlusions using graph cuts, in: Proceedings Eighth IEEE International Conference on Computer Vision. ICCV, IEEE Comput. Soc, 2001.
S. Geman, D. Geman, Stochastic relaxation, gibbs distributions, and the bayesian restoration of images, IEEE Transactions on Pattern Analysis and Machine Intelligence PAMI-6 (6) (1984) 721–741.
A. Blake, P. Kohli, C. Rother, Markov Random Fields for Vision and Image Processing, The MIT Press, 2011.
M. Nikolova, M. K. Ng, C.-P. Tam, Fast nonconvex nonsmooth minimization methods for image restoration and reconstruction, IEEE Transactions on Image Processing 19 (12) (2010) 3073–3088.
A. Blake, A. Zisserman, Visual Reconstruction, MIT Press, Cambridge, MA, USA, 1987.
Y. Boykov, O. Veksler, R. Zabih, Fast approximate energy minimization via graph cuts, IEEE Transactions on Pattern Analysis and Machine Intelligence 23 (11) (2001) 1222–1239.
M. Nikolova, Markovian reconstruction using a GNC approach, IEEE Transactions on Image Processing 8 (9) (1999) 1204–1220.
T. Pock, A. Chambolle, D. Cremers, H. Bischof, A convex relaxation approach for computing minimal partitions, in: 2009 IEEE Conference on Computer Vision and Pattern Recognition, IEEE, 2009.
M. Hurn, C. Jennison, An extension of Geman and Reynolds’ approach to constrained restoration and the recovery of discontinuities, IEEE Transactions on Pattern Analysis and Machine Intelligence 18 (6) (1996) 657–662.
V. Kolmogorov, Convergent tree-reweighted message passing for energy minimization, IEEE Transactions on Pattern Analysis and Machine Intelligence 28 (10) (2006) 1568–1583.
Y. Boykov, V. Kolmogorov, An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision, in: Lecture Notes in Computer Science, Springer Berlin Heidelberg, 2001, pp. 359–374.
M. Douimi, H. Cherifi, Cutting enumerative algorithm for the minimizing of energy function., GRETSI, Trait. Signal 15 (1) (1998) 67–78.
M. A. Little, N. S. Jones, Generalized methods and solvers for noise removal from piecewise constant signals. i. background theory, Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 467 (2135) (2011) 3088–3114.
M. A. Little, N. S. Jones, Generalized methods and solvers for noise removal from piecewise constant signals. II. new methods, Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 467 (2135) (2011) 3115–3140.
L. Condat, A direct algorithm for 1-d total variation denoising, IEEE Signal Processing Letters 20 (11) (2013) 1054–1057.
I. W. Selesnick, A. Parekh, I. Bayram, Convex 1-d total variation denoising with non-convex regularization, IEEE Signal Processing Letters 22 (2) (2015) 141–144.
M. Malek-Mohammadi, C. R. Rojas, B. Wahlberg, A class of nonconvex penalties preserving overall convexity in optimization-based mean filtering, IEEE Transactions on Signal Processing 64 (24) (2016) 6650–6664.
J. Rosskopf, K. Paul-Yuan, M. B. Plenio, J. Michaelis, Energy-based scheme for reconstruction of piecewise constant signals observed in the movement of molecular machines, Physical Review E 94 (2) (aug 2016).
C. Couprie, L. Grady, L. Najman, J.-C. Pesquet, H. Talbot, Dual constrained TV-based regularization on graphs, SIAM Journal on Imaging Sciences 6 (3) (2013) 1246–1273.
L. I. Rudin, S. Osher, E. Fatemi, Nonlinear total variation based noise removal algorithms, Physica D: nonlinear phenomena 60 (1-4) (1992) 259–268.
A. Chambolle, V. Caselles, D. Cremers, M. Novaga, T. Pock, An introduction to total variation for image analysis, Theoretical foundations and numerical methods for sparse recovery 9 (263-340) (2010) 227.
R. Gribonval, Should penalized least squares regression be interpreted as maximum a posteriori estimation?, IEEE Transactions on Signal Processing 59 (5) (2011) 2405–2410.
C. R. Vogel, M. E. Oman, Iterative methods for total variation denoising, SIAM Journal on Scientific Computing 17 (1)(1996) 227–238.
H. H. Bauschke, P. L. Combettes, et al., Convex analysis and monotone operator theory in Hilbert spaces, Vol. 408, Springer, 2011.
K. Thulasiraman, S. Arumugam, T. Nishizeki, A. Brandstädt, et al., Handbook of Graph Theory, Combinatorial Optimization, and Algorithms., Taylor & Francis, 2016.
Y. R. Chemla, K. Aathavan, J. Michaelis, S. Grimes, P. J. Jardine, D. L. Anderson, C. Bustamante, Mechanism of force generation of a viral dna packaging motor, Cell 122 (5) (2005) 683–692.
J. D. Watson, Molecular biology of the gene, Vol. 1, Pearson Education India, 2004.
R. Killick, P. Fearnhead, I. A. Eckley, Optimal detection of changepoints with a linear computational cost, Journal of the American Statistical Association 107 (500) (2012) 1590–1598.
J. Bai, Estimating multiple breaks one at a time, Econometric theory 13 (3) (1997) 315–352.
P. Fryzlewicz, et al., Wild binary segmentation for multiple change-point detection, The Annals of Statistics 42 (6) (2014) 2243–2281.
F. Desobry, M. Davy, C. Doncarli, An online kernel change detection algorithm, IEEE Trans. Signal Processing 53 (8-2) (2005) 2961–2974.
P. Fryzlewicz, Unbalanced haar technique for nonparametric function estimation, Journal of the American Statistical Association 102 (480) (2007) 1318–1327.
C. Truong, L. Oudre, N. Vayatis, Selective review of offline change point detection methods, Signal Processing 167 (2020) 107299.
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
