DP: a Fast Median Filter Approximation

Ryan Marcus, William Ward2013 · DOI

TL;DR

This paper introduces "DP," a novel, non-discrete algorithm for approximating median filters. DP offers a significant speedup over existing fast median filter algorithms without requiring data discretization, making it suitable for applications like computed tomography that use floating-point data.

What Problem Does This Paper Address?

Median filters are powerful tools for noise reduction in images, but they are notoriously computationally expensive. This high computational cost limits their use in real-time applications or large-scale batch processing. While several "fast" median filter algorithms exist, many rely on discretizing image data into histogram bins, which is unsuitable for applications dealing with continuous data like floating-point values found in computed tomography. Other approaches use efficient sorting for small datasets or statistical methods, but these can offer varying accuracy. This paper addresses the need for a fast median filter approximation that works with continuous data and provides quantifiable error bounds.

Methods

The core of this paper is the introduction of the "DP" (Dynamic Programming, though not explicitly stated as such, the description implies this approach) algorithm. DP approximates a median filter by processing an image using a sliding kernel (e.g., 3x3). Unlike histogram-based methods, DP does not maintain a histogram. Instead, it cleverly exploits data overlap between successive kernel positions. As the kernel slides one column to the right, DP discards the median of the leftmost column of the previous kernel's window and calculates the median of the new rightmost column. The approximate median of the entire kernel is then derived from the medians of a few key columns. This approach avoids data discretization and is designed for efficiency. The paper also rigorously analyzes the accuracy of DP, providing mathematical bounds on how close the approximated median is to the true median.

Datasets

Not discussed in the paper. The paper focuses on algorithm development and theoretical analysis, with performance benchmarks presented on generic image sizes rather than specific named datasets.

Key Insights and Ideas

  • Non-Discretization is Key: The most significant insight is that a fast median filter approximation can be achieved without discretizing the input data. This opens up median filtering to a broader range of applications, particularly those using floating-point data.
  • Exploiting Data Overlap: The DP algorithm's efficiency stems from its ability to reuse computations from previous kernel positions, a common theme in dynamic programming and sliding window algorithms.
  • Quantifiable Error Bounds: The paper doesn't just claim speed; it provides a solid mathematical framework to prove that the DP approximation is not arbitrary. The bounds derived (α and β) give users a clear understanding of the potential deviation from the true median.
  • Trade-off Between Speed and Precision: The paper implicitly highlights the inherent trade-off in approximation algorithms: gaining speed often means sacrificing perfect accuracy. DP aims to strike a favorable balance.

Key Results

  • Speed: The DP algorithm is demonstrated to be faster than implementations of several other fast median filter algorithms, including those by Huang, Dong, and Narendra, as shown in benchmark tests (Table 4 and Figure 2). For instance, on a 5000x5000 image, DP achieved a time of 0.46s, significantly outperforming Huang (5.693s) and Narendra (0.653s).
  • Accuracy: While not always finding the exact median, DP guarantees a value within known bounds (α and β). For a 7x7 kernel, DP selects a value within one index of the median 51.9% of the time and within four indices of the median 96.2% of the time.
  • Versatility: The algorithm is designed to work with arbitrary kernel sizes, though proofs focus on odd-sized square kernels.

Limitations and Future Work

  • Approximation, Not Exact: The primary limitation is that DP is an approximation algorithm and does not guarantee the exact median. However, the paper provides clear error bounds to manage this.
  • Focus on Square Kernels: While the algorithm can handle arbitrary kernels, the theoretical proofs and analysis are primarily focused on square kernels of odd side length.
  • Future Work: The paper suggests that further investigation into other approximation algorithms not covered in this study could be beneficial. The authors also imply that the performance of DP could be further optimized, as it compares favorably to existing methods.

Summary updated

Abstract

We present a new non-discrete algorithm that quickly approximates a median filter. This new algorithm proves to be faster than our implementations of many other fast median filter algorithms.
BibTeX
@misc{marcus2013dp,
  author = {Ryan Marcus and William Ward},
  title = {{DP: a Fast Median Filter Approximation}},
  year = {2013},
  doi = {10.2172/1088342},
}
Figure