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:

Source image		Image with added Gaussian noise

Easiest noise removal algorithms:

r = 1, median filtering		r = 1, mean by square neighborhood

Epsilon-V filtering:

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
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:

Image with added Gaussian noise		K = 1/8N, r = 7, Gaussian noise was not suppressed
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.