Fast rank algorithms

Maria V. Storozhilova, Dmitry V. Yurin

Rank algorithms are well-known approach to image enhancement, denoising, and some other applications. Whereas there is known a wide class of rank algorithms, only a small set of them such as min, max and median filters are frequently used in practice. More complex algorithms as mean by epsilon-V neighbourhood or mean by KNV- neighbourhood are used very rare, probably due to their computation complexity. On the other hand, there are known fast median filtering algorithms.

The target of our research is to develop fast rank algorithms. Based on multiscale histograms and using lazy histogram updating technique we developed fast calculation scheme for finding

  • Arbitrary rank element by neighbourhood
  • Mean by epsilon-V neighbourhood
  • Mean by KNV neighbourhood
  • Sliding equalization

Download source code (MS Visual Studio 2008 project)

Fast rank algorithms in use, image size 250x250 pixels:

klen4.png klen4_noise.png
Source image Image with added Gaussian noise

Easiest noise removal algorithms:

klen4_r3_median.png klen4_r3_sqAverage.png
r = 1, median filtering r = 1, mean by square neighborhood

Epsilon-V filtering:

klen4_r5_epsv10.png klen4_r5_epsv15.png
epsilon = 10 (too small), r = 2, Gaussian noise was not suppressed epsilon = 15 (good), r = 2, Most of Gaussian noise was suppressed, leaf boundaries remained sharp
klen4_r15_epsv15.png klen4_r15_epsv30.png
epsilon = 15 (good), r = 7, Most of Gaussian noise was suppressed, leaf boundaries remained sharp epsilon = 30 (too large), r = 7, Gaussian noise was suppressed, leaf boundaries remained sharp, but micro relief was eliminated

KNV filtering:

klen4_noise.png klen4_r15_KNV1_8.png
Image with added Gaussian noise K = 1/8N, r = 7, Gaussian noise was not suppressed
klen4_r15_KNV1_4.png klen4_r15_KNV1_3.png
K = 1/4N, r = 7, Gaussian noise was partially suppressed, sharp corners of the leaf (≤90°) were “rounded” K = 1/3N, r = 7, Gaussian noise was suppressed, sharp corners of the leaf (≤120°) were “rounded”

Publications

2013

M. V. Storozhilova, D. V. Yurin. “Fast Rank Algorithms Based on Multiscale Histograms and Lazy Calculations” // Pattern Recognition and Image Analysis, Vol. 23, No. 3, Pleiades Publishing, Ltd., 2013, p. 367–374. Springer.

2011

M. V. Storozhilova, D. V. Yurin. “Fast rank algorithms based on multiscale histograms” // In: 21-th International Conference on Computer Graphics GraphiCon'2011. Moscow, Russia, 2011, pp. 132−135. PDF.

M. Storozhilova, D. Yurin. “Fast Rank Algorithms with Multiscale Histograms Lazy Updating” // In: 8th Open German-Russian Workshop “Pattern Recognition and Image Understanding” (OGRW-8-2011). Lobachevsky State University of Nizhny Novgorod, November 21-26, 2011, 2011, pp. 280−283. PDF.