Translator Disclaimer
21 March 1989 Fast Implementation Of Ranked Filters On General-Purpose Image Processing Hardware
Author Affiliations +
Proceedings Volume 1004, Automated Inspection and High-Speed Vision Architectures II; (1989)
Event: 1988 Cambridge Symposium on Advances in Intelligent Robotics Systems, 1988, Boston, MA, United States
The median filter is one widely-used member of the class of ranked-intensity filters. Such filters are useful in signal processing, and particularly in machine vision, because they effectively remove an important and difficult-to-deal-with kind of noise, called variously "spike" noise or "salt-and-pepper" noise. By their nature, these filters are nonlinear. Filters involving linear operations, such as convolution - a weighted summation of the pixels in a neighborhood - can be done incrementally, and hence lend themselves to implementation on fast "pipelined" architectures. Two special cases of ranked-intensity filters, the "maximum" and "minimum" filters, can also be implemented incrementally. In contrast, the general ranked-intensity filter requires a sorting process over all pixels in the neighborhood. The usual "bubble sort" algorithm requires n passes and n*(n-1)/2 separate comparisons to fully determine the rank of all pixels in an n-pixel neighborhood. More efficient algorithms are known, but these also require multiple passes. As a result, software implementations of ranked-intensity filters are slow, and the hardware implementations now becoming available require special boards or chips devoted to that function alone. This paper presents improved sorting algorithms for ranked-intensity filters, and shows various practical techniques for implementation of these algorithms on existing fast multi-purpose image processing hardware. While not as fast as a dedicated hardware implementation, the resulting system is considerably faster than a software implementation, and yet it retains the general-purpose character of software systems. This makes it useful for laboratory algorithm development systems and for near-real-time applications. The same algorithms could also be used to design more efficient custom hardware or provide faster software implementations.
© (1989) COPYRIGHT Society of Photo-Optical Instrumentation Engineers (SPIE). Downloading of the abstract is permitted for personal use only.
Frederick M. Waltz "Fast Implementation Of Ranked Filters On General-Purpose Image Processing Hardware", Proc. SPIE 1004, Automated Inspection and High-Speed Vision Architectures II, (21 March 1989);

Back to Top