Hier finden Sie wissenschaftliche Publikationen aus den Fraunhofer-Instituten.

Fast and memory-efficient quantile filter for data in three and higher dimensions

: Mosbach, D.; Hagen, H.; Godehardt, M.; Wirjadi, O.


Institute of Electrical and Electronics Engineers -IEEE-; IEEE Signal Processing Society:
IEEE International Conference on Image Processing, ICIP 2014. Proceedings. Vol.4 : 27-30 October 2014, Paris, France
Piscataway, NJ: IEEE, 2014
ISBN: 978-1-4799-5751-4
ISBN: 978-1-4799-5752-1
International Conference on Image Processing (ICIP) <21, 2014, Paris>
Fraunhofer ITWM ()

Quantile and median filters are usually implemented by accumulating a histogram in a mask with side length 2r + 1, and then selecting the desired quantile from the histogram. Fully updating the histogram for every pixel in a d-dimensional image leads to an O(rd) algorithm per pixel. Huang et al. proposed to shift the histogram pixel-by-pixel to reduce the complexity to O(rd-1) per pixel. We also show how to transfer their algorithm to higher dimensions, in this contribution. Perreault and Hébert extended this idea to reach O(1) runtime per pixel in arbitrary dimension. Thus, from an algorithmic point of view, quantile filtering of d-dimensional data is a solved problem. But the memory requirements of that algorithm grow with a power of D - 1. In this contribution, we therefore propose a novel hybrid quantile filter algorithm which is situated between the two aforementioned methods in terms of memory requirements, and which is faster for a wide range of mask sizes due to reduced overhead.