4
$\begingroup$

Let's begin with a little review of unweighted median filtering.

Suppose I have a list of $N$ real-valued numbers, $x=x_1,...,x_N$. Let $m_i$ be the median of $K$ consecutive values: $m_i=$ median$(x_i,...,x_{i+K})$. Let $m=(m_1,...,m_{N-K+1})$. The act of transforming $x$ to $m$ is called (unweighted) median filtering. We usually imagine $N\gg K$, and frequently we assume that $K$ is odd (so the median is unambiguously defined).

Median filtering is a useful smoothing technique in signal processing because it is robust against outliers; apparently the 2 dimensional analogue is useful in image processing because it smooths images while keeping edges relatively intact.

There is a naive $O(NK\log(K))$ algorithm to compute $m$ from $x$ (take each of the $O(N)$ windows $(x_i,...,x_{i+K})$, sort in $O(K\log(K))$ time, and report the medians). However, this performance can be substantially improved (both in theory and practice). The true complexity is $\Omega(N\log(K))$; see [Suomela, 2014] for an overview of algorithms that can achieve this (plus a clever, new algorithm).

I am interested in a closely (?) related problem, weighted median filtering. Given a set of $K$ weights, $w_1,...,w_K$, such that $\sum_i w_i=1$, and $w_i\geq 0$, the weighted median of a set $z_1,...,z_K$ is the $z_i$ such that $$\sum_{j: z_j<z_i}w_j<1/2$$ and $$\sum_{j: z_j\geq z_i}w_j\leq 1/2$$

Note that if all the $w_i=1/K$, then the weighted median reduces to the regular median.

The naive algorithm (where we treat each window of length $K$ separately) can compute the weighted median in $O(NK\log(K))$. As Emil points out, it is possible to compute the weighted median of a single set in $O(K)$ time (as outlined on the wikipedia page on weighted median), so one can improve this to $O(NK)$. My question is: Is there a more efficient algorithm?

A few notes:

  • If you assume that the $x_i$ take values over some small set, there are various special algorithms one can use. Unfortunately for me, my values will probably be largely distinct.
  • There is a paper by Zhang et al in 2014 with the promising title "100+ Times Faster Weighted Median Filter". If I'm reading their paper correctly, the results only apply to the 2 dimensional problem, and (in the language of this post) reduces the complexity from $O(NK)$ to $O(N\sqrt{K})$ (although it's not clear to me if this result holds in one dimension).
  • In typical usage, the weights form a window function of some sort, which typically has a largest weight in the middle of the window, and then shrinks towards either end. I would be very interest in a solution even if it only applied to this special case.
$\endgroup$
2
  • 1
    $\begingroup$ The Wikipedia page you link to tells me that weighted median can be computed in linear time, so the naive algorithm should be actually only $O(NK)$, right? $\endgroup$ Oct 23, 2015 at 17:19
  • $\begingroup$ Good point; I'll update the post. $\endgroup$ Oct 23, 2015 at 17:24

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.