Module zune_imageprocs::median

source ·
Expand description

Applies a median filter of given dimensions to an image. Each output pixel is the median of the pixels in a (2 * radius + 1) * (2 * radius + 1) kernel of pixels in the input image.

Performs O(radius) operations per pixel

§Algorithm

A simple median function can be implemented by sorting items in a window and then picking the middle value, but then this has some not so good perfomance especially with large windows e.g if I were calculating a radius of 37, the window would be ((2*37)+1* (2*37)+1)) -> 75 * 75 -> 5625 values to sort on every window position, which no matter what computer, it’s gonna be slow

But one thing to note is that what happens from one window to another is that we drop the rightmost values and add the leftmost values

┌─┬───────────┬─┐
│ │           │ │
│ │           │ │
│ │           │ │
│ │           │ │
└─┴───────────┴─┘
▲             ▲
│             │
drop           add

So we can maintain a histogram of values in our window, the histogram tells us the frequencies of values in our windows on moving from one window to another, we drop the leftmost values, and add the rightmost

while this is still expensive, it is faster than sorting

Structs§

  • Median
    Median returns a new image in which each pixel is the median of its neighbors.

Functions§