publications

2021

1. EnVar

   Constrained energy variation for change point detection

   A. Belcaid, and H. Belkbir

   Multidimensional Systems and Signal Processing, Jul 2021

   Abs HTML

   The problem of change point detection can be solved either by online methods, based on a discrepancy measure, or by offline methods. The former tries to detect the change points one by one with a sliding window and leads to a lower computational time but are more sensitive to noise. Conversely, offline methods consider the entire data to detect all the change points which make them more robust against the noise but at a price of higher computational cost. In this paper, we propose an operational search method that combines the benefits of both approaches with the double aim to get higher noise resistance while keeping a blazingly fast time. The search method slides over the edges of the signal to determines their state by considering a global constrained energy. Thanks to the calculus of variation, the computation of this energy is reduced to the estimation of the effective jump for each edge. We study the performance and accuracy of our energy variation method to detect the change points in synthetic and real-world examples. The results compare favorably against state of the art algorithm in terms of speed and accuracy.

2. LPclass

   Nonconvex Energy Minimization with Unsupervised Line Process Classifier for Efficient Piecewise Constant Signals Reconstruction

   A. Belcaid, and M. Douimi

   Statistics, Optimization & Information Computing, Mar 2021

   Abs HTML

   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.

2020

1. OCPC

   A Novel Online Change Point Detection Using an Approximate Random Blanket and the Line Process Energy

   A. Belcaid, and M. Douimi

   International Journal on Artificial Intelligence Tools, Sep 2020

   Abs HTML

   In this paper, we focus on the problem of change point detection in 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 novel window-sliding algorithm for an online change point detection. The proposed approach considers a local blanket of a global Markov Random Field (MRF) representing the signal and its noisy observation. For each window, we define and solve the local energy minimization problem to deduce the gradient on each edge of the MRF graph. The gradient is then processed by an activation function to filter the weak features and produce the final jumps. We demonstrate the effectiveness of our method by comparing its running time and several detection metrics with state of the art algorithms.

2018

1. dpsfil

   A DPS filter for nonconvex edge preserving for PieceWise constant signals denoising

   A. Belcaid, M. Douimi, and E. Zemmouri

   In 2018 4th International Conference on Optimization and Applications (ICOA), Apr 2018

   Abs HTML

   A robust estimator, namely the DPS algorithm, for piecewise constant signals denoising, is revised in this paper. Starting from its Markov random field formulation, which defines the solution as the global minimizer of a non-convex non-smooth energy function. The DPS algorithm transforms the line process mixed energy into a discrete optimization problem and proposes a BFS search strategy to find the optimal state. We develop a numerical scheme to replace the BFS search by a simple linear scan over the edges of the MRF. Each visit to an edge considers a local blanket of the MRF and then computes the estimated signal around the vicinity of the edge. The gradient of the solution will decide the existence or absence of a discontinuity based on a threshold. Theoretical results shows that the new implementation has a linear time and space complexity, but the local aspect reduces the robustness of the method against noise. A set of numerical simulations assist to show the reduction in time compared to the classical implementation and to compare the restoration quality against state-of-the-art algorithms.

2. recDps

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

   A. Belcaid,  M. Douimi, and A. Fihri

   Inverse Problems & Imaging, Apr 2018

   Abs HTML

   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.

2017

1. dpsExt

   A DPS extension to restore blurred and noisy piecewise constant signals

   A. Belcaid, M. Douimi, and E. Zemmouri

   Inverse Problems in Science and Engineering, Nov 2017

   Abs HTML

   In this paper, we are interested in restoring piecewise constant signals obtained from a linear operator A (e.g. a blurring operator) and degraded by a white Gaussian noise. The number of plateaus and their values are unknown. So the problem could be tackled as a joint restoration and unsupervised segmentation in the context of linear inverse problems. The DPS algorithm is a combinatorial algorithm proposed to solve the classical case, where the linear operator is reduced to I. The solution is computed as a global minimizer of an energy function that contains a quadratic fidelity term and a non-convex pairwise potential term. DPS offers a faster alternative to the GNC algorithm that minimizes the same energy in a continuation deterministic approach. We present an extension to the DPS algorithm for the general case. This extension only requires the regularity of the matrix , unlike the GNC extension that needs further computation of its smallest eigenvalue in order to formulate a convex relaxation. Also, we present a message passing and shared memory implementation to speed up the running time for high dimension signals. The parallelization is possible since DPS evaluate the energy on a set of nodes in a given hypercube, and in each level of the hypercube, the nodes are independents.