A coarse-to-fine algorithm for fast median filtering of image data with a huge number of levels

A two-step algorithm exploiting a reduced local grey-level histogram is proposed for efficient running-median calculation in digital monochrome images whose number of levels is considerably large, such as medical images, SAR images, or 2-D data maps. The first step borrows the concept of sliding window for fast update of the local histogram, as well as the strategy of percentile upgrade for fast median retrieval, and provides a coarse estimate of the actual median which is refined in the second stage, involving only a limited portion of the histogram. Comparisons in terms of theoretical number of operations evidence a computing time O(L2) instead of O(L), where L = L1.L2 is the number of levels, and L1 is the size of the reduced histogram. Also computer tests validate the ideal relationship and suggest a practical factorization criterion of the local histogram, when dealing with natural correlated images. Experimental results substantially prove the validity of the novel algorithm as a feasible alternative, for calculation of any rank-order value, to level-sorting techniques, whenever both classic histogram-based schemes and sorting algorithms are prohibitively time-consuming, as it happens in some practical image processing applications.