A Tree-Based, Constant-Time Rank-Order Algorithm for Moving Window Filtering Applications
Abstract
An element of rank r is the rth smallest element in a sequence. Rank-order filtering techniques are widely used in signal and image processing for removal of shot or impulse noises. In many applications, a moving window of some fixed size is moved over an endless sequence of elements at a regular step and every time the rank-order element of the window is computed as the filtered output. In this work, we present a tree-based algorithm that can compute any rank-order element in a moving window in constant time. Once the tree is constructed with all elements of the first instance of the moving window, to delete an oldest element, to insert a newest element and then to compute the rank order element takes constant amount of time. Specifically it takes m constant steps, where m is the number of bits used in representing elements in binary.
Recommended Citation
D. C. Kar and S. R. Subramanya, "A Tree-Based, Constant-Time Rank-Order Algorithm for Moving Window Filtering Applications," 15th International Conference on Computer Applications in Industry and Engineering 2002, CAINE 2002, pp. 45 - 48, International Society for Computers and Their Applications, Jan 2002.
Department(s)
Electrical and Computer Engineering
Keywords and Phrases
order-statistic filter; rank-order; sorting; Tree
International Standard Book Number (ISBN)
978-161839535-1
Document Type
Article - Conference proceedings
Document Version
Citation
File Type
text
Language(s)
English
Rights
© 2024 International Society for Computers and Their Applications, All rights reserved.
Publication Date
01 Jan 2002
