Smoothing for signals with discontinuities using higher order Mumford–Shah models
Smoothing for signals with discontinuities using higher order Mumford–Shah models
复制标题
DOI：
10.1007/s00211-019-01052-8
复制
发表时间：
2018-03
影响因子：
2.1
通讯作者：
M. Storath;Lukas Kiefer;A. Weinmann
中科院分区：
文献类型：
--
作者：
M. Storath;Lukas Kiefer;A. Weinmann
最小化Mumford-Shah泛函经常用于平滑具有不连续性的信号或时间序列。标准Mumford-Shah模型的一个重要局限性是数据中的线性趋势（以及一般的多项式趋势）不能很好地保留。这可以通过建立更高阶的样条来改进，这导致更高阶的Mumford-Shah模型。在这项工作中，我们研究这些模型在单变量的情况下：我们讨论了重要的区别，一阶Mumford-Shah模型，我们得到的唯一性结果，他们的解决方案。作为一个主要的贡献，我们得到快速极小化算法的任意阶Mumford-Shah模型。我们表明，所有建议的计划的最坏情况下的复杂性是二次的信号的长度。值得注意的是，它们因此实现了分段常数Mumford-Shah模型（这是该类中最简单的模型）的最快求解器的最坏情况复杂度。此外，我们得到的稳定性结果所提出的算法。我们补充这些结果与数值研究。我们的参考实现在不到1秒的时间内处理超过10，000个元素的信号。
Minimizing the Mumford–Shah functional is frequently used for smoothing signals or time series with discontinuities. A significant limitation of the standard Mumford–Shah model is that linear trends—and in general polynomial trends—in the data are not well preserved. This can be improved by building on splines of higher order which leads to higher order Mumford–Shah models. In this work, we study these models in the univariate situation: we discuss important differences to the first order Mumford–Shah model, and we obtain uniqueness results for their solutions. As a main contribution, we derive fast minimization algorithms for Mumford–Shah models of arbitrary orders. We show that the worst case complexity of all proposed schemes is quadratic in the length of the signal. Remarkably, they thus achieve the worst case complexity of the fastest solver for the piecewise constant Mumford–Shah model (which is the simplest model of the class). Further, we obtain stability results for the proposed algorithms. We complement these results with a numerical study. Our reference implementation processes signals with more than 10,000 elements in less than 1 s.