Rank Order Filtering on Massively-Parallel Single-Bit Mesh Processor Arrays

Abstract

Rank order filters have a wide variety of applications in image processing as an effective tool for removing noise in images without severely distorting abrupt changes in the images. The k-th rank filter with an m x m window sets each pixel the k-th smallest value of the m2 pixels in its m x m neighborhood. The median filter is the most commonly used special case of rank order filters. Rank order filtering requires intensive computation. In this paper, we consider implementation of rank order filters on massively-parallel single-bit mesh-connected computers such as the Lockheed Martin Parallel Algebraic Logic (PAL) computer.

We design rank filtering algorithms using the threshold decomposition and radix splitting techniques. We map an n x n image onto an n x n single-bit mesh array with one pixel per processing element (PE). Suppose that the maximum pixel value is L. Using threshold decomposition technique, we can implement any rank filter in O((m log m + log L)L) time on a mesh processor array with O(log L + log m) bits of space on each PE. Using the radix splitting technique, we can implement any rank order filter in O(m2 log m log L ) time on a mesh processor array with O(log L + m2) bits of space on each PE. If the local space in each PE is limited to O(log L + log m) bits, we can have an O(m2 (log L + log m) log L) implementation. We also present some experimental results of the implementation of those algorithms on the PAL computer.