Abstract

The class of median-related operators called the stack filters are well-known for outperforming linear filtering in many applications which involve restoration of signals corrupted with impulsive noise, when sharp edges are to be preserved. Various subclasses of stack filters, such as the rank order operators and the weighted median filters, show a great deal of promise in finding commercial applications in image processing and image sequence filtering for advanced television systems. Moreover, the stark filters being closely related to morphological signal processing, the theory of their design and implementation constitutes a very attractive framework for the development of algorithms for low-level machine vision. This thesis, therefore, is concerned with the problems of efficient design and implementation of stack filters. The focus is on exploring the possibility of using the L p norm optimality criterion for the design of stack filters, and on the development of hardware-oriented algorithms for the implementation of these filters. The problem of designing optimal stack filters by employing a general objective function given as the L p norm of the error between the desired signal and the estimated one is addressed. This design problem is formulated as an optimization problem, in which a positive Boolean function is determined such that the L p norm of the error in signal estimation using stack filters is minimized. It is shown that the L p norm can be expressed as a linear combination of the responses of the positive Boolean function to all possible binary input vectors. Based on this error formulation, it is established that an L p -norm optimal stack filter can be determined as the solution of a linear program. It is shown that for the specific problem of restoring images corrupted with impulsive noise, the L p -optimal stack filters with p Y 2 are capable of removing the noise much more effectively and provide a better visual performance than achieved by the conventional minimum mean absolute error stack filters. The time-area complexities of the conventional parallel and bit-serial algorithms for stack filtering depend on the number of grey levels of an input image (signal). In this thesis, two new hardware-oriented algorithms for multidimensional stack filtering, for which the time-area complexity depends on the size of the filter, are developed. The new algorithms achieve significantly increased computational efficiency compared to the conventional algorithms for stack filtering by evaluating the Boolean function at thresholds corresponding to the sample-values within the filter-window and by taking advantage of the fact that, in most image processing applications, many pixels appearing in a filter-window assume non-distinct values. In one algorithm, the output of the filter is determined iteratively by employing a divide-and-conquer strategy. This strategy is based on successively partitioning the filter window into two sets with elements larger and smaller than the current threshold level, respectively. The other algorithm uses a binary tree search method for stack filtering in conjunction with a technique of compressing the dynamic range of the window samples. Motivated by the fact that in typical images, the details of the scene are locally situated, a hardware-oriented design and implementation of locally optimal mean absolute error rank order filters is developed and applied to the problem of intrafield deinterlacing of video signals.