Fast Algorithms for Change Detection using Robust Parameter Estimation

Research project P 13645 Fast Algorithmx for Change Detection Peter ZINTERHOF 28.06.1999 In computer systems for industrial or medical diagnostics, a crucial problem is t detect local changes in relevant data which are represented for processing in the form one-dimensional signals, two-dimensional signals (images) or three-dimensional signals (e.g., tomographs). The changes to be detected are considered with respect to both the time axis and the spatial coordinates. They represent possible flaws in the objects diagnostics and must be further analyzed in detail. Attention is paid to such two-dimensional signals as radiographic images and their sequences, where the local changes (objects) have a small size and a low contrast with superimposed noise. The know methods for radiographs analysis fail to detect reliably such changes. The project goal is development and analysis of time-efficient algorithms robust parameter estimation and change detection in noisy and low-contrast signals. T other aims of this project are as follows. Development and investigation of structural mathematical models of two-dimensional signals serving as a theoretical basis for design of fast algorithms for change detection. The mathematical models should adequate to real signals, concise for the purpose of simplicity of an algorithm design, and quite general to encompass a wide class of signals. Design and investigation of fast recursive algorithms for structure-adaptive filtering and reliable change detection in re time when the background of objects is noisy and non-homogeneous. The methodology to solve these problems consists of a creation of adaptive and fast algorithms for change detection based on adequate mathematical models of signals including explicitly the model parameters to be estimated in a robust way. A composite local model is used as the underlying image model which includes polynomial regression model of intensity function as well as structural model of local objects. The maximum posteriori probability approach for robust parameter estimation in the polynomial regression model is proposed in order to select best partial estimate out of all computed partial estimates in order to eliminate the influence of outliers. Having estimated model parameters, the basic test statistics for change detection like the local normalized contrast can be computed in a simple and robust way and used directly during generation and testing of structural statistical hypotheses. The hypothesis generation and testing should be organized in a hierarchical manner (as a tree structure) in order to ensure time-efficient detection and analysis. The fast algorithm design is based on a recursive computation of a given local function both along the time axis and over the coordinates on the image plane. Another basic principle for developing fast algorithms is that of using approximate version of t] local processing function which does not change the processing results or modify the slightly. Computation of the basic regression parameters per pixel can be implemented recursively (principle of translational recursion) as a linear filter by using the so-called primitive kernel functions. The class of primitive kernel functions allow to reduce t] computational complexity of filtering by an order, i.e. in O(L) times, with respect to direct implementation, where L is the initial filter size.