### Background closes #320 This PR adds a fast histogram-based median filter. It is based on a paper by Oded Green [1] as available in [`opencv_contrib`](https://github.com/opencv/opencv_contrib/blob/4.x/modules/cudafilters/src/cuda/median_filter.cu). It is a GPU-based adaptation of an earlier CPU-based publication [2]. This new functionality has been added to the existing `median` function and will be automatically used when possible (although the user can override the automated choice via a new keyword-only `algorithm` parameter. The CUDA file [here](https://github.com/opencv/opencv_contrib/blob/4.x/modules/cudafilters/src/cuda/median_filter.cu) has a BSD 3-clause license up top, although the repository states that it is Apache 2.0 licensed, so that is likely out of date. We do already list OpenCV's extra modules and the Apache 2.0 license for it in our 3rdparty license folder. ### References [1] O. Green, "Efficient Scalable Median Filtering Using Histogram-Based Operations," in IEEE Transactions on Image Processing, vol. 27, no. 5, pp. 2217-2228, May 2018, https://doi.org/10.1109/TIP.2017.2781375. [2] S. Perreault and P. Hebert, "Median Filtering in Constant Time," in IEEE Transactions on Image Processing, vol. 16, no. 9, pp. 2389-2394, Sept. 2007, https://doi.org/10.1109/TIP.2007.902329. ### Improvements There are a number of generalizations in the implementation here as compared to the one in OpenCV: - supports odd-sized rectangular footprints as well as square ones - supports int8, uint16 and int16 in addition to uint8 - the dtype used to store the histogram counts is adapted to the filter's footprint size - handles many additional boundary extension modes via explicit pre-pad and post-crop (in principle could adapt the kernel for each case to avoid this overhead, but likely not worth the substantial additional effort) - automatically switches between the sorting-based and histogram-based implementations depending on kernel size (sorting is much faster for very small kernels while the histogram-based approach is much faster for large ones) ### Notes/Limitations The GPU I tested this on has a static shared memory limit of 48k per block. This means that the `HFine` shared memory array can exceed the available GPU memory once there are more than ~12000 gray levels in the histogram. So, for int16 or uint16, we I can only run the algorithm on images where the min/max range does not exceed that value. One fairly common case in medical imaging is DICOM images with 12-bit range (0-4095) that are stored at 16-bit int. This shared memory limit is compatible with this case. ### Performance see summary in the next comment Authors: - Gregory Lee (https://github.com/grlee77) Approvers: - Gigon Bae (https://github.com/gigony) - https://github.com/jakirkham URL: #317

[FEA] fast histogram-based median implementation #320

Description

Activity

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions