Fast computation of a class of running filters

Author

Coltuc, Dinu ; Pitas, Ioannis

Author_Institution

Res. Inst. for Electr. Eng., Bucharest, Romania

Volume

46

Issue

3

fYear

1998

fDate

3/1/1998 12:00:00 AM

Firstpage

549

Lastpage

553

Abstract

This paper focuses on the computation of a class of running filters defined as the n-ary extension of an associative, commutative, and idempotent binary operation T on an ordered sequence of operands. The well-known max/min filters are the prominent representatives of the class. For any arbitrary window filter of size n, the existence of a fast algorithm of complexity O(log₂ n) T operations is proven. A remarkable feature of the proof is its ability to generate a particular solution for every n. In addition to the theoretical results, practical implementation aspects regarding the flexibility of pipeline processors for fast computation of the one-dimensional (1-D) and two-dimensional (2-D) running filters are investigated

Keywords

computational complexity; digital filters; pipeline processing; two-dimensional digital filters; associative operation; commutative operation; complexity; fast computation; idempotent binary operation; max/min filters; n-ary extension; one-dimensional running filters; operands; pipeline processors; two-dimensional running filters; window filter; Arithmetic; Computational complexity; Delay; Filters; Informatics; Lattices; Partitioning algorithms; Pipelines; Signal processing; Two dimensional displays;

fLanguage

English

Journal_Title

Signal Processing, IEEE Transactions on

Publisher

ieee

ISSN

1053-587X

Type

jour

DOI

10.1109/78.661323

Filename

661323