Algorithms and Hardware for Efficient Image Smoothing

This work develops some algorithms for efficient implementation of mean and separable median filters for image noise smoothing. The procedures suggested use one-dimensional algorithms repeatedly to obtain two-dimensional mean and separable median in ≤4 and 4 [log2(n+1)]-2 operations, respectively, for an n x n square neighborhood (nbhd). A simple generalization of the algorithms to k dimensions shows that at most 2k and k(2 [log2(n+1)]-1) operations are required for obtaining the mean and separable median of an n k nbhd. However, parallel processing can be easily applied to these algorithms. Given only five parallel processors, less than one operation is required to obtain the sum of an n x n nbhd in two dimensions, and for n ≤ 31 the maximum number of comparisons required to obtain the two-dimensional separable median filter of an n x n nbhd is reduced to less than four. Experimentally we demonstrate that the separable median filter' performs better than median filter for certain classes of images. A simple hardware implementation of the above algorithm is also outlined. It is seen that the complexity of this implementation increases linearly depending on the number of inputs, unlike sort-based implementations whose complexity increases exponentially