Jukka Suomela

Median filtering is equivalent to sorting

Manuscript · June 2014

author’s version arXiv.org

Abstract

This work shows that the following problems are equivalent, both in theory and in practice:

  • median filtering: given an $n$-element vector, compute the sliding window median with window size $k$,
  • piecewise sorting: given an $n$-element vector, divide it in $n/k$ blocks of length $k$ and sort each block.

By prior work, median filtering is known to be at least as hard as piecewise sorting: with a single median filter operation we can sort $\Theta(n/k)$ blocks of length $\Theta(k)$. The present work shows that median filtering is also as easy as piecewise sorting: we can do median filtering with one piecewise sorting operation and linear-time postprocessing. In particular, median filtering can directly benefit from the vast literature on sorting algorithms—for example, adaptive sorting algorithms imply adaptive median filtering algorithms.

The reduction is very efficient in practice—for random inputs the performance of the new sorting-based algorithm is on a par with the fastest heap-based algorithms, and for benign data distributions it typically outperforms prior algorithms.

The key technical idea is that we can represent the sliding window with a pair of sorted doubly-linked lists: we delete items from one list and add items to the other list. Deletions are easy; additions can be done efficiently if we reverse the time twice: First we construct the full list and delete the items in the reverse order. Then we undo each deletion with Knuth’s dancing links technique.

Links

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author’s copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.