On the computational complexity of multivariate median filters

被引：19

作者：

Barni, M ^{[1
]}

Cappellini, V ^{[1
]}

机构：

[1] Univ Florence, Dipartimento Ingn Elettr, I-50139 Florence, Italy

来源：

SIGNAL PROCESSING | 1998年 / 71卷 / 01期

关键词：

vector median filters; computational complexity; fast algorithms; multivariate ordering;

D O I：

10.1016/S0165-1684(98)00133-9

中图分类号：

TM [电工技术]; TN [电子技术、通信技术];

学科分类号：

0808 ; 0809 ;

摘要：

Though the noise removal capability of multivariate median filters has been carefully investigated, a comprehensive analysis of their complexity is still missing. In this work, the complexity of the most commonly used multivariate median filters is thoroughly analyzed. For each filter theoretical results are derived and validated against experimental data, proving that computational complexity depends mainly on the approach adopted to sort multivariate samples. Algorithms based on marginal ordering are very fast, whereas the use of an ordering scheme based on the aggregate sum of distances leads to very slow algorithms. An intermediate behavior is observed for filters relying on reduced ordering. A fast algorithm for the implementation of the vector median based on 1-norm is also described which significantly reduces the complexity of this filter. (C) 1998 Elsevier Science B.V. All rights reserved.

引用

页码：45 / 54

页数：10

共 17 条

[1] VECTOR MEDIAN FILTERS [J].

ASTOLA, J ;

HAAVISTO, P ;

NEUVO, Y .

PROCEEDINGS OF THE IEEE, 1990, 78 (04) :678-689

[2] Fast Vector Median Filter Based on Euclidean Norm Approximation [J].

Bami, M. ;

Cappellini, V. ;

Mecocci, A. .

IEEE SIGNAL PROCESSING LETTERS, 1994, 1 (06) :92-94

[3] ORDERING OF MULTIVARIATE DATA [J].

BARNETT, V .

JOURNAL OF THE ROYAL STATISTICAL SOCIETY SERIES A-STATISTICS IN SOCIETY, 1976, 139 :318-354

[4] A fast algorithm for 1-norm vector median filtering [J].

Barni, M .

IEEE TRANSACTIONS ON IMAGE PROCESSING, 1997, 6 (10) :1452-1455

[5]

Barni M., 1995, Proceedings. International Conference on Image Processing (Cat. No.95CB35819), P362, DOI 10.1109/ICIP.1995.529721

[6]

BARNI M, 1992, SIGNAL PROCESS, V6, P1485

[7] Ranking in R(p) and its Use in Multivariate Image Estimation [J].

Hardie, Russell C. ;

Arce, Gonzalo R. .

IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS FOR VIDEO TECHNOLOGY, 1991, 1 (02) :197-+

[8] FAST 2-DIMENSIONAL MEDIAN FILTERING ALGORITHM [J].

HUANG, TS ;

YANG, GJ ;

TANG, GY .

IEEE TRANSACTIONS ON ACOUSTICS SPEECH AND SIGNAL PROCESSING, 1979, 27 (01) :13-18

[9]

NEUVO Y, 1990, SPIE, V1360, P1171

[10] Multichannel L filters based on reduced ordering [J].

Nikolaidis, N ;

Pitas, I .

IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS FOR VIDEO TECHNOLOGY, 1996, 6 (05) :470-482

← 1 2 →