Order Statistics In Digital Image Processing
Order Statistics in Digital Image ProcessingIOANNIS PITAS AND ANASTASIOS N. VENETSANOPOULOS, FELLOW, IEEEIn recent years significant advances have been made in thedevelopment of nonlinear image processing techniques. Such techniques are used in digital image filtering, image enhancement, andedge detection. One of the most important families of nonlinearimage filters is based on order shztktics. The widely used medianfilter is the best known filter of this family. Nonlinear filtersbased on order statistics have excellent robustness propertiesin the presence of impulsive noise. They tend to preserve edgeinformation, which is very important to human perception. Theircomputation is relatively easy and fast compared with some linearfilters. All these features make them very popular in the imageprocessing community. Their theoretical analysis is relatively difficultcompared with that of the linear filters. However, several new toolshave been developed in recent years that make this analysis easier.In this review paper an analysis of their properties as well as theiralgorithmic computation will be presented.I. INTRODUCTIONLinear processing techniques are very important toolsthat are used extensively in digital signallimage processing. Their mathematical simplicity and the existence of aunifying linear systems theory make their design and implementation easy. Moreover, linear processing techniquesoffer satisfactory performance for a variety of applications.However, many digital image processing problems cannotbe efficiently solved by using linear techniques.An example where linear digital image processing techniques fail is the case of non-Gaussian andlor signaldependent noise filtering (e.g. impulsive noise filtering).Such types of noise appear in a multitude of digital image processing applications. Impulsive noise is frequentlyencountered in digital image transmission as a consequenceof man-made noise sources or decoding errors. Signaldependent noise is the photoelectron noise of photosensingdevices and the film-grain noise of photographic films[l]. Speckle noise that appears in ultrasonic imaging andin laser imaging is multiplicative noise; i.e. it is signaldependent noise. Another example where linear techniquesfail is the case of nonlinear image degradations. Suchdegradations occur during image formation and duringimage transmission through nonlinear channels [ 11, [5]. TheManuscript received August 29, 1990; revised July 22, 1992.I. Pitas is with the Department of Electrical Engineering, University ofThessaloniki, Thessaloniki 54006, Greece.A. N. Venetsanopoulos is with the Department of Electrical Engineering,University of Toronto, Toronto M5S 1A4, Canada.IEEE Log Number 9206277.human visual perception mechanism has been shown tohave nonlinear characteristics as well [2], [ 5 ] .Linear filters, which were originally used in image filtering applications, cannot cope with the nonlinearities of theimage formation model and cannot take into account thenonlinearities of human vision. Furthermore, human visionis very sensitive to high-frequency information. Imageedges and image details (e.g. corners and lines) have highfrequency content and carry very important information forvisual perception. Filters having good edge and image detailpreservation properties are highly suitable for digital imagefiltering. Most of the classical linear digital image filtershave low-pass characteristics [3]. They tend to blur edgesand to destroy lines, edges, and other fine image details.These reasons have led researchers to the use of nonlinearfiltering techniques.Nonlinear techniques emerged very early in digital imageprocessing. However, the bulk of related research has beenpresented in the past decade. This research area has hada dynamic development. This is indicated by the amountof research presently published and the popularity andwidespread use of nonlinear digital processing in a varietyof applications. Most of the currently available imageprocessing software packages include nonlinear techniques(e.g. median filters and morphological filters). A multiplicity of nonlinear digital image processing techniqueshave appeared in the literature. The following classesof nonlinear digital imagehignal processing techniquescan be identified at present: 1) order statistic filters 2)homomorphic filters, 3) polynomial filters, 4) mathematical morphology, 4) neural networks, and 5) nonlinearimage restoration. One of the main limitations of nonlineartechniques at present is the lack of a unifying theorythat can encompass all existing nonlinear filter classes.Each class of nonlinear processing techniques possesses itsown mathematical tools that can provide reasonably goodanalysis of its performance. Cross-fertilization of theseclasses has been shown to be promising. For example,mathematical morphology and order statistic filters havebeen efficiently integrated in one class, although they comefrom completely different origins.In the following, we shall focus on the description ofthe order statistics techniques. Although such techniqueshave been applied to digital signal processing as well, most0018-9219/92 03.00 0 1992 IEEEPROCEEDINGS OF THE IEEE, VOL. 80, NO. 12, DECEMBER 19921893
of the reported work has been applied to digital imageprocessing. We shall focus our presentation on digital imageprocessing applications, in order to render it more concise.We shall also give links to other nonlinear filter classes,whenever applicable. The class of filters based on orderstatistics is very rich. The best known filter is the medianfilter. It originates from robust estimation theory. It wassuggested by Tukey for time series analysis [6]. Later,it became popular in digital image processing because ofits computational simplicity and its good performance. Itsstatistical and deterministic properties have been studiedthoroughly.Since its first use, several modifications and extensionsof the median filter have been proposed. Many of themhave solid theoretical foundations from the theory of robuststatistics [7]-[9]. However, there are also filters basedon order statistics that have ad hoc structures, due tothe lack of a powerful unifying theory in the area ofnonlinear filtering. Several efforts have been made in thepast decade to provide a unifying theory in the area oforder statistics filtering. Some fruitful results based onthreshold decomposition (to be described later) are expectedto provide useful design and implementation tools. Ingeneral, filters based on order statistics have good behaviorin the presence of additive white noise or impulsive noise,if they are designed properly. Many of them have goodedge preservation properties.The adaptation of order statistics filters is a very important task. It is well known that image characteristics(e.g. local statistics) change from one image region tothe other. Noise characteristics usually vary with time.Thus, digital image filters based on order statistics mustbe spatially and/or temporally adaptive. Furthermore, thecharacteristics of the human visual system (e.g. edge preservation requirements, local contrast enhancement) lead tospatially adaptive digital image filter structures as well.Another reason for the adaptation of the order statisticsfilters has to do with the difficulties encountered in theoptimal design of such filters for certain characteristics ofsignal and noise. Although order statistics filters are basedon rich mathematical foundations, such design algorithmsdo not exist or are difficult to implement.One of the main reasons for the popularity and widespread use of certain filters based on order statistics is theircomputational simplicity. Their computation can becomefaster if appropriate fast algorithms are designed. Severalsuch algorithms have appeared in the literature, especiallyfor the fast (serial or parallel) implementation of the medianfilter. Another research activity is the design of specialVLSI chips for order statistics filtering. A number ofchips for fast median and max/min filtering have beenpresented in the literature. The related efforts for fast filterimplementation are reviewed in this paper as well.The organization of the paper is as follows. Section I1includes the probabilistic and the deterministic propertiesof the median filter and its modifications. The analysis israther detailed, since it provides the tools and methods forthe evaluation of the performance of the rest of the order1894statistics filters. Section 111 gives an overview of severalfilters that are based on order statistics. It also includes thedescription of certain filters that are not based on orderstatistics but are related to them though robust estimationtheory. Adaptive order statistics filters are presented inSection IV. Algorithms and image processor architecturessuitable for fast order statistics filtering are given in SectionV. Conclusions are drawn in Section VI.AND ITS EXTENSIONS11. THE MEDIANFILTERThe median filter is the most popular example of filtersbased on order statistics [4], [5]. Order statistics haveplayed an important role in statistical data analysis andespecially in the robust analysis of data contaminated withoutlying observations, called outliers [4], [7], [8]. One ofthe most important applications of order statistics is robustestimation of parameters [7]-[9]. The median is a prominentexample of robust estimators. In the following, a briefintroduction to some concepts of robust statistics will begiven. This description aims at giving some definitions thatwill be used in the description of the robustness propertiesof the median filter. Let us suppose that the randomvariables X i , i l , . . ,n, are distributed according toa known parametric probability function F(X,e).Suchparameters can be the mean and the standard deviation; i.e.,eT [ p 171.The parameter vector 8 has to be estimatedfrom the observation data X i , i 1 , . . . ,n. Mean andstandard deviation estimations correspond to location andscale estimation. The estimators have the formwhere T ( X 1 , . . , X n ) denotes a function of X I , . * * , X n .Often, there are some observation data (outliers) that havevery different probability distributions from the modelF(X, Therefore, the probability distribution model isonly approximately valid. Robust estimation theory proposes estimators for approximate parametric models, whichminimize the effect of the outliers. An estimator can havetwo robustness measures. The breakdownpoint E* (0 5E 5 1 ) determines the percentage of the outliers, abovewhich the estimator becomes unreliable [7], [8]. If anestimator has breakdown point E* 1/2 (e.g. the median),it is reliable only if less than 50% of the observation dataoutlie from the model distribution. A formal mathematicaldefinition of the breakdown point can be found in [7]. Theinfluence function I F ( x ;T ,F ) of an estimator shows theeffect of a single outlier on the performance of the estimatorat a point 2. It is defined as follows [7]: e).I F ( a ;T ,F ) limT((1-t)F tA,) - T ( F ).tt-0(2)The gross-error sensitivity y* measures the worst effect ofa contamination at any point x :y* sup IIF(z;T ,F)I(3)Xwith sup denoting supremum. If y* is finite, the estimatorT is said to be B-robust at the distribution F . The performance of an estimator is directly related to its outputPROCEEDINGS OF THE IEEE, VOL. 80, NO. 12, DECEMBER 1992
variance, V ( T ,F ) . The smaller the variance, the better theperformance of the estimator. The relative efficiency of twoestimators T ,S at data distribution F is measured by theirasymptotic relative efficiency, ARE(T,S):Input(4)outputHere V ( S ,F ) , V ( T ,F ) are the variances of the estimatorsT , S at the distribution F . The higher A R E ( T , S ) is, thebetter the performance of the estimator T over the estimatorS. The calculation of the ARE of various estimators and itsrelation to the influence function can be found in [7]. Theprevious description of robust estimation concepts is farfrom complete. The interested reader can find more detailsin [5]-[9]. Robust estimation has found significant applications in digital signal processing [141-[24]. An excellentreview in this area is [19]. Having defined some basicnotions of robust estimation, we proceed to the definitionand analysis of the median filters.Let X I ,X,, . . X , be random variables. If they arearranged in ascending order of magnitude, )X(1) I X(2) I . . *IX(n)7(5)X ( * )is called the ith-order statistic. The maximum and theminimum of X i , i 1 , . . . !n are denoted by X(n),X(1)respectively. A very important order statistic is the medianm e d ( X i ) , given by. . . . . . . e . . . . e .m.0.0 . .SQUARECIRCLECROSSX-SHAPE(b)Fig. 1. (a) Filtering of a three-valued sequence by a median filterof length n 3. (b) Windows of two-dimensional median filters.Statistical analysis presents the statistical properties of themedian filter output. Deterministic analysis presents certainstructural properties (e.g. the shape of signals that areinvariant under median filtering).A. Statistical AnalysisIf X i , i 1,. . !n are independent identically distributed (iid) random variables having cumulative densityfunction (cdf) P ( x ) ,the cdf of the r-th order statistic, X(,),is given byA one-dimensional median jilter of size n, n 2u 1,is defined by the following relation [25]:yi med(xi-,, . . . , xi,. , xi v), i E 2,(7)where 2 denotes the set of integers. In most cases, filterwindows having odd length are used, due to the simplicityof the corresponding definition, as can be seen in (6). Thesignal sequence is of finite extent in most practical cases.It is appended by appropriately chosen values (usually 0's)at both ends in order to accommodate boundary problems.An example of filtering a three-level sequence by a medianfilter (7) of length n 3 is shown in Fig. l(a). The inputsequence has been appended by one sample at the beginning and at the end, respectively, to create the necessaryboundary conditions. A two-dimensional median jilter hasthe following definition: i jmed(xi ,,j ,; ( r ,3) E A ) , (4j)E 2'.(8)The set A c Z2 is the filter window. Such windows areshown in Fig. l(b). The window shape influences certainspatial properties of the median filter, e.g. edge and imagedetail preservation. Analog versions of the median filterhave also been defined. Their definition and properties canbe found in [26] and [27]. Having defined the medianfilter, we can proceed to the presentation of its properties.PITAS AND VENETSANOPOULOS: ORDER STATISTICSThe probability density function (pdf) fr(x)of X(,) is givenbyf,(x) .("-r - 11 ) P y x ) [ 1 - P(z)],-'p(z),(10)where p(x) is the pdf of X i , i 1, . . , n. The cdf and pdfof the median can be found from (9) and (10) by substitutingr v 1. It can be easily seen from these relations that theanalytic calculation of the cdf and the pdf of the medianfilter output is cumbersome, even for the iid case. Thisfact makes the theoretical analysis relatively complicated.Numerical methods for the calculation of the pdf and cdfcan be found in [lo] and [ll]. Order statistic distributionshave been used in optimal data sorting [12]. The interestedreader is referred to [4] for the calculation of the expectedvalues and moments of order statistics [13]. As statedpreviously, the output variance is of particular importanceto median filter performance. The smaller the variance, thebetter the filter performance. It has been shown that medianfilters perform well for long-tailed noise distributions(e.g. Laplacian noise), whereas their performance is poorfor short-tailed noise distributions (e.g. uniform noise)[7]-[9]. This fact suggests that the median filter is efficientat removing impulsive noise. The good performance of thee1895
Table 2Table 1 Asymptotic Relative Efficiency of the MedianFilter with Respect to the Arithmetic MeanRate of Failure of the Median Filter in Removing Impulse NoiseWindow SueImpulse Rate .0990.0170.40.3520.3170.2670.1540.50.50.50.50.5 ARE median filter at long-tailed distributions is explained by thefact that it minimizes the L1 norm [5],[9]:a12;- T,Ii l-min.(11)According to (ll), the median is the maximum likelihoodestimate (MLE) of location for the Laplacian distribution:f(2) 1ne-’z’.Lof existence p in a constant image neighborhood, theprobability of correct reconstruction, P ( n ,p ) , is given by1251Traditionally, the median filter performance is compared tothe performance of the moving average filter:(15)The probabilities of erroneous reconstruction, 1 - P(n,p),are given in Table 2. It can be seen that a 3 x 3 medianfilter (n 9) can reject impulses having 30% probability ofoccurrence with probability of success over 90%. Figure 2illustrates that the median removes impulses efficiently,whereas the moving average fails to do so.The median filter has low-pass characteristics if its inputis white additive noise, as can be found by examining theautocorrelation function and the power spectrum of its output [ 5 ] , [28]. The autocorrelation function can be calculatednumerically by the joint pdf of the filter output [28]-[30]. Inthe case of nonwhite input noise, the evaluation of medianfilter performance is much more difficult. Its performanceis certainly inferior to that of the moving average filter [25].As stated in the introduction, edge information is veryimportant for human perception. Therefore, its preservationand, possibly, its enhancement constitute a very important subjective feature of the performance of an imagefilter. Edges, by definition, contain high frequencies. Therefore, low-pass linear filters, e.g. the moving average filter,smooth them and produce images which are unpleasant tothe eye. In contrast, the median filter tends to preservethe edge sharpness, owing to its robustness properties. Anidealized noisy vertical edge model of height h is shown inFig. 3(a). It is described by the following equation:and it is unbounded. Therefore, the moving average filter isvery susceptible to impulses. The breakdown point of themedian is E* 1/2. The median becomes unreliable onlyif more than 50% of the data are outliers. The arithmeticmean has E* 0. Even a single outlier can destroy itsperformance.The statistical and robustness properties of the medianmake it very suitable for impulsive noise filtering. Theperformance of the median in impulsive noise filtering canbe measured by the probability of correct signal reconstruction. If the impulses have constant value and probabilitywhere h denotes the edge height and zij is white noise.It is clearly seen, by comparing parts (b) and (c) ofFig. 3, that the median filter preserves edges much betterthan the moving average filter. Figure 4 shows an imagecorrupted by additive Gaussian noise. The 7 x 7 medianfilter produces a much more pleasant output than that ofa 7 x 7 moving average filter, because it does not bluredges. However, the median filter output contains more. .3 t--Ywhich is essentially a “moving” arithmetic mean. Thearithmetic mean is the MLE estimate of location for theGaussian distribution and it minimizes the L2 norm. Theasymptotic relative efficiency of the median versus thearithmetic mean ARE(med(si),Z) (4) is shown in Table 1.It can easily be seen that the median is more efficient forlong-tailed distributions, whereas the arithmetic mean ismore efficient for the Gaussian distribution and for shorttailed distributions. This means that the moving averagefilter performs better than the median filter in additiveGaussian noise removal [5], [25]. The ARE(med(zi),3 )for various other distributions can be found in [5] and [9].The median is a B-robust operator, because its influencefunction is bounded [7]:Therefore, a single outlier (e.g. impulse)
widespread use of nonlinear digital processing in a variety of applications. Most of the currently available image processing software packages include nonlinear techniques (e.g. median filters and morphological filters). A multi- plicity of nonlinear digital image processing techniques have appeared in the literature.
Digital Image Fundamentals Titipong Keawlek Department of Radiological Technology Naresuan University Digital Image Structure and Characteristics Image Types Analog Images Digital Images Digital Image Structure Pixels Pixel Bit Depth Digital Image Detail Pixel Size Matrix size Image size (Field of view) The imaging modalities Image Compression .
L2: x 0, image of L3: y 2, image of L4: y 3, image of L5: y x, image of L6: y x 1 b. image of L1: x 0, image of L2: x 0, image of L3: (0, 2), image of L4: (0, 3), image of L5: x 0, image of L6: x 0 c. image of L1– 6: y x 4. a. Q1 3, 1R b. ( 10, 0) c. (8, 6) 5. a x y b] a 21 50 ba x b a 2 1 b 4 2 O 46 2 4 2 2 4 y x A 1X2 A 1X1 A 1X 3 X1 X2 X3
A digital image is a 2D representation of a scene as a finite set of digital values, calledpicture elements or pixels or pels. The field of digital image processing refers to processing digital image by means of a digital computer. NOTE: A digital image is composed of finite number of elements like picture elements, image
Digital image processing is the use of computer algorithms to perform image processing on digital images. As a . Digital cameras generally include dedicated digital image processing chips to convert the raw data from the image sensor into a color-corrected image in a standard image file format. I
Actual Image Actual Image Actual Image Actual Image Actual Image Actual Image Actual Image Actual Image Actual Image 1. The Imperial – Mumbai 2. World Trade Center – Mumbai 3. Palace of the Sultan of Oman – Oman 4. Fairmont Bab Al Bahr – Abu Dhabi 5. Barakhamba Underground Metro Station – New Delhi 6. Cybercity – Gurugram 7.
Corrections, Image Restoration, etc. the image processing world to restore images [25]. Fig 1. Image Processing Technique II. TECHNIQUES AND METHODS A. Image Restoration Image Restoration is the process of obtaining the original image from the degraded image given the knowledge of the degrading factors. Digital image restoration is a field of
DIGITAL IMAGE FUNDAMENTALS & IMAGE TRANSFORMS The field of digital image processing refers to processing digital images by means of a digital computer. An image may be defined as a two- dimensional function, f(x,y) where x and y are spatial (plane) coordinates, and the amplitude of f at any pair of coordinates (x, y) is called the intensity or .
Java Digital Image Processing 1 Digital Image Processing (DIP) deals with manipulation of digital images using a computer. It is a subfield of signals and systems but focuses particularly on images. DIP focuses on developing a computer system that is able to perform processing on an image. The input of such system is a digital image.
