Code Monkey home page Code Monkey logo

medianfilter's Introduction

Median Filter

Build

mkdir build
cd build
cmake ...
make

Run

./MedianFilter --radius 25 --filepath ../resources/cat.bmp --algorithm constant

For the example above, we run a median filter with a radius of 25 on the picture of the cat at the relative path ../resources/cat.bmp, using an algorithm with asymptotics O(1). The following algorithms are available:

  • simple - a naive implementation of the median filter
  • huang - an algorithm by Huang et al.
  • constant - algorithm O(1)
  • opencv - implementation of opencv (for tests)

Examples for radii 9 and 25 can be found in folder resources. There you can also find a picture of the cat.

The results of the program work the same for all the above described algorithms.

Benchmark

To compare the speeds I have also written a simple benchmark in Python, it is located in the folder benchmark. An example of running it:

``bash python3 main.py --program-path ../cmake-build-release-system/MedianFilter --image-path ../resources/cat.bmp


The `requirements.txt` contains all the required modules for the
benchmark. In the same folder you can find the graphs of the dependencies
of the algorithms performance (msec/megapixel)
on the window radius. For the `simple` algorithm the benchmark was not
was not run for R > 10 due to non-optimality of the algorithm.

### Actual asymptotics

Let an image `h x w` be given, a filter of radius `R`. 
Consider the image as a three-channel image. Then 

- `simple`:
`O(h * w * R * logR)`

- `huang`:
`O(h * w * R)`

- `constant`
`O(h * w)`.

And the last two estimates are amortized because
window initialization may take `O(R^2)`, but further
pass will take `O(R)` and `O(1)` (respectively
for algorithms)
for each step of the pass.

### Optimal composition of algorithms

The graphs show that with ` R > 100` the algorithm
`constant` performs better than `huang`. It makes sense, because
For small R in `huang` we have to go through a smaller
number of values (by `O(R)` values, instead of `256`).

It is clear that the given implementation is far from optimal.
When optimizing algorithms, this bound may change.
But in this situation it is `R = 100`. Up to it we should
use `huang`, after it `constant`.

medianfilter's People

Contributors

jungletryne avatar

Watchers

 avatar  avatar

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    ๐Ÿ–– Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. ๐Ÿ“Š๐Ÿ“ˆ๐ŸŽ‰

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google โค๏ธ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.