NDLI: Branchless vectorized median filtering

Content Provider	IEEE Xplore Digital Library
Author	Kachelriess, M.
Copyright Year	2009
Description	Author affiliation: Institute of Medical Physics (IMP), University of Erlangen-Nu¿rnberg, Henkestr. 91, 91052 Erlangen, Germany (Kachelriess, M.)
Abstract	Median filtering is an important tool in signal or image processing. Based on the vector capabilities of modern hardware, which allows for vectorized min, max and mask operations, we provide a median algorithm of complexity O(NM) that is both branchless and vectorized. In contrast to conventional fast median filters, whose run-time is data-dependent and that can operate only on scalar data, its runtime is predictable and data-independent and it can simultaneously operate on several one-dimensional signals thereby making use of data-level parallelism. Our branchless vectorized median (BVM) filter keeps track of a sorted array from which values are deleted and to which new values are inserted. As a spin-off effect we could also use our work to provide a data sorting algorithm that is branchless and vectorized. Although it is of $O(M^{2})$ computational complexity while other sort algorithms are of O(M lnM) computational complexity, at least for typical data, it may outperform other implementations for small M. This is mainly due to the fact that we have no unexpected branches which would stall the instruction pipeline and that we can simultaneously operate on vectors of data. Here, however, we focus on median filtering. BVM is compared to a median filter based on doubly linked lists (DLL) and to the median implementation of the Intel Performance Primitives (IPP) library. The comparison uses constant data and linear data, which are two unrealistic settings, and random data, which is more realistic. For constant data IPP is up to five times faster than BVM whose run-time does not depend on the data themselves. However, regarding the realistic case of median filtering noisy data BVM outperforms DLL by about a factor of 1.5 and IPP by about a factor of 2 in our CPU-based implementations, which is far more than we did expect initially.
Starting Page	4099
Ending Page	4105
File Size	152536
Page Count	7
File Format	PDF
ISBN	9781424439614
ISSN	10957863
DOI	10.1109/NSSMIC.2009.5402362
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2009-10-24
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Filtering Filters Runtime Computational complexity Signal processing Image processing Hardware Parallel processing Sorting Pipelines
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Hierarchical recursive running median

Adaptive decimated median filters for image processing

Median-based filtering methods for EEG seizure detection

Research on Image Median Filtering Algorithm and Its FPGA Implementation

A new architecture of median filters with linear hardware complexity

High performance median filtering using commodity graphics hardware

Novel FPGA-based implementation of median and weighted median filters for image processing

Generalized median filtering and related nonlinear filtering techniques

A fast weighted median filter architecture for image processing

Branchless vectorized median filtering

Similar Documents

Hierarchical recursive running median

Adaptive decimated median filters for image processing

Median-based filtering methods for EEG seizure detection

Research on Image Median Filtering Algorithm and Its FPGA Implementation

A new architecture of median filters with linear hardware complexity

High performance median filtering using commodity graphics hardware

Novel FPGA-based implementation of median and weighted median filters for image processing

Generalized median filtering and related nonlinear filtering techniques

A fast weighted median filter architecture for image processing

Branchless vectorized median filtering