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 i s proposed for efficient running-median calculation in digital monochr ome images whose number of levels is considerably large, such as medic al images, SAR images, or 2-D data maps. The first step borrows the co ncept of sliding window for fast update of the local histogram, as wel l as the strategy of percentile upgrade for fast median retrieval, and provides a coarse estimate of the actual median which is refined in t he second stage, involving only a limited portion of the histogram. Co mparisons in terms of theoretical number of operations evidence a comp uting time O(L2) instead of O(L), where L = L1.L2 is the number of lev els, 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 histo gram-based schemes and sorting algorithms are prohibitively time-consu ming, as it happens in some practical image processing applications.