The Median Filter Problem

Description:

    Image processing is a very important field within industrial automation, and more concretely, in the automated visual inspection. For example, automatically analyzing predetermined features of manufactured parts on an assembly line to look for defects and process variations [1]. In these applications, the main challenge normally is the requirement of real-time results.

    On the other hand, in many of these applications, the acquired images must pass through a stage of image preprocessing in order to remove distracting and useless information from the images. For example, the existence of impulsive noise in the images is one of the most habitual problems.

    Median filter is the nonlinear filter more used to remove the impulsive noise from an image [8], [4], [1]. Furthermore, it is a more robust method than the traditional linear filtering, because it preserves the sharp edges.

    Median filter is a spatial filtering operation, so it uses a 2-D mask that is applied to each pixel in the input image. To apply the mask means to centre it in a pixel, evaluating the covered pixel brightnesses and determining which brightness value is the median value. Figure presents the concept of spatial filtering based on a 3x3 mask, where I is the input image and O is the output image.

    The median value is determined by placing the brightnesses in ascending order and selecting the centre value [1]. The obtained median value will be the value for that pixel in the output image. Figure shows an example of the median filter application, as in this case, habitually a 3x3 median filter is used.

The optimization problem:

    The main problem of the median filter is its high computational cost (for sorting N pixels, the temporal complexity is O(N·log N), even with the most efficient sorting algorithms). When the median filter must be carried out in real time, the software implementation in general-purpose processors does not usually give good results. ASICs [6] have been required traditionally. However, they imply a limited functionality due to their predefined architecture. Also, the price for application as well as the production time are usually prohibitive.

    Reconfigurable computing architectures [7] are sufficiently flexible so that new operations can be implemented in the existent hardware, and they are quite quick for real-time execution. Moreover, the price/performance ratio of these systems makes them a broadly competitive alternative to ASICs. FPGAs [2] have been identified as the natural platform for CCMs [3] due to their reprogrammability [5].

    For these reasons, we believe that FPGAs are a good alternative to achieve the solution of this problem: the real-time implementation of median filter. This implementation will allow us to use this operation within automated visual inspection systems, maintaining the requirements of real-time operation and reduced cost so that these systems can be introduced into an industrial environment.

Related Papers:

[1] G.A. Baxes. “Digital Image Processing. Principles & Applications”, Wiley & Sons (1994).
[2] S.D. Brown, J. Rose. “FPGA and CLPD Architectures: A Tutorial”, IEEE Design & Test of Computers, 13(2), pp. 42-57 (1996).
[3] D.A. Buell, K.L. Pocek. “Custom Computing Machines: An Introduction”, Journal on Supercomput., 9, pp. 219-230 (1995).
[4] R.M. Haralick, L.G. Shapiro. “Computer and Robot Vision”, Addison-Wesley, vol. 1 (1992).
[5] S. Hauck. “The Roles of FPGAs in Reprogrammable Systems”, Proc. of IEEE, 86(4), pp. 615-638 (April 1998).
[6] M.J.S. Smith. “Application-Specific Integrated Circuits”, Addison-Wesley (1997).
[7] J. Villasenor, W.H. Mangione-Smith. “Configurable Computing”, Scientific American, 276(6), pp. 54-59 (June 1997).
[8] L. Yin, R. Yang, M. Gabbouj, Y. Neuvo. “Weighted Median Filters: A Tutorial”, IEEE Trans. on Circuits and Systems, 43(3), pp. 157-192 (March 1996).